第二章線性表
2.1線性表的型別定義
【線性表】是乙個n個資料元素的有限序列
線性表中的資料元素既可以是乙個數字或者字元，如：
（a, b, c, d, e, ）或者
（6, 17, 23, 14, 56, 11）
資料元素也可能是由由多個資料項構成的記錄，如：
【線性表的特點】：
◆ 存在唯一的乙個稱作「第乙個」的資料元素
◆ 存在唯一的乙個被稱作「最後乙個」的資料元素
◆ 除第乙個之外，集合中每乙個元素均只有乙個前驅
◆ 除最後乙個外，集合中每乙個元素均只有乙個後繼
【線性表的長度】：線性表中元素的個數
【空表】：元素個數n=0時，稱為空表
【注】線性表是指一種邏輯結構
2.2線性表的順序表示和實現
【線性表的順序儲存表示】指的是用一組位址連續的儲存單元依次儲存線性表的資料元素
假設線性表的每個元素需占用l個儲存單元，設線性表第i個資料元素的儲存位置為loc(ai)，第i+1個資料元素的儲存位置loc(ai+1)則滿足下列關係：
loc(ai+1) = loc(ai) + l
【順序表】：通常稱順序結構的線性表為順序表
【特點】：邏輯上相鄰的元素的儲存位置也相鄰，可以隨機訪問，因此，線性表是一種可以隨機訪問的資料結構。
由於順序表中，邏輯上相鄰的元素在物理位置上也相鄰，因此在資料的插入和刪除時需要移動元素。
由於原來邏輯上24和28相鄰，因此在物理位置上24和28相鄰，在24後插入元素25，24同元素25相鄰，25和24、28相鄰，因此需要移動資料元素
原來資料24和21、28相鄰，刪除24後，21和28相鄰，因此需要移動資料。
【一般情況下】：
● 假設順序表有n個元素，在第i個位置之前插入乙個元素時，需要將第n至第i個元素向後移動乙個位置，將第i個位置空出來，插入新元素。
● 假設順序表有n個元素，將第i個位置的元素刪除，需要將從第i+1至第n（共n-i）個元素依稀向前移動乙個位置。
● 當在順序表中插入和刪除資料元素時，其時間主要耗費在移動元素上，而移動元素的個數取決於插入或刪除元素的位置
● 在等概率情況下，順序表中刪除或插入乙個資料元素，平均約移動表中一半元素
2.3 線性表的鏈式表示和實現
2.3.1線性鍊錶
【特點】用一組任意的儲存單元儲存線性表的資料元素（這組儲存單元可以是連續的，也可以是不連續的）
【舉例】
【結點結構】
單鏈表的結點有兩個域：資料域和指標域
資料域用來存放單鏈表的資料資訊
指標域存放下指向下乙個結點的指標，即下乙個結點的儲存位置
【線性鍊錶&單鏈表】由於鍊錶中每乙個結點只包含乙個指標域，因此又稱單鏈表或線性鍊錶。
【頭結點】為了操作方便有時在單鏈表的第乙個結點之前附設乙個頭結點，頭結點的資料域中可以不存放任何信心，或者存放單鏈表的長度等類的附加資訊。
【注】頭結點並不是單鏈表的第乙個結點
【舉例】帶頭結點的非空單鏈表
【舉例】帶頭結點的空單鏈表
【單鏈表的插入】
設有單鏈表h
【單鏈表結點型別定義】
typedef struct lnodelnode;
1、將資料d插入單鏈表，使之成為單鏈表的第乙個結點
【操作】
lnode *q=(lnode *)malloc(sizeof(lnode)
*q -> date = d
*q -> next = h -> next;
h -> next = q
2、將資料d插入單鏈表a結點後面
【步驟】
lnode *q=(lnode *)malloc(sizeof(lnode)
*q -> date = d
*q -> next = a -> next;
a-> next = q
【詳解】
【單鏈表的刪除】
1、 在單鏈表h中刪除結點a
【注】要刪除單鏈表中的乙個結點，必須知道該節點的前驅結點
【步驟】
q-> next = p -> next
free( p )
【詳解】
【練習】
1、 如何找到單鏈表（整型）中最大關鍵字？時間複雜度是多少？
【提示】
先去乙個最小的整型數a，從煉表頭開始乙個接乙個的進行比較，若大於a，替換，小於a，轉下乙個結點，時間複雜度是o（n）
2、 如何在單鏈表中第i個位置插入結點？時間複雜度是多少？
【提示】首先判斷i的有效性，然後遍歷單鏈表，找到第i-1個位置，在第i-1個位置後插入新結點，時間複雜度是o(n)
3、 如何刪除單鏈表中關鍵字為key的第乙個結點？ 時間複雜度是多少？
2.3.2迴圈鍊錶
【迴圈鍊錶】表中最後乙個結點的指標指向頭結點，整個鍊錶形成乙個環，從迴圈鍊錶中的任乙個結點出發均可找到表中其他結點。
【帶尾結點的單鏈表】有時鍊錶中不設頭結點而設尾指標，可以使某些操作簡化。
【注】掌握迴圈鍊錶的插入和刪除操作
2.3.3 雙向鍊錶
【概念】雙向鍊錶中包含兩個指標域，其一是指向直接後繼，另乙個是指向前趨。
【注】掌握雙向鍊錶的插入和刪除操作
資料結構 c語言版 複習
積少成多，爭取每天進步一點。資料結構複習資料 一 填空題 1.資料結構是一門研究非數值計算的程式設計問題中計算機的操作物件以及它們之間的關係和運算等的學科 2.資料結構被形式地定義為 d r 其中d是資料元素的有限集合 r是d上的關係有限集合 3.資料結構包括資料的邏輯結構 資料的儲存結構和資料的運...
資料結構 c語言版 複習
資料結構複習資料 一 填空題 1.資料結構是一門研究非數值計算的程式設計問題中計算機的操作物件以及它們之間的關係和運算等的學科。2.資料結構被形式地定義為 d,r 其中d是資料元素的有限集合，r是d上的關係有限集合。3.資料結構包括資料的邏輯結構 資料的儲存結構和資料的運算這三個方面的內容。4.資料...
資料結構 c語言版 複習
資料結構複習資料 一 填空題 1.資料結構是一門研究非數值計算的程式設計問題中計算機的操作物件以及它們之間的關係和運算等的學科。2.資料結構被形式地定義為 d,r 其中d是資料元素的有限集合，r是d上的關係有限集合。3.資料結構包括資料的邏輯結構 資料的儲存結構和資料的運算這三個方面的內容。4.資料...