线性表的建立

线性表的建立线性表的建立线性表的建立资料仅供参考文件编号：2022年4月线性表的建立版本号：A修改号：1页次：1.0审核：批准:发布日期：线性表的建立、插入和删除班级：计科021姓名：罗晶晶学号：03日期：2005/4/25实验题目：1、建立一个顺序存储的线性表，实现线性表的插入、删除操作2、建立一个单链表，实现单链表的插入、删除操作运行环境：visualC++需求分析程序的功能：（1）建立一个按关键字有序的线性表，从键盘上输入一个数，将该数插入到表中，使该线性表插入数据后仍按关键字有序。（2）建立一个线性表，从键盘上输入一个数，查找表中是否存在该数，若有则删除所有与该数相等的数。测试数据：顺序存储的线性表：已建立一个有序的线性表为：１３３４９请输入要插入的数据：８插入数据后的顺序表为：１３３４８９请输入要删除的数据：３删除后的顺序表为：１４８９单链表：请输入记录，输入0则结束：120现在链表中的2个记录是：12请输入要插入的记录：1现在链表中的3个记录是：1120请输入要删除的数据：1删除了：1现在链表中的2个记录是：12概要设计顺序表的抽象数据类型的定义：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详细设计采用c语言定义相关的数据类型；#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{int*elem; intlength; intlistsize;}SQLIST;其中部分操作的伪码算法如下：voidCreate(SQLIST&L)//建立线性表{=(int*)malloc(LIST_INIT_SIZE*sizeof(int)); if(! printf("为线性表分配空间失败!"); =0; =LIST_INIT_SIZE;}voidInsert(SQLIST&A,intx)//实现有序的插入操作{if==printf("线性表错误!");if(x>[]) []=x; else { inti=0; while(x>=[i]) i++; for(intj=;j>=i;j--) [j+1]=[j]; [i]=x; } ++;}voidlistdelete(SQLIST&L,intx)//实现有序的删除操作{ inti=0; if==0)cout<<"ERROR"<<endl; while(i<= { if[i]==x) { for(intj=i+1;j<=;++j)[j-1]=[j]; ; } else i++; }3、#include<>#include<>typedefstructstudent//单链表的存储结构{ longnum; structstudent*next;}LINK;调试分析调试中遇到的问题及对问题的解决方法:在线性表中删除一个元数时，要判断是否有重复的数据，有重复的话就要全部删除，解决的方法是写一个判断的for语句。算法的时间复杂度和空间复杂度。在长度为n的顺序表中插入一个元数的时间复杂度为0（n），删除一个元数的时间复杂度为0（n）测试结果顺序存储的线性表单链表源程序（带注释）1、顺序表的操作程序#include<>#include<>#include<>#include<>#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{ int*elem; intlength; intlistsize;}SQLIST;voidCreate(SQLIST&L)//建立线性表{ =(int*)malloc(LIST_INIT_SIZE*sizeof(int)); if(! printf("为线性表分配空间失败!"); =0; =LIST_INIT_SIZE;}voidInsert(SQLIST&A,intx)//实现有序的插入操作{ if==printf("线性表错误!"); if(x>[]) []=x; else { inti=0; while(x>=[i]) i++; for(intj=;j>=i;j--) [j+1]=[j]; [i]=x; } ++;}voidlistdelete(SQLIST&L,intx)//实现有序的删除操作{ inti=0; if==0)cout<<"ERROR"<<endl; while(i<= { if[i]==x) { for(intj=i+1;j<=;++j)[j-1]=[j]; ; } else i++; }cout<<"\nOK\n删除后的顺序表为:\n"<<endl;}voidmain(){ SQLISTs; Create(s); [0]=1; [1]=3; [2]=3; [3]=4; [4]=9; =5;printf("\n\n----------------------------------------顺序表为---------------------------------------\n"); printf("\n\n已建立的顺序表为:\n"); for(inti=0;i<;i++) printf("%d",[i]); printf("\n\n请输入要插入的数据:\n"); inttmp; scanf("%d",&tmp); Insert(s,tmp); printf("\n\n插入数据后的顺序表为:\n"); for(i=0;i<;i++) printf("%d",[i]);printf("\n\n请输入要删除的数据:\n");intj; cin>>j;listdelete(s,j); for(intt=0;t<;t++) printf("%d",[t]);getch();}2、单链表表的操作程序#include<>#include<>typedefstructstudent//单链表的存储结构{ 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->num<p1->num) { if(head==p1)head=p0; else p2->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个结点 else p2->next=p1->next; printf("删除了:%ld",num); n=n-1; } else printf("没有找到%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("%1d",&stu->num); while(stu->num!=0) { head=Insert(head