天津大學(xué)本科課程考研數(shù)據(jù)結(jié)構(gòu)課件全

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

什么是數(shù)據(jù)結(jié)構(gòu)基本概念和術(shù)語(yǔ)抽象數(shù)據(jù)類型算法分析性能分析與度量第一章緒論學(xué)生成績(jī)表格選課單學(xué)號(hào)課程號(hào)時(shí)間成績(jī)20001DS2000SX20002001,22000,9788720002ART2000DS20002002,22001,2689020003SX2000DS20002000,92001,2877820004SX2000ART20002000,92002,28976UNIX文件系統(tǒng)結(jié)構(gòu)圖/rootbinlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp例如:在迷宮問題中,計(jì)算機(jī)之所以能夠找到迷宮的出口,是因?yàn)槿藗円褜⑺阉鞒隹诘牟呗允孪却嫒胗?jì)算機(jī)中.在迷宮中,每走到一處,接下來可走的通路有三條,如圖:計(jì)算機(jī)處理的這類對(duì)象之間通常不存在線性關(guān)系,若將從迷宮入口處到出口的過程中所有可能的通路都畫出來,則可以得到一棵倒長(zhǎng)的”樹”.”樹根”是迷宮入口,”樹葉”是出口或死路.”樹”可以是某些非數(shù)值計(jì)算問題的數(shù)學(xué)模型.入口死路死路死路死路死路死路死路死路死路死路出口死路死路死路死路在應(yīng)用程序中涉及到各種各樣的數(shù)據(jù)，如何在計(jì)算機(jī)中組織、存儲(chǔ)、傳遞數(shù)據(jù)，需要討論它們的歸類及它們之間的關(guān)系，從而建立相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，依此實(shí)現(xiàn)軟件功能。綜上，描述這類非數(shù)值計(jì)算問題的數(shù)學(xué)模型不是數(shù)學(xué)方程,而是樹、表和圖之類的數(shù)據(jù)結(jié)構(gòu)。因此從廣義上講，數(shù)據(jù)結(jié)構(gòu)描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型及其上的操作在計(jì)算機(jī)中的表示和實(shí)現(xiàn)。基本概念和術(shù)語(yǔ)數(shù)據(jù)(Data)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計(jì)算機(jī)中，被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)的集合。

數(shù)值性數(shù)據(jù)（整數(shù)、定點(diǎn)數(shù)、浮點(diǎn)數(shù)）非數(shù)值性數(shù)據(jù)（文字?jǐn)?shù)據(jù)）數(shù)據(jù)元素（DataElement）數(shù)據(jù)的基本單位。在計(jì)算機(jī)程序中常作為一個(gè)整體進(jìn)行考慮和處理。有時(shí)一個(gè)數(shù)據(jù)元素可以由若干數(shù)據(jù)項(xiàng)(DataItem)組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位。數(shù)據(jù)元素又稱為元素、結(jié)點(diǎn)、記錄數(shù)據(jù)項(xiàng)(DataItem)

姓名俱樂部名稱出生日期年月日入隊(duì)日期職位業(yè)績(jī)數(shù)據(jù)元素DataElement數(shù)據(jù)項(xiàng)DataItem數(shù)據(jù)字段DataField數(shù)據(jù)對(duì)象(dataobject)具有相同性質(zhì)的數(shù)據(jù)元素的集合。整數(shù)數(shù)據(jù)對(duì)象N={0,1,2,…}字母字符數(shù)據(jù)對(duì)象

C={‘A’,‘B’,‘C’,…‘F’}數(shù)據(jù)結(jié)構(gòu)（DataStructure）形式定義：

某一數(shù)據(jù)對(duì)象的所有數(shù)據(jù)成員之間的關(guān)系。記為：

Data_Structure={D,S}

其中，D是某一數(shù)據(jù)對(duì)象，S是該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。四個(gè)基本結(jié)構(gòu)集合線性結(jié)構(gòu)樹形結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲(chǔ)無關(guān)；從具體問題抽象出來的數(shù)據(jù)模型；與數(shù)據(jù)元素本身的形式、內(nèi)容無關(guān)；與數(shù)據(jù)元素的相對(duì)位置無關(guān)。數(shù)據(jù)的邏輯結(jié)構(gòu)分類線性結(jié)構(gòu)

線性表非線性結(jié)構(gòu)

樹圖（或網(wǎng)絡(luò)）bindevetclibuser2114131211234678910315871011998745662313155線性結(jié)構(gòu)樹形結(jié)構(gòu)

樹二叉樹二叉排序樹堆結(jié)構(gòu)123548711102916125643125436113318146651921圖結(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)依賴于計(jì)算機(jī)語(yǔ)言。

順序存儲(chǔ)表示鏈接存儲(chǔ)表示索引存儲(chǔ)表示散列存儲(chǔ)表示數(shù)據(jù)處理將數(shù)據(jù)通過人力或機(jī)器，將收集到的數(shù)據(jù)加以系統(tǒng)的處理，歸納出有價(jià)值的信息。編輯（edit）：將存在某種媒體上的數(shù)據(jù)經(jīng)過計(jì)算機(jī)復(fù)制到另一媒體時(shí)，對(duì)輸入的數(shù)據(jù)逐一檢查，其目的在于改變數(shù)據(jù)的存儲(chǔ)形式和效率，以便后面的處理。排序（sort）：將數(shù)據(jù)根據(jù)某一鍵值，以某種順序排序后輸出，其目的在于方便其他方面的數(shù)據(jù)處理。歸并（merge）：將兩種以上相同性質(zhì)的文件數(shù)據(jù)歸并在一起。分配（distribute）：將一個(gè)文件的數(shù)據(jù)按照某一基準(zhǔn)分配在兩個(gè)以上的存儲(chǔ)體，其目的在于方便各個(gè)分配的文件能獨(dú)自處理。建檔（generate）：根據(jù)某些條件規(guī)格，配合某些已存在的文件，再產(chǎn)生一個(gè)新的且有利用價(jià)值的文件。更新（update）：根據(jù)數(shù)據(jù)的變動(dòng)來更新主檔案，以保持主檔案的正確與完整性。計(jì)算（compute）：將讀取的文件數(shù)據(jù)，依據(jù)規(guī)定方法計(jì)算處理。鏈表（list）：是一種數(shù)據(jù)的集合，也就是一系列的數(shù)據(jù)存儲(chǔ)于內(nèi)存，以某種關(guān)系來連接這些相關(guān)聯(lián)的數(shù)據(jù)。查找（search）：輸入一個(gè)鍵值到數(shù)據(jù)表中進(jìn)行對(duì)照，找出具有相同鍵值的數(shù)據(jù)。查詢（inquiry）：根據(jù)數(shù)據(jù)項(xiàng)的鍵值或條件，到主檔案中找出符合該條件或鍵值相同的數(shù)據(jù)，依照用戶指定的方法輸出。其它處理：分類（classifying）、摘要（summarizing）、變換(transmission)。抽象數(shù)據(jù)類型（AbstractDataType）數(shù)據(jù)類型

定義：一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。C語(yǔ)言中的基本數(shù)據(jù)類型

intcharfloatdoublevoid

整型字符型浮點(diǎn)型雙精度型無值抽象數(shù)據(jù)類型是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作數(shù)據(jù)結(jié)構(gòu)+定義在此數(shù)據(jù)結(jié)構(gòu)上的一組操作=抽象數(shù)據(jù)類型例如：矩陣+（求轉(zhuǎn)置、加、乘、 求逆、求特征值） 構(gòu)成一個(gè)矩陣的抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型的描述抽象數(shù)據(jù)類型可用（D，S，P）三元組表示 其中，D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，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ù)對(duì)象、數(shù)據(jù)關(guān)系用偽碼描述；基本操作定義格式為 基本操作名（參數(shù)表） 初始條件：〈初始條件描述〉

操作結(jié)果：〈操作結(jié)果描述〉基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；引用參數(shù)以&打頭，除可提供輸入值外，還將返回操作結(jié)果?！俺跏紬l件”描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息?！安僮鹘Y(jié)果”說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略之。抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)

抽象數(shù)據(jù)類型可以通過固有數(shù)據(jù)類型(高級(jí)編程語(yǔ)言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來實(shí)現(xiàn)抽象數(shù)據(jù)類型類class數(shù)據(jù)對(duì)象數(shù)據(jù)成員基本操作成員函數(shù)(方法)在C++中，類的成分(數(shù)據(jù)成員和成員函數(shù))可以有三種訪問級(jí)別Private私有成分（只允許類的成員函數(shù)進(jìn)行訪問）

protected保護(hù)成分（只允許類的成員函數(shù)及其子孫類進(jìn)行訪問）public公有成分（允許類的成員函數(shù)、類的實(shí)例及其子孫類、子孫類的實(shí)例進(jìn)行訪問）自然數(shù)的抽象數(shù)據(jù)類型定義ADT

NaturalNumberisobjects:一個(gè)整數(shù)的有序子集合,它開始于0,

結(jié)束于機(jī)器能表示的最大整數(shù)(MaxInt)。Function:

對(duì)于所有的x,

y

NaturalNumber;

False,TrueBoolean,+、-、<、==、=等都是可用的服務(wù)。

Zero():NaturalNumber

返回自然數(shù)0IsZero(x):if(x==0)返回True

Booleanelse返回FalseAdd(x,y):if(x+y<=MaxInt)返回x+y

NaturalNumber

else返回MaxIntSubtract(x,y):if(x<y)返回0

NaturalNumberelse返回x-yEqual(x,y):if(x==y)返回True

Booleanelse返回FalseSuccessor(x):if(x==MaxInt)返回xNaturalNumberelse返回x+1end

NaturalNumber程序的產(chǎn)生五個(gè)階段：需求（輸入、輸出）設(shè)計(jì)（編寫算法）分析（選擇最佳算法）細(xì)化與編碼（編寫程序）驗(yàn)證（程序驗(yàn)證、測(cè)試、調(diào)試）算法分析算法定義：為了解決某類問題而規(guī)定的一個(gè)有限長(zhǎng)的操作序列。特性：有窮性算法在執(zhí)行有窮步后能結(jié)束確定性每步定義都是確切、無歧義可行性每一條運(yùn)算應(yīng)足夠基本輸入有0個(gè)或多個(gè)輸入輸出有一個(gè)或多個(gè)輸出算法設(shè)計(jì)例子：

選則排序問題：遞增排序解決方案：逐個(gè)選擇最小數(shù)據(jù)算法框架：

for(inti=0;i<n-1;i++){

//n-1趟 從a[i]檢查到a[n-1];

若最小整數(shù)在a[k],交換a[i]與a[k];}細(xì)化：SelectSortvoidselectSort(inta[],intn){

//對(duì)n個(gè)整數(shù)a[0],a[1],…,a[n-1]按遞增順序排序

for(inti=0;i<n-1;i++){

intk=i;

//從a[i]查到a[n-1],找最小整數(shù),在a[k]

for(intj=i+1;j<n;j++)

if(a[j]<a[k])k=j;

inttemp=a[i];a[i]=a[k];a[k]=temp;}}

模板

(template)定義

適合多種數(shù)據(jù)類型的類定義或算法，在特定環(huán)境下通過簡(jiǎn)單地代換，變成針對(duì)具體某種數(shù)據(jù)類型的類定義或算法例：求最大值max(a,b)宏定義：#definemax(a,b)((a)>(b)?(a):(b))缺點(diǎn)不能檢查數(shù)據(jù)類型，損害類型安全性例：求最大值max(a,b)函數(shù)重載：intmax(inta,intb){returna>b?a:b;}floatmax(floata,floatb){returna>b?a:b;}voidmain(){ cout<<“Max(3,5)is”<<max(3,5)<<endl; cout<<“Max(‘3’,’5’)is”<<max(‘3’,’5’)<<endl;}對(duì)于輸入max(3,5)和max(‘3’,’5’)的結(jié)果？例：求最大值max(a,b)函數(shù)模板：#include<iostream.h>template<classT>Tmax(Ta,Tb){returna>b?a:b;}voidmain(){ cout<<“Max(3,5)is”<<max(3,5)<<endl; cout<<“Max(‘3’,’5’)is”<<max(‘3’,’5’)<<endl;}性能分析與度量算法的性能標(biāo)準(zhǔn)正確性：包括不含語(yǔ)法錯(cuò)誤對(duì)幾組數(shù)據(jù)運(yùn)行正確對(duì)典型、苛刻的數(shù)據(jù)運(yùn)行正確；對(duì)所有數(shù)據(jù)運(yùn)行正確可讀性效率：高效、低存儲(chǔ)需要。（算法執(zhí)行時(shí)間短，同時(shí)所占用的存儲(chǔ)空間小。健壯性：當(dāng)輸入非法數(shù)據(jù)時(shí)，算法也能作出適當(dāng)反應(yīng)，而不會(huì)出現(xiàn)莫名其妙的輸出結(jié)果。算法的后期測(cè)試在算法中的某些部位插裝時(shí)間函數(shù)time

(),

測(cè)定算法完成某一功能所花費(fèi)時(shí)間

doublestart,stop;

time(&start);

intk=seqsearch(a,n,x);

time(&stop);

doublerunTime=stop-start;printf("%d%d\n",n,runTime);intseqsearch(inta[],intn,intx){//在a[0],…,a[n-1]中搜索x

inti=0;

while(i<n&&a[i]!=x)

i++;

if(i==n)return

-1;

returni;}

算法的事前估計(jì)空間復(fù)雜度度量存儲(chǔ)空間的固定部分

程序指令代碼的空間，常數(shù)、簡(jiǎn)單變量、定長(zhǎng)成分(如數(shù)組元素、結(jié)構(gòu)成分、對(duì)象的數(shù)據(jù)成員等)變量所占空間可變部分

尺寸與實(shí)例特性有關(guān)的成分變量所占空間、引用變量所占空間、遞歸棧所用空間、通過new和delete命令動(dòng)態(tài)使用空間時(shí)間復(fù)雜度度量運(yùn)行時(shí)間=算法中每條語(yǔ)句執(zhí)行時(shí)間之和。每條語(yǔ)句執(zhí)行時(shí)間=該語(yǔ)句的執(zhí)行次數(shù)（頻度）*語(yǔ)句執(zhí)行一次所需時(shí)間。語(yǔ)句執(zhí)行一次所需時(shí)間取決于機(jī)器的指令性能和速度和編譯所產(chǎn)生的代碼質(zhì)量，很難確定。設(shè)每條語(yǔ)句執(zhí)行一次所需時(shí)間為單位時(shí)間，則一個(gè)算法的運(yùn)行時(shí)間就是該算法中所有語(yǔ)句的頻度之和。時(shí)間復(fù)雜度一、時(shí)間復(fù)雜度即算法中語(yǔ)句重復(fù)執(zhí)行次數(shù)的數(shù)量級(jí)就是時(shí)間復(fù)雜度。二、表示方法：

T(n)=O(f(n))f(n)表示基本操作重復(fù)執(zhí)行的次數(shù)，是n的某個(gè)函數(shù)，隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率屬于同一數(shù)量級(jí)；O表示f(n)和T(n)只相差一個(gè)常數(shù)倍。T（n)稱做漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。幾種時(shí)間復(fù)雜度O(1):常數(shù)時(shí)間O(log2n)：對(duì)數(shù)時(shí)間O(n)：線性時(shí)間O(nlog2n)：線性對(duì)數(shù)時(shí)間O(n2):平方時(shí)間O(n3):立方時(shí)間O(2n):指數(shù)時(shí)間上述的時(shí)間復(fù)雜度的優(yōu)劣次序如下（n>=16):O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)第二章線性表線性表順序表鏈表順序表與鏈表的比較線性表定義：

n（0）個(gè)數(shù)據(jù)元素的有限序列，記作（a1,…ai-1,ai,ai+1,…,an）

其中,ai

是表中數(shù)據(jù)元素，n是表長(zhǎng)度。特點(diǎn):同一線性表中元素具有相同特性。相鄰數(shù)據(jù)元素之間存在序偶關(guān)系。除第一個(gè)元素外，其他每一個(gè)元素有一個(gè)且僅有一個(gè)直接前驅(qū)。除最后一個(gè)元素外，其他每一個(gè)元素有一個(gè)且僅有一個(gè)直接后繼。 a1a2a3a4a5a6順序表定義：將線性表中的元素相繼存放在一個(gè)連續(xù)的存儲(chǔ)空間中。

存儲(chǔ)結(jié)構(gòu)：數(shù)組。特點(diǎn)：線性表的順序存儲(chǔ)方式。存取方式：順序存取、隨機(jī)存取順序存儲(chǔ)結(jié)構(gòu)示意圖458990674078

012345順序表的存儲(chǔ)方式：LOC(ai+1)=LOC(ai)+lLOC(ai)=LOC(a1)+(i-1)*l

a1

a2

…ai………an12…i………n

aa+l…a+(i-1)*l………a+(n-1)*l

idle順序表（SeqList）的類型定義

#defineListSize100//最大允許長(zhǎng)度

typedefintListData;

typedefstruct

{

ListData*data;//存儲(chǔ)空間基址

intlength; //當(dāng)前元素個(gè)數(shù)

}

SeqList;順序表基本運(yùn)算初始化

voidInitList(SeqList&L){L.data=(ListData*)malloc(ListSize*sizeof(ListData));if(L.data==NULL){printf(“存儲(chǔ)分配失敗!\n”);exit(1);}L.length=0;}按值查找：找x在表中的位置，若查找成功，返回表項(xiàng)的位置，否則返回-1

intFind(SeqList&L,ListDatax){inti=0;while(i<L.length&&L.data[i]!=x)i++;if(i<L.length)returni;elsereturn-1;}順序搜索圖示253457164809

012345data搜索

16i253457164809

i253457164809

i253457164809

i搜索成功2534571648

01234data搜索50i2534571648

i2534571648

i2534571648

i2534571648

i搜索失敗搜索成功的平均比較次數(shù)

若搜索概率相等，則

搜索不成功數(shù)據(jù)比較n

次按值查找：判斷x是否在表中

intIsIn(SeqList&L,ListDatax){ inti=0, found=0; while(i<L.length&&!found) if(L.data[i]!=x)i++; elsefound=1;returnfound;}求表的長(zhǎng)度

intLength(SeqList&L){returnL.length;}提取函數(shù)：在表中提取第i個(gè)元素的值

ListDataGetData(SeqList&L,inti){if(i>=0&&i<L.length)returnL.data[i];elseprintf(“參數(shù)

i不合理！\n”); }

按值查找：尋找x的后繼

intNext(SeqList&L,ListDatax){inti=Find(x);if(i>0&&i<L.length)returni+1; elsereturn-1;}尋找x的前驅(qū)

intPrevious(SeqList&L,ListDatax){inti=Find(x);if(i>0&&i<L.length)returni-1; elsereturn-1;}插入25345716480963

0123456750插入x2534575016480963

0123456750i順序表插入時(shí)，平均數(shù)據(jù)移動(dòng)次數(shù)AMN在各表項(xiàng)插入概率相等時(shí)順序表的插入

intInsert(SeqList&L,ListDatax,inti){

//在表中第i個(gè)位置插入新元素x

if(i<0||i>L.length||L.length==ListSize)return0;//插入不成功

else{ for(intj=L.length;j>i;j--) L.data[j]=L.data[j-1]; L.data[i]=x;L.length++; return1;//插入成功

}}刪除253457501648096316刪除

x2534575048096301234567順序表刪除平均數(shù)據(jù)移動(dòng)次數(shù)AMN在各表項(xiàng)刪除概率相等時(shí)順序表的刪除

intDelete(SeqList&L,ListDatax){

//在表中刪除已有元素x

inti=Find(L,x); //在表中查找xif(i>=0){ L.length--; for(intj=i;j<L.length;j++) L.data[j]=L.data[j+1];return1; //成功刪除

} return0;//表中沒有x}順序表的應(yīng)用:集合的“并”運(yùn)算voidUnion(SeqList&A,SeqList&B){intn=Length(A);intm=Length(B);for(inti=0;i<m;i++){ intx=GetData(B,i);//在B中取一元素

intk=Find(A,x);//在A中查找它

if(k==-1)//若未找到插入它

{Insert(A,x,n);n++;}}}集合的“交”運(yùn)算

voidIntersection(SeqList&A,SeqList&B){intn=Length(A);intm=Length(B);inti=0;while(i<n){intx=GetData(A,i);//在A中取一元素

intk=Find(B,x);//在B中查找它

if(k==-1){Delete(A,i);n--;} elsei++;//未找到在A中刪除它

}}順序表(SeqList)類的定義template<classType> classSeqList{Type*data;//順序表存儲(chǔ)數(shù)組

intMaxSize; //最大允許長(zhǎng)度

intlast; //當(dāng)前最后元素下標(biāo)public: SeqList(intMaxSize=defaultSize); ~SeqList(){delete[]data;}

intLength()const

{returnlast+1;

}C++描述

intFind(Type&x)const;//查找

intLocate(inti)const; //定位

intInsert(Type&x,inti);//插入

intRemove(Type

&x); //刪除

intNext(Type

&x); //后繼

intPrior(Type

&x);//前驅(qū)

intIsEmpty(){returnlast==-1;

} intIsFull(){returnlast==MaxSize-1;

}TypeGet(inti){//提取

returni<0||i>last？NULL:data[i];}}

C++描述順序表部分公共操作的實(shí)現(xiàn)

template<classType>

//構(gòu)造函數(shù)

SeqList<Type>::SeqList(intsz){if(sz>0){ MaxSize=sz;last=-1; data=newType[MaxSize];

if(data==NULL){MaxSize=0;last=-1;return;}

}}C++描述template<classType> intSeqList<Type>::Find(Type

&x)const{//搜索函數(shù)：在順序表中從頭查找結(jié)點(diǎn)值等于//給定值x的結(jié)點(diǎn)

inti=0;

while(i<=last&&data[i]!=x)i++;

if(i>last)return-1;

elsereturni; }C++描述template<classType>intSeqList<Type>::Insert(Type&x,inti){//在表中第

i個(gè)位置插入新元素

x

if(i<0

||

i>last+1

||

last==MaxSize-1)

return0;//插入不成功

else{last++;

for(intj=last;j>i;j--)data[j]=data[j-1]; data[i]=x;return1;//插入成功

}}C++描述

template<classType>intSeqList<Type>::Remove(Type&x){

//在表中刪除已有元素

x

inti=Find(x); //在表中搜索

x

if(i>=0){ last--;

for(intj=i;j<=last;j++)data[j]=data[j+1];

return1; //成功刪除

} return0;//表中沒有

x}C++描述順序表的應(yīng)用：集合的“并”運(yùn)算

voidUnion(SeqList<int>

&A,SeqList<int>

&B){

intn=A.Length();

intm=B.Length();

for(inti=0;i<m;i++){ intx=B.Get(i);//在B中取一元素

intk=A.Find(x);//在A中搜索它

if(k==-1)//若未找到插入它

{A.Insert(n,x);n++;}}}C++描述順序表的應(yīng)用：集合的“交”運(yùn)算

voidIntersection(SeqList<int>

&A,SeqList<int>

&B){

intn=A.Length();

intm=B.Length();inti=0;

while(i<n){intx=A.Get(i);//在A中取一元素

intk=B.Find(x);//在B中搜索它

if(k==-1){A.Remove(i);n--;} elsei++;//未找到在A中刪除它

}}C++描述鏈表（LinkedList）鏈表是線性表的鏈接存儲(chǔ)表示單鏈表靜態(tài)鏈表循環(huán)鏈表雙向鏈表單鏈表(SinglyLinkedList)定義：用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。例如：線性表ZHOU,ZHAO,SUN,WU,WANG,ZHANG,LI數(shù)據(jù)域指針域ZHANG13WANG1LInullZHAO37WU7ZHOU19SUN25存儲(chǔ)地址17131925313731頭指針表中節(jié)點(diǎn)位置6572413每個(gè)元素由結(jié)點(diǎn)(Node)構(gòu)成, 它包括兩個(gè)域:數(shù)據(jù)域Data和指針域Linkdatalink存儲(chǔ)結(jié)構(gòu)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)：存儲(chǔ)單元可以不連續(xù)。存取方式：順序存取。Node單鏈表結(jié)構(gòu)單鏈表的類型定義typedefcharListData;typedefstructnode{//鏈表結(jié)點(diǎn)

ListDatadata; //結(jié)點(diǎn)數(shù)據(jù)域

structnode*link;//結(jié)點(diǎn)鏈域}ListNode;typedefListNode*LinkList;//鏈表頭指針LinkListfirst;//鏈表頭指針單鏈表的類定義多個(gè)類表達(dá)一個(gè)概念(單鏈表)。鏈表結(jié)點(diǎn)(ListNode)類鏈表(List)類鏈表游標(biāo)(Iterator)類定義方式復(fù)合方式嵌套方式

繼承方式

classList;

//鏈表類定義（復(fù)合方式）

classListNode{

//鏈表結(jié)點(diǎn)類

friendclassList;

//鏈表類為其友元類

private:

intdata;

//結(jié)點(diǎn)數(shù)據(jù),整型

ListNode*link;

//結(jié)點(diǎn)指針

};classList{

//鏈表類

private:ListNode*first,*last;

//表頭指針};classList{

//鏈表類定義(嵌套方式)private:

classListNode{

//嵌套鏈表結(jié)點(diǎn)類

public:

intdata;

ListNode*link;

};ListNode*first,*last;

//表頭指針public:

//鏈表操作………};鏈表類和鏈表結(jié)點(diǎn)類定義(繼承方式)classListNode{

//鏈表結(jié)點(diǎn)類

protected:

intdata;

ListNode*link;

};classList:public

classListNode{

//鏈表類,繼承鏈表結(jié)點(diǎn)類的數(shù)據(jù)和操作

private:ListNode*first,*last;

//表頭指針};單鏈表的基本運(yùn)算插入（三種情況）

第一種情況：在第一個(gè)結(jié)點(diǎn)前插入

newnode->link=first;first=newnode;（插入前）（插入后）

firstnewnodenewnodefirst第二種情況：在鏈表中間插入

newnode->link=p->link; p->link=newnode；(插入前)(插入后)newnodepnewnodep第三種情況：在鏈表末尾插入

newnode->link=p->link; p->link=newnode；p(插入前)(插入后)newnodenewnodep算法描述intList::Insert(intx,inti){//在鏈表第

i個(gè)結(jié)點(diǎn)處插入新元素

x

ListNode*p=first;for(

k=0;k<i-1;k++)

//找第i-1個(gè)結(jié)點(diǎn)

if(p==NULL)break;

elsep=p->link;

if(p==NULL&&first!=NULL){

cout<<“無效的插入位置!\n”;return0;}

ListNode*newnode=

//創(chuàng)建新結(jié)點(diǎn)

newListNode(x,NULL);

if(first==NULL||i==0){

//插在表前

newnode->link=first; if(first==NULL)last=newnode;

first=newnode;}else{

//插在表中或末尾

newnode->link=p->link;

if(p->link==NULL)last=newnode;

p->link=newnode;}

return1;

}刪除 在單鏈表中刪除ai結(jié)點(diǎn)

q=p->link; p->link=q->link;刪除前刪除后ai-1aiai+1pqpai-1ai+1aiintList::Remove(inti){//在鏈表中刪除第i個(gè)結(jié)點(diǎn)

ListNode*p,*q;if(i==0)

//刪除表中第

1個(gè)結(jié)點(diǎn)

{q=first;p=first=first->link;}else{

p=first; intk=0;

//找第i-1個(gè)結(jié)點(diǎn)

while(p!=NULL&&k<i-1)

{p=p->link;k++;}if(p==NULL||p->link==NULL){cout<<“無效的刪除位置!\n”;return0;

}

else{

//刪除表中或表尾元素

q=p->link;

//重新鏈接

p->link=q->link;} if(

q==last)last=p; //可能修改last

Typex=q->data;deleteq;

//刪除q

returnx;

//返回第i個(gè)結(jié)點(diǎn)的值

}帶表頭結(jié)點(diǎn)的單鏈表表頭結(jié)點(diǎn)位于表的最前端，本身不帶數(shù)據(jù)，僅標(biāo)志表頭。設(shè)置表頭結(jié)點(diǎn)的目的:簡(jiǎn)化鏈表操作的實(shí)現(xiàn)。非空表空表^ana1firstfirst^插入

q->link=p->link; p->link=q;firstqfirstqfirstq^firstq^pppp插入前插入后表頭表尾qq插入pp表中intInsert(LinkListfirst,ListDatax,inti){//將新元素x插入在鏈表中第i號(hào)結(jié)點(diǎn)位置

ListNode*p=Locate(first,i-1);if(p==NULL)return0; //參數(shù)i值不合理返回0ListNode*newnode=//創(chuàng)建新結(jié)點(diǎn)

(ListNode*)malloc(sizeof(ListNode));newnode->data=x;newnode->link=p->link;//鏈入

p->link=newnode;return1; }刪除

q=p->link;p->link=q->link;deleteq;刪除前first(非空表）(空表）first^firstpq^pqfirst刪除后intdelete(LinkListfirst,inti){ //將鏈表第i號(hào)元素刪去

ListNode*p,*q p=Locate(first,i-1);//尋找第i-1個(gè)結(jié)點(diǎn)

if(p==NULL||p->link==NULL) return0;//i值不合理或空表

q=p->link; p->link=q->link;//刪除結(jié)點(diǎn)

free(q); //釋放

return1;}前插法建立單鏈表從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)：生成新結(jié)點(diǎn)將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中將該新結(jié)點(diǎn)插入到鏈表的前端直到讀入結(jié)束符為止。firstqfirstq^^LinkListcreateListF(void){charch;ListNode*q;LinkListhead=//建立表頭結(jié)點(diǎn)(LinkList)malloc(sizeof(ListNode));head->link=NULL;while((ch=getchar())!=‘\n’){q=(ListNode*)malloc(sizeof(ListNode));q->data=ch;//建立新結(jié)點(diǎn)

q->link=head->link;//插入到表前端

head->link=q;}returnhead;}后插法建立單鏈表每次將新結(jié)點(diǎn)加在鏈表的表尾；尾指針r,總是指向表中最后一個(gè)結(jié)點(diǎn)，新結(jié)點(diǎn)插在它的后面；^qfirst^r^first^rLinkListcreateListR(void){charch;LinkListhead=//建立表頭結(jié)點(diǎn)(LinkList)malloc(sizeof(ListNode));ListNode*q,*r=head; while((ch=getchar())!=‘\n’){q=(ListNode*)malloc(sizeof(ListNode));q->data=ch;//建立新結(jié)點(diǎn)

r->link=q;r=q;

//插入到表末端}

r->link=NULL;

returnhead;}單鏈表清空voidmakeEmpty(LinkListfirst){//刪去鏈表中除表頭結(jié)點(diǎn)外的所有其它結(jié)點(diǎn)

ListNode*q;while(first->link!=NULL){//當(dāng)鏈不空時(shí)，循環(huán)逐個(gè)刪去所有結(jié)點(diǎn)

q=first->link;first->link=q->link; free(q);//釋放

} last=first;}計(jì)算單鏈表長(zhǎng)度intLength(LinkListfirst){ListNode*p=first->link;//指針p指示第一個(gè)結(jié)點(diǎn)

intcount=0;while(p!=NULL){//逐個(gè)結(jié)點(diǎn)檢測(cè)

p=p->link;count++;} returncount;}

按值查找ListNode*Find(LinkListfirst,ListDatavalue){ //在鏈表中從頭搜索其數(shù)據(jù)值為value的結(jié)點(diǎn)

ListNode*p=first->link;

//指針p指示第一個(gè)結(jié)點(diǎn)

while(p!=NULL&&p->data!=value)p=p->link;returnp;}按序號(hào)查找（定位）

ListNode*Locate(LinkListfirst,inti){//返回表中第i個(gè)元素的地址

if(i<0)returnNULL;ListNode*p=first;intk=0;while(p!=NULL&&k<i){p=p->link;k++;} //找第i個(gè)結(jié)點(diǎn)

if(k==i)returnp;//返回第i個(gè)結(jié)點(diǎn)地址

elsereturnNULL;}1ZHANG2WANG6LI5ZHAO5WU-1CHEN31ZHANG2WANG3LI4ZHAO5WU-101234560123456修改前（插入chen,刪除zhao)修改后用一維數(shù)組描述線性鏈表靜態(tài)鏈表定義constintMaxSize=100;//靜態(tài)鏈表大小typedefintListData;typedefstructnode{//靜態(tài)鏈表結(jié)點(diǎn)

ListDatadata;

intlink;}SNode;typedefstruct{//靜態(tài)鏈表

SNodeNodes[MaxSize];intnewptr; //當(dāng)前可分配空間首地址}SLinkList;鏈表空間初始化voidInitList(SLinkList*SL){SL->Nodes[0].link=1;SL->newptr=1;//當(dāng)前可分配空間從1開始

//建立帶表頭結(jié)點(diǎn)的空鏈表

for(inti=1;i<MaxSize-1;i++)SL->Nodes[i].link=i+1;//構(gòu)成空閑鏈接表

SL->Nodes[MaxSize-1].link=-1;

//鏈表收尾}在靜態(tài)鏈表中查找具有給定值的結(jié)點(diǎn)intFind(SLinkListSL,ListDatax){intp=SL.Nodes[0].link;//指針p指向鏈表第一個(gè)結(jié)點(diǎn)

while(p!=-1)//逐個(gè)查找有給定值的結(jié)點(diǎn)

if(SL.Nodes[p].data!=x)p=SL.Nodes[p].link;elsebreak; returnp;}在靜態(tài)鏈表中查找第i個(gè)結(jié)點(diǎn)intLocate(SLinkListSL,inti){if(i<0)return-1;//參數(shù)不合理

intj=0,p=SL.Nodes[0].link;while(p!=-1&&j<i){//循環(huán)查找第i號(hào)結(jié)點(diǎn)

p=SL.Nodes[p].link;j++;}if(i==0)return0;returnp;}在靜態(tài)鏈表第i個(gè)結(jié)點(diǎn)處插入一個(gè)新結(jié)點(diǎn)intInsert(SLinkList*SL,inti,ListDatax){intp=Locate(SL,i-1);if(p==-1)return0;//找不到結(jié)點(diǎn)

intq=SL->newptr;//分配結(jié)點(diǎn)

SL->newptr=SL->Nodes[SL->newptr].link;SL->Nodes[q].data=x;

SL->Nodes[q].link=SL.Nodes[p].link;SL->Nodes[p].link=q;

//插入

return1;}在靜態(tài)鏈表中釋放第i個(gè)結(jié)點(diǎn)intRemove(SLinkList*SL,inti){intp=Locate(SL,i-1);if(p==-1)return0;//找不到結(jié)點(diǎn)

intq=SL->Nodes[p].link;//第i號(hào)結(jié)點(diǎn)

SL->Nodes[p].link=SL->Nodes[q].link;SL->Nodes[q].link=SL->newptr;//釋放

SL->newptr=q;return1;}循環(huán)鏈表(CircularList)特點(diǎn):最后一個(gè)結(jié)點(diǎn)的link指針不為NULL，而是指向頭結(jié)點(diǎn)。只要已知表中某一結(jié)點(diǎn)的地址，就可搜尋所有結(jié)點(diǎn)的地址。存儲(chǔ)結(jié)構(gòu):鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

帶表頭結(jié)點(diǎn)的循環(huán)鏈表an-1firsta1a0first(空表)(非空表)循環(huán)鏈表的插入template<classType>classCircList;template<classType>classCircListNode{friendclassCircList<Type>;public:CircListNode(Typed=0,CircListNode<Type>*next=NULL)

:data(d),link(next){}//構(gòu)造函數(shù)private:

Typedata; //結(jié)點(diǎn)數(shù)據(jù)

CircListNode<Type>*link;//鏈接指針}

循環(huán)鏈表類的定義template<classType>classCircList{private:CircListNode<Type>*first,*current,*last;

//鏈表的表頭指針、當(dāng)前指針和表尾指針public:CircList(Typevalue); ~CircList();

intLength()const; BooleanIsEmpty()

{returnfirst->link==first;

}BooleanFind(constType&value);

TypegetData

()const;

voidFirster(){current=first;} BooleanFirst();

BooleanNext();BooleanPrior(); voidInsert(constType&value);

voidRemove();

};搜索成功搜索不成功循環(huán)鏈表的搜索算法firstfirst3131484815155757搜索15搜索25currentcurrentcurrentcurrentcurrentcurrentcurrentcurrent循環(huán)鏈表的搜索算法template<classType>CircListNode<Type>*CircList<Type>::

Find(Typevalue

){//在鏈表中從頭搜索其數(shù)據(jù)值為value的結(jié)點(diǎn)

CircListNode<Type>*p=first->link;

//檢測(cè)指針

p

指示第一個(gè)結(jié)點(diǎn)

while(p!=first&&p->data!=value)

p=p->link;

returnp;}if(first!=NULL){

CircListNode<Type>*second=first->link;first->link=av;av=second;

first=NULL;}利用可利用空間表回收循環(huán)鏈表firstavfirstav回收前回收后if(av==NULL)newnode=newCircListNode<Type>;else{newnode=av;av=av->link;

}從可利用空間表分配結(jié)點(diǎn)avnewnodeav分配前的可利用空間表分配后的可利用空間表和新結(jié)點(diǎn)約瑟夫問題用循環(huán)鏈表求解約瑟夫問題n個(gè)人圍成一個(gè)圓圈，首先第1個(gè)人從1開始一個(gè)人一個(gè)人順時(shí)針報(bào)數(shù),報(bào)到第m個(gè)人，令其出列。然后再?gòu)南乱粋€(gè)人開始，從1順時(shí)針報(bào)數(shù)，報(bào)到第m個(gè)人，再令其出列，…，如此下去,直到圓圈中只剩一個(gè)人為止。此人即為優(yōu)勝者。例如n=8m=3約瑟夫問題的解法#include<iostream.h>#include“CircList.h”voidJosephus(intn,intm){for(inti=0;i<n-1;i++){//執(zhí)行n-1次

for(intj=0;j<m-1;j++)Next();

//數(shù)m-1個(gè)人

cout<<“Deleteperson”<<getData()<<endl;Remove();//刪去

}}voidmain(){CircList<int>clist; intn,m; cout<<“EntertheNumberofContestants?”;cin>>n>>m;for(inti=1;i<=n;i++)clist.insert(i);//形成約瑟夫環(huán)

clist.Josephus(n,m);//解決約瑟夫問題}多項(xiàng)式(Polynomial)n階多項(xiàng)式Pn(x)有n+1項(xiàng)。

系數(shù)a0,a1,a2,…,an

指數(shù)0,1,2,…,n。按升冪排列classPolynomial{public:Polynomial();//構(gòu)造函數(shù)

intoperator!();//判是否零多項(xiàng)式

floatCoef(inte);

intLeadExp();//返回最大指數(shù)

Polynomial

Add(Polynomial

poly);PolynomialMult(Polynomialpoly);

floatEval(floatx); //求值}多項(xiàng)式(Polynomial)的抽象數(shù)據(jù)類型

#include<iostream.h>classpower{

doublex;

inte;

doublemul;

public:

power(doubleval,intexp);

//構(gòu)造函數(shù)

doubleget_power(){returnmul;}

//取冪值

};創(chuàng)建power類，計(jì)算x的冪

power::power(doubleval,intexp){

//按val值計(jì)算乘冪

x=val;e=exp;mul=1.0;

if(exp==0)return;

for(;e