主頁 >  其他 > 《資料結構》第二章 | 線性表 知識梳理（應對期末考）

《資料結構》第二章 | 線性表 知識梳理（應對期末考）

2021-09-13 09:20:36 其他

文章目錄

  • 一、線性表的定義和特點及案例引入
    • 1.線性表的定義和特點
    • 2.案例引入
      • (1) 一元多項式的運算
      • (2) 稀疏多項式的運算
      • (3) 圖書資訊管理系統
  • 二、線性表的型別定義
  • 三、線性表的順序表示和實作
    • 1.初始化順序表
    • 2.順序表取值
    • 3.順序表查找
    • 4.順序表的插入
    • 5.順序表的洗掉
    • 6.基本操作補充
    • 7.順序表的特點
  • 四、線性表的鏈式表示和實作
    • 1.鏈表介紹及單鏈表、雙鏈表、回圈鏈表基本定義
    • 2.三個典型問題
    • 3.鏈表的特點及優缺點
  • 五、單鏈表
    • 1.單鏈表的定義和實作
    • 2.單鏈表的存盤結構定義
    • 3.初始化單鏈表
    • 4.基本操作補充
    • 5.單鏈表的取值
    • 6.單鏈表的查找
    • 7.單鏈表的插入
    • 8.單鏈表的洗掉
    • 9.鏈表運算時間效率分析
  • 六、回圈鏈表
    • 1.回圈鏈表的基本形態：
    • 2.回圈鏈表特點
    • 3.回圈鏈表的合并
  • 七、雙向鏈表
    • 1.雙向鏈表基本形態及特點
    • 2.雙向鏈表的插入
    • 3.雙向鏈表的洗掉
  • 八、順序表和鏈表的比較
  • 九、線性表的應用
    • 1.線性表的合并
    • 2. 順序有序表的合并
    • 3.有序鏈表的合并
  • 十、案例實作與分析
    • 1.多項式的創建
    • 2.多項式的相加
  • 十一、單鏈表、回圈鏈表、雙向鏈表的時間效率的比較
  • 十二、總結

線性表的知識是資料結構中的重點及基礎，涉及到的知識會比較多，但對線性表的操作反復進行理解與實踐會使你對線性表的理解更加深刻、學的更好，

一、線性表的定義和特點及案例引入

1.線性表的定義和特點

了解線性表內元素的關系，書上對這部分也有了比較詳細的介紹，在此我僅用圖把它們的關系羅列出來，
在這里插入圖片描述

在這里插入圖片描述

2.案例引入

(1) 一元多項式的運算

了解每一項的指數與其在線性表中的對應關系，
在這里插入圖片描述
創建新陣列c，分別從頭遍歷比較a和b的每一項，指數相同，對應系數相加，若其和不為零，則在c中增加一個新項，指數不相同，則將指數較小的項復制到c中，當一個多項式已遍歷完畢時，將另一個剩余項依次復制到c中即可，
在這里插入圖片描述

(2) 稀疏多項式的運算

對于稀疏多項式，每個項的指數不再代表一個陣列的下標，因此分別要開辟空間存放系數和指數，
在這里插入圖片描述
對于指數不是依次增加的多項式，要學會如何去存盤資料，例如：

在這里插入圖片描述

因此當我們在存盤上面兩個多項式時，如果仍然使用順序表進行存盤，則缺點有：（1）存盤空間分配不靈活，（2）運算的空間復雜度高，我們應該使用鏈式結構進行存盤，

在這里插入圖片描述
進行上面兩個多項式的相加：

分析：首先我們從A的結點開始，往后一位則是指數為0，系數為7的結點，與B進行比較，發現B中沒有指數為0的結點，我們不作處理，再對鏈表A后面的結點進行分析，發現鏈表A與鏈表B都有指數為1的結點，則將它們的系數相加放在鏈表A中，以此類推進行分析，程序與結果如下圖：

在這里插入圖片描述

在這里插入圖片描述
在這里插入圖片描述

在這里插入圖片描述

(3) 圖書資訊管理系統

對于圖書資訊管理系統，我們經常會有查找、插入、洗掉、修改、排序、計數等操作，用順序表或鏈表存盤圖書資訊的方式如下：

在這里插入圖片描述

小結：
(1) 線性表中資料元素的型別可以為簡單型別，也可以為復雜型別，
(2) 許多實際應用問題所涉的基本操作有很大相似性，不應為每個具體應用單獨撰寫一個程式,過于耗費成本，
(3) 從具體應用中抽象出共性的邏輯結構和基本操作（抽象資料型別），然后實作其存盤結構和基本操作，

二、線性表的型別定義

線性表主要分為順序表與鏈表，它們的重要基本操作有初始化、取值、查找、插入、洗掉，順序表的存盤方式為隨機存盤，鏈表的存盤方式為順序存盤，

順序存盤定義：把邏輯上相鄰的資料元素存盤在物理上相鄰的存盤單元中的存盤結構，簡言之，邏輯上相鄰，物理上也相鄰，

順序存盤方法：用一組地址連續的存盤單元依次存盤線性表的元素，可通過陣列V[n]來實作，

三、線性表的順序表示和實作

資料元素相互之間的存盤關系：
在這里插入圖片描述
順序表的型別定義：

#define  MAXSIZE 100     //最大長度
typedef  struct 
{
 	 ElemType  *elem;      //指向資料元素的基地址
  	int  length;                 //線性表的當前長度                        
 }SqList；

圖書表的順序存盤結構型別定義：

#define MAXSIZE 10000	//圖書表可能達到的最大長度 
typedef struct			//圖書資訊定義
{ 
   char no[20];			//圖書ISBN
   char name[50];		//圖書名字
   float price; 			//圖書價格
}Book; 
typedef struct
{ 
   Book *elem;	             //存盤空間的基地址 
   int length;		//圖書表中當前圖書個數 
}SqList;		//圖書表的順序存盤結構型別為SqList

以下是對順序表操作的具體步驟，對于簡單的代碼，在代碼后面我注釋說明；而相對復雜的代碼，我再具體進行解釋及說明，

1.初始化順序表

方法1：引數為參考型別：

Status InitList_Sq(SqList &L)                   //構造一 個空的順序表L
{
    L.elem=new ElemType[MAXSIZE];   //為順序表分配空間
    if(!L.elem) exit(OVERFLOW);           //存盤分配失敗
    L.length=0;				     //空表長度為0
    return OK;
}

方法2：引數用指標型別：

Status InitList_Sq(SqList *L) //構造一個空的順序表L
{
	L-> elem=new ElemType[MAXSIZE];   //為順序表分配空間
    if(! L-> elem) exit(OVERFLOW);       //存盤分配失敗
    L-> length=0;	            	  //空表長度為0
    return OK;
}

2.順序表取值

獲取順序表L中的某個資料元素的內容：

int GetElem(SqList L,int i,ElemType &e)
{
  if (i<1||i>L.length) return ERROR;   
   //判斷i值是否合理，若不合理，回傳ERROR
  e=L.elem[i-1];   //第i-1的單元存盤著第i個資料
  return OK;
}

這個演算法的時間復雜度為O(1)，

3.順序表查找

在線性表L中查找值為e的資料元素:

int LocateELem(SqList L,ElemType e)
{
  	for (i=0;i< L.length;i++)
      	if (L.elem[i]==e) return i+1;   //回傳查找值為e的位置             
 	 return 0;
}

要求順序表查找演算法的時間復雜度要先了解一個知識：什么是平均查找長度？（簡稱ASL），書上對平均查找長度有明確的解釋，我這里就簡單地解釋一下，平均查找長度就是（每個元素被操作的概率）乘以（最壞情況下n次到第i個元素的和除以2），例如查找操作，假設一共有n個元素，因為每一個元素都有被查找的可能，因此概率為n分之1，假設最壞情況是回圈第n次才找到該元素，因此時間復雜度就為n分之1乘以i的1到n的和，

4.順序表的插入

在這里插入圖片描述
在線性表L中第i個資料元素之前插入資料元素e：

Status ListInsert_Sq(SqList &L,int i ,ElemType e)
{
   if(i<1 || i>L.length+1) return ERROR;	         //i值不合法
   if(L.length==MAXSIZE) return ERROR;    //當前存盤空間已滿     
   for(j=L.length-1;j>=i-1;j--) 
       L.elem[j+1]=L.elem[j];    //插入位置及之后的元素后移
    L.elem[i-1]=e;                     //將新元素e放入第i個位置
    ++L.length;		     	//表長增1
    return OK;
}

時間復雜度為O(n)，

5.順序表的洗掉

在這里插入圖片描述
將線性表L中第i個資料元素洗掉：

Status ListDelete_Sq(SqList &L,int i)
{
   if((i<1)||(i>L.length)) return ERROR;	 //i值不合法
   for (j=i;j<=L.length-1;j++)                   
　  　L.elem[j-1]=L.elem[j];       //被洗掉元素之后的元素前移  
   --L.length;               	                 //表長減1
  return OK;
}

時間復雜度：O(n)，

6.基本操作補充

銷毀線性表L：

void DestroyList(SqList &L)
{
  if (L.elem) delete[]L.elem;  //釋放存盤空間
}

清空線性表L：

void ClearList(SqList &L) 
{
   L.length=0;          //將線性表的長度置為0
}

求線性表L的長度：

int GetLength(SqList L)
{
   return (L.length);             
}

判斷線性表L是否為空：

int IsEmpty(SqList L)
{
  if (L.length==0) return 1;      
   else return 0;
}

7.順序表的特點

(1) 利用資料元素的存盤位置表示線性表中相鄰資料元素之間的前后關系，即線性表的邏輯結構與存盤結構一致，

(2) 在訪問線性表時，可以快速地計算出任何一個資料元素的存盤地址，因此可以粗略地認為，訪問每個元素所花時間相等，

這種存取元素的方法被稱為隨機存取法，

優點：
(1) 存盤密度大（結點本身所占存盤量/結點結構所占存盤量），
(2) 可以隨機存取表中任一元素，

缺點：
(1) 在插入、洗掉某一元素時，需要移動大量元素，
(2) 浪費存盤空間，
(3) 屬于靜態存盤形式，資料元素的個數不能自由擴充，

因此，為了克服順序表的缺點而產生了鏈表，

四、線性表的鏈式表示和實作

1.鏈表介紹及單鏈表、雙鏈表、回圈鏈表基本定義

結點：資料元素的存盤映像，由資料域和指標域兩部分組成，
鏈表： n 個結點由指標鏈組成一個鏈表，它是線性表的鏈式存盤映像，稱為線性表的鏈式存盤結構，

鏈式存盤結構定義：
結點在存盤器中的位置是任意的，即邏輯上相鄰的資料元素在物理上不一定相鄰，

線性表的鏈式表示又稱為非順序映像或鏈式映像，

鏈表示意圖：
在這里插入圖片描述
鏈表各結點由兩個域組成：
資料域：存盤元素數值資料，
指標域：存盤直接后繼結點的存盤位置，
在這里插入圖片描述
單鏈表、雙鏈表、回圈鏈表：
結點只有一個指標域的鏈表，稱為單鏈表或線性鏈表，
有兩個指標域的鏈表，稱為雙鏈表，
首尾相接的鏈表稱為回圈鏈表，

在這里插入圖片描述
頭指標、頭結點、首元結點：
頭指標是指向鏈表中第一個結點的指標，
首元結點是指鏈表中存盤第一個資料元素a1的結點，
頭結點是在鏈表的首元結點之前附設的一個結點；資料域內只放空表標志和表長等資訊，
在這里插入圖片描述
鏈表有兩種表現形式：頭結點的有無，
在這里插入圖片描述

2.三個典型問題

問題一：如何表示空表？
答：有頭結點時，當頭結點的指標域為空時表示空表，
如圖所示：
在這里插入圖片描述
問題二：在鏈表中設定頭結點有什么好處？
答：
(1) 便于首元結點的處理，首元結點的地址保存在頭結點的指標域中,所以在鏈表的第一個位置上的操作和其它位置一致，無須進行特殊處理，
(2) 便于空表和非空表的統一處理，無論鏈表是否為空，頭指標都是指向頭結點的非空指標，因此空表和非空表的處理也就統一了，

問題三：頭結點的資料域內裝的是什么？
答：頭結點的資料域可以為空，也可存放線性表長度等附加資訊，但此結點不能計入鏈表長度值，
如圖所示：
在這里插入圖片描述

3.鏈表的特點及優缺點

鏈表（鏈式存盤結構）的特點：
(1) 結點在存盤器中的位置是任意的，即邏輯上相鄰的資料元素在物理上不一定相鄰，
(2) 訪問時只能通過頭指標進入鏈表，并通過每個結點的指標域向后掃描其余結點，所以尋找第一個結點和最后一個結點所花費的時間不等，

這種存取元素的方法被稱為順序存取法，

優點：
(1) 資料元素的個數可以自由擴充，
(2) 插入、洗掉等操作不必移動資料，只需修改鏈接指標，修改效率較高，

缺點：
(1) 存盤密度小，
(2) 存取效率不高，必須采用順序存取，即存取資料元素時，只能按鏈表的順序進行訪問（順藤摸瓜），

五、單鏈表

1.單鏈表的定義和實作

  • 單鏈表是由表頭唯一確定，因此單鏈表可以用頭指標的名字來命名，
  • 若頭指標名是L，則把鏈表稱為表L ，
    在這里插入圖片描述

2.單鏈表的存盤結構定義

typedef struct Lnode
{
     ElemType   data;       //資料域
     struct LNode  *next;   //指標域
}LNode,*LinkList; //LNode指結點，*LinkList指的是指標
// *LinkList為Lnode型別的指標

LNode與*LinkList相等，創建的都是指標，
在這里插入圖片描述
注意區分指標變數和結點變數兩個不同的概念：

  • 指標變數p：表示結點地址，
  • 結點變數*p：表示一個結點，

后面的代碼中會大量用到指標，我覺得用圖來進行說明更方便理解，
在這里插入圖片描述

3.初始化單鏈表

Status InitList_L(LinkList &L){ 
   L=new LNode;//設定一個頭結點                    	
   L->next=NULL;//頭結點的指標域置空
   return OK; 
}

4.基本操作補充

單鏈表的銷毀：

Status DestroyList_L(LinkList &L)
{
    LinkList p;//設定指標p
       while(L)
        {
            p=L;  
            L=L->next;
            delete p;  //洗掉結點
        }
     return OK;
 }

清空單鏈表

Status ClearList(LinkList & L){
  // 將L重置為空表 
   LinkList p,q;
   p=L->next;   //p指向第一個結點
   while(p)       //沒到表尾 
      { 
        q=p->next; delete p;     p=q;   
      }
   L->next=NULL;   //頭結點指標域為空 
   return OK;
 }

求單鏈表表長

int  ListLength_L(LinkList L){
//回傳L中資料元素個數
    LinkList p;
    p=L->next;  //p指向第一個結點
     i=0;             
     while(p){//遍歷單鏈表,統計結點數
           i++;
           p=p->next;    } 
    return i;                             
 }

判斷表是否為空

int ListEmpty(LinkList L)
{ 
	//若L為空表，則回傳1，否則回傳0 
   if(L->next)   //非空 
     return 0;
   else
     return 1;
 }

5.單鏈表的取值

鏈表的查找：要從鏈表的頭指標出發，順著鏈域next逐個結點往下搜索，直至搜索到第i個結點為止，因此，鏈表不是隨機存取結構，

演算法步驟：
(1) 從第1個結點（L->next）順鏈掃描，用指標p指向當前掃描到的結點，p初值p = L->next，
(2) j做計數器，累計當前掃描過的結點數，j初值為1，
(3) 當p指向掃描到的下一結點時，計數器j加1，
(4) 當j = i時，p所指的結點就是要找的第i個結點，

Status GetElem_L(LinkList L,int i,ElemType &e){ 
    p=L->next;j=1; //初始化
     while(p&&j<i){	//向后掃描，直到p指向第i個元素或p為空 
       p=p->next; ++j; 
     } 
     if(!p || j>i)return ERROR; //第i個元素不存在 
     e=p->data; //取第i個元素 
     return OK; 
}//GetElem_L

6.單鏈表的查找

演算法步驟：
(1) 從第一個結點起，依次和e相比較，
(2) 如果找到一個其值與e相等的資料元素，則回傳其在鏈表中的“位置”或地址；
(3) 如果查遍整個鏈表都沒有找到其值和e相等的元素，則回傳或“NULL”，

1.回傳L中值為e的資料元素的地址，查找失敗回傳NULL，

LNode *LocateELem_L (LinkList L，Elemtype e) {
  p=L->next;
  while(p &&p->data!=e)  
        p=p->next;                		
  return p; 	
}

2.回傳L中值為e的資料元素的位置序號，查找失敗回傳0，

int LocateELem_L (LinkList L，Elemtype e) {
 //回傳L中值為e的資料元素的位置序號，查找失敗回傳0 
  p=L->next; j=1;
  while(p &&p->data!=e)  
        {p=p->next;  j++;}          		
  if(p) return j; 
  else return 0;
}

7.單鏈表的插入

1.任意位置插入：

演算法步驟：
在這里插入圖片描述

//在L中第i個元素之前插入資料元素e 
Status ListInsert_L(LinkList &L,int i,ElemType e){ 
     p=L;j=0; 
      while(p&&j<i?1){p=p->next;++j;}	//尋找第i?1個結點 
      if(!p||j>i?1)return ERROR;	//i大于表長 + 1或者小于1  
      s=new LNode;			//生成新結點s 
      s->data=e;      		           //將結點s的資料域置為e 
      s->next=p->next;	   	          //將結點s插入L中 
      p->next=s; 
      return OK; 
}//ListInsert_L

2.頭插法

演算法步驟：

從一個空表開始，重復讀入資料：
(1) 生成新結點，
(2) 將讀入資料存放到新結點的資料域中，
(3) 將該新結點插入到鏈表的前端，

在這里插入圖片描述

void CreateList_F(LinkList &L,int n){ 
     L=new LNode; 
      L->next=NULL; //先建立一個帶頭結點的單鏈表 
      for(i=n;i>0;--i){ 
        p=new LNode; //生成新結點 
        cin>>p->data; //輸入元素值 
        p->next=L->next;L->next=p; 	//插入到表頭 
     } 
}//CreateList_F

3.尾插法

演算法步驟：
(1) 從一個空表L開始，將新結點逐個插入到鏈表的尾部，尾指標r指向鏈表的尾結點，
(2) 初始時，r同L均指向頭結點，每讀入一個資料元素則申請一個新結點，將新結點插入到尾結點后，r指向新結點，

在這里插入圖片描述

void CreateList_L(LinkList &L,int n){ 
      //正位序輸入n個元素的值，建立帶表頭結點的單鏈表L 
      L=new LNode; 
      L->next=NULL; 	
      r=L; 	                                //尾指標r指向頭結點 
      for(i=0;i<n;++i){ 
        p=new LNode;	　	       //生成新結點 
        cin>>p->data;   		       //輸入元素值 
        p->next=NULL; r->next=p;       //插入到表尾 
        r=p; 	                                  //r指向新的尾結點 
      } 
}//CreateList_L

8.單鏈表的洗掉

演算法步驟：
(1) 找到ai-1存盤位置p，
(2) 保存要洗掉的結點的值，
(3) 令p-＞next指向ai的直接后繼結點，
(4) 釋放結點ai的空間，

洗掉示意圖：
在這里插入圖片描述

//將線性表L中第i個資料元素洗掉
 Status ListDelete_L(LinkList &L,int i,ElemType &e){
    p=L;j=0; 
    while(p->next &&j<i-1){                  //尋找第i個結點，并令p指向其前驅 
        p=p->next; ++j; 
    } 
    if(!(p->next)||j>i-1) return ERROR; //洗掉位置不合理 
    q=p->next;                                        //臨時保存被刪結點的地址以備釋放 
    p->next=q->next; 	                  //改變洗掉結點前驅結點的指標域 
    e=q->data; 	                                //保存洗掉結點的資料域 
    delete q; 	                                //釋放洗掉結點的空間 
 return OK; 
}//ListDelete_L

9.鏈表運算時間效率分析

1.查找: 因線性鏈表只能順序存取，即在查找時要從頭指標找起，查找的時間復雜度為 O(n)，
2.插入和洗掉: 因線性鏈表不需要移動元素，只要修改指標，一般情況下時間復雜度為 O(1)，
3.但是，如果要在單鏈表中進行前插或洗掉操作，由于要從頭查找前驅結點，所耗時間復雜度為 O(n) ，

六、回圈鏈表

1.回圈鏈表的基本形態：

在這里插入圖片描述

2.回圈鏈表特點

從回圈鏈表中的任何一個結點的位置都可以找到其他所有結點，而單鏈表做不到，

對回圈鏈表，有時不給出頭指標，而給出尾指標，可以更方便的找到第一個和最后一個結點，
在這里插入圖片描述

3.回圈鏈表的合并

首先設定一個指標指向第一個鏈表的頭結點處，連接各個元素，連接完畢后去掉第二個鏈表的頭結點，即完成回圈鏈表的合并，
在這里插入圖片描述

LinkList  Connect(LinkList  Ta,LinkList  Tb)
{//假設Ta、Tb都是非空的單回圈鏈表
      p=Ta->next; //①p存表頭結點
      Ta->next=Tb->next->next;//②Tb表頭連結Ta表尾
      delete Tb->next; //③釋放Tb表頭結點
      Tb->next=p; //④修改指標
      return  Tb;
}

七、雙向鏈表

1.雙向鏈表基本形態及特點

typedef struct DuLNode{
    ElemType   data;              
    struct DuLNode  *prior;  
    struct DuLNode  *next;  
}DuLNode, *DuLinkList

在這里插入圖片描述

雙向鏈表除了資料域外，在其兩端分別都是指標，
在這里插入圖片描述
需要注意的是，雙向鏈表有以下的特點：d->next->prior = d->prior->next = d，

2.雙向鏈表的插入

雙向鏈表插入的圖示：
在這里插入圖片描述

Status ListInsert_DuL(DuLinkList &L,int i,ElemType e){
   if(!(p=GetElemP_DuL(L,i))) return ERROR;//查找第i個元素，在該元素前插入
    s=new DuLNode; 
   s->data=e;
   s->prior=p->prior;  
   p->prior->next=s;
   s->next=p;  
   p->prior=s;
   return OK;
}

3.雙向鏈表的洗掉

雙向鏈表洗掉圖示及關鍵步驟：
在這里插入圖片描述

Status ListDelete_DuL(DuLinkList &L,int i,ElemType &e)
{
   if(!(p=GetElemP_DuL(L,i)))     return ERROR;
   e=p->data;
   p->prior->next=p->next;
   p->next->prior=p->prior;
   delete p; 
   return OK;
}

八、順序表和鏈表的比較

在這里插入圖片描述
此表不需要記，理解即可，

九、線性表的應用

1.線性表的合并

問題描述：假設利用兩個線性表La和Lb分別表示兩個集合A和B,現要求一個新的集合，

演算法步驟：
依次取出Lb 中的每個元素，執行以下操作，
1.在La中查找該元素，
2.如果找不到，則將其插入La的最后，

void union(List &La, List Lb){
  La_len=ListLength(La);
  Lb_len=ListLength(Lb); 
  for(i=1;i<=Lb_len;i++){
      GetElem(Lb,i,e);
      if(!LocateElem(La,e)) 
           ListInsert(&La,++La_len,e);                     
  }
}

2. 順序有序表的合并

問題描述：
已知線性表La 和Lb中的資料元素按值非遞減有序排列,現要求將La和Lb歸并為一個新的線性表Lc,且Lc中的資料元素仍按值非遞減有序排列，（非遞減排列不排除元素相等）

演算法步驟：
1.創建一個空表Lc，
2.依次從 La 或 Lb 中“摘取”元素值較小的結點插入到 Lc 表的最后，直至其中一個表變空為止，
3.繼續將 La 或 Lb 其中一個表的剩余結點插入在 Lc 表的最后，

在這里插入圖片描述

void MergeList_Sq(SqList LA,SqList LB,SqList &LC){ 
     pa=LA.elem;  pb=LB.elem;     //指標pa和pb的初值分別指向兩個表的第一個元素 
     LC.length=LA.length+LB.length;      	//新表長度為待合并兩表的長度之和 
     LC.elem=new ElemType[LC.length];    	//為合并后的新表分配一個陣列空間 
     pc=LC.elem;                         		//指標pc指向新表的第一個元素 
     pa_last=LA.elem+LA.length-1; 	//指標pa_last指向LA表的最后一個元素 
     pb_last=LB.elem+LB.length-1; 	//指標pb_last指向LB表的最后一個元素 
     while(pa<=pa_last && pb<=pb_last){  	//兩個表都非空 
      if(*pa<=*pb) *pc++=*pa++;        	//依次“摘取”兩表中值較小的結點      
      else *pc++=*pb++;      } pa++;             //LB表已到達表尾
     while(pb<=pb_last)  *pc+
     while(pa<=pa_last)  *pc++=*+=*pb++;          //LA表已到達表尾 
}//MergeList_Sq

3.有序鏈表的合并

演算法步驟：
在這里插入圖片描述
合并后示意圖：
在這里插入圖片描述

void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
   pa=La->next;  pb=Lb->next;
   pc=Lc=La;                    //用La的頭結點作為Lc的頭結點 
   while(pa && pb){
      if(pa->data<=pb->data){ pc->next=pa;pc=pa;pa=pa->next;}
      else{pc->next=pb; pc=pb; pb=pb->next;}
   pc->next=pa?pa:pb;      //插入剩余段  
   delete Lb;                     //釋放Lb的頭結點}

總結：順序有序表的合并與鏈式有序表的合并的時間復雜度都為O(m+n)，因為順序有序表合并時需要開辟另一個存盤空間，因此合并順序有序表的空間復雜度為O(m+n)，而合并鏈式有序表只需將前后地址修改即可，沒有開辟新的存盤空間，因此空間復雜度為0(1)，

十、案例實作與分析

1.多項式的創建

演算法步驟：
在這里插入圖片描述

void CreatePolyn(Polynomial &P,int n)
{//輸入m項的系數和指數，建立表示多項式的有序鏈表P
   P=new PNode; 
   P->next=NULL;		//先建立一個帶頭結點的單鏈表 
   for(i=1;i<=n;++i)		//依次輸入n個非零項
   {
      s=new PNode;		//生成新結點 
      cin>>s->coef>>s->expn;	//輸入系數和指數 
      pre=P;			//pre用于保存q的前驅，初值為頭結點 
      q=P->next;			//q初始化，指向首元結點
      while(q&&q->expn<s->expn)	//找到第一個大于輸入項指數的項*q
      {
         pre=q; 
         q=q->next; 
     }				
      s->next=q;			//將輸入項s插入到q和其前驅結點pre之間 
      pre->next=s; 
   }			 
}

2.多項式的相加

多項式相加示意圖：
在這里插入圖片描述
多項式相加演算法步驟：
在這里插入圖片描述
書上有類C語言代碼，因此這里不必重復，
假設兩個多項式的項數分別為m和n，則演算法的時間復雜度為O(m+n)，空間復雜度為O(1)，

十一、單鏈表、回圈鏈表、雙向鏈表的時間效率的比較

在這里插入圖片描述

十二、總結

  • 掌握線性表的邏輯結構特性是資料元素之間存在著線性關系，在計算機中表示這種關系的兩類不同的存盤結構是順序存盤結構（順序表）和鏈式存盤結構（鏈表），

  • 熟練掌握這兩類存盤結構的描述方法，掌握鏈表中的頭結點、頭指標和首元結點的區別及回圈鏈表、雙向鏈表的特點等，

  • 熟練掌握順序表的查找、插入和洗掉演算法 ，

  • 能夠從時間和空間復雜度的角度比較兩種存盤結構的不同特點及其適用場合 ，

原創不易，如果此篇文章對您了解資料結構的線性表有幫助，麻煩點個贊支持一下謝謝，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/299676.html

標籤：其他

上一篇：??兩萬字《演算法 + 資料結構》如何開始??

下一篇：二叉樹鏈式結構

標籤雲
其他(157675) Python(38076) JavaScript(25376) Java(17977) C(15215) 區塊鏈(8255) C＃(7972) AI(7469) 爪哇(7425) MySQL(7132) html(6777) 基礎類(6313) sql(6102) 熊猫(6058) PHP(5869) 数组(5741) R(5409) Linux(5327) 反应(5209) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4554) 数据框(4311) css(4259) 节点.js(4032) C語言(3288) json(3245) 列表(3129) 扑(3119) C++語言(3117) 安卓(2998) 打字稿(2995) VBA(2789) Java相關(2746) 疑難問題(2699) 细绳(2522) 單片機工控(2479) iOS(2429) ASP.NET(2402) MongoDB(2323) 麻木的(2285) 正则表达式(2254) 字典(2211) 循环(2198) 迅速(2185) 擅长(2169) 镖(2155) 功能(1967) .NET技术(1958) Web開發(1951) python-3.x(1918) HtmlCss(1915) 弹簧靴(1913) C++(1909) xml(1889) PostgreSQL(1872) .NETCore(1853) 谷歌表格(1846) Unity3D(1843) for循环(1842)

熱門瀏覽
  • 網閘典型架構簡述

    網閘架構一般分為兩種：三主機的三系統架構網閘和雙主機的2+1架構網閘。 三主機架構分別為內端機、外端機和仲裁機。三機無論從軟體和硬體上均各自獨立。首先從硬體上來看，三機都用各自獨立的主板、記憶體及存盤設備。從軟體上來看，三機有各自獨立的作業系統。這樣能達到完全的三機獨立。對于“2+1”系統，“2”分為 ......

    uj5u.com 2020-09-10 02:00:44 more
  • 如何從xshell上傳檔案到centos linux虛擬機里

    如何從xshell上傳檔案到centos linux虛擬機里及：虛擬機CentOs下執行 yum -y install lrzsz命令，出現錯誤：鏡像無法找到軟體包 前言 一、安裝lrzsz步驟 二、上傳檔案 三、遇到的問題及解決方案 總結 前言 提示：其實很簡單，往虛擬機上安裝一個上傳檔案的工具 ......

    uj5u.com 2020-09-10 02:00:47 more
  • 一、SQLMAP入門

    一、SQLMAP入門 1、判斷是否存在注入 sqlmap.py -u 網址/id=1 id=1不可缺少。當注入點后面的引數大于兩個時。需要加雙引號， sqlmap.py -u "網址/id=1&uid=1" 2、判斷文本中的請求是否存在注入 從文本中加載http請求，SQLMAP可以從一個文本檔案中 ......

    uj5u.com 2020-09-10 02:00:50 more
  • Metasploit 簡單使用教程

    metasploit 簡單使用教程 浩先生， 2020-08-28 16:18:25 分類專欄： kail 網路安全 linux 文章標簽： linux資訊安全 編輯 著作權 metasploit 使用教程 前言 一、Metasploit是什么？ 二、準備作業 三、具體步驟 前言 Msfconsole ......

    uj5u.com 2020-09-10 02:00:53 more
  • 游戲逆向之驅動層與用戶層通訊

    驅動層代碼： #pragma once #include <ntifs.h> #define add_code CTL_CODE(FILE_DEVICE_UNKNOWN,0x800,METHOD_BUFFERED,FILE_ANY_ACCESS) /* 更多游戲逆向視頻www.yxfzedu.com ......

    uj5u.com 2020-09-10 02:00:56 more
  • 北斗電力時鐘（北斗授時服務器）讓網路資料更精準

    北斗電力時鐘（北斗授時服務器）讓網路資料更精準 北斗電力時鐘（北斗授時服務器）讓網路資料更精準 京準電子科技官微——ahjzsz 近幾年，資訊技術的得了快速發展，互聯網在逐漸普及，其在人們生活和生產中都得到了廣泛應用，并且取得了不錯的應用效果。計算機網路資訊在電力系統中的應用，一方面使電力系統的運行 ......

    uj5u.com 2020-09-10 02:01:03 more
  • 【CTF】CTFHub 技能樹 彩蛋 writeup

    ?碎碎念 CTFHub：https://www.ctfhub.com/ 筆者入門CTF時時剛開始刷的是bugku的舊平臺，后來才有了CTFHub。 感覺不論是網頁UI設計，還是題目質量，賽事跟蹤，工具軟體都做得很不錯。 而且因為獨到的金幣制度的確讓人有一種想去刷題賺金幣的感覺。 個人還是非常喜歡這個 ......

    uj5u.com 2020-09-10 02:04:05 more
  • 02windows基礎操作

    我學到了一下幾點 Windows系統目錄結構與滲透的作用 常見Windows的服務詳解 Windows埠詳解 常用的Windows注冊表詳解 hacker DOS命令詳解（net user / type /md /rd/ dir /cd /net use copy、批處理 等） 利用dos命令制作 ......

    uj5u.com 2020-09-10 02:04:18 more
  • 03.Linux基礎操作

    我學到了以下幾點 01Linux系統介紹02系統安裝，密碼啊破解03Linux常用命令04LAMP 01LINUX windows： win03 8 12 16 19 配置不繁瑣 Linux：redhat,centos(紅帽社區版)，Ubuntu server,suse unix:金融機構，證券，銀 ......

    uj5u.com 2020-09-10 02:04:30 more
  • 05HTML

    01HTML介紹 02頭部標簽講解03基礎標簽講解04表單標簽講解 HTML前段語言 js1.了解代碼2.根據代碼 懂得挖掘漏洞 （POST注入/XSS漏洞上傳）3.黑帽seo 白帽seo 客戶網站被黑帽植入劫持代碼如何處理4.熟悉html表單 <html><head><title>TDK標題，描述 ......

    uj5u.com 2020-09-10 02:04:36 more
最新发布
  • 2023年最新微信小程式抓包教程

    01 開門見山 隔一個月發一篇文章，不過分。 首先回顧一下《微信系結手機號資料庫被脫庫事件》，我也是第一時間得知了這個訊息，然后跟蹤了整件事情的經過。下面是這起事件的相關截圖以及近日流出的一萬條資料樣本： 個人認為這件事也沒什么，還不如關注一下之前45億快遞資料查詢渠道疑似在近日復活的訊息。 訊息是 ......

    uj5u.com 2023-04-20 08:48:24 more
  • web3 產品介紹：metamask 錢包 使用最多的瀏覽器插件錢包

    Metamask錢包是一種基于區塊鏈技術的數字貨幣錢包，它允許用戶在安全、便捷的環境下管理自己的加密資產。Metamask錢包是以太坊生態系統中最流行的錢包之一，它具有易于使用、安全性高和功能強大等優點。 本文將詳細介紹Metamask錢包的功能和使用方法。 一、 Metamask錢包的功能 數字資 ......

    uj5u.com 2023-04-20 08:47:46 more
  • vulnhub_Earth

    前言 靶機地址->>>vulnhub_Earth 攻擊機ip：192.168.20.121 靶機ip：192.168.20.122 參考文章 https://www.cnblogs.com/Jing-X/archive/2022/04/03/16097695.html https://www.cnb ......

    uj5u.com 2023-04-20 07:46:20 more
  • 從4k到42k，軟體測驗工程師的漲薪史，給我看哭了

    清明節一過，盲猜大家已經無心上班，在數著日子準備過五一，但一想到銀行卡里的余額……瞬間心情就不美麗了。最近，2023年高校畢業生就業調查顯示，本科畢業月平均起薪為5825元。調查一出，便有很多同學表示自己又被平均了。看著這一資料，不免讓人想到前不久中國青年報的一項調查：近六成大學生認為畢業10年內會 ......

    uj5u.com 2023-04-20 07:44:00 more
  • 最新版本 Stable Diffusion 開源 AI 繪畫工具之中文自動提詞篇

    🎈 標簽生成器 由于輸入正向提示詞 prompt 和反向提示詞 negative prompt 都是使用英文，所以對學習母語的我們非常不友好 使用網址：https://tinygeeker.github.io/p/ai-prompt-generator 這個網址是為了讓大家在使用 AI 繪畫的時候 ......

    uj5u.com 2023-04-20 07:43:36 more
  • 漫談前端自動化測驗演進之路及測驗工具分析

    隨著前端技術的不斷發展和應用程式的日益復雜，前端自動化測驗也在不斷演進。隨著 Web 應用程式變得越來越復雜，自動化測驗的需求也越來越高。如今，自動化測驗已經成為 Web 應用程式開發程序中不可或缺的一部分，它們可以幫助開發人員更快地發現和修復錯誤，提高應用程式的性能和可靠性。 ......

    uj5u.com 2023-04-20 07:43:16 more
  • CANN開發實踐：4個DVPP記憶體問題的典型案例解讀

    摘要：由于DVPP媒體資料處理功能對存放輸入、輸出資料的記憶體有更高的要求（例如，記憶體首地址128位元組對齊），因此需呼叫專用的記憶體申請介面，那么本期就分享幾個關于DVPP記憶體問題的典型案例，并給出原因分析及解決方法。 本文分享自華為云社區《FAQ_DVPP記憶體問題案例》，作者：昇騰CANN。 DVPP ......

    uj5u.com 2023-04-20 07:43:03 more
  • msf學習

    msf學習 以kali自帶的msf為例 一、msf核心模塊與功能 msf模塊都放在/usr/share/metasploit-framework/modules目錄下 1、auxiliary 輔助模塊，輔助滲透（埠掃描、登錄密碼爆破、漏洞驗證等） 2、encoders 編碼器模塊，主要包含各種編碼 ......

    uj5u.com 2023-04-20 07:42:59 more
  • Halcon軟體安裝與界面簡介

    1. 下載Halcon17版本到到本地 2. 雙擊安裝包后 3. 步驟如下 1.2 Halcon軟體安裝 界面分為四大塊 1. Halcon的五個助手 1) 影像采集助手：與相機連接，設定相機引數，采集影像 2) 標定助手：九點標定或是其它的標定，生成標定檔案及內參外參，可以將像素單位轉換為長度單位 ......

    uj5u.com 2023-04-20 07:42:17 more
  • 在MacOS下使用Unity3D開發游戲

    第一次發博客，先發一下我的游戲開發環境吧。 去年2月份買了一臺MacBookPro2021 M1pro(以下簡稱mbp)，這一年來一直在用mbp開發游戲。我大致分享一下我的開發工具以及使用體驗。 1、Unity 官網鏈接： https://unity.cn/releases 我一般使用的Apple ......

    uj5u.com 2023-04-20 07:40:19 more

Copyright © 2010-2020 有解無憂