C语言数据结构线性表的基本操作实验报告

1、实验一线性表的基本操作一、实验目的与基本要求1掌握数据结构中的一些基本概念。数据、数据项、数据元素、数据类型和数据结构，以及它们之间的关系。2了解数据的逻辑结构和数据的存储结构之间的区别与联系；数据的运算与数据的逻辑结构的关系。3掌握顺序表和链表的基本操作：插入、删除、查找以及表的合并等运算。4掌握运用 C语言上机调试线性表的基本方法。二、实验条件1硬件：一台微机2软件：操作系统和C语言系统三、实验方法确定存储结构后，上机调试实现线性表的基本运算。四、实验内容1建立顺序表，基本操作包括：初始化，建立一个顺序存储的链表，输出顺序表，判断是否为空，取表中第 i 个元素，定位函数（返回第一个与 x

2、相等的元素位置），插入，删除。2建立单链表，基本操作包括：初始化，建立一个链式存储的链表，输出顺序表，判断是否为空，取表中第 i 个元素，定位函数（返回第一个与 x 相等的元素位置），插入，删除。3假设有两个按数据元素值非递减有序排列的线性表A 和 B，均以顺序表作为存储结构。编写算法将 A 表和 B 表归并成一个按元素值非递增有序 （允许值相同）排列的线性表 C。（可以利用将 B 中元素插入 A 中，或新建 C表）4 假设有两个按数据元素值非递减有序排列的线性表A 和 B，均以单链表作为存储结构。编写算法将 A 表和 B 表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表

3、C。五、附源程序及算法程序流程图1. 源程序（ 1）源程序 ( 实验要求 1 和 3) #include<stdio.h> #include<malloc.h> #include<stdlib.h> #defineLIST_INIT_SIZE100 #defineLISTINCREMENT10 typedefstructarrint*elem;intlength;intlistsize;Sqlist;voidmenu();/菜单voidInitList(Sqlist*p); voidShowList(Sqlist*p); voidListDelete(Sql

4、ist*p,inti,int&e);/ 创建线性表/ 输出顺序线性表/ 在顺序线性表中删除第i 个元素，并用e 返回其值voidListInsert(Sqlist*p);/ 在顺序线性表中第i 个元素前插入新元素evoidListEmpty(Sqlist*p); voidGetList(Sqlist*p,inti,int&e);/ 判断 L 是否为空表/ 用 e 返回 L 中第 i个数据元素的值voidListInsert(Sqlist*p,inti,inte);boolcompare(inta,intb);voidLocateElem(Sqlist*L,inte);/ 在顺序

5、线性表L 中查找第1 个值与e 满足compare()d元素的位序voidMergeList_L(Sqlist*La,Sqlist*Lb);/归并voidmain()SqlistLa;SqlistLb;intn,m,x;menu();scanf("%d",&n);while(n)switch(n)case0:;break;case1:InitList(&La);break;case2:ListEmpty(&La);break;case3:printf("请输入插入的位序:n");scanf("%d",&

6、m);printf("请出入要插入的数:n");scanf("%d",&x);ListInsert(&La,m,x);break;case4:printf("请输入删除元素的位序:n");scanf("%d",&m);ListDelete(&La,m,x);printf("删除的元素为:%dn",x);break;case5:printf("请输入要找的与线性表中相等的数:n");scanf("%d",&m);Loc

7、ateElem(&La,m);break;case6:printf("请输入查找的位序 :n");scanf("%d",&m);GetList(&La,m,x);printf("La 中第 %d个元素的值为 %dn",m,x);break; case7:ShowList(&La);break;case8:InitList(&Lb);break;case9:MergeList_L(&La,&Lb);printf("归并成功 !");break;menu();sc

8、anf("%d",&n);/* 菜单 */voidmenu()printf("*nn");printf("0.printf("1.printf("2.printf("3.printf("4.printf("5.printf("6.printf("7.printf("8.printf("9.退出 nn");创建线性表 Lann");判断 La 是否为空表 nn");插入元素 (La)nn");删除元素 (La)

9、nn");定位元素 (La)nn");取元素 (La)nn");输出线性表 nn");创建线性表 Lbnn");归并为一个线性表Lann");printf("*nn");/* 创建顺序线性表L*/voidInitList(Sqlist*L)intn;inti=0;L->elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int);if(NULL=L->elem)printf("储存分配失败 !n");elseL->length=0;L->lis

10、tsize=LIST_INIT_SIZE;printf("输入顺序表 a:n");scanf("%d",&n);while(n)L->elemi=n;i+;L->length+;L->listsize=L->listsize-4;scanf("%d",&n);/* 输出顺序线性表 */voidShowList(Sqlist*p)inti;if(0=p->length)printf("数组为空 !n");elsefor(i=0;i<p->length;i+)p

11、rintf("%d",p->elemi);printf("n");/* 判断 L 是否为空表 */voidListEmpty(Sqlist*p)if(0=p->length)printf("L是空表 !n");elseprintf("L不是空表 !n");/* 在顺序线性表中第i 个元素前插入新元素e*/voidListInsert(Sqlist*p,inti,inte)int*newbase;int*q1;int*q2;while(i<1|i>p->length+1)printf(&

12、quot; 您输入的 i 超出范围 !n 请重新输入要插入的位置 n:"); scanf("%d",&i);if(p->length>=p->listsize)newbase=(int*)realloc(p->elem,(p->listsize+LISTINCREMENT)*sizeof(int); if(!newbase)exit(0);elsep->elem=newbase;p->listsize+=LISTINCREMENT;q1=&(p->elemi-1);for(q2=&(p->

13、;elemp->length-1);q2>=q1;-q2)*(q2+1)=*q2;*q1=e;+p->length;/*/ 在顺序线性表中删除第 i 个元素，并用 e 返回其值 */ voidListDelete(Sqlist*p,inti,int&e) int*q1,*q2;while(i<1|i>p->length)printf("您输入的 i 超出范围 ! 请重新输入 :");scanf("%d",&i);q1=&(p->elemi-1);e=*q1;q2=p->elem+p-

14、>length-1;for(+q1;q1<=q2;+q1)*(q1-1)=*q1;-p->length;/* 对比 a 与 b 相等 */boolcompare(inta,intb)if(a=b)return1;elsereturn0;/* 在顺序线性表 L 中查找第 1 个值与 e 满足 compare()d 元素的位序 */ voidLocateElem(Sqlist*L,inte)inti=1;int*p;p=L->elem;while(i<=L->length&&!compare(*p+,e)+i;if(i<=L->len

15、gth)printf(" 第 1 个与 e 相等的元素的位序为 %dn",i); elseprintf("没有该元素 !n");/* 用 e 返回 L 中第 i 个数据元素的值 */voidGetList(Sqlist*p,inti,int&e)Sqlist*p1;p1=p;e=p1->elemi-1;/* 已知顺序线性表La 和 Lb 是元素按值非递减排列 */* 把 La 和 Lb 归并到 La 上,La 的元素也是按值非递减 */ voidMergeList_L(Sqlist*La,Sqlist*Lb) inti=0,j=0,k,t;

16、int*newbase;Sqlist*pa,*pb;pa=La;pb=Lb;while(i<pa->length&&j<pb->length)if(pa->elemi>=pb->elemj)if(pa->listsize=0)newbase=(int*)realloc(pa->elem,(pa->listsize+LISTINCREMENT)*sizeof(int); if(!newbase)exit(0);for(k=pa->length-1;k>=i;k-)pa->elemk+1=pa->e

17、lemk;pa->length+;pa->elemi=pb->elemj;i+;j+;elsei+;while(j<pb->length)if(pa->listsize<pb->length-j)newbase=(int*)realloc(pa->elem,(pa->listsize+LISTINCREMENT)*sizeof(int); if(!newbase)exit(0);for(j;j<pb->length;j+,i+)pa->elemi=pb->elemj;pa->length+;for(i=0

18、;i<pa->length/2;i+)t=pa->elemi;pa->elemi=pa->elempa->length-i-1;pa->elempa->length-i-1=t;（ 2）源程序 ( 实验要求 2 和 4) #include<stdio.h> #include<malloc.h> #include<stdlib.h> typedefstructLNodeintdata;structLNode*next;LNode,*LinkList;voidmenu();LinkListInitList();vo

19、idShowList(LinkListL);voidListDelete(LinkListL,inti,int&e);voidListEmpty(LinkListL);voidGetList(LinkListL,inti,int&e);voidListInsert(LinkListL,inti,inte);boolcompare(inta,intb);voidLocateElem(LinkListL,inte);LinkListMergeList_L(LinkListLa,LinkListLb);inttotal=0;voidmain()LinkListLa;LinkListL

20、b;La=(LinkList)malloc(sizeof(structLNode);La->next=NULL;Lb=(LinkList)malloc(sizeof(structLNode);Lb->next=NULL;intn;intm;intx;menu();scanf("%d",&n);while(n)switch(n)case0:;break;case1:La->next=InitList();break;case2:ListEmpty(La);break;case3:printf("请输入要插入到第几个节点前:n");

21、scanf("%d",&m);printf("请输入插入的数据 :n");scanf("%d",&x);ListInsert(La,m,x);break;case4:printf("请输入删除元素的位序:n");scanf("%d",&m);ListDelete(La,m,x);printf("删除的元素为 :%dn",x);break;case5:printf("请输入要找的与线性表中相等的数:n");scanf("%d

22、",&m);LocateElem(La,m);break;case6:printf("请输入查找的位序 :n");scanf("%d",&m);GetList(La,m,x);printf("La中第 %d个元素的值为 %dn",m,x);break;case7:ShowList(La);break;case8:Lb->next=InitList();break;case9:La=MergeList_L(La,Lb);printf("归并成功 n");break;menu();sca

23、nf("%d",&n);voidmenu()printf("*nn");printf("0.printf("1.printf("2.printf("3.printf("4.printf("5.printf("6.printf("7.printf("8.printf("9.退出 nn");创建线性表 Lann");判断是否为空表 nn");插入元素 nn");删除元素 nn");定位元素 nn&quo

24、t;);取元素 nn");输出线性表 nn");创建线性表 Lbnn");归并两线性表 nn");printf("*nn");/ 创建链式线性表 L LinkListInitList()intcount=0;LinkListpHead=NULL;LinkListpEnd,pNew;pEnd=pNew=(LinkList)malloc(sizeof(structLNode); printf(" 请输入数据 :n");scanf("%d",&pNew->data);while(pNew

25、->data)count+;if(count=1)pNew->next=pHead;pEnd=pNew;pHead=pNew;elsepNew->next=NULL;pEnd->next=pNew;pEnd=pNew;pNew=(LinkList)malloc(sizeof(structLNode);printf("请输入数据 :n");scanf("%d",&pNew->data);free(pNew);total=total+count;returnpHead;/ 判断 L 是否为空表voidListEmpty(

26、LinkListL)if(NULL=L->next)printf("此表为空表 !n");elseprintf("此表不为空表 !n");/ 在链式线性表中第 i 个元素前插入新元素 e voidListInsert(LinkListL,inti,inte)LinkListp;LinkLists;p=L;intj=0;while(p&&j<i-1)p=p->next;+j;if(!p|j>i-1)printf("不存在您要找的节点 !n");elses=(LinkList)malloc(size

27、of(int);s->data=e;s->next=p->next;p->next=s;printf("插入节点成功 !n");/ 输出链式线性表 voidShowList(LinkListL)LinkListp; p=L->next;if(p=NULL)printf("此表为空表 !n");elsewhile(p)printf("%d",p->data);p=p->next;printf("n");/ 在链式线性表中删除第 i 个元素，并用 e 返回其值 voidList

28、Delete(LinkListL,inti,int&e)LinkListp;LinkListq;p=L;intj=0;while(p->next&&j<i-1)p=p->next;+j;if(!(p->next)|j>i-1)printf("没有找到要删除的位置 !");elseq=p->next;p->next=q->next;e=q->data;free(q);/ 用 e 返回 L 中第 i 个数据元素的值 voidGetList(LinkListL,inti,int&e)LinkLi

29、stp;p=L->next;intj=0;while(p->next&&j<i-1)p=p->next;+j;if(!(p)|j>i-1)printf("没有找到要查找的位置!");elsee=p->data;/ 对比 a 与 b 相等 boolcompare(inta,intb)if(a=b)return1;elsereturn0;/ 在链式线性表 L 中查找第 1 个值与 e 满足 compare()d 元素的位序 voidLocateElem(LinkListL,inte)inti=0;LinkListp;p=L;w

30、hile(p->next&&!compare(p->data,e)p=p->next;i+;if(NULL=p->next)if(0=compare(p->data,e)printf("没有该元素 !n");elseprintf("第 1 个与 e 相等的元素的位序为 %dn",i);elseif(compare(p->data,e)printf("没有该元素 !n");LinkListMergeList_L(LinkListLa,LinkListLb)inti,j,k;LinkLi

31、stpa_1,pb_1,pa_2,pb_2,pc,pd;pa_1=La->next;pc=pa_2=La;pb_1=pb_2=Lb->next;if(pa_1->data>pb_1->data)pc=pa_2=Lb;pa_1=Lb->next;pb_1=pb_2=La->next;while(pa_1&&pb_1)if(pa_1->data>=pb_1->data)pa_2->next=pb_1;pb_2=pb_1->next;pb_1->next=pa_1;pb_1=pb_2;pa_2=pa_2-&

32、gt;next;elsepa_1=pa_1->next;pa_2=pa_2->next;if(pb_1)pa_2->next=pb_1;pd=(LinkList)malloc(sizeof(structLNode);pd->next=NULL;pa_2=pd;k=total;for(i=0;i<total;i+)pa_1=pc->next;for(j=1;j<k;j+)pa_1=pa_1->next;pb_1=(LinkList)malloc(sizeof(structLNode);pa_2->next=pb_1;pa_2=pa_2->next;pa_2->data=pa_1->data;k-;pa_2->next=NULL;returnpd;2. 流程图 ( 实验要求 1 和