第2章順序表1學(xué)生

第2章線性表

【教學(xué)重點(diǎn)】順序結(jié)構(gòu)，鏈?zhǔn)浇Y(jié)構(gòu)，基本操作

【教學(xué)難點(diǎn)】鏈?zhǔn)浇Y(jié)構(gòu)，雙向鏈表，應(yīng)用舉例

【課外作業(yè)】選擇，判斷，填空，分析，設(shè)計(jì)

【上機(jī)實(shí)踐】驗(yàn)證，分析，設(shè)計(jì)，編程，運(yùn)行

【刪除內(nèi)容】靜態(tài)線性表不予講授，內(nèi)容過時(shí)第2章講解內(nèi)容2.1線性表的類型定義2.2順序表的表示和實(shí)現(xiàn)

2.3鏈?zhǔn)奖淼谋硎竞蛯?shí)現(xiàn)

2.4線性表的應(yīng)用舉例

本章小結(jié)——習(xí)題課

2.1線性表的類型定義2.1.1線性表的基本概念一、線性結(jié)構(gòu)特點(diǎn)

數(shù)據(jù)元素之間一對一關(guān)系，而且：

(1)集合中必然存在一個(gè)唯一的“第一元素”。(2)集合中必然存在一個(gè)唯一的“最后元素”。(3)除最后元素外，均有一個(gè)唯一的“后繼”。(4)除第一元素外，均有一個(gè)唯一的“前驅(qū)”。

2.1線性表的類型定義

再次指出，數(shù)據(jù)元素只是一個(gè)抽象符號，可以代表各種各樣的事物，隨具體問題而定。例如，一個(gè)數(shù)據(jù)元素可以代表一個(gè)學(xué)生、一個(gè)公交站點(diǎn)、一個(gè)城市、一個(gè)棋盤布局。

單值元素：一個(gè)數(shù)據(jù)元素只有一個(gè)數(shù)據(jù)項(xiàng)。

舉例：大寫英文字母{A，B，C，D，E，…，Z}

多值元素：一個(gè)數(shù)據(jù)元素包含多個(gè)數(shù)據(jù)項(xiàng)。

舉例：“學(xué)生信息”表中的數(shù)據(jù)元素。2.1線性表的類型定義二、線性表的定義

線性表舉例（線性表為圓括號，集合為花括號）：【實(shí)例1】大寫英文字母：(A，B，C，…，X，Y，Z)【實(shí)例2】有限整數(shù)數(shù)列：(11，13，15，17，19，21)【實(shí)例2】撲克牌的點(diǎn)數(shù)：(2，3，…，10，J，Q，K，A)【實(shí)例4】每年中的月份：(1,2,3,4,5,6,7,8,9,10,11,12)【實(shí)例5】學(xué)生基本信息：(s1，s2，s3，s4，s5，s6，s7，s8)【實(shí)例6】十六進(jìn)制數(shù)碼：(0，1,…,9，A，B，C，D，E，F(xiàn))2.1線性表的類型定義

線性表(LinearList)：

n(n≥0)個(gè)特性相同的數(shù)據(jù)元素的有限序列。n為線性表的長度，當(dāng)n=0時(shí)，為空表。當(dāng)n>0時(shí)，線性表記作：

(a1，a2，…，ai-1，ai，ai+1，…，an)

①特性相同：n個(gè)數(shù)據(jù)元素屬于同一個(gè)數(shù)據(jù)對象，代表同一類事物；

②有限：所有數(shù)據(jù)元素構(gòu)成一個(gè)有限集合；

③有序：相鄰的數(shù)據(jù)元素構(gòu)成有序?qū)Γㄐ蚺缄P(guān)系）。2.1線性表的類型定義

下標(biāo)編號：下標(biāo)為數(shù)據(jù)元素的序號，編號從1開始，a1為第一個(gè)數(shù)據(jù)元素(首結(jié)點(diǎn))，an為最后一個(gè)數(shù)據(jù)元素(尾結(jié)點(diǎn))，ai為第i個(gè)數(shù)據(jù)元素，中間結(jié)點(diǎn)。

直接后繼(簡稱后繼)：從前向后，a1的后繼是a2，a2的后繼是a3，…，an沒有后繼。一般情況：ai的后繼是ai+1(1≤i≤n-1)。

直接前驅(qū)(簡稱前驅(qū))：從后先前，an的前驅(qū)是an-1，an-1的直接前驅(qū)是an-2，…，a1沒有前驅(qū)。一般：ai的前驅(qū)是ai-1(2≤i≤n)。2.1線性表的類型定義2.1.2線性表的邏輯結(jié)構(gòu)

線性表邏輯結(jié)構(gòu)的描述：D={a1，a2,...,an}枚舉法R1={<a1,a2>，<a2,a3>，…，<an-1,an>}枚舉法或者D={ai|ai∈ElemSet，i=1,2,…,n，n≥0}描述法R1={<ai-1,ai>|ai-1,ai∈D，i=1,2,…,n}描述法

ElemSet代表一般數(shù)據(jù)元素的集合，根據(jù)實(shí)際問題，代表不同的集合。2.1線性表的類型定義線性表的抽象數(shù)據(jù)類型：ADTList{數(shù)學(xué)模型：線性表的邏輯結(jié)構(gòu)描述

基本操作：12個(gè)基本操作（函數(shù)名稱）}ADTList或者ADTList{數(shù)據(jù)對象：D={ai|ai∈ElemSet，i=1,2,…,n，n≥0}

數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai∈D，i=1,2,…,n}

基本操作：12個(gè)基本操作（講解10個(gè)）}ADTList2.1線性表的類型定義2.1.3線性表的基本操作12個(gè)基本操作，講授10個(gè)：①構(gòu)建線性表：StatusInitList(SqList&L)

初始條件：無

操作結(jié)果：構(gòu)建一個(gè)空的線性表L。②遍歷元素：StatusListTraverse(SqListL)

初始條件：線性表L已經(jīng)存在。

操作結(jié)果：逐個(gè)輸出數(shù)據(jù)元素。③銷毀線性表：StatusDestroyList(SqList&L)

初始條件：線性表L已經(jīng)存在。

操作結(jié)果：銷毀線性表L，釋放線性表占用的內(nèi)存空間。2.1線性表的類型定義④清空線性表：StatusClearList(SqList&L)

初始條件：線性表L已經(jīng)存在。

操作結(jié)果：將線性表L置空，線性表長度n=0。⑤線性表判空：StatusListEmpty(SqListL)

初始條件：線性表L已經(jīng)存在。

操作結(jié)果：L為空(n=0)，函數(shù)返回TRUE，否則FALSE。⑥求取長度：intListLength(SqListL)

初始條件：線性表L已經(jīng)存在。

操作結(jié)果：函數(shù)返回線性表L中的數(shù)據(jù)元素個(gè)數(shù)。2.1線性表的類型定義⑦獲取元素：StatusGetElem(SqListL,inti,ElemType&e)

初始條件：線性表L已經(jīng)存在，且非空。

操作結(jié)果：給定元素位置i，得到第i個(gè)數(shù)據(jù)元素的值。⑧定位元素：intLocateElem(SqListL,ElemTypee)

初始條件：線性表L已經(jīng)存在，且非空。

操作結(jié)果：給定數(shù)據(jù)元素的值，返回元素的位序。⑨插入元素：StatusListInsert(SqList&L,inti,ElemTypee)

初始條件：線性表L已經(jīng)存在。

操作結(jié)果：在第i個(gè)位置，插入數(shù)據(jù)元素e，L長度加1。⑩刪除元素：StatusListDelete(SqList&L,inti,ElemType&e)

初始條件：線性表L已經(jīng)存在，且非空。

操作結(jié)果：刪除第i個(gè)位置的數(shù)據(jù)元素，L長度減1。2.2線性表的順序表示和實(shí)現(xiàn)

2.2.1線性表的機(jī)內(nèi)表示

邏輯結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)的書面表達(dá)形式，兩層含義：數(shù)據(jù)元素取值的集合，數(shù)據(jù)元素之間的邏輯關(guān)系（相鄰關(guān)系）。

物理結(jié)構(gòu)：邏輯結(jié)構(gòu)的機(jī)內(nèi)表示，又稱存儲結(jié)構(gòu)，或邏輯結(jié)構(gòu)的機(jī)內(nèi)映像。

書面表示：邏輯結(jié)構(gòu)——數(shù)據(jù)元素(元素取值，邏輯相鄰)

機(jī)內(nèi)表示：物理結(jié)構(gòu)——

結(jié)點(diǎn)(存儲內(nèi)容，地址相鄰)

物理結(jié)構(gòu)需要表達(dá)兩層含義：

（1）數(shù)據(jù)元素取值的機(jī)內(nèi)存儲；

（2）元素相鄰關(guān)系的機(jī)內(nèi)表示。2.2線性表的順序表示和實(shí)現(xiàn)

數(shù)據(jù)元素存放在地址連續(xù)的存儲單元，邏輯相鄰的數(shù)據(jù)元素在存儲器中的物理位置也相鄰，用存儲單元的物理位置來表示數(shù)據(jù)元素之間的相鄰關(guān)系。邏輯相鄰與物理相鄰一致，物理位置體現(xiàn)數(shù)據(jù)元素之間的相鄰關(guān)系。

線性表的這種機(jī)內(nèi)表示稱為線性表的順序存儲結(jié)構(gòu)或順序映像，通常稱為線性表的順序表。2.2線性表的順序表示和實(shí)現(xiàn)

假設(shè)一個(gè)數(shù)據(jù)元素占用l個(gè)存儲單元，l中的第1個(gè)存儲單元作為數(shù)據(jù)元素的存儲位置。

第1個(gè)數(shù)據(jù)元素a1的存儲地址——LOC(a1)

（基地址）

第2個(gè)數(shù)據(jù)元素a2的存儲地址——LOC(a2)+

l

第i個(gè)數(shù)據(jù)元素ai的存儲地址——LOC(ai)+(i-1)×l

第n個(gè)數(shù)據(jù)元素an的存儲地址——LOC(a1)+(n-1)×l2.2線性表的順序表示和實(shí)現(xiàn)

要點(diǎn)小結(jié)：

（1）通常用一維數(shù)組存儲線性表的數(shù)據(jù)元素，C/C++數(shù)組下標(biāo)從0開始，數(shù)據(jù)元素的編號從1開始。第i個(gè)數(shù)據(jù)元素的數(shù)組下標(biāo)維(i-1)

。

（2）基址Loc(a1)加上一個(gè)常數(shù)，得到其它數(shù)據(jù)元素的存儲地址，因此可以隨機(jī)存取線性表中的任意數(shù)據(jù)元素。

（3）問題規(guī)模不同，所需存儲空間也不同，因此要求線性表的長度可變。在C語言中，用動態(tài)分配的一維數(shù)組來實(shí)現(xiàn)。2.2線性表的順序表示和實(shí)現(xiàn)存儲結(jié)構(gòu)定義：

typedefstruct{ElemType*elem;//指針變量，指向基址intlength;//當(dāng)前數(shù)據(jù)元素個(gè)數(shù)intlistsize;//當(dāng)前存儲空間大小}SqList;//SqList為類型名，不是變量名

ElemType泛指一般數(shù)據(jù)類型，應(yīng)用程序中確定具體的數(shù)據(jù)類型，如int、char等。

Elem為ElemType類型的指針，指向線性表的基址，通過基址隨機(jī)存取數(shù)據(jù)元素。

2.2線性表的順序表示和實(shí)現(xiàn)

2.2.2線性表的操作實(shí)現(xiàn)

一、構(gòu)建順序表（算法2.3）

算法思想：

①動態(tài)分配一個(gè)數(shù)組空間，數(shù)組大小預(yù)先定義。

②內(nèi)存分配成功，指針變量elem指向順序表的基址；內(nèi)存分配失敗，elem值為NULL，結(jié)束程序運(yùn)行。

③當(dāng)前表長設(shè)為0，當(dāng)前存儲空間大小設(shè)為LIST_INIT_SIZE。2.2線性表的順序表示和實(shí)現(xiàn)算法描述：#defineLIST_INIT_SIZE100#defineLISTINCREMENT10StatusInitList(SqList&L)//引用類型，雙向傳遞{L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);//分配失敗，結(jié)束程序

L.length=0;//空表，表長為0L.listsize=LIST_INIT_SIZE;//初始存儲容量

returnOK;}//InitList

2.2線性表的順序表示和實(shí)現(xiàn)算法分析：O(1)

，沒有循環(huán)

語法復(fù)習(xí)：引用類型參數(shù)雙向傳遞，內(nèi)存分配函數(shù)；C語言中的運(yùn)算符sizeof，用來計(jì)算變量或類型所占用的內(nèi)存字節(jié)數(shù)。exit函數(shù)用來結(jié)束程序運(yùn)行。voidmain(){SqListL;InitList(L);}

InitList(SqList&L)//虛實(shí)結(jié)合，雙向傳遞，L雙向賦值，返回主函數(shù)2.2線性表的順序表示和實(shí)現(xiàn)二、遍歷數(shù)據(jù)元素

從第1個(gè)元素開始，依次顯示輸出所有數(shù)據(jù)元素。為簡明起見，未按教材編寫算法。voidListTraverse(SqListL)//單向傳遞{for(i=1;i<=L.length;i++)//i為數(shù)據(jù)元素編號printf(L.elem[i-1]);//或printf(L.elem+i-1);}

算法分析：O(n)

問題規(guī)模為當(dāng)前表長L.length，即當(dāng)前表長n；只有一層循環(huán)，執(zhí)行n次。2.2線性表的順序表示和實(shí)現(xiàn)三、求取表長

intListLength(SqListL)//單向傳遞，訪問，不修改{returnL.length;}//時(shí)間復(fù)雜度：O(1)四、清空順序表

StatusClearList(SqList&L)//雙向傳遞，線性表改變

{L.length=0;returnOK;}//時(shí)間復(fù)雜度：O(1)五、順序表判空

StatusListEmpty(SqListL)//單向傳遞{returnL.length==0?TRUE:FALSE;}

時(shí)間復(fù)雜度：O(1)2.2線性表的順序表示和實(shí)現(xiàn)六、銷毀順序表

清空線性表：線性表中沒有數(shù)據(jù)元素，長度為0，還可以再插入數(shù)據(jù)元素。

銷毀線性表：線性表已經(jīng)不存在，無法訪問線性表，不能插入數(shù)據(jù)元素。

StatusDestroyList(SqList&L)//雙向傳，線性表改變{free(L.elem);returnOK;}

算法分析：O(1)

【課堂演示1-順序表簡單操作，插入操作先用后講】2.2線性表的順序表示和實(shí)現(xiàn)七、插入數(shù)據(jù)元素（算法2.4）

假設(shè)，插入一個(gè)數(shù)據(jù)元素e，為了保證邏輯結(jié)構(gòu)和物理結(jié)構(gòu)一致，在第i個(gè)位置插入，要求1≤i≤n+1。1≤i≤n：需要移動數(shù)據(jù)元素插入前：(a1，a2，…，ai-1，ai，…，an)插入后：(a1，a2，…，ai-1，e，ai，…，an)i＝n+1：無需移動數(shù)據(jù)元素插入前：(a1，a2，…，ai-1，ai，…，an)插入后：(a1，a2，…，ai-1，ai，…，an，e)2.2線性表的順序表示和實(shí)現(xiàn)

2.2線性表的順序表示和實(shí)現(xiàn)算法思想：

（1）檢查插入位置：在第i個(gè)位置插入，1≤i≤n+1，否則i值不合法，返回ERROR。

（2）檢查存儲空間：存儲空間夠用，執(zhí)行后面操作，如果不夠用，則增加存儲空間。

（3）移動數(shù)據(jù)元素：依次后移數(shù)據(jù)元素an，an-1，…，ai，在第i個(gè)位置插入，移動數(shù)據(jù)元素個(gè)數(shù)為(n-i+1)。

（4）插入數(shù)據(jù)元素：執(zhí)行數(shù)據(jù)元素的賦值操作，將插入的數(shù)據(jù)元素放在第i個(gè)位置。

（5）增加表的長度：插入成功，表長加1，返回OK。2.2線性表的順序表示和實(shí)現(xiàn)

確切說法：在第i個(gè)位置插入，1≤i≤n+1。

模糊說法：在第i個(gè)位置之前插入。說法不妥原因：

（1）在第n+1個(gè)位置插入，為第n個(gè)位置之后。（2）插入后才是“之前”，插入前是“第i個(gè)位置”。

數(shù)據(jù)元素的訪問：

【課堂演示2-順序表插入操作】2.2線性表的順序表示和實(shí)現(xiàn)算法描述：不判斷存儲空間

StatusListInsert(SqList&L,inti,ElemTypee)//算法2.4{ElemType*p,*q;//輔助變量，算法描述可以省略

if(i<1||i>L.length+1)returnERROR;//i值是否合法

//此處為if語句，判斷當(dāng)前存儲空間是否已滿q=L.elem+i-1;//指針變量q為插入位置for(p=L.elem+L.length-1;p>=q;--p)*(p+1)=*p;//右移或后移數(shù)據(jù)元素*q=e;++L.length;//插入e，表長增1returnOK;

}//ListInsert2.2線性表的順序表示和實(shí)現(xiàn)判斷存儲空間程序代碼：if(L.length>=L.listsize)//當(dāng)前存儲空間是否已滿

{newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType))if(!newbase)exit(OVERFLOW);//分配失敗，程序結(jié)束L.elem=newbase;//新基址L.listsize=L.listsize+LISTINCREMENT;//增加存儲容量}2.2線性表的順序表示和實(shí)現(xiàn)

算法量級估算：

算法執(zhí)行時(shí)間主要是移動數(shù)據(jù)元素，函數(shù)中有一個(gè)循環(huán)，用來移動數(shù)據(jù)元素。因此時(shí)間復(fù)雜度T(n)=O(n)。

最壞情況分析：

最好情況，在第n+1個(gè)位置插入，移動0個(gè)數(shù)據(jù)元素，執(zhí)行0次基本操作；最壞情況，在第1個(gè)位置插入，移動n個(gè)數(shù)據(jù)元素，執(zhí)行n次基本操作。時(shí)間復(fù)雜度均按最壞情況考慮，間復(fù)雜度T(n)=O(n)。2.2線性表的順序表示和實(shí)現(xiàn)平均移動次數(shù)：

移動次數(shù)之和：0+1+2，…，+n-1+n=n(n+1)/2

兩端項(xiàng)相加為n，項(xiàng)數(shù)(n+1)/2

假定每個(gè)位置的插入概率相等，n+1個(gè)插入位置：pi=1/(n+1)

每個(gè)位置平均移動次數(shù)（數(shù)學(xué)期望值expectedvalue）：

Eins=pi

×n(n+1)/2=n/2

時(shí)間復(fù)雜度T(n)=O(n)

2.2線性表的順序表示和實(shí)現(xiàn)八、刪除數(shù)據(jù)元素（算法2.5）

為了保證邏輯結(jié)構(gòu)和物理結(jié)構(gòu)一致，刪除第i個(gè)位置的數(shù)據(jù)元素ai，需要依次移動第i個(gè)位置后面的數(shù)據(jù)元素。

刪除前：(a1，a2，…，ai-1，ai，…，an)

刪除后：(a1，a2，…，ai-1，ai+1，…，an)算法思想：

（1）檢查刪除位置：第i個(gè)位置1≤i≤n；

（2）移動數(shù)據(jù)元素：第i個(gè)位置，移動次數(shù)（n-i）；

（3）減小表的長度：刪除成功，表長減1。

2.2線性表的順序表示和實(shí)現(xiàn)算法描述：StatusListDelete(SqList&L,inti,ElemType&e)//算法2.5{ElemType*p,*q;//算法描述中可以省略if(i<1||i>L.length)returnERROR;p=L.elem+i-1;//p為刪除位置e=*p;//被刪除元素的值賦給eq=L.elem+L.length-1;//表尾元素的位置for(++p;p<=q;++p)//左移*(p-1)=*p;L.length--;//表長減1retu