数据结构线性表设计代码Word格式文档下载.docx

1、SqList Lx;Status InitList_Sq（SqList&L） /分配空间 L.elem=new ElemTypeLIST_INIT_SIZE; if（!L.elem）exit（OVERFLOW）; L.length =0; L.listsize=LIST_INIT_SIZE; return OK;Status ListInsert（SqList&L,inti,ElemType e） /插入新元素 int *q,*p;ElemType *newbase; if（iL.length+1） return ERROR; if（L.length=L.listsize） newbase=n

2、ew ElemTypeL.listsize+LISTINCREMENT;newbase） exit（OVERFLOW）; L.elem=newbase; L.listsize+=LISTINCREMENT; q=&（L.elemi-1）; for （p=&（L.elemL.length-1）;p=q;-p） *（p+1）=*p; *q=e; +L.length;Status Listlength（SqList L） /长度 int *p=L.elem; /判断线形表是否存在 while（p） return （L.length）;Status GetElem（SqList L, inti,Ele

3、mType&e） /取元素 if（iL.length） return ERROR; else e=L.elemi-1; return e;void MergeList（SqListLa,SqListLb,SqList&Lc） /合并 ElemTypeai,bj; InitList_Sq（Lc）; int i=1,j=1,k=0; intLa_len,Lb_len; La_len=Listlength（La）; Lb_len=Listlength（Lb）; while（i=La_len）&（j=Lb_len） GetElem（La,i,ai）;GetElem（Lb,j,bj）; if（ai=bj

4、） ListInsert（Lc,+k,ai）;+i; else ListInsert（Lc,+k,bj）;+j; while（i=La_len） GetElem（La,i+,ai）; ListInsert（Lc,+k,ai）; while（j=Lb_len） GetElem（Lb,j+,bj）; ListInsert（Lc,+k,bj）;void show（SqListL,int i） /显示 intj;ElemType k;cout顺序表显示如下:endl;for（j=0;ji-1;j+） k=L.elemj;k;if（j=i-1 & i0） coutk;void create（SqList

5、&L,int n） /输入元素 int e; for（int i=0;ie; L.elemi=e; L.length=i+1;Status ListDelete_Sq（SqList&L,inti,ElemType&e） /删除 ElemType *p, *q;L.length） return ERROR; p=& e=*p; q=L.elem+L.length-1; for（+p;pa;请输入顺序表的元素（共a个）create（L1,a）;show（L1,a）; void chaxun（SqList&L1） /取第i个位置的元素ElemType e1;请选择所要取出元素的位置:j;while（

6、jListlength（L1） cout输入有误，请重新输入 cout GetElem（L1,j,e1）;取出的元素为:e1void xiugai（SqList&L1） /修改第i个位置的元素 int j; ElemType e1; a=L1.length;请选择所要修改元素的位置: cout要修改成的元素:e1; Listxiugei（L1,j,e1）;修改后的顺序表数据: show（L1,a）;void shanchu（SqList&L1） /删除顺序表里的元素请选择所要删除元素的位置: ListDelete_Sq（L1,j,e1）; show（L1,a-1）;void charu（SqL

7、ist&L1） /插入元素到顺序表里请选择所要插入元素的位置:要插入的元素: ListInsert（L1,j,e1）; show（L1,a+1）;void hebing（SqList&L3） /合并两个顺序表 SqList L1,L2;inta,b;InitList_Sq（L1）; InitList_Sq（L2）;请输入第一个有序表的长度：请输入第一个有序表的元素（共请输入第二个有序表的长度：b;请输入第二个有序表的元素（共bchoice;switch（choice） case 1: shuru（Lx）;break;case 2: show（Lx,Lx.length）; case 3:顺序表的

8、长度:Listlength（Lx）next=NULL; /建立一个带头结点的单链表LinkList q=L; /使q指向表尾 for（int i=1;=n; p=new LNode;p-data; p- q-next=p; q=p;Status GetElem（LinkListL,inti,ElemType&e）/取第i个元素 LinkList p=L-next; int j=1; while（p&i） p=p- +j;p|ji） return error; /第i个元素不存在 e=p- return ok;Status LinkInsert（LinkList&L,inti,ElemType

9、e） /插入 LinkList p=L; int j=0;i-1） +j; /寻找第i-1个结点i-1） return error; /i小于1或者大于表长加1 LinkList s=new LNode; /生成新结点 s-data=e;next=p- /插入L中 p-next=s;Status ListDelete（LinkList&e） / 删除 LinkList q; while（p-next& /寻找第i个结点，并令p指向其前驱 p=p-（p-next）|ji-1） return error; /删除位置不合理 q=p-next=q- /删除并释放结点 e=q- delete（q）;v

10、oidMergeList（LinkList&La,LinkList&Lb,LinkList&Lc） /合并两个顺序链表 LinkListpa,pc,pb; pa=La- pb=Lb- Lc=pc=La; while（pa&pb） if（pa-datadata） pc-next=pa; pc=pa; pa=pa-elsenext=pb; pc=pb; pb=pb- pc-next=pa?pa:pb;delete（Lb）; void show（LinkList L） /显示 p=L-while（p）- p=p-int Length（LinkListL,int i） /表长 i=0; LinkLis

11、t p=L- +i;return i;void xiugai（LinkList L） /修改 inti,j=1; ElemType k; ElemTypee,m;请输入要修改的元素位置（0length）:i; GetElem（L,i,e）;该位置的元素:edata=k;修改后的单链表显示如下: show（L）;void hebing（） /合并两个单链表 inta,b;LinkListLa,Lb,Lc;请输入第一个有序链表的长度:请输入第一个有序链表的元素共（个）： CreateList（La,a）;show（La）;请输入第二个有序链表的长度:请输入第二个有序链表的元素共（ CreateLi

12、st（Lb,b）;show （Lb）; MergeList（La,Lb,Lc）;合并后的有序链表如下：show（Lc）;void main（） /主函数 int select; int x; ElemType y; LinkList list; for（; 单链表的基本操作 1.单链表的创建 2.单链表的显示 3.单链表的长度 6.插入元素到单链表里 7.删除单链表里的元素 8.合并两个单链表请选择:select; switch（select）请输入单链表的长度: cinx;请输入x个元素 CreateList（list,x）; break; case 2:单链表显示如下: show（list

13、）; break; int s; cout单链表的长度为:Length（list,s） case 4: while（xLength（list,s） GetElem（list,x,y）;该位置的元素为:y case 5: xiugai（list）; break; case 6:请选择要插入的位置:要插入的元素值:y; LinkInsert（list,x,y）;插入后单链表显示如下: case 7:请选择要删除的位置:ListDelete（list,x,y）;要删除的元素值:删除后的单链表显示如下: case 8: hebing（）; exit（0）; default :单链表的创建如下图2-4单

14、链表的显示如下图2-5单链表的插入如下图2-6单链表的删除如下图2-6算法分析：针对上述程序，线性表采用顺序存储，插入操作采用平均移动次数，算法时间复杂性都为：O（n）六、心得体会在这次设计的过程中，我还遇到了，很多的问题。顺序表是按顺序存储的，用了一维数组来存储，又结合C+的程序设计，我又用了类，但是，在执行时出现了问题。后来问同学，指出我的错误，不过获益不少。我又重新整理思路，把顺序表的基本操作写好了。虽然走了很多弯路，但是让我认识到，一定要创新，大胆，不能按照旧的思路去干新的事情。单链表写起来简单多了，这个很快就搞定了。但是细节上出了问题。比如说，有些变量的重复定义，有些变量又没有定义，在调用函数，就直接复制过来，没有改参数通过修改，我深刻理解到：细节决定成败，在以后，不管做任何事情都要认真，细心。这次的实验报告，让我受益匪浅，不仅有知识方面的，还有生活和精神上的。总之，我会继续我的兴趣编程，相信在编程的过程中，能不断的提高自己。