天津大學本科課程考研數(shù)據(jù)結構課件全

數(shù)據(jù)結構

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

數(shù)值性數(shù)據(jù)（整數(shù)、定點數(shù)、浮點數(shù)）非數(shù)值性數(shù)據(jù)（文字數(shù)據(jù)）數(shù)據(jù)元素（DataElement）數(shù)據(jù)的基本單位。在計算機程序中常作為一個整體進行考慮和處理。有時一個數(shù)據(jù)元素可以由若干數(shù)據(jù)項(DataItem)組成。數(shù)據(jù)項是具有獨立含義的最小標識單位。數(shù)據(jù)元素又稱為元素、結點、記錄數(shù)據(jù)項(DataItem)

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

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

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

Data_Structure={D,S}

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

線性表非線性結構

樹圖（或網(wǎng)絡）bindevetclibuser2114131211234678910315871011998745662313155線性結構樹形結構

樹二叉樹二叉排序樹堆結構123548711102916125643125436113318146651921圖結構網(wǎng)絡結構數(shù)據(jù)的存儲結構（物理結構）數(shù)據(jù)結構在計算機中的表示。數(shù)據(jù)的存儲結構依賴于計算機語言。

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

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

intcharfloatdoublevoid

整型字符型浮點型雙精度型無值抽象數(shù)據(jù)類型是指一個數(shù)學模型以及定義在此數(shù)學模型上的一組操作數(shù)據(jù)結構+定義在此數(shù)據(jù)結構上的一組操作=抽象數(shù)據(jù)類型例如：矩陣+（求轉置、加、乘、 求逆、求特征值） 構成一個矩陣的抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型的描述抽象數(shù)據(jù)類型可用（D，S，P）三元組表示 其中，D是數(shù)據(jù)對象，S是D上的關系集，P是對D的基本操作集。

ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對象：〈數(shù)據(jù)對象的定義〉

數(shù)據(jù)關系：〈數(shù)據(jù)關系的定義〉

基本操作：〈基本操作的定義〉 }ADT抽象數(shù)據(jù)類型名其中,數(shù)據(jù)對象、數(shù)據(jù)關系用偽碼描述；基本操作定義格式為 基本操作名（參數(shù)表） 初始條件：〈初始條件描述〉

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

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

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

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

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

對于所有的x,

y

NaturalNumber;

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

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)生五個階段：需求（輸入、輸出）設計（編寫算法）分析（選擇最佳算法）細化與編碼（編寫程序）驗證（程序驗證、測試、調試）算法分析算法定義：為了解決某類問題而規(guī)定的一個有限長的操作序列。特性：有窮性算法在執(zhí)行有窮步后能結束確定性每步定義都是確切、無歧義可行性每一條運算應足夠基本輸入有0個或多個輸入輸出有一個或多個輸出算法設計例子：

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

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

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

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

//對n個整數(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)境下通過簡單地代換，變成針對具體某種數(shù)據(jù)類型的類定義或算法例：求最大值max(a,b)宏定義：#definemax(a,b)((a)>(b)?(a):(b))缺點不能檢查數(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;}對于輸入max(3,5)和max(‘3’,’5’)的結果？例：求最大值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;}性能分析與度量算法的性能標準正確性：包括不含語法錯誤對幾組數(shù)據(jù)運行正確對典型、苛刻的數(shù)據(jù)運行正確；對所有數(shù)據(jù)運行正確可讀性效率：高效、低存儲需要。（算法執(zhí)行時間短，同時所占用的存儲空間小。健壯性：當輸入非法數(shù)據(jù)時，算法也能作出適當反應，而不會出現(xiàn)莫名其妙的輸出結果。算法的后期測試在算法中的某些部位插裝時間函數(shù)time

(),

測定算法完成某一功能所花費時間

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;}

算法的事前估計空間復雜度度量存儲空間的固定部分

程序指令代碼的空間，常數(shù)、簡單變量、定長成分(如數(shù)組元素、結構成分、對象的數(shù)據(jù)成員等)變量所占空間可變部分

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

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

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

其中,ai

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

存儲結構：數(shù)組。特點：線性表的順序存儲方式。存取方式：順序存取、隨機存取順序存儲結構示意圖458990674078

012345順序表的存儲方式：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//最大允許長度

typedefintListData;

typedefstruct

{

ListData*data;//存儲空間基址

intlength; //當前元素個數(shù)

}

SeqList;順序表基本運算初始化

voidInitList(SeqList&L){L.data=(ListData*)malloc(ListSize*sizeof(ListData));if(L.data==NULL){printf(“存儲分配失敗!\n”);exit(1);}L.length=0;}按值查找：找x在表中的位置，若查找成功，返回表項的位置，否則返回-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;}求表的長度

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

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的前驅

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

0123456750插入x2534575016480963

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

intInsert(SeqList&L,ListDatax,inti){

//在表中第i個位置插入新元素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ù)移動次數(shù)AMN在各表項刪除概率相等時順序表的刪除

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}順序表的應用:集合的“并”運算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++;}}}集合的“交”運算

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;//順序表存儲數(shù)組

intMaxSize; //最大允許長度

intlast; //當前最后元素下標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);//前驅

intIsEmpty(){returnlast==-1;

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

}TypeGet(inti){//提取

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

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

template<classType>

//構造函數(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ù)：在順序表中從頭查找結點值等于//給定值x的結點

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個位置插入新元素

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++描述順序表的應用：集合的“并”運算

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++描述順序表的應用：集合的“交”運算

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）鏈表是線性表的鏈接存儲表示單鏈表靜態(tài)鏈表循環(huán)鏈表雙向鏈表單鏈表(SinglyLinkedList)定義：用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。例如：線性表ZHOU,ZHAO,SUN,WU,WANG,ZHANG,LI數(shù)據(jù)域指針域ZHANG13WANG1LInullZHAO37WU7ZHOU19SUN25存儲地址17131925313731頭指針表中節(jié)點位置6572413每個元素由結點(Node)構成, 它包括兩個域:數(shù)據(jù)域Data和指針域Linkdatalink存儲結構：鏈式存儲結構特點：存儲單元可以不連續(xù)。存取方式：順序存取。Node單鏈表結構單鏈表的類型定義typedefcharListData;typedefstructnode{//鏈表結點

ListDatadata; //結點數(shù)據(jù)域

structnode*link;//結點鏈域}ListNode;typedefListNode*LinkList;//鏈表頭指針LinkListfirst;//鏈表頭指針單鏈表的類定義多個類表達一個概念(單鏈表)。鏈表結點(ListNode)類鏈表(List)類鏈表游標(Iterator)類定義方式復合方式嵌套方式

繼承方式

classList;

//鏈表類定義（復合方式）

classListNode{

//鏈表結點類

friendclassList;

//鏈表類為其友元類

private:

intdata;

//結點數(shù)據(jù),整型

ListNode*link;

//結點指針

};classList{

//鏈表類

private:ListNode*first,*last;

//表頭指針};classList{

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

classListNode{

//嵌套鏈表結點類

public:

intdata;

ListNode*link;

};ListNode*first,*last;

//表頭指針public:

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

//鏈表結點類

protected:

intdata;

ListNode*link;

};classList:public

classListNode{

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

private:ListNode*first,*last;

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

第一種情況：在第一個結點前插入

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個結點處插入新元素

x

ListNode*p=first;for(

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

//找第i-1個結點

if(p==NULL)break;

elsep=p->link;

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

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

ListNode*newnode=

//創(chuàng)建新結點

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結點

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

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

//刪除表中第

1個結點

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

p=first; intk=0;

//找第i-1個結點

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個結點的值

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

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

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

(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號元素刪去

ListNode*p,*q p=Locate(first,i-1);//尋找第i-1個結點

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

q=p->link; p->link=q->link;//刪除結點

free(q); //釋放

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

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

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

r->link=q;r=q;

//插入到表末端}

r->link=NULL;

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

ListNode*q;while(first->link!=NULL){//當鏈不空時，循環(huán)逐個刪去所有結點

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

} last=first;}計算單鏈表長度intLength(LinkListfirst){ListNode*p=first->link;//指針p指示第一個結點

intcount=0;while(p!=NULL){//逐個結點檢測

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

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

ListNode*p=first->link;

//指針p指示第一個結點

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

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

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

if(k==i)returnp;//返回第i個結點地址

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

ListDatadata;

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

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

//建立帶表頭結點的空鏈表

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

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

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

while(p!=-1)//逐個查找有給定值的結點

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

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

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

intq=SL->newptr;//分配結點

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個結點intRemove(SLinkList*SL,inti){intp=Locate(SL,i-1);if(p==-1)return0;//找不到結點

intq=SL->Nodes[p].link;//第i號結點

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

SL->newptr=q;return1;}循環(huán)鏈表(CircularList)特點:最后一個結點的link指針不為NULL，而是指向頭結點。只要已知表中某一結點的地址，就可搜尋所有結點的地址。存儲結構:鏈式存儲結構

帶表頭結點的循環(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){}//構造函數(shù)private:

Typedata; //結點數(shù)據(jù)

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

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

//鏈表的表頭指針、當前指針和表尾指針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的結點

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

//檢測指針

p

指示第一個結點

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;

}從可利用空間表分配結點avnewnodeav分配前的可利用空間表分配后的可利用空間表和新結點約瑟夫問題用循環(huán)鏈表求解約瑟夫問題n個人圍成一個圓圈，首先第1個人從1開始一個人一個人順時針報數(shù),報到第m個人，令其出列。然后再從下一個人開始，從1順時針報數(shù)，報到第m個人，再令其出列，…，如此下去,直到圓圈中只剩一個人為止。此人即為優(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個人

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);//解決約瑟夫問題}多項式(Polynomial)n階多項式Pn(x)有n+1項。

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

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

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

floatCoef(inte);

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

Polynomial

Add(Polynomial

poly);PolynomialMult(Polynomialpoly);

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

#include<iostream.h>classpower{

doublex;

inte;

doublemul;

public:

power(doubleval,intexp);

//構造函數(shù)

doubleget_power(){returnmul;}

//取冪值

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

power::power(doubleval,intexp){

//按val值計算乘冪

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

if(exp==0)return;

for(;e