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

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

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

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

號(hào)單元，比如data[i]。72.2線性表的順序存儲(chǔ)——順序表

82.2線性表的順序存儲(chǔ)——順序表2.2.1順序表的定義和初始化92.2線性表的順序存儲(chǔ)——順序表2.2.1順序表的定義和初始化——方法①和②102.2線性表的順序存儲(chǔ)——順序表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線性表的順序存儲(chǔ)——順序表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;//將表的長(zhǎng)度設(shè)為0，表示表為空}intmain(){SeqList*pSeqList;//定義一個(gè)指向順序表的指針變量

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

return

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

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

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

int

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

int

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

return

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

2.2線性表的順序存儲(chǔ)——順序表

182.2線性表的順序存儲(chǔ)——順序表

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

2.2線性表的順序存儲(chǔ)——順序表

212.2線性表的順序存儲(chǔ)——順序表

222.2線性表的順序存儲(chǔ)——順序表2.2.2順序表的基本操作查找——在表中查找與給定值x相等的數(shù)據(jù)元素偽代碼2-6按年齡查找順序表中的指定學(xué)生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;//定位成功，返回存儲(chǔ)單元的下標(biāo)}2.2線性表的順序存儲(chǔ)——順序表2.2.2順序表的基本操作查找——在表中查找與給定值x相等的數(shù)據(jù)元素偽代碼2-7按學(xué)號(hào)查找順序表中的指定學(xué)生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;//定位成功，返回存儲(chǔ)單元的下標(biāo)}2.3線性表的鏈?zhǔn)酱鎯?chǔ)——單鏈表單鏈表LinkedList類型的定義形式將存儲(chǔ)一個(gè)數(shù)據(jù)元素的變量data，和指示下一個(gè)元素位置的指針變量next，封裝成結(jié)構(gòu)體LinkedList，作為結(jié)點(diǎn)的類型。252.3線性表的鏈?zhǔn)酱鎯?chǔ)——單鏈表2.3.1單向鏈表的結(jié)構(gòu)26

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

28頭結(jié)點(diǎn)頭指針數(shù)據(jù)結(jié)點(diǎn)2.3線性表的鏈?zhǔn)酱鎯?chǔ)——單鏈表無頭結(jié)點(diǎn)單鏈表的定義和初始化29偽代碼2-8typedef

struct_LinkNode{

ElemTypedata;

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

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

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

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

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

head=NULL;

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

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

return

0;}LinkListhead和LinkNode

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

LinkNode*pNew,*p=h;

intj=2;

if(i==1)

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

{

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

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

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

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

h=pNew;

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

return

1;

//插入成功

}

34

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

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

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

//尋找插入位置i

{

j++;

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

}

if(p!=NULL)

{

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

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

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

pNew->next=p->next;

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

p->next=pNew;

return

1;//插入成功

}

else

{

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

return

0;//插入失敗

}}2.3線性表的鏈?zhǔn)酱鎯?chǔ)——單鏈表有頭結(jié)點(diǎn)單鏈表的定義和初始化35typedef

struct_LinkNode{

ElemTypedata;

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

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

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

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

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

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

//設(shè)置有頭結(jié)點(diǎn)的單鏈表為空表，即頭結(jié)點(diǎn)的指針域?yàn)榭?/p>

head->next=NULL;

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

return

0;}偽代碼2-92.3線性表的鏈?zhǔn)酱鎯?chǔ)——單鏈表有頭結(jié)點(diǎn)的單鏈表，和無頭結(jié)點(diǎn)時(shí)的比較有頭結(jié)點(diǎn)單鏈表的插入、刪除、查找、求表長(zhǎng)、輸出等基本操作，雖然與無頭結(jié)點(diǎn)單鏈表的基本操作大體一致，但在細(xì)節(jié)上會(huì)有些差異?；静僮髦胁糠衷葹閔ead

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

LinkNode*pre,*p;

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

return

0;

//刪除失敗

//如果刪除的是第1個(gè)結(jié)點(diǎn)

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

{

p=h;

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

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

free(p);

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

return

1;

//刪除成功

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

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

pre=h;

//pre指向第1個(gè)結(jié)點(diǎn)

p=pre->next;//p指向第2個(gè)結(jié)點(diǎn)

while(p!=NULL)

{

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

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

{

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

pre->next=p->next;

free(p);

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

return

1;

//刪除成功

}

pre=p;

p=p->next;//p指向下一個(gè)結(jié)點(diǎn)

}

return

0;//刪除失敗}偽代碼2-10無頭結(jié)點(diǎn)單鏈表的刪除操作(續(xù))如果刪除的不是第1個(gè)結(jié)點(diǎn)，統(tǒng)一處理！2.3線性表的鏈?zhǔn)酱鎯?chǔ)——單鏈表偽代碼2-11有頭結(jié)點(diǎn)單鏈表的刪除操作40int

del(LinkNode*h,charstuId[]){

LinkNode*pre,*p;

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

pre=h;

//pre指向頭結(jié)點(diǎn)

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

while(p!=NULL)

{

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

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

{

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

free(p);

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

return

1;

//刪除成功

}

pre=p;

p=p->next;//p指向下一個(gè)結(jié)點(diǎn)

}

return

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