【考研或自學資料結構2.1】——線性表（線性表的定義，線性表的基本操作）

線性表

• • 1. 線性表的定義
  • 2. 線性表的基本操作
  • 3 本節重點

離線筆記：

連結：https://pan.baidu.com/s/1e-goeFpFw4CwxYoKhBsCtA

提取碼：eiyq

1. 線性表的定義

線性表是具有

相同

資料類型的n（n≥0）個資料元素的有限

序列

，其中n為表長，當n = 0時線性表是一個

空表

。若用L命名線性表，則其一般表示為

相同：每個資料元素所占空間一樣大

序列：有次序

L = (a1, a2, … , ai, ai+1, … , an)

幾個概念：

ai是線性表中的“第i個”元素線性表中的

位序

a1是

表頭元素

；an是

表尾元素

。

除第一個元素外，每個元素有且僅有一個

直接前驅

；除最後一個元素外，每個元素有且僅有一個

直接後繼

。

注意：

位序

從1開始數組下标從0開始

2. 線性表的基本操作

線性表的基本操作即資料結構三要素中——“運算”

為什麼要實作對資料結構的基本操作？

①團隊合作程式設計，你定義的資料結構要讓别人能夠很友善的使用（封裝）

②将常用的操作/運算封裝成函數，避免重複工作，降低出錯風險

基本操作

• InitList(&L)：

  初始化表

  。構造一個空的線性表L，配置設定記憶體空間。
• DestroyList(&L)：

  銷毀操作

  。銷毀線性表，并釋放線性表L所占用的記憶體空間。
• ListInsert(&L,i,e)：

  插入操作

  。在表L中的第i個位置上插入指定元素e。
• ListDelete(&L,i,&e)：

  删除操作

  。删除表L中第i個位置的元素，并用e傳回删除元素的值。
• LocateElem(L,e)：

  按值查找操作

  。在表L中查找具有給定關鍵字值的元素。
• GetElem(L,i)：

  按位查找操作

  。擷取表L中第i個位置的元素的值。

其他常用操作：

• Length(L)：

  求表長

  。傳回線性表L的長度，即L中資料元素的個數。
• PrintList(L)：

  輸出操作

  。按前後順序輸出線性表L的所有元素值。
• Empty(L)：

  判空操作

  。若L為空表，則傳回true，否則傳回false。

Tips：

①對資料的操作（記憶思路） —— 創銷、增删改查

②C語言函數的定義 —— <傳回值類型> 函數名 (<參數1類型> 參數1，<參數2類型> 參數2，……)

③實際開發中，可根據實際需求定義其他的基本操作

④函數名和參數的形式、命名都可改變（Reference：嚴蔚敏版《資料結構》）

⑤什麼時候要傳入引用“&” —— 對參數的修改結果需要“帶回來”

什麼時候要傳入參數的引用“&” —— 對參數的修改結果需要“帶回來”

3 本節重點