數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)（第五版） 課件 第02章 線性表

第2章線性表第2章線性表2.1線性表的定義與操作2.1.1線性表的定義2.1.2線性表的基本操作2.2線性表的順序存儲2.2.1順序表的定義和初始化2.2.2順序表的基本操作2.3線性表的鏈式存儲2.3.1單向鏈表的結(jié)構(gòu)2.3.2單鏈表的基本操作2.3.3循環(huán)鏈表2.3.4雙向鏈表2重難點順序表的多種定義和初始化方式單鏈表的定義、初始化和相關(guān)操作給鏈表添加頭結(jié)點的目的循環(huán)鏈表的基本操作雙向鏈表插入、刪除操作32.1.1線性表的定義

4沒有前驅(qū)，有且僅有一個后繼。沒有后繼，有且僅有一個前驅(qū)。2.1.1線性表的定義——邏輯結(jié)構(gòu)

ABCDEF52.1.2線性表的基本操作線性表上的基本操作有：創(chuàng)建線性表：createList()求表的長度：intgetListLength(L)按值查找：searchList(L,x)，x是給定的待查找數(shù)據(jù)元素或其屬性（數(shù)據(jù)項的值）。插入操作：insertElem(&L,i,x)刪除操作：deleteElem(&L,i,&x)顯示操作：showList(L)62.2線性表的順序存儲——順序表2.2.1順序表的定義和初始化順序表的定義及特點用一組地址連續(xù)的存儲單元（就是數(shù)組），依次存儲線性表中的數(shù)據(jù)元素，這種存儲形式的線性表就稱為順序表。在順序表中所有數(shù)據(jù)元素的物理/存儲順序和邏輯順序是一致的；因此數(shù)據(jù)元素之間的關(guān)系可以隱含，無需存儲。順序表的優(yōu)點：可以隨機存取——知道數(shù)組名data

和下標i，即可直接訪問data數(shù)組的i

號單元，比如data[i]。72.2線性表的順序存儲——順序表

82.2線性表的順序存儲——順序表2.2.1順序表的定義和初始化92.2線性表的順序存儲——順序表2.2.1順序表的定義和初始化——方法①和②102.2線性表的順序存儲——順序表2.2.1順序表的定義和初始化——方法①11#defineN40typedef

struct{

DataTypedata[N];

int

last;}SeqList;//定義順序表類型SeqListvoidinit(SeqList&list)//list為引用參數(shù){list.last=-1;

}intmain(){SeqListseqList;//seqList為局部變量，存放于棧內(nèi)存區(qū)init(seqList);//初始化順序表seqList為空//......//后續(xù)操作

return

0;}偽代碼2-12.2線性表的順序存儲——順序表2.2.1順序表的定義和初始化——方法②12#include<stdlib.h>#defineN40typedef

struct{

ElemTypedata[N];

int

length;}SeqList;//定義順序表類型SeqListvoidinit(SeqList*&pList)//pList為SeqList*類型的引用{pList=(SeqList*)malloc(sizeof(SeqList));pList->length=0;//將表的長度設(shè)為0，表示表為空}intmain(){SeqList*pSeqList;//定義一個指向順序表的指針變量

init(pSeqList);//......//后續(xù)操作

return

0;}偽代碼2-22.2線性表的順序存儲——順序表方法①——適用于順序表空間較小的情況SeqListseqList;//seqList必須定義在main函數(shù)中，程序運行時seqList的空間位于棧內(nèi)存區(qū)缺點：若其中data數(shù)組過大，則會引起棧內(nèi)存溢出方法②——推薦

SeqList*pSeqList;//指向順序表的指針變量優(yōu)點：pSeqList為指針變量，只占用4個字節(jié)；malloc函數(shù)開辟的順序表空間位于堆內(nèi)存區(qū)。缺點：其中data數(shù)組的大小固定為N個單元，若表中元素達到N個，則無法繼續(xù)插入新的數(shù)據(jù)元素。132.2線性表的順序存儲——順序表2.2.1順序表的定義和初始化——方法③142.2線性表的順序存儲——順序表2.2.1順序表的定義和初始化——方法③15#include<stdlib.h>#defineN40typedef

struct{ElemType*pData;//動態(tài)數(shù)組的起始地址，單元可以擴充

int

listSize;//pData所指空間中數(shù)組單元的個數(shù)

int

length;//表中元素的個數(shù)（小于單元個數(shù)）}SeqList;voidinit(SeqList&list)//list為seqList的引用{//給順序表seqList的pData開辟N個單元的初始空間list.pData=(ElemType*)malloc(N*sizeof(ElemType));list.listSize=N;//記錄順序表中數(shù)組單元的個數(shù)為Nlist.length=0;//將順序表的長度設(shè)置為0，表示表為空}偽代碼2-32.2線性表的順序存儲——順序表2.2.1順序表的定義和初始化——方法③16intmain(){SeqListseqList;//定義一個順序表seqListinit(seqList);//......//后續(xù)操作

return

0;}偽代碼2-3seqList.pdata所指空間為動態(tài)分配，空間不夠時可以擴充！方法③適用于：順序表中的元素個數(shù)可能存在很大變動，不易或無法估算最多元素個數(shù)的情況。2.2線性表的順序存儲——順序表2.2.2順序表的基本操作插入——在順序表的第i個位置，插入元素x17

2.2線性表的順序存儲——順序表

182.2線性表的順序存儲——順序表

192.2線性表的順序存儲——順序表2.2.2順序表的基本操作刪除——將表中第i個元素從表中去掉20

2.2線性表的順序存儲——順序表

212.2線性表的順序存儲——順序表

222.2線性表的順序存儲——順序表2.2.2順序表的基本操作查找——在表中查找與給定值x相等的數(shù)據(jù)元素偽代碼2-6按年齡查找順序表中的指定學生23int

locateByAge(SeqList*pList,int

age){

inti=0;

while(i<pList->length&&

pList->data[i].age!=age)i++;

if(i>=pList->length)

return-1;//定位失敗

else

returni;//定位成功，返回存儲單元的下標}2.2線性表的順序存儲——順序表2.2.2順序表的基本操作查找——在表中查找與給定值x相等的數(shù)據(jù)元素偽代碼2-7按學號查找順序表中的指定學生24int

locateByStuId(SeqList*pList,char

stuId[]){

inti=0;

while(i<pList->length&&

strcmp(pList->data[i].stuId,stuId)!=0)i++;

if(i>=pList->length)

return-1;//定位失敗

else

returni;//定位成功，返回存儲單元的下標}2.3線性表的鏈式存儲——單鏈表單鏈表LinkedList類型的定義形式將存儲一個數(shù)據(jù)元素的變量data，和指示下一個元素位置的指針變量next，封裝成結(jié)構(gòu)體LinkedList，作為結(jié)點的類型。252.3線性表的鏈式存儲——單鏈表2.3.1單向鏈表的結(jié)構(gòu)26

2.3線性表的鏈式存儲——單鏈表2.3.1單向鏈表的結(jié)構(gòu)鏈式存儲結(jié)構(gòu)中不要求各結(jié)點的內(nèi)存地址連續(xù)；即，鏈表中各元素的物理/存儲順序和邏輯順序很可能不一致。在每個結(jié)點內(nèi)部，均用指針成員保存下一個結(jié)點的地址。27單鏈表的存取必須從頭指針(變量)開始。2.3線性表的鏈式存儲——單鏈表

28頭結(jié)點頭指針數(shù)據(jù)結(jié)點2.3線性表的鏈式存儲——單鏈表無頭結(jié)點單鏈表的定義和初始化29偽代碼2-8typedef

struct_LinkNode{

ElemTypedata;

//數(shù)據(jù)域

struct_LinkNode*next;//指針域}LinkNode,*LinkList;

//定義結(jié)點類型LinkNode

//和結(jié)點指針類型LinkListintmain(){

LinkNode*head;//定義頭指針變量head

head=NULL;

//設(shè)置無頭結(jié)點的單鏈表為空表

//......//在此進行后續(xù)的插入和刪除等操作

return

0;}LinkListhead和LinkNode

*head，都是定義頭指針變量head；當head的值為NULL時，表示鏈表為空；否則head的值應(yīng)為第一個結(jié)點的地址。2.3線性表的鏈式存儲——單鏈表2.3.2單鏈表的基本操作從表頭插入結(jié)點建立單鏈表30從單鏈表的表頭依次插入線性表(25,45,18,66,24)中的元素，建立單鏈表存儲結(jié)構(gòu)的過程2.3線性表的鏈式存儲——單鏈表2.3.2單鏈表的基本操作從表尾插入結(jié)點建立單鏈表31尾指針(變量)從單鏈表的表尾依次插入線性表(25,45,18,66,24)中的元素，建立單鏈表存儲結(jié)構(gòu)的過程2.3線性表的鏈式存儲——單鏈表2.3.2單鏈表的基本操作在單鏈表的中間某個位置插入一個新結(jié)點32尾指針(變量)從單鏈表的中間插入結(jié)點時，必須先找到插入位置的直接前驅(qū)，否則無法插入。2.3線性表的鏈式存儲——單鏈表插入元素x到單鏈表的第i個位置，i≥1程序2-1無頭結(jié)點單鏈表的Line51~9033//intinsert(LinkList&h,inti,Studentx)intinsert(LinkNode*&h,inti,Studentx){

LinkNode*pNew,*p=h;

intj=2;

if(i==1)

//如果要在單鏈表的最前面插入

{

//給待插入的新結(jié)點開辟空間

pNew=(LinkNode*)malloc(sizeof(LinkNode));

pNew->data=x;//構(gòu)造新結(jié)點

pNew->next=h;//設(shè)置新結(jié)點的指針域

h=pNew;

//頭指針指向新結(jié)點

return

1;

//插入成功

}

34

//p應(yīng)指向新結(jié)點的直接前驅(qū)

//如果i==2，指針p不用后移，因此j的初始值為2

while(p!=NULL&&j<i)

//尋找插入位置i

{

j++;

p=p->next;//指針p后移，使其指向下一個結(jié)點

}

if(p!=NULL)

{

//給待插入的新結(jié)點開辟空間

pNew=(LinkNode*)malloc(sizeof(LinkNode));

pNew->data=x;//構(gòu)造結(jié)點

pNew->next=p->next;

//將結(jié)點插入到p所指結(jié)點之后

p->next=pNew;

return

1;//插入成功

}

else

{

printf("插入位置不合法!\n");

return

0;//插入失敗

}}2.3線性表的鏈式存儲——單鏈表有頭結(jié)點單鏈表的定義和初始化35typedef

struct_LinkNode{

ElemTypedata;

//數(shù)據(jù)域

struct_LinkNode*next;//指針域}LinkNode,*LinkList;

//定義結(jié)點類型LinkNodeintmain(){

LinkNode*head;//定義頭指針變量head

//給頭結(jié)點開辟空間

head=(LinkNode*)malloc(sizeof(LinkNode));

//設(shè)置有頭結(jié)點的單鏈表為空表，即頭結(jié)點的指針域為空

head->next=NULL;

//......//后續(xù)的查找、插入和刪除等操作

return

0;}偽代碼2-92.3線性表的鏈式存儲——單鏈表有頭結(jié)點的單鏈表，和無頭結(jié)點時的比較有頭結(jié)點單鏈表的插入、刪除、查找、求表長、輸出等基本操作，雖然與無頭結(jié)點單鏈表的基本操作大體一致，但在細節(jié)上會有些差異。基本操作中部分原先為head

的地方，需要將其改為head->next362.3線性表的鏈式存儲——單鏈表以刪除操作為例，比較有無頭結(jié)點時的差異假設(shè)指針變量p已指向單鏈表中的待刪除結(jié)點，則刪除*p的操作如下37從單鏈表的中間刪除結(jié)點時，必須先找到刪除位置的直接前驅(qū)(*pre)，否則無法刪除。2.3線性表的鏈式存儲——單鏈表偽代碼2-10無頭結(jié)點單鏈表的刪除操作38//刪除學號為stuId的元素intdel(LinkNode*&h,charstuId[]){

LinkNode*pre,*p;

if(h==NULL)//如果單鏈表為空

return

0;

//刪除失敗

//如果刪除的是第1個結(jié)點

if(strcmp(h->data.stuId,stuId)==0)

{

p=h;

//p指向待刪除結(jié)點

h=h->next;//頭指針指向新的第1個結(jié)點

free(p);

//釋放被刪除結(jié)點

return

1;

//刪除成功

}如果刪除的是第1個結(jié)點，這種沒有前驅(qū)的特殊情況，需要單獨處理！

//查找待刪除結(jié)點的直接前驅(qū)，用pre指向

pre=h;

//pre指向第1個結(jié)點

p=pre->next;//p指向第2個結(jié)點

while(p!=NULL)

{

//如果p指向了待刪除的結(jié)點

if(strcmp(p->data.stuId,stuId)==0)

{

//從鏈表中斷開待刪除的結(jié)點

pre->next=p->next;

free(p);

//釋放被刪除結(jié)點

return

1;

//刪除成功

}

pre=p;

p=p->next;//p指向下一個結(jié)點

}

return

0;//刪除失敗}偽代碼2-10無頭結(jié)點單鏈表的刪除操作(續(xù))如果刪除的不是第1個結(jié)點，統(tǒng)一處理！2.3線性表的鏈式存儲——單鏈表偽代碼2-11有頭結(jié)點單鏈表的刪除操作40int

del(LinkNode*h,charstuId[]){

LinkNode*pre,*p;

//查找待刪除結(jié)點的直接前驅(qū)，用pre指向

pre=h;

//pre指向頭結(jié)點

p=pre->next;//p指向第1個數(shù)據(jù)結(jié)點

while(p!=NULL)

{

//如果p指向了待刪除的結(jié)點

if(strcmp(p->data.stuId,stuId)==0)

{

pre->next=p->next;//斷開待刪除的結(jié)點

free(p);

//釋放被刪除結(jié)點

return

1;

//刪除成功

}

pre=p;

p=p->next;//p指向下一個結(jié)點

}

return

0;//未找到指定結(jié)點，刪除失敗}無論刪除的是不是第1個元素，都不再需要單獨處理！因為第1個元素，已經(jīng)是第2個結(jié)點。2.3線性表的鏈式存儲——循環(huán)鏈表2.3.3循環(huán)鏈表412.3線性表的鏈式存儲——循環(huán)鏈表2.3.3循環(huán)鏈表普通的單向鏈表，判斷p是否指向最后那個結(jié)點判斷p所指結(jié)點的指針域是否為空即p->next==NULL單向循環(huán)鏈表，判斷p是否指向最后那個結(jié)點判斷p所指結(jié)點指針域的值，是否等于頭指針即p->next==head循環(huán)單鏈表也可以只設(shè)一個尾指針，從表頭或表尾插入都方便422.3線性表的鏈式存儲——雙向