本書主要介紹了線性表、棧和隊列、樹、圖等數(shù)據(jù)結(jié)構(gòu)及相關操作，同時還介紹了查找、排序等算法。在介紹基本知識的基礎上與實際應用相結(jié)合，加深學生對知識的理解。為了便于學生理解所學知識，本書還增加了對C語言中結(jié)構(gòu)體知識的簡單回顧。每章以實際例子引出知識點，每章最后綜合應用全章知識解決一個實際問題。書中全部算法用C語言實現(xiàn)，且全都可編譯執(zhí)行。每章后面附有相關習題，配套實驗指導中附有參考答案及解析，便于學生自己練習相關知識點。
“數(shù)據(jù)結(jié)構(gòu)”課程是高等學校計算機及相關專業(yè)的一門重要的專業(yè)基礎課程，熟練掌握這門課程中介紹的內(nèi)容是學習計算機其他相關課程的必備條件。
“數(shù)據(jù)結(jié)構(gòu)”課程主要研究計算機處理對象的邏輯結(jié)構(gòu)、在計算機中的表示形式及各種基本操作的實現(xiàn)算法。其主要解決系統(tǒng)開發(fā)過程中設計階段的問題，包括對實際問題建模，分析數(shù)據(jù)的邏輯結(jié)構(gòu)及基本運算，將數(shù)據(jù)在計算機中存儲并實現(xiàn)基本運算等。
本書是河北省高等學校人文社會科學研究項目“基于多學科的應用型‘數(shù)據(jù)結(jié)構(gòu)’課程體系建設綜合研究”項目成果，旨在培養(yǎng)學生的應用能力。本書是在深入研究國內(nèi)外數(shù)據(jù)結(jié)構(gòu)優(yōu)秀教材和大量文獻的基礎上，結(jié)合各位編者多年的教學經(jīng)驗和科研成果編寫而成。本書注重理論與實踐相結(jié)合，每章導讀中利用生活實例引出相關的知識點，在每種數(shù)據(jù)結(jié)構(gòu)介紹完之后都會舉一個應用案例，讀者在學習知識點的基礎上能夠與實際相結(jié)合，達到學有所用的目的。
本書中所有算法都采用C語言函數(shù)的形式描述，同時對這些函數(shù)的關鍵語句都進行了詳細注釋，并已在Visual C++6.0運行環(huán)境下調(diào)試運行通過，便于讀者理解算法，并方便讀者對基本運算進行驗證，從而在此基礎上學會應用。
本書共分8章，系統(tǒng)介紹了線性表、棧和隊列、串、樹、圖等基本數(shù)據(jù)結(jié)構(gòu)及應用，并介紹了查找和排序的各種算法及應用。本書課后習題部分提供了各種類型的練習題，供讀者練習，加深對各章知識的理解，并在配套教材《數(shù)據(jù)結(jié)構(gòu)實驗指導與習題解析》中提供了習題答案及解析。
本書由燕京理工學院孫麗云和馬睿擔任主編，由燕京理工學院邵蘭潔和李珊、武漢工程科技學院劉艷擔任副主編。其中，馬睿編寫了第1章、第6章和第7章的內(nèi)容；孫麗云編寫了第2章、第3章的內(nèi)容，并完成了統(tǒng)稿、審稿工作；李珊編寫了第4章的內(nèi)容；邵蘭潔編寫了第5章的內(nèi)容；孫麗云和劉艷編寫了第8章的內(nèi)容。課題組成員劉淑艷、劉佩賢、王慧、牛玉玲等老師提供了大量編寫素材。
本書在編寫過程中得到了燕京理工學院信息科學與技術學院各位領導的指導和幫助，同時得到了華中科技大學出版社的大力支持，在此一并表示感謝。
為了方便教學，本書還配有電子課件等教學資源包，任課教師和學生可以登錄“我們愛讀書”網(wǎng)（www.ibook4us.com）免費注冊并瀏覽，或者發(fā)郵件至hustpeiit@163.com免費索取。
由于作者水平有限，書中難免有錯誤及疏漏之處，懇請同行專家及讀者指正，以便進一步提高本書質(zhì)量。作者電子郵箱：57025032@qq.com。
第2章線性表
第 2 章 線性表
線性表是最簡單、最基本,也是最常用的數(shù)據(jù)結(jié)構(gòu)。 幼兒園小朋友人數(shù)眾多,有的幼兒園為便于管理,會給每個班級排一個固定順序的隊伍,如班級里有30個小朋友,會按照順序給小朋友排學號1,2,3……30,不管是平時放學排隊還是外出參加活動,小朋友都按照學號排隊,讓每個小朋友記住自己前后的小朋友,若發(fā)現(xiàn)前后小朋友不在馬上報告老師,而老師只要記住第1個小朋友就可以了。班級中,只有1號前面沒有小朋友,只有30號后面沒有小朋友,其他每個學號都是前面只有一個小朋友,后面只有一個小朋友,這就是一個典型的線性表。 本章我們就要來學習線性表。 2.1線性表的邏輯結(jié)構(gòu) 2.1.1線性表的定義 線性表L是n(n≥0)個具有相同屬性的數(shù)據(jù)元素a1,a2,a3,…,an組成的有限序列。其中，序列中元素的個數(shù)n稱為線性表的長度。 當n=0時稱為空表,即不含有任何元素。 常常將非空的線性表L(n>0)記為：L=(a1,a2,…，ai-1,ai,ai+1,…，an)。 其中，ai-1為ai的直接前驅(qū),ai＋1為ai的直接后繼。a1為表頭元素,an為表尾元素。線性表有以下特點。 (1) 在非空的線性表中,存在唯一的一個被稱為“第一個”的數(shù)據(jù)元素,又稱為表頭元素；存在唯一的一個被稱為“最后一個”的元素,又稱為表尾元素。 (2) 線性表中數(shù)據(jù)的位置先后是有序的。除表頭元素外,線性表中的每一個元素有且僅有一個前驅(qū)；除表尾元素外,線性表中的每一個元素有且僅有一個后繼。表頭元素只有一個后繼而沒有前驅(qū),表尾元素只有一個前驅(qū)而沒有后繼。 (3) 線性表中的數(shù)據(jù)的類型是相同的。表的長度n的取值是有限數(shù),最小為0。 在日常生活中,線性表的例子很多。例如，26個英文字母組成的字母表(A,B,C,…,Y,Z)就是一個典型的線性表,該表長度是26,每個字母是表中的一個元素。表21所示的學生信息表也構(gòu)成了一個線性表。 表21學生信息表 學號姓名班級年齡宿舍 160210001崔雨計科160118星苑305 160210002丁潔計科160119星苑305 160210003樊辰計科160118松苑207 160210004馮波計科160119松苑207 160210005郭力計科160120松苑207 160210006胡志計科160120松苑207 該線性表表長為6,表中每個學生的信息為一個“數(shù)據(jù)元素”,包括學號、姓名、班級、年齡和宿舍等“數(shù)據(jù)項”信息。
2.1.2線性表的基本運算 數(shù)據(jù)結(jié)構(gòu)的基本運算是定義在邏輯結(jié)構(gòu)層次上的,而這些運算的具體實現(xiàn)是需要建立在存儲結(jié)構(gòu)上的,因此下面定義的線性表的基本運算作為邏輯結(jié)構(gòu)的一部分,其具體實現(xiàn)卻要在線性表的存儲結(jié)構(gòu)確定之后才能夠完成。 線性表的基本操作有以下幾項。 (1) 線性表L的初始化，其語句如下。 InitList(L) 構(gòu)造一個空的線性表L，即表的初始化。 (2) 創(chuàng)建線性表L，其語句如下。 CreatList(L) (3) 求線性表L的長度，其語句如下。 GetLength(L) 求表中結(jié)點的個數(shù),即求表的長度。 (4) 按序號取線性表L中的元素，其語句如下。 GetNode(L,i) 取線性表L中的第i個元素,這里1≤i≤Length(L)。 (5) 在線性表L中查找元素e，其語句如下。 LocateList(L,e) 在L中查找值為e 的結(jié)點,并返回該結(jié)點在L中的位置。若L中有多個結(jié)點的值和e 相同,則返回首次找到的結(jié)點位置；若L中沒有結(jié)點的值為e,則返回一個特殊值(如-1),表示查找失敗。 (6) 在線性表L中插入新元素，其語句如下。 InsertList(L,i,e) 在線性表L的第i個位置上插入一個值為x 的新結(jié)點,使得原編號為i,i+1,…,n的結(jié)點變?yōu)榫幪枮閕+1,i+2,…,n+1的結(jié)點。這里1≤i≤n+1,而n是原表L的長度。插入后,表L的長度加1。 (7) 在線性表L中刪除元素，其語句如下。 DeleteList(L,i) 刪除線性表L的第i個結(jié)點,使得原編號為i+1,i+2,…,n的結(jié)點變成編號為i,i+1,…,n-1的結(jié)點。這里1≤i≤n (n是原表L的長度),刪除后表L的長度減1,為n-1。 (8) 將線性表中元素輸出，其語句如下。 PrintList(L) 將線性表L中的元素打印輸出,若對線性表進行了一些操作,如插入、刪除等,需要將其打印輸出查看操作結(jié)果。
2.2線性表的順序存儲及運算實現(xiàn) 線性表有兩種基本的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。
2.2.1線性表的順序存儲結(jié)構(gòu) 線性表的順序存儲是最簡單、最直接的一種存儲方式,即把線性表的結(jié)點按邏輯順序依次存放在一組地址連續(xù)的存儲單元里。這樣的存儲方式使線性表邏輯上相鄰的元素存儲在物理地址相鄰的存儲單元里,即以計算機內(nèi)“物理位置相鄰”來反映數(shù)據(jù)元素之間邏輯上的相鄰關系,采用這種存儲方式的線性表又稱為順序表。 順序表有以下特征。 (1) 線性表的所有元素所占的空間是連續(xù)的。 (2) 線性表中各個數(shù)據(jù)元素在存儲空間中是按照邏輯順序依次存放的。 由于線性表中的所有數(shù)據(jù)元素都是同一數(shù)據(jù)類型,所以每個元素在存儲器中占用的空間(字節(jié)數(shù))相同。只要知道了第1個數(shù)據(jù)元素a1的存儲地址和它所占有的存儲單元個數(shù),即可求得第i個數(shù)據(jù)元素ai的地址。假定第一個元素a1的地址為LOC(a1),每個數(shù)據(jù)元素占k個字節(jié),則第i個數(shù)據(jù)元素ai的地址是： LOC(ai)=LOC(a1)+(i－1)×k(1≤i≤n) 例如：第2個數(shù)據(jù)元素a3的地址是LOC(a2)=LOC(a1)+k 第3個數(shù)據(jù)元素a3的地址是LOC(a3)=LOC(a1)+2k …… 第i個數(shù)據(jù)元素ai的地址是LOC(ai)=LOC(a1)+(i－1)×k 順序表的順序存儲結(jié)構(gòu)如圖21所示。 圖21順序表的順序存儲示意圖 由于線性表中的數(shù)據(jù)元素都是按照邏輯關系進行存儲的，所以只要確定了順序表的起始位置，線性表中的任一數(shù)據(jù)元素都可以隨機存取，因此線性表的順序存儲結(jié)構(gòu)是一種“隨機存取”的存儲結(jié)構(gòu)。 順序表在具體實現(xiàn)時,一般用高級語言中的數(shù)組來對應連續(xù)的存儲空間。設最多可存儲MaxSize個元素,在C語言中可用數(shù)組data\[MaxSize\]來存儲數(shù)據(jù)元素,為保存線性表的長度需定義一個整型變量length。線性表的第l,2,…,n個元素分別存放在此數(shù)組下標為0,1,…,length-1數(shù)組元素中,如圖21所示。 在C語言中,可用下述類型定義來描述線性表。 #defineMaxSize100/*順序表的容量*/ typedefintDataType;/*在應用中,將實際數(shù)據(jù)類型定義成DataType */ typedefstruct{ DataTypedata\[MaxSize\];/*定義存儲表元素的數(shù)組*/ intlength;/*順序表的實際長度*/ }SeqList; /*順序表數(shù)據(jù)類型說明*/ SeqList *L;/*定義一個順序表類型的指針變量L*/ 在使用一維數(shù)組存放線性表時,通常定義的數(shù)組的空間要比實際表稍長大一些,以便對線性表進行各種運算,特別是對線性表的插入運算。一般情況下,應該盡可能考慮到使用的線性表可能達到的最大長度,如果定義的存儲空間過小,則在線性表動態(tài)增長時可能會出現(xiàn)存儲空間不夠而無法插入新的元素的情況；如果存儲空間過大,而實際又沒有用到那么大的存儲空間,則會造成存儲空間的浪費。在實際應用中,可以根據(jù)線性表動態(tài)變化過程中的一般規(guī)模來決定開辟存儲空間量,設置足夠的數(shù)組長度,以備擴展。
2.2.2順序表上基本運算的實現(xiàn)
1. 順序表L的初始化 順序表的初始化即構(gòu)造一個空表,順序表是否為空取決于其數(shù)據(jù)元素個數(shù)是否為0,因此,只要將表L的長度設置為0即可構(gòu)造出一個空表。 算法21順序表的初始化。 void InitList(SeqList *L)/*順序表的初始化即將表的長度置為0*/ { L-＞length=0; } 該算法的時間復雜度為O(1)。
2. 創(chuàng)建一個順序表L 算法22創(chuàng)建一個元素為整型數(shù)的順序表,元素不包括0,遇到0時表示輸入結(jié)束。順序表長度由用戶輸入的數(shù)據(jù)來決定。 void CreatList(SeqList *L) { int k=0;/*計數(shù)*/ DataType x; scanf("%d",&x); while(x!=0)/*依次從鍵盤輸入順序表元素,遇到0結(jié)束。*/ { L->data\[k\]=x; k++; scanf("%d",&x); } L->length=k; } 該算法的時間復雜度為O(n),其中n為該順序表中元素個數(shù)的規(guī)模。 思考： 若順序表長度為固定值,如何創(chuàng)建順序表？
書單推薦
