实现两个链表的合并(数据结构课程设计c语言版)
课程设计报告课程设计题目：实现两个链表的合并
学生姓名黎微微
专业计算机信息管理
班级1141301
指导教师吴志强
2013年01月08 日
一、课程设计目的：
课程设计为学生提供了一个既动手又动脑，独立实践的机会，将课本上的理论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。提高学生适应实际，实践编程的能力。
二、课程设计题目：
实现两个链表的合并
要求：1）输入2个单链表
2）输出2个单链表合并后形成的结果。
三、模块划分：
（1）数据模块
参考使用课本上的具有头结点的链表抽象数据类型linklist，该抽象数据类型中包含一个elemtype类型的数据和一个指针，在开始用时，elemtype定义为整型变量，指针用来指向下一个元素。对应的使用链表抽象数据类型linklist基本操作的函数有：初始化操作函数void ini(linklist *s)。
（2）创建链表模块
void create(linklist *s)
其功能是创建链表录入数据。
（3）输出数据模块
void display(linklist *s)
其功能为是输出s链表中的各项元素，从而验证操作是否成功
（4）排序模块
void sort(linklist *s)
此函数功能是s链表使用冒泡法对链表进行排序
（5）合并链表模块
void add(linklist *s1,linklist *s2)
其功能是按照题目要求实现两个链表的合并，将s2链表插入到s1链表中。
（6）主函数模块
void main()，函数中调用了各个模块的函数，从而实现了题目合并排序的要求
四、流程图：
Creat s1链表
对s1进行排序
Creat s2链表
对s2进行排序
对排序后的s1.s2链表合并
S1为null s1!=null
S1=s2 将s2插入
s1中
显示s1（即合并后的链表）
结束
五、算法设计分析
这个两个链表的交叉合并算法主要运用到的是链表的基本操作，定义节点，将链表的创建、链表的插入、链表内容升序排列，通过主函数调用。这样就大大精简了主函数的操作。但主函数中很大篇幅用到了if、else语句，用以指定链表指定结点，这样就使得本来很精简变得繁琐，降低了程序的质量。所以其有优点和缺点，但需要不断的改进，不断优化该程序。
六、数据结构：
（1）数据类型DataType定义如下：
typedef int elemtype;
（2）带头结点链表抽象数据类型的结点结构定义如下：
typedef struct node
{
elemtype data;
struct node *next;
}linklist;
七、源程序：
#define null 0
typedef int elemtype;
typedef struct node
{
elemtype data;
struct node *next;
}
lin;
void inia(lin *a)
{
a->next=null;
}
void create(lin *a)
{ lin *p,*q=a;
elemtype e;
printf("please input the data;\n"); scanf("%d",&e);
while(e!=-1)
{
p=(lin *)malloc(sizeof(lin));
p->data=e;
q->next=p;
q=q->next;
scanf("%d",&e);
}
q->next=null;
}
void display(lin *a)
{
lin *p=a->next;
if(a->next==null)
printf("the lin is empty!\n"); else
{
printf("output the data:\n"); while(p!=null)
{
printf("%5d",p->data);
p=p->next;
}
}
printf("\n");
}
void sort(lin *a)
{
lin *p,*q;
elemtype t;
p=s->next;
while(p!=null)
{
q=p->next;
while(q!=null)
{
if(p->data>q->data)
{ t=p->data;
p->data=q->data;
q->data=t;
}
q=q->next;
}
p=p->next;
}
}
void add(lin *s1,lin *s2)
{
lin *p1=a1->next,*p2=a1,*q1=a2->next,*q2=a2;
if(s1==null)
a1=a2;
while(p1!=null&&q1!=null)
{
if(p1->data
{ p1=p1->next;
p2=p2->next
}
else
{ q2->next=q1->next;
q1->next=p2->next;
p2->next=q1;
p2=p2->next;
q1=q2->next;
}
}
if(q1!=null)
p2->next=q1;
} void main()
{
lin *a1,*a2;
s1=(lin *)malloc(sizeof(lin));
inia(a1);
create(a1);
display(a1);
sort(a1);
display(a1);
a2=(lin *)malloc(sizeof(lin));
inia(a2);
create(a2);
display(a2);
sort(a2);
display(a2);
add(a1,a2);
display(a1)
}
八、实验运行结果显示：
九、实验收获和体会：
这次的课程设计，加强了我们动手、思考和解决问题的能力。巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。培养了我选用参考书，查阅手册及文献资料的能力。从中我意识到程序的成功不仅仅是消除语法上的错误，而且还要执行成功。缺乏完整的思路，尽管语法正确，程序还是无法执行。数据结构的设计考验的不仅仅是我们对书本知识的理解，还考验了我们分析事物时思维的逻辑紧密性，加深并巩固了我对数据结构的认识。平时看课本时，有些问
题就不是很能理解，做完课程设计，那些问题就迎刃而解了。而且还可以记住很多东西。认识来源于实践，实践是认识的动力和最终目的，实践是检验真理的唯一标准。所以这个期末测试之后的课程设计对我们的作用是非常大的。
将递增有序的单链表A和B合并成递减有序的单链表C
将递增有序的单链表A和B合并成递减有序的单链表C 实现程序如下： #include
算法设计题打印部分
算法设计题打印部分 假设有两个按元素值递增次序排列的线性表均以单链表形 式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表并要求利用原来两个单链表的结点存 放归并后的单链表。【北京大学1998 三、1 5分】类似本题的另外叙述有1设有两个无头结点的单链表头指针分 别为hahb链中有数据域data链域next两链表的数据都按递增序存放现要求将hb表归到ha表中且归并后ha仍递增序归并中ha表中已有的数据若hb中也有则hb中的数据不归并到ha中hb的链表在算法中不允许破坏。【南京理工大学1997 四、315分】PROCEDURE mergehahb 2已知头指针分别为la和lb 的带头结点的单链表中结点按元素值非递减有序排列。写出将la 和lb两链表归并成一个结点按元素值非递减有序排列的单链表其头指针为lc并计算算法的时间复杂度。【燕山大学1998 五20分】 2. 图编者略中带头结点且头指针为ha和hb的两线性表A和B 分别表示两个集合。两表中的元素皆为递增有序。请写一算法求A和B的并集AUB。要求该并集中的元素仍保持递增有序。且要利用A和B的原有结点空间。【北京邮电大学1992 二15分】类似本题的另外叙述有1 已知递增有序的两个单链表AB分别存储了一个集合。设计算法实现求两个集合的并集的运算A:A∪B【合肥工业大学1999 五、18分】2已知两个链表A和B分别表示两个集合其元素递增排列。编一函数求A与
B的交集并存放于A链表中。【南京航空航天大学2001 六10分】3设有两个从小到大排序的带头结点的有序链表。试编写求这两个链表交运算的算法即L1∩L2。要求结果链表仍是从小到大排序但无重复元素。【南京航空航天大学1996 十一10分】4己知两个线性表A B均以带头结点的单链表作存储结构且表中元素按值递增有序排列。设计算法求出A 与B的交集C要求C另开辟存储空间要求C同样以元素值的递增序的单链表形式存贮。【西北大学2000 五8分】5已知递增有序的单链表AB和C分别存储了一个集合设计算法实现AA∪B∩C并使求解结构A 2 仍保持递增。要求算法的时间复杂度为OABC。其中A为集合A的元素个数。【合肥工业大学2000 五、18分】3. 知L1、L2分别为两循环单链表的头结点指针mn分别为L1、L2表中数据结点个数。要求设计一算法用最快速度将两表合并成一个带头结点的 循环单链表。【东北大学1996 二12分】类似本题的另外叙述有1试用类Pascal语言编写过程PROC joinVAR lalink lblink 实现连接线性表la和lblb在后的算法要求其时间复杂度为01 占用辅助空间尽量小。描述所用结构。【北京工业大学1997 一、1 8分】2设有两个链表ha为单向链表hb 为单向循环链表。编写算法将两个链表合并成一个单向链表要求算法所需时间与链表长度无关。【南京航空航天大学1997 四8分】4. 顺序结构线性表LA与LB的结点关键字
链表习题高考真题
（2）下列程序的功能是实现向head指向的链表中插入新结点s，如图17所示，使该链表按结点的id值保持升序排列。 图17 #include
数据结构课后习题及解析第二章
第二章习题 1. 描述以下三个概念的区别：头指针，头结点，首元素结点。 2. 填空： （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4. 设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5. 写一算法，从顺序表中删除自第i个元素开始的k个元素。 6. 已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7. 试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2）以单链表作存储结构。 8. 假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。
两个线性表合并成一个线性表
#include
if( (pa->data) <= (pb->data) ) { pc->next=pa; pc=pc->next; pa=pa->next; } else { pc->next=pb; pc=pc->next; pb=pb->next; } } if(pa) { pc->next=pa; } if(pb) { pc->next=pb; } pc=lc->next; while(pc) { printf("%d\t",*pc); pc=pc->next; } printf("\n"); }
数据结构经典算法试题
1．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学1998 三、1 （5分）】 LinkedList Union(LinkedList la,lb) { pa=la->next; pb=lb->next; la->next=null; while(pa!=null && pb!=null) ∥当两链表均不为空时作 if(pa->data<=pb->data) { r=pa->next; pa->next=la->next; ∥将pa结点链于结果表中，同时逆置。 la->next=pa; pa=r; } else {r=pb->next; pb->next=la->next; ∥将pb结点链于结果表中，同时逆置。 la->next=pb; pb=r; } while(pa!=null) ∥将la表的剩余部分链入结果表，并逆置。 {r=pa->next; pa->next=la->next; la->next=pa; pa=r; } while(pb!=null) {r=pb->next; pb->next=la->next; la->next=pb; pb=r; } }
1）设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏。【南京理工大学1997 四、3（15分）】 LinkedList Union(LinkedList ha, hb)∥ha和hb是两个无头结点的数据域值递增有序的单链 ｛LinkedList 表，本算法将hb中并不出现在ha中的数据合并到ha中，合并中不能破坏hb链表。 la; la=(LinkedList)malloc(sizeof(LNode)); la->next=ha; pa=ha; pb=hb; pre=la; while(pa&&pb) if(pa->data
c语言实现单链表的合并 归并算法
#include
if(integer != -1) { s=(Node*)malloc(sizeof(Node)); s->data=integer; r->next=s; r=s; } else { flag=0; r->next=NULL; } } } void UnionList(LinkList &LA,LinkList &LB,LinkList &LC) { Node *p,*q,*r,*y; p=LA->next; q=LB->next; r=LC; while (p)
{ y=(Node*)malloc(sizeof(Node)); y->data=p->data; r->next=y; r=y; p=p->next; } while (q) { y=(Node*)malloc(sizeof(Node)); y->data=q->data; r->next=y; r=y; q=q->next; } r->next=NULL; } void DeSameList(LinkList *LC)//删除c表的相同元素。{ Node *p,*q,*r; for(p=(*LC)->next;p!=NULL;p=p->next)
实验报告03-两个有序链表的合并
实验目的及要求： 了解和掌握链表的特点； 掌握链表基本操作的实现； 掌握两个有序链表合并的算法 要求完成链表的初始化、插入、有序表合并、显示操作的实现。实验设备环境及要求： PC机一台，内存要求128M以上，VC++6.0集成开发环境。 实验内容与步骤： 1、在VC++6.0环境中新建一个工程和C++文件； 2、实现链表初始化、插入、有序合并算法，代码如下： #include
LinkList p=L->next; if(!p) printf("此链表为空！"); while(p){ printf("%d",p->data); p=p->next; } printf("\n"); } void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){ LinkList pa=La->next; LinkList pb=Lb->next; LinkList pc=Lc=La; while(pa&&pb){ if(pa->data<=pb->data){ pc->next=pa;pc=pa;pa=pa->next; } else{ pc->next=pb;pc=pb;pb=pb->next; } } pc->next=pa?pa:pb; free(Lb); } void main(){ LinkList La,Lb,Lc; InitList_L(La); InitList_L(Lb); InitList_L(Lc); ListInsert_L(La,1,2); ListInsert_L(La,2,3); ListInsert_L(La,3,5); Disp_L(La); ListInsert_L(Lb,1,1); ListInsert_L(Lb,2,4); ListInsert_L(Lb,3,6); ListInsert_L(Lb,4,7); Disp_L(Lb); MergeList_L(La,Lb,Lc); printf("合并之后的链表为:\n"); Disp_L(Lc); }实验指导与数据处理：
实现两个链表的合并
实现两个链表的合并 基本功能要求： （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 输出线性表C： （1）用直接插入排序法对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)结构体struct Node的创建。 (2)struct Node *create（）链表的创建。 (3)void print(struct Node *head)功能是对链表进行输出。 (4)struct Node * inter_link(struct Node * chain1, 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; };
两个有序链表的合并
《数据结构》实验报告 班级：JS001001 姓名：周卫华学号：2010300028 E-mail:770234417@https://www.wendangku.net/doc/e2416274.html, ◎实验题目: 将两个带头结点的有序循环链表合并成一个带头结点的有序循环链表 ◎实验目的：1.掌握使用visual c++6.0上机调试程序的基本方法。 2.掌握线性表的链式存储结构-循环链表的定义及C语言实现。 3.掌握线性表在链式存储结构-循环链表中的基本操作如将两个循环链表合并为一个循环链表的操作。 ◎实验内容：设A与B分别为两个带有头结点的有序循环链表（所谓有序是指链接点按数据域值大小链接，本题不妨设按数据域值从小到大排列），list1和list2分别为指向两个链表的头指针。将这两个链表合并为一个带头结点的有序循环链表。 一、需求分析 本程序需要实现将两个有序循环链表合成一个有序循环链表的功能，即对这个程序输入两个有序循环链表，该程序输出一个有序循环链表。对于输入的两个循环链表要求是必须是有序非递减的，如1，2，3，5，7符合输入条件，但是3，5，4，7，2，9则不符合输入条件。输入值可以是任意实数。输出的有序循环链表依赖于输入的两个有序循环链表。如输入的两个链表为1，3，4，6，8；2，5，7，9则输出的链表为1，2，3，4，5，6，7，8，9.上面展示了输入正确时的预期输出，当输入不正确时则不能得到正确的输出，如输入1，3，5，4，6；2，5，3，7时输出为1，2，3，5，4，5，3，6，7显然不正确。 二、概要设计 按照题意，本程序中使用单向循环链表作为存储结构，每一个节点为结构体类型，存放数据和下一个节点的地址。基本流程如下：定义三个该结构体类型的指针变量list1,list2,head；期中list1,list2用来构造存放输入数据的两个循环链表的头指针，head 用来作为生成的第三个循环链表的头指针。接下来主函数调用creat()函数并手工输入数据构成两个待合并链表。然后调用print()函数用来打印list1,list2来验证构造的链表正确。链表构造完成后调用mergell()函数来合并list1,list2并存放在head中，最后把head打印出来。本程序主要模块有：主程序模块，构造链表并输入数据模块，打印输出链表模块，合并链表模块。 三、详细设计 1.元素类型，节点类型和指针类型： 元素类型：int num;int lista=0,listb=0; 节点类型： struct list { int num; struct list *next; }; 指针类型：struct list *head,*end;struct list *pa,*pb,*pc; struct list *list1,*list2,; 2．每个模块的分析： （1）主程序模块： int main() //主函数
将两个递增链表合并成一个递减的链表
#include"stdio.h" #include"stdlib.h" struct Node {int date; struct Node *next; }Node; goujian(struct Node *L) { struct Node *s,*p; int e;p=L; printf("输入数据："); scanf("%d",&e); while(e!=-999) {s=(struct Node *)malloc(sizeof(struct Node)); s->date=e; s->next=p->next; p->next=s; scanf("%d",&e); p=s;} } outline(struct Node *L) {struct Node *p; p=L->next; printf("输出数据："); while(p!=NULL) {printf("%d ",p->date); p=p->next; } } hebing(struct Node *h1,struct Node *h2) {struct Node *q,*p,*r,*s; p=h1->next; q=h2->next; r=h1; r->next=NULL; while(p!=NULL&&q!=NULL) {if(p->date<=q->date) { s=p; p=p->next; s->next=r->next; r->next=s; } else {
s=q; q=q->next; s->next=r->next; r->next=s; } if(q==NULL) {while(p!=NULL) {s=p; p=p->next; s->next=r->next; r->next=s;} } if(p==NULL) {while(q!=NULL) { s=q; q=q->next; s->next=r->next; r->next=s;} } } free(h2); } void main() {struct Node *h1,*h2; h1=(struct Node *)malloc(sizeof(struct Node)); h2=(struct Node *)malloc(sizeof(struct Node)); h1->next=NULL; h2->next=NULL; goujian(h1); goujian(h2); hebing(h1,h2); outline(h1); }
将两个单链表合并成一个并且不改变其排序性
将两个单链表合并成一个并且不改变其排序性 #include
scanf("%d",&x); } return L; } void pur_LinkList(LinkList H) { LNode *p,*q,*r; p=H->next;//指向第1个数据元素的结点 while(p) { q=p; while(q->next) { if(q->next->data==p->data) { r=q->next; q->next=r->next; free (r); } else q=q->next; }
p=p->next; } } void print(LinkList h) {LinkList H; H=h->next;//指向第1个结点 while(H) { printf("%6d",H->data); H=H->next; } printf("\n"); } main() {LinkList H;//单链表头指针的值 H=Creat_LinkList1(); print( H); pur_LinkList(H); print( H); }
两个升序表合并成一个降序表
#include "stdafx.h" #include
LNode *p,*q,*s; p=A->next; // p指向链表A的第一个未比较的数据结点 q=B->next; // q指向链表B的第一个未比较的数据结点 *C=A; //生成链表的*C的头结点 (*C)->next=NULL; free(B); //释放链表B的头结点空间 while(p!=NULL&&q!=NULL) //将A、B两链表中当前比较结点中值小的元素赋给*s { if(p->data
实现两个链表的合并(数据结构课程设计c语言版)
课程设计报告课程设计题目：实现两个链表的合并 学生姓名 专业 班级 指导教师 2012年06 月21 日
一、课程设计目的： 课程设计为学生提供了一个既动手又动脑，独立实践的机会，将课本上的理论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。提高学生适应实际，实践编程的能力。 二、课程设计题目： 实现两个链表的合并 要求：1）输入2个单链表 2）输出2个单链表合并后形成的结果。 三、模块划分： （1）数据模块 参考使用课本上的具有头结点的链表抽象数据类型linklist，该抽象数据类型中包含一个elemtype类型的数据和一个指针，在开始用时，elemtype定义为整型变量，指针用来指向下一个元素。对应的使用链表抽象数据类型linklist基本操作的函数有：初始化操作函数void ini(linklist *s)。 （2）创建链表模块 void create(linklist *s) 其功能是创建链表录入数据。 （3）输出数据模块 void display(linklist *s) 其功能为是输出s链表中的各项元素，从而验证操作是否成功 （4）排序模块 void sort(linklist *s) 此函数功能是s链表使用冒泡法对链表进行排序 （5）合并链表模块
void add(linklist *s1,linklist *s2) 其功能是按照题目要求实现两个链表的合并，将s2链表插入到s1链表中。（6）主函数模块 void main()，函数中调用了各个模块的函数，从而实现了题目合并排序的要求 四、流程图： Creat s1链表 对s1进行排序 Creat s2链表 对s2进行排序 对排序后的s1.s2链表合并 S1为null s1!=null S1=s2 将s2插入 s1中 显示s1（即合并后的链表） 结束
实现两个链表的合并 课程设计报告
目录 一需求分析 (1) 二概要设计 (2) 三详细设计 (3) 四调试分析与测试结果 (5) 五总结 (6) 六参考文献 (7) 七致谢 (8) 八附录 (9)
一需求分析 题目：实现两个链表的合并 问题描述： （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 输出线形表C （5）用直接插入排序法对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） 由题目的相关信息可以分析得：首先我们需要建立两个链表AB，A链表的元素个数为m，B链表的元素个数为n；在将A、B链表进行合并，根据m和n的大小关系决定链表C的元素顺序；再将C进行直接插入排序得到一个新的链表D；最后输出四个链表ABCD的相关信息。
本次课程设计所需要用到的是关于链表的建立、合并以及直接插入排序的排序算法。需要先建立两个链表，再将其合并为一个无序链表，最后对这个无序链表进行直接插入排序并将其输出。难点在于将AB合并为链表C的操作以及对链表C进行直接插入排序的操作。 图1.链表合并的流程图
我所负责的直接插入排序的代码编写以及主函数的编写。直接插入排序的定义如下：把n个待排序的元素看成一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含n-1个元素，排序过程中每次从无序表中取出第一个元素，把他的排序吗一次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表；主函数的编写则是调用AB链表初始化函数，再调用合并AB链表函数，再调用直接插入排序函数，最后依次输出ABCD四个链表的相关信息。 void SortCToD() { struct Node *pre, *postC, *postD, *lopD; int len; //表示总的长度 len = m + n; pre = D; //指向D有序数列的尾指针 postC = C->next; //指向C列表 //列表D第一个节点加入postD = new Node; //分配一个新的节点 postD->data = postC->data; //将D的值赋给C postD->next = 0; //D的下一个节点为0 pre->next = postD; //pre的下一个节点指向D pre = postD; //pre指向D postC = postC->next; //指向下一个节点 while (postC) { //pre为指向插入的前一个节点，lopD 是指向插入的后一个节点 pre = D; //pre指向D lopD = D->next; //lopD指向D的下一个节点 while (lopD) //当D不为空 { if (lopD->data > postC->data) //判断条件 break; else { pre = lopD; //pre指向D lopD = lopD->next; //指向下一个节点
攻坚实验二 两个有序链表序列的交集
攻坚实验二两个有序链表序列的交集 一、实验目的 1．熟练掌握循环控制语句。 2．熟练掌握构造新链表方法。 3．熟练掌握链表的遍历查找操作与结点插入操作。 二、实验内容 已知两个非降序链表序列S1和S2,设计函数构造出S1与S2的交集新链表S3。 三、实验要求 1. 输入说明：输入分2行，分别在每行给出由若干个正整数构成的非降序序列，用-1表示序列的结尾（-1不属于这个序列）。数字用空格间隔2．输出说明：在一行中输出两个输入序列的交集序列，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。 四、实验分析 （1）问题分析 设序列S1与S2的长度分别为N1和N2。求交集可从两个序列的列首开始比较，不断将相等的值移入新序列，并注意过程中不断更新下一次要比较的链表指
针，需O(min(N1,N2))时间。 可以令结点指针P1指向S1的首结点，P2指向S2首结点，不断比较P1与P2所指结点的值：若两结点值相等，则创建新结点将这个值插入到新链表S3的末尾，并将P1与P2分别往前移(P=P->next);若不相等，将较小结点的对应结点指针往前移。 创建结点时，注意用malloc函数申请内存；由于每次总是插入S3末尾，可以用指针变量pRear指向S3尾结点，添加新结点时插入pRear结点之后并更新pRear。 如此反复直到某个链表遍历完，即P1或P2为空为止。 （2）实现要点 使用带空头结点的链表结构，可以简化程序。注意检查边界情况，例如当某个链表序列为空时的情况。 五、主要仪器及耗材 计算机及VC6软件 六、实验注意事项 1.应分析源程序，并注意运行结果是否为预期结果。 2.注意大小写及英文字符（ASCII码） 七、思考题 1.如果允许利用和修改链表S1和S2,如何在不申请新内存的情况下，构造出其交集序列链表？
链表的合并
B．学生模拟题（SC6_6B.cpp） 【题目描述】 有2个从小到大已经排序好的（有序）表，每个结点的数据是1个整数，已知两个表的数据存放在带头结点的单向链表中，将2个有序表合并成1个新的有序表，并要求新的有序表中去掉重复相同的数据。打开SC6_6B.cpp文件，完成程序的编写。 【输入】 输入文件SC6_6B.in有4行，第1行有1个整数n，即第1个表的结点数，第2行有n 个整数；第3行有1个整数m，即第2个表的结点数，第4行有m个整数。整数之间用空格隔开。 【输出】 输出文件SC6_6B.out有1行，将上述2个表的数据从小到大排序输出，数据中没有相同项，每个整数之后输出1个空格。 【输入输出样例1】 0≤m,n；1≤m+n；所有数据均为整数。 #include "stdio.h" const int INF=0x7fffffff; //无穷大整数 struct ND { int data; struct ND *next; }; ND *createLink( ) { ND *head, *p; int n; head = p = new ND; scanf("%d", &n); while( n-- ) { p->next = new ND; p = p->next; scanf("%d", &p->data); } p->next = NULL; return head; } void printLink( ND *head ) { ND *p=head->next; if( p==NULL )return ; while( p )
{ printf( "%d ",p->data ); p=p->next; } printf("\n"); } void deleteLink( ND *head) { ND *p=head; while( p ) { head = p->next; delete p; p = head; } } ND * megerLink( ND *ha, ND *hb ) //合并2有序表,返回合并后链表头结点的地址 { ND *pa=ha->next, *pb=hb->next, *hc, *pc; int data, lastData=INF; //lastData为上一个结点的数据项，用于判定是否有相同数据hc=pc=new ND; //************************************************ while(pa||pb){ if(pa&&(pb==NULL||pa->data<=pb->data) ) { data=pa->data; pa=pa->next; } else if(pb&&(pa==NULL||pb->data
数据结构.单链表的合并
[数据结构] 单链表的合并 14 辽宁大学宋文龙 一、实验内容： 1、求La和Lb两集合的并运算，要求占用原来空间。 A、在main函数上边编写一个函数能够实现La和Lb两集合的并运算（合 并后仍然是递增的），例如： void bing(LinkList La,LinkList Lb){ //求La和Lb两集合的并运算,结果用La保存而无需使用LC //因为占用原来空间，所以需释放多余结点 …… } 注意本算法需考虑删除相同的元素，因为我们考虑的集合中没有重复 元素。 B、在main函数中输入数据：(如果是头插法，输入数据时要倒着录) La：1 3 7 8 1520 Lb：2 4 81517 24 90 C、在主函数中调用bing（La,Lb）算法，并输出合并后的La结果： 1 2 3 4 7 8 15 17 20 24 90 二，实验完整代码： #include
LinkList creatlist(LinkList L,int n){ LinkList p,q; int i; L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; p=(LinkList)malloc(sizeof(LNode)); printf("第1个节点值:"); scanf("%d",&(p->data)); p->next=L->next; L->next=p; q=p;//插入第一个结点，for语句插入剩余结点 for(i=n-1;i>0;i--){ p=(LinkList)malloc(sizeof(LNode)); printf("第%d个节点值:",n+1-i); scanf("%d",&(p->data)); p->next=q->next; q->next=p; q=p; } //使用尾插法，创建一个含有n个结点的带头结点的单链表 //也可以使用头插法来创建L return L; //因为链表是动态分配内存，所以创建后头指针需返回，在调用时接收} void show(LinkList L){ //能够输出带头结点的单链表L中的各个结点的值 LinkList p; for(p=L->next;p!=NULL;p=p->next){ printf("%d\t",p->data);