实现两个链表的合并.doc

《实现两个链表的合并.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程设计题目一：实现两个链表的合并题目二：可变长顺序表设计班级：计科1202班姓名：学期：2013-2014学年第二学期题目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） 用直接插入排序法对C进行升序排序，生成链表D，

2、并输出链表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表中的数据元素，在奇数位插入B表中的数据元素，最后在插入A表中剩余的数

3、据元素；当m

4、in1, int a, struct  Node * chain2, int b)算法的功能是实现两个链表的交叉合并，并且可以根据两链表的长短将行不通的插入。(5) void InsertSort(struct  Node  *p,int m)算法的功能是对一合并好的链表进行升序插入排序。(6) main()函数主要是对算法进行测试。数据结构：数据结构定义如下：struct Node    {    long int number;    struct Node *next;};源程序：#include

5、lib.h>#include#include#include#define L sizeof(struct Node) struct Node //结构体{    long int number;    struct Node *next;}; struct Node *create(int a)//链表创建函数{    int n;    struct Node *p1, *p2, *head;    head = NULL;    n = 0;    

6、p2 = p1 = (struct Node *) malloc(L); //分配内存    scanf("%ld", &p1->number);    while (a)//录入链表信息    {        n = n + 1;        if (n == 1)            head = p1;        else            p2->next = p1;        p2 = p1;        p1 = (struct Node *) malloc(L);       

7、 if (a != 1)//分配内存            scanf("%ld", &p1->number);        a--; //控制输入的个数    }    p2->next = NULL;    return (head);}//链表创建函数结束 void print(struct Node *head)//输出函数{    struct Node *p;    p = head;    printf("数字:");    if (head != NULL)        do//循环实现

8、输出        {            printf("%ld", p->number);            printf("     ");            p = p->next;        } while (p != NULL);    printf(""); }//链表的交叉合并算法 struct Node * inter_link(struct Nod