合并链表,实验三

一、目的和要求

1. 掌握链表的数据结构和基本使用方法 2. 掌握链表合并算法

二、实验内容

将两个已经按从小到大顺序排好序的链表 l1, l2 合并成一个新的排好序的链表 l3 。

[ 要求 ] 1) 在 O(n) 时间复杂度内完成。例如不得先连接二表，再整体排序。 2) l1 和 l2 能够由用户输入。

3) 合并后的新链表不占用存储空间，即直接将 l1 和 l2 链接在一起

三、算法见讲义，程序请自行设计。

源代码如下

#include #include #include struct Node { int num; Node * next; };

Node * createTail() { int x; Node *head = NULL, *p = NULL, *tail = NULL;//初始化指针 puts(\"请输入链表的数据内容(end of '.'):\"); //以'.'结束链表的输入 while( 1 == scanf(\"%d\ { p = (Node *)malloc(sizeof(Node)); //为结点创建存储空间 p->num = x; p->next = NULL; if( head == NULL ) { tail = p; head = tail; } else { tail->next = p; tail = p;

} } getchar(); return head; }

Node * Combination(Node* head1, Node* head2) { Node *head3,*tail,*p = head1,*q = head2, *s; if( NULL == p ) return q; if( NULL == q ) return p; tail = p; if( p->num > q->num) tail = q; head3 = tail; while( NULL != p && NULL != q ) { if(p->num <= q->num ) //两个链表的元素进行比较，小的那个值赋给新链表的尾部 { s = p; p = p->next; } else { s = q; q = q->next; } tail->next = s; tail = s; } if( NULL == p ) p = q; s = p; tail->next = s; return head3; }

void print(Node *head) { if( NULL == head ) return; printf(\"\\n显示链表元素: \"); while(head)

{ printf(\"%d \ head = head->next; } puts(\"\\n\"); }

void main( void ) { Node* head1,*head2,*head3; head1 = createTail(); print(head1); head2 = createTail(); print(head2); head3 = Combination(head1,head2); print(head3); }