實(shí)現(xiàn)兩個(gè)鏈表的合并.docVIP

實(shí)現(xiàn)兩個(gè)鏈表的合并基本功能要求：（1）建立兩個(gè)鏈表A和B，鏈表元素個(gè)數(shù)分別為m和n個(gè)。（2）假設(shè)元素分別為(x1,x2,xm)，和(y1,y2, yn)。把它們合并成一個(gè)線性表C，使得：當(dāng)m=n時(shí)，C=x1,y1,x2,y2,xn,yn,xm當(dāng)nm時(shí)，C=y1,x1,y2,x2,ym,xm,yn輸出線性表C：（1） 用直接插入排序法對(duì)C進(jìn)行升序排序，生成鏈表D，并輸出鏈表D。測(cè)試數(shù)據(jù)：（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) 結(jié)構(gòu)體struct Node的創(chuàng)建。(2) struct Node *create（）鏈表的創(chuàng)建。(3) void print(struct Node *head)功能是對(duì)鏈表進(jìn)行輸出。(4) struct Node * inter_link(struct Node * chain1, int a, struct Node * chain2, int b)算法的功能是實(shí)現(xiàn)兩個(gè)鏈表的交叉合并，并且可以根據(jù)兩鏈表的長(zhǎng)短將行不通的插入。(5) void InsertSort(struct Node *p,int m)算法的功能是對(duì)一合并好的鏈表進(jìn)行升序插入排序。(6) main()函數(shù)主要是對(duì)算法進(jìn)行測(cè)試。數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)定義如下：struct Node long int number; struct Node *next;源程序：#include#include#include#include#define L sizeof(struct Node)struct Node /結(jié)構(gòu)體 long int number; struct Node *next;struct Node *create(int a)/鏈表創(chuàng)建函數(shù) int n; struct Node *p1, *p2, *head; head = NULL; n = 0; p2 = p1 = (struct Node *) malloc(L); /分配內(nèi)存 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); if (a != 1)/分配內(nèi)存 scanf(%ld, &p1-number); a-; /控制輸入的個(gè)數(shù) p2-next = NULL; return (head);/鏈表創(chuàng)建函數(shù)結(jié)束void print(struct Node *head)/輸出函數(shù) struct Node *p; p = head; printf(數(shù)字:n); if (head != NULL) do/循環(huán)實(shí)現(xiàn)輸出 printf(%ld, p-number); printf( ); p = p-next; while (p != NULL); printf(n);/鏈表的交叉合并算法struct Node * inter_link(struct Node * chain1, int a, struct Node * chain2, int b) int temp; struct Node *head, *p1, *p2, *pos; /*判斷a，b大小并合并 */ if (a = b) head = p1 = chain1; p2 = chain2; else/*ba*/ head = p1 = chain2; p2 = chain1; temp = a, a = b, b = temp; /*交換a和b*/ /*下面把p1的每個(gè)元素插在p2相應(yīng)元素之前，p1長(zhǎng)a,p2長(zhǎng)b*/ pos = head; /*此時(shí)pos指向p1中的第一個(gè)元素*/ while (p2 != NULL) /漂亮，蛇形插入 p1 = p1-next; pos-next = p2; pos = p2; p2 = p2-next; pos-next = p1; pos = p1; return head;/對(duì)合并好的鏈表進(jìn)行排序void InsertSort(struct Node *p, int m)/排序函數(shù) int i, j, t; struct Node *k; k = p; for (i = 0; i m - 1; i+) for (j = 0; j number (p-next)-number) t = p-number; p-number = (p-next)-number; (p-next)-number = t; p = p-next; p = k; /主函數(shù)int main()/main函數(shù) struct Node *p1, *p2; int a; int b; int h; printf(請(qǐng)輸入第一個(gè)鏈表:n); printf(n輸入鏈表的長(zhǎng)度a:n); scanf(%d, &a); printf(請(qǐng)輸入鏈表數(shù)據(jù)：); p1 = create(a); printf(n你剛才輸入的第一個(gè)鏈表信息:n ); print(p1); printf(n 請(qǐng)輸入第二個(gè)鏈表:n); printf(n輸入鏈表的長(zhǎng)度b:n); scanf(%d, &b); printf(請(qǐng)輸入鏈表數(shù)據(jù)：); p2 = create(b); printf(n你剛才輸入的第二個(gè)鏈表的信息:n); print(p2); p1 = i