两个有序链表的合并

《数据结构》实验报告

班级：JS001001 姓名：周卫华学号：2010300028 E-mail:770234417@https://www.wendangku.net/doc/523376406.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() //主函数

printf(" 欢迎使用将两个有序循环链表合并成一个有序循环链表程序");

struct list*list1,*list2,*head;//定义三个struct list类型的指针变量 list1=(struct list *)malloc(sizeof(struct list));

list2=(struct list *)malloc(sizeof(struct list));

head=(struct list *)malloc(sizeof(struct list));//为list1,list2,head 申请空间

printf("\n请按从小到大的顺序输入第一组有序循环链表，以0结束\n"); list1=creat(); //调用创建链表的函数

printf("输入的这组链表是：\n");

print(list1); //打印第一个链表

printf("\n\n请按从小到大的顺序输入第二组有序循环链表，以0结束\n"); list2=creat(); //调用创建链表的函数

printf("输入的这组链表是：\n");

print(list2); //打印第二个循环链表

mergell (list1,list2,head) ; //调用合并两个链表的函数

printf("\n\n合并后的有序循环链表为：\n");

print(head->next);//打印合并后的循环链表

return 0;

}

（2）构造链表并输入每个数据模块：

struct list *creat() //定义创建链表的函数

{

struct list*p=NULL;

struct list*q=NULL; //定义两个活动指针变量

head=NULL;

int num;

scanf("%d",&num);

while(num!=0)

{

p=(struct list *)malloc(sizeof (struct list)); //开辟空间

p->num=num;

if(head==NULL)

head=p;

else

q->next=p;

q=p;

scanf("%d",&num);

}

end=q; //将链表的结尾最后一个结点赋给end

end->next=head; //让最后一个结点的的下个结点的地址不为空而指向头指针

return(head); //返回新建链表的头指针

}

（3）打印已经构造完成的链表模块

void print(struct list*head) //定义打印循环链表的函数

{

struct list*r=head; //定义活动指针变量以输出各节点数据

do

{

printf("%d ",r->num);

r=r->next;

}while(r!=head); //当活动指针重新指向头结点时，循环结束}

（4）合并两个有序循环链表模块

struct list *mergell(struct list *la,struct list *lb,struct list * lc) //定义合并函数

{

struct list *pa,*pb,*pc; //定义三个活动指针变量分别指向la,lb,lc

int lista=0,listb=0;

pc=lc;

pa=la;

pb=lb; //为pa,pb,pc赋值

while(((pa!=la)||(lista==0))&&((pb!=lb)||(listb==0)))//使用while循环语句

{

if(pa->num<=pb->num)

{

pc->next=pa;

pc=pa;

pa=pa->next;

lista=1;

}

else

{

pc=pb;

pb=pb->next;

listb=1;

}

}

if(pa!=la) //如果lb数据已经完成排序而la还有数据未排，则把la未排数据插入到lc后面

{

while(pa!=la)

{

pc->next=pa;

pc=pa;

pa=pa->next;

}

pc->next=lc->next;

}

else //如果la数据已经完成排序而lb还有数据未排，则把lb未排数据插入到lc后面

{

while(pb!=lb)

{

pc->next=pb;

pc=pb;

pb=pb->next;

}

pc->next=lc->next;

}

}

函数调用关系如下所示：

main()

{

creat();

print();

creat();

print();

mergell();

print();

}

3.完整的程序见附件。

四、程序使用说明及测试结果

1.程序使用说明

（1）本程序的运行环境是codeblocks

(2)当程序运行后，界面出现“请按从小到大的顺序输入第一组有序循环链表，以0结束”字样，这时，将第一组有序循环链表输入，并在有效数据后面添加0作为结束标志。接着界面出现“请按从小到大的顺序输入第二组有序循环链表，以0结束”按照同样的方法输入即可。输入完毕后程序会自动输出合并后的有序循环链表。

2.测试结果

当第一组链表为：1，3，5，6，9第二组链表为3，4，5，7，8时，该程序输出为1，3，3，4，5，5，6，7，8，9

3调试过程中遇到的问题及解决办法

在调试发现输出有乱数的问题，后来发现当定义一个结构体指针变量时必须给它

申请一个空间才能实际应用，即struct list*list1,*list2,*head;//定义三个

struct list类型的指针变量

list1=(struct list *)malloc(sizeof(struct list));

list2=(struct list *)malloc(sizeof(struct list));

head=(struct list *)malloc(sizeof(struct list));

另外我对循环结构的应用不够灵活，尤其对循环终止条件的确定比较弱。

4运行界面如下所示

五、实验总结

在刚开始进行编程时，由于大脑中没有形成具体的思路，导致思维比较混乱，到后来我静下心来，采用从上到下的编程方法，将一个大问题分解成几个小问题进行逐一突破，例如我编写了creat（）函数，print()函数，mergell（）函数供main()函数调用，然后对具体的每一个函数进行构思，这样一来我的思路就明确了。不过在这种情况下必须要对函数调用，数据传输，形参实参关系比较理解。以前总是觉得编程算法知道就行了，上机只不过是将它代码化，可是当真的做实验的时候，才发现任何事情都是说起来容易做起来难，不过我相信只要肯下工夫，肯练，肯思考，一定会编出优秀的程序！

将递增有序的单链表A和B合并成递减有序的单链表C

将递增有序的单链表A和B合并成递减有序的单链表C 实现程序如下： #include #include typedef struct node { char data; //data为结点的数据信息 struct node *next; //next为指向后继结点的指针 }LNode; //单链表结点类型 LNode *CreateLinkList() //生成单链表 { LNode *head,*p,*q; int i,n; head=(LNode*)malloc(sizeof(LNode)); //生成头结点 head->next=NULL ; p=head; q=p; //指针q始终指向链尾结点 printf("Input length of list: \n"); scanf("%d", &n); //读入结点数据 printf("Input data of list: \n"); for(i=1;i<=n;i++) //生成链表的数据结点 { p=(LNode *)malloc(sizeof(LNode)); //申请一个结点空间 scanf("%d",&p->data); p->next=NULL; q->next=p; //在链尾插入 q=p; } return head; //返回指向单链表的头指针head } void Merge(LNode *A,LNode *B,LNode **C) { //将升序链表A、B合并成降序链表*C 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->datadata) { s=p; p=p->next;

算法与数据结构习题

《算法与数据结构》习题1 第一部分 一、单项选择题 1.（）二叉排序树可以得到一个从小到大的有序序列。 A、先序遍历 B、中序遍历 C、后序遍历 D、层次遍历 2.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i 结点的左孩子结点的编号为（）。 A、2i+1 B、2i C、i/2 D、2i-1 3.设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序 列为（）。 A、q=p->next；p->data=q->data；p->next=q->next；free(q)； B、q=p->next；q->data=p->data；p->next=q->next；free(q)； C、q=p->next；p->next=q->next；free(q)； D、q=p->next；p->data=q->data；free(q)； 4.设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得 到序列为（）。 A、BADC B、BCDA C、CDAB D、CBDA 5.设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。 A、n B、n-1 C、m D、m-1 6.设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。 A、O(1) B、O(log2n) C、O(nlog2n) D、O(n2) 7.设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。 A、25 B、10 C、7 D、1 二、填空题 1.设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A 的后面插入结点X的操作序列为______=p；s->right=p->right；______=s； p->right->left=s；（设结点中的两个指针域分别为left和right）。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为______。 3.设一棵三叉树中有50个度数为0的结点，21个度数为2的结点，则该二叉树中度数为 3的结点数有______个。 4.后缀算式9 2 3 + - 10 2 / -的值为______。中缀算式（3+4X）-2Y/3对应的后缀算式 为______。 5.设初始记录关键字序列为(K1，K2，…，Kn)，则用筛选法思想建堆必须从第______个元 素开始进行筛选。 6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点

算法设计题打印部分

算法设计题打印部分 假设有两个按元素值递增次序排列的线性表均以单链表形 式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表并要求利用原来两个单链表的结点存 放归并后的单链表。【北京大学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的结点关键字

[计算机软件及应用]23490数据结构习题答案

第2章线性表 2．算法设计题 （1）将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。 void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){ pa=La->next; pb=Lb->next; Lc=pc=La; //用La的头结点作为Lc的头结点 while(pa && pb){ if(pa->datadata){ pc->next=pa;pc=pa;pa=pa->next;} else if(pa->data>pb->data) {pc->next=pb; pc=pb; pb=pb->next;} else {// 相等时取La的元素，删除Lb的元素 pc->next=pa;pc=pa;pa=pa->next; q=pb->next;delete pb ;pb =q;} } pc->next=pa?pa:pb; //插入剩余段 delete Lb; //释放Lb的头结点} （2）将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。 void union(LinkList& La, LinkList& Lb, LinkList& Lc, ) { pa = La->next; pb = Lb->next; // 初始化 Lc=pc=La; //用La的头结点作为Lc的头结点 Lc->next = NULL; while ( pa || pb ) { if ( !pa ) { q = pb; pb = pb->next; } else if ( !pb ) { q = pa; pa = pa->next; } else if (pa->data <= pb->data ) { q = pa; pa = pa->next; } else { q = pb; pb = pb->next; } q->next = Lc->next; Lc->next = q; // 插入 } delete Lb; //释放Lb的头结点} （3）已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出A与B的交集，并存放于A链表中。 void Mix(LinkList& La, LinkList& Lb, LinkList& Lc, ) { pa=la->next;pb=lb->next;∥设工作指针pa和pb； Lc=pc=La; //用La的头结点作为Lc的头结点 while(pa&&pb) if(pa->data==pb->data)∥交集并入结果表中。 { pc->next=pa;pc=pa;pa=pa->next;

链表习题高考真题

（2）下列程序的功能是实现向head指向的链表中插入新结点s，如图17所示，使该链表按结点的id值保持升序排列。 图17 #include #include typedef struct Node{ int id; char *name; struct Node *next; }Node; void Innode(Node *head,int id,char *str) { int j=0; Node *p,*q,*s; p=head; while( ④) { q=p; p=p->next; } s=(Node*)malloc(sizeof(Node)); s->id=id; s->name=str; ⑤ ⑥ } main() { /*省略创建链表head的代码*/ Innode(head,3,”Jone”); } 36．Merge函数用于将两个升序的链表head1和head2合并成一个链表，并保持合并后链表依然升序。排序的依据为结构体类型Node中的data成员，合并中不得删除节点。下面给出Merge函数的主体框架,在空出的五个位置补充该主体框架缺失的代码段。注意：不能定义新的变量，可不用已定义的某些变量。 typedef struct Node { int data； struct Node *next； }Node； Node *Merge(Node *head1，Node *head2) { if ( head1==NULL) return head2； if(head2==NULL) return headl； Node *head=NULL；//head指针用于指向合并后链表的头结点 Node *pl=NULL； Node *p2=NULL； if(headl->datadata){ head=headl； ______①______

数据结构课后习题及解析第二章

第二章习题 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 #include //节点结构 struct LinkList { int data; struct LinkList * next; }; void main() { int a[8]={1,3,4,7,7,8,34,45}; int b[9]={1,2,4,7,9,12,33,43,56}; LinkList *pa=NULL; LinkList *pb=NULL; LinkList *pc=NULL; LinkList *la=NULL;//la,lb,lc保存链表首地址 LinkList *lb=NULL; LinkList *lc=NULL; // 初始化单链表 for(int i=7;i>=0;i--) { pa=(LinkList *) malloc(sizeof(struct LinkList)); pa->data=a[i]; pa->next=la; la=pa; } for(int j=8;j>=0;j--) { pb=(LinkList *) malloc(sizeof(struct LinkList)); pb->data=b[j]; pb->next = lb; lb=pb; } lc=pc=(LinkList *) malloc(sizeof(struct LinkList));//LC指向单链表的头节点 //递增排序 while(pa && pb) {

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->datadata)∥处理ha中数据 {pre->next=pa;pre=pa;pa=pa->next;} else if(pa->data>pb->data)∥处理hb中数据。 {r=(LinkedList)malloc(sizeof(LNode)); r->data=pb->data; pre->next=r; pre=r; pb=pb->next;} Else∥处理pa- >data=pb->data; {pre->next=pa; pre=pa; pa=pa->next;∥两结点数据相等时，只将ha的数据链入。 pb=pb->next; } if(pa!=null)pre->next=pa;∥将两链表中剩余部分链入结果链表。 else pre->next=pb; free(la); }

c语言实现单链表的合并 归并算法

#include #include typedef struct Node { int data; struct Node *next; }Node, *LinkList; LinkList LA,LB,LC; void InitList(LinkList *L) //初始化单链表 { *L=(LinkList)malloc(sizeof(Node)); (*L)->next=NULL; } void EnterList(LinkList &L) //尾插法创建单链表。{ Node *s,*r; int flag=1,integer; r=L; while(flag) { scanf("%d",&integer);

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)

数据结构作业标准答案

第一章 单选题 1、下列关于算法的基本特征，说法不正确的是（）。能行性是算法中的每一个步骤必须能够实现且能达到预期的目的。算法的确定性是指算法中的每一个步骤必须是有明确的定义，不允许模棱两可。 算法的有穷性是指算法必须能在有限的时间内做完。算法与提供情报无关。 [D] 教师批改：D 2、算法的时间复杂度取决于（）。问题的规模待处理的数据的初态 问题的难度 A 和B [D] 教师批改：D 3、下列选项中，不是算法基本特征的是（）。可行性有穷性 确定性高效率 [D] 教师批改：D 4、通常一个好的算法应达到的目标中，不包括（）。正确性可读性 技巧性健壮性 [C] 教师批改：C 5、在一般的计算机系统中，基本的运算和操作不包括（）。语法处理算术运算 关系运算数据传输 [A] 教师批改：A 6、工程上常用的分治法是（）。列举法归纳法 减半递推技术回溯法 [C] 教师批改：C 多选题 7、算法设计的要求包括（）。 正确性可读性 健壮性唯一性 [ABC] 教师批改：A，B，C 8、算法的时间复杂度应该与（）无关。 所使用的计算机程序设计语言 基本运算的执行次数程序编制者 [ABD] 教师批改：A，B，D 9、下列关于算法的描述中，不正确的有（）。 算法即是计算机程序算法是解决问题的计算方法 算法是排序方法算法是解决问题的有限运算序列 [ABC] 教师批改：A，B，C 填空题 16、所谓算法是指（）。 教师批改：解题方案的准确而完整的描述 17、算法的基本特征有（）、（）、（）和（） 教师批改：能行性、确定性、有穷性和拥有足够的情报。

18、一个算法通常由两种基本要素组成，它们是（）和（）。 教师批改：算法中对数据的运算和操作。 算法的控制结构。 19、工程上常用的几种算法设计方法有列举法、（）、（）、（）、（）和回溯法。 教师批改：归纳法、递推、递归、减半递推技术。 20、算法的复杂度主要包括（）复杂度和（）复杂度。 教师批改：时间、空间 综合题 21、设给定3个整数a，b，c，试写出寻找这3个整数的中数的算法；并分析在平均情况与最坏情况下，该算法分别要做多少次比较？ 寻找这3个整数的中数的算法用C语言描述如下（中数m由函数值返回）： int mid ( int a, int b, int c) { int m 。m=a 。 if ( m>=b ) { if (m>=c) { if ( b>=c ) m=b 。else m=c 。} } else { if ( m<=c) { if (b>=c) m=c。else m=b 。} } return ( m ) 。 } 假设a，b，c中的每一个数为中数的概率相等（均为1/3）。由于当a为中数时需要比较2次，b或c为中数时均需要比较3次，因此，在平均情况下上述算法所需要的比较次数为 2*（1/3）+3*（1/3）+3*（1/3）= 8/3 即在平均情况下，上述算法需要比较8/3次。 在最坏情况下，上述算法需要比较3次（当b或c为中数时）。 第二章 选择题 1、下列排序方法中，哪一个是稳定的排序方法（）。归并排序稀尔排序 堆排序快速排序 [A] 教师批改：A 2、设输入序列为1，2，3，4，借助一个栈得到的输出序列可以是（）。3，4，1，2 4，2，1，3 4，1，2，3 1，3，4，2 [D] 教师批改：D 3、用数组A[m]存放循环队列的元素值，若其头尾指针分别为front和rear，则循环队列中当前元素的个数为（）。(rear+front)%m (rear-front+m)%m (rear-front)%m (rear-front+1)%m [D] 教师批改：B 4、对于下三角矩阵A，若采用一个一维数组B以行为主顺序存放压缩矩阵A，则A43存放在（）中. B7 B8 B9 B10 [C] 教师批改：C 5、深度为5的二叉树至多有（）个结点。16 32

实验报告03-两个有序链表的合并

实验目的及要求： 了解和掌握链表的特点； 掌握链表基本操作的实现； 掌握两个有序链表合并的算法 要求完成链表的初始化、插入、有序表合并、显示操作的实现。实验设备环境及要求： PC机一台，内存要求128M以上，VC++6.0集成开发环境。 实验内容与步骤： 1、在VC++6.0环境中新建一个工程和C++文件； 2、实现链表初始化、插入、有序合并算法，代码如下： #include #include typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; int InitList_L(LinkList &L){ L= (LinkList)malloc(sizeof(LNode)); L->next=NULL; return 1; } int ListInsert_L(LinkList &L,int i,ElemType e){ LinkList p; p=L; int j=0; while(p&&jnext; ++j; } if(!p||j>i-1) return 0; LinkList s=(LinkList)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; return 1; } void Disp_L(LinkList L){

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; };

《数据结构》实验指导书(修订版)

《数据结构》实验指导书 郑州轻工业学院

目录 前言 (3) 实验01 顺序表的基本操作 (7) 实验02 单链表的基本操作 (19) 实验03 栈的基本操作 (32) 实验04 队列的基本操作 (35) 实验05 二叉树的基本操作 (38) 实验06 哈夫曼编码 (40) 实验07 图的两种存储和遍历 (42) 实验08 最小生成树、拓扑排序和最短路径 (46) 实验09 二叉排序树的基本操作 (48) 实验10 哈希表的生成 (50) 实验11 常用的内部排序算法 (52) 附：实验报告模板 (54)

前言 《数据结构》是计算机相关专业的一门核心基础课程，是编译原理、操作系统、数据库系统及其它系统程序和大型应用程序开发的重要基础，也是很多高校考研专业课之一。它主要介绍线性结构、树型结构、图状结构三种逻辑结构的特点和在计算机内的存储方法，并在此基础上介绍一些典型算法及其时、空效率分析。这门课程的主要任务是研究数据的逻辑关系以及这种逻辑关系在计算机中的表示、存储和运算，培养学生能够设计有效表达和简化算法的数据结构，从而提高其程序设计能力。通过学习，要求学生能够掌握各种数据结构的特点、存储表示和典型算法的设计思想及程序实现，能够根据实际问题选取合适的数据表达和存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。另外本课程的学习过程也是进行复杂程序设计的训练过程，通过算法设计和上机实践的训练，能够培养学生的数据抽象能力和程序设计能力。学习这门课程，习题和实验是两个关键环节。学生理解算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否学好《数据结构》的关键。为了更好地配合学生实验，特编写实验指导书。 一、实验目的 本课程实验主要是为了原理和应用的结合，通过实验一方面使学生更好的理解数据结构的概念和常用的几种数据结构在计算机中的存储和实现的方法，加强学生动手能力；另一方面培养学生从实际问题中抽象出对应的抽象数据类型，进而找到合适的计算机存储方法和算法，为以后课程的学习、大型软件的开发、实际工程问题打下良好的软件开发基础。 二、实验要求 1、每次实验前学生必须根据实验内容认真准备实验程序及调试时所需的输入数据。 2、在指导教师的帮助下能够完成实验内容，得出正确的实验结果。 3、实验结束后总结实验内容、书写实验报告。 4、遵守实验室规章制度、不缺席、按时上、下机。 5、实验学时内必须做数据结构的有关内容，不允许上网聊天或玩游戏，如发现上述现象，取消本次上机资格，平时成绩扣10分。 6、实验报告有一次不合格，扣5分，两次以上不合格者，平时成绩以零分记。 三、实验环境 VC++或其他C++相关的编译环境。 四、说明 1、本实验的所有算法中元素类型应根据实际需要合理选择。 2、实验题目中带＊者为较高要求，学生可自选；其余部分为基本内容，应尽量完成（至少完成70%，否则实验不合格）。 3、数据结构是很多高校的硕士研究生入学考试的专业课之一，希望有志于考研的学生能够在

两个有序链表的合并

《数据结构》实验报告 班级：JS001001 姓名：周卫华学号：2010300028 E-mail:770234417@https://www.wendangku.net/doc/523376406.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); }

数据结构-实验指导书

《数据结构》实验指导书 计算机专业实验中心编 2020年5月25日

目录 《数据结构》上机实验内容和要求 ................................................................... 错误!未定义书签。实验一、顺序表的实现及应用 ........................................................................... 错误!未定义书签。实验二、链表的实现及应用 ............................................................................... 错误!未定义书签。实验三、栈的实现及应用 ................................................................................... 错误!未定义书签。实验四、队列的实现及应用 ............................................................................... 错误!未定义书签。实验五、二叉树操作及应用 ............................................................................... 错误!未定义书签。实验六、图的遍历操作及应用 ........................................................................... 错误!未定义书签。实验七、查找算法的实现 ................................................................................... 错误!未定义书签。实验八、排序算法的实现 ................................................................................... 错误!未定义书签。

数据结构模拟试题

模拟试题1 一、选择题（共10题，每题1分，共10分） 1．下面关于线性表的叙述中，错误的是哪一个？（） A．线性表采用顺序存储，必须占用一片连续的存储单元 B．线性表采用顺序存储，便于进行插入和删除操作 C．线性表采用链接存储，不必占用一片连续的存储单元 D．线性表采用链接存储，便于插入和删除操作 2．在一个单链表中，已知q所指结点是p所指结点的前驱，若在p和q之间插入s所指结点，则执行的操作是（）。 A. s->next=p->next;p->next=s; B. q->next=s;s->next=p; C. p->next=s->next;s->next=p; D. p->next=s;s->next=q; 3．设有三个元素X，Y，Z顺序进栈，下列得不到的出栈排列是( )。 A．XYZ B. YZX C. ZXY D. ZYX 4．若用一个长度为6的数组来实现循环队列，且当前rear和front的值分别为0和3，则从队列中删除一个元素，再增加两个元素后，rear和front的值分别是( )。 A．1和5 B．2和4 C．4和2 D. 5和1 5．下列说法中正确的是（）。 A．二叉树就是度为2的树 B．二叉树中不存在度大于2的结点 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 6．在具有n个结点的二叉链表中，共有（）个空指针。 A. n B. n-1 C. n+1 D. 不确定 7．根据二叉树与树的转换关系可知，深度为h的满二叉树对应的森林由（）棵树构成。 A．1 B．log2n C. h/2 D. h 8．在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A．1/2 B．1 C. 2 D. 4 9．对17个元素的查找表做折半查找，则查找长度为5的元素下标依次是（）。 A．8,17 Ｂ．5,10,12 C．9,16 D．9,17 10．关于排序，下列说法中正确的是（）。 A. 稳定的排序方法优于不稳定的排序方法，因为稳定的排序方法效率较高 B. 在顺序表上实现的排序方法在链表上也可以实现 C. 在链表上可以实现简单选择排序，但是难以实现堆排序 D. 就平均性能而言，堆排序最佳 二、填空题（共10空，每空2分，共20分） 1．计算机执行下面的语句时，语句s的执行次数为 _______ 。 for(i=l；i=i;j--) s; 2．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_______。3．数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是_______ 。