『壹』 將兩個遞增的有序鏈表合並為一個遞增的有序鏈表。要求結果鏈表仍使用原來的兩個鏈表的存儲空間，不另外占
!有個前提，兩個鏈表的數據類型都是一樣的哦
第一種:先新建一個鏈表，然後遍歷第一鏈表，同時把它的值都賦給新建的鏈表，然後，開始第二個鏈表，也是同樣的辦法。加上第二個的時候，先找到新建鏈表的表尾，再表尾處開始添加第二個
第二種:首先遍歷第一個鏈表，找到表尾，然後去掉第二個鏈表的表頭，把第二個鏈表的頭部賦給第一個鏈表的尾部 //當然，如果沒有表頭什麼的就直接把第一個節點賦給第一個就行了。
第二種方法之後，兩個鏈表就合成一個了。
『貳』 怎麼將兩個順序存儲的有序表合並成一個有序表
具體代碼如下：
#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;
}
}