数据结构实验报告 线性表的基本操作文档格式.docx

1、（6）根据算法，将两个有序的单链表合并成一个有序单链表。测试数据 由学生任意指定。（一）顺序表的基本操作#includeusing namespace std;#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef int ElemType;#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct /结构体 ElemType *elem; int length; int lis

2、tsize;SqList;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,int i,ElemType e） /插入新元素 int *q,*p;ElemType *newbase; if（iL.length+1） return ERROR; if（L.length=L.lis

3、tsize） newbase=new 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（Sq

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

5、Elem（Lb,j,bj）; if（ai=bj） 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（SqList L,int i） /显示 int j;ElemType k; cout顺序表显示如下:endl; for（j=0;ji-1;j+） k=L.elemj;k; if（j=i-1 &

6、i0） k=L.elemj; coutk;void create（SqList &L,int n） /输入元素 int e; for（int i=0;ie; L.elemi=e; L.length=i+1;Status ListDelete_Sq（SqList &L,int i,ElemType &e） /删除 ElemType *p, *q;L.length） return ERROR; p=& e=*p; q=L.elem+L.length-1; for（+p;pa;请输入顺序表的元素（共aListlength（L1） cout输入有误，请重新输入 cout GetElem（L1,j,e1

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

8、 show（L1,a+1）;void hebing（SqList &L3） /合并两个顺序表 SqList L1,L2; int a,b; InitList_Sq（L2）;请输入第一个有序表的长度：请输入第一个有序表的元素（共请输入第二个有序表的长度：b;请输入第二个有序表的元素（共b create（L2,b）; show（L2,b）; MergeList（L1,L2,L3）;合并后的有序表如下： show（L3,a+b）;void main（） /主菜单 int choice; for（;） cout 顺序表的基本操作 1.顺序表的创建 2.顺序表的显示 3.顺序表的长度 4.取第i个位置的

9、元素 5.修改第i个位置的元素 6.插入元素到顺序表里 7.删除顺序表里的元素 8.合并两个顺序表 9.退出系统请选择：choice; switch（choice） case 1: shuru（Lx）;break; case 2: show（Lx,Lx.length）; case 3:顺序表的长度: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（LinkList L,int i,Elem

10、Type &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,int i,ElemType 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中next=s;Status L

11、istDelete（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）;void MergeList（LinkList &La,LinkList &Lb,LinkList &Lc） /合并两个顺序链表 LinkList pa,pc,pb; pa=La- pb=Lb- Lc=pc=La; while（pa&pb） if（pa-datadata） pc-next=pa; p

12、c=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（LinkList L,int i） /表长 i=0; LinkList p=L- +i; return i;void xiugai（LinkList L） /修改 int i,j=1; ElemType k; ElemType e,m;请输入要修改的元素位置（0length）:i; GetElem（L,i,e）;该位置的元素:edata=k;修改后

13、的单链表显示如下: show（L）;void hebing（） /合并两个单链表 int a,b; LinkList La,Lb,Lc;请输入第一个有序链表的长度:请输入第一个有序链表的元素共（个）： CreateList（La,a）; show（La）;请输入第二个有序链表的长度:请输入第二个有序链表的元素共（ CreateList（Lb,b）; show （Lb）; MergeList（La,Lb,Lc）;合并后的有序链表如下： show（Lc）;void main（） /主函数 int select; int x; ElemType y; LinkList list; for（; 单链表

14、的基本操作 1.单链表的创建 2.单链表的显示 coutselect; switch（select） case 1:coutx;请输入x个元素 CreateList（list,x）; break; case 2:单链表显示如下: show（list）; case 3: int s;单链表的长度为:Length（list,s） break; case 4: while（xLength（list,s） cout cout GetElem（list,x,y）;该位置的元素为:y case 5: xiugai（list）; break; case 6:请选择要插入的位置:要插入的元素值:y; LinkInsert（ list,x,y）;插入后单链表显示如下: show（list）; break; case 7:请选择要删除的位置: while（x cout ListDelete（list,x,y）;要删除的元素值: