下载文档原格式
算法设计题打印部分假设有两个按元素值递增次序排列的线性表均以单链表形式存储。
请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表并要求利用原来两个单链表的结点存放归并后的单链表。
【北京大学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同样以元素值的递增序的单链表形式存贮。
链表的反转与合并掌握链表反转和合并操作的实现链表是一种常见的数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。
链表的反转和合并是链表操作中常见且重要的操作，在很多编程问题中都有应用。
本文将介绍链表的反转和合并操作的实现方法。
一、链表的反转链表的反转是指将链表中节点的顺序反向排列。
例如，对于链表1→2→3→4→5，反转后的链表为5→4→3→2→1。
实现链表的反转有两种常见的方法：迭代法和递归法。
1. 迭代法迭代法的实现思路是，从链表头节点开始，依次遍历每个节点，将该节点的指针指向前一个节点。
具体步骤如下：1）定义三个指针：当前节点指针cur、前一个节点指针prev、下一个节点指针next。
2）遍历链表，将当前节点的指针指向前一个节点，然后更新prev、cur和next指针的位置。
3）重复上述步骤，直到遍历到链表末尾。
以下是迭代法的实现代码示例（使用Python语言）：```pythondef reverse_list(head):prev = Nonecur = headwhile cur:next = cur.nextcur.next = prevprev = curcur = nextreturn prev```2. 递归法递归法的实现思路是，从链表的尾节点开始，依次反转每个节点。
具体步骤如下：1）递归地反转除最后一个节点外的链表。
2）将当前节点的指针指向前一个节点。
3）返回反转后的链表的头节点。
以下是递归法的实现代码示例（使用Python语言）：```pythondef reverse_list(head):if not head or not head.next:return headnew_head = reverse_list(head.next)head.next.next = headhead.next = Nonereturn new_head```二、链表的合并链表的合并是指将两个有序链表按照一定的规则合并成一个有序链表。
第2章线性表1．选择题（1）顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。
A．110 B．108 C．100 D．120答案：B解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。
（2）在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。
A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B．在第i个结点后插入一个新结点（1≤i≤n）C．删除第i个结点（1≤i≤n）D．将n个结点从小到大排序答案：A解释：在顺序表中插入一个结点的时间复杂度都是O(n2)，排序的时间复杂度为O(n2)或O(nlog2n)。
顺序表是一种随机存取结构，访问第i个结点和求第i个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是O(1)。
（3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。
A．8 B．63.5 C．63 D．7答案：B解释：平均要移动的元素个数为：n/2。
（4）链接存储的存储结构所占存储空间（）。
A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点值C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点值，另一部分存放结点所占单元数答案：A（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。
A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续或不连续都可以答案：D（6）线性表Ｌ在（）情况下适用于使用链式结构实现。
A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂答案：B解释：链表最大的优点在于插入和删除时不需要移动数据，直接修改指针即可。
（7）单链表的存储密度（）。
A．大于1 B．等于1 C．小于1 D．不能确定答案：C解释：存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空间之比，假设单链表一个结点本身所占的空间为D，指针域所占的空间为N，则存储密度为：D/(D+N)，一定小于1。
数据结构课程设计实现两个链表的合并一、需求分析：题目：实现两个链表的合并问题描述：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。
由题目的相关信息可以分析得到：首先我们需要建立两个链表AB，A链表的元素个数为m；B链表的元素个数为n；在将A\B链表进行合并，更具m和n的大小关系决定链表C的元素顺序；再将C经行直接插入排序得到一个新的链表D；最后输出ABCD的相关信息。
二、算法的流程图三、算法设计分析这个两个链表的交叉合并算法主要运用到的是链表的基本操作，定义节点，将链表的创建、计算链表的长度、链表A,B的交叉组合、链表内容升序排列、删除链表指定位置元素、删除指定的元素等算法写成了独立函数，通过主函数调用。
这样就大大精简了主函数的操作。
但主函数中很大篇幅用到了if、else语句，用以指定链表指定结点和指定元素的删除操作，这样就使得本来很精简变得繁琐，降低了程序的质量。
所以其有优点和缺点，但需要不断的改进，不断优化该程序。
四、源代码程序源代码:#include<stdio.h>#include<stdlib.h>typedef struct node //节点定义{int data;struct node *next;} node,*linklist;linklist creat(linklist head) //该函数用来创建链表{node *r,*s;int a;r = (linklist)malloc(sizeof(node));head = r;scanf("%d",&a);while(a != 0){s =(node*)malloc(sizeof(node));s->data=a;r->next=s;r=s;printf("please input a data:");scanf("%d",&a);}r->next=NULL;return head;}linklist length(linklist l) // 返回L中数据元素个数{int i=0;linklist p=l->next; // p指向第一个结点while(p){i++;p=p->next;}return i;}linklist mergel(linklist A,linklist B) //用于实现链表A,B的交叉组合 {int m,n;node *p,*q,*s,*t;linklist C;p=A->next;q=B->next;m=length(A);n=length(B);C=A;if(m<n){p=B->next;q=A->next;C=B;}while(p&&q){s=p->next;p->next=q;if(s){t=q->next;q->next=s;}p=s;q=t;}return C;}linklist sort(linklist L) //链表内容升序排列{linklist p,q,min;int temp;p=L;while( p=p->next ){q=min=p;while(q=q->next){if( q->data<min->data )min = q;}if( min!=p ){temp = p->data;p->data = min->data;min->data=temp;}}return L;}linklist Delete(linklist l,int index) //删除链表指定位置元素{ linklist p,t;int cx=1; //用于计数p=l;if(index<length(l)){while(p&&(cx<index)){t=p;p=p->next;cx++;}t->next=p->next;}elseprintf("input indext error");return l;}linklist Delete_element(linklist l,int data) //删除指定的元素{ linklist p;p=l;if(p->next){while(p->next->data!=data){p=p->next;}p->next=p->next->next;}elseprintf("don't faind the element");return l;}linklist display(linklist l) //打印{ linklist p;printf("new linklist :\n");p = l->next;while(p){printf("%d\n",p->data);p= p->next;}return l;}main(){linklist p,q,A,B,C,D;int indexs;int datas;char name;int cmd;printf("Creat linklist A:\n"); //创建A链表,并打印printf("please input a data:");A = creat(A);printf("Creat linklist B:\n"); //创建B链表,并打印printf("please input a data:");B = creat(B);C = mergel(A,B); //生成C链表，并打印 printf("linklist C\n");p = C->next;while(p){printf("%d\n",p->data);p=p->next;}D=C; //对C进行排序生成D sort(D);printf("linklist D:\n");q = D->next;while(q){printf("%d\n",q->data);q = q->next;}printf("\nplease input 0 or 1 \n");//用1和0判断是按位置删除还是直接删除元素scanf("%d",&cmd);if(cmd==0) //位置删除{printf("please input linklist name\n ");fflush(stdin);scanf("%c",&name);printf("\nplease input index \n");scanf("%d",&indexs);fflush(stdin);if(name=='A'){Delete(A,indexs);display(A);}else if(name=='B'){Delete(B,indexs);display(B);}else if(name=='C'){Delete(C,indexs);display(C);}else if(name=='D'){Delete(D,indexs);display(D);}elseprintf("nameError");}else if(cmd==1) //元素删除{fflush(stdin); //清除缓冲printf("please input linklist name\n ");//fflush(stdin);scanf("%c",&name);printf("\nplease input datas \n");scanf("%d",&datas);if(name=='A'){Delete_element(A,datas);display(A);}else if(name=='B'){Delete_element(B,datas);display(B);}else if(name=='C'){Delete_element(C,datas);display(C);}else if(name=='D'){Delete_element(D,datas);display(D);}elseprintf("name2error");}elseprintf("cmdError");printf("\nOver\n");getchar();return 0;}六、实验运行结果显示：设计体会及今后改进的意见;短短一周的数据结构课程设计结束了，回想着这一周自己的表现，感觉不是很满意，感到自己许多不足之处。
《数据结构（C语言版第2版）》（严蔚敏著）第二章练习题答案第2章线性表1．选择题（1）顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。
A．110 B．108 C．100 D．120答案：B解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。
（2）在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。
A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B．在第i个结点后插入一个新结点（1≤i≤n）C．删除第i个结点（1≤i≤n）D．将n个结点从小到大排序答案：A解释：在顺序表中插入一个结点的时间复杂度都是O(n2)，排序的时间复杂度为O(n2)或O(nlog2n)。
顺序表是一种随机存取结构，访问第i个结点和求第i个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是O(1)。
（3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。
A．8 B．63.5 C．63 D．7答案：B解释：平均要移动的元素个数为：n/2。
（4）链接存储的存储结构所占存储空间（）。
A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点值C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点值，另一部分存放结点所占单元数答案：A（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。
A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续或不连续都可以答案：D（6）线性表Ｌ在（）情况下适用于使用链式结构实现。
A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂答案：B解释：链表最大的优点在于插入和删除时不需要移动数据，直接修改指针即可。
（7）单链表的存储密度（）。
A．大于1 B．等于1 C．小于1 D．不能确定答案：C解释：存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空间之比，假设单链表一个结点本身所占的空间为D，指针域所占的空间为N，则存储密度为：D/(D+N)，一定小于1。
要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。
每张答题纸都要写上姓名和学号。
一、单项选择题（每小题2分，共20小题，共计40分）1、设n是描述问题规模的非负整数，下面程序片段的时间复杂度为（）。
x=1;while (x<=n)x=5*x;A. O(log5n)B.O(n)C.O(n log5n)D.O(n5)2、顺序表和链表相比存储密度较大，这是因为（）。
A.顺序表的存储空间是预先分配的B.顺序表不需要增加指针来表示元素之间的逻辑关系C.链表中所有节点的地址是连续的D.顺序表中所有元素的存储地址是不连续的3、在长度为n（n≥1）的循环双链表L中，在尾节点之后插入一个新节点的时间复杂度为（）。
A. O(n2)B.O(n)C. O(1)D.O(n log2n)4、设栈的输入序列是1、2、3、4，则（）不可能是其出栈序列。
A.1，2，4，3B.2，1，3，4C.1，4，3，2D.4，3，1，25、当用一个数组data[0..n-1]存放栈中元素时，栈底最好（）。
A. 设置在data[0]或data[n-1]处B.设置在data[n-1]处C. 设置在data[0]处D.设置在data数组的任何位置6、在数据处理过程中常需要保存一些中间数据，如果先保存的数据先处理，则使用（）来保存这些数据。
A.线性表B. 队列C. 栈D.单链表7、在环形队列中，元素的排列顺序（）。
A.与队头和队尾指针的取值有关B.与元素值的大小有关C.由元素进队的先后顺序确定D.与存放队中元素的数组大小有关8、将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（）。
A.100B.40C.80D.559、设目标串为s，模式串为是t，在KMP模式匹配中，next[4]=2的含义是（）。
A.表示t4字符前面最多有2个字符和开头的2个字符相同B.表示s4字符前面最多有2个字符和开头的2个字符相同C.表示目标串匹配失败的位置是i=4D.表示模式串匹配失败的位置是j=210、由权值分别为9、2、7、5的四个叶子节点构造一棵哈夫曼树，该树的带权路径长度为（）。
/* 链表的操作1) 定义链表的结构；2) 写函数创建链表；3) 输入两个正数链表，连接成一个非递减链表（用借助辅助链表的方法）。
*/#include<stdio.h># include <stdio.h># include <malloc.h># define null 0typedef struct LNode{int data;struct LNode *next;} LNode,*linklist;linklist creatlist (){LNode *p,*L;L=(LNode *)malloc(sizeof(LNode));L->next=null; L->data=0;while(1){p=(LNode *)malloc(sizeof(LNode));scanf("%d",&p->data);if(p->data==-1) break;++L->data;p->next=L->next;L->next=p;}return L;}void output(linklist L){LNode *p;printf("the follow is the Linklist data:\n");for(p=L->next;p!=null;p=p->next)printf("%3d",p->data);printf("\n the data is over.\n") ;}linklist sort(linklist L){int i;linklist p,q,r,s;r=(linklist)malloc(sizeof(LNode));r->next=null;for(i=0;i<L->data;i++){p=L->next;q=L->next->next;do{if((p->data)>(q->data))q=q->next;else{p=q;q=q->next;}} while(q) ;s=(linklist)malloc(sizeof(LNode));s->data=p->data;p->data=0;s->next=r->next;r->next=s;}return r;}linklist Merglist(linklist L1,linklist L2,linklist L3) {linklist p1,p2,p3;p1=L1->next;p2=L2->next;L3=p3=L1;while(p1&&p2){if(p1->data<=p2->data){p3->next=p1;p3=p1;p1=p1->next;}else {p3->next=p2;p3=p2;p2=p2->next;}}p3->next=p1?p1:p2;free(L2);return L3;}main(){linklist Lb;linklist La,Lc;La=creatlist();Lb=creatlist();La=sort(La);Lb=sort(Lb);output(La);output(Lb);Lc=Merglist(La,Lb,Lc);output(Lc);getch();}。
1、假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。
请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
输入: 1 2 5 6 83 4 7 9 10输出: 10 9 8 7 6 5 4 3 2 1测试数据输入：7 9 10 118 12 13 14输出：14 13 12 11 10 9 8 7链表翻转2.带头结点且头指针为ha和hb的两线性表A和B 分别表示两个集合。
两表中的元素皆为递增有序。
请写一算法求A和B的并集AUB。
要求该并集中的元素仍保持递增有序。
且要利用A和B的原有结点空间。
输入: 1 2 5 6 82 5 7 9输出: 1 2 5 6 7 8 9测试数据输入：7 9 10 118 9 10 11输出：7 8 9 10 113. 知L1、L2分别为两循环单链表的头结点指针，m,n分别为L1、L2表中数据结点个数。
要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。
4. 顺序结构线性表LA与LB的结点关键字为整数。
LA与LB的元素按非递减有序，线性表空间足够大。
试用类PASCAL语言给出一种高效算法，将LB中元素合到LA中，使新的LA的元素仍保持非递减有序。
高效指最大限度的避免移动元素。
5. 已知不带头结点的线性链表list，链表中结点构造为（data、link），其中data为数据域，link为指针域。
请写一算法，将该链表按结点数据域的值的大小从小到大重新链接。
要求链接过程中不得使用除该链表以外的任何链结点空间。
6. 设L为单链表的头结点地址，其数据结点的数据都是正整数且无相同的，试设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。
7. 设 Listhead为一单链表的头指针，单链表的每个结点由一个整数域DATA和指针域NEXT组成，整数在单链表中是无序的。
编一PASCAL 过程，将 Listhead链中结点分成一个奇数链和一个偶数链，分别由P,Q指向，每个链中的数据按由小到大排列。
精品文档考试教学资料施工组织设计方案数据结构（C语言版）（第2版）课后习题答案李冬梅2015.3目录第1章绪论 (1)第2章线性表 (5)第3章栈和队列 (13)第4章串、数组和广义表 (26)第5章树和二叉树 (33)第6章图 (42)第7章查找 (54)第8章排序 (65)第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。
如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。
数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。
在有些情况下，数据元素也称为元素、结点、记录等。
数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。
数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。
例如，学生基本信息表中的学号、姓名、性别等都是数据项。
数据对象：是性质相同的数据元素的集合，是数据的一个子集。
例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。
逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。
因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
存储结构：数据对象在计算机中的存储表示，也称为物理结构。
抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。
具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。
第1章4．答案：（1）顺序存储结构顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述。
（2）链式存储结构顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无需占用一整块存储空间。
但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。
所以链式存储结构通常借助于程序设计语言的指针类型来描述。
5. 选择题(1)~(6)：CCBDDA\6．（1）O(1) （2）O(m*n) （3）O(n2)（4）O(log3n) （5）O(n2) （6）O(n)（第2章1．选择题（1）~（5）：BABAD （6）~（10）： BCABD （11）~（15）：CDDAC\2．算法设计题（1）将两个递增的有序链表合并为一个递增的有序链表。
要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。
表中不允许有重复的数据。
[题目分析]合并后的新表使用头指针Lc指向，pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表La和Lb均为到达表尾结点时，依次摘取其中较小者重新链接在Lc表的最后。
如果两个表中的元素相等，只摘取La表中的元素，删除Lb表中的元素，这样确保合并后表中无重复的元素。
当一个表到达表尾结点，为空时，将非空表的剩余元素直接链接在Lc表的最后。
void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc){法设计题（1）将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。
当第0号栈的栈顶指针top[0]等于-1时该栈为空，当第1号栈的栈顶指针top[1]等于m时该栈为空。
两个栈均从两端向中间增长。
试编写双栈初始化，判断栈空、栈满、进栈和出栈等算法的函数。
第2章线性表一、选择题1.表长为N 的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（E ），删除一个元素需要移动的元素个数为（A ）。
A. (N-1)/2B. NC. N+1D. N-1E. N/2F. (N+1)/2G. (N-2)/22.线性表是具有N 个（C ）的有限序列。
A、表元素B、字符C、数据元素D、数据项E、信息3.“线性表的逻辑顺序和物理顺序总是一致的。
”这个结论是（B ）。
A、正确的B、错误的C、不一定，与具体结构有关。
4.线性表采用链式存储结构时，要求内存中可用存储单元的地址（D ）。
A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续或不连续都可以。
5.带头结点的单链表为空的判定条件是（B ）。
A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL6.不带头结点的单链表head 为空的判定条件是（A ）。
A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL7.非空的循环单链表head 的尾结点P 满足（ C ）。
A、P->NEXT=NULLB、p=NULLC、p->next==headD、p==head8.在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（B ）。
A、O(1)B、O(n)C、O(n2)D、O(nlog2n)9.在一个单链表中，若删除P 所指结点的后继结点，则执行（ A ）。
A、p->next=p->next->nextB、p=p->next;p->next=p->next->nextC、p->next=p->next;D、p=p->next->next;10.在一个单链表中，若在Ｐ所指结点之后插入Ｓ所指结点，则执行（B ）。
Java编程实现递增排序链表的合并题⽬描述输⼊两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满⾜单调不减规则。
解答：/*public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}}*/public class Solution {public ListNode Merge(ListNode list1,ListNode list2) {if(list1==null)return list2; //判断到某个链表为空就返回另⼀个链表。
如果两个链表都为空呢？没关系，这时候随便返回哪个链表，不也是空的吗?if(list2==null)return list1;ListNode list0=null;//定义⼀个链表作为返回值if(list1.val<list2.val){//判断此时的值，如果list1⽐较⼩，就先把list1赋值给list0，反之亦然list0=list1;list0.next=Merge(list1.next, list2);//做递归，求链表的下⼀跳的值}else{list0=list2;list0.next=Merge(list1, list2.next);}return list0;}}简化⼀下，⽤那个三⽬运算符：public class Solution {public ListNode Merge(ListNode list1,ListNode list2) {if(list1==null)return list2;if(list2==null)return list1;ListNode head;list0= list1.val>list2.val?list2:list1;list0.next = list1.val>list2.val?Merge(list1,list2.next):Merge(list1.next,list2);return list0;}}据说这道题⾯试的时候经常考，因为它跟斐波那契数列问题⼀样有递归和⾮递归两种解法，上⾯说了递归的解法，下⾯再来讲下⾮递归的解法：/*public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}}*/public class Solution {public ListNode Merge(ListNode list1,ListNode list2) {if(list1 == null)return list2;if(list2 == null )return list1;ListNode tmp1 = list1;ListNode tmp2 = list2;ListNode head = new ListNode(0);//这⾥不能把返回链表赋值为null，因为下⼀⾏马上就要把它赋值给另⼀链表，得让它在内存⾥有位置才⾏ListNode headptr = head;while(tmp1 != null && tmp2!=null){if(tmp1.val <= tmp2.val){head.next=tmp1;head = head.next;tmp1 = tmp1.next;} else{head.next=tmp2;head = head.next;tmp2=tmp2.next;}}//其中⼀个链表已经跑到头之后，继续单链表的合并while(tmp1 != null){head.next = tmp1;head = head.next;tmp1= tmp1.next;}while(tmp2 != null){head.next = tmp2;head = head.next;tmp2= tmp2.next;}head = headptr.next;return head;}}总结以上就是本⽂关于Java编程实现递增排序链表的合并的全部内容，感兴趣的朋友可以参阅：、、以及本站其他相关专题，如有不⾜之处，欢迎留⾔指出，希望对⼤家有所帮助。
/*问题描述：实现两个链表的合并基本要求：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");}}。
链表求并集算法链表是一种常见的数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。
链表可以用来解决许多实际问题，其中之一就是求两个链表的并集。
求两个链表的并集，意味着要将两个链表中的所有元素合并到一个新的链表中，而且新链表中的元素不能重复。
具体的算法步骤如下：1. 创建一个新链表，用于存放两个链表的并集。
2. 遍历第一个链表，将链表中的元素逐个添加到新链表中。
在添加之前，需要判断新链表中是否已经存在相同的元素，如果存在则不添加。
3. 遍历第二个链表，将链表中的元素逐个添加到新链表中。
同样，在添加之前需要判断新链表中是否已经存在相同的元素。
4. 完成遍历后，新链表中的元素就是两个链表的并集。
下面通过一个具体的例子来说明链表求并集的算法。
假设有两个链表，链表A的元素为1、2、3，链表B的元素为3、4、5。
我们要求两个链表的并集。
首先创建一个新链表，用于存放并集，记为链表C。
遍历链表A，将链表A中的元素逐个添加到链表C中。
此时链表C 的元素为1、2、3。
然后遍历链表B，将链表B中的元素逐个添加到链表C中。
在添加之前，需要判断链表C中是否已经存在相同的元素。
对于元素3，链表C中已经存在，因此不添加。
最终链表C的元素为1、2、3、4、5。
通过以上步骤，我们就得到了链表A和链表B的并集。
需要注意的是，链表求并集的时间复杂度为O(n)，其中n为两个链表中元素的总个数。
除了求两个链表的并集，链表还可以进行其他的操作，如求交集、差集等。
这些操作的实现方法类似，只需根据具体的需求进行相应的判断和操作即可。
总结起来，链表求并集算法的步骤简单明了，只需遍历两个链表，判断并添加元素即可。
通过合理运用链表的特点，我们可以解决许多实际问题，提高编程效率。
