实现两个链表的合并

二、基本功能要求：

1. 建立两个链表A和B，链表元素个数分别为m和n个。

2. 假设元素分别为(x1,x2,…xm)，和(y1,y2, …yn)。把它们合并成一个线性表C，使

得：

当m>=n时，C=x1,y1,x2,y2,...xn,yn, (x)

当n>m时，C=y1,x1,y2,x2,…ym,xm,…,yn

3. 输出线性表C：用直接插入排序法对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）

四、理论分析结果：

1. A表的数据元素个数m=6，B表的数据元素个数 n=9，此时m分析合并结果：当mC=23，30，56，41，78，15，23，12，12，56，33，80，79，90，55

排序结果：

D=12，12，15，23，23，30，33，41，55，56，56，78，79，80，90

2. A表的数据元素个数m=9，B表的数据元素个数 n=5，此时m>n

分析合并结果：当m>=n时，应该先插入A表中的数据元素，在偶数位插入A表中的数据元素，在奇数位插入B表中的数据元素，最后插入A表中剩余的数据元素。

C=30，23，41，56，15，78，12，23，56，12，80，23，12， 34

排序结果：

D=12，12，12，15，23，23，23，30，34，41，56，56，78，805.1 分析问题，给出数学模型，设计相应的数据结构：

1) 分析问题特点，用数学表达式或其它形式描述其数学模型。

2) 选择能够体现问题本身特点的一种或几种逻辑结构。

3) 依据逻辑结构和问题特点，设计并选择相应的存储结构（顺序存储结构和链式存储

结构对应的算法实现有区别）。

5.2 算法设计：

1) 确定所需模块：对于复杂的程序设计，要充分利用模块化程序设计方法和面向对象

思想，自顶向下，逐步细化。

2) 各子模块功能描述：给出主要模块的算法描述，用流程图或伪代码表示。

3) 模块之间的调用关系：给出算法各模块之间的关系图示。

5.3 上机实现程序：

为提高工作效率，充分利用上机调试时间，在上机之前应列出程序清单。

5.4 有代表性的各种测试数据去验证算法及程序的正确性：

根据课程设计的要求对给定的数据进行测试，验证算法以及程序的正确性。

5.5 算法分析及优化：

经过上机调试，源程序运行正确，并且实现算法要求的功能，解决课程设计题目中给出的问题后，分析算法的时间复杂度和空间复杂度，如有可能对程序进行优化改进。

六、模块划分：

1.单链表头文件：LinList.h

主要包括单链表的存储结构、初始化、求数据元素个数、插入、删除数据元素、取数据元素、撤消单链表的函数。

2. 单链表操作头文件：MyList.h

主要包括单链表测试、单链表合并、单链表合并排序函数。

3.测试主函数文件：TestLinList.h

主要包括文件包含、数据导入和操作模块程序。

7.1 带头结点的单链表存储结构

typedef struct Node

{

DataType data;

struct Node *next;

}SLNode;

7.2 单链表的初始化

void ListInitiate(SLNode **head)

{

/*如果有内存空间，申请头结点空间并使头指针head指向头结点*/

if((*head = (SLNode *)malloc(sizeof(SLNode)))==NULL)

exit(1);

(*head)->next = NULL;/*尾标记NULL */

}

7.3 求单链表中的数据元素个数

int ListLength(SLNode *head)

{

SLNode *p = head; /*p指向头结点*/

int size = 0; /*size初始为0*/

while(p->next != NULL) /*循环计数*/

{

p = p->next;size ++;

}

return size;

}

7.4 向单链表中插入数据元素

int ListInsert(SLNode *head,int i,DataType x)

{

SLNode *p, *q;

int j;

p = head;

j = -1;while(p->next!=NULL && j{

p = p->next; j++;

}

if(j != i - 1)

{

printf("Eorror: 插入位置参数错!\\n");

return 0;

}

if((q = (SLNode *)malloc(sizeof(SLNode))) == NULL)

exit(1);

q->data = x;

q->next = p->next;

p->next = q;

return 1;

}//注：此单链表是带头结点的

7.5 从单链表中删除数据元素

int ListDelete(SLNode *head,int i,DataType *x)

{

SLNode *p, *s; int j;

p=head;

j = -1;

while(p->next != NULL && p->next->next!=NULL && j{

p=p->next;j++;

}

if(j!=i-1)

{

printf("Eorror: 删除位置参数错!\\n");

return 0;

}

s = p->next;

*x=s->data;

p->next = p->next->next;

free(s);

return 1;

}

ListGet(SLNode *head,int i,DataType *x)

{

SLNode *p;

int j;

p=head;

j=-1;

while(p->next!=NULL && j{

p=p->next;j++;

}

if(j!=i)

{

printf("Eorror: 取数据元素位置参数出错!\\n");

return 0;

}

*x=p->data;

return 1;

}

7.7 撤消单链表

void Destroy(SLNode **head)

{

SLNode *p,*p1;

p=*head;

while(p!=NULL)

{

p1=p;p=p->next;free(p1);

}

*head=NULL;

}

7.8 单链表测试函数

void SingleList(int a[],int al)

{

int i,x;

SLNode *head;

ListInitiate(&head);//向单链表插入数据元素

for(i=0;i{

if(ListInsert(head,i,a[i]) == 0)

{

printf("Error:插入数据元素错误! \\n");return;

}

}

//从单链表取数据元素

printf("结果:");

for(i=0; i{

if(ListGet(head,i,&x) == 0)

{

printf("Error:取数据元素错误! \\n");return;

}

else printf("%d

}

printf("\\n");

Destroy(&head);//撤消单链表

printf("\\n");

}

7.9 单链表合并函数

void CombineList(int a[],int b[],int al,int bl)

{

int i,j=0,x;

int *list;

SLNode *head;

list=(int *)malloc((al+bl)*sizeof(int));

if(al{

//较长数组的数据元素赋给动态数组的偶数位

for(i=0;i<2*al;i+=2)

{

if(i%2==0)

{

list[i]=b[j];j++;

}

}

j=0;//恢复公共下标初始值

//较短数组的数据元素赋给动态数组的奇数位

for(i=0;i<2*al;i++)

{

if(i%2==1)

{

list[i]=a[j];j++;

}

}

//较长数组剩余数据元素赋值

for(i=2*al;i{

list[i]=b[j];j++;

}

}

else//a[]数组的数据元素个数>= b[]数组的数据元素个数{

//较长数组b[]的数据元素赋给动态数组的偶数位

for(i=0;i<2*bl;i+=2)

{

if(i%2==0)

{

list[i]=a[j];j++;

}

}

j=0;//恢复公共下标初始值

//较短数组a[]的数据元素赋给动态数组的奇数位

for(i=0;i<2*bl;i++)

{

if(i%2==1)

{

list[i]=b[j];j++;

}

}

//较长数组a[]剩余数据元素赋值

for(i=2*bl;i{

list[i]=a[j];j++;

}

ListInitiate(&head);

//向单链表插入数据元素

for(i=0;i{

if(ListInsert(head,i,list[i]) == 0)

{

printf("Error:插入A的数据元素错误! \\n");

}

}

free(list);

//从单链表取数据元素

for(i=0;i{

if(ListGet(head,i,&x) == 0)

{

printf("Error:取数据元素错误! \\n");return;

}

else

printf("%d

}

printf("\\n");

Destroy(&head);//撤消单链表

}

7.10 直接插入法排序

for(i=0;i{

temp=list[i+1];

j=i;

while(j>-1 && temp{

list[j+1]=list[j];j--;

}

list[j+1]=temp;

}//直接插入法对数组list[]排序

7.11 操作模块设计

printf("**********数据结构单链表合并测试实验************\\n");printf("**** 1. 测试单链表A ****\\n"); printf("**** 2. 测试单链表B ****\\n"); printf("**** 3. 合并单链表A、B得到单链表C ****\\n"); printf("**** 4. 对单链表C升序排序得到单链表D ****\\n"); printf("**** 0. 退出合并单链表的测试程序****\\n"); printf("**********数据结构单链表合并测试实验************\\n"); …… ……

while(flag==1)

{

printf("输入功能号码:");

scanf("%d

switch(flag)

{

case 1:

printf("测试单链表A\\n");

SingleList(&a,al);

flag=1;//功能循环标志

break;

case 2:

printf("测试单链表B\\n");

SingleList(&b,bl);

flag=1;//功能循环标志

break;

case 3:

printf("测试单链表A、B的合并\\n");

CombineList(&a,&b,al,bl);

flag=1;//功能循环标志

break;

case 4:

printf("测试单链表C的排序\\n");

SortList(&a,&b,al,bl);

flag=1;//功能循环标志

break;

case 0:

printf("Message:欢迎下次再次测试单链表合并程序!\\n");

break;//flag!=0退出程序标志

default:

printf("Error:功能号码选择错误,请重新选择!\\n");

flag=1;//功能循环标志

break;}

}

八、测试程序运行结果：

8.1 测试第1组数据

（1）单链表测试：

测试目的：测试单链表是否能够进行插入、读取等操作。

测试结果：单链表A=30，41，15，12，56，80

单链表B=23，56，78，23，12，33，79，90，55

（2）单链表合并测试：

测试目的：测试两个单链表是否能够按照要求进行合并

测试结果：单链表C=23，30，56，41，78，15，23，12，12，56，33，80，79，90，

55（3）单链表合并后排序测试：

测试目的：测试两个合并后的单链表是否能够升序排序后输出

测试结果：单链表D=12，12，15，23，23，30，33，41，55，56，56，78，79，80，

90

8.2 测试第2组数据

（1）单链表测试：

测试目的：测试单链表是否能够进行插入、读取等操作。

测试结果：单链表A= 30，41，15，12，56，80，23，12，34

单链表B= 23，56，78，23，12

（2）单链表合并测试：

测试目的：测试两个单链表是否能够按照要求进行合并

测试结果：单链表C= 30，23，41，56，15，78，12，23，56，12，80，23，12，34 （3）单链表合并后排序测试：

测试目的：测试两个合并后的单链表是否能够升序排序后输出

测试结果：单链表D= 12，12，12，15，23，23，23，30，34，41，56，56，78，80

8.3 测试说明：

（1）经过反复的程序调试和修改，最终实现了本次课程设计的任务。限于篇幅，程序运行结果只有调试修改正确以后的的运行结果。

（2）为了方便测试，在测试过程中，把要测试的数据直接通过添加数据程序代码导入到程序中。把程序运行结果和理论分析结果进行对比，验证程序的正确性。

8.4 测试结论：

（1）在程序完成编写之后，程序的连接、编译、运行开始不能够正常通过，经过调试、

修改之后，最终都能够正常通过，修改过后的程序中没有语法错误。

（2）把测试结构和理论的分析结构进行对比，通过程序运行结果的观察得知程序运行结果和理论分析结果基本吻合。

（3）通过单链表的操作可以完成两个单链表的合并，除此之外，还能够对单链表合并后的数据元素进行排序。

九、课程设计总结：

9.1 课程设计题目的选择

在本次的数据结构课程设计中，我选择的题目是“实现两个单链表的合并”，从所学习过的知识入手进行课程的设计。程序设计语言选择C语言，由于学习的时间较早，经过一段时间的编程积累用的相对比较熟练。

9.2 对题目的认识

单链表是数据结构里面典型的线性表，适用范围比较广泛，使用方法也相对灵活，在课堂上我们学习了单链表的基本数据结构和单链表的基本操作，但是并没有运用到实际的程序中，这次课程设计把我们的理论知识和程序实践联系起来了。

9.3 编程心得

通过本次的课程设计，使我学会了如何去组织代码量较大大程序。与此同时，也使我学会了一些对代码量较大的的程序进行编写、连接、编译运行、以及调试和修改的技巧。

9.4 课程设计感想

这次的课程设计涉及到编程语言和数据结构的知识，要求和平时的实验相比相对较高。从本次的课程设计可以检验我们对C语言和数据结构的掌握情况，同时也检验了我们对所学习过的知识的灵活运用情况。在创新性方面，这次的课程设计虽然完成了课程设计的任务，但是缺乏创造性的设计思想，在以后的学习过程中还得继续努力。

参考文献资料

[1].严蔚敏编著.数据结构（C语言版）.清华大学出版社，2002

[2].朱战立. 编著.数据结构——使用C语言.西安交通大学出版社，2004

[3].朱战立，张选平编著.数据机构学习指导和典型题解.西安交通大学出版社，2002

[4].苏小红，孙志岗等编著.C语言大学实用教程（第2版）.电子工业出版社，2008

[5].梁肇新编著.编程高手箴言.电子工业出版社，2003

[6].周海燕，赵崇敏等编著.C语言程序设计.科学出版社，2001下载本文