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

1实验一线性表的基本操作一、实验目的与基本要求1．掌握数据结构中的一些基本概念。数据、数据项、数据元素、数据类型和数据结构，以及它们之间的关系。2．了解数据的逻辑结构和数据的存储结构之间的区别与联系；数据的运算与数据的逻辑结构的关系。3．掌握顺序表和链表的基本操作：插入、删除、查找以及表的合并等运算。4．掌握运用C语言上机调试线性表的基本方法。二、实验条件1．硬件：一台微机2．软件：操作系统和C语言系统三、实验方法确定存储结构后，上机调试实现线性表的基本运算。四、实验内容1．建立顺序表，基本操作包括：初始化，建立一个顺序存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。2．建立单链表，基本操作包括：初始化，建立一个链式存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。3．假设有两个按数据元素值非递减有序排列的线性表A和B，均以顺序表作为存储结构。编写算法将A表和B表归并成一个按元素值非递增有序（允许值相同）排列的线性表C。（可以利用将B中元素插入A中，或新建C表）4．假设有两个按数据元素值非递减有序排列的线性表A和B，均以单链表作为存储结构。编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C。五、附源程序及算法程序流程图1.源程序（1）源程序(实验要求1和3)#includestdio.h#includemalloc.h#includestdlib.h#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstructarr{2int*elem;intlength;intlistsize;}Sqlist;voidmenu();//菜单voidInitList(Sqlist*p);//创建线性表voidShowList(Sqlist*p);//输出顺序线性表voidListDelete(Sqlist*p,inti,int&e);//在顺序线性表中删除第i个元素，并用e返回其值voidListInsert(Sqlist*p);//在顺序线性表中第i个元素前插入新元素evoidListEmpty(Sqlist*p);//判断L是否为空表voidGetList(Sqlist*p,inti,int&e);//用e返回L中第i个数据元素的值voidListInsert(Sqlist*p,inti,inte);boolcompare(inta,intb);voidLocateElem(Sqlist*L,inte);//在顺序线性表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,&m);printf(请出入要插入的数:\n);scanf(%d,&x);ListInsert(&La,m,x);break;case4:printf(请输入删除元素的位序:\n);scanf(%d,&m);3ListDelete(&La,m,x);printf(删除的元素为:%d\n,x);break;case5:printf(请输入要找的与线性表中相等的数:\n);scanf(%d,&m);LocateElem(&La,m);break;case6:printf(请输入查找的位序:\n);scanf(%d,&m);GetList(&La,m,x);printf(La中第%d个元素的值为%d\n,m,x);break;case7:ShowList(&La);break;case8:InitList(&Lb);break;case9:MergeList_L(&La,&Lb);printf(归并成功!);break;}menu();scanf(%d,&n);}}/*菜单*/voidmenu(){printf(********************\n\n);printf(0.退出\n\n);printf(1.创建线性表La\n\n);printf(2.判断La是否为空表\n\n);printf(3.插入元素(La)\n\n);printf(4.删除元素(La)\n\n);printf(5.定位元素(La)\n\n);printf(6.取元素(La)\n\n);printf(7.输出线性表\n\n);4printf(8.创建线性表Lb\n\n);printf(9.归并为一个线性表La\n\n);printf(********************\n\n);}/*创建顺序线性表L*/voidInitList(Sqlist*L){intn;inti=0;L-elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));if(NULL==L-elem)printf(储存分配失败!\n);else{L-length=0;L-listsize=LIST_INIT_SIZE;printf(输入顺序表a:\n);scanf(%d,&n);while(n){L-elem[i]=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;ip-length;i++)printf(%d,p-elem[i]);printf(\n);}/*判断L是否为空表*/voidListEmpty(Sqlist*p)5{if(0==p-length)printf(L是空表!\n);elseprintf(L不是空表!\n);}/*在顺序线性表中第i个元素前插入新元素e*/voidListInsert(Sqlist*p,inti,inte){int*newbase;int*q1;int*q2;while(i1||ip-length+1){printf(您输入的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);else{p-elem=newbase;p-listsize+=LISTINCREMENT;}}q1=&(p-elem[i-1]);for(q2=&(p-elem[p-length-1]);q2=q1;--q2)*(q2+1)=*q2;*q1=e;++p-length;}/*/在顺序线性表中删除第i个元素，并用e返回其值*/voidListDelete(Sqlist*p,inti,int&e){int*q1,*q2;while(i1||ip-length){printf(您输入的i超出范围!请重新输入:);scanf(%d,&i);}6q1=&(p-elem[i-1]);e=*q1;q2=p-elem+p-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-length)printf(第1个与e相等的元素的位序为%d\n,i);elseprintf(没有该元素!\n);}/*用e返回L中第i个数据元素的值*/voidGetList(Sqlist*p,inti,int&e){Sqlist*p1;p1=p;e=p1-elem[i-1];}/*已知顺序线性表La和Lb是元素按值非递减排列*//*把La和Lb归并到La上,La的元素也是按值非递减*/voidMergeList_L(Sqlist*La,Sqlist*Lb){inti=0,j=0,k,t;int*newbase;Sqlist*pa,*pb;pa=La;pb=Lb;7while(ipa-length&&jpb-length){if(pa-elem[i]=pb-elem[j]){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-elem[k+1]=pa-elem[k];pa-length++;pa-elem[i]=pb-elem[j];i++;j++;}elsei++;}while(jpb-length){if(pa-listsizepb-length-j){newbase=(int*)realloc(pa-elem,(pa-listsize+LISTINCREMENT)*sizeof(int));if(!newbase)exit(0);}for(j;jpb-length;j++,i++){pa-elem[i]=pb-elem[j];pa-length++;}}for(i=0;ipa-length/2;i++){t=pa-elem[i];pa-elem[i]=pa-elem[pa-length-i-1];pa-elem[pa-length-i-1]=t;}}8（2）源程序(实验要求2和4)#includestdio.h#includemalloc.h#includestdlib.htypedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;voidmenu();LinkListInitList();voidShowList(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;LinkListLb;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(