您的当前位置:首页正文

线性表的基本操作 实验报告

来源:个人技术集锦
实验1 线性表的基本操作

姓名 小明

一、需求分析

1.程序的功能:实现基本线性表的运算:插入数据,删除数据,查找数据,求顺序表长度,遍历链表。

2.输入输出的要求:数据必须为整数并大于0,插入数据必须为一位整数; 3.测试数据

测试数据可由使用者自己输入。

二、概要设计

1.本程序所用的抽象数据类型的定义:由顺序表,结构体通过指针连接组成; 2.主程序的流程及各程序模块之间的层次关系。 选择操作 输 入 初始 元 素 1.定义相关的数据类型:

结构体链表SqList,其中包含

删除数据插入数据查找数据比较数据求长度退 出

然后根据各个选项调用所需函数

三、详细设计

ElemType *elem; int length;int listsize; 2.写出各模块的伪码算法; 插入数据:

Status ListInsert(Sqlist &L,int i,ElemType e) {

int *q=&(L.elem[i-1]); ElemType *newbase,*p; if(i<1||i>(L.length+1)) return ERROR; if(L.length>=L.listsize) {

newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase)exit(OVERFLOW); L.elem=newbase;

L.listsize+=LISTINCREMENT; }

for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; *q=e; ++L.length; return OK; }

删除数据:

Status ListDelete(Sqlist &L,int i,ElemType e) {

if(i<1||(i>L.length)) return ERROR; ElemType *p,*q; p=&(L.elem[i-1]);

e=*p;

q=L.elem+L.length-1; for(++p;p<=q;++p) *(p-1)=*p; --L.length; return OK; } 求表长:

int ListLength(Sqlist L) {

return L.length; }

Status GetElem(Sqlist &L,int i) {

if(i<0||i>L.length) }

查找数据:

Status GetElem(Sqlist &L,int i) {

if(i<0||i>L.length) }

int LocationElem(Sqlist L,ElemType element) {

exit(OVERFLOW);

exit(OVERFLOW);

return L.elem[i-1];

return L.elem[i-1];

int i=0;

for(i=0;iif(L.elem[i]==element)

printf(\"第%d个元素为%d.\\n\

return i; }

3.画出函数的调用关系图。 调 用 PrintLis 调用ListDelete 调用ListInser 调用GetElem 调用LocationElem 调用ListLength 谢谢使用 1 2 3 4 5 6 0 菜单

四、使用说明及测试结果 1输入初始元素值:

2删除数据

删除数据1

3、插入数据

插入数据1

4、查找数据

查找数据3

5、求长度

0退出

六、源程序

#include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2

#define LIST_INIT_SIZE 5 #define LISTINCREMENT 1

typedef int Status; typedef int ElemType;

typedef struct {

ElemType *elem; //存储空间基址 int length; //当前长度

int listsize; //当前分配的存储容量 }Sqlist;

static Sqlist L;

static ElemType element;

Status InitList(Sqlist &L) {

L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem)exit(OVERFLOW); L.length=0;

L.listsize=LIST_INIT_SIZE ; return OK; }

Status DestroyList(Sqlist &L) {

if(L.elem==NULL) return ERROR; else

free(L.elem); return OK; }

Status ClearList(Sqlist &L) {

if(L.elem==NULL) exit(ERROR);

int i;

ElemType *p_elem=L.elem; for(i=0;i*L.elem=NULL; L.elem++; }

L.elem=p_elem; return OK; }

Status ListEmpty(Sqlist L) { int i;

ElemType *p_elem=L.elem; for(i=0;iif(*L.elem!=0) {

L.elem=p_elem; return FALSE; } L.elem++; }

return TRUE; }

int ListLength(Sqlist L) {

return L.length;

}

Status GetElem(Sqlist &L,int i) {

if(i<0||i>L.length)

exit(OVERFLOW);

return L.elem[i-1]; }

int LocationElem(Sqlist L,ElemType element) { int i=0;

for(i=0;iprintf(\"第%d个元素为%d.\\n\return i; }

Status ListInsert(Sqlist &L,int i,ElemType e) {

int *q=&(L.elem[i-1]); ElemType *newbase,*p; if(i<1||i>(L.length+1)) return ERROR; if(L.length>=L.listsize) {

newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));

if(!newbase)exit(OVERFLOW);

L.elem=newbase;

L.listsize+=LISTINCREMENT; }

for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; *q=e; ++L.length; return OK; }

Status ListDelete(Sqlist &L,int i,ElemType e) {

if(i<1||(i>L.length)) return ERROR; ElemType *p,*q; p=&(L.elem[i-1]); e=*p;

q=L.elem+L.length-1; for(++p;p<=q;++p) *(p-1)=*p; --L.length; return OK; }

void PrintList(Sqlist L) {

for(int i=0;i//***********************主函数******************************// void main() { int i; Sqlist La; InitList(La);

printf(\"请输入%d个初始元素值:\for(i=0;i<=4;i++) {scanf(\"%d\La.length++;}

printf(\"存入的结果为:\"); PrintList(La); menu:

printf(\"\\n\\n*************请选择要对线性表进行的操作:*************\\n1 显示,2 删除,3 插入,4 查找,5 比较,6 长度,0 退出\\n请选择操作序号:\");

int flag;

scanf(\"%d\switch(flag) { case 1: printf(\"\\n\"); PrintList(La); break; case 2:

printf(\"\\n请输入要删除元素的位置:\"); scanf(\"%d\ElemType e; ListDelete(La,i,e);

printf(\"改变后的线性表:\");

PrintList(La); break; case 3:

{printf(\"\\n请输入要插入的元素:\"); ElemType e; scanf(\"%d\

printf(\"请输入要插入的位置:\"); scanf(\"%d\ListInsert(La,i,e);

printf(\"改变后的线性表:\"); PrintList(La);} break; case 4:

printf(\"\\n请输入要查找元素的位置:\"); int i;

scanf(\"%d\e=GetElem(La,i);

printf(\"第%d个元素的值是:%d\\n\break; case 5: int m;

printf(\"\\n请输入比较的元素:\"); scanf(\"%d\LocationElem(La,m); break; case 6:

printf(\"\\n线性表元素个数为:%d\\n\break; default:

printf(\"\\n输入的选择不存在!\\n\");

break; case 0:

printf(\"\\n谢谢使用!\\n\"); return; }

goto menu; }

因篇幅问题不能全部显示,请点此查看更多更全内容