‘壹’ 将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来的两个链表的存储空间，不另外占
!有个前提，两个链表的数据类型都是一样的哦
第一种:先新建一个链表，然后遍历第一链表，同时把它的值都赋给新建的链表，然后，开始第二个链表，也是同样的办法。加上第二个的时候，先找到新建链表的表尾，再表尾处开始添加第二个
第二种:首先遍历第一个链表，找到表尾，然后去掉第二个链表的表头，把第二个链表的头部赋给第一个链表的尾部 //当然，如果没有表头什么的就直接把第一个节点赋给第一个就行了。
第二种方法之后，两个链表就合成一个了。
‘贰’ 怎么将两个顺序存储的有序表合并成一个有序表
具体代码如下：
#include<stdio.h>
#include<stdlib.h>
#define MAX 40
typedef struct
{
int data[MAX];
int length;
}LinkList;
void Initial_List(LinkList * &l,int n)//初始化顺序表
{
int i=0;
l=(LinkList *)malloc(sizeof(LinkList));
l->length = 0;
for(;i<n;i++)
scanf("%d",l->data+i);
l->length = n;
}
void Link(LinkList *l1,LinkList *l2,LinkList * &l3)//连接顺序表
{
int i,j;
l3=(LinkList *)malloc(sizeof(LinkList));
l3->length = l1->length + l2->length;
for(i=0;i<l3->length;i++)
{
if(i<l1->length)
{
l3->data[i] = l1->data[i];
}
else
{
l3->data[i] = l2->data[i%(l1->length)];
}
}
for(i=0;i<l3->length;i++)
{
for(j=i+1;j<l3->length;j++)
{
if(l3->data[i]>l3->data[j])
{
int temp=l3->data[i];
l3->data[i]=l3->data[j];
l3->data[j]=temp;
}
}
}
}
void Disp_List(LinkList *l)
{
int i=0;
printf("output: ");
for(;i<l->length;i++)
printf("%d ",l->data[i]);
printf(" ");
}
int main()
{
LinkList *l1,*l2,*l3;
int n;
printf("请输入第一个序列的元素个数: ");
scanf("%d",&n);
printf("请输入第一个序列的所有元素: ");
Initial_List(l1,n);
printf("请输入第二个序列的元素个数: ");
scanf("%d",&n);
printf("请输入第二个序列的所有元素: ");
Initial_List(l2,n);
Link(l1,l2,l3);
Disp_List(l3);
return 0;
}
‘叁’ 链式有序表的合并
#include"stdio.h"
#include"stdlib.h"
#defineStuNum14//宏定义学生数量1
#defineStuNum24//宏定义学生数量2
typedefstructstudent
{
intxuehao;
intscore;
structstudent*next;
}Student,*Pstudent;
voidCreatLink(Pstudenthead,intsize)
{
Pstudentphead=head,pstu;
for(inti=0;i<size;i++)
{
pstu=(Pstudent)malloc(sizeof(student));
pstu->score=head[i].score;
pstu->xuehao=head[i].xuehao;
pstu->next=NULL;
phead->next=pstu;
phead=pstu;
}
}
//按成绩大小排序，只是将原始输入的那两个表排序。
voidSort(Pstudentpstu,intsize)
{
for(inti=0;i<size-1;i++)
{
for(intj=0;j<size-1-i;j++)
{
if(pstu[j].score<pstu[j+1].score)
{
intscore=pstu[j].score;
intxh=pstu[j].xuehao;
pstu[j].score=pstu[j+1].score;
pstu[j].xuehao=pstu[j+1].xuehao;
pstu[j+1].score=score;
pstu[j+1].xuehao=xh;
}
}
}
}
voidprint(Pstudenthead)
{
head=head->next;
while(head)
{
printf("学号：%d，成绩：%d ",head->xuehao,head->score);
head=head->next;
}
return;
}
//合并链表和排序用链表实现
PstudentCombination(Pstudenthead1,Pstudenthead2)
{
PstudentpCom=(Pstudent)malloc(sizeof(student));
Pstudenttemp=pCom,p1=head1->next,p2=head2->next;
while(p1!=NULL||p2!=NULL)
{
if(p1->score>p2->score)
{
pCom->next=p1;
pCom=p1;
if(p1->next==NULL)
{
break;
}
p1=p1->next;
}else
{
pCom->next=p2;
pCom=p2;
if(p2->next==NULL)
{
break;
}
p2=p2->next;
}
}
if(p1->next==NULL)
{
pCom->next=p2;
}else
{
pCom->next=p1;
}
returntemp;
}
voidmain()
{
Studentstu1[StuNum1],stu2[StuNum2];
printf("请输入第一组学生信息：");
for(inti=0;i<StuNum1;i++)
{
printf("第1.%d个同学的学号,成绩为：",i+1);
scanf("%d",&stu1[i].xuehao);
scanf("%d",&stu1[i].score);
stu1[i].next=NULL;
}
printf("请输入第二组学生信息：");
for(inti=0;i<StuNum2;i++)
{
printf("第2.%d个同学的学号,成绩为：",i+1);
scanf("%d",&stu2[i].xuehao);
scanf("%d",&stu2[i].score);
stu2[i].next=NULL;
}
Sort(stu1,StuNum1);
Sort(stu2,StuNum2);
CreatLink(stu1,StuNum1);
CreatLink(stu2,StuNum2);
Pstudentps=Combination(stu1,stu2);
printf("合并后的的有序表： ");
print(ps);
return;
}
‘肆’ 将长度m和n的有序链表合并为一个个新的有序链表的算法的时间复杂度为
您好，你的问题，我之前好像也遇到过，以下是我原来的解决思路和方法，希望能帮助到你，若有错误，还望见谅！展开全部
要插入到长度为m的单链表，需要找到表尾，这个过程的时间复杂度为o(m)，连接的时间复杂度为o(1)，所以总的时间复杂度为o(m)，所以答案选C。
单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
时间复杂度是同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。
时间复杂度的计算方法：
1、一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
分析：随着模块n的增大，算法执行的时间的增长率和 f(n) 的增长率成正比，所以 f(n) 越小，算法的时间复杂度越低，算法的效率越高。
2、在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出 T(n) 的同数量级，找出后，f(n) = 该数量级，若 T(n)/f(n) 求极限可得到一常数c，则时间复杂度T(n) = O(f(n))。非常感谢您的耐心观看，如有帮助请采纳，祝生活愉快！谢谢！
‘伍’ 顺序和链式存储结构哪个能存储有序表
觉得顺序存储结构和链式存储结构都可以存储有序表。顺序存储结构可以预先预留一定空间(如一维数组)，链表存储结构比较灵活，可以动态开辟空间，需要时增加。要用哪种存储结构要看你的有序表要进行什么操作了。
‘陆’ 设AB是两个线性表，其表中元素递增有序，长度为m，n。试写一算法分别以顺序存储和链式存储将AB归并
立C[m+n];
指针pa=A,pb=B。
则，if(pa!=null&&pb!=null)
if（*pa<=*pb)
{C[i]=*pa;pa++;}
else
{C[i]=*pb;pb++;}
else
if(pa==null)
C[i]=*pb,直到pb==null;然后结束整个大循环
if(pb==null)
C[i]=*pa,直到pa==null;然后结束整个大循环
循环m+n次，填满C。
链式存储，就是把上面的C的空间省下，将链按照上面的方式重新链接。
‘柒’ 有序线性表可采用的存储结构是什么
有序线性表既可以采用顺序存储结构，也可以采用链式存储结构
‘捌’ 链式有序表的合并中，为什么要把第二个表的头结点释放掉 在链式有序表的合并中，假设头指针为 LA
没有用了，所以释放了。
两根筷子，一头合起来，只有一上一下，所以去掉一个
‘玖’ 有序表归并算法实现
PROC union(VAR LA:Linear_list; LB:Linear_list);
{将所有在线性表LB中存在而线性表LA中不存在的数据元素插入到线性表LA中去}
n := LENGTH(LA); {确定线性表LA的长度}
FOR i:=1 TO LENGTH(LB) DO
[
x:=GET(LB,i);{取得LB中第i个数据元素}
k:=LOCATE(LA,x);{在LA中进行搜索}
IF k=0 THEN
[
INSERT(LA,n+1,x);
n:=n+1;
]
{将LA中不存在的元素插入到LA中，同时修改n的值}
]
ENDP;{union}
c语言实现--顺序存储结构
#include <iostream>
using namespace std;
struct sqlist//顺序存储结构
{
int elem[10];
int last;
};
void Union (struct sqlist *LA, struct sqlist *LB);
int Locate (struct sqlist *temp, int x);
/********************************************/
// name: main //
// parameter: none //
// return : none //
// details: //
/********************************************/
void main()
{
sqlist LA,LB;
//init LA
LA.elem[0] = 1;
LA.elem[1] = 2;
LA.elem[2] = 3;
LA.last = 3;
//init LB
LB.elem[0] = 2;
LB.elem[1] = 3;
LB.elem[2] = 4;
LB.last = 3;
Union(&LA, &LB);//归并
}
/********************************************/
// name: Union //
// parameter: sqlist LA, sqlist LB //
// return : none //
// details: 归并两个线性表LA,LB //
/********************************************/
void Union (struct sqlist *LA, struct sqlist *LB)
{
int i;
int x;
int k;
for (i=0; i<(*LB).last; i++)
{
x = (*LB).elem[i];
k = Locate(LA, x);
if (k==-1)
{
(*LA).elem[(*LA).last] = x;
(*LA).last++;
}
}
}
/********************************************/
// name: Locate //
// parameter: sqlist *temp (struct), //
// int x (need to find) //
// return : i //
// details: 查找线性表temp中是否有x,如 //
// 存在则返回序号，否则返回-1 //
/*******************************************/
int Locate (struct sqlist *temp, int x)
{
int i = 0;
for (i=0; i<(*temp).last; i++)
{
if ((*temp).elem[i] == x)
return i;
}
return -1;
}
PROC merge_linklist(la，lb：linkisttp；VAR lc：linkisttp)；
｛la和lb为参与归并的两个有序表，lc为结果有序表｝
pa：=la↑．next；pb：=lb↑．next；lc：=la；pc：=lc；
WHILE (pa<>NIL AND pb<>NIL) DO
IF pa↑．data<=pb↑．data
THEN [ pc↑．next：=pa；pc：=pa；pa：=pa↑．next]
ELSE [ pc↑．next：=pb；pc：=pb；pb：=pb↑．next]；
IF (pa<>NIL)
THEN pc↑．next：=pa
ELSE pc↑．next：=pb；
dispose(lb)
ENDP；{merge_linklist}
#include <iostream>
using namespace std;
struct linklist
{
int data;
struct linklist *next;
};
void create(int elements[], int num, struct linklist*);
void Union(struct linklist* la, struct linklist* lb, struct linklist*);
void Free(struct linklist* l);
/********************************************/
// name: main //
// parameter: none //
// return : none //
// details: //
/********************************************/
void main()
{
//初始化链表时用到的数组
int elements_1[10] = {1,2,3,4,5,6,7,8,9,10};
int elements_2[5] = {9,10,11,12,13};
//两个链表la,lb和归并结果链表lc
struct linklist *la = (struct linklist*)malloc(sizeof(linklist));
struct linklist *lb = (struct linklist*)malloc(sizeof(linklist));
struct linklist *lc = (struct linklist*)malloc(sizeof(linklist));
//创建链表
create (elements_1, 10, la);
create (elements_2, 5, lb);
//归并
Union(la, lb, lc);
Free(lc);
free(la);
free(lb);
elements_1[1]=2;
}
/********************************************/
// name: Free //
// parameter: *linklist //
// return : none //
// details: 归并 //
/********************************************/
void Free(struct linklist* l)
{
struct linklist* p;
struct linklist* q;
p = (*l).next;
while (p!=NULL)
{
q = p;
p = (*p).next;
free(q);
}
free(l);
}
/********************************************/
// name: Union //
// parameter: linklist,linklist //
// ,*linklist //
// return : none //
// details: 归并 //
/********************************************/
void Union(struct linklist *la, struct linklist *lb, struct linklist* lc)
{
//建立移动指针
struct linklist *pa;
struct linklist *pb;
struct linklist *pc;
pa = (*la).next;
pb = (*lb).next;
pc = lc;
while(pa!=NULL && pb!=NULL)
{
if ((*pa).data <= (*pb).data)
{
(*pc).next = pa;
pc = pa;
pa = (*pa).next;
}
else
{
(*pc).next = pb;
pc = pb;
pb = (*pb).next;
}
}
if (pa!=NULL)
(*pc).next = pa;
else
(*pc).next = pb;
}
/********************************************/
// name: create //
// parameter: array,max,*linklist //
// return : none //
// details: 将给定的数组制成链表 //
/********************************************/
void create(int elements[], int num, struct linklist* l)
{
struct linklist* p;
int i = 0;
//先建立一个空表
(*l).next = NULL;
for (i=num-1; i>=0; i--)
{
p = (struct linklist*)malloc (sizeof(linklist));
(*p).data = elements[i];
//前插式创建
(*p).next = (*l).next;
(*l).next = p;
}
}
‘拾’ 有序链表的合并，c语言
#include<stdio.h>
#include<malloc.h>
typedefstructlist{
intdata;
structlist*next;//下一个节点地址
}list;
//第一条链表
structlist*L=NULL;//头
structlist*head=NULL;//首
structlist*p=NULL;
//第二条链表
structlist*L1=NULL;//头
structlist*head1=NULL;//首
structlist*p1=NULL;
//代理链表
structlist*L2=NULL;//头
structlist*q=NULL;//L2备用地址
structlist*q1=NULL;//备用地址
intmain(){
inti=0,length;
printf("请输入链表的长度 ");
scanf("%d",&length);
head=(structlist*)malloc(sizeof(structlist));
L=head;
printf("请依次输入链表的内容 ");
for(i;i<length;i++){
p=(structlist*)malloc(sizeof(structlist));
scanf("%d",&p->data);
p->next=NULL;
head->next=p;
head=p;
}
inti1=0,length1;
printf("请输入链表的长度 ");
scanf("%d",&length1);
head1=(structlist*)malloc(sizeof(structlist));
L1=head1;
printf("请依次输入链表的内容 ");
for(i1;i1<length1;i1++){
p1=(structlist*)malloc(sizeof(structlist));
scanf("%d",&p1->data);
p1->next=NULL;
head1->next=p1;
head1=p1;
}
L2=(structlist*)malloc(sizeof(structlist));
q=L2;//备用合并链表起始地址
p=L->next;
p1=L1->next;
while(p&&p1){
if(p->data<p1->data){
L2->next=p;
L2=p;
p=p->next;
}elseif(p->data==p1->data){
L2->next=p;
L2=p;
p=p->next;
q1=p1->next;//备用相同元素的下一个地址指向
free(p1);
p1=q1;
}elseif(p->data>p1->data){
L2->next=p1;
L2=p1;
p1=p1->next;
}
}
L2->next=p?p:p1;
free(L1);
printf("合并后链表的内容 ");
p=q->next;
while(p){
printf("%d",p->data);
p=p->next;
}
}