下载文档原格式
/*问题描述：实现两个链表的合并基本要求：1) 建立两个链表A和B，链表元素个数分别为m和n个；2) 假设元素分别为(x1,x2,…xm)，和(y1,y2, …yn)；3）把它们合并成一个顺序表C，使得：当m>=n时，C=x1,y1,x2,y2,...xn,yn, (x)当n>m时，C=y1,x1,y2,x2,…ym,xm,…,yn4）输出顺序表C5) 用直接插入排序法对顺序表C进行升序排序，生成链表D，并输出链表D。
6）能删除链表D中指定位置和指定值的元素。
提示：可考虑使用链表、顺序表等数据结构*/#include<stdio.h>#include<stdlib.h>#include<string.h>typedef struct linknode{ char data;struct linknode *next;}node;node *head=NULL,*head1=NULL,*head2=NULL;int n;void Merge(){int n1=0,n2=0;node *p,*q,*r;if(head!=NULL);else if(head1==NULL)head=head2;else if(head2==NULL)head=head1;else{p=head1->next;while(p!=NULL){n1++;p=p->next;}p=head2->next;while(p!=NULL){n2++;p=p->next;}if(n1>=n2){head=head1;p=head1->next;q=head2->next;while(q!=NULL){r=q->next;q->next=p->next;p->next=q;p=p->next->next;q=r;}}else{head=head2;p=head2->next;q=head1->next;while(q!=NULL){r=q->next;q->next=p->next;p->next=q;p=p->next->next;q=r;}}head1=NULL;head2=NULL;}printf("\t\t");p=head->next;while(p!=NULL){printf("%c ",p->data);p=p->next;}printf("\n");}void CreateList() /*尾插法建立单链表*/{node *p,*s;char x;n=0;head1=(node*)malloc(sizeof(node));p=head1;printf("\n\t\t建立单链表A:");printf("\n\t\t说明：请逐个输入字符，结束标记为#\n");printf("\t\t输入：");scanf("%c",&x);while(x!='#'){s=(node*)malloc(sizeof(node)); /*申请一个新结点*/n++;s->data=x; /*对新结点的data域赋值*/s->next=NULL; /*对新结点的next域赋空值*/p->next=s; /*将新结点连接到表的末尾*/p=s; /*P指向最后结点*/scanf("%c",&x);}head2=(node*)malloc(sizeof(node));p=head2;printf("\n\t\t建立单链表B:");printf("\n\t\t说明：请逐个输入字符，结束标记为#\n");printf("\t\t输入：");getchar();scanf("%c",&x);while(x!='#'){s=(node*)malloc(sizeof(node)); /*申请一个新结点*/n++;s->data=x; /*对新结点的data域赋值*/s->next=NULL; /*对新结点的next域赋空值*/p->next=s; /*将新结点连接到表的末尾*/p=s; /*P指向最后结点*/scanf("%c",&x);}}void frees(){node *p,*q;if(head!=NULL){p=head;head=NULL;while(p!=NULL){q=p->next;free(p);p=q;}}if(head1!=NULL){p=head1;head1=NULL;while(p!=NULL){q=p->next;free(p);p=q;}}if(head2!=NULL){p=head2;head2=NULL;while(p!=NULL){q=p->next;free(p);p=q;}}}void InsList(int i,char x) /*在单链表第i个位置插入元素*/ {node *s,*p;int j;if(i<1) /*若i<1, 则插入位置错误*/ {printf("\n\t\t\t插入位置不合法！\n");return;}else{p=head;j=0;while(p!=NULL&&j<i-1) /*寻找插入位置*/{j++;p=p->next;}if(p!=NULL) /*插入*/{s=(node*)malloc(sizeof(node));s->data=x;s->next=p->next;p->next=s;n++;}else{printf("\n\t\t\t未找到插入位置！\n");return;}}}void DelList(int i) /*删除单链表中第i个元素*/{node *p,*q;int j=0;if(head->next==NULL){printf("\n\t\t\t线性表已经为空！\n");return;}if(i<1){printf("\n\t\t\t位置不合法！\n");return;}p=head;while(p->next!=NULL && j<i-1) /*循环直到p指向第i-1个结点*/ {p=p->next;j++;}if(p->next==NULL || j>i-1){printf("\n\t\t\t没找到要删除的位置！\n");return;}else{q=p->next; p->next=q->next; /*删除第i个结点*/n--;free(q);}}void ShowList() /*显示单链表所有元素*/{node *p=head,*q,*r,*s;int i;q=p->next;r=q->next;q->next=NULL;while(r!=NULL){i=1;p=head;q=p->next;s=r->next;while(q!=NULL){if(q->data>r->data){r->next=q;p->next=r;i=0;break;}p=q;q=q->next;}if(i){p->next=r;r->next=NULL;}r=s;}p=head;printf("\n\t\t");while(p->next!=NULL){printf("%c ",p->next->data);p=p->next;}}void SearchList(char x){node *p;p=head->next;while(p!=NULL){if(p->data==x)printf("\t\t%c ",p->data);p=p->next;}}void main(){int choice,i,j=1;char x;head=NULL;while(j!=0){printf("\n\n\n\n");printf("\t\t\t 线性表子系统\n");printf("\n\t\t***************************************");printf("\n\t\t* 1-------建表*");printf("\n\t\t* 2-------合并*");printf("\n\t\t* 3-------插入*");printf("\n\t\t* 4-------删除*");printf("\n\t\t* 5-------排序*");printf("\n\t\t* 6-------显示*");printf("\n\t\t* 7-------查找*");printf("\n\t\t* 0-------返回*");printf("\n\t\t***************************************\n"); printf("\t\t请选择菜单号(0--6)：");scanf("%d",&choice);getchar();if(choice==1){if(head==NULL && head1==NULL && head2==NULL) CreateList();else{frees();CreateList();}}else if (choice==2){Merge();}else if (choice==3){ printf("\n\t\t请输入的位置i和数值x(输入格式：i，x):");scanf("%d,%c",&i,&x);InsList(i,x);}else if (choice==4){ printf("\n\t\t请输入要删除元素的位置：");scanf("%d",&i);DelList(i);}else if (choice==5){ if(head==NULL)printf("\n\t\t请先建立线性表！");elseShowList();}else if (choice==6){node *p;if(head==NULL){printf("\t\t请合并或建立线性表");}else{p=head->next;printf("\n\t\t表长为%d\n\t\t",n);printf("线性表数据为:\n\t\t\t");while(p!=NULL){printf("%c ",p->data);p=p->next;}printf("\n");}}else if (choice==7){if(head==NULL)printf("\t\t请合并或建立线性表");else{printf("\n\t\t请输入要查找的元素：");scanf("%c",&x);SearchList(x);}}else if (choice==0)j=0;elseprintf("\n\t\t输入错误！请重新输入！\n");}}。
算法设计题打印部分假设有两个按元素值递增次序排列的线性表均以单链表形式存储。
请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表并要求利用原来两个单链表的结点存放归并后的单链表。
【北京大学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同样以元素值的递增序的单链表形式存贮。
数据结构试卷（五）一、选择题(30分)1．数据的最小单位是（）。
(A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量2．设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（）。
(A) 40，50，20，95 (B) 15，40，60，20(C) 15，20，40，45 (D) 45，40，15，203．设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（）。
(A) 15，25，35，50，20，40，80，85，36，70(B) 15，25，35，50，80，20，85，40，70，36(C) 15，25，35，50，80，85，20，36，40，70(D) 15，25，35，50，80，20，36，40，70，854．函数substr(“DATASTRUCTURE”，5，9)的返回值为（）。
(A) “STRUCTURE”(B) “DATA”(C) “ASTRUCTUR”(D) “DATASTRUCTURE”5．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（）。
(A) O(log2n) (B) O(1) (C) O(n2) (D) O(n)6．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为N l，……，度数为m的结点数为Nm，则N0=（）。
(A) N l+N2+……+Nm (B) l+N2+2N3+3N4+……+(m-1)Nm(C) N2+2N3+3N4+……+(m-1)Nm (D) 2N l+3N2+……+(m+1)Nm7．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。
(A) 25 (B) 10 (C) 7 (D) 18．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（）。
数据结构试卷（一）一、选择题(30分)1．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。
(A) O(n)(B) O(nlog2n)(C) O(1)(D) O(n2)2．设一棵二叉树的深度为k，则该二叉树中最多有（）个结点。
(A) 2k-1(B) 2k(C) 2k-1(D) 2k-13．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。
(A) n(B) e(C) 2n(D) 2e4．在二叉排序树中插入一个结点的时间复杂度为（）。
(A) O(1)(B) O(n)(C) O(log2n)(D) O(n2)5．设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。
(A) n(B) n-1(C) m(D) m-16．设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序序列。
(A) 3(B) 4(C) 5(D) 87．设用链表作为栈的存储结构则退栈操作（）。
(A) 必须判别栈是否为满(B) 必须判别栈是否为空(C) 判别栈元素的类型(D) 对栈不作任何判别8．下列四种排序中（）的空间复杂度最大。
(A) 快速排序(B) 冒泡排序(C) 希尔排序(D) 堆9．设某二叉树中度数为0的结点数为N0，度数为1的结点数为N l，度数为2的结点数为N2，则下列等式成立的是（）。
(A) N0=N1+1(B) N0=N l+N2(C) N0=N2+1(D) N0=2N1+l10.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（）。
(A) log2n+1(B) log2n-1(C) log2n(D) log2(n+1)二、填空题(42分)1．1．设有n个无序的记录关键字，则直接插入排序的时间复杂度为________，快速排序的平均时间复杂度为_________。
《数据结构》题库及答案一、选择题1．线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。
a. 随机存储；b.顺序存储；c. 索引存取；d. HASH 存取2．一个栈的入栈序列是a,b,c,d,e ，则栈的不可能的输出序列是 。
a. edcba;b. decba;c. dceab;d.abcde3．一个队列的入队序列是1，2，3，4，则队列的输出序列是 。
a. 4,3,2,1;b. 1,2,3,4;c. 1,4,3,2;d.3,2,4,14．在一个单链表中，已知p 结点是q 结点的直接前驱结点，若在p 和q 之间插入结点s ，则执行的操作是 。
a. s->nxet=p->next; p->next=s;b. p->next=s->next; s->next=p;c. q->next=s; s->next=p;d. p->next=s; s->next=q;5．设有两个串p,q ，求q 在p 中首次出现的位置的运算称作 。
a.联接b.模式匹配c.求子串d.求串长6．二维数组M 的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i 的范围从0到8，列下标j 的范围从1到10，则存放M 至少需要 个字节。
a. 90b.180c.240d.540 7．在线索二叉树中，结点p 没有左子树的充要条件是 。
a. p->lch==NULLb. p->ltag==1c. p->ltag==1且p->lch=NULLd. 以上都不对8．在栈操作中，输入序列为（A ，B ，C ，D ），不可能得到的输出序列为：______A 、（A ，B ，C ，D ） B 、（D ，C ，B ，A ） C 、（A ，C ，D ，B ） D 、（C ，A ，B ，D ）9．已知某二叉树的后序序列是dabec ，中序序列是debac ，则它的先序序列是 。
头歌桂林电子科技大学数据结构答案1、线性结构中数据元素之间是（）关系。
[单选题] *A、一对多B、多对多C、多对一D、一对一(正确答案)2、在计算机中存储数据时，通常不仅要存储各数据元素的值，而且要存储（）。
[单选题] *A、数据的处理方法B、数据元素的类型C、数据元素之间的关系(正确答案)D、数据的存储方法3、计算机算法指的是（）。
[单选题] *A、计算方法B、排序方法C、求解问题的有限运算序列(正确答案)D、调度方法4、算法分析的目的是（）。
[单选题] *A、找出数据结构的合理性B、研究算法中的输入和输出的关系C、分析算法的效率以求改进(正确答案)D、分析算法的易懂性和文档性5、某算法的时间复杂度为O（n²），表明该算法的（）。
[单选题] *A、问题规模是n²B、执行时间等于n²C、执行时间与n²成正比(正确答案)D、问题规模与n²成正比6、线性表是（）。
[单选题] *A、一个有限序列，可以为空(正确答案)B、一个有限序列，不可以为空C、一个无限序列，可以为空D、一个无限序列，不可以为空7、在n个元素的顺序表中，算法的时间复杂度是O(1)的操作是（）。
[单选题] *A、访问第i个元素(2≤i≤n)及其前驱元素(正确答案)B、在第i(1≤i≤n)个元素后插入一个新元素C、删除第i个元素(1≤i≤n)D、将n个元素从小到大排序8、将两个分别含有m、n个元素的有序顺序表归并成一个有序顺序表，对应算法的时间复杂度是（）。
这里MIN表示取最小值。
[单选题] *A、O(n)C、O(m+n)(正确答案)D、O(MIN(m , n))9、线性表的链式存储结构和顺序存储结构相比，其优点是（）。
[单选题] *A、所有的操作算法实现简单B、便于随机存取C、便于插入和删除元素(正确答案)D、节省存储空间10、设线性表中有n个元素，以下运算中，（）在单链表上实现要比在顺序表上实现效率更高。
2022年复旦大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为（）。
A.5B.6C.8D.92、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。
A.NB.2N-1C.2ND.N-13、线性表的顺序存储结构是一种（）。
A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构4、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。
A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改5、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l6、下列关于无向连通图特性的叙述中，正确的是（）。
Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1 A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ7、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。
A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，198、在下述结论中，正确的有（）。
①只有一个结点的二叉树的度为0。
②二叉树的度为2。
③二叉树的左右子树可任意交换。
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A.①②③B.⑦③④C.②④D.①④9、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）。
链表的合并实验报告文稿归稿存档编号：[KKUY-KKIO69-OTM243-OLUI129-G00I-FDQS58-课程设计报告课程设计题目：两个链表的合并专业：软件工程班级：姓名：学号:指导教师:年月日目录1.课程设计的目的及要求2.课程设计的内容（分析和设计）3.算法流程图4.详细步骤5.代码6.显示结果7.课程设计的总结一．课程设计的目的及要求1.目的：实现两个链表的合并2.要求：（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（3）用直接插入排序法对C进行升序排序，生成链表D，并输出链表D。
（4）能删除指定单链表中指定位子和指定值的元素。
二．课程设计的内容（分析和设计）1..分析由题目的相关信息可以分析得：首先我们需要建立两个链表AB，A链表的元素个数为m，B链表的元素个数为n；在将A、B链表进行合并，根据m和n的大小关系决定链表C的元素顺序；再将C进行直接插入排序得到一个新的链表D；没次输入完一次链表信息，程序都会对相应的链表进行输入操作以此确保程序输入的数据是你想要输入的数据。
同时当你合并好和排序好后都会进行输出操作。
最后当排序好后你可以指定你所要删除数据的位置来删除你所要删除的数据。
2.设计本次课程设计所需要用到的是关于链表的建立、合并以及直接插入排序的排序算法。
需要先建立两个链表，再将其合并为一个无序链表，最后对这个无序链表进行直接插入排序并将其输出。
难点在于将AB合并为链表C的操作以及对链表C进行直接插入排序的操作和根据用户的意愿可以对链表进行删除的操作。
三．算法流程图四．详细步骤(1)结构体的创建：struct Node(2)链表的创建：struct Node *create（）链表的创建。
将两个升序链表合并为⼀个新的升序链表并返回。
新链表是通过拼接给定的两个链表的所有节点组成的。
我们可以⽤迭代的⽅法来实现上述算法。
当 l1 和 l2 都不是空链表时，判断 l1 和 l2 哪⼀个链表的头节点的值更⼩，将较⼩值的节点添加到结果⾥，当⼀个节点被添加到结果⾥之后，将对应链表中的节点向后移⼀位。
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode prehead = new ListNode(-1); //哨兵，⽤于最后返回合并后的结果
ListNode minValNode = prehead;
while(l1 != null && l2 != null){
if(l1.val <= l2.val){
minValNode.next = l1;
l1 = l1.next;
}else{
minValNode.next = l2;
l2 = l2.next;
}
minValNode = minValNode.next;
}
minValNode.next = l1 == null?l2 : l1; //两链表长度不⼀，短链表的next先为空，则minValNode的next就是长链表剩下的
return prehead.next; //返回结果链表
}
}
当然还有更好的⽅法，请在评论区留⾔，如果有不懂或者错误的地⽅，也请指出，加以改正。
两个单链表的合并算法
单链表是一种常见的链式数据结构，其中每个节点包含一个数据元素和一个指向下一个节点的指针。
在实际应用中，我们经常需要将多个单链表合并成一个单链表，以方便处理和操作。
本文介绍了两种不同的单链表合并算法。
第一种算法是顺序合并法。
顺序合并法的基本思路是依次扫描两个单链表，并将其中的元素逐个比较，将较小的元素插入到新链表中。
具体实现可以采用递归或循环的方式，时间复杂度为O(m+n)，其中m 和n分别表示两个单链表的长度。
第二种算法是归并排序法。
归并排序法的基本思路是将两个单链表分别进行归并排序，然后再将两个有序单链表合并成一个有序单链表。
具体实现可以采用递归的方式，时间复杂度为O(nlogn)，其中n 表示单链表的长度。
无论采用哪种算法，单链表合并都需要注意指针的处理和边界情况的处理，以确保程序的正确性和有效性。
- 1 -。
