當前位置:首頁 » 服務存儲 » 有序表歸並鏈式存儲
擴展閱讀
電腦硬碟吱吱聲 2022-06-30 15:39:12
賓得k5的參數如何配置 2022-06-30 15:37:58
固態移動硬碟評測 2022-06-30 15:34:10

有序表歸並鏈式存儲

發布時間: 2022-05-19 14:49:38

『壹』 將兩個遞增的有序鏈表合並為一個遞增的有序鏈表。要求結果鏈表仍使用原來的兩個鏈表的存儲空間,不另外占

!有個前提,兩個鏈表的數據類型都是一樣的哦
第一種:先新建一個鏈表,然後遍歷第一鏈表,同時把它的值都賦給新建的鏈表,然後,開始第二個鏈表,也是同樣的辦法。加上第二個的時候,先找到新建鏈表的表尾,再表尾處開始添加第二個
第二種:首先遍歷第一個鏈表,找到表尾,然後去掉第二個鏈表的表頭,把第二個鏈表的頭部賦給第一個鏈表的尾部 //當然,如果沒有表頭什麼的就直接把第一個節點賦給第一個就行了。

第二種方法之後,兩個鏈表就合成一個了。

『貳』 怎麼將兩個順序存儲的有序表合並成一個有序表

具體代碼如下:

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

  • }

  • }