1、第二章 線性表 線性表概念及其邏輯結(jié)構(gòu) 線性表的存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ) 鏈?zhǔn)酱鎯?chǔ) 數(shù)組 一維數(shù)組 結(jié)構(gòu)數(shù)組 二維數(shù)組 鏈表 循環(huán)鏈表 靜態(tài)鏈表 線性表應(yīng)用實(shí)例 有序線性表1線性表（一） 線性表概念及其邏輯結(jié)構(gòu) 線性表的存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ) 鏈?zhǔn)酱鎯?chǔ) 數(shù)組 一維數(shù)組 結(jié)構(gòu)數(shù)組 二維數(shù)組21 線性表及其邏輯結(jié)構(gòu)一、線性表概念與特性線性表是最簡(jiǎn)單、最常用的一種數(shù)據(jù)結(jié)構(gòu) 。通常線性表只被廣泛地定義為是“n個(gè)元素的有限序列”，n0，表示線性表元素個(gè)數(shù) ，也稱(chēng)線性表的表長(zhǎng)。線性表中數(shù)據(jù)元素之間的關(guān)系是線性排列的有次序關(guān)系，除了首元素和尾元素之外，其它數(shù)據(jù)元素都是首尾相接的。 線性表的邏輯結(jié)構(gòu)簡(jiǎn)單，便于實(shí)現(xiàn)存儲(chǔ)和

2、操作。在實(shí)際應(yīng)用中被廣泛采用。線性表可以按照其邏輯順序在計(jì)算機(jī)內(nèi)實(shí)現(xiàn)順序存儲(chǔ)。也可不按照邏輯順序，以鏈?zhǔn)浇Y(jié)構(gòu)動(dòng)態(tài)地存儲(chǔ)。常用的數(shù)據(jù)結(jié)構(gòu)諸如數(shù)組、堆棧、隊(duì)列等都被稱(chēng)為線性表。3二、線性表邏輯結(jié)構(gòu)特征均勻性：雖然不同數(shù)據(jù)表的數(shù)據(jù)元素可以是各種各樣的，但對(duì)于同一線性表的各數(shù)據(jù)元素必定具有相同的數(shù)據(jù)類(lèi)型和長(zhǎng)度。線性關(guān)系：數(shù)據(jù)元素之間的相對(duì)位置是線性的。首元素與尾元素唯一；除尾元素元素之外，各元素均有唯一的直接后繼。除首元素之外，各元素均有唯一的直接前驅(qū)。有序性：各數(shù)據(jù)元素在線性表中的位置只取決于它們的序。有限長(zhǎng)度：是 n個(gè)同類(lèi)元素的有限集合。當(dāng)線性表元素個(gè)數(shù) n=0時(shí)稱(chēng)為空表。非空的線性表（n0）記作

3、： (a1 ， a2，an) 。通?？捎枚M表示為L(zhǎng)=(D，R)。4三、線性表的基本操作 1）Setnull（L） 置空表 （初始化線性表L為空表） 2）ListLength（L） 求表長(zhǎng)度；求表中元素個(gè)數(shù) 3）GetElem（L，i，e） 取表中第i個(gè)元素（1in） 4）PriorElem（L，i） 取i的前趨元素 5）NextElem（L，i） 取i的后繼元素 6）LocateElem（L，e） 返回指定元素在表中的位置 7）ListInsert（L，i，e）插入元素 8）ListDelete（L，e） 刪除元素 9）ListEmpty（L） 判別表是否為空 10）ClearList（L

4、）清除所有元素 11）InitList（&L）同第一個(gè)，初始化線性表為空 12）ListTraverse（L）遍歷輸出所有元素 13）Find（L，e）查找并返回元素 14）ListUpdate（L，e）修改元素 15）ListSort（L）對(duì)所有元素重新按給定的條件排序 5四、線性表的抽象數(shù)據(jù)類(lèi)型描述抽象數(shù)據(jù)類(lèi)型線性表描述為： ADT List 數(shù)據(jù)對(duì)象：D=ai|1in, n0, ai屬于ElemType類(lèi)型 數(shù)據(jù)關(guān)系：R=| ai, ai+1D, i=1,n-1 基本運(yùn)算： Setnull（L） /置空表 （初始化線性表L為空表） ListLength（L） / 求表長(zhǎng)度；求表中元素個(gè)數(shù)

5、 GetElem（L，i,，e） /取表中第i個(gè)元素（1in） ADT List62 線性表的存儲(chǔ)結(jié)構(gòu)一、線性表的兩種存儲(chǔ)結(jié)構(gòu)線性表基本存儲(chǔ)結(jié)構(gòu)有兩種：順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 順序存儲(chǔ)的線性表稱(chēng)為順序表。是靜態(tài)存儲(chǔ)模式，符合靜態(tài)存儲(chǔ)特性。典型的數(shù)據(jù)結(jié)構(gòu)如一維數(shù)組，以及由它描述（仿真，即實(shí)現(xiàn)映像存儲(chǔ)）的較為高級(jí)的數(shù)據(jù)結(jié)構(gòu)，如數(shù)組棧、數(shù)組隊(duì)列、堆、基于數(shù)組的圖形等。鏈?zhǔn)酱鎯?chǔ)的線性表稱(chēng)為鏈表。是動(dòng)態(tài)存儲(chǔ)模式。符合動(dòng)態(tài)存儲(chǔ)特性。典型的數(shù)據(jù)結(jié)構(gòu)如單鏈表，以及由它描述的較為高級(jí)的數(shù)據(jù)結(jié)構(gòu)以及復(fù)雜鏈表，如鏈棧、鏈隊(duì)列、多重鏈表、循環(huán)鏈表等。7二、線性表的存儲(chǔ)結(jié)構(gòu)特性1、順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)屬于靜態(tài)內(nèi)存

6、配置，使用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)元素，這種存儲(chǔ)結(jié)構(gòu)基本特點(diǎn)是：邏輯上相鄰的元素，物理存儲(chǔ)位置相也相鄰。所需存儲(chǔ)空間需要在數(shù)據(jù)操作之前申請(qǐng)。程序運(yùn)行中數(shù)據(jù)空間通常無(wú)變化，或通過(guò)動(dòng)態(tài)數(shù)組申請(qǐng)?jiān)鲅a(bǔ)空間。元素存儲(chǔ)位置與其在線性表中的邏輯序相關(guān)聯(lián)（如為邏輯位置的函數(shù)），通常以一維數(shù)組下標(biāo)（整型向量）來(lái)表示。數(shù)據(jù)元素具備隨機(jī)訪問(wèn)特性。 順序存儲(chǔ)空間計(jì)算：假定線性表的元素類(lèi)型為ElemType，則每個(gè)元素所占用存儲(chǔ)空間大?。ㄗ止?jié)數(shù)）為sizeof(ElemType)，整個(gè)線性表n個(gè)元素所占用存儲(chǔ)空間的大小為 ：n*sizeof(ElemType)82、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特性鏈表是鏈?zhǔn)酱鎯?chǔ)的結(jié)構(gòu)，屬于動(dòng)態(tài)內(nèi)存配置，

7、使用一組任意的存儲(chǔ)單元存儲(chǔ)元素。這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。這種存儲(chǔ)結(jié)構(gòu)基本特點(diǎn)是：邏輯上相鄰的元素在物理位置上并不需要相鄰。所需內(nèi)存空間動(dòng)態(tài)配置，可在程序運(yùn)行過(guò)程中申請(qǐng)存儲(chǔ)空間?？呻S時(shí)釋放不需要的內(nèi)存空間。元素存儲(chǔ)位置以數(shù)據(jù)結(jié)點(diǎn)中的指針值（整型）來(lái)表示。數(shù)據(jù)元素不具備隨機(jī)訪問(wèn)特性。鏈?zhǔn)酱鎯?chǔ)空間管理： 欲創(chuàng)建新結(jié)點(diǎn)s，則使用如下方式申請(qǐng)存儲(chǔ)空間： s=(LinkList *)malloc(sizeof(LinkList);釋放結(jié)點(diǎn)s所占用的存儲(chǔ)空間： free(s);93 數(shù)組數(shù)組是最基礎(chǔ)和重要的數(shù)據(jù)結(jié)構(gòu)之一。一維數(shù)組這種最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)通常被用作描述占用連續(xù)內(nèi)存空間的線性表存

8、儲(chǔ)映像。一、數(shù)組概念及特性數(shù)組(Arry)是數(shù)據(jù)結(jié)構(gòu)中最基本的結(jié)構(gòu)類(lèi)型，是存儲(chǔ)同一類(lèi)型數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。它是一種循序式的結(jié)構(gòu)。幾乎所有的程序設(shè)計(jì)語(yǔ)言都允許用數(shù)組來(lái)描述數(shù)據(jù)。數(shù)組特性：同類(lèi)型元素；循序結(jié)構(gòu)（可實(shí)現(xiàn)順序存儲(chǔ)）； （對(duì)元素的）隨機(jī)訪問(wèn)特性（因其循序性）。對(duì)于每一個(gè)數(shù)組元素而言，都有一個(gè)索引值（Index）和一個(gè)內(nèi)容值（Value） ，表示其相對(duì)位置和相應(yīng)的數(shù)據(jù)。數(shù)組使用的是一種靜態(tài)的內(nèi)存空間配置，需要程序設(shè)計(jì)者事先定義好數(shù)據(jù)類(lèi)型和所需要的內(nèi)存空間的大小，程序在編譯過(guò)程中會(huì)自動(dòng)按照事先的定義配置內(nèi)存空間。 10靜態(tài)的內(nèi)存空間配置缺乏使用彈性。設(shè)計(jì)程序時(shí)，若使用數(shù)組存儲(chǔ)數(shù)據(jù)（比如執(zhí)行過(guò)程中

9、的某個(gè)結(jié)果或最終結(jié)果），如果事先定義的數(shù)組空間過(guò)小，使用時(shí)就容易造成程序的執(zhí)行錯(cuò)誤，反之如果定義的數(shù)組空間過(guò)大，則造成內(nèi)存空間的浪費(fèi)。正因?yàn)閿?shù)組的這種靜態(tài)的內(nèi)存空間配置，所以針對(duì)數(shù)組通常只做兩種運(yùn)算：給定一組下標(biāo)，存取相應(yīng)的數(shù)據(jù)元素。給定一組下標(biāo)，修改相應(yīng)數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值。 二、一維數(shù)組 1、數(shù)組的說(shuō)明 象對(duì)變量一樣, 數(shù)組也必須在使用之前先定義。數(shù)組的定義包括：( 1 ) 數(shù)組元素的類(lèi)型說(shuō)明( 2 ) 存儲(chǔ)在數(shù)組中的最大元素個(gè)數(shù)的說(shuō)明。一個(gè)典型的數(shù)組定義為: 數(shù)據(jù)類(lèi)型 數(shù)組名 長(zhǎng)度 11通常使用數(shù)組的下標(biāo)值，也就是索引值來(lái)標(biāo)識(shí)某個(gè)數(shù)組的元素。例如 a5。2、數(shù)組元素的存儲(chǔ) 在一維數(shù)組

10、中，一旦數(shù)組元素a1的存儲(chǔ)地址LOC(a1)確定，并假設(shè)每個(gè)數(shù)據(jù)元素占用k個(gè)存儲(chǔ)單元，則任一數(shù)據(jù)元素ai 的存儲(chǔ)地址LOC(ai)就可由以下公式求出： LOC(ai)=LOC(a1)+(i-1)*k (0in)【例】聲明一個(gè)長(zhǎng)度為10的整型一維數(shù)組（10個(gè)數(shù)據(jù)元素），數(shù)組名NumberA。 int NumberA10；按照C語(yǔ)言數(shù)組元素下標(biāo)從0開(kāi)始，則有如下公式：NumberAi的內(nèi)存位置 = 數(shù)組首元素位置 + ( i 聲明數(shù)據(jù)類(lèi)型所占內(nèi)存的大小 )123、字符型一維數(shù)組字符數(shù)組用于存放字符串和字符型數(shù)據(jù)。有兩種用法：一是當(dāng)作字符的數(shù)組來(lái)使用。這時(shí)的用法與整數(shù)的數(shù)組、 實(shí)數(shù)的數(shù)組等相同，對(duì)字

11、符數(shù)組的輸入、輸出、賦值、引用等都是針對(duì)單個(gè)的元素進(jìn)行。二是更為重要的用法即存儲(chǔ)、處理字符串。這時(shí)它除了可以像普通數(shù)組一樣使用外，還可以把字符串作為一個(gè)整體進(jìn)行操作。字符串常量與字符串變量 ：字符串常量是用雙引號(hào)包圍的字符序列。存儲(chǔ)字符串常量時(shí)，系統(tǒng)會(huì)在字符序列后自動(dòng)加上 0 標(biāo)志字符串的結(jié)束。字符串的長(zhǎng)度定義為字符串中的有效字符數(shù)，不包括結(jié)束標(biāo)志0和雙引號(hào)。 C語(yǔ)言中所謂的字符串變量是以0作為結(jié)束標(biāo)志的字符數(shù)組，用于存儲(chǔ)和處理字符串常量。在書(shū)中統(tǒng)稱(chēng)為字符串的，既可能是字符串常量也可能是存儲(chǔ)了字符串常量的字符串變量，即特殊的字符數(shù)組。 13字符數(shù)組的初始化說(shuō)明 (1) 用字符對(duì)字符數(shù)組初始化。

12、這時(shí)把字符數(shù)組當(dāng)作普通數(shù)組看待, 產(chǎn)生的數(shù)組不會(huì)有結(jié)束符0。 例：char rat5=H,E,L,L,O;(2) 用字符串常量對(duì)字符數(shù)組初始化。這時(shí)把字符數(shù)組當(dāng)作字符串變量看待。 例：char panic6=“HELLO“; （或char panic6=“HELLO“; ） 這時(shí)存放在數(shù)組panic中的字符包含結(jié)束標(biāo)志0，因此與初始化(1)等價(jià)。 指定了數(shù)組的長(zhǎng)度，那么其大小不得小于初始化字符串的長(zhǎng)度。多余的元素位置被系統(tǒng)自動(dòng)初始化為0。 14【例】初始化字符數(shù)組： static char word=H,e,l,l,o,!; (靜態(tài)全局變量) 按照這個(gè)語(yǔ)句, 內(nèi)存中將實(shí)際保留六個(gè)字符的空間。如

13、下圖： 為了打印出數(shù)組 word 的內(nèi)容, 我們?cè)L問(wèn)數(shù)組的每一個(gè)元素, 且用 %c 格式顯示它?？梢允褂孟旅娴恼Z(yǔ)句: for(i=0;ii，或ji）。存儲(chǔ)方法：可以設(shè)計(jì)一個(gè)一維數(shù)組，按照以行為主序或以列為主序?qū)⑵鋲嚎s存儲(chǔ)到一維數(shù)組上，以節(jié)省空間。 對(duì)一個(gè)大小為n*n的方陣： 轉(zhuǎn)換成以行為主的一維數(shù)組： Dataij的位置=n+(n-i+1)*i/2+(j-i) （即為一維數(shù)組的Index ） 轉(zhuǎn)換成以列為主的一維數(shù)組： Dataij的位置=j*(j+1)/2+i （即為一維數(shù)組的Index ）26【例】設(shè)計(jì)一個(gè)將上三角數(shù)組轉(zhuǎn)換成以列為主序的一維數(shù)組的程序。 1）聲明所需數(shù)組空間，依據(jù)是欲存儲(chǔ)元素個(gè)數(shù)n*(1+n)/2。n為方陣的行或列數(shù)。 2）利用兩層循環(huán)（i、j控制）遍歷原三角數(shù)組中的每一筆數(shù)據(jù)，當(dāng)滿(mǎn)足條件ij時(shí),即當(dāng)元素的行數(shù)小于等于列數(shù)時(shí)，則將元素存儲(chǔ)于一維數(shù)組的j*(j+1)/2+i位置，即為其index。 程序主要語(yǔ)句：for(i=0