數據結構與演算法筆記 cp2-1：線性表

  • 2019 年 11 月 7 日
  • 筆記

線性表

1.1 定義：

List，由零個或多個數據特性相同的元素構成的有限序列。個數 n 稱為線性表的長度，n=0 的時候稱為空表。比如說，十二星座就是一個線性表，它的「第一個」和「最後一個」元素都是唯一的，並且中間的元素均只有一個前驅、一個後繼。

1.2 抽象數據類型

ADT List{      Data:.......      Operation:          InitList(&L): 初始化，建立一個空的線性表L          ClearList(&L): 清空線性表L          GetElem(L,i,&e): 將L中第i個位置元素值返回給e          LocateElem(L,e): 在L中查找與e相等的元素          ListInsert(&L,i,e): 在L中第i個位置插入新元素e          ListDelete(&L,i,&e): 刪除L中第i個位置元素，並用e返回其值          ListLength(L): 返回L長度  } ADT List

線性表的順序存儲結構 / 順序表

2.1 定義：

指的是用一段地址連續的存儲單元依次存儲線性表的數據元素。

各個元素的地址之間構成等差數列，因此，知道了某一個元素的地址，就可以隨時推導出其它元素的地址，也就是說不管取出還是存入哪一個元素，花費的時間都一樣，是一個常數(O(1))，這種特性的存儲結構就叫隨機存取結構。

一維數組可以實現線性表的順序存儲結構，不過要注意數組下標從0開始，而說線性表的時候說的是位序，是從1開始的。

2.2 基本操作

(1) 初始化：

首先定義線性表順序存儲結構：

typedef struct Table{      int * head;//聲明了一個名為head的長度不確定的數組，也叫「動態數組」      int length;//記錄當前順序表的長度      int size;//記錄順序表分配的存儲容量  }table;

第一個操作是初始化，包括：給head申請足夠大小的物理空間；給size和length賦初值：

#define Size 5 //對Size進行宏定義，表示順序表申請空間的大小  table initTable(){      table t;      t.head=(int*)malloc(Size*sizeof(int));//構造一個空的順序表，動態申請存儲空間      if (!t.head) //如果申請失敗，作出提示並直接退出程式      {          printf("初始化失敗");          exit(0);      }      t.length=0;//空表的長度初始化為0      t.size=Size;//空表的初始存儲空間為Size      return t;  }

(2) 取值： 找某一個位序的元素，只需要判斷位序的合法性，之後返回數組[位序-1]即可。

(3) 查找/修改： 遍曆數組元素，與目標元素比較，相等則返回。如果要修改，重新賦值即可。

(4) 刪除： 找到目標元素，讓後續元素整體前移一個位置，之後長度減一即可。

table delTable(table t,int add){      if (add>t.length || add<1) {          printf("被刪除元素的位置有誤");          exit(0);      }      //刪除操作      for (int i=add; i<t.length; i++) {          t.head[i-1]=t.head[i];      }      t.length--;      return t;  }

比如說要刪除5個元素中的第三個，那麼 add 就是 3，而 t.head[3] 就是第四個元素，從這個元素開始依次向前移動並覆蓋前面的元素。

(5) 插入： 找到目標位置，將該位置對應元素以及後續元素整體後移一個位置，之後長度加一即可。

//插入函數，其中，elem為插入的元素，add為插入到順序表的位置  table addTable(table t,int elem,int add)  {      //判斷插入本身是否存在問題      if (add>t.length+1||add<1) {          printf("插入位置有問題");          return t;      }      //線性表長度等於數組長度，沒有多餘空間容納新插入的元素，此時需要申請      if (t.length==t.size) {          t.head=(int *)realloc(t.head, (t.size+1)*sizeof(int));          if (!t.head) {              printf("存儲分配失敗");              return t;          }          t.size+=1;      }      for (int i=t.length-1; i>=add-1; i--) {          t.head[i+1]=t.head[i];      }      t.head[add-1]=elem;      t.length++;      return t;  }

  • 首先要注意範圍的判斷，add 作為目標位置，至少也得等於1，此時是插在最前面；同時，add 可以等於 length+1，此時是插在最後面，但不能比 length+1 更大了，否則會出現空隙。
  • 接著要注意是從後往前遍歷的，因為如果是從前往後的話就會發生覆蓋。
  • 可以不做「目標位置是否在表尾」的判斷，這樣會直接繞過for循環，執行賦值。

這裡可以發現，線性表的插入和刪除元素操作往往需要移動大量的元素。

Tags:

VirMach 便宜 VPS