采用顺序表、单链表二种存储结构

南京信息工程大学数据结构实验（实习）报告实验（实习）名称顺序表、单链表实验（实习）日期2015-10-11得分指导教师顾韵华系计软院专业计科年级2014级班次2姓名一、实验目的1、掌握采用顺序表、单链表二种存储结构实现线性表的归并运算。二、实验内容1、输入两个顺序表A和B的元素值（整数），元素递增有序，编写程序将A和B归并成一个按元素值递增有序的顺序表C。分别输出顺序表A、B和C所有元素的值。2、输入两个单链表A和B的元素值（整数），其表中元素递增有序，编写程序将A和B归并成一个按元素值递增有序的单链表C。分别输出单链表A、B和C所有结点的值。三、数据结构设计和实现1、顺序表数据结构设计和实现#includestdio.h#includestdlib.h#includemalloc.h#includetime.h//常量定义#defineLIST_INIT_SIZE100#defineLISTINCREMENT10#defineOK1#defineERROR0#defineOVERFLOW-2#defineTrue1#defineFalse0//函数返回值类型定义typedefintStatus;//表节点数据类型定义typedefintElemType;//顺序表类型定义typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;//顺序表各操作声明StatusInitList_Sq(SqList&L);StatusDetroyList_Sq(SqList&L);StatusClearList_Sq(SqList&L);intListEmpty_Sq(SqListL);intListLength_Sq(SqListL);StatusGetElem_Sq(SqListL,inti,ElemType&e);StatusListInsert_Sq(SqList&L,inti,ElemTypee);StatusListDelete_Sq(SqList&L,inti,ElemType&e);voidPrintList_Sq(SqListL);voidMergeList(SqListLa,SqListLb,SqList&Lc);#includelink.h#includeiostream.hStatusInitList_Sq(SqList&L){L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;}StatusDetroyList_Sq(SqList&L){if(L.elem)free(L.elem);returnOK;}StatusClearList_Sq(SqList&L){if(L.elem){L.length=0;L.listsize=0;}returnOK;}intListEmpty_Sq(SqListL){return(L.length==0);}intListLength_Sq(SqListL){coutL.length;return0;}StatusGetElem_Sq(SqListL,inti,ElemType&e){if(i1||i=L.length)returnERROR;e=L.elem[i-1];returnOK;}StatusListInsert_Sq(SqList&L,inti,ElemTypee){ElemType*newbase,*p,*q;if(i1||iL.length+1)returnERROR;if(L.length=L.listsize){newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;}q=&(L.elem[i-1]);for(p=&L.elem[L.length-1];p=q;p--)*(p+1)=*p;*q=e;L.length++;returnOK;}StatusListDelete_Sq(SqList&L,inti,ElemType&e){ElemType*p,*q;if(i1||iL.length)returnERROR;p=&(L.elem[i-1]);e=*p;q=L.elem+L.length-1;for(++p;pq;++p)*(p-1)=*p;L.length--;returnOK;}voidPrintList_Sq(SqListL){inti;if(L.length==0)cout该表为空endl;elsefor(i=0;iL.length;i++)coutL.elem[i];}#includelink.h#includeiostream.hvoidMergeList(SqListLa,SqListLb,SqList&Lc){int*pa;pa=La.elem;int*pb;pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;int*pc;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));if(!Lc.elem)exit(OVERFLOW);//存储分配失败int*pa_last;pa_last=La.elem+La.length-1;int*pb_last;pb_last=Lb.elem+Lb.length-1;while(pa=pa_last&&pb=pb_last){//归并if(*pa=*pb)*pc++=*pa++;else*pc++=*pb++;}while(pa=pa_last)*pc++=*pa++;while(pb=pa_last)*pc++=*pb++;}//MergeList_Lintmain(){SqListL1,L2,L3;ElemTypee;inti;InitList_Sq(L1);//构造空的单链表L1InitList_Sq(L2);//构造空的单链表L2printf(请输入表L1元素值，共5个\n);for(i=0;i5;i++){scanf(%d,&e);ListInsert_Sq(L1,i+1,e);//向表中插入用户输入的元素值}printf(请输入表L2元素值，共3个\n);for(i=0;i3;i++){scanf(%d,&e);ListInsert_Sq(L2,i+1,e);//向表中插入用户输入的元素值}//合并L1和L2MergeList(L1,L2,L3);//输出合并后表L3的各个元素值printf(L1与L2合并后的表元素值为：\n);PrintList_Sq(L3);printf(\n);return0;}2、单链表数据结构设计和实现typedefstructLNode{ElemTypedata;structLNode*next;//next为指向LNode类型节点的指针}LNode,*LinkList;//LNode为节点类型，LinkList为指向LNode类型节点的指针(即头指针)单链表操作的函数原型包括：StatusInitList(LinkList&L);//构造一个新的链表LStatusDestroyList(LinkList&L);//销毁线性表LStatusClearList(LinkList&L);//将线性表L重置为空表intListEmpty(LinkListL);//判断L是否为空表intListLength(LinkListL);//返回L中数据元素的个数StatusGetElem(LinkListL,inti,ElemType&e);//用e返回L中第i个数据元素的值intLocateElem(LinkListL,ElemTypee);//判断e是否存在于L中StatusListInsert(LinkList&L,inti,ElemTypee);//在L中第i个位置之前插入数据元素eStatusListDelete(LinkList&L,inti,ElemType&e);//删除L中第i个数据元素，并用e返回其值voidPrintList(LinkListL);//输出顺序表中的数据元素voidDeleteElem(LinkList&L,ElemTypee);//删除线性表中所有值为e的结点voidMergeList(LinkList&La,LinkList&Lb,LinkList&Lc);//链表的二路归并单链表各操作实现：StatusInitList(LinkList&L)//构造一个新的有头节点的空链表L{L=(LinkList)malloc(sizeof(LNode));//生成新节点(此处为头节点)L-next=NULL;//头节点的指针域指向NULLif(!L)returnERROR;returnOK;}//InitListStatusDestroyList(LinkList&L)//销毁链表L{LinkListp,r;p=L-next;r=p-next;while(p!=NULL){free(p);p=r;r=p-next;}free(L);returnOK;}//DestroyListStatusClearList(LinkList&L)//将链表L重置为空表{LinkListp,r;p=L-next;r=p-next;while(p!=NULL){free(p);p=r;r=p-next;}L-next=NULL;returnOK;}//ClearListintListEmpty(LinkListL)//判断L是否为空表{return(L-next==NULL);}//ListEmptyintListLength(LinkListL)//返回L中元素结点个数{LinkListp;p=L;inti=0;while(p-next!=NULL){p=p-next;i++;}returni;}//ListLengthStatusGetElem(LinkListL,inti,ElemType&e)//用e返回L中第i个数据元素的值{LinkListp=L;intj=0;while(p!=NULL&&ji){p=p-next;j++;}if(p==NULL||ji-1)returnERROR;e=p-data;returnOK;}//GetElemintLocateElem(LinkListL,ElemTypee)//判断e是否存在于L中{LinkListp=L;inti=0;while(p-next!=NULL){p=p-next;i++;if(p-data==e)returni;}return0;}//LocateElemStatusListInsert(LinkList&L,inti,ElemTypee)//在L中第i个位置之前插入数据元素e{LinkListp=L,s;intj=0;while(p!=NULL&&ji-1){p=p-next;j++;}if(p==NULL||ji-1)returnERROR;s=(LinkList)malloc(sizeof(LNode));s-data=e;s-next=p-next;p-next=s;returnOK;}//ListInsertStatusListDelete(LinkList&L,inti,ElemType&e)//删除L中第i个数据元素，并用e返回其值{Link