數(shù)據(jù)結(jié)構(gòu)-C 語言描述

數(shù)據(jù)結(jié)構(gòu)——C語言描數(shù)據(jù)結(jié)構(gòu)——C語言描 主 C91的綜述；第2章至第7章分別介紹了線性表、棧、隊(duì)列、串、多維數(shù)組廣義表、樹和圖等幾種基本的數(shù)據(jù)結(jié)構(gòu)；第8章和第9章分別介紹了查找圖書在版編目（CIP）數(shù)據(jù)結(jié)構(gòu)：C語言描述/王國鈞主編.—北京：科學(xué)出（面向21世紀(jì)高等院校計(jì)算機(jī)系列規(guī)劃教材ISBN7-03-016077-Ⅰ.數(shù)… Ⅱ.王… Ⅲ.數(shù)據(jù)結(jié)構(gòu)-高等學(xué)校-教材Ⅳ.TP311.12中國版本圖書館CIP數(shù)據(jù)核字（2005）第088632號(hào)責(zé)任編輯：呂建 趙衛(wèi)江／責(zé)任校對：劉彥責(zé)任印制：呂春珉／封面設(shè)計(jì)：飛天創(chuàng)出版北京東黃城根北街16雙青印刷廠印科學(xué)出版社發(fā)行各地新華書店經(jīng)*2005年8月第一 開本：787×10922006年8月第二次印 印張：16印數(shù)：3501－5 字?jǐn)?shù)：376定價(jià)：22.00（如有印裝質(zhì)量問題，我社負(fù)責(zé)調(diào)換<環(huán)偉銷售部電輯部電 本書共91章為概論2章至第4章分別介紹了線性表、棧、隊(duì)列和串幾種基本的數(shù)據(jù)結(jié)構(gòu)，它們都屬于線性結(jié)構(gòu)5章至第7章分別介紹了多維數(shù)組義表、樹和圖等非線性結(jié)構(gòu)；第8章和第9章分別介紹了查找和排序，它們都是數(shù)據(jù)處和詳盡的注釋，自始至終使用C語言來描述算法和數(shù)據(jù)結(jié)構(gòu)，各章的程序都在TurboC或VisualC++6.0中調(diào)試通過，以方便讀者在計(jì)算機(jī)上進(jìn)行實(shí)踐，有助于理解算法的實(shí)另外，本書也可供從事計(jì)算機(jī)應(yīng)用的工程技術(shù)人員參考，讀者只需掌握C語言編程為了方便教學(xué)，本書配有教學(xué)課件，可在科學(xué)出版社網(wǎng)站wcecm）載。由于編者水平有限，因此書中錯(cuò)誤難免，殷切希望廣大讀者批評指正若需與編者交換意見，或索要部分習(xí)題參考解答，請發(fā)函至下列E-mail信箱 20055 第1 數(shù)據(jù)和數(shù)據(jù)元 數(shù)據(jù)對象和數(shù)據(jù)類 數(shù)據(jù)結(jié) 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的重要 數(shù)據(jù)結(jié)構(gòu)的應(yīng)用舉 什么是算 算法的描述和設(shè) 算法分 第2 線性表的定 線性表的基本操 順序 順序表的基本操 一個(gè)完整的例子 單鏈表的基本概 單鏈表的基本操 一個(gè)完整的例子 循環(huán)鏈 雙向鏈 雙向循環(huán)鏈 靜態(tài)鏈 約瑟夫問 多項(xiàng)式加 電文加 數(shù)據(jù)結(jié)構(gòu)——C 第3 棧的定義與基本操 順序棧的存儲(chǔ)結(jié)構(gòu)和操作的實(shí) 鏈棧的存儲(chǔ)結(jié)構(gòu)和操作的實(shí) 數(shù)制轉(zhuǎn) 括號(hào)匹配問 子程序的調(diào) 利用一個(gè)棧逆置一個(gè)帶頭結(jié)點(diǎn)的單鏈 隊(duì)列的定義與基本操 鏈隊(duì)列的存儲(chǔ)結(jié)構(gòu)和操作的實(shí) 順序隊(duì)列的存儲(chǔ)結(jié)構(gòu)和操作的實(shí) 打印楊輝三角 迷宮問題：尋找一條從迷宮入口到出口的最短路 *第4章 串的定 串的基本操 串的定長順序存 串的堆存儲(chǔ)結(jié) 串的塊鏈存儲(chǔ)結(jié) 基本的模式匹配算 模式匹配的改進(jìn)算法——KMP算 第5 多維數(shù)組的定 數(shù)組的存儲(chǔ)結(jié) 目錄v目錄v特殊矩 稀疏矩 第6 樹的定 樹的一些基本慨 樹的基本操 二叉樹的定義和基本操 二叉樹的性 二叉樹的存儲(chǔ)結(jié) 二叉樹的遍 線索二叉 基于遍歷的應(yīng)用與線索二叉樹的應(yīng) 樹的存儲(chǔ)結(jié) 樹、森林和二叉樹之間的轉(zhuǎn) 樹和森林的遍 與哈夫曼樹相關(guān)的基本概 哈夫曼樹的應(yīng) 哈夫曼編碼算法的實(shí) 第7 圖的定 圖的相關(guān)術(shù) 鄰接矩陣表示 鄰接表表示 深度優(yōu)先搜索 數(shù)據(jù)結(jié)構(gòu)——C廣度優(yōu)先搜索 非連通圖的遍 生成樹的概 構(gòu)造最小生成樹的普里姆（Prim）算 構(gòu)造最小生成樹的克魯斯卡爾(Kruskal)算 從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路 每一對頂點(diǎn)之間的最短路 第8 查找表和查 查找表的數(shù)據(jù)結(jié)構(gòu)表 平均查找長度 順序查 二分查 分塊查 二叉排序 B- B-樹上的基本運(yùn) 散列表的概 散列函數(shù)的構(gòu)造方 處理沖突的方 散列表上的運(yùn) 第9 關(guān)鍵字與排 排序的穩(wěn)定 排序方法的分 排序算法性能評 不同存儲(chǔ)方式的排序過 目錄目錄直接插入排 希爾排 冒泡排 快速排 直接選擇排 堆排 多關(guān)鍵字的排 鏈?zhǔn)交鶖?shù)排 第1 本章要 什么是數(shù)據(jù)結(jié) 為什么要學(xué)習(xí)數(shù)據(jù)結(jié) 算法和算法分本章學(xué)習(xí)目 了解數(shù)據(jù)結(jié)構(gòu)的基本概念，理解常用術(shù) 掌握數(shù)據(jù)元素間的4類結(jié)構(gòu)關(guān) 掌握算法的定義及特性，掌握算法設(shè)計(jì)的要 初步掌握分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度的方 數(shù)據(jù)結(jié)構(gòu)——C語言描數(shù)據(jù)和數(shù)據(jù)元數(shù)據(jù)（da）是信息的載體，是對客觀事物的符號(hào)表示，它能夠被計(jì)算機(jī)識(shí)別、存數(shù)據(jù)的范疇。數(shù)據(jù)元素（dataelement）是數(shù)據(jù)的基本單位，通常在計(jì)算機(jī)程序中作為一個(gè)整體進(jìn)數(shù)據(jù)對象和數(shù)據(jù)類數(shù)據(jù)對象（dataobjec）是性質(zhì)相同的數(shù)據(jù)元素的集合，它是數(shù)據(jù)的一個(gè)子集。例如，整數(shù)數(shù)據(jù)對象是集合N={01，±2，±3，…；大寫字母字符數(shù)據(jù)對象是集合C=N1應(yīng)該是上述集NN1={012±xntxint是依賴于所使用的計(jì)算機(jī)和語言的最大整數(shù)。數(shù)據(jù)類型（datatype）是計(jì)算機(jī)程序中的數(shù)據(jù)對象以及定義在這個(gè)數(shù)據(jù)對象集合上的一組操作的總稱。例如，C語言中的整數(shù)類型是區(qū)間-maxint，maxint]上的整數(shù)，在提供的，如C語言中的整型、實(shí)型、字符型等；結(jié)構(gòu)數(shù)據(jù)類型是利用計(jì)算機(jī)語言提供的一種描述數(shù)據(jù)元素之間邏輯關(guān)系的機(jī)制由用戶自己定義而成的C語言中的數(shù)組類數(shù)據(jù)結(jié)數(shù)據(jù)結(jié)構(gòu)（datastructure）是指數(shù)據(jù)對象以及該數(shù)據(jù)對象集合中的數(shù)據(jù)元素之間的數(shù)據(jù)元素的組織形式一般包含下列內(nèi)容列4類（見圖1.1）。①集合：其中的數(shù)據(jù)元素之間除了“屬于同一個(gè)集合”的關(guān)系以外，別無其他②線性結(jié)構(gòu)：其中的數(shù)據(jù)元素之間存在一對一的關(guān)系第1 圖 4類基本邏輯結(jié)構(gòu)關(guān)③樹型結(jié)構(gòu)：其中的數(shù)據(jù)元素之間存在一對多的關(guān)系④圖狀結(jié)構(gòu)（或稱網(wǎng)狀結(jié)構(gòu)）：其中的數(shù)據(jù)元素之間存在多對多的關(guān)系由于數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它獨(dú)立于計(jì)算機(jī)，與數(shù)據(jù)的存儲(chǔ)C語言描述的算法來實(shí)現(xiàn)。例 學(xué)生成績表（見表1.1）是一個(gè)數(shù)據(jù)結(jié)構(gòu)學(xué)生成績學(xué)姓高等普通平均陳小馬麗林春王澄######張吉表1.1（或記錄），由學(xué)號(hào)、姓名、（或字段（又稱直接前驅(qū)（又稱直接后繼 數(shù)據(jù)結(jié)構(gòu)——C語言描“馬麗麗”所在結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)是“陳小潔”結(jié)點(diǎn)，其后繼結(jié)點(diǎn)是“林春英”結(jié)點(diǎn)，上述結(jié)點(diǎn)之間的關(guān)系構(gòu)成了這張學(xué)生成績表的邏輯結(jié)構(gòu)。其次，表1.1的存儲(chǔ)結(jié)構(gòu)是指用計(jì)算機(jī)語言如何表示各結(jié)點(diǎn)之間的這種關(guān)系，也就第三，在表1.1中，經(jīng)常要查看一些學(xué)在不會(huì)產(chǎn)生混淆的前提下，可以將數(shù)據(jù)的邏輯結(jié)構(gòu)簡稱為數(shù)據(jù)結(jié)構(gòu)。本書的第2到第4章介紹的都是線性結(jié)構(gòu)，第5章到第7章介紹的都是非線性結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可采用以下4種基本的存儲(chǔ)方法得到順序存儲(chǔ)方該方法主要應(yīng)用于線性的數(shù)據(jù)結(jié)構(gòu)，而非線性的數(shù)據(jù)結(jié)構(gòu)可以通過某種線性化的法來實(shí)現(xiàn)順序存儲(chǔ)鏈接存儲(chǔ)方索引存儲(chǔ)方稱為索引項(xiàng)。索引項(xiàng)的一般形式是：（關(guān)鍵字，地址），所謂關(guān)鍵字（ky）是指能夠組結(jié)點(diǎn)的起始存儲(chǔ)位置。散列存儲(chǔ)方該方法的基本思想是根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址上述4種基本的存儲(chǔ)方法，既可以單獨(dú)使用，也可以組合起來對數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲(chǔ)第1 需需要指出的是，不管怎樣定義數(shù)據(jù)結(jié)構(gòu)，都應(yīng)該將數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的重要數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對象以及它們之要想更有效地使用計(jì)算機(jī)，就必須學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的有關(guān)知識(shí)。約占用了90%以上的計(jì)算機(jī)時(shí)間。由于非數(shù)值計(jì)算問題所涉及的數(shù)據(jù)結(jié)構(gòu)更為復(fù)雜，數(shù)Nrh數(shù)據(jù)結(jié)構(gòu)的應(yīng)用舉例 電話號(hào)碼的查詢問題66數(shù)據(jù)結(jié)構(gòu)——C序，另外構(gòu)造一張姓氏索引表，存儲(chǔ)結(jié)構(gòu)如圖.2更為有效。在第8章中將進(jìn)一步討論查找策略。圖 電話號(hào)碼查詢問題的索引存例 n個(gè)城市之間鋪設(shè)光纜的問題假設(shè)需要在nnn1n數(shù)學(xué)模型是如圖1.（圖n中選取n1n“求圖的最小生成樹”的問題，見圖1.3（b），將在第7圖 圖及其最小生成樹示第1 什么是算算法（algorithm）是對特定問題求解步驟的一種描述，它是指令的有限序列，其每一條指令表示一個(gè)或多個(gè)操作。此外，一個(gè)算法還具有下列5個(gè)特性有窮性。一個(gè)算法必須在執(zhí)行有窮步之后結(jié)束，即算法必須在有限時(shí)間內(nèi)完成確定性。算法中每一步必須有確切的含義，不會(huì)產(chǎn)生二義性。并且，在任何條件下，算法只有唯一的一條執(zhí)行路徑，即對于相同的輸入只能得出相同的輸出?？尚行?。一個(gè)算法是可行的，即算法中的每一步都可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次得以實(shí)現(xiàn)。輸入。一個(gè)算法有零個(gè)或多個(gè)輸入，它們是算法開始時(shí)對算法給出的初始量輸出。一個(gè)算法有一個(gè)或多個(gè)輸出，它們是與輸入有特定關(guān)系的量算法的描述和設(shè)算法是一個(gè)十分古老的研究課題，然而計(jì)算機(jī)的出現(xiàn)為這個(gè)課題注入了青春和活助，許多過去靠人工無法計(jì)算的復(fù)雜問題都有了解決的希望。一個(gè)算法可以采用自然語言、數(shù)學(xué)語言或者約定的符號(hào)語言（如偽碼、框圖等）88數(shù)據(jù)結(jié)構(gòu)——C描述。為了方便讀者的閱讀和實(shí)踐，本書中的算法和數(shù)據(jù)結(jié)構(gòu)均使用C語言來描述。C語言遵照NICroC或Vsual++6.0中調(diào)試通過。對書中采用的一些預(yù)定義常量，簡要說明如下#defineTRUE1#defineFALSE#defineOK#defineERROR其他有關(guān)C語言的知識(shí)，請參考專門介紹C語言的書籍在例1.2中，我們介紹了電話號(hào)碼的查詢問題的兩種算法，那么如何來評價(jià)這些算正確性——算法應(yīng)當(dāng)滿足具體問題的需求健壯性——當(dāng)輸入數(shù)據(jù)非法時(shí)，算法也能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，而不會(huì)產(chǎn)生莫明其妙的輸出結(jié)果或出錯(cuò)信息，并中止程序的執(zhí)行?？勺x性——算法主要是為了方便人們的閱讀和交流，其次才是機(jī)器執(zhí)行執(zhí)行算法所耗費(fèi)的時(shí)間執(zhí)行算法所耗費(fèi)的存儲(chǔ)空間，其中主要考慮輔助存儲(chǔ)空間算法分的就是程序所用算法在運(yùn)行時(shí)所要花費(fèi)的時(shí)間代價(jià)和程序中使用的數(shù)據(jù)結(jié)構(gòu)所占有的空間代價(jià)。通常就稱為時(shí)間復(fù)雜度（時(shí)間代價(jià)）和空間復(fù)雜度（空間代價(jià)）。算法的時(shí)間復(fù)雜度分當(dāng)需要解決的問題的規(guī)模（以某種單位計(jì)算）由1增至n時(shí)，解決問題的算法所耗費(fèi)的時(shí)間也以某種單位由f(1)增至f(n)，這時(shí)就稱該算法的時(shí)間代價(jià)為f(n)。型的操作（或算法類型“原該語句重復(fù)執(zhí)行的次數(shù)。1.4有下列三個(gè)程序段（2）for(i=1;i<=n;i++){x=x+1;（3）for(j=1;j<=n;for(k=1;k<=n;k++){x=x+1;第1 它們含基本操作“x加1”的語句的頻度分別為1、n和n2例1.5對n個(gè)記錄進(jìn)行升序排序的問題，采用最簡單的選擇排序方法每次處理時(shí)，先從n個(gè)未排序的記錄中選出一個(gè)最小記錄，則第一次要經(jīng)過n-1次比較，才能選出最小記錄；第二次再從剩下的n-1個(gè)記錄中經(jīng)過n-2次比較，選出次小記錄……如此反復(fù)，直到只剩兩個(gè)記錄時(shí)，經(jīng)過1次比較就可以確定它們的大小。整個(gè)(n-1)+(n-2)+…+1=n×(n-在同一個(gè)算法處理兩個(gè)規(guī)模相同的問題，所花費(fèi)的時(shí)間和空間代價(jià)也不一定相同。（即對同樣規(guī)模的問題所花費(fèi)的人們通常采用大O表示法來描述算法分析的結(jié)果。如果存在正的常數(shù)M和n0，當(dāng)問題的規(guī)模n≥n0后，算法的時(shí)間量度T(n)≤Mf(n)那么就稱該算法的時(shí)間復(fù)雜度為O(f(n))。這種說法意味著：當(dāng)n充分大時(shí)，該算法的時(shí)間復(fù)雜度不大于f(n)的一個(gè)常對于例1.4的程序段（1）來說，其時(shí)間復(fù)雜度為O(1)，程序段（2）的時(shí)間復(fù)雜度為O(n)，程序段（3）的時(shí)間復(fù)雜度為O(n2)；而對于例1.5的選擇排序方法來說，其時(shí)間復(fù)雜度為O(n2)。算法另外還可能呈現(xiàn)的時(shí)間復(fù)雜度有：O(log2n)和O(2n)等。通常c<log2n<n<nlog2n<n2<n3<10其中，c是與n無關(guān)的任意常數(shù)。上述函數(shù)排序與數(shù)學(xué)中對無窮大的分級(jí)完全一致，因?yàn)榭紤]的也是n值變化過程中的趨勢，參見圖1.4。圖 常見函數(shù)曲線變化速度的比較數(shù)據(jù)結(jié)構(gòu)——C1.6要交換變量xy中的內(nèi)容，其程序段為temp=x;x=y;由于以上3條語句的頻度均為1，說明該程序段的執(zhí)行時(shí)間是一個(gè)與問題規(guī)模n無關(guān)的常數(shù)，因此，算法的時(shí)間復(fù)雜度為O(1)。1.7程序段如下for((i=1;i<=n;i++)for(j=1;j<=n;j++)for(k=1;k<=n;k++)在此程序段中，因?yàn)楹静僮鳌皒加1”的語句“x++;”的頻度是n3，所以該序段的時(shí)間復(fù)雜度為O(n3)算法的空間復(fù)雜度分與算法的時(shí)間復(fù)雜度類似，可以定義算法的空間復(fù)雜度如下：如果存在正的常數(shù)M和n0，當(dāng)問題的規(guī)模n≥n0后，算法的空間量度S(n)M·f(n)那么就稱該算法的空間復(fù)雜度為O(f(n))。數(shù)據(jù)的表示形式有關(guān)（見第8章1.8求例1.5中選擇排序方法的空間復(fù)雜度一個(gè)中間變量（temp）的存儲(chǔ)空間，這是與問題規(guī)模n無關(guān)的常數(shù)，因此，選擇排序方法的空間復(fù)雜度為O(1)。夠區(qū)分算法與程序的異同，了解怎樣的算法才是一個(gè)“好”的算法，并學(xué)會(huì)利用時(shí)間本章小結(jié)的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)的運(yùn)算。討論了數(shù)據(jù)邏輯結(jié)構(gòu)的4第1 基本結(jié)構(gòu)關(guān)系，以及數(shù)據(jù)存儲(chǔ)的4種基本方法。讀者學(xué)習(xí)這些內(nèi)容后，希望能對數(shù)據(jù)結(jié)算法和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)，不可分割。本章介紹了算法的定義和5個(gè)特性，討論了本書使用C語言來描述算法和數(shù)據(jù)結(jié)構(gòu)，以方便讀者在計(jì)算機(jī)上進(jìn)行實(shí)踐活動(dòng) 一、填空數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)元素之間的邏輯關(guān)系，通常有下列4類 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器里的表示，主要有4種基本存儲(chǔ)方法 二、選擇一個(gè)算法必須在執(zhí)行有窮步之后結(jié)束，這是算法的 ）正確 B.有窮C.確定 D.可行也就是說對于每步需要執(zhí)行的動(dòng)作必須嚴(yán)格、清楚地給出規(guī)定，這是算法的（ ）。正確 B.有窮C.確定 D.可行序列”，其中的每一步都是我們力所能及的一個(gè)動(dòng)作，這是算法的（ ）。正確 B.有窮C.確定 D.可行三、簡答算法與程序有何異同什么是數(shù)據(jù)結(jié)構(gòu)？試舉一個(gè)簡單的例子說明什么是數(shù)據(jù)的邏輯結(jié)構(gòu)？什么是數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)什么是算法？算法有哪些特性四、算法分析將下列復(fù)雜度由小到大重新排序：2n、n!、n2、10000、log2n、nlog2n用大O表示法描述下列復(fù)雜度 （2）6（3）3n4+n （4）nlog2n+n數(shù)據(jù)結(jié)構(gòu)——C設(shè)n為正整數(shù)，請用大O表示法描述下列程序段的時(shí)間復(fù)雜度（1）i=1;k=0; （2）i=0;k=0; {k=k+10*i; （3）i=1;j=0; {if(i>j) else}（5）for((i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) {if(x>100){x-=10;y--;}x+=c;(c為常數(shù)) elsex++;}第2 線性本章要令線性表的基本概念令線性表的順序存儲(chǔ)令線性表的鏈?zhǔn)酱媪罹€性表兩種不同存儲(chǔ)結(jié)構(gòu)的比令線性表的應(yīng)本章學(xué)習(xí)目 掌握單鏈表上的基本運(yùn) 掌握循環(huán)鏈表、雙向鏈表和靜態(tài)鏈表的概 學(xué)會(huì)利用線性表來解決問 數(shù)據(jù)結(jié)構(gòu)——C線性結(jié)構(gòu)是指結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系。線性結(jié)構(gòu)的基本特征是①有而且只有一個(gè)“第一元素”②有而且只有一個(gè)“最后元素”③除第一元素之外，其他元素都有唯一的直接前驅(qū)④除最后元素之外，其他元素都有唯一的直接后繼線性表是一種常用的簡單的數(shù)據(jù)結(jié)構(gòu)，它屬于線性結(jié)構(gòu)的范疇例2.1 26個(gè)大寫英文字母表（A,B,C,…,Z）就是一個(gè)線性表，表中的每一個(gè)字母例2.2 第1章例1.1中的學(xué)生成績表（表1.1），也是一個(gè)線性表，其中每個(gè)學(xué)生綜上所述，線性表可以描述如下線性表的定(a1,a2,…,ai-1,ai,ai+1,…,其中，數(shù)據(jù)元素的個(gè)數(shù)n稱為線性表的長度。當(dāng)n＝0時(shí)稱為空表始結(jié)點(diǎn)（第一元素）a1，它沒有直接前驅(qū)，只有一個(gè)直接后繼a2；有而且只有一個(gè)終端結(jié)點(diǎn)（最后元素）an，它沒有直接后繼，只有一個(gè)直接前驅(qū)an-1；而除了a1和an外，其他的每一個(gè)結(jié)點(diǎn)ai（2≤i≤n-1）都有而且只有一個(gè)直接前驅(qū)ai-1和一個(gè)直接后繼ai+1。例2.3例2.1中介紹的26個(gè)大寫英文字母表（A,B,C,…,Z）的表長是26，在該表中，起始結(jié)點(diǎn)A沒有直接前驅(qū)，A的唯一直接后繼是B；終端結(jié)點(diǎn)Z沒有直接后繼，Z的唯一直接前驅(qū)是Y；而對于B,C,D,…,Y中的任意一個(gè)字母，都有一個(gè)唯一的直接前線性表的基本操設(shè)線性表L=(a1,a2,…,an)，則可以定義以下基本操作：1）InitList(L)：初始化操作，置L為空線性表。ClearList(L)：清除線性表的內(nèi)容，將L置為空表ListLength(L)：求表長Ins(L，i，Item)：插入數(shù)據(jù)。把Item插入到表L的第i個(gè)位置，表長加1；如果i<1或i>ListLength(L)+1，則插入不成功。Del(L，i)：刪除數(shù)據(jù)。如果1≤i≤ListLength(L)，則刪除第i個(gè)數(shù)據(jù)，線性表的長度減1，返回TRUE；否則，刪除不成功，返回FALSE第2 線性 GetNode(L，i)：獲取表L中第i(1≤i≤ListLength)個(gè)結(jié)點(diǎn)的值。7）Loc(L，Item)：定位(按值查找)。如果表L中存在一個(gè)值為Item的結(jié)點(diǎn)，則返該結(jié)點(diǎn)的位置；若表L中存在多個(gè)值為Item的結(jié)點(diǎn)，則返回第一次找到的結(jié)點(diǎn)位置；若表L中不存在值為Item的結(jié)點(diǎn)，則返回0。8）GetNext(L，Item，p)：獲取后繼結(jié)點(diǎn)。首先找到Item所在的位置，然后把的后繼結(jié)點(diǎn)的值賦給p；若成功，則返回TRUE；否則，返回FALSE。9）GetPrior(L，Item，p)：獲取前驅(qū)結(jié)點(diǎn)。首先找到Item所在的位置，然后把Item順序C組來描述順序表的。例2.4一個(gè)順序存儲(chǔ)結(jié)構(gòu)的線性表（順序表）的示例typedef{charname[20];charno[10];floatscore;STUDENT則s就是一個(gè)以STUDENT類型為數(shù)據(jù)元素的線性表假設(shè)線性表L的每個(gè)元素需占用m個(gè)存儲(chǔ)單元，并以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置，則線性表中第i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai+1)和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai)之間滿足如下關(guān)系： 線性表L的第i個(gè)元素的存儲(chǔ)位置和第一個(gè)元素的存儲(chǔ)位置的關(guān)系為LOC(ai)=LOC(a1)+(i-1) 其中LOC(a1)是線性表的第一個(gè)數(shù)據(jù)元素a1的存儲(chǔ)位置，通常稱為線性表的起始位順序表的特點(diǎn)是以元素在計(jì)算機(jī)內(nèi)部存儲(chǔ)的物理位置相鄰來表示線性表中數(shù)據(jù)元2.2地址，就能計(jì)算出該數(shù)據(jù)元素的直接前驅(qū)和直接后繼的地址，計(jì)算公式見式（2.1）。 數(shù)據(jù)結(jié)構(gòu)——C例2.5 在例2.4的線性表s中，如果設(shè)第一個(gè)數(shù)據(jù)元素的地址為b，則可以得出如圖2.1所示的存儲(chǔ)結(jié)構(gòu)圖。注意：s中每一個(gè)數(shù)據(jù)元素所占的存儲(chǔ)單元為20+10+4=34圖 線性表s的順序存儲(chǔ)結(jié)構(gòu)順序表的基本操現(xiàn)在利用C語言來描述一個(gè)順序表，由于表的長度通常是可變的，因此需要定義一typedefintdatatype; /*定義數(shù)據(jù)元素的類型，這里假設(shè)為int*/#definemaxsize1024 /*線性表的最大長度，這里假設(shè)為1024*/typedefstruct datatypeint /*表長其中，數(shù)據(jù)域data是存放線性表結(jié)點(diǎn)的一個(gè)數(shù)組，數(shù)組下標(biāo)范圍為0～maxsize-1。length是線性表的長度。順序表的初始算法 構(gòu)造一個(gè)空的順序表voidInitList(sequenlist*L/*構(gòu)造一個(gè)空的順序表，只需要把表長度置為0{/*L是sequenlist類型的指針變量L /*0}存取第i個(gè)數(shù)據(jù)元素，只需要知道線性表的基地址就可以了。需要注意的是，在C語言第第2 線性 其中，m是數(shù)據(jù)元素所占的單元數(shù)目。清除線性表的內(nèi)長置為0。算法 清除一個(gè)已經(jīng)存在的線性表的內(nèi)容voidClearList(sequenlist{L-}本算法時(shí)間復(fù)雜度為O(1)定位(按值查找則返回。算法 定位（按值查找）intLoc(sequenlistL，datatype{intj=L.length;/*取出線性表的長度*/ /*空表*/returnFALSE;{if(L.data[i]==Item)/*找到Item*/returni; /*返回找到的位置*/}printf(″找不到該return0;/*沒有找到0}本算法中，可能找到Item，這時(shí)平均比較次數(shù)為O(n/2)，其中，n是線性表的長度；也可能找不到Item，這時(shí)算法的比較次數(shù)為O(n)。因此，本算法的時(shí)間復(fù)雜度為O(n)插入數(shù)要在線性表中第i個(gè)位置插入一個(gè)數(shù)據(jù)元素Item，需要考慮以下因素i是否在1和L.length之間，如果是，則先將原來的第i個(gè)位置及以后的數(shù)據(jù)元素向后移動(dòng)一個(gè)位置，然后把Item插入到第i個(gè)位置，再將線性表長度加1，返回TRUE；如果i不在1和L.length之間，則說明插入位置不合適，返回FALSE，如圖2.2所示。 數(shù)據(jù)結(jié)構(gòu)——C插入…ai……插入…ai……圖 在順序表中插入結(jié)點(diǎn)的示意算法 插入數(shù)據(jù)intIns(sequenlist*L，inti，datatype{/*在順序表*L的第i個(gè)位置插入新結(jié)點(diǎn)*/intj;if(i<1||i>L-returnFALSE； /*位置不合適*/L->data[j]=L->data[j-1];/*結(jié)點(diǎn)后移L->data[i- /*1*/returnTRUE;}數(shù)為(n/2)，其中，n是線性表的長度。因此，本算法的時(shí)間復(fù)雜度為O(n)。注意:本算法最直觀的思考方法是從前向后移動(dòng)數(shù)據(jù)，也就是用語句for(j=i;j<=L-L->data[j+1]=L-這個(gè)算法是不正確的，因?yàn)榍懊娴闹禃?huì)把后面的值覆蓋刪除數(shù)刪除數(shù)據(jù)和插入數(shù)據(jù)很相似，都要求判斷i的值是否合適，如果位置合適，則把后面的數(shù)據(jù)向前移動(dòng)，刪除成功，表的長度減1，返回TRUE，否則，返回FALSE。如所示圖 在順序表中刪除結(jié)點(diǎn)的示意第第2 線性算法 刪除數(shù)據(jù)intDel(sequenlist*L，int{/*刪除順序表*L中的第i個(gè)結(jié)點(diǎn)*/intj;if(i<1||i>L->length)/*位置不合適returnFALSE；L->data[j]=L->data[j+1];/*結(jié)點(diǎn)前移 /*表長減1*/returnTRUE；}一個(gè)完整的例子例6 編制C程序，利用順序存儲(chǔ)方式來實(shí)現(xiàn)下列功能：根據(jù)鍵盤輸入數(shù)據(jù)建立一個(gè)線性表并輸出該線性表然后根據(jù)屏幕菜單的選擇可以進(jìn)行數(shù)據(jù)的插入或刪除并在插入或刪除數(shù)據(jù)后再輸出線性表最后在屏幕菜單中選擇Q或q的運(yùn)行。程序如下：#include"stdio.h" #include"malloc.h"#definemaxsize1024typedefchardatatype;typedefstruct datatypedata[maxsize];intlast;/*在第i個(gè)元素前插入元素x（注意：元素從0始計(jì)數(shù)）*/intinsert(sequenlist*L,datatypex,inti) intif(L->last==maxsize- /*如果原線性表已滿{printf("overflow");return0;}elseif(i<0)||(i>L /*如果輸入的i值超出范圍{printf("error,pleaseinputtheright'i'");return0;}{for(j=L->last;j>=i;j--)/*從第i個(gè)元素起,