实现两个链表的合并

1、百度文库- 让每个人平等地提升自我数据结构课程设计题目一：实现两个链表的合并题目二：可变长顺序表设计班级：计科 1202 班姓名：学期： 2013-2014 学年第二学期11百度文库- 让每个人平等地提升自我题目 1：实现两个链表的合并基本要求：（ 1）建立两个链表 A 和 B，链表元素个数分别为 m 和 n 个。（ 2）假设元素分别为 (x1,x2,xm)，和 (y1,y2, yn)。把它们合并成一个线性表C：当 m>=n 时， C=x1,y1,x2,y2,xn,yn,xm当 n>m 时， C=y1,x1,y2,x2,ym,xm, ,yn（ 3）输出线性表 C：（ 4） 用直接插

2、入排序法对 C 进行升序排序，生成链表 D，并输出链表 D。测试数据：（ 1） A 表（ 30，41，15， 12，56，80）B 表（ 23， 56，78，23，12，33， 79，90，55）（ 2） A 表（ 30，41，15， 12，56，80，23，12， 34）B 表（ 23， 56，78，23，12）算法思想 ：首先我们需要建立两个链表 A,B ，A 链表的元素个数为 m； B 链表的元素个数为 n；在将 A,B 链表进行合并，根据 m 和 n 的大小关系决定链表 C 的元素顺序（当 m>=n 时，应该先插入 A 表中的数据元素，在偶数位插入 A 表中的数据元素，在奇数位插

3、入 B 表中的数据元素，最后在插入 A 表中剩余的数据元素；当 m<n 时，应该先插入 B 表中的数据元素，在偶数位插入 B 表中的数据元素，在奇数位插入 A 表中的数据元素，最后在插入 B 表中剩余的数据元素），再将 C 经行直接插入排序得到一个新的链表D；最后输出 ABCD 的相关信息。模块划分 :(1) 结构体 struct Node 的创建。(2) struct Node *create（）链表的创建。(3) void print(struct Node *head)功能是对链表进行输出。(4) struct Node * inter_link(struct Node * cha

4、in1, int a, struct Node * chain 2, int b)算法的功能是实现两个链表的交叉合并， 并且可以根据两链表的长短将行不通的插入。(5) void InsertSort(struct Node *p,int m)算法的功能是对一合并好的链表进行升序插入排序。(6) main() 函数主要是对算法进行测试。22百度文库- 让每个人平等地提升自我数据结构：数据结构定义如下：struct Nodelong int number;struct Node *next;源程序：#include<>#include<>#include<>#i

5、nclude<>#define L sizeof(struct Node)struct Node33百度文库- 让每个人平等地提升自我44百度文库- 让每个人平等地提升自我始化空表Datatype InitList_Sq(SqList &L)= (Datatype *)malloc(LIST_INIT_SIZE *sizeof(Datatype);if(!exit(-1);立顺序表 LDatatype CreatList_Sq(SqList &L,int n)int i;Datatype e;55百度文库- 让每个人平等地提升自我printf("输入顺序表

6、的长度 :");scanf("%d",&n);= n;if > LIST_INIT_SIZE)= (Datatype *) realloc,*sizeof(Datatype); printf(" 输入数据 :");for(i = 0;i <= ;i+)scanf("%d",&e);i = e;return 1;毁线性表Datatype DestoryList_Sq(SqList &L)iffree;= NULL;= =0;return 1;return 0;定是否空表Datatype Li

7、stEmpty_Sq(SqList L)ifreturn 0;return 1;L中数据元素的个数int ListLength_Sq(SqList L)return ;表第 i 个元素Datatype GetElem_Sq(SqList L, int i, Datatype &e)入结点Datatype ListInsert_Sq(SqList &L, int i, Datatype e)除结点Datatype ListDelete_Sq(SqList &L, int i, Datatype &e)出顺序表void Output(SqList L)立一个顺序表

8、");for(i = 0;i < 10;i+)66百度文库- 让每个人平等地提升自我printf(" ");printf("*");printf("n");for(i = 0;i < 10;i +)printf(" ");printf("*");printf("2.输出一个顺序表 ");for(i = 0;i < 10;i+)printf(" ");printf("*");printf("n&quo

9、t;);for(i = 0;i < 10;i +)printf(" ");printf("*");printf("3.向顺序表中插入一个元素");for(i = 0;i < 2;i+)printf(" ");printf("*");printf("n");for(i = 0;i < 10;i +)printf(" ");printf("*");printf("4.删除顺序表中的一个元素");for(

10、i = 0;i < 2;i+)printf(" ");printf("*");printf("n");for(i = 0;i < 10;i+)printf(" ");printf("*");printf("5.从顺序表中取出一个元素");for(i = 0;i < 2;i+)printf(" ");printf("*");printf("n");for(i = 0;i < 10;i+)prin

11、tf(" ");printf("*");printf("6.求顺序表中数据元素个数");for(i = 0;i < 2;i+)printf(" ");printf("*");printf("n");for(i = 0;i < 10;i+)77百度文库- 让每个人平等地提升自我printf(" ");printf("*");printf("7.判断顺序表中是否为空 ");for(i = 0;i < 4

12、;i+)printf(" ");printf("*");printf("n");for(i = 0;i < 10;i+)printf(" ");printf("*");printf("8.销毁线性表 ");for(i = 0;i < 14;i+)printf(" ");printf("*");printf("n");for(i = 0;i < 10;i+)printf(" ");

13、printf("*");printf("0.退出");for(i = 0;i < 8;i+)printf(" ");printf("*");printf("n");put();int main()/主函数int n = 0,i,j = 0,k = 1,m,q,x,y,e;SqList l,la,lc;InitList_Sq(l);mainpp();while(k)printf("请选择 -8 ：");scanf("%d",&m);getcha

14、r();switch(m)case 0:exit(0);case 1:CreatList_Sq(l,n);Output(l);88百度文库- 让每个人平等地提升自我break;case 2:Output(l);printf("n");break;case 3:printf(" 请输入要插入的元素的位置及其值： "); fflush(stdin);scanf("%d,%d",&i,&x);ListInsert_Sq(l,i,x);Output(l);printf("n");break;case 4:p

15、rintf("请输入要删除元素的位置：");fflush(stdin);scanf("%d",&i);ListDelete_Sq(l,i,y);Output(l);printf("n");break;case 5:printf("请输入要取出的元素的序号：");fflush(stdin);scanf("%d",&i);GetElem_Sq(l,i,e);printf("取出的第 %d个元素为： %dn",i,e);break;case 6:printf(" 顺序表中数据元素的个数为： %d",ListLength_Sq(l);case 7:q = ListEmpty_Sq(l);if(q = 1)printf("此表为空 ");elseprintf("此表不空 ");printf("