關于結構體類型與結構體變量（1）結構體類型與結構體變量是兩個不同的概念，其區別如同int類型與int型變量的區別一樣。（2）結構體類型中的成員名，可以與程序中的變量同名，它們代表不同的對象，互不干擾。1

如何訪問結構體變量的成員?假設有結構體變量var,指針變量pointer指向結構變量var，則以下三種形式等價：

1）var.成員

2）pointer->成員

3）(*pointer).成員/*“*pointer”外面的括號不能省！*/注意：在格式（1）中，分量運算符左側的運算對象，只能是結構體變量；而在格式（2）中，指向運算符左側的運算對象，只能是指向結構體變量（或結構體數組）的指針變量。2C語言動態內存分配(1)庫函數malloc()·用法：void*malloc(unsignedsize)·功能：在內存的動態存儲區分配１個長度為

size的連續空間。·返回值：申請成功，則返回新分配內存塊的起始地址；否則，返回NULL。·函數原型：malloc.h，stdlib.h。3malloc()函數的返回值是一個無類型指針，其特點是可以指向任何類型的數據。但在實際使用malloc()函數時，必須將其返回值強制轉換成被賦值指針變量的數據類型，以免出錯。C語言動態內存分配4(2)運算符sizeof·格式：sizeof(變量名／類型名)·功能：求變量／類型占用的內存字節數（正整數）。例如，在IBM-PC機上，sizeof(int)=2。C語言動態內存分配5（3）庫函數free()·用法：voidfree(void*ptr)·功能：釋放由ptr指向的內存塊（ptr是調用malloc()函數的返回值）。·返回值：無。·函數原型：stdlib.h，malloc.h。C語言動態內存分配6typedef語句typedef語句(類型說明語句)的功能是利用某個已有的數據類型定義一個新的數據類型。其格式為:

typedef數據類型名新數據類型名如：typedefintinteger;integeri,j;

7typedef語句例：typedefstruct

/*學生信息結構體類型：由學號、姓名、性別和生日共4項組成*/{charno[7];charname[9];charsex[3];structdatebirthday;}

std_info;

其后的變量說明語句中可以省略結構體類型說明符struct:std_infostudent;8線性結構的定義：

若結構是非空有限集，則有且僅有一個開始結點和一個終端結點，并且所有結點都最多只有一個直接前趨和一個直接后繼。→可表示為：（a1,a2,……,an）

簡言之，線性結構反映結點間的邏輯關系是

的。特點①只有一個首結點和尾結點；特點②除首尾結點外，其他結點只有一個直接前驅和一個直接后繼。線性結構包括：線性表、堆棧、隊列、字符串、數組等，其中最典型、最常用的是------線性表一對一(1:1)9第2章線性表2.1線性表抽象數據類型2.2線性表的順序表示和實現2.3線性表的鏈式表示和實現10（a0,a1,…ai-1，ai,ai＋1

，…,an-1）線性表的邏輯結構：n=0時稱為數據元素線性起點ai的直接前趨ai的直接后繼下標，是元素的序號，表示元素在表中的位置n為元素總個數，即表長。n≥0空表線性終點11

（A,B,C,D,……,Z）學號姓名性別年齡班級012019010622陳建武男192019級電信0301班012019010704趙玉鳳女182019級電信0302班012019010813王澤男192019級電信0303班012019010906薛荃男192019級電信0304班012019011018王春男192019級電信0305班：：：

：：例：分析學生情況登記表是什么結構。分析：數據元素都是同類型（記錄），元素間關系是線性的。分析：數據元素都是同類型（字母），元素間關系是線性的。例：分析26個英文字母組成的英文表是什么結構。12線性表抽象數據類型

它包括兩個方面：數據集合：｛a0,a1,…,an-1｝ai的數據類型為DataType

操作集合：(1)ListInitiate(L)初始化線性表

(2)ListInsert(L,i,x)插入數據元素

(3)ListLength(L)求當前數據元素個數

(4)ListDelete(L,i,x)刪除數據元素

(5)ListGet(L,i,x)取數據元素13線性表的存儲結構(1)順序存儲結構:它是使用一片地址連續的有限內存單元空間存儲數據元素的一種計算機存儲數據方法。特點：邏輯上相鄰的元素，物理上也相鄰。(2)鏈式存儲結構:它是把數據元素和指針定義成一個存儲體，使用指針把發生聯系的數據元素鏈接起來的一種計算機存儲數據方法。特點：任意兩個在邏輯上相鄰的數據元素在物理上不一定相鄰，數據元素的邏輯次序是通過鏈中的指針鏈接實現的。142.2線性表的順序表示和實現一、順序表的存儲結構二、順序表的實現三、順序表的運算效率分析152.2.1、順序表的存儲結構表示

1、順序表：用一組地址連續的存儲單元依次存儲線性表的各個數據元素。即采用順序存儲結構的線性表。它通常采用靜態數組實現數據元素的存儲。可以利用數組V[n]來實現注意：在C語言中數組的下標是從0開始，即：

V[n]的有效范圍是從V[0]～V[n-1]16若已知表中首元素在存儲器中的位置，則其他元素存放位置亦可求出（利用數組V[n]的下標）。設首元素a0的存放地址為LOC(a0)（稱為首地址），設每個元素占用存儲空間（地址長度）為L字節，則表中任一數據元素的存放地址為：

LOC(ai

)=LOC(a0)+L*i對上述公式的解釋如圖所示2.2.1順序表的存儲結構表示17a0a1……aiai+1……an-1

地址內容元素在表中的位序0i1n-1空閑區i+1Lb=LOC(a0)b+Lb+iLb+(n-1)Lb+(MaxSize-1)LLOC(ai)=LOC(a0)+L*i線性表的順序存儲結構示意圖18設有一維數組Ｍ，下標的范圍是０到９，每個數組元素用相鄰的５個字節存儲。存儲器按字節編址，設存儲數組元素Ｍ[０]的第一個字節的地址是９８，則Ｍ[３]的第一個字節的地址是多少？113LOC(M[3])=98+5×3=113解：已知地址計算通式為：LOC(ai)=LOC(a0)+L*i例:19用C語言描述：typedefstruct{DateTypelist[MaxSize];intsize;}SeqList;

/*MaxSize表示數組的最大元素個數，list表示順序表的數組名，size表示順序表中當前存儲的數據元素個數，它必須滿足size≤MaxSize，SeqList是該結構體的名字。*/2.2.2順序表的實現20順序表的操作(1)ListInitiate(L)初始化線性表

(2)ListInsert(L,i,x)插入數據元素

(3)ListLength(L)求當前數據元素個數

(4)ListDelete(L,i,x)刪除數據元素

(5)ListGet(L,i,x)取數據元素212.順序表操作的實現

（1）初始化ListInitiate(L)voidListInitiate(SeqList*L) {L->size=0; /*定義初始數據元素個數*/}

（2）求當前數據元素個數ListLength(L)intListLength(SeqListL) {returnL.size;}

22線性表操作

ListInsert(L,i,e)的實現：首先分析:插入元素時，線性表的邏輯結構發生什么變化？23

(a0,…,ai-1,ai,…,an-1)改變為a0a1

…ai-1ai

…an-1a0a1

…ai-1

…aiean-1<ai-1,ai><ai-1,e>,<e,ai>表的長度增加(a0,…,ai-1,e,ai,…,an-1)24插入算法ListInsert(L,i,x)描述算法功能：在線性表（n個元素）的第i個位置前插入一個元素輸入：順序表輸出：插入元素后的順序表1.判斷表是否滿，如果滿則顯示提示信息2.判斷插入的位置i是否合法(n>i>=0)，如果不合法，則顯示錯誤信息3.將第n-1至第i

位的元素向后移動一個位置4.將要插入的元素寫到第i個位置；5.表長加1。25（3）插入數據元素ListInsert(L,i,x)關鍵代碼

intListInsert(SeqList*L,inti,DataTypex){intj;for(j=L->size;j>i;j--)L->list[j]=L->list[j-1];/*依次后移*/

L->list[i]=x; /*插入x*/ L->size++; /*元素個數加1*/ return1;}26線性表操作

ListDelete(L,i,e)的實現：首先分析：刪除元素時，線性表的邏輯結構發生什么變化？27

(a0,…,ai-1,ai,ai+1,…,an-1)改變為ai+1…an-1<ai-1,ai>,<ai,ai+1><ai-1,ai+1>表的長度減少a0a1

…ai-1ai

ai+1

…

an-1a0a1

…ai-1

(a0,…,ai-1,ai+1,…,an-1)28刪除算法ListDelete(L,i,x)描述算法功能：刪除線性表（n個元素）的第i個位置上的元素輸入：順序表輸出：刪除的元素1.判斷刪除的位置i是否合法(n-1>i>=0)，如果不合法，則顯示錯誤信息2.將第i+1至第n-1位的元素向前移動一個位置；3.表長減1。29（4）刪除數據元素ListDelete(L,i,x)關鍵代碼intListDelete(SeqList*L,inti,DataType*x) {intj;

*x=L->list[i];/*保存刪除的元素到x中*/

for(j=i+1;j<=L->size-1;j++)L->list[j-1]=L->list[j];/*依次前移*/

L->size--; /*數據元素個數減1*/

return1;}30查找元素算法ListGet(L,i,x)描述算法功能：查找線性表（n個元素）的第i個位置上的元素輸入：順序表輸出：查找到的元素1.判斷查找的位置i是否合法(n-1>i>=0)，如果不合法，則顯示錯誤信息2.直接取出第i個位置的元素31（5）取數據元素ListGet(L,i,x)intListGet(SeqListL,inti,DataType*x){if(i<0||i>L.size-1){printf("參數i不合法!\n"); return0;}else{ *x=L.list[i];return1;}}32例2-1：建立一個線性表，先依次輸入數據元素1，2，3，4，…，10，然后刪除５，最后依次顯示當前線性表中的數據元素。假設該線性的數據元素個數最壞情況下不會超過100個。

33實現方法：

1、采用直接編寫一個主函數實現。

2、利用已設計實現的抽象數據類型模塊。（存放在頭文件名為SeqList.h的文件中，通過#include“SeqList.h”

）程序設計如下：#include<stdio.h> #defineMaxSize100 typedefintDataType;#include"SeqList.h"

34voidmain(void){SeqListmyList;inti,x;

ListInitiate(&myList);for(i=0;i<10;i++)

ListInsert(&myList,i,i+1);

ListDelete(&myList,4,&x);for(i=0;i<ListLength(myList);i++){ListGet(myList,i,&x);printf(“%d”,x);}}程序運行結果：1234678910351.頭文件分為系統頭文件自定義頭文件2.頭文件的處理：先把被包含的文件內容復制到引用頭文件的語句處，形成一個新的源程序，再編譯成一個目標文件。C語言頭文件362.2.3順序表操作的效率分析算法時間主要耗費在移動元素的操作上，因此計算時間復雜度的基本操作（最深層語句頻度）

T(n)=O(移動元素次數)而移動元素的個數取決于插入或刪除元素的位置.思考：若插入在尾結點之后，則根本無需移動（特別快）；若插入在首結點之前，則表中元素全部要后移（特別慢）；應當考慮在各種位置插入（共n+1種可能）的平均移動次數才合理。時間效率分析:37推導：假定在每個元素位置上插入x的可能性都一樣（即概率P相同），則應當這樣來計算平均執行時間：將所有位置的執行時間相加，然后取平均。若在首結點前插入，需要移動的元素最多，后移n次；若在a1后面插入，要后移n-1個元素，后移次數為n-1;……若在an-1后面插入，要后移1個元素；若在尾結點an之后插入，則后移0個元素；所有可能的元素移動次數合計：0+1+…+n=n(n+1)/2

故插入時的平均移動次數為：n(n+1)/2÷（n+1）＝n/2≈O(n)

共有多少種插入形式?——連頭帶尾有n+1種!38

順序表中的其余操作都和數據元素個數n無關，因此，在順序表中插入和刪除一個數據元素的時間復雜度為O(n),其余操作的時間復雜度都為O(1)主要優點是算法簡單，空間單元利用率高；主要缺點是需要預先確定數據元素的最大個數，插入和刪除時需要移動較多的數據元素。主要優缺點39思考題P22頁，刪除算法的效率Edl是如何計算出來的？402.5算法設計舉例例2-4設計一個順序表的刪除函數，把順序表L中的數據元素x刪除。算法思想：首先，找到要刪除元素的位置，然后，從這個位置到最后一個元素，逐個前移，最后，把元素個數減1。41intListDataDelete(SeqList*L,DataTypex){inti,j;for(i=0;i<L->size;i++) if(x==L->list[i])break;

if(i==L->size)return0; else {for(j=i;j<L->size;j++) L->list[j]=L->list[j+1];

L->size--; return1;}}

42算法練習題1.編寫算法實現順序表的逆置，要求把順序表A中的數據元素序列（a0,a1,a2,…..an-1）逆置為（an-1,…..a2,a1,a0），并存儲到順序表B中。43算法練習題2.編寫算法實現順序表的就地逆置，把數據元素序列（a0,a1,a2,…..an-1）逆置為（an-1,…..a2,a1,a0）。442.3線性表的鏈式表示和實現一、單鏈表的存儲結構二、單鏈表的操作實現三、鏈表的運算效率分析45１、單鏈式及表示方法(1)單鏈表:構成鏈表的結點只有一個指向直接后繼結點的指針。其結構特點：邏輯上相鄰的數據元素在物理上不一定相鄰。如何實現？通過指針來實現！讓每個存儲結點都包含兩部分：數據域和指針域指針域數據域nextdata或樣式：數據域：存儲元素數值數據指針域：存儲直接后繼的存儲位置設計思想：犧牲空間效率換取時間效率一、單鏈表的存儲結構46例：請畫出26個英文字母表的鏈式存儲結構。該字母表在內存中鏈式存放的樣式舉例如下：解：該字母表的邏輯結構為：（a,b,…,y,z）鏈表存放示意圖如下：a1heada2/\an……討論1：每個存儲結點都包含兩部分：數據域和

。討論2：在單鏈表中，除了首元結點外，任一結點的存儲位置由

指示。其直接前驅結點的鏈域的值指針域(鏈域)47

線性表具有兩種存儲方式，即順序方式和鏈接方式。現有一個具有五個元素的線性表L={23，17，47，05，31}，若它以鏈接方式存儲在下列100～119號地址空間中，每個結點由數據（占2個字節）和指針（占2個字節）組成，如下圖所示。其中指針X，Y，Z的值分別為多少？該線性表的首結點起始地址為多少？末結點的起始地址為多少？Z47Y31V23X17U05100119104108116112116NULL(0)100108112答：X=

Y=

Z=

,

首址=

末址=

。例：481）結點：數據元素的存儲映像。由數據域和指針域兩部分組成；2）鏈表：n個結點由指針鏈組成一個鏈表。它是線性表的鏈式存儲映像，稱為線性表的鏈式存儲結構。3）單鏈表、雙鏈表、多鏈表、循環鏈表：結點只有一個指針域的鏈表，稱為單鏈表或線性鏈表；有兩個指針域的鏈表，稱為雙鏈表（但未必是雙向鏈表）；有多個指針域的鏈表，稱為多鏈表；首尾相接的鏈表稱為循環鏈表。a1heada2an……循環鏈表示意圖：head(2)與鏈式存儲有關的術語：494）頭指針、頭結點和首元結點的區別頭指針頭結點首元結點a1heada2…infoan^頭指針是指向鏈表中第一個結點（或為頭結點、或為首元結點）的指針；首元結點是指鏈表中存儲線性表第一個數據元素a０的結點。頭結點是在鏈表的首元結點之前附設的一個結點；數據域內只放空表標志和表長等信息，它不計入表長度。示意圖如下：50答：討論1.在鏈表中設置頭結點有什么好處？討論2.如何表示空表？頭結點即在鏈表的首元結點之前附設的一個結點，該結點的數據域可以為空，也可存放表長度等附加信息，其作用是為了對鏈表進行操作時，可以對空表、非空表的情況以及對首元結點進行統一處理，編程更方便。答：無頭結點時，當頭指針的值為空時表示空表；^頭指針無頭結點^頭指針頭結點有頭結點有頭結點時，當頭結點的指針域為空時表示空表。頭結點不計入鏈表長度！51一個線性表的邏輯結構為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲結構用單鏈表表示如下，請問其頭指針的值是多少？存儲地址數據域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：頭指針是指向鏈表中第一個結點的指針，因此關鍵是要尋找第一個結點的地址。7ZHAOH31稱：頭指針H的值是31２、帶頭結點單鏈表和不帶頭結點單鏈表的比較例：52上例鏈表的邏輯結構示意圖有以下兩種形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH區別：①無頭結點②有頭結點頭結點不計入鏈表長度！53對比帶頭結點的單鏈表的插入、刪除過程和不帶帶頭結點的單鏈表的插入、刪除過程，可以得知：

●若設計的單鏈表帶頭結點，則無論是在第一個數據元素結點前插入還是在其他數據元素結點前插入都不會改變頭指針的數值。

●若設計的單鏈表不帶頭結點，則在第一個數據元素結點前插入與在其他數據元素結點前插入其算法的處理方法不同。

●在單鏈表中刪除一個結點時類似。

因此，單鏈表一般構造成帶頭結點的單鏈表。54討論:鏈表的數據元素有兩個域，不再是簡單數據類型，編程時該如何表示？因每個結點至少有兩個分量，且數據類型通常不一致，所以要采用結構數據類型。答：以26個字母的鏈表為例，每個結點都有兩個分量：字符型指針型設每個結點用變量node表示，其指針用p表示，兩個分量分別用data和*next表示，以下兩個分量賦值方法是否正確？p*nextdatanode方式1：直接表示為

node.data＝'a'；node.next=q方式2：p指向結點首地址，然后p->data='a';p->next=q;方式3：p指向結點首地址，然后(*p).data='a'；(*p).next＝q‘a’‘b’qp55sizeof(x)——計算x的長度malloc(m)—開m字節空間free(p)——刪除一個變量問1：自定義結構類型變量node的長度m是多少？問2：結構變量node的首地址(指針p）是多少？問3：怎樣刪除結構變量node？*nextdatanode，長度為m字節pm＝sizeof(node)//單位是字節p＝(node*)malloc(m)free(p)//只能借助node的指針刪除！56②對于指向結構類型的指針變量，可說明為：

SLNode*p,*q;//或用

structNode*p,*q;//注：上面已經定義了SLNode為用戶自定義的Node類型。①類型定義可以寫為：typedefstructNode//Node是自定義結構類型名稱{DataTypedata;//定義數據域的變量名及其類型

structNode*next;//定義指針域的變量名及其類型}SLNode，*p;//SLNode是Node結構類型的類型替代,

*p是指針型的Node結構類型的替代

此結構數據類型的C表示法57單鏈表基本操作1.初始化2.求單鏈表中元素個數3.插入元素4.刪除元素5.取數據元素6.撤消單鏈表二、單鏈表的操作實現58１、初始化voidListInitiate(SLNode**head)／*初始化*/{ /*如果有內存空間，申請頭結點空間并使頭指針head指向頭結點*/

*head=(SLNode)malloc(sizeof(SLNode));(*head)->next=NULL; }59２、求單鏈表中數據元素的個數

intListLength(SLNode*head)

{

SLNode*p=head;

/*p指向頭結點*/

intsize=0;

/*size初始為0*/

while(p->next!=NULL)/*循環計數*/

{

p=p->next;

size++;

}

returnsize;

}60在鏈表中插入一個元素X的示意圖如下：Xqabp鏈表插入的核心語句：Step1：q->next=p->next;Step2：p->next=q；p->nextq->next思考：Step1和2能互換么？X結點的生成方式：m=sizeof(SLNode);q=(SLNode*)malloc(m);q->data=X;q->next=?bap插入X３、向單鏈表中插入一個元素61intListInsert(SLNode*head,inti,DataTypex){SLNode*p,*q; intj; p=head; j=-1;(1)while(p->next!=NULL&&j<i-1){ p=p->next;j++; }

if(j!=i-1){ printf("插入位置參數錯！"); return0;}(2)

q=(SLNode*)malloc(sizeof(SLNode)); q->data=x;q->next=p->next;

p->next=q;(4) return1;}

注：此單鏈表是帶頭結點的62在鏈表中刪除某元素b的示意圖如下：cabp刪除動作的核心語句（可以借助輔助指針變量s）：s=p->next;//首先保存b的指針，靠它才能找到c；p->next=s->next;

//將a、c兩結點相連，淘汰b結點；free(s)；//徹底釋放b結點空間p->next思考：省略free(s)語句行不行？(p->next)->next××s４、從單鏈表中刪除一個元素63intListDelete(SLNode*head,inti,DataType*x)

{ SLNode*p,*s; intj;(1)p=head;

j=-1; while(p->next!=NULL&&p->next->next!=NULL&&j<i-1)

{

p=p->next; j++; }

if(j!=i-1) {

printf(“插入位置參數錯！”);

return0; }(2)

s=p->next;*x=s->data;(3)

p->next=s->next;

free(s);

return1;

} 645.取數據元素ListGet(head,i,x)intListGet(SLNode*head,inti,DataType*x){SLNode*p;intj;

p=head;j=-1;

while(p->next!=NULL&&j<i){p=p->next; j++; }

if(j!=i){printf(“取元素位置參數錯！”); return0;}

*x=p->data;return1;}

65（6）撤消單鏈表Destroy(head)voidDestroy(SLNode**head){SLNode*p,*p1;

p=*head;while(p!=NULL){p1=p;p=p->next;free(p1); }*head=NULL;}66三、單鏈表的操作效率分析（1）查找

因線性鏈表只能順序存取，即在查找時要從頭指針找起，查找的時間復雜度為

O(n)。時間效率分析（2）插入和刪除

因線性鏈表不需要移動元素，只要修改指針，僅就插入或刪除而言，時間復雜度為

O(1)。但是，如果要在單鏈表中進行在某結點前插或刪除操作，因為要從頭查找前驅結點，所以一般情況下，單鏈表插入和刪除操作的時間復雜度是O(n)（同順序表）。67單鏈表操作的效率分析（P34頁）單鏈表的插入和刪除操作不需移動數據元素，只需比較數據元素。因此，當在單鏈表的任何位置上插入數據元素的概率相等時，在單鏈表中插入一個數據元素時比較數據元素的平均次數為：刪除一個數據元素時比較數據元素的平均次數為：另外，單鏈表求數據元素個數操作的時間復雜度為O(n)。68和順序表相比主要優點是不需要預先確定數據元素的最大個數，插入和刪除操作不需要移動數據元素；主要缺點是查找數據元素時需要順序進行，不能像順序表那樣隨機查找任意一個數據元素。另外，每個結點中要有一個指針域，因此空間單元利用率不高。而且單鏈表操作的算法也較復雜。單鏈表和順序表相比，單鏈表的優點和缺點正好相反。69四、應用舉例例2-3編程實現：建立一個單鏈表，首先依次輸入數據元素１,２,…,10，然后刪除數據元素５，最后依次顯示當前表中的數據元素。

#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedefintDataType; #include"LinList.h"重點是鏈表70

voidmain(void){SLNode*head;inti,x;

ListInitiate(&head);

for(i=0;i<10;i++)

ListInsert(head,i,i+1);

ListDelete(head,4,&x);

for(i=0;i<ListLength(head);i++){ListGet(head,i,&x); printf(“%d”,x); }

Destroy(&head);}程序運行結果：123467891071

最后一個結點的指針域的指針又指回第一個結點的鏈表a1a2…...an1.循環鏈表

和單鏈表的差別僅在于，判別鏈表中最后一個結點的條件不再是“后繼是否為空”，而是“后繼是否為頭結點”。五、其它形式的鏈表72

2.雙向鏈表a1a2…...an^^73雙向循環鏈表空表非空表a1a2…...an74（１）雙向循環鏈表的存儲結構雙向循環鏈表：鏈表中每個結點除后繼指針域和數據域外還有一個前驅指針域。其結點的結構為：雙向鏈表結點的結構體定義如下：

typedefstructNode{DataTypedata;structNode*next;structNode*prior;}DLNode;priordatanext75（2）雙向鏈表的操作實現(1)前插設p已指向第i元素，請在第i元素前插入元素xx

sai-1

ai

p指針域的變化：①ai-1的后繼從ai(指針是p)變為x（指針是s):s->next=p;

p->prior->next=s;

②ai的前驅從ai-1(指針是p->prior)變為x(指針是s);

s->prior=p->prior;p->prior=s;76

p指針域的變化：

后繼方向：ai-1的后繼由ai(指針p)變為ai+1(指針p->next

);p->prior->next

=

p->next;

前驅方向：ai+1的前驅由ai(指針p)變為ai-1(指針p->prior);p->next->prior

=p->prior;(2)雙向鏈表的刪除操作設p指向第i個元素，刪除第i個元素ai-1

ai

ai+1

772.4靜態鏈表靜態鏈表：在數組中增加一個（或兩個）指針域，這些指針域用來存放下一個（或上一個）數據元素在數組中的下標，從而構成用數組構造的單鏈表（或雙鏈表）。靜態鏈表中的指針又稱仿真指針。78例：一線性表S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)，用靜態鏈表如何表示？data1ZHAO3LI5QIAN6WU0ZHOU4SUN2…………0123456…1000cur說明1：假設S為SLinkList型變量，則S[MAXSIZE]

為一個靜態鏈表；S[0].next則表示第1個結點在數組中的位置。說明2：如果數組的第i個分量表示鏈表的第k個結點，則：S[i].data表示第k個結點的數據；S[i].next

表示第k+1個結點(即k的直接后繼)的位置。i頭結點79例2-6設頭指針為head，并設帶頭結點單鏈表中的數據元素遞增有序，編寫算法將數據元素x插入到帶頭結點單鏈表的適當位置上，要求插入后保持單鏈表數據元素的遞增有序。算法思想：從鏈表的第一個數據元素結點開始，逐個比較每個結點的data域值和x的值，當data小于等于x時，進行下一個結點的比較；否則就找到了插入結點的合適位置，此時申請新結點把x存入，然后把新結點插入；當比較到最后一個結點仍有data小于等于x時，則把新結點插入單鏈表尾。2.5算法設計舉例80voidLinListInsert(SLNode*head,DataTypex){SLNode*curr,*pre,*q;

curr=head->next;pre=head;

while(curr!=NULL&&curr->data<=x){pre=curr; curr=curr->next;}q=(SLNode*)malloc(sizeof(SLNode));q->data=x;

q->next=pre->next;pre->next=q;}81算法設計說明：（1）在循環定位插入位置時，循環條件必須首先是curr!=NULL，然后是curr->data<=x。如果次序顛倒，則當curr為空（即等于鏈表結束標記NULL）時,將因為curr->data不存在而出錯；次序不顛倒時，當curr等于NULL時將退出循環，不會進行后邊條件curr->data<=x的比較。（2）當比較到最后一個結點仍有data小于等于x時，此時有pre指向最后一個結點，curr等于NULL，則上述算法把新結點插入