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

第2章線(xiàn)性表主要知識(shí)點(diǎn)線(xiàn)性表抽象數(shù)據(jù)類(lèi)型順序表單鏈表循環(huán)單鏈表循環(huán)雙向鏈表靜態(tài)鏈表設(shè)計(jì)舉例2.1

線(xiàn)性表抽象數(shù)據(jù)類(lèi)型1.線(xiàn)性表的定義線(xiàn)性表是一種可以在任意位置插入和刪除數(shù)據(jù)元素操作、由n(n≥0)個(gè)相同類(lèi)型數(shù)據(jù)元素a0,a1,…,an-1組成的線(xiàn)性結(jié)構(gòu)。線(xiàn)性結(jié)構(gòu):2.線(xiàn)性表抽象數(shù)據(jù)類(lèi)型數(shù)據(jù):｛a0,a1,…,an-1｝,ai的數(shù)據(jù)類(lèi)型為DataType操作:(1)ListInitiate(L)初始化線(xiàn)性表(2)ListLength(L)求當(dāng)前數(shù)據(jù)元素個(gè)數(shù)(3)

ListInsert(L,i,x)插入數(shù)據(jù)元素(4)ListDelete(L,i,x)刪除數(shù)據(jù)元素(5)ListGet(L,i,x)取數(shù)據(jù)元素｛a0,a1,…,an-1｝表示數(shù)據(jù)元素有次序關(guān)系,簡(jiǎn)稱(chēng)序列。2.2線(xiàn)性表的順序表示和實(shí)現(xiàn)1.順序表的存儲(chǔ)結(jié)構(gòu)

實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)的方法是使用數(shù)組。數(shù)組把線(xiàn)性表的數(shù)據(jù)元素存儲(chǔ)在一塊連續(xù)地址空間的內(nèi)存單元中，這樣線(xiàn)性表中邏輯上相鄰的數(shù)據(jù)元素在物理存儲(chǔ)地址上也相鄰。數(shù)據(jù)元素間的邏輯上的前驅(qū)、后繼邏輯關(guān)系就表現(xiàn)在數(shù)據(jù)元素的存儲(chǔ)單元的物理前后位置上。順序表的存儲(chǔ)結(jié)構(gòu)如圖所示順序存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表稱(chēng)作順序表a0a1a2a3a4a5…listsize=6MaxSize-10123456其中a0,a1,

a2等表示順序表中存儲(chǔ)的數(shù)據(jù)元素，list表示順序表存儲(chǔ)數(shù)據(jù)元素的數(shù)組，MaxSize表示存儲(chǔ)順序表的數(shù)組的最大存儲(chǔ)單元個(gè)數(shù)，size表示順序表當(dāng)前存儲(chǔ)的數(shù)據(jù)元素個(gè)數(shù)。

typedef

struct{DataType

list[MaxSize];

intsize;}SeqList;2.順序表操作的實(shí)現(xiàn)

（1）初始化ListInitiate(L)void

ListInitiate(SeqList*L) {L->size=0; /*定義初始數(shù)據(jù)元素個(gè)數(shù)*/}

（2）求當(dāng)前數(shù)據(jù)元素個(gè)數(shù)ListLength(L)int

ListLength(SeqListL) {returnL.size;}

（3）插入數(shù)據(jù)元素ListInsert(L,i,x)

int

ListInsert(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++; /*元素個(gè)數(shù)加1*/

return1;}（4）刪除數(shù)據(jù)元素ListDelete(L,i,x)int

ListDelete(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--; /*數(shù)據(jù)元素個(gè)數(shù)減1*/

return1;}（5）取數(shù)據(jù)元素ListGet(L,i,x)int

ListGet(SeqListL,inti,DataType*x){if(i<0||i>L.size-1){printf("參數(shù)i不合法!\n"); return0;}else{ *x=L.list[i];return1;}}3.順序表操作的效率分析時(shí)間效率分析:算法時(shí)間主要耗費(fèi)在移動(dòng)元素的操作上，因此計(jì)算時(shí)間復(fù)雜度的基本操作(最深層語(yǔ)句頻度)T(n)=O(移動(dòng)元素次數(shù))而移動(dòng)元素的個(gè)數(shù)取決于插入或刪除元素的位置i.若i=size，則根本無(wú)需移動(dòng)（特別快）；若i=0，則表中元素全部要后移（特別慢）；應(yīng)當(dāng)考慮在各種位置插入（共n+1種可能）的平均移動(dòng)次數(shù)才合理。設(shè)Pi是在第i個(gè)存儲(chǔ)位置插入一個(gè)數(shù)據(jù)元素的概率，順序表中的數(shù)據(jù)元素個(gè)數(shù)為n,當(dāng)在順序表的任何位置上插入數(shù)據(jù)元素的概率相等時(shí)，有Pi=1/(n+1),則

插入時(shí)的平均移動(dòng)次數(shù)為:n(n+1)/2÷（n+1）＝n/2≈O(n)同理可證:順序表刪除一元素的時(shí)間效率為:T（n)=(n-1)/2≈O(n)

順序表中的其余操作都和數(shù)據(jù)元素個(gè)數(shù)n無(wú)關(guān)，因此，在順序表中插入和刪除一個(gè)數(shù)據(jù)元素的時(shí)間復(fù)雜度為O(n),其余操作的時(shí)間復(fù)雜度都為O(1)主要優(yōu)點(diǎn)是算法簡(jiǎn)單，空間單元利用率高；主要缺點(diǎn)是需要預(yù)先確定數(shù)據(jù)元素的最大個(gè)數(shù)，插入和刪除時(shí)需要移動(dòng)較多的數(shù)據(jù)元素。主要優(yōu)缺點(diǎn)4.順序表應(yīng)用舉例例：編程實(shí)現(xiàn)如下任務(wù):建立一個(gè)線(xiàn)性表，首先依次輸入數(shù)據(jù)元素1，2，3，…，10，然后刪除數(shù)據(jù)元素5，最后依次顯示當(dāng)前線(xiàn)性表中的數(shù)據(jù)元素。要求采用順序表實(shí)現(xiàn)，假設(shè)該順序表的數(shù)據(jù)元素個(gè)數(shù)在最壞情況下不會(huì)超過(guò)100個(gè)。

實(shí)現(xiàn)方法：

1、采用直接編寫(xiě)一個(gè)主函數(shù)實(shí)現(xiàn)。

2、利用已設(shè)計(jì)實(shí)現(xiàn)的抽象數(shù)據(jù)類(lèi)型模塊。（存放在頭文件名為SeqList.h中，通過(guò)#include“SeqList.h”）程序設(shè)計(jì)如下：#include<stdio.h> #defineMaxSize100 typedef

int

DataType;#include"SeqList.h"

voidmain(void){SeqList

myList;

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);}程序運(yùn)行結(jié)果：12346789102.3線(xiàn)性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)1.單鏈表的結(jié)構(gòu)(1)單鏈表中構(gòu)成鏈表的結(jié)點(diǎn)只有一個(gè)指向直接后繼結(jié)點(diǎn)的指針域。其結(jié)構(gòu)特點(diǎn)：邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。結(jié)點(diǎn)結(jié)構(gòu)如圖示：指針域數(shù)據(jù)域nextdata或數(shù)據(jù)域：存儲(chǔ)元素?cái)?shù)值數(shù)據(jù)指針域：存儲(chǔ)直接后繼的存儲(chǔ)位置(2)頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)的區(qū)別頭指針頭結(jié)點(diǎn)首元結(jié)點(diǎn)a0heada1…an^示意圖如下：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)、或?yàn)槭自Y(jié)點(diǎn)）的指針；頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長(zhǎng)等信息，它不計(jì)入表長(zhǎng)度。首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線(xiàn)性表第一個(gè)數(shù)據(jù)元素a０的結(jié)點(diǎn)。(3)帶頭結(jié)點(diǎn)單鏈表和不帶頭結(jié)點(diǎn)單鏈表的比較pa0a1an-1∧…h(huán)eaddatanextx∧s(a)插入前pa0a1an-1∧…h(huán)eaddatanextx∧s(b)插入后1).在帶頭結(jié)點(diǎn)單鏈表第一個(gè)數(shù)據(jù)元素前插入結(jié)點(diǎn)2).刪除帶頭結(jié)點(diǎn)單鏈表第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)pa0a1an-1∧…h(huán)eaddatanext3).在不帶頭結(jié)點(diǎn)單鏈表第一個(gè)數(shù)據(jù)元素前插入結(jié)點(diǎn)a0a1an-1∧…h(huán)eadx∧s(a)插入前a0a1an-1∧…h(huán)eadxs(b)插入后4).在不帶頭結(jié)點(diǎn)單鏈表其他數(shù)據(jù)元素前插入結(jié)點(diǎn)pai-1a0aian-1∧…h(huán)eaddatanextxs…×5).刪除不帶頭結(jié)點(diǎn)單鏈表第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)a0a1an-1∧…h(huán)eaddatanext×6).刪除不帶頭結(jié)點(diǎn)單鏈表其他數(shù)據(jù)元素結(jié)點(diǎn)pai-1a0aian-1∧…h(huán)eaddatanext…×ai+1結(jié)論：（1）帶頭結(jié)點(diǎn)單鏈表無(wú)論在第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)前插入，還是在其他結(jié)點(diǎn)前插入，操作方法一樣；而不帶頭結(jié)點(diǎn)單鏈表在第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)前插入，和在其他結(jié)點(diǎn)前插入，操作方法不一樣（2）刪除操作和插入操作類(lèi)似（3）設(shè)計(jì)帶頭結(jié)點(diǎn)單鏈表的算法時(shí)，頭指針參數(shù)可設(shè)計(jì)成輸入型參數(shù)；設(shè)計(jì)不帶頭結(jié)點(diǎn)單鏈表的算法時(shí)，頭指針參數(shù)必須設(shè)計(jì)成輸出型參數(shù)（4）因此，帶頭結(jié)點(diǎn)單鏈表的算法設(shè)計(jì)簡(jiǎn)單結(jié)點(diǎn)定義：typedef

structNode{

DataTypedata;

structNode*next;}SLNode2.單鏈表的操作實(shí)現(xiàn)（1）初始化ListInitiate(head)voidListInitiate(SLNode**head){

*head=(SLNode*)malloc(sizeof(SLNode));(*head)->next=NULL; }（2）求當(dāng)前數(shù)據(jù)元素個(gè)數(shù)ListLength(head)int

ListLength(SLNode*head){

SLNode*p=head;

intsize=0;

while(p->next!=NULL) {p=p->next; size++; }returnsize;}（3）插入ListInsert(head,i,x)int

ListInsert(SLNode*head,inti,DataTypex){SLNode*p,*q;intj;

p=head;j=-1;

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

if(j!=i-1){printf(“插入位置參數(shù)錯(cuò)！”); return0;}q=(SLNode*)malloc(sizeof(SLNode));q->data=x;q->next=p->next;p->next=q; return1;}說(shuō)明：①要在帶頭結(jié)點(diǎn)的單鏈表第i（0≤i≤size）個(gè)結(jié)點(diǎn)前插入一個(gè)存放數(shù)據(jù)元素x的結(jié)點(diǎn)，首先要在單鏈表中尋找到第i-1個(gè)結(jié)點(diǎn)并由指針p指示，然后動(dòng)態(tài)申請(qǐng)一個(gè)結(jié)點(diǎn)存儲(chǔ)空間并由指針q指示，并把數(shù)據(jù)元素x的值賦予新結(jié)點(diǎn)的數(shù)據(jù)元素域（即q->data=x），最后修改新結(jié)點(diǎn)的指針域指向ai結(jié)點(diǎn)（即q->next=p->next），并修改ai-1結(jié)點(diǎn)的指針域指向新結(jié)點(diǎn)q（即p->next=q）。②循環(huán)條件由兩個(gè)子條件邏輯與組成，其中子條件p->next!=NULL保證指針?biāo)附Y(jié)點(diǎn)存在，子條件j<i-1保證最終讓指針p指向ai-1結(jié)點(diǎn)。

（4）刪除ListDelete(head,i,x)int

ListDelete(SLNode*head,inti,DataType*x){SLNode*p,*s;intj;

p=head;j=-1;

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

if(j!=i-1){printf(“插入位置參數(shù)錯(cuò)！”); return0;}

s=p->next;*x=s->data;p->next=p->next->next;

free(s);return1;}

說(shuō)明：要在帶頭結(jié)點(diǎn)的單鏈表中刪除第i（0≤i≤size-1）個(gè)結(jié)點(diǎn)，首先要在單鏈表中尋找到第i-1個(gè)結(jié)點(diǎn)并由指針p指示，然后讓指針s指向ai結(jié)點(diǎn)（即s=p->next），并把數(shù)據(jù)元素ai的值賦予x（即*x=s->data），最后把a(bǔ)i結(jié)點(diǎn)脫鏈（即p->next=p->next->next），并動(dòng)態(tài)釋放ai結(jié)點(diǎn)的存儲(chǔ)空間（即free(s)）。刪除過(guò)程如圖2-14所示。圖中的①對(duì)應(yīng)算法中的刪除語(yǔ)句。（5）取數(shù)據(jù)元素ListGet(head,i,x)int

ListGet(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(“取元素位置參數(shù)錯(cuò)！”); return0;}

*x=p->data;return1;}

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

p=*head;

while(p!=NULL){p1=p;p=p->next;free(p1); }*head=NULL;}4.單鏈表操作的效率分析單鏈表的插入和刪除操作不需移動(dòng)數(shù)據(jù)元素，只需比較數(shù)據(jù)元素。因此，當(dāng)在單鏈表的任何位置上插入數(shù)據(jù)元素的概率相等時(shí)，在單鏈表中插入一個(gè)數(shù)據(jù)元素時(shí)比較數(shù)據(jù)元素的平均次數(shù)為：刪除一個(gè)數(shù)據(jù)元素時(shí)比較數(shù)據(jù)元素的平均次數(shù)為：另外，單鏈表求數(shù)據(jù)元素個(gè)數(shù)操作的時(shí)間復(fù)雜度為O(n)。和順序表相比主要優(yōu)點(diǎn)是不需要預(yù)先確定數(shù)據(jù)元素的最大個(gè)數(shù)，插入和刪除操作不需要移動(dòng)數(shù)據(jù)元素；主要缺點(diǎn)是查找數(shù)據(jù)元素時(shí)需要順序進(jìn)行，不能像順序表那樣隨機(jī)查找任意一個(gè)數(shù)據(jù)元素。另外，每個(gè)結(jié)點(diǎn)中要有一個(gè)指針域，因此空間單元利用率不高。而且單鏈表操作的算法也較復(fù)雜。單鏈表和順序表相比，單鏈表的優(yōu)點(diǎn)和缺點(diǎn)正好相反。5.單鏈表應(yīng)用舉例例：編程實(shí)現(xiàn)如下任務(wù):建立一個(gè)線(xiàn)性表，首先依次輸入數(shù)據(jù)元素1，2，3，…，10，然后刪除數(shù)據(jù)元素5，最后依次顯示當(dāng)前線(xiàn)性表中的數(shù)據(jù)元素。要求采用單鏈表實(shí)現(xiàn)。#include<stdio.h> #include<stdlib.h> #include<malloc.h>typedef

int

DataType;#include"LinList.h"

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)==0);

printf(“%d”,x);

}

Destroy(&head);}程序運(yùn)行結(jié)果：12346789102.4循環(huán)單鏈表循環(huán)單鏈表是單鏈表的另一種形式，其結(jié)構(gòu)特點(diǎn)是鏈表中最后一個(gè)結(jié)點(diǎn)的指針域指向整個(gè)鏈表的第一個(gè)結(jié)點(diǎn)，從而使鏈表形成一個(gè)環(huán)。它的優(yōu)點(diǎn)是從鏈尾到鏈頭比較方便。循環(huán)單鏈表也有帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)兩種結(jié)構(gòu)。一個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表如下圖示：a0a1an-1…h(huán)eadhead(a)空鏈表(b)非空鏈表程序設(shè)計(jì)：p!=NULL 改為 p!=headP->next!=NULL 改為 p->next!=head2.5雙向鏈表雙向鏈表是每個(gè)結(jié)點(diǎn)除后繼指針域外還有一個(gè)前驅(qū)指針域，它有帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)，循環(huán)和非循環(huán)結(jié)構(gòu)，雙向鏈表是解決查找前驅(qū)結(jié)點(diǎn)問(wèn)題的有效途徑。結(jié)點(diǎn)結(jié)構(gòu)如圖示：priordatanext下圖是帶頭結(jié)點(diǎn)的循環(huán)雙向鏈表的結(jié)構(gòu)，可見(jiàn)，其前驅(qū)指針和后繼指針各自構(gòu)成自己的循環(huán)單鏈表。head(a)空鏈表a0a1an-1head(b)非空鏈表…在雙向鏈表中:設(shè)指針p指向第i個(gè)數(shù)據(jù)元素結(jié)點(diǎn)，則p->next指向第i+1個(gè)數(shù)據(jù)元素結(jié)點(diǎn)，p->next->prior仍指向第i個(gè)數(shù)據(jù)元素結(jié)點(diǎn)，即p->next->prior=p;同樣p->prior->next=p。循環(huán)雙向鏈表的插入過(guò)程如圖示：a0aian-1head…xs…ai-1××…④①②③p刪除過(guò)程如圖示：ai+1aian-1head……ai-1××①②p2.6靜態(tài)鏈表在數(shù)組中增加一個(gè)(或兩個(gè))指針域用來(lái)存放下一個(gè)(或上一個(gè))數(shù)據(jù)元素在數(shù)組中的下標(biāo)，從而構(gòu)成用數(shù)組構(gòu)造的單鏈表。因?yàn)閿?shù)組內(nèi)存空間的申請(qǐng)方式是靜態(tài)的，所以稱(chēng)為靜態(tài)鏈表，增加的指針?lè)Q做仿真指針。結(jié)構(gòu)如下：ABCE∧headD(a)常規(guī)鏈表A1B2C3D4E-1┇(b)靜態(tài)鏈表1datanext01234┇maxSize-1A2E-1B4D1C3┇(b)靜態(tài)鏈表2datanext01234┇maxSize-12.7設(shè)計(jì)舉例例2-4設(shè)計(jì)一個(gè)順序表的刪除函數(shù)，把順序表L中的數(shù)據(jù)元素x刪除。算法思想：首先，找到要?jiǎng)h除元素的位置，然后，從這個(gè)位置到最后一個(gè)元素，逐個(gè)前移，最后，把元素個(gè)數(shù)減1。int

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

例2-5構(gòu)造一個(gè)順序表的刪除算法，把順序表L中所有值相同的數(shù)據(jù)元素x全部刪除。算法思想：在例2-4所設(shè)計(jì)的刪除算法的基礎(chǔ)上，增加外重循環(huán)進(jìn)行查找，查找到元素x則刪除，然后繼續(xù)進(jìn)行這樣的過(guò)程和刪除過(guò)程，直到元素末尾結(jié)束。int

ListMoreDataDelete(SeqList*L,DataTypex){inti,j;

inttag=0;

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

L->list[j]=L->list[j+1]; L->size--;

i--;

tag=1; }}

returntag;}例2-6設(shè)頭指針為head，并設(shè)帶頭結(jié)點(diǎn)單鏈表中的數(shù)據(jù)元素遞增有序，編寫(xiě)算法將數(shù)據(jù)元素x插入到帶頭結(jié)點(diǎn)單鏈表的適當(dāng)位置上，要求插入后保持單鏈表數(shù)據(jù)元素的遞增有序。算法思想：從鏈表的第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)開(kāi)始，逐個(gè)比較每個(gè)結(jié)點(diǎn)的data域值和x的值，當(dāng)data小于等于x時(shí)，進(jìn)行下一個(gè)結(jié)點(diǎn)的比較；否則就找到了插入結(jié)點(diǎn)的合適位置，此時(shí)申請(qǐng)新結(jié)點(diǎn)把x存入，然后把新結(jié)點(diǎn)插入；當(dāng)比較到最后一個(gè)結(jié)點(diǎn)仍有data小于等于x時(shí)，則把新結(jié)點(diǎn)插入單鏈表尾。voidLinListInsert(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;}算法設(shè)計(jì)說(shuō)明：（1）在循環(huán)定位插入位置時(shí)，循環(huán)條件必須首先是curr!=NULL，然后是curr->data<=x。如果次序顛倒，則當(dāng)curr為空（即等于鏈表結(jié)束標(biāo)記NULL