线性表的建立

线性表的建立、插入和删除班级：计科021姓名：罗晶晶学号：0207110183日期：2005/4/25实验题目：1、建立一个顺序存储的线性表，实现线性表的插入、删除操作2、建立一个单链表，实现单链表的插入、删除操作一、运行环境：visualC++二、需求分析1．程序的功能：（1）建立一个按关键字有序的线性表，从键盘上输入一个数，将该数插入到表中，使该线性表插入数据后仍按关键字有序。（2）建立一个线性表，从键盘上输入一个数，查找表中是否存在该数，若有则删除所有与该数相等的数。2．测试数据：顺序存储的线性表：已建立一个有序的线性表为：１３３４９请输入要插入的数据：８插入数据后的顺序表为：１３３４８９请输入要删除的数据：３删除后的顺序表为：１４８９单链表：请输入记录，输入0则结束：120现在链表中的2个记录是：12请输入要插入的记录：1现在链表中的3个记录是：1120请输入要删除的数据：1删除了：1现在链表中的2个记录是：12三、概要设计1．顺序表的抽象数据类型的定义：ADTList{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}{称n为线性表的表长;称n=0时的线性表为空表。}数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}{设线性表为(a1，a2,...，ai，...，an),称i为ai在线性表中的位序。}基本操作：InitList(&L)操作结果：构造一个空的线性表L。DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则FALSE。ListLength(L)初始条件：线性表L已存在。操作结果：返回L中元素个数。GetElem(L,i,&e)初始条件：线性表L已存在，且1≤i≤LengthList(L)。操作结果：用e返回L中第i个元素的值。LocateElem(L,e,compare())初始条件：线性表L已存在，e为给定值，compare()是元素判定函数。操作结果：返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。ListTraverse(L,visit())初始条件：线性表L已存在，Visit()为某个访问函数。操作结果：依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。ListInsert(&L,i,e)初始条件：线性表L已存在，且1≤i≤LengthList(L)+1。操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。ListDelete(&L,i,&e)初始条件：线性表L已存在且非空，1≤i≤LengthList(L)。操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。}ADTList四、详细设计1．采用c语言定义相关的数据类型；#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{int*elem;intlength;intlistsize;}SQLIST;2．其中部分操作的伪码算法如下：voidCreate(SQLIST&L)//建立线性表{L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));if(!L.elem)printf(为线性表分配空间失败!);L.length=0;L.listsize=LIST_INIT_SIZE;}voidInsert(SQLIST&A,intx)//实现有序的插入操作{if(A.length==A.listsize)printf(线性表错误!);if(xA.elem[A.length-1])A.elem[A.length]=x;else{inti=0;while(x=A.elem[i])i++;for(intj=A.length;j=i;j--)A.elem[j+1]=A.elem[j];A.elem[i]=x;}A.length++;}voidlistdelete(SQLIST&L,intx)//实现有序的删除操作{inti=0;if(L.length==0)coutERRORendl;while(i=L.length){if(L.elem[i]==x){for(intj=i+1;j=L.length-1;++j)L.elem[j-1]=L.elem[j];L.length--;}elsei++;}3、#includestdio.h#includestdlib.htypedefstructstudent//单链表的存储结构{longnum;structstudent*next;}LINK;五、调试分析1．调试中遇到的问题及对问题的解决方法:在线性表中删除一个元数时，要判断是否有重复的数据，有重复的话就要全部删除，解决的方法是写一个判断的for语句。2．算法的时间复杂度和空间复杂度。在长度为n的顺序表中插入一个元数的时间复杂度为0（n），删除一个元数的时间复杂度为0（n）六、测试结果顺序存储的线性表单链表七、源程序（带注释）1、顺序表的操作程序#includestdio.h#includemalloc.h#includeconio.h#includeiostream.h#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{int*elem;intlength;intlistsize;}SQLIST;voidCreate(SQLIST&L)//建立线性表{L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));if(!L.elem)printf(为线性表分配空间失败!);L.length=0;L.listsize=LIST_INIT_SIZE;}voidInsert(SQLIST&A,intx)//实现有序的插入操作{if(A.length==A.listsize)printf(线性表错误!);if(xA.elem[A.length-1])A.elem[A.length]=x;else{inti=0;while(x=A.elem[i])i++;for(intj=A.length;j=i;j--)A.elem[j+1]=A.elem[j];A.elem[i]=x;}A.length++;}voidlistdelete(SQLIST&L,intx)//实现有序的删除操作{inti=0;if(L.length==0)coutERRORendl;while(i=L.length){if(L.elem[i]==x){for(intj=i+1;j=L.length-1;++j)L.elem[j-1]=L.elem[j];L.length--;}elsei++;}cout\nOK\n删除后的顺序表为:\nendl;}voidmain(){SQLISTs;Create(s);s.elem[0]=1;s.elem[1]=3;s.elem[2]=3;s.elem[3]=4;s.elem[4]=9;s.length=5;printf(\n\n----------------------------------------顺序表为---------------------------------------\n);printf(\n\n已建立的顺序表为:\n);for(inti=0;is.length;i++)printf(%d,s.elem[i]);printf(\n\n请输入要插入的数据:\n);inttmp;scanf(%d,&tmp);Insert(s,tmp);printf(\n\n插入数据后的顺序表为:\n);for(i=0;is.length;i++)printf(%d,s.elem[i]);printf(\n\n请输入要删除的数据:\n);intj;cinj;listdelete(s,j);for(intt=0;ts.length;t++)printf(%d,s.elem[t]);getch();}2、单链表表的操作程序#includestdio.h#includestdlib.htypedefstructstudent//单链表的存储结构{longnum;structstudent*next;}LINK;intn;//定义一个全局变量(链表的结点个数)LINK*Create()//建立{LINK*head;LINK*p1,*p2;n=0;p1=p2=(LINK*)malloc(sizeof(LINK));scanf(%ld,&p1-num);head=NULL;while(p1-num!=0){n=n+1;if(n==1)head=p1;else//p1指向新开的结点,p2指向链表中的最后一个结点p2-next=p1;//把p1所指的结点连在p2所指结点的后面p2=p1;//p2指向链表中的最后一个结点p1=(LINK*)malloc(sizeof(LINK));scanf(%ld,&p1-num);}p2-next=NULL;returnhead;}LINK*Insert(LINK*head,LINK*stud)//插入{LINK*p0,*p1,*p2;p1=head;//p1指向第一个结点p0=stud;//p0指向待插入的结点if(head==NULL){head=p0;p0-next=NULL;}else{while((p0-num=p1-num)&&(p1-next!=NULL)){p2=p1;//p2指向p1刚才所指的结点p1=p1-next;}if(p0-nump1-num){if(head==p1)head=p0;elsep2-next=p0;p0-next=p1;}else{p1-next=p0;p0-next=NULL;}}n=n+1;returnhead;}LINK*Delete(LINK*head,longnum)//删除{LINK*p1,*p2;if(head==NULL){printf(链表为空!\n\n);return(head);}p1=head;//p1指向第一个结点while(num!=p1-num&&p1-next!=NULL)//如果要删除的不是第一个接点，{p2=p1;//将p1赋给p2，使p2指向刚才检查过的结点p1=p1-next;//p1指向下一个结点}if(num==p1-num)//如果删除的是第一个结点{if(p1==head)head=p1-next;//head指向原来的第2个结点elsep2-next=p1-next;printf(删除了:%ld,num);n=n-1;}elseprintf(没有找到%ld,num);return(head);}voidprint(LINK*head)//输出{LINK*p;printf(\n现在链表中的%1d个记录是:\n,n);p=head;if(head!=NULL)do{printf(%ld\n,p-num);p=p-next;}while(p!=NULL);}voidmain(){printf(\n---------------------------------单链表的操作---------------------------------\n\n);LINK*head,*stu;longDelete_num;printf(请输入记录,输入0则结束:\n\n);head=Create();//建立操作print(head);printf(请输入要插入的记录:\n);//插入操作stu=(LINK*)malloc(sizeof(LINK));scanf