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

姓名 小明

一、需求分析

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; }