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

南京信息工程大学数据结构实验（实习）报告实验（实习）名称 顺序表、单链表 实验（实习）日期 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、 顺序表数据结构设计和实现#include #include #include #include /常量定义#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define OK 1#define ERROR 0#define OVERFLOW -2#define True 1#define False 0/函数返回值类型定义typedef int Status;/表节点数据类型定义typedef int ElemType;/顺序表类型定义typedef structElemType *elem;int length;int listsize; SqList;/顺序表各操作声明Status InitList_Sq(SqList &L);Status DetroyList_Sq(SqList &L);Status ClearList_Sq(SqList &L);int ListEmpty_Sq(SqList L);int ListLength_Sq(SqList L);Status GetElem_Sq(SqList L,int i,ElemType &e);Status ListInsert_Sq(SqList &L,int i,ElemType e);Status ListDelete_Sq(SqList &L,int i,ElemType &e);void PrintList_Sq(SqList L);void MergeList(SqList La,SqList Lb,SqList &Lc);#includelink.h#includeiostream.hStatus InitList_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;return OK;Status DetroyList_Sq(SqList &L)if (L.elem) free(L.elem);return OK;Status ClearList_Sq(SqList &L)if (L.elem)L.length=0;L.listsize=0;return OK;int ListEmpty_Sq(SqList L)return (L.length=0);int ListLength_Sq(SqList L)coutL.length;return 0;Status GetElem_Sq(SqList L,int i,ElemType &e)if (i=L.length)return ERROR;e=L.elemi-1;return OK;Status ListInsert_Sq(SqList &L,int i,ElemType e)ElemType *newbase,*p,*q; if (iL.length+1)return ERROR;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.elemi-1);for (p=&L.elemL.length-1;p=q;p-)*(p+1)=*p;*q=e;L.length+;return OK;Status ListDelete_Sq(SqList &L,int i,ElemType &e)ElemType *p,*q; if (iL.length)return ERROR;p=&(L.elemi-1);e=*p;q=L.elem+L.length-1;for (+p;pq;+p)*(p-1)=*p;L.length-;return OK;void PrintList_Sq(SqList L)int i;if (L.length=0)cout该表为空endl;else for (i=0;iL.length;i+) coutL.elemi ;#include link.h#includeiostream.hvoid MergeList(SqList La,SqList Lb,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_Lint main()SqList L1,L2,L3;ElemType e;int i;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;inext=NULL; /头节点的指针域指向NULLif(!L) return ERROR;return OK;/InitListStatus DestroyList(LinkList &L) /销毁链表LLinkList p,r;p=L-next; r=p-next;while(p!=NULL)free(p);p=r;r=p-next;free(L);return OK;/DestroyListStatus ClearList(LinkList &L) /将链表L重置为空表LinkList p,r;p=L-next; r=p-next;while(p!=NULL)free(p);p=r;r=p-next;L-next=NULL;return OK;/ClearListint ListEmpty(LinkList L) /判断L是否为空表return (L-next=NULL);/ListEmptyint ListLength(LinkList L) /返回L中元素结点个数LinkList p; p=L;int i=0;while(p-next!=NULL)p=p-next;i+;return i;/ListLengthStatus GetElem(LinkList L,int i,ElemType &e) /用e返回L中第i个数据元素的值LinkList p=L;int j=0;while(p!=NULL&jnext;j+;if(p=NULL|ji-1) return ERROR;e=p-data;return OK;/GetElemint LocateElem(LinkList L,ElemType e) /判断e是否存在于L中LinkList p=L;int i=0;while(p-next!=NULL)p=p-next;i+;if(p-data=e)return i;return 0;/LocateElemStatus ListInsert(LinkList &L,int i,ElemType e) /在L中第i个位置之前插入数据元素eLinkList p=L,s;int j=0;while(p!=NULL&jnext;j+;if(p=NULL|ji-1) return ERROR;s=(LinkList)malloc(sizeof(LNode);s-data=e;s-next=p-next;p-next=s;return OK;/ListInsertStatus ListDelete(LinkList &L,int i,ElemType &e) /删除L中第i个数据元素，并用e返回其值LinkList p=L,q;int j=0;while(p-next!=NULL&jnext;j+;if(p-next=NULL|ji-1) return ERROR;q=p-next;p-next=q-next;e=q-data;free(q);return OK;/ListDeletevoid PrintList(LinkList L)LinkList p=L-next;while(p!=NULL)printf(%d ,p-data);p=p-next;printf(n);/PrintListvoid DeleteElem(LinkList &L,ElemType e) /删除线性表中所有值为e的结点LinkList p=L,q;while(p-next!=NULL)q=p-next;if(q-data=e)p-next=q-next;free(q);elsep=p-next;/DeleteElemvoid MergeList(LinkList &La,LinkList &Lb,LinkList &Lc) /链表的二路归并LinkList pa,pb,pc;pa=La-next; pb=Lb-next;Lc=pc=La;while(pa&pb)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;elsepc-next=pb;pc=pb;pb=pb-next;pc-next=pa?pa:pb;free(Lb);/MergeList四、程序调试1、顺序表的实现：采用多文件结构，创建程序的过程为：