線性表是由n個具有相同特性的資料元素的有限序列,是最基本、最簡單、也是最常用的一種資料結構

文章目錄

• 資料結構：線性表
• • 一、線性表的類型定義
  • 二、線性表的表示與實作
  • 三、線性連結清單的表示與實作
  • 四、循環連結清單的表示與實作
  • 五、雙向連結清單的表示與實作

資料結構：線性表

一、線性表的類型定義

1. 由一組相同類型資料構成；

2. 特點：

   存在唯一一個沒有前驅的頭元素；

   存在一個沒有後繼的尾元素；

   除了頭與尾，每個元素隻有一個直接前驅與後繼；

3. 線性表是一種典型線性結構：其資料的運算定義在邏輯結構上，而運算的具體實作是在存儲結構上進行的；

4. 基本運算：

   (1) 初始化線性表Initlist(L) // 置空

   将線性表L置為空表。

   (2) 求線性表的長度Getlen(L) // 周遊線性表，統計元素個數

   求解并傳回線性表所含元素的個數n。若線性表為空，則傳回整數0。

   (3) 按序号取元素Getelem(L,i) // 周遊線性表，元素定位

   讀取線性表L第i個資料元素，要求滿足1≤i≤Getlen(L)。

   (4) 按值查找Locate(L,x)

   線上性表L中查找值為ｘ的資料元素，若查找成功則傳回第一個值為x的元素的序号或位址; 否則，在L中未找到值為ｘ的資料元素，傳回一特殊值（例如0），表示查找失敗。

   (5) 插入元素Inselem (L,i,x)

   線上性表L的第 i 個位置上插入一個值為 x 的新元素，這樣使原序号為 i , i+1, …, n 的資料元素的序号變為 i+1,i+2, …, n+1，要求1≤i≤Getlen(L)+1，插入後原表長增1。

   (6) 删除元素Delelem(L,i)

   線上性表L中删除序号為i的資料元素，删除後使序号為 i+1, i+2,…, n 的元素變為序号i, i+1,…,n-1，要求1≤i≤Getlen(L)，删除後表長減１。

5. 兩種基本存儲結構：

   順序存儲結構和鍊式存儲結構；

二、線性表的表示與實作

• 順序存儲

1. 基本特點：

   所有元素占用的位址空間是連續的；

   所有元素存儲空間按照邏輯順序存放；（常用數組描述）

2. 順序存儲下常用運算：

   資料元素的插入；

   

   資料元素的删除；

   

   順序表的合并；

   

3. 優缺點：

   優點：

   1. 存取速度高效，通過下标來直接存儲

      缺點：

   2. 插入和删除比較慢；
   3. 不可以增長長度 ；

三、線性連結清單的表示與實作

• 鍊式存儲

1. 基本特點：

   每個元素一部分存儲自身值，一部分存放前驅或者後驅指針（指針單元稱為結點）；

   有一個頭指針指向第一個節點

   //C 語言采用結構資料類型描述結點如下：
   typedef struct LNode{
         ElemType data;            //結點值
         struct LNode *next;       //存儲下一個結點的位址
   }LNode,*LinkList;
   LNode *head;
              

2. 鍊式存儲下常用運算：

   資料元素的取出:

   

   資料元素的插入:

資料元素的定位:

順序表的合并:

1. 優缺點：

   優點：

   1. 插入和删除速度快，保留原有的實體順序

      缺點：

   2. 查找速度慢，因為查找時，需要循環連結清單通路

四、循環連結清單的表示與實作

​ 循環連結清單是另一種形式的鍊式存儲結構，将單連結清單中最後一個結點的指針指向連結清單的頭結點，使整個連結清單頭尾相接形成一個環形，使單向連結清單前後相連，成為循環連結清單。

操作範例：将兩個循環連結清單首尾相接進行合并，La為第一個循環連結清單表尾指針，Lb為第二個循環連結清單表尾指針，合并後Lb為新連結清單的尾指針，head指向整個合并後的連結清單。

圖解：

實作：

具體操作如下：
LinkList list_merge(LinkList head,LinkList La,LinkList Lb)
{ LNode *p, *q;
p=(LNode *)malloc(sizeof(LNode));//為p申請空間
q=p
p=La->next;                    //指針p指向La連結清單頭
q=Lb->next;                  //指針q指向Lb連結清單頭
La->next=q->next;  
                         //使連結清單Lb連結到La的尾部，并去掉Lb連結清單中的頭結點
Lb->next=p;                 //設定Lb為連結清單的尾指針
head=p;
free(p);
return  head;
}
           

五、雙向連結清單的表示與實作

​ 單連結清單隻有一個指向後繼的指針來表示結點間的邏輯關系。故從任一結點開始找其後繼結點很友善，但要找前驅結點則比較困難。雙向鍊式是用兩個指針表示結點間的邏輯關系。即增加了一個指向其直接前驅的指針域，這樣形成的連結清單有兩條不同方向的鍊，前驅和後繼，是以稱為雙連結清單。

結構圖：

非空雙向連結清單：

優點：在需要查找前驅的操作中，就不必再從頭開始周遊整個連結清單。這種結構極大地簡化了某些操作。

//雙向連結清單結點的定義如下：
  typedef struct DuLNode{
   ElemType data;
   struct DuLNode *prior;
   struct DuLNode *next;
  }DuLNode,*DuLinkList。