數(shù)據(jù)結構與算法實踐指導 課件匯 張彬連 1-順序表-5 二叉樹

第1章

順序表主講教師：張彬連吉首大學1.1知識簡介1.1.1順序表結構

線性表的順序表示稱為順序存儲結構或順序映像，把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中，即邏輯上相鄰，物理上也相鄰。順序存儲是用一組地址連續(xù)的存儲單元依次存儲線性表的元素。1.1知識簡介1.1.1順序表結構

如有n個元素的線性表(a1，a2，…，ai-1，ai，…，an)的順序存儲如下圖所示。12…i-1i…na1a2…ai-1ai

…an

假設用Loc(ai)表示第i個數(shù)據(jù)元素的存儲位置，Loc(a1)就表示第一個數(shù)據(jù)元素的存儲位置，每個元素占c個存儲單元，則有：

1.1知識簡介1.1.1順序表結構

每個數(shù)據(jù)元素的存儲位置和起始位置相差一個常數(shù)，這個常數(shù)和數(shù)據(jù)元素在線性表中的位序成正比。因此，只要確定了起始位置，線性表中的任一數(shù)據(jù)元素都可以隨機存取，所以順序表是一種隨機存取的存儲結構。1.1知識簡介1.1.2順序表的表示

順序表有兩種表示方式：

靜態(tài)順序表（長度是固定的）

動態(tài)順序表（長度可以自己定義）1.1知識簡介1.1.2順序表的表示

靜態(tài)順序表定義如下：#defineMAXSIZE100//線性表的最大長度typedefstructSqList{ElemTypeelem[MAXLEN];//存放順序表中的元素intlength;//順序表中元素的個數(shù)}SqList;

采用這種方式定義順序表時，表中元素的最大個數(shù)是確定的，在程序中不能被修改。如有定義SqListL，則L是一個靜態(tài)順序表，最多可放100個元素。1.1知識簡介1.1.2順序表的表示

動態(tài)順序表定義如下：#defineMAXSIZE100//線性表的最大長度typedefstructSqList{ElemType*elem;//順序表中存放元素空間首地址intlength;//順序表中元素的個數(shù)intsize;//順序表的大小}SqList;

采用這種方式定義順序表時，表中元素的最大個數(shù)可以根據(jù)需要定義，在程序中也可根據(jù)需要進行擴充。其中size表示順序表可以存儲的數(shù)據(jù)元素個數(shù)，如果空間不夠時不考慮擴充空間，size可以不定義。1.1知識簡介1.1.2順序表的表示

由于elem是指針類型，定義SqListL后，順序表L中存放數(shù)據(jù)元素的空間沒有分配，需要動態(tài)分配空間?？梢远x一個初始化順序表L的函數(shù)InitSqList(SqList&L)，函數(shù)可以定義如下：intInitSqList(SqList&L){L.elem=(ElemType*)malloc(MAXSIZE*sizeof(ElemType));If(L.elem==NULL)exit(-1);//退出程序L.length=0；//初始長度為0return1；}1.1知識簡介1.1.2順序表的表示

InitSqList()函數(shù)中使用了malloc()函數(shù)動態(tài)申請空間，所以在程序結束之前的某個位置應該將這些內(nèi)存空間釋放，否則會導致內(nèi)存泄漏。C語言中用free()釋放malloc()申請的內(nèi)存，定義釋放順序表L內(nèi)存的函數(shù)DestroySqList(SqList&L)，函數(shù)可以定義如下：voidDestroySqList(SqList&L)//釋放順序表L中申請的內(nèi)存{if(L.elem!=NULL)//如果elem指向的內(nèi)存沒有被釋放{free(L.elem);//釋放elem指向的內(nèi)存L.elem=NULL;//釋放內(nèi)存之后，賦值L.elem為NULL}}1.1知識簡介1.1.2順序表的表示需要注意的是ElemType是元素類型，它是一個抽象的概念，可以表示任何類型的元素。例如線性表中存放整數(shù)，則可在定義之前加入typedefintElemType，元素類型就變?yōu)檎?，也可以在定義順序表的時候將ElemType修改為自己需要的類型。1.2實驗目的

本章的實驗案例是以順序表作為存儲結構，通過本章的實驗加深對順序表的理解，培養(yǎng)以順序表作為線性表的存儲結構解決實際問題的能力，并能分析其時間和空間復雜度，同時鍛煉學生實際編程和算法設計的能力。1.3實驗范例

一個班有50個學生，每個學生的信息有學號、姓名和性別，現(xiàn)在有大學英語和高等數(shù)學兩門課程組織了考試，每個學生獲得了相應的成績，如下表所示。要求設計一個簡單的管理系統(tǒng)對學生信息進行管理。要求用順序表實現(xiàn)。學號姓名性別大學英語高等數(shù)學2023001AlanF93882023002DanieM75692023003PeterM56772023004BillF87902023005HelenM79862023006AmyF68751.3實驗范例

初始化順序表：要求建立一個長度為0的順序表，用來存放學生的信息。1.3.1范例11.3實驗范例1、問題分析1.3.1范例1

先需要定義順序表類型，順序表中每個元素用來存儲一個學生的信息，需要定義結構體類型，ElemType代表該結構體類型。然后初始化順序表L，分配能放MAXSIZE學生信息的空間。初始化時并沒有輸入學生信息，因此將順序表的有效元素個數(shù)length初始化為0。1.3實驗范例2、算法描述1.3.1范例1

先定義結構體類型，包含學號、姓名、大學英語成績、高等數(shù)學成績，結構體定義如下：typedefstructStudent{charNo[8];//學號charname[16];//姓名charsex;//性別intenglish;//大學英語成績intmath;//高等數(shù)學成績}Student;1.3實驗范例2、算法描述1.3.1范例1

在本實驗中當空間不夠時，不考慮追加空間，所以順序表SqList中不需要定義size成員。順序表SqList定義如下：typedefstructSqList{Student*elem;//存放學生信息空間的首地址

intlength;//存放的學生人數(shù)}SqList;1.3實驗范例2、算法描述1.3.1范例1

在本實驗中當空間不夠時，不考慮追加空間，所以順序表SqList中不需要定義size成員。順序表SqList定義如下：或者：typedefStudentElemType;typedefstructSqList{ElemType*elem;//存放學生信息空間的首地址

intlength;//存放的學生人數(shù)}SqList;1.3實驗范例2、算法描述1.3.1范例1

順序表類型定義好之后，定義函數(shù)InitSqList(SqList&L)對順序表L進行初始化。該函數(shù)先新申請可以存放MAXSIZE個Student變量（或對象）的空間，將順序表L的初始長度length設置為0。InitSqList()函數(shù)可以定義如下：intInitSqList(SqList&L)//初始化順序表L{L.elem=(Student*)malloc(MAXSIZE*sizeof(Student));if(L.elem==NULL)exit(-1);//退出程序L.length=0;//初始長度為0return1;}1.3實驗范例3、算法分析1.3.1范例1

用InitSqList()函數(shù)初始化順序表L時，只需申請空間并設置length的值，每個語句最多執(zhí)行1次。因此，該函數(shù)的時間復雜度為O(1)。1.3實驗范例

輸入n個學生的信息：要求把n（例如n=50）個學生的信息輸入到順序表mylist中，每個學生的信息按學號、姓名、英語成績、數(shù)學成績的次序輸入。1.3.2范例21.3實驗范例1、問題分析1.3.2范例2

范例1已經(jīng)定義了順序表mylist可用于存放學生信息，現(xiàn)要求輸入n個學生的信息。輸入過程用循環(huán)實現(xiàn)，一個學生即為一個元素，在循環(huán)內(nèi)一次輸入一個學生信息，總共執(zhí)行n次即可。因此，可設計一個函數(shù)InputSqList(SqList&L,intn)實現(xiàn)在L中添加n個元素。為了檢測數(shù)據(jù)是否輸入正確，可以將順序表中的信息輸出，定義函數(shù)PrintListInfo(SqListL)輸出順序表中存儲的學生信息。1.3實驗范例2、算法描述1.3.2范例2

Student類型中學號和姓名是字符數(shù)組，性別是字符型，為了保證在輸入過程中輸入的字符正確，在輸入學號、姓名和性別之前調用fflush(stdin)來清空輸入緩沖區(qū)。InputSqList(SqList&L,intn)函數(shù)可以定義如下：voidInputSqList(SqList&L,intn){inti;for(i=0;i<n;i++){//以下讀入第i個學生的信息printf("第%d個學生的信息\n",i+1);fflush(stdin);//清空輸入緩沖區(qū)printf("學號:");gets(L.elem[i].No);printf("姓名:");fflush(stdin);gets(L.elem[i].name);printf("性別：");scanf("%c",&L.elem[i].sex);printf("大學英語成績：");scanf("%d",&L.elem[i].english);printf("高等數(shù)學成績：");scanf("%d",&L.elem[i].math);}L.length=n;//有效數(shù)據(jù)長度為n}1.3實驗范例2、算法描述1.3.2范例2

需要注意的是在InputSqList()函數(shù)中沒有對數(shù)據(jù)的合法性進行驗證。在對數(shù)據(jù)進行輸入的時候，可以定義一個函數(shù)InputOneStu(Student&stu)用于輸入一個學生的數(shù)據(jù)：voidInputOneStu(Student&stu){fflush(stdin);//清空輸入緩沖區(qū)printf("學號:");gets(stu.No);fflush(stdin);printf("姓名:");fflush(stdin);

gets();printf("性別：");scanf("%c",&stu.sex);printf("大學英語成績：");scanf("%d",&stu.english);printf("高等數(shù)學成績：");scanf("%d",&stu.math);}1.3實驗范例2、算法描述1.3.2范例2InputSqList(SqList&L,intn)函數(shù)可改寫成如下形式：voidInputSqList(SqList&L,intn){inti;Studenttmpstu;for(i=0;i<n;i++){InputOneStu(tmpstu);L.elem[i]=tmpstu;}L.length=n；//有效數(shù)據(jù)長度為n}1.3實驗范例2、算法描述1.3.2范例2

如果Student內(nèi)部包含指針變量，例如學生信息還包含家庭地址的信息，這個家庭地址定義為字符指針變量，如char*address。在給address賦值時，需給該指針分配空間，然后調用strcpy函數(shù)將家庭地址信息復制到該空間中。此時需要定義函數(shù)來實現(xiàn)數(shù)據(jù)元素賦值，假設定義函數(shù)CopyStu(Student&this_stu,Student&other_stu)實現(xiàn)，在輸入學生信息是調用該函數(shù)CopyStu(L.elem[i],tmpstu)代替語句L.elem[i]=tmpstu實現(xiàn)賦值。1.3實驗范例3、算法分析1.3.2范例2InputOneStu()函數(shù)在讀入一個學生的數(shù)據(jù)時函數(shù)內(nèi)每個語句執(zhí)行1次，因此InputOneStu()函數(shù)的時間復雜度為O(1)。InputSqList()函數(shù)需要讀入n個學生的數(shù)據(jù)，即需調用InputOneStu()函數(shù)n次。因此，InputSqList()函數(shù)的時間復雜度為O(1*n)，即O(n)。1.3實驗范例

查找學生的信息：要求在順序表中查找某一姓名（如姓名為“Peter”）的同學的信息，并把查到的信息顯示出來。1.3.3范例31.3實驗范例1、問題分析1.3.3范例3

查找過程：可以從順序表中的第一個元素開始往后查找，比較該元素中的姓名是否為要找的姓名，如果順序表中某個元素的姓名等于要找的姓名，則輸出該數(shù)據(jù)元素的信息。1.3實驗范例1、問題分析1.3.3范例3

可以從順序表中L.elem[0]開始，比較該元素的姓名是否為要查找的姓名name，由于name是字符數(shù)組，比較需要調用strcmp()函數(shù)來實現(xiàn)。判斷strcmp(L.elem[0].name,name)的結果是否為0，如果結果為0則L.elem[0]元素中的姓名和要查找的姓名相等。如果L.elem[0]中的姓名和要查找的姓名不同，就繼續(xù)將L.elem[1]中的姓名進行比較，以此類推。因此，可以定義一個循環(huán)變量i，i從0開始一直到L.length-1，比較L.elem[i]中的姓名是否為要找的姓名，如果找到則輸出相關信息。1.3實驗范例2、算法描述1.3.3范例3

在順序表L中，查找姓名為name的學生，如果找到則輸出其信息。函數(shù)定義如下：voidSearchElemSqList(SqListL,char*name){inti;

//從第一個學生開始往后查看

for(i=0;i<L.length;i++){

//如果有姓名為參數(shù)name的同學

if(strcmp(L.elem[i].name,name)==0){printf("學號：%s\n",L.elem[i].No);printf("姓名：%s\n",L.elem[i].name);printf("性別：%c\n",L.elem[i].sex);

printf("大學英語成績：%d\n",L.elem[i].english);

printf("高等數(shù)學成績：%d\n",L.elem[i].math);

}

}}1.3實驗范例2、算法描述1.3.3范例3SearchElemSqList()函數(shù)實現(xiàn)了查找和輸出數(shù)據(jù)元素信息兩個功能，不符合模塊化設計思想?？梢赃M一步將其輸出信息部分從函數(shù)中去掉，當找到名為”Peter”的同學之后即返回該元素的下標。如果整個表都查找完了，還找不到”Peter”，則返回-1（-1是一個不存在的下標）。1.3實驗范例2、算法描述1.3.3范例3SearchElemSqList函數(shù)可以改寫如下：intSearchElemSqList(SqListL,char*name){inti;for(i=0;i<L.length;i++){if(strcmp(L.elem[i].name,name)==0)//有姓名為參數(shù)name的同學returni;//返回元素所在的位置（下標）}return-1;}1.3實驗范例2、算法描述1.3.3范例3

對于原來的輸出部分，設計一個函數(shù)PrintStuInfo(SqListL,inti)用于輸出順序表L中的第i個元素的信息。PrintStuInfo(SqListL,inti)函數(shù)可以定義如下：voidPrintStuInfo(SqListL,inti){printf("學號：%s\n",L.elem[i].No);printf("姓名：%s\n",L.elem[i].name);printf("性別：%c\n",L.elem[i].sex);printf("大學英語成績：%d\n",L.elem[i].english);printf("高等數(shù)學成績：%d\n",L.elem[i].math);}1.3實驗范例3、算法分析1.3.3范例3SearchElemSqList()函數(shù)需要從第一個學生開始進行查看，在最壞的情況下需要查看所有學生的信息。因此，SearchElemSqList()函數(shù)的時間復雜度為O(n)。1.3實驗范例

插入一個學生的信息：要求在第i個位置插入一個學生的信息，原來的第i個位置及其之后的學生都往后移動一個位置。1.3.4范例41.3實驗范例1、問題分析1.3.4范例4

假設要在第2個位置插入一個新的元素（即在L.elem[1]的位置插入一個新的學生信息），需要從最后一個元素開始往后移動，即先把L.elem[length-1]移動到L.elem[length]的地方，最后把原L.elem[1]移動到L.elem[2]的地方。該移動元素的操作需要用循環(huán)來實現(xiàn)，用for循環(huán)實現(xiàn)如下：for(j=L.length-1;j>=i-1;j--)

L.elem[j+1]=L.elem[j];

當元素移動完之后，再把新的元素存入第2個位置，用語句L.elem[i-1]=stu;（stu為新加入的學生信息）。當新的學生信息被加入之后，順序表的有效長度應該增加1。1.3實驗范例1、問題分析1.3.4范例4并不是所有情況都能插入。所以在移動元素之前需判斷該元素是否能插入到順序表中。不能插入的情況有如下四種：（1）當i<=0時，插入的位置不正確。（2）當i>=MAXSIZE時，插入的位置也不正確，因為這個位置已經(jīng)超過了順序表的長度范圍。（3）即使i的位置正確，但順序表已經(jīng)滿了，即L.length=MAXSIZE。對于這種情況，可以把L中最后一個元素擠出，也可以提示操作失敗。在本例中，我們將這種情況視為操作失敗。1.3實驗范例1、問題分析1.3.4范例4并不是所有情況都能插入。所以在移動元素之前需判斷該元素是否能插入到順序表中。不能插入的情況有如下四種：（4）當L.length<i<MAXSIZE時，將元素插入到length之后的位置，不需要移動元素。例如順序表L中最多可以存放50個元素，插入之前L中已經(jīng)有10個元素，現(xiàn)要求將新的元素插入到第15個位置，即給出的i=15。對于這種情況，可以在程序中提示給出的i錯誤，也可以把新的元素直接加入到L的最后面。在本例中將把新元素加到L的最后面。1.3實驗范例2、算法描述1.3.4范例4

定義函數(shù)intInsertElemSqList(SqList&L,Studentstu,inti)實現(xiàn)在順序表L中的第i個位置插入學生信息為stu的元素。函數(shù)可以定義如下：intInsertElemSqList(SqList&L,Studentstu,inti){//插入位置不在1到MAXSIZE之間，或者空間不夠if(i<1||i>MAXSIZE||L.length==MAXSIZE)return0;//空間夠但是位置不在1-L.length之間，插入到最后一個元素后面if(i>L.length&&i<=MAXSIZE){L.elem[L.length]=stu;L.length++;return1;

}1.3實驗范例2、算法描述1.3.4范例4

定義函數(shù)intInsertElemSqList(SqList&L,Studentstu,inti)實現(xiàn)在順序表L中的第i個位置插入學生信息為stu的元素。函數(shù)可以定義如下：intInsertElemSqList(SqList&L,Studentstu,inti){……

//將元素L.elem[L.length-1]到L.elem[i-1]逐個往后移動一個位置for(intj=L.length-1;j>=i-1;j--)L.elem[j+1]=L.elem[j];L.elem[i-1]=stu;//將x插入到順序表中L.length++;//順序表L的長度加1return1;}1.3實驗范例3、算法分析1.3.4范例4InsertElemSqList()函數(shù)需要從最后一個元素開始將元素逐個往后移動，在最壞的情況下所有學生的信息都要被移動。因此，InsertElemSqList()函數(shù)的時間復雜度為O(n)。1.4實驗任務完成下列任務，并分析各算法的時間復雜度。任務1：按表格的方式打印顯示序順序表L中的所有信息。要求：設計一個表頭，即第一行顯示“學號

姓名

性別

英語

數(shù)學

總成績”，然后將每個學生的信息打印一行，盡量使打印出的信息與表頭對應項對齊。任務2：寫一個函數(shù)刪除順序表L中某一元素。要求：因有學生留級或轉學，需要將該學生信息從表L中去掉。即給出一個學號，刪除該學號的學生信息。1.4實驗任務完成下列任務，并分析各算法的時間復雜度。任務3：在有序的順序表中加入元素后，使表仍然有序。要求：重新初始化線性表L，要求每次加入新的學生信息后，線性表L中的元素按總成績從高到低排列。任務4：將線性表中L的數(shù)據(jù)保存到一個磁盤文件中。要求：創(chuàng)建一個磁盤文件，將線性表L中的元素按次序寫入一個文件中，下次實驗可以讀出該文件中的數(shù)據(jù)。1.5任務提示

任務1要求打印顯示學生信息，可以設計一個函數(shù)ShowStuInfo(SqList&L)顯示L中的信息。該函數(shù)先打印表頭，然后逐行打印每個學生的信息。ShowStuInfo(SqList&L)函數(shù)可設計如下：任務1提示voidShowStuInfo(SqList&L){ShowTitle();//顯示表頭標題for(i=0;i<L.length;i++)

ShowOneStuInfo(L.elem[i]);//顯示一個學生的信息}

然后在ShowTitle()函數(shù)和ShowOneStuInfo()函數(shù)中對數(shù)據(jù)進行格式化即可，比較簡單的方法是使用“\t”將數(shù)據(jù)對齊。1.5任務提示

從順序表L的第一個元素開始，依次將學生的學號和給出的學號stuNo進行比較，如果相等，則將該元素后面的元素都往前移一個位置，同時順序表的長度減1?？梢栽O計函數(shù)DeleteElemSqList(SqList&L,char*stuNo)來刪除順序表L中學號為stuNo的學生。任務2提示1.5任務提示

函數(shù)可設計如下：任務2提示voidDeleteElemSqList(SqList&L,char*stuNo){i=0;while(i<=L.length-1){

//如果第i個元素值與e相等

if(strcmp(L.elem[i].No,stuNo)==0)

{

//將i之后的所有元素逐個往前移動//將有序順序表的表長減1return;//元素被刪除之后即可返回

}

else

i++;

}}1.5任務提示

先初始化一個順序表L，然后設計一個添加元素的算法（函數(shù)），當添加一個元素后順序表L內(nèi)的元素仍然有序，重復調用這個函數(shù)n次即可以建立一個長度為n的順序表。本任務要求順序表內(nèi)學生的總成績從高到低排序，當添加一個元素時順序表的情況如下：

（1）順序表當前為空，則直接將新的元素加入到第一個位置，即L.elem[0]的位置。

（2）順序表當前不為空，即L.elem[0]到L.elem[L.length-1]中有元素，且有序?，F(xiàn)在一個新學生stu的信息要加入到有序順序表L中，可以從順序表當前最后一個元素開始，如果該位置元素的總成績小于stu的總成績就往后移一個位置，直到某個位置元素的總成績大于stu的總裁成績，然后把stu加入到該元素的后面。任務3提示1.5任務提示

經(jīng)以上分析，添加一個學生信息的函數(shù)可設計如下：任務3提示intInsertElemSqList(SqList&L,Studentstu){intj;if(L.length==0){L.elem[0]=stu;L.length=1;return1;}j=L.length-1;while(j>=0&&stu.english+stu.math>L.elem[j].english+L.elem[j].math){L.elem[j+1]=L.elem[j];j=j-1;}L.elem[j+1]=stu;return1;}1.5任務提示

需要注意的是在InsertElemSqList()函數(shù)中沒有考慮元素個數(shù)超出界限的情況，即沒有處理順序表已經(jīng)滿了還繼續(xù)添加元素的情況，請讀者自己補充相關代碼。任務3提示1.5任務提示

本任務要求將順序表中所有學生數(shù)據(jù)寫入到磁盤文件，設計一個參考函數(shù)如下：任務4提示voidWriteElemToFile(SqList&L,char*filename){將數(shù)據(jù)寫入文件的步驟。1、定義文件指針。2、打開文件，可以采用兩種格式寫入：文本文件和二進制文件的形式。3、向文件寫數(shù)據(jù)，用一個for循環(huán)將L.elem[i]逐個寫入到文件。4、關閉文件。}第2章

鏈表主講教師：張彬連吉首大學2.1知識簡介

線性表的鏈式表示又稱為非順序映像。鏈式存儲是指元素在存儲器中的位置是任意的，也就是說邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。數(shù)據(jù)元素之間的先后關系通過指針來實現(xiàn)。常見的鏈表形式有單鏈表和雙鏈表。2.1知識簡介2.1.1單鏈表

為了表示相鄰兩個元素之間前驅和后繼的邏輯關系，每個數(shù)據(jù)元素除了存儲本身的信息之外，還需存儲其后繼元素的存儲位置。這兩個部分就組成了數(shù)據(jù)元素的存儲映像，稱為結點（node）。結點包括數(shù)據(jù)域和指針域，其中數(shù)據(jù)域用來存儲數(shù)據(jù)元素的信息，指針域用來存儲后繼元素的存儲位置。每個結點只有一個指針域的鏈表稱為單鏈表，單鏈表結點結構如下圖所示。2.1知識簡介2.1.1單鏈表

單鏈表結點結構定義如下：typedefstructLNode{ ElemTypedata;//數(shù)據(jù)域structLNode*next;//指針域}LNode,*LinkList;2.1知識簡介2.1.1單鏈表

當應用鏈表時，為了使鏈表的第一個結點和其他結點的處理一致，通常在鏈表的第一個結點之前加一個頭結點，這個頭結點的結構可以與其它結點相同，也可以和其它結點不同，一般情況頭結點和鏈表中其他結點類型一致。如有n個數(shù)據(jù)元素的線性表（a1,a2,……,an），帶頭結點的單鏈表結構如下圖所示。

單鏈表可以用頭指針的名字來命名，上圖中指向頭結點的指針名為L，則該鏈表稱為單鏈表L。2.1知識簡介2.1.1單鏈表

在實際應用中，一般使用指針訪問鏈表。如下圖，用指針p指向第i-1個元素，則有p->data=ai-1，p->next為下一個元素的地址，即第i個元素的位置。從而p->next->data=ai。如果想要取得第i個元素，必須先找到第i-1個元素的地址。同理如果想要找到第i-1個元素，必須先找到第i-2個元素的地址。依次往前，直到找到頭指針。在單鏈表中，想要取得第i個元素，必須從頭指針出發(fā)順鏈進行尋找。2.1知識簡介2.1.1單鏈表

如果指針p指向第i-1個元素，將p指向第i個元素的操作為：p=p->next。一般而言，可以先讓p指向頭結點，然后在一定的條件下將p往后移動到需要的位置。一個可參考的程序段如下：p=L;//先讓p指向頭結點while(p滿足某個條件){……//其他語句p=p->next;//將p往后移動……//其他語句}

對于一個鏈表，經(jīng)常需要進行查找、插入、刪除等操作。查找操作可以通過上面給出的參考程序段進行擴充實現(xiàn)。2.1知識簡介2.1.1單鏈表

對于插入操作而言，一般是在某個結點之后插入一個新結點，如在p結點之后插入一個新結點的基本方法如下：

（1）先將要插入的元素組裝成一個新結點q。

（2）新結點q的下一個結點的地址賦值為為原來p結點的下一個結點的地址。

（3）原來p結點的下一個結點賦值為新結點q。2.1知識簡介2.1.1單鏈表以上3步對應的語句為：q=(LNode*)malloc(sizeof(LNode));q->data=給定的值;q->next=p->next;p->next=q;

因此，當插入新結點時，務必先找到插入的位置，即它前面那個結點。此外，當新結點被malloc()函數(shù)或new操作創(chuàng)建后，應該及時給它賦值。2.1知識簡介2.1.1單鏈表

對于刪除操作而言，一般是刪除某個結點之后的一個結點，如刪除p結點之后的一個結點的基本方法如下：

（1）先用一個指針變量q指向要刪除的結點。

（2）因為q最終會被刪除，p的下一個結點的地址賦值為q結點的下一個結點的地址。

（3）釋放q指向的結點的空間。2.1知識簡介2.1.1單鏈表以上3步對應的語句為：q=p->next;p->next=q->next;free(q);

為了刪除單鏈表中的某個結點，應該先找到它的前面那個結點。此外，在刪除結點時，要及時調用free()函數(shù)或new操作釋放結點所占用的內(nèi)存空間。2.1知識簡介2.1.2雙鏈表

雙鏈表也就是雙向鏈表，它的每個結點中都有兩個指針，分別指向它的直接后繼和直接前驅，其結點結構如下圖所示。

從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。一般構造雙向循環(huán)鏈表，讓最后一個結點的后繼指針域指向頭結點，頭結點的前驅指針域指向最后一個結點。下圖所示為有n個元素帶頭結點的雙向鏈表L。2.1知識簡介2.1.2雙鏈表（1）雙向循環(huán)鏈表初始化

初始化雙向循環(huán)鏈表就是建立只有頭結點的雙向循環(huán)鏈表?？盏碾p向循環(huán)鏈表結構如下圖所示。初始化時先生成頭結點L，然后將頭結點的next和prior域分別指向頭結點。2.1知識簡介2.1.2雙鏈表（1）雙向循環(huán)鏈表初始化

初始化L的主要代碼如下：

L=(DuLNode*)malloc(sizeof(DuLNode));//成頭結點L

L->next=L;//指針域指向頭結點

L->prior=L;//指針域指向頭結點2.1知識簡介2.1.2雙鏈表（2）雙向循環(huán)鏈表建立

和單鏈表建立類似，建立雙向循環(huán)鏈表的過程也是一個結點“逐個插入”的過程。先建立一個只含頭結點的雙向循環(huán)鏈表，然后依次生成新結點，不斷地將其插入到鏈表的頭部或尾部，分別稱其為“頭插法”和“尾插法”。2.1知識簡介2.1.2雙鏈表（2）雙向循環(huán)鏈表建立

用尾插法將結點p插入雙向循環(huán)鏈表如下圖所示：p->prior=L->prior；p->next=L；L->prior->next=p；L->prior=p；2.1知識簡介2.1.2雙鏈表（2）雙向循環(huán)鏈表建立

當掌握了將一個結點加入到鏈表尾部之后，應用該方法創(chuàng)建雙鏈表的方法可參考如下代碼。StatusCreateDuLLinkList(DuLCirLinkList&L){scanf("%d",&length);for(i=1;i<=length;i++){//生成插入的結點DuLNode*p=(DuLNode*)malloc(sizeof(DuLNode));

輸入數(shù)據(jù)元素的信息;2.1知識簡介2.1.2雙鏈表（2）雙向循環(huán)鏈表建立

當掌握了將一個結點加入到鏈表尾部之后，應用該方法創(chuàng)建雙鏈表的方法可參考如下代碼。StatusCreateDuLLinkList(DuLCirLinkList&L){p->prior=L->prior;p->next=L;L->prior->next=p;L->prior=p;}returnOK;}2.1知識簡介2.1.2雙鏈表（3）在雙向循環(huán)鏈表中查找元素

鏈表是一種"順序存取"的結構，要在帶頭結點的雙向循環(huán)鏈表中查找和給定值x相等的元素，必須從頭結點開始沿著后繼指針依次比較，直到找到值相等的結點為止，如果查找成功，則返回元素的序號，否則返回0。2.1知識簡介2.1.2雙鏈表（3）在雙向循環(huán)鏈表中查找元素intLocateElem(DuLCirLinkListL,DElemTypex){//從第一個元素開始p=L->next;j=0;//計數(shù)器初始化while(p!=L){j++;if(p->data==x){break;

}p=p->next;}//找到則返回計數(shù)器j的值，否則返回0if(p!=L)returnj;elsereturn0;}如果需要返回結點的地址，則將函數(shù)返回類型改成DuLNode*類型。如果找到則返回p，否則返回NULL。2.2實驗目的

本章的實驗案例是以鏈表作為存儲結構，通過本章的實驗加深對鏈表的理解，培養(yǎng)以鏈表作為線性表的存儲結構解決實際問題的應用能力，同時鍛煉學生實際編程和算法設計的能力。2.3實驗范例

一個班有50個學生，每個學生的信息有學號、姓名和性別，現(xiàn)在有大學英語和高等數(shù)學兩門課程組織了考試，每個學生獲得了相應的成績，如下表所示。要求設計一個簡單的管理系統(tǒng)對學生信息進行管理。要求用鏈表實現(xiàn)。學號姓名性別大學英語高等數(shù)學2023001AlanF93882023002DanieM75692023003PeterM56772023004BillF87902023005HelenM79862023006AmyF68752.3實驗范例

建立單鏈表：要求建立一個帶頭結點的單鏈表存放學生信息，將用戶輸入的n個學生的信息按尾插入法建立相應單鏈表。2.3.1范例12.3實驗范例1、問題分析2.3.1范例1

鏈表是一個動態(tài)的結構，它不需要預分配空間，因此建立鏈表的過程是一個結點“逐個插入”的過程。先建立一個只含頭結點的空單鏈表，然后依次生成新結點，再不斷地將其插入到單鏈表的頭部或尾部，分別稱其為“頭插法”和“尾插法”。2.3實驗范例1、問題分析2.3.1范例1

尾插法過程如下：(1)初始化空單鏈表

用r指向當前單鏈表的最后一個結點，對應的語句為：r=L;2.3實驗范例1、問題分析2.3.1范例1

尾插法過程如下：(2)生成一個新的結點p，然后輸入數(shù)據(jù)到p的數(shù)據(jù)域并將p的指針域賦值為空，再將p插入r之后，最后將r指向當前最后一個結點p。插入第一個結點過程如下圖所示，對應的語句為：p=(LNode*)malloc(sizeof(LNode));p->data=輸入的數(shù)據(jù);p->next=NULL;r->next=p;r=p;2.3實驗范例1、問題分析2.3.1范例1

尾插法過程如下：(3)重復第2步，插入其他元素。圖在單鏈表L中插入第二個結點的過程如下圖所示。2.3實驗范例2、算法描述2.3.1范例1

先定義結構體類型，包含學號、姓名、大學英語成績、高等數(shù)學成績，結構體定義如下：typedefstructStudent{charNo[8];//學號charname[16];//姓名charsex;//性別intenglish;//大學英語成績intmath;//高等數(shù)學成績}Student;2.3實驗范例2、算法描述2.3.1范例1

然后定義結點類型。結點類型定義如下：typedefstructLNode//定義結點類型{Studentdata;//數(shù)據(jù)部分

structLNode*next;//指向下一個結點的指針}LNode,*LinkList;//LinkList為指向LNode的指針類型2.3實驗范例2、算法描述2.3.1范例1

結點類型定義好之后，先初始化單鏈表，即建立一個頭結點。類似于第1章中順序表的初始化，初始化單鏈表L的函數(shù)可以定義如下：intInitListList(LinkList&L)//先初始化單鏈表{L=(LinkList)malloc(sizeof(LNode));if(L==NULL)//空間分配失敗exit(-1);L->next=NULL;return1;}2.3實驗范例2、算法描述2.3.1范例1

單鏈表L被初始化之后，根據(jù)前面分析的尾插法步驟，構造一個能放n個學生信息的單鏈表，用尾插法建立長度為n的單鏈表L函數(shù)可以定義如下：voidCreateLinkList_R(LinkListL,intn){inti;LNode*p,*r;Studentstu;r=L;//r指向當前最后一個結點printf("輸入%d個數(shù)據(jù)：",n);for(i=0;i<n;i++)

{

//生成結點pp=(LinkList)malloc(sizeof(LNode));//輸入數(shù)據(jù)到p的數(shù)據(jù)域InputOneStu(stu);//讀入一個學生的數(shù)據(jù)p->data=stu;p->next=NULL;//將結點p插入到尾結點r的后面r->next=p;//r指向新的尾結點r=p;}}2.3實驗范例2、算法描述2.3.1范例1

接著定義函數(shù)PrintListInfo(SqListL)輸出鏈表中存儲的學生信息。從第一個結點開始沿著鏈域逐個輸出每個結點的數(shù)據(jù)域中的數(shù)據(jù)。voidPrintListInfo(LinkListL){p=L->next;while(p!=NULL){printf("學號：%s\n",p->data.No);printf("姓名：%s\n",p->);printf("性別：%c\n",p->data.sex);printf("大學英語成績：%d\n",p->data.english);printf("高等數(shù)學成績：%d\n",p->data.math);p=p->next;}}2.3實驗范例2、算法描述2.3.1范例1

然后在main()中定義鏈表L，調用函數(shù)InitListList()初始化鏈表，調用函數(shù)CreateLinkList_R(L,5)；建立長度為5的單鏈表，接著調用函數(shù)PrintListInfo()將鏈表中的信息輸出。主函數(shù)定義如下：#include<stdio.h>#include<stdlib.h>//在main()之前加入類型定義和函數(shù)定義intmain(){LinkListL;InitListList(L);CreateLinkList_R(L,5);PrintListInfo(L);return0;}2.3實驗范例3、算法分析2.3.1范例1

采用尾插法創(chuàng)建鏈表時，因為r一直指向鏈表的尾部，插入一個結點的時間復雜度為O(1)。CreateLinkList_R()函數(shù)一共需要插入n個結點，其時間復雜度為O(n)。2.3實驗范例

在范例1建立的單鏈表L中查找學號為stuID的學生信息。要求在單鏈表L中的查找學號stuID，如果能找到該學號，則返回該學生在鏈表中的序號；如果找不到該學號，則返回0。2.3.2范例22.3實驗范例1、問題分析2.3.2范例2

該問題需要遍歷鏈表。即從第一個有學生信息的結點開始，將結點的數(shù)據(jù)域中的學號部分與stuID比較，同時用一個計數(shù)器存儲結點的序號。如果發(fā)現(xiàn)結點的數(shù)據(jù)域中的學號與stuID相等則查找結束，返回計數(shù)器的值。當鏈表中的結點全部找完，還沒找到為stuID的學號則返回0。本例中學號為一個字符串，判斷兩個字符串是否相等可使用strcmp()函數(shù)。2.3實驗范例2、算法描述2.3.2范例2

根據(jù)以上分析，在單鏈表L中查找學號為stuID的元素并返回序號的函數(shù)可以定義如下：intLocateElem(LinkListL,char*stuID){LNode*p;intj;p=L->next;//從第一個結點開始查找j=1;//依次將單鏈表中的元素和stuID進行比較while(p&&strcmp(p->data.No,stuID)!=0){p=p->next;j++;

}if(p)//p不為空，即找到stuIDreturnj;//返回序號

elsereturn0;}2.3實驗范例2、算法描述2.3.2范例2

在范例1的基礎上，在main()中調用函數(shù)LocateElem()查詢學號為2023003的學生，也可以輸入學號。由于查找過程中需要調用strcmp比較兩個字符串進，需要加上頭文件string.h。主函數(shù)定義如下：#include<stdio.h>#include<stdlib.h>#include<string.h>//在main()之前加入類型定義和函數(shù)定義intmain(){LinkListL;InitListList(L);CreateLinkList_R(L,5);PrintListInfo(L);

intpos=LocateElem(L,"2023003");if(pos==0){printf("該學生不存在！\n");}

else{printf("該學生是第%d位！\n",pos);}return0;}2.3實驗范例3、算法分析2.3.2范例2

在鏈表中查找某一元素時，因為要遍歷整個鏈表，所以其時間復雜度為O(n)，其中n為鏈表的長度。2.3實驗范例

刪除單鏈表L中姓名為stuName的所有學生的信息。要求在單鏈表L中查找姓名為stuName的學生，如果找到則將之刪除，并返回被刪除的學生人數(shù)。2.3.3范例32.3實驗范例1、問題分析2.3.3范例3

因為需要返回被刪除的學生人數(shù)，需用一個計數(shù)器存儲被刪除結點的個數(shù)，計算器初始時為0。從第一個結點開始依次查看鏈表中結點的數(shù)據(jù)信息，把結點的數(shù)據(jù)域中的姓名name與stuName比較，如果結點數(shù)據(jù)域中的name與stuNamex相等則刪除該結點并將計數(shù)器加1。重復這一步驟直到鏈表L中所有的結點都被查看完。最后返回計數(shù)器的值。2.3實驗范例1、問題分析2.3.3范例3

在單鏈表中刪除第i個結點，需要修改第i-1個結點的指針域。所以在找到第i個結點的同時，還需存儲第i-1個結點的地址。如上圖所示，假設q是要被刪除的結點，q的前面那個結點為p，將q移出鏈表并且銷毀的操作為：p->next=q->next;free(q);2.3實驗范例2、算法描述2.3.3范例3

設計一個函數(shù)刪除單鏈表L中姓名為stuName的所有學生信息，并返回被刪除的學生（結點）數(shù)。函數(shù)可以定義如下：intDeleteElem(LinkList&L,char*stuName){LNode*p,*q;intcnt=0;//計數(shù)器q=L->next;//初始化工作指針p=L;while(q!=NULL){

if(strcmp(q->,stuName)==0){//找到要刪除的結點p->next=q->next;//將結點從鏈表中摘除free(q);2.3實驗范例2、算法描述2.3.3范例3

設計一個函數(shù)刪除單鏈表L中姓名為stuName的所有學生信息，并返回被刪除的學生（結點）數(shù)。函數(shù)可以定義如下：

q=p->next;cnt++;//計數(shù)器加1}else{//不相等，指針后移，繼續(xù)比較下一個結點p=p->next;q=q->next;}}returncnt;}2.3實驗范例2、算法描述2.3.3范例3

在范例1的基礎上，在main()中調用函數(shù)DeleteElem()刪除姓名為Peter的學生，并輸出刪除的人數(shù)，為了檢測刪除是否操作成功，調用函數(shù)PrintListInfo()輸出刪除后的鏈表信息。主函數(shù)定義如下：#include<stdio.h>#include<stdlib.h>#include<string.h>//在main()之前加入類型定義和函數(shù)定義intmain(){LinkListL;InitListList(L);

CreateLinkList_R(L,5);PrintListInfo(L);intnum=DeleteElem(L,"Peter");printf("共刪除%d個學生！\n",num);PrintListInfo(L);return0;}2.3實驗范例3、算法分析2.3.3范例3

DeleteElem()函數(shù)先要在鏈表中找到將被刪除的元素，這一過程的時間復雜度為O(n)。刪除元素的操作主要是修改指針，不需要移動元素，時間主要耗費在查找元素上。2.4實驗任務完成下列任務，并分析各算法的時間復雜度。任務1：在單鏈表L中的第i個學生后面插入一個新學生stu。要求：將新學生stu的信息加入到鏈表L中第i個學生的后面，如果給出的i大于鏈表的長度，則將stu插入鏈表的末尾；如果給出的i小于或等于0，則將stu直接插入表頭之后。因此，鏈表L、stu和i都為函數(shù)的參數(shù)。任務2：統(tǒng)計單鏈表L中高等數(shù)學大于x并且大學英語大于x的學生人數(shù)。要求：設計一個函數(shù)統(tǒng)計前面已建立好的鏈表L中滿足條件的學生人數(shù)，并返回統(tǒng)計的結果。2.4實驗任務完成下列任務，并分析各算法的時間復雜度。任務3：在任務2的基礎上，將單鏈表L中高等數(shù)學成績和大學英語成績在min_score到max_score之間的學生組織成一個新的單鏈表L2。要求：將鏈表L中符合條件如高等數(shù)學和大學英語兩門課程成績在min_score到max_score之間的學生組成一個新的鏈表L2，并把這些學生從原鏈表L中刪除。任務4：編程實現(xiàn)在帶頭結點的雙向循環(huán)鏈表中插入和刪除元素。（選做）要求：建立一個存儲學生信息的雙向鏈表，設計一個函數(shù)將一個學生的信息插入到鏈表的第i個位置，然后再通過調用這個函數(shù)建立一個雙鏈表。雙鏈表建立之后，設計一個函數(shù)將鏈表中第i個位置的學生信息刪除，即刪除第i個結點。2.5任務提示

先在單鏈表L中找到第i個結點的地址p，同時用pre指向該結點的前驅結點，用計數(shù)器j存儲p指向的結點序號。如果第i個元素的地址為空，將結點s插入到pre結點之后。如果p不等于NULL，則將結點s插入到結點p之后。由于p最開始指向頭結點，如果i小于或等于0，直接將結點s插入頭結點之后，下圖顯示了將s插入到結點p之后的操作步驟。任務1提示①s->next=p->next;②p->next=s;2.5任務提示偽代碼描述如下：任務1提示voidInsertElem(LinkList&L,inti,Studentstu){s=(LinkList)malloc(sizeof(LNode));//生成結點ss->data=stu;//將x存入結點的數(shù)據(jù)域p=L;j=0;//尋找插入位置，并使p指向插入位置的前驅結點，即L中的第i個位置while(p!=NULL&&j<i){pre=p;p=p->next;j++;

}2.5任務提示任務2提示

鏈表是一種"順序存取"的結構，要統(tǒng)計鏈表中滿足某種條件的元素個數(shù)，需用一個計數(shù)器表示符合條件的元素個數(shù)。具體方法是從單鏈表第一個結點開始沿著指針域依次找到各個結點，看結點的數(shù)據(jù)域是否符合統(tǒng)計條件，如果符合統(tǒng)計條件則計數(shù)器加1，直到把鏈表中的結點全部查看完，最后返回計數(shù)器的值。該算法過程與計算鏈表長度類似。2.5任務提示偽代碼描述如下：任務2提示intCountElem(LinkListL,intx){cnt=0;//計數(shù)器p=L->next;//p指向第一個結點//將鏈表中的元素逐個和給定值x進行比較，相等則計數(shù)器加1while(p!=NULL){if(p->data.english>x&&p->data.math>x)//找到一個符合條件的元素cnt++;p=p->next;//p指向后一個結點}returncnt;}2.5任務提示任務3提示

任務3要求將鏈表L中符合條件的學生加入新鏈表L2中，并把這些學生信息從原鏈表L中刪除。這實際上就是將符合條件的結點從L中分離出來并且鏈接到L2。因此，首先需初始化L2，然后再將L中滿足條件的結點從L中刪除并插入到L2中（采用頭插法，每次插入到頭結點之后），同時返回插入到L2中的結點個數(shù)。2.5任務提示任務3提示intMoveElem(LinkList&L,intmin_score,intmax_score,LinkList&L2){count=0;p=L;while(p->next!=NULL){if((p->next->data.english>=min_score&&p->next->data.english<=max_score)&&(p->next->data.math>=min_score&&p->next->data.math<=max_score)){q=p->next;//以下要把q結點移動到L2中p->next=q->next;//把q結點從L中移出q->next=L2->next;//把q結點鏈接到L2表頭的后面L2->next=q;count++;

｝

elsep=p->next;

}

returncount;//返回移動的結點數(shù)}可設計函數(shù)框架如下：2.5任務提示任務4提示在鏈表中第i個位置插入結點，只需要第i-1個結點存在就可以插入。因此首先需要找到第i-1個結點p，如果找到p，則將元素插入到結點p之后。下圖顯示了將結點s插入雙向循環(huán)鏈表中結點p之后的操作步驟。①s->prior=p;

②s->next=p->next;③p->next=s;

④p->next->prior=s;2.5任務提示任務4提示偽代碼描述如下：intInsertElem(DuLCirLinkList&L,inti,DElemTypex){//在L中找到第i-1個結點的位置pp=GetElem(L,i