數(shù)據(jù)結(jié)構(gòu)課件15

學(xué)時(shí)數(shù)：72學(xué)時(shí)（16學(xué)時(shí)實(shí)驗(yàn)）+課程設(shè)計(jì)（一周）教材：《數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版》嚴(yán)蔚敏、吳偉民-----清華大學(xué)出版社（配題集）課程介紹教學(xué)參考書：[1]殷人昆等，數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++描述），清華大學(xué)出版社[2]《數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言篇》習(xí)題與解析，李春葆，清華大學(xué)出版社[3]丁寶康等，數(shù)據(jù)結(jié)構(gòu)自學(xué)考試指導(dǎo)，清華大學(xué)出版社答疑地點(diǎn)：綜合樓B321（luying@）數(shù)據(jù)結(jié)構(gòu)學(xué)時(shí)數(shù)：72學(xué)時(shí)（16學(xué)時(shí)實(shí)驗(yàn)）+課程設(shè)計(jì)（一周）課程介紹教數(shù)據(jù)結(jié)構(gòu)第一章 緒論第二章 線性表第三章 棧和隊(duì)列第四章串第五章數(shù)組和廣義表第六章樹和二叉樹第七章圖第八章查找第九章內(nèi)部排序數(shù)據(jù)結(jié)構(gòu)第一章 緒論任務(wù)：編程實(shí)現(xiàn)求解圓的面積

main(){floatr,s;scanf(“%f”,&r);s=3.14×r×r;printf(“%f”,s);}數(shù)據(jù)結(jié)構(gòu)任務(wù)：編程實(shí)現(xiàn)求解圓的面積數(shù)據(jù)結(jié)構(gòu)main(){floatr,s;

printf(“Calculatingtheareaofacircular…”);printf(“\npleaseinputtheradius:”);scanf(“%f”,&r);s=3.14×r×r;printf(“area=%f”,s);}數(shù)據(jù)結(jié)構(gòu)main()數(shù)據(jù)結(jié)構(gòu)main(){floatr,s;

printf(“Calculatingtheareaofacircular…”);printf(“\npleaseinputtheradius:”);scanf(“%f”,&r);

if(r<=0)exit(0);else{s=3.14×r×r;printf(“area=%f”,s);}}數(shù)據(jù)結(jié)構(gòu)main()數(shù)據(jù)結(jié)構(gòu)

voidmenu(){printf(“Calculatingtheareaofacircular…”);printf(“\n\n\t1.calculating…”);printf(“\n\t2.exit…”);

printf(“\n\n\tpleaseinputyourchoice(1or2):”);

}

main(){floatr,s;

intchoice;menu();scanf(“%d”,&choice);while(choice!=2){printf(“\npleaseinputtheradius:”);scanf(“%f”,&r);

while(r>0){s=3.14×r×r;printf(“area=%f”,s);}

menu();

scanf(“%d”,&choice);

}}數(shù)據(jù)結(jié)構(gòu)程序=數(shù)據(jù)結(jié)構(gòu)+算法voidmenu()數(shù)據(jù)結(jié)構(gòu)程序=數(shù)據(jù)結(jié)構(gòu)第一章 緒論§1.1什么是數(shù)據(jù)結(jié)構(gòu)一、數(shù)據(jù)結(jié)構(gòu)課程的研究?jī)?nèi)容

用計(jì)算機(jī)解決一個(gè)具體問(wèn)題：抽象適當(dāng)?shù)臄?shù)學(xué)模型設(shè)計(jì)解決該數(shù)學(xué)模型的算法編寫程序、測(cè)試、調(diào)整——得到最終答案

?電話號(hào)碼查詢問(wèn)題

數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算的操作對(duì)象以及它們之間的關(guān)系和操作等等的學(xué)科?！獙?duì)相關(guān)的各種信息如何表示、組織和存儲(chǔ)？第一章 緒論§1.1什么是數(shù)據(jù)結(jié)構(gòu)—對(duì)相關(guān)的各種信息如何第一章 緒論二、發(fā)展：

1968年，《數(shù)據(jù)結(jié)構(gòu)》作為一門獨(dú)立的課程在國(guó)外設(shè)立。數(shù)據(jù)結(jié)構(gòu)——圖論、表、樹、網(wǎng)絡(luò)、集合代數(shù)論、格、關(guān)系、文件管理。

程序=數(shù)據(jù)結(jié)構(gòu)+算法

《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)科學(xué)中一門綜合性的專業(yè)基礎(chǔ)課，是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程。不僅是一般程序設(shè)計(jì)的基礎(chǔ)，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)及其它系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。第一章 緒論二、發(fā)展：第一章 緒論§1.2基本概念和術(shù)語(yǔ)1、數(shù)據(jù)（Data）

是對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。它是計(jì)算機(jī)程序加工的“原料”，如：整數(shù)、實(shí)數(shù)、字符串、圖像、聲音等。2、數(shù)據(jù)元素（DataElement）

是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。如：學(xué)校學(xué)籍管理系統(tǒng)中的學(xué)生信息就是一個(gè)數(shù)據(jù)元素。第一章 緒論§1.2基本概念和術(shù)語(yǔ)第一章 緒論3、數(shù)據(jù)項(xiàng)（DataItem）

一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成，是數(shù)據(jù)的不可分割的最小單位。如：書目信息中的書名、作者名等即為一個(gè)數(shù)據(jù)項(xiàng)；學(xué)生信息中的學(xué)號(hào)。4、數(shù)據(jù)對(duì)象（DataObject）

是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。如：整數(shù)數(shù)據(jù)對(duì)象集合N={0,+/-1,+/-2,……}；如：學(xué)籍管理系統(tǒng)中的學(xué)生信息數(shù)據(jù)庫(kù)文件。第一章 緒論3、數(shù)據(jù)項(xiàng)（DataItem）第一章 緒論5、數(shù)據(jù)結(jié)構(gòu)（DataStructure）

是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

結(jié)構(gòu)數(shù)據(jù)元素不是孤立存在的，它們之間存在某種關(guān)系，這種數(shù)據(jù)元素相互之間的關(guān)系稱為結(jié)構(gòu)。

Data_Structure=(D,S)元素有限集關(guān)系有限集例1：用數(shù)據(jù)結(jié)構(gòu)表示一周中的七天。Data_Structure=(D,S),其中，D={}S={}

Mon,Tue,Wen,Thu,Fri,Sat,Sun<Mon,Tue>,<Tue,Wen>,<Wen,Thu>…第一章 緒論5、數(shù)據(jù)結(jié)構(gòu)（DataStructure）第一章 緒論6、邏輯結(jié)構(gòu)

結(jié)構(gòu)定義中的“關(guān)系”描述的是數(shù)據(jù)元素之間的邏輯關(guān)系，因此又稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。4類基本結(jié)構(gòu)：

集合（沙堆）

線性結(jié)構(gòu)（一對(duì)一，隊(duì)列）

樹形結(jié)構(gòu)（一對(duì)多，家族譜）圖狀結(jié)構(gòu)（多對(duì)多，交通圖）

第一章 緒論6、邏輯結(jié)構(gòu)第一章 緒論7、物理結(jié)構(gòu)/存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示/映象稱為數(shù)據(jù)的物理結(jié)構(gòu)。包括數(shù)據(jù)元素的表示和關(guān)系的表示。位、元素（結(jié)點(diǎn)）、數(shù)據(jù)域。兩種具體存儲(chǔ)結(jié)構(gòu)：(z1=3.0+2.3i)第一章 緒論7、物理結(jié)構(gòu)/存儲(chǔ)結(jié)構(gòu)第一章 緒論順序映象----順序存儲(chǔ)結(jié)構(gòu)特點(diǎn)是借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。非順序映象----鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

特點(diǎn)是借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。算法的設(shè)計(jì)取決于選定的數(shù)據(jù)（邏輯）結(jié)構(gòu),算法的實(shí)現(xiàn)依賴于采用的存儲(chǔ)結(jié)構(gòu)。第一章 緒論順序映象----順序存儲(chǔ)結(jié)構(gòu)算法的設(shè)計(jì)取決于選定數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)存儲(chǔ)（物理）結(jié)構(gòu)數(shù)據(jù)運(yùn)算線性結(jié)構(gòu)非線性結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)插入運(yùn)算刪除運(yùn)算修改運(yùn)算查找運(yùn)算排序運(yùn)算樹形結(jié)構(gòu)圖狀結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)存儲(chǔ)（物理）結(jié)構(gòu)數(shù)據(jù)運(yùn)算線8、數(shù)據(jù)類型（DataType）是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。如：int——+，-，*，/，mod等。

9、抽象數(shù)據(jù)類型（AbstractDataType,ADT）

是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。

抽象數(shù)據(jù)類型的定義僅取決于它的邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無(wú)關(guān)。第一章 緒論8、數(shù)據(jù)類型（DataType）第一章 緒論抽象數(shù)據(jù)類型的形式定義抽象數(shù)據(jù)類型可用三元組表示（D，S，P）

其中，D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系對(duì)象，P是對(duì)D的基本操作。ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對(duì)象：〈數(shù)據(jù)對(duì)象的定義〉數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉基本操作：〈基本操作的定義〉}ADT抽象數(shù)據(jù)類型名第一章 緒論抽象數(shù)據(jù)類型的形式定義第一章 緒論第一章 緒論§1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型可通過(guò)固有數(shù)據(jù)類型來(lái)表示和實(shí)現(xiàn)，即利用處理器中已存在的數(shù)據(jù)類型來(lái)說(shuō)明新的結(jié)構(gòu)，用已經(jīng)實(shí)現(xiàn)的操作來(lái)組合新的操作。第一章 緒論§1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)第一章 緒論§1.4算法和算法分析一、算法（Alogrithm）

算法是對(duì)特定問(wèn)題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。特性：有窮性；確定性；可行性；輸入；輸出。第一章 緒論§1.4算法和算法分析第一章 緒論二、算法設(shè)計(jì)的要求

正確性；可讀性；健壯性；效率與低存儲(chǔ)量需求第一章 緒論二、算法設(shè)計(jì)的要求三、算法效率的度量1、時(shí)間復(fù)雜度：

算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)，算法的時(shí)間量度記作

T（n）=O（f（n））隨著問(wèn)題規(guī)模的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f（n）的增長(zhǎng)率相同，稱為算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。第一章 緒論

原操作通常是最深層循環(huán)內(nèi)的語(yǔ)句中的原操作，執(zhí)行次數(shù)和包含它的語(yǔ)句的頻度相同。語(yǔ)句的頻度指的是該語(yǔ)句重復(fù)執(zhí)行的次數(shù)。三、算法效率的度量第一章 緒論原操作通常是最深第一章 緒論常量階O（1）線性階O（n）平方階O（n2）對(duì)數(shù)階O（logn）指數(shù)階O（2n）2、算法的存儲(chǔ)空間需求以空間復(fù)雜度作為算法所需存儲(chǔ)空間的量度,記作S（n）=O（f（n））。第一章 緒論常量階O（1）第一章 緒論a)for(i=0;i<m;i++)for(j=0;j<n;j++)b[i][j]=0;

O(m×n)b)s=0;for(i=0;i<n;i++)for(j=i;j<n;j++)s+=b[i][j];

O(n2)c)i=1;while(i<n)i×=2;

O(log2n)第一章 緒論a)for(i=0;i<m;i++線形結(jié)構(gòu)的特點(diǎn)：

在數(shù)據(jù)元素的非空有限集中1、存在唯一的一個(gè)被稱做“第一個(gè)”的數(shù)據(jù)元素；2、存在唯一的一個(gè)被稱做“最后一個(gè)”的數(shù)據(jù)元素；3、除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前趨；4、除最后一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼。第二章 線性表線形結(jié)構(gòu)的特點(diǎn)：第二章 線性表第二章 線性表§2.1線性表的類型定義一、線性表

線性表是n個(gè)數(shù)據(jù)元素的有限序列。數(shù)據(jù)元素可以是一個(gè)數(shù)字、一個(gè)符號(hào)，甚至是更復(fù)雜的信息。例如：（A，B，C，……，Z）；（Mon，Tues，Wes，Thus，F(xiàn)ri，Sat，Sun）一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)（Item）組成，稱為記錄（Record）。

含有大量記錄的線性表又稱文件（File）。第二章 線性表§2.1線性表的類型定義第二章 線性表

同一線性表中的元素必定具有相同特性，即屬于同一數(shù)據(jù)對(duì)象，且相鄰數(shù)據(jù)元素之間存在序偶關(guān)系。線性表抽象記為:(a1，a2，ai，ai+1，

……，an)線性表抽象數(shù)據(jù)類型定義：

ADTList{數(shù)據(jù)對(duì)象：D={ai|aiElemSet,i=1,2,…,n,n0}數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,aiD,i=2,…,n}基本操作}第二章 線性表同一線性表中的元素必定具有相同特性，即二、特點(diǎn)：1.線性表的長(zhǎng)度是其中數(shù)據(jù)元素的個(gè)數(shù)n，n=0時(shí)稱為空表；2.非空表中，表中每個(gè)數(shù)據(jù)元素除第一個(gè)和最后一個(gè)外，有且僅有一個(gè)直接前趨和一個(gè)直接后繼元素。稱ai-1是ai的直接前趨元素，ai+1是ai的直接后繼元素；3.非空表中，每個(gè)數(shù)據(jù)元素在線性表中的位置僅由它們自己的序號(hào)決定；4.線性表的長(zhǎng)度可根據(jù)需要增長(zhǎng)或縮短，即對(duì)線性表的數(shù)據(jù)元素不僅可以進(jìn)行訪問(wèn)，還可以進(jìn)行插入或刪除等。第二章 線性表二、特點(diǎn)：第二章 線性表§2.2線性表的順序表示和實(shí)現(xiàn)一、線性表的順序表示1、描述：

用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。假設(shè)線性表的每個(gè)元素需占用k個(gè)存儲(chǔ)單元，并以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置。則：

LOC（ai+1）=LOC（ai）+k

LOC（ai）=LOC（a1）+（i-1）*kLOC（a1）是線性表的第一個(gè)數(shù)據(jù)元素a1的存儲(chǔ)位置，稱做線性表的起始位置/基地址。第二章 線性表§2.2線性表的順序表示和實(shí)現(xiàn)第二章 線性表2、特點(diǎn)：1）為表中相鄰的元素ai和ai+1賦以相鄰的存儲(chǔ)位置LOC（ai）和LOC（ai+1），即，以元素在計(jì)算機(jī)內(nèi)“物理位置相鄰”來(lái)表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系；2）每一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置都和線性表的起始位置相差一個(gè)和數(shù)據(jù)元素在線性表中的位序成正比的常數(shù)；3）只要確定了存儲(chǔ)線性表的起始位置，線性表中任一數(shù)據(jù)元素都可以隨機(jī)存取，即，線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。第二章 線性表2、特點(diǎn)：第二章 線性表二、線性表的順序存儲(chǔ)實(shí)現(xiàn)1、線性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)：Typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;2、順序表的初始化：

malloc();第二章 線性表二、線性表的順序存儲(chǔ)實(shí)現(xiàn)第二章 線性表3、線性表的插入：

將（a1，……，ai-1，ai，……，an）變成

（a1，……，ai-1，b，ai，……，an）(n=n+1)數(shù)據(jù)元素ai-1和ai之間的邏輯關(guān)系發(fā)生了變化。在第i(1≤i≤n)個(gè)元素之前插入一個(gè)元素時(shí)，需將第n至第i（共n-i+1）個(gè)元素向后移動(dòng)一個(gè)位置。第二章 線性表3、線性表的插入：第二章 線性表內(nèi)存a1a2aiai+1an01i-1數(shù)組下標(biāo)n-1in12i元素序號(hào)i+1nn+1內(nèi)存a1a2aiai+1an01i-1數(shù)組下標(biāo)n-1in12i元素序號(hào)i+1nn+1an-1x第二章 線性表內(nèi)存a1a2aiai+1an01i-1數(shù)組下標(biāo)n-1in124、線性表的刪除：

將（a1，……，ai-1，ai，ai+1……，an）變成（a1，……，ai-1，ai+1，……，an）(n=n-1)第二章 線性表4、線性表的刪除：第二章 線性表內(nèi)存a1a2aiai+1an01i-1數(shù)組下標(biāo)n-1in12i元素序號(hào)i+1nn+1內(nèi)存a1a2ai+1數(shù)組下標(biāo)01i-1n-2in-112i元素序號(hào)i+1n-1nanai+2第二章 線性表內(nèi)存a1a2aiai+1an01i-1數(shù)組下標(biāo)n-1in12第二章 線性表§2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

不要求邏輯上相鄰的元素在物理位置上相鄰一、線性鏈表1、定義：n個(gè)結(jié)點(diǎn)(node--數(shù)據(jù)域+指針域)鏈結(jié)成一個(gè)鏈表,即為線性表（a1，a2，......an)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。其中每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域,稱為線性鏈表／單鏈表。第二章 線性表§2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)ZHAOQIANSUNLIZHOUWUZHENGWANG^H例:線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925數(shù)據(jù)域指針域LIQIANSUNWANGWUZHAOZHENGZHOU存儲(chǔ)地址1713192531374331H頭指針第二章 線性表ZHAOQIANSUNLIZHOUWUZHENGWANG^H第二章 線性表２、特點(diǎn)

1）單鏈表可由頭指針唯一確定，整個(gè)鏈表的存取必須從頭指針開始/非隨機(jī)存??；2）最后一個(gè)結(jié)點(diǎn)的指針為“空”(null)；3）數(shù)據(jù)元素之間的邏輯關(guān)系由結(jié)點(diǎn)中的指針指示。抽象數(shù)據(jù)類型定義：

TypedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;第二章 線性表２、特點(diǎn)第二章 線性表3、單鏈表的查找GetElem_L(LinkListL,inti,ElemType&e)){/*L為帶頭結(jié)點(diǎn)的單鏈表的頭指針，查找第i個(gè)元素并由e返回*/p=L->next;j=1;

while(p&&j<i)/*移動(dòng)指針直到空或j>=i*/{p=p->next;++j;}if(!p||j>i)returnERROR;e=p->data;/*取第i個(gè)元素*/returnOK;}第二章 線性表3、單鏈表的查找第二章 線性表4、單鏈表插入結(jié)點(diǎn)

ListInsert_L(LinkList&L,inti,ElemTypee))

{/*帶頭結(jié)點(diǎn)的單鏈表L，在第i個(gè)元素前插入e*/

p=L;j=0;

while(p&&j<i-1)/*尋找第i-1個(gè)結(jié)點(diǎn)*/

{p=p->next;++j;}if(!p||j>i-1)returnERROR;s=(LinkList)malloc(sizeof(Lnode));s->data=e;s->next=p->next;p->next=s;

/*插入元素e*/

returnOK;}第二章 線性表4、單鏈表插入結(jié)點(diǎn)第二章 線性表5、單鏈表刪除結(jié)點(diǎn)ListDelete_L(LinkList&L,inti,ElemType&e))

{/*帶頭結(jié)點(diǎn)的單鏈表L，刪除第i個(gè)元素并由e返回*/

p=L;j=0;

while(p->next&&j<i-1)/*定位到第i-1個(gè)結(jié)點(diǎn)*/

{p=p->next;++j;}if(!(p->next)||j>i-1)returnERROR;q=p->next;p->next=q->next;e=q->data;

free(q);

/*刪除并釋放結(jié)點(diǎn)，由元素e返回*/

returnOK;}第二章 線性表5、單鏈表刪除結(jié)點(diǎn)第二章 線性表6、兩個(gè)有序鏈表的合并MergeList_L(LinkList&La,LinkList&Lb,LinkList&La)

{/*合并兩個(gè)非遞減單鏈表La和Lb為L(zhǎng)c*/

pa=La->next;pb=Lb->next;

Lc=pc=La;

while(pa&&pb)/*La和Lb都非空，未歸并完*/

{if(pa->data<=pb-<data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}pc->next=pa?pa:pb;

/*La和Lb有一個(gè)已歸并完，將另一個(gè)

free(Lb);鏈接在pc后*/}第二章 線性表6、兩個(gè)有序鏈表的合并第二章 線性表二、循環(huán)鏈表

表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。由此，從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其它結(jié)點(diǎn)。三、雙向鏈表

結(jié)點(diǎn)有兩個(gè)指針域，分別指向其直接后繼和直接前趨。TypedefstructDuLnode{ElemTypedata;structDuLnode*prior;structDuLnode*next;}DuLnode,*DuLinkList;第二章 線性表二、循環(huán)鏈表第二章 線性表§2.4一元多項(xiàng)式的表示及相加

利用線性鏈表的基本操作實(shí)現(xiàn)一元多項(xiàng)式的運(yùn)算，表中結(jié)點(diǎn)不僅要存儲(chǔ)非零系數(shù)，而且必須同時(shí)存儲(chǔ)相應(yīng)的指數(shù)。線性表((p1，e1)

，(p2，e2)，…，(pm，em))唯一確定一元多項(xiàng)式

Pn（x）=p1xe1+p2xe2+…+pmxem，0<=e1<e2<…<em<=n例：一元多項(xiàng)式的相加

比較兩個(gè)一元多項(xiàng)式鏈表中結(jié)點(diǎn)的指數(shù)第二章 線性表§2.4一元多項(xiàng)式的表示及相加比較兩個(gè)第三章 棧和隊(duì)列

§

3.1棧一、抽象數(shù)據(jù)類型棧（Stack）限定僅在表尾進(jìn)行插入和刪除操作的線性表。表尾稱為棧頂（top），表頭稱為棧底（bottom）。不含元素的空表稱為空棧。

棧S=（a1，a2，……，an），稱a1為棧底元素，an為棧頂元素。

后進(jìn)先出

---后進(jìn)先出的線性表/LIFO結(jié)構(gòu)。

基本操作：在棧頂進(jìn)行插入、刪除、棧的初始化、判空及取棧頂元素棧的抽象數(shù)據(jù)類型定義：第三章 棧和隊(duì)列§3.1棧第三章 棧和隊(duì)列二、棧的兩種表示和實(shí)現(xiàn)1、順序棧棧的順序存儲(chǔ)結(jié)構(gòu)是利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。設(shè)常量：STACK_INIT_SIZE存儲(chǔ)空間初始分配量

STACKINCREMENT存儲(chǔ)空間分配增量抽象數(shù)據(jù)類型定義：

typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;

第三章 棧和隊(duì)列二、棧的兩種表示和實(shí)現(xiàn)第三章 棧和隊(duì)列base為棧底指針，始終指向棧底，base=NULL表示棧結(jié)構(gòu)不存在；top為棧頂指針，初值指向棧底，即top=base，表示?？?。

插入新的棧頂元素,指針top增1----先插入后增1；刪除棧頂元素，指針top減1----先減1后刪除。

空棧的棧頂指針始終指向棧頂元素的下一個(gè)位置。2、鏈棧ABCDtopbasetopbase第三章 棧和隊(duì)列base為棧底指針，始終指第三章 棧和隊(duì)列top123450進(jìn)棧Atop出棧棧滿BCDEFtoptoptoptoptop123450ABCDEFtoptoptoptoptoptop?？誦asebasetop第三章 棧和隊(duì)列top123450進(jìn)棧Atop出棧棧滿BCD第三章 棧和隊(duì)列

§

3．2棧的應(yīng)用舉例一、數(shù)制轉(zhuǎn)換例：對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制數(shù)。N=(Ndivd)*d+Nmodd

Voidconversion(){InitStack(S);(1384)10=(2504)8scanf(“%d”,N);NNdiv8Nmoddwhile(N)13841684{Push(S,N%8);/*余數(shù)壓棧*/168210N=N/8;}2125while(!StackEmpty(S))202{Pop(S,e);/*出棧*/

Printf(“%d”,e);}}/*輸出8進(jìn)制的各位數(shù)*/第三章 棧和隊(duì)列§3．2棧的應(yīng)用舉例第三章 棧和隊(duì)列二、括號(hào)匹配的檢驗(yàn)---“期待的急迫程度”[（[][]）]12345678

在算法中設(shè)置一個(gè)棧，每讀入一個(gè)括號(hào)，若是右括號(hào)，則或者使置于棧頂?shù)淖罴逼鹊钠诖靡韵?，或者是不合法的情況；若是左括號(hào)，則作為一個(gè)新的更急迫的期待壓入棧中，自然使原有的在棧中的所有未消解的期待的急迫性都降了一級(jí)。在算法的開始和結(jié)束時(shí)，棧都應(yīng)該是空的.第三章 棧和隊(duì)列二、括號(hào)匹配的檢驗(yàn)---“期待的急迫程度”第三章 棧和隊(duì)列三、行編輯程序voidLineEdit(){InitStack(S);ch=getchar();/*從終端接收一個(gè)字符*/while(ch!=EOF){while(ch!=EOF&&ch!=‘\n’){switch(ch){case‘#’:Pop(S,c);break;/*出棧，刪除一個(gè)字符*/case‘@’:ClearStack(s);break;/*清棧*/default:Push(S,ch);break;}/*壓棧，插入一個(gè)有效字符*/ch=getchar();}

將棧內(nèi)字符送至數(shù)據(jù)區(qū)；

ClearStack(S);if(ch!=EOF)ch=getchar();}DestroyStack(S);}第三章 棧和隊(duì)列三、行編輯程序第三章 棧和隊(duì)列§3.3隊(duì)列一、抽象數(shù)據(jù)類型隊(duì)列的定義隊(duì)列（Queue）是一種“先進(jìn)先出”（FIFO）的線性表。只允許在表的一端進(jìn)行插入，而在表的另一端刪除元素。其中，允許插入的一端叫做隊(duì)尾（rear），允許刪除的一端叫做隊(duì)頭（front）.

出隊(duì)列a1a2a3……

an

入隊(duì)列

隊(duì)隊(duì)頭尾第三章 棧和隊(duì)列§3.3隊(duì)列第三章 棧和隊(duì)列二、鏈隊(duì)列——隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

用鏈表表示的隊(duì)列稱為鏈隊(duì)列。一個(gè)鏈隊(duì)列由頭指針和尾指針唯一確定。

空的判決條件為頭指針和尾指針均指向頭結(jié)點(diǎn)。Q.frontQ.reardatanext頭結(jié)點(diǎn)隊(duì)頭隊(duì)尾第三章 棧和隊(duì)列二、鏈隊(duì)列——隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)空的判決條第三章 棧和隊(duì)列三、順序隊(duì)列——隊(duì)列順序表示和實(shí)現(xiàn)

用一組地址連續(xù)的存儲(chǔ)單元依次存放從隊(duì)頭到隊(duì)尾的元素，附設(shè)指針front和rear分別指示隊(duì)頭元素和隊(duì)尾元素的位置。j1j2j3Q.rearQ.frontQ.rearQ.front543210j3Q.rearQ.frontj5Q.rearQ.frontj6第三章 棧和隊(duì)列三、順序隊(duì)列——隊(duì)列順序表示和實(shí)現(xiàn)j1j2j第三章 棧和隊(duì)列基本思想：把隊(duì)列設(shè)想成環(huán)形，讓sq[0]接在sq[M-1]之后，若rear+1==M,則令rear=0;實(shí)現(xiàn)：利用模運(yùn)算入隊(duì)：sq[rear]=x;rear=(rear+1)%M;出隊(duì)：x=sq[front];front=(front+1)%M;新問(wèn)題：隊(duì)滿、隊(duì)空判定條件循環(huán)隊(duì)列0M-11frontrear…...…...第三章 棧和隊(duì)列基本思想：把隊(duì)列設(shè)想成環(huán)形，讓sq[0]接在第三章 棧和隊(duì)列;012345rearfrontJ4,J5,J6出隊(duì)J5J6J7012345rearfrontJ4J9J8J7,J8,J9入隊(duì)J5J6012345rearfront初始狀態(tài)J4第三章 棧和隊(duì)列;012345rearfrontJ4,J5,第三章 棧和隊(duì)列012345rearfront解決方案：1.另外設(shè)一個(gè)標(biāo)志以區(qū)別隊(duì)空、隊(duì)滿2.少用一個(gè)元素空間,只剩下一個(gè)單元時(shí)就認(rèn)為隊(duì)滿，此時(shí)，隊(duì)尾指針只差一步追上隊(duì)頭指針。隊(duì)空：front==rear

隊(duì)滿：(rear+1)%M==frontJ5J6J7012345rearfrontJ4J8J8J6J4012345rearfrontJ7J5或第三章 棧和隊(duì)列012345rearfront解決方案：J5第四章 串字符串一般稱為串，在不同類型的應(yīng)用中，必須根據(jù)具體情況使用合適的存儲(chǔ)結(jié)構(gòu)。

§4．1串類型的定義1、串/String

是由零個(gè)或多個(gè)字符組成的有限序列。一般記為：s=‘a(chǎn)1a2……an’

（n0），ai（1in）可以是字母、數(shù)字或其它字符。2、串的長(zhǎng)度

串中字符的數(shù)目稱為串的長(zhǎng)度。零個(gè)字符的串稱為空串，記為“”，其長(zhǎng)度為零。第四章 串字符串一般稱為串，在不同類型的應(yīng)用中，必須第四章 串3、子串串中任意個(gè)連續(xù)的字符組成的子序列稱為該串的子串，包含子串的串相應(yīng)地稱為主串。4、字符在串中的位置

字符在序列中的序號(hào)稱為該字符在串中的位置。子串在主串中的位置以第一個(gè)字符在主串中的位置來(lái)表示。例：

a=‘BEI’b=‘JING’c=‘BEIJING’d=‘BEIJING’5、串相等

兩個(gè)串相等，當(dāng)且僅當(dāng)這兩個(gè)串的值相等。即，只有當(dāng)兩個(gè)串的長(zhǎng)度相等，并且各個(gè)對(duì)應(yīng)位置的字符都相等時(shí)才相等。第四章 串3、子串第四章 串6、空格串

由一個(gè)或多個(gè)空格組成的串‘’稱為空格串，其長(zhǎng)度為串中空格字符的個(gè)數(shù)。注意：串值必須用一對(duì)單引號(hào)括起來(lái)，但單引號(hào)‘’不屬于串。7、串的抽象數(shù)據(jù)類型定義串的基本操作中，通常以串的整體作為操作對(duì)象。第四章 串6、空格串第四章 串例：定位函數(shù)Index（S，T，pos）算法：在主串S中從第i（pos）個(gè)字符起，取長(zhǎng)度和T相等的子串和T比較。若相等，求得函數(shù)值為i，否則i值增1直到串S中不存在和串T相等的子串為止。第四章 串例：定位函數(shù)Index（S，T，pos）第四章 串§4．2串的表示和實(shí)現(xiàn)串有三種機(jī)內(nèi)表示方法：一、定長(zhǎng)順序存儲(chǔ)表示用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列。按照予定義的大小，為每個(gè)定義的串變量分配一個(gè)固定長(zhǎng)度的存儲(chǔ)區(qū)，可用定長(zhǎng)數(shù)組描述.#defineMAXSTRLEN255typedefunsignedcharSstring[MAXSTRLEN+1];

串的實(shí)際長(zhǎng)度可在予定義長(zhǎng)度的范圍內(nèi)隨意,超過(guò)予定義長(zhǎng)度的串值則被舍區(qū)去，稱為“截?cái)唷?第四章 串§4．2串的表示和實(shí)現(xiàn)第四章 串

串長(zhǎng)度表示：1)[0]下標(biāo)分量存放串的實(shí)際長(zhǎng)度；2)串尾后加入一個(gè)不計(jì)入串長(zhǎng)的結(jié)束標(biāo)識(shí)符“\0”。例1：串聯(lián)接Concat（&T，S1，S2）算法：基于串S1和S2長(zhǎng)度的不同情況，串T值的產(chǎn)生有如下三種情況：1、S1[0]+S2[0]MAXSTRLEN;2、S1[0]MAXSTRLEN而

S1[0]+S2[0]MAXSTRLEN；3、S1[0]=MAXSTRLEN。例2：求子串SubString（&Sub，S，pos，len）算法：求子串的過(guò)程即為復(fù)制字符序列的過(guò)程第四章 串串長(zhǎng)度表示：第四章 串二、堆分配存儲(chǔ)表示仍以一組地址連續(xù)的存儲(chǔ)單元存放串值字符序列，但存儲(chǔ)空間是在程序執(zhí)行過(guò)程中動(dòng)態(tài)分配而得：malloc（）、free（）

typedefstruct{char*ch;intlength;}HString;例1：串復(fù)制StrCopy（&T，S）算法：若串T存在，則先釋放串T所占空間free（T）。當(dāng)串S不空時(shí)，首先為串T分配大小和串S長(zhǎng)度相等的存儲(chǔ)空間，然后將串S的值復(fù)制到串T中。第四章 串二、堆分配存儲(chǔ)表示第四章 串例2：串插入StrInsert（&S，pos，T）算法：為串S重新分配大小等于串S和串T長(zhǎng)度之和S.length+T.length的存儲(chǔ)空間，然后進(jìn)行串值復(fù)制。特點(diǎn)：1）具有順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)，處理方便；2）對(duì)串長(zhǎng)沒(méi)有限制，操作靈活。第四章 串例2：串插入StrInsert（&S，pos，T第四章 串三、串的塊鏈存儲(chǔ)表示采用鏈表方式存儲(chǔ)串值“結(jié)點(diǎn)大小”：每個(gè)結(jié)點(diǎn)既可以存放一個(gè)字符，也可以存放多個(gè)字符.

headABCDEFGHI###^headABI^C…第四章 串三、串的塊鏈存儲(chǔ)表示headABCDEFGHI##第四章 串塊鏈存儲(chǔ)表示#defineCHUNKSIZE80typedefstructChunk{charch[CHUNKSIZE];structChunk*next;}Chunk;typedefstruct{chunk*head,*tail;intcurlen;}Lstring;

以鏈表存儲(chǔ)串時(shí)，除頭指針外還可附設(shè)一個(gè)尾指針指示鏈表中的最后一個(gè)結(jié)點(diǎn)，并給出當(dāng)前串的長(zhǎng)度塊鏈結(jié)構(gòu)。

設(shè)置尾指針的目的是為了便于進(jìn)行聯(lián)結(jié)操作，但需要處理第一個(gè)串尾的無(wú)效字符。第四章 串塊鏈存儲(chǔ)表示以鏈表存儲(chǔ)串時(shí)，除頭指針外還可模式匹配：即子串定位運(yùn)算（Index函數(shù)）算法目的：確定主串中所含子串第一次出現(xiàn)的位置（定位）——即如何實(shí)現(xiàn)Index(S,T,pos)函數(shù)初始條件：串S和T存在，T是非空串，1≤pos≤StrLength(s)操作結(jié)果：若主串S中存在和串T值相同的子串，則返回它在主串S中第pos個(gè)字符之后第一次出現(xiàn)的位置；否則函數(shù)值為0注：串S稱為被匹配的串，T稱為模式串。若S包含T，則稱“匹配成功”，否則稱“匹配不成功”。第四章 串§4．3串的模式匹配算法模式匹配：即子串定位運(yùn)算（Index函數(shù)）算法目的：確定主串一、基本設(shè)計(jì)思想將主串的第pos個(gè)字符和模式的第1個(gè)字符比較,(pos=1)若相等，繼續(xù)比較后續(xù)字符;若不等，從主串的下一字符（pos+1）起，重新與第1個(gè)字符比較直到主串的一個(gè)連續(xù)子串字符序列與模式相等。返回值為S中與T匹配的子序列第1個(gè)字符的序號(hào)，即匹配成功，否則匹配失敗，返回值0第四章 串一、基本設(shè)計(jì)思想將主串的第pos個(gè)字符和模式的第1個(gè)字符比第四章 串intIndex(SStringS,SStringT,Intpos){i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(S[i]==T[j]){++i;++j;}else{i=i-j+2;j=1;}}if(j>T[0])return(i-T[0]);elsereturn0;}/*i=i-(j-1)+1指針后退*/第四章 串/*i=i-(j-1)+1指針后退*/主串S=‘a(chǎn)babcabcacbab’，模式串T=‘a(chǎn)bcac’第1趟匹配：ababcabcacbab

abcac(i=3,j=3)第2趟匹配：ababcabcacbab

abcac(i=2,j=1)第3趟匹配：ababcabcacbab

abcac(i=7,j=5)第4趟匹配：ababcabcacbab

abcac(i=4,j=1)第5趟匹配：ababcabcacbab

abcac(i=5,j=1)第6趟匹配：ababcabcacbab

abcac能否利用已部分匹配過(guò)的信息而加快模式串的滑動(dòng)速度?KMP算法第四章 串主串S=‘a(chǎn)babcabcacbab’，模式串T=‘a(chǎn)bca

當(dāng)主串S中第i個(gè)字符與模式串P中第j個(gè)字符”失配”時(shí)(Si≠Pj)，主串中第i個(gè)字母應(yīng)與模式中哪個(gè)字符再比較呢?假設(shè)此時(shí)應(yīng)與模式串中第k個(gè)字符繼續(xù)比較，則模式串P中前k-1個(gè)字符的子串必滿足下列的關(guān)系（1<K<j）

‘P1P2…Pk-1’=‘Si-k+1Si-k+2…Si-1’而得到的部分匹配的結(jié)果是（Si和Pj失配時(shí)的結(jié)果）

‘P1P2…Pj-1’=‘Si-j+1Si-j+2…Si-1’兩式聯(lián)立可得：

‘P1P2…Pk-1’=‘Pj-k+1Pj-k+2…Pj-1’結(jié)論:K的選擇與主串無(wú)關(guān),只與模式串的結(jié)構(gòu)有關(guān)同理可得：

‘Pj-k+1Pj-k+2…Pj-1’=‘Si-k+1Si-k+2…Si-1’第四章 串二、KMP算法當(dāng)主串S中第i個(gè)字符與模式串P中第j個(gè)字符”失配”時(shí)

j12345tabcacnext[j]根據(jù)‘P1P2…Pk-1’=‘Pj-k+1Pj-k+2…Pj-1’，求next[j]01112令next[j]=k=0j=1Max{k|1<k<j且‘P1P2…Pk-1’=‘Pj-k+1Pj-k+2…Pj-1’

}1其它第四章 串j1234第1趟匹配：ab

a

bcabcacbab

ab

c

ac第2趟匹配：ababca

b

cacbab

abca

c第3趟匹配：ababcabcacbab

a

bcac例：改進(jìn)的主串S=‘a(chǎn)babcabcacbab’和子串T=‘a(chǎn)bcac’的匹配過(guò)程第四章 串

j12345tabcacnext[j]01112第1趟匹配：ababcabcacba令next[j]=k，根據(jù)‘P1P2…Pk-1’=‘Pj-k+1Pj-k+2…Pj-1’,求

j12345678910111213141516模式串a(chǎn)bcdabcdabcdaabcnext[j]01111234567891023

j1234567模式串a(chǎn)aaaaabnext[j]0123456Nextval[j]

0000006

Nextval[j]

01110111011101011

第四章 串令next[j]=k，根據(jù)‘P1P2…Pk-1’=‘P第1趟匹配：aaaaabaaaaaaab

aaaaa

a第2趟匹配：aaaaabaaaaaaab

aaaa

a第3趟匹配：aaaaabaaaaaaab

aaa

a

j1234567模式串

aaaaaabnext[j]0123456第4趟匹配：aaaaabaaaaaaab

aa

a第5趟匹配：aaaaabaaaaaaab

a

a

第6趟匹配：aaaaabaaaaaaab

a

第7趟匹配：aaaaabaaaaaaab

aaaaaa

b

第四章 串第1趟匹配：aaaaabaaaaaa設(shè)主串S=‘S1S2……Sm’，,子串P=‘P1P2……Pn’當(dāng)Si和Pj不相等（失配）時(shí)，求出next[j]=K，表示下一次比較時(shí)讓Si和Pk相比較如果Pk和Pj相等，Si和Pk肯定不相等，所以，必然需要再繼續(xù)比較下去，即next[j]的值需要修正如果Pk和Pj不相等，則Si和Pk有可能相等，有比較的必要，即next[j]的值不需要修正再下一次比較的時(shí)候，是判斷Pk所對(duì)應(yīng)的next[j]所代表的字符是否與Pk相等，即Pk是否等于Pnext[k]，如果相等則繼續(xù)比較，否則即可得到next[j]的修正值第四章 串設(shè)主串S=‘S1S2……Sm’，,子串P=‘P1P2……Pnext[j]pnext[j]≠p

j;nextval[j]=nextval[next[j]]pnext[j]＝pj第四章 串next[j]的修正值next[j]

j1234567模式串a(chǎn)aaaaabnext[j]0123456Nextval[j]

0000006

j12345678910111213141516模式串a(chǎn)bcdabcdabcdaabcnext[j]01111234567891023Nextval[j]

01110111011101011

第四章 串

next[j]pnext[j]≠p

j;nextval[j]=nextval[next[j]]pnext[j]＝pjj12345第五章 數(shù)組和廣義表數(shù)組和廣義表是線性表的擴(kuò)充——表中的數(shù)據(jù)元素本身也是一個(gè)數(shù)據(jù)結(jié)構(gòu)?！?.1數(shù)組的定義數(shù)組的抽象數(shù)據(jù)類型定義：

注意：數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。實(shí)現(xiàn)初始化、銷毀、存取元素和修改元素值等操作。第五章 數(shù)組和廣義表數(shù)組和廣義表是線性表的擴(kuò)充第五章 數(shù)組和廣義表§5.2數(shù)組的順序表示和實(shí)現(xiàn)存儲(chǔ)單元是一維結(jié)構(gòu)，而數(shù)組是個(gè)多維結(jié)構(gòu),則用一組連續(xù)存儲(chǔ)單元存放數(shù)組的數(shù)據(jù)元素就有個(gè)次序約定問(wèn)題。

二維數(shù)組可有兩種存儲(chǔ)方式：

1）以列序?yàn)橹餍颍?/p>

2）以行序?yàn)橹餍?。第五?數(shù)組和廣義表§5.2數(shù)組的順序表示和實(shí)現(xiàn)第五章 數(shù)組和廣義表對(duì)于數(shù)組，一旦規(guī)定了它的維數(shù)和各維的長(zhǎng)度，便可為它分配存儲(chǔ)空間。反之，只要給出一組下標(biāo)便可求得相應(yīng)數(shù)組元素的存儲(chǔ)位置。以行序?yàn)橹餍驗(yàn)槔僭O(shè)每個(gè)數(shù)據(jù)元素占L個(gè)存儲(chǔ)單元，則二維數(shù)組A中任一元素aij的存儲(chǔ)位置可由下式確定：

LOC（i，j）=LOC（0，0）+（b2*i+j）＊L

數(shù)組元素的存儲(chǔ)位置是其下標(biāo)的線性函數(shù)—稱這種存儲(chǔ)結(jié)構(gòu)為隨機(jī)存儲(chǔ)結(jié)構(gòu)。第五章 數(shù)組和廣義表對(duì)于數(shù)組，一旦規(guī)定了它的維2.下三角矩陣

矩陣下三角部分元素是隨機(jī)的，而上三角部分元素全部相同（為某常數(shù)C）或全為0?！?.3特殊矩陣一、三角矩陣1.上三角矩陣

矩陣上三角部分元素是隨機(jī)的，而下三角部分元素全部相同（為某常數(shù)C）或全為0。第五章 數(shù)組和廣義表2.下三角矩陣§5.3特殊矩陣第五章 數(shù)組和廣義表（a）上三角矩陣（b）下三角矩陣第五章 數(shù)組和廣義表（a）上三角矩陣（b）下三角矩陣第五章 數(shù)組和廣義表二、對(duì)角矩陣

若矩陣中所有非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中，區(qū)域外的值全為0，則稱為對(duì)角矩陣。

常見的有三對(duì)角矩陣、五對(duì)角矩陣、七對(duì)角矩陣等。一個(gè)7×7的三對(duì)角矩陣第五章 數(shù)組和廣義表二、對(duì)角矩陣一個(gè)7×7的三對(duì)角矩陣第五章 數(shù)組和廣義表三、特殊矩陣壓縮存儲(chǔ)1．三角矩陣下三角矩陣矩陣中共有n(n+1)/2個(gè)非零元素，共需要n(n+1)/2+1個(gè)存儲(chǔ)空間。若將其存放到一維向量空間S[0]..S[n(n+1)/2]中，則S[K]與a[i][j]的對(duì)應(yīng)關(guān)系為：

當(dāng)i≥j時(shí)，a[i][j]是非零元素，a[i][j]前面有i行，共有1+2+3+…i=i(i+1)/2個(gè)元素，a[i][j]前面有j列，共j個(gè)元素，即k=i(i+1)/2+j；當(dāng)i<j時(shí)，a[i][j]是零元素，存放在最后一個(gè)存儲(chǔ)單元S[n(n+1)/2]中。

i(i+1)/2+j當(dāng)i≥jn(n+1)/2當(dāng)i＜jK=第五章 數(shù)組和廣義表三、特殊矩陣壓縮存儲(chǔ)下三角矩陣當(dāng)i≥j時(shí)，a[i]上三角矩陣矩陣中共有n(n+1)/2個(gè)非零元素，共需要n(n+1)/2+1個(gè)存儲(chǔ)空間。若將其存放到一維向量空間S[0]..S[n(n+1)/2]中，則S[K]與a[i][j]的對(duì)應(yīng)關(guān)系為：當(dāng)i≤j時(shí),a[i][j]是非零元素,a[i][j]前面有i行,共有n+(n-1)+(n-2)+…(n-(i-1))=i(n+n-i+1)/2=i*n-i(i-1)/2個(gè)元素，a[i][j]前面有j列，共j-i個(gè)非零元素，即k=i*n-i(i-1)/2+j-i；當(dāng)i<j時(shí)，a[i][j]是零元素，存放在最后一個(gè)存儲(chǔ)單元S[n(n+1)/2]中。

i*n-i(i-1)/2+j-i當(dāng)i≤jn(n+1)/2當(dāng)i>jK=第五章 數(shù)組和廣義表上三角矩陣當(dāng)i≤j時(shí),a[i][j]是非零元素,2．對(duì)角矩陣（僅討論三對(duì)角矩陣的壓縮存儲(chǔ)）。在一個(gè)nn的三對(duì)角矩陣中，只有n+n-1+n-1個(gè)非零元素，故只需3n-2個(gè)存儲(chǔ)單元即可，零元已不占用存儲(chǔ)單元。故，可將nn三對(duì)角矩陣A壓縮存放到只有3n-2個(gè)存儲(chǔ)單元的s向量中，假設(shè)仍按行優(yōu)先順序存放，

s[k]與a[i][j]的對(duì)應(yīng)關(guān)系為：3i或3j當(dāng)i=j3i+1或3j-2當(dāng)i=j-13i-1或3j+2當(dāng)i=j+1K=第五章 數(shù)組和廣義表2．對(duì)角矩陣（僅討論三對(duì)角矩陣的壓縮存儲(chǔ)）。s[k]與a[i第五章 數(shù)組和廣義表§5.4廣義表一、廣義表的定義

廣義表是線性表的推廣，也稱為列表。廣泛地用于人工智能等領(lǐng)域的表處理語(yǔ)言LISP語(yǔ)言。抽象數(shù)據(jù)類型廣義表的定義：

廣義表一般記作：

LS=(a1，a2，…，an)

廣義表的名稱,大寫小寫廣義表的長(zhǎng)度

ai可以是單個(gè)元素，也可以是廣義表，分別稱為原子和子表。當(dāng)LS非空時(shí)，稱第一個(gè)元素為表頭，其余元素組成的表(a2，…，an)為表尾。

第五章 數(shù)組和廣義表§5.4廣義表第五章 數(shù)組和廣義表二、廣義表的結(jié)論1、列表的元素可以是子表,而子表的子表還可以是子表，…。故，列表是一個(gè)多層次結(jié)構(gòu)；2、列表可為其它列表所共享,且通過(guò)子表的名稱引用，如D；3、列表可以是一個(gè)遞歸的表,即列表也可以是其本身的子表,如E;4、任何一個(gè)非列表其表頭可能是原子,也可能是列表,而其表尾必為列表。

注意：列表（）和（（））不同

空表n=0n=1,表頭、表尾均為空表（）例：A=()B=(e)C=(a，(b，c，d))D=(A，B，C)E=(a，(E))ADBCabcde第五章 數(shù)組和廣義表二、廣義表的結(jié)論例：A=()第五章 數(shù)組和廣義表§5.5廣義表的存儲(chǔ)結(jié)構(gòu)廣義表LS=(a1，a2，…，an)的數(shù)據(jù)元素可以具有不同的結(jié)構(gòu)，通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，每個(gè)數(shù)據(jù)元素用一個(gè)結(jié)點(diǎn)表示。1、頭尾鏈表存儲(chǔ)表示值域Tag=1hptp標(biāo)志域標(biāo)志域Tag=0atom表頭指針表尾指針表結(jié)點(diǎn)原子結(jié)點(diǎn)第五章 數(shù)組和廣義表§5.5廣義表的存儲(chǔ)結(jié)構(gòu)值域Ta第五章 數(shù)組和廣義表2、擴(kuò)展線性鏈表存儲(chǔ)表示值域Tag=1hptp標(biāo)志域標(biāo)志域Tag=0atomtp表頭指針后繼結(jié)點(diǎn)指針后繼結(jié)點(diǎn)指針表結(jié)點(diǎn)原子結(jié)點(diǎn)第五章 數(shù)組和廣義表2、擴(kuò)展線性鏈表存儲(chǔ)表示習(xí)題一、選擇題1.下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？（B）A.線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。B.線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C.線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。D.線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。2.線性表是具有n個(gè)（C）的有限序列（n>0）。A.表元素B.字符C.數(shù)據(jù)元素D.數(shù)據(jù)項(xiàng)E.信息項(xiàng)3.若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（A）存儲(chǔ)方式最節(jié)省時(shí)間。A.順序表B.雙鏈表C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D.單循環(huán)鏈表習(xí)題一、選擇題習(xí)題4.某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（D）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.單鏈表B.僅有頭指針的單循環(huán)鏈表C.雙鏈表D.僅有尾指針的單循環(huán)鏈表5.設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選用(D)最節(jié)省時(shí)間。A.單鏈表B.單循環(huán)鏈表C.帶尾指針的單循環(huán)鏈表D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表6.完成在雙循環(huán)鏈表結(jié)點(diǎn)p之后插入s的操作是（D）。A.p->next=s;s->priou=p;p->next->priou=s;s->next=p->next;B.p->next->priou=s;p->next=s;s->priou=p;s->next=p->next;C.s->priou=p;s->next=p->next;p->next=s;p->next->priou=s;D.s->priou=p;s->next=p->next;p->next->priou=s;p->next=s;習(xí)題4.某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元習(xí)題二、判斷題1.鏈表中的頭結(jié)點(diǎn)僅起到標(biāo)識(shí)的作用。(×)2.順序存儲(chǔ)結(jié)構(gòu)的主要缺點(diǎn)是不利于插入或刪除操作。(√)3.線性表采用鏈表存儲(chǔ)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的。(√)4.對(duì)任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一定優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。(×)5.順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。(×)6.為了很方便的插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。(√)7.鏈表是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表,進(jìn)行插入、刪除操作時(shí)，在鏈表中比在順序存儲(chǔ)結(jié)構(gòu)中效率高。(√)習(xí)題二、判斷題習(xí)題三、算法題1、設(shè)順序表va中的數(shù)據(jù)元素遞增有序。試寫一算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。2、已知線性表中的元素以值遞增有序排列。試寫一個(gè)高效的算法，刪除表中所有值大于mink且小于maxk的元素（若表中存在這樣的元素），并分析算法的時(shí)間復(fù)雜度。（分別以單鏈表/順序表做存儲(chǔ)結(jié)構(gòu)）3、試寫一算法，實(shí)現(xiàn)順序表的就地逆置，即利用原表的存儲(chǔ)空間將線性表（a1，a2，…，an）逆置為（an

，an-1，…，a1

）。習(xí)題三、算法題習(xí)題4、試寫一算法，對(duì)單鏈表實(shí)現(xiàn)就地逆置。5、假設(shè)稱正讀和反讀都相同的字符序列為“回文”，例如，‘a(chǎn)bba’和‘a(chǎn)bcba’是回文，‘a(chǎn)bcde’和‘a(chǎn)babab’則不是回文。試寫一個(gè)算法判別讀入的一個(gè)以‘@’為結(jié)束符的字符序列是否是“回文”。6、試寫一算法，實(shí)現(xiàn)堆存儲(chǔ)結(jié)構(gòu)的串的置換操作Replace(&S,T,V)。習(xí)題4、試寫一算法，對(duì)單鏈表實(shí)現(xiàn)就地逆置。習(xí)題習(xí)題學(xué)時(shí)數(shù)：72學(xué)時(shí)（16學(xué)時(shí)實(shí)驗(yàn)）+課程設(shè)計(jì)（一周）教材：《數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版》嚴(yán)蔚敏、吳偉民