数据结构试验二第五组

《数据结构试验二第五组》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实验二线性表操作小组名称：第5组组长：韩威言小组成员：JB164025程功JB164013陈鑒玮负责需求分析、测试JB164025程功定义结构体JB164071孙瑞瑞定义链表中的函数JB164013陈縈玮定义顺序表中的函数JB164067韩威言负责编写主函数菜单JB164015丁志毅JB164071孙瑞瑞负责实验报告完成时间：2018-3-27一、需求分析1、程序设计的任务：1.掌握用C语言调试程序的基本方法。2.掌握线性表的基本运算，如插入、删除等。2、演示程序以用户和计算机的对话方式执行，即

2、在计算机终端上显示“线性表的操作”菜单之后，由用户根据菜单在键盘上输入想要执行的操作，然后分步显示每一个操作的结果。3、程序执行的命令包括：1.线性表在顺序存储结构上的插入元素，删除元素运算2.单链表的建链表，插入结点，删除结点运算3.循环链表的建链表，插入结点，删除结点运算4.双向链表的建链表，插入结点，删除结点运算5.一元多项式的创建、输出、相加、相减、相乘运算。4、测试数据顺序表节点数8,数据元素1,2,3,4,5,6,7,8。链表长度8,数据元素1,2,3,4,5,6,7,8。二、概要设

3、计1、抽象数据类型定义：ADTList{数据对象：D={ai

4、aiEElcmSet,i=l,2,...,n,n>=0}数据关系：Rl={

5、ai-1,aiED,i=2,,n}基本操作：InitList(&L)操作结果：构造一个空的线性表L。Listlnsert(&L,i,e)初始条件：线性表L己存在，KiSLengthList(L)+l。操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。ListDelete(&L，i,&e)初始条件：线性表L己存在且非空，l

6、gthList(L)。操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。GetElem(&L,i,&e)初始条件：线性表L己存在，KiSLengthList(L)。操作结果：用e返［HlL中第i个元素的。ListLength(L)初始条件：线性表L己存在。操作结果：返回L屮数据元素个数。ClearList(&L)初始条件：线性表L已存在。操作结果：将L重置为空表。}ADTList2、本程序包含的程序模块：三、详细设计1、基本信息声明ftdefineTRUE1ttdefineFALSE0

7、#defineOK1#defineERROR0^defineINFEASIBLE-1#defineOVERFLOW-2ttdefineLISTINITSIZE50^defineLISTINCREMENT10//结构体//typedefintStatus;typcdcfintElcmTypc;typedefstruct{ElemType氺elem;intlength;intlistsize;}SqList;typcdcfstructlink{intdata;structlink氺next;}lin

8、k，*linklist;2、相关算法声明、定义(1)构建线性表StatusInitListSq(SqList氺L){inti,a;L->clcm=(ElemType*)malloc(LIST_INIT_SIZE*sizcof(ElemType));//分配空间if(!L->elem)exit(OVERFLOW);//若存储分配失败,返回-2L->length=0;//空表，长度为0I->listsize=LTST_TNIT_STZR;//初始存储容量printf("请输入结点数：");scanf

9、(〃％d〃，&a);printf(〃请输入数据:〃)；for(i=0;ilength)++；}returnOK;}(2)线性表插入StatusListInscrt_Sq(SqList*L,inti,ElemTypec){int*q=&(L-〉elem[i-l]);ElemType氺newbase,氺p;if(i

10、

11、i>L->length+l)returnERROR;//检查i值是否合理//将线性表第i个元素之后的所有

12、元素向后移动if(L-〉length〉=L-〉listsize)newbase=(ElemType氺)realloc(L->elem,(L->1istsize+LISTINCREMENT)氺sizeof(ElemType));if(!newbase)exit(OVERFLOW);L->elem=newbase;L->listsize+=LISTINCREMENT;}q=&(L->elem[i-1]);for(p=&(L->elem[L->length-l]);p>=q;—p)*(p+l)=氺p;