數(shù)據(jù)結(jié)構(gòu)與算法（C++版）課件第2章 線性表

第2章線性表數(shù)據(jù)結(jié)構(gòu)與算法

(C++版)(第2版)2.1線性表的邏輯結(jié)構(gòu)一、線性表的定義和特點(diǎn)1.線性表的定義

n（

0）個(gè)數(shù)據(jù)元素的有限序列，記作:

（a1,a2,…,an）

ai

是線性表中數(shù)據(jù)元素，n是線性表長度，其中ai稱為ai+1的直接前驅(qū)，簡稱為前驅(qū)，ai+1稱為ai的直接后繼，簡稱為后繼。

2.線性表的特點(diǎn)除第一個(gè)元素外，其他每一個(gè)元素有一個(gè)且僅有一個(gè)直接前驅(qū)。除最后一個(gè)元素外，其他每一個(gè)元素有一個(gè)且僅有一個(gè)直接后繼。a1a2a3a4a5a6一、線性表基本操作（1）intLength()const

初始條件：線性表已存在。

操作結(jié)果：返回線性表元素個(gè)數(shù)。

（2）boolEmpty()const

初始條件：線性表已存在。

操作結(jié)果：如線性表為空，則返回true，否則返回false。（3）voidClear()

初始條件：線性表已存在。

操作結(jié)果：清空線性表。

（4）voidTraverse(void(*visit)(constElemType&)) const

初始條件：線性表已存在。

操作結(jié)果：依次對線性表的每個(gè)元素調(diào)用函數(shù)(*visit)。（5）boolGetElem(intposition,ElemType&e)const

初始條件：線性表已存在，1≤position≤Length()。

操作結(jié)果：用e返回第position個(gè)元素的值。

（6）boolSetElem(intposition,constElemType&e)

初始條件：線性表已存在，1≤position≤Length()。

操作結(jié)果：將線性表的第position個(gè)位置的元素賦值為e。（7）boolDelete(intposition,ElemType&e)

初始條件：線性表已存在，1≤position≤Length()。

操作結(jié)果：刪除線性表的第position個(gè)位置的元素,并用e返回其值，長度減1。（8）boolDelete(intposition)初始條件：線性表已存在，1≤position≤Length()。操作結(jié)果：刪除線性表的第position個(gè)元素,，長度減1。（9）boolInsert(intposition,constElemType&e)

初始條件：線性表已存在，1≤position≤Length()+1。

操作結(jié)果：在線性表的第position個(gè)位置前插入元素e，長度加1。2.2線性表的順序存儲結(jié)構(gòu)1.順序表的定義和特點(diǎn)定義：將線性表中的元素相繼存放在一個(gè)連續(xù)的存儲空間中。特點(diǎn)：可利用一維數(shù)組描述存儲結(jié)構(gòu)，采用線性表的順序存儲方式253457164809

012345elemsa1

a2

a3

a4

a5

a6

2.順序表(SeqList)類模板的

定義//順序表類模板template<classElemType>classSqList{protected://順序表實(shí)現(xiàn)的數(shù)據(jù)成員: intcount; //元素個(gè)數(shù)

intmaxSize; //順序表最大元素個(gè)數(shù)

ElemType*elems; //元素存儲空間public://抽象數(shù)據(jù)類型方法聲明及重載編譯系統(tǒng)默認(rèn)方法聲明: SqList(intsize=DEFAULT_SIZE);

//構(gòu)造函數(shù)模板

virtual~SqList(); //析構(gòu)函數(shù)模板

intLength()const; //求線性表長度

boolEmpty()const; //判斷線性表是否為空

voidClear(); //將線性表清空 voidTraverse(void(*visit)(constElemType&)) const; //遍歷線性表

boolGetElem(intposition,ElemType&e)const; //求指定位置的元素

boolSetElem(intposition,constElemType&e);

//設(shè)置指定位置的元素值

boolDelete(intposition,ElemType&e);//刪除元素

boolDelete(intposition); //刪除元素

boolInsert(intposition,constElemType&e);

//插入元素

SqList(constSqList<elemType>&source);

//復(fù)制構(gòu)造函數(shù)模板

SqList<elemType>&operator=(const SqList<elemType>&source);

//重載賦值運(yùn)算符};template<classElemType>SqList<ElemType>::SqList(intsize)//操作結(jié)果：構(gòu)造一個(gè)最大元素個(gè)數(shù)為size的空順序表{ maxSize=size; //最大元素個(gè)數(shù) elems=newElemType[maxSize];//分配存儲空間 count=0; //空線性表元素個(gè)數(shù)為0}template<classElemType>SqList<ElemType>::~SqList()//操作結(jié)果：銷毀線性表{ delete[]elems; //釋放存儲空間}3.順序表部分操作的實(shí)現(xiàn)（1）表項(xiàng)的插入25345716480963

a1

a2

a3

a4

a5

a6

a7

a8elems50插入e2534575016480963

a1

a2

a3

e

a4

a5

a6

a7elems50itemplate<classElemType>boolSqList<ElemType>::Insert(intposition,constElemType&e)//操作結(jié)果：在線性表的第position個(gè)元素前插入元素e，// position的的取值范圍為// 1≤position≤Length()+1，如線性表已滿,則返回// false，如position合法,則返回true,否則返回false{ if(count==maxSize) { //線性表已滿返回false returnfalse; } elseif(position<1||position>Length()+1) { //position范圍錯(cuò) returnfalse; //范圍錯(cuò) }

else { //成功 intlength=Length(); //暫存線性表長度

ElemTypetemElem; //臨時(shí)元素

count++; //插入后元素個(gè)數(shù)將自增1 for(inttemPos=length;temPos>=position; temPos--) { //插入位置之后的元素右移

GetElem(temPos,temElem);

SetElem(temPos+1,temElem); } SetElem(position,e); //將e賦值到position處 returntrue; //插入成功 }}（2）表項(xiàng)的刪除2534575016480963

a1

a2

a3

a4

a5

a6

a7

a8elems16刪除

e25345750480963

a1

a2

a3

a4

a6

a7

a8

a9elemstemplate<classElemType>boolSqList<ElemType>::Delete(intposition,ElemType&e)//操作結(jié)果：刪除線性表的第position個(gè)元素,并前用e返// 回其值，position的取值范圍為1≤position≤Length()，// position合法時(shí)返回true，否則返回false{ if(position<1||position>Length()) { //position范圍錯(cuò) returnfalse; //范圍錯(cuò) } else { //position合法 GetElem(position,e); //用e返回被刪除元素 ElemTypetemElem; //臨時(shí)元素 for(inttemPos=position+1; temPos<=Length();temPos++) { //被刪除元素之后的元素依次左移

GetElem(temPos,temElem);

SetElem(temPos-1,temElem);

} count--; //刪除后元素個(gè)數(shù)將自減1 returntrue; //刪除成功 }}4.順序表的應(yīng)用：集合的“差”運(yùn)算//文件路徑名:s2_1\alg.htemplate<classElemType>voidDifference(constSqList<ElemType>&la, constSqList<ElemType>&lb, SqList<ElemType>&lc)//操作結(jié)果:用lc返回la和lb表示的集合的差集//方法:在la中取出元素,在lb中進(jìn)行查找,如果未在lb中// 出現(xiàn)了,將其插入到lc{ ElemTypeaElem,bElem; lc.Clear(); //清空lc for(intaPos=1;aPos<=la.Length();aPos++) { la.GetElem(aPos,aElem);

//取出la的一個(gè)元素aElem boolisExist=false;

//表示aElem是否在lb中出現(xiàn)

for(intbPos=1;bPos<=lb.Length();bPos++) { lb.GetElem(bPos,bElem);

//取出lb的一個(gè)元素bElem if(aElem==bElem) { isExist=true; //aElem同時(shí)在la和lb中

//出現(xiàn),置isExist為true

break; //退出內(nèi)層循環(huán)

} } if(!isExist) { //aElem在la中出現(xiàn),而未在lb中未出現(xiàn), // 將其插入到lc中

lc.Insert(lc.Length()+1,aElem); } }}2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)一、單鏈表

(SinglyLinkedList)

用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。以data(元素的值)

+next(后繼)=結(jié)點(diǎn)(表示數(shù)據(jù)元素)以“結(jié)點(diǎn)的序列”表示線性表稱作單鏈表1.單鏈表的概念

以線性表中第一個(gè)數(shù)據(jù)元素a1的存儲地址作為線性表的地址，稱作線性表的頭指針。頭結(jié)點(diǎn)

a1a2…...an^頭指針頭指針

有時(shí)為了操作方便，在第一個(gè)結(jié)點(diǎn)之前虛加一個(gè)“頭結(jié)點(diǎn)”，這時(shí)指向頭結(jié)點(diǎn)的指針稱為鏈表的頭指針。空指針線性表為空表時(shí)，頭結(jié)點(diǎn)的指針成份為空

//結(jié)點(diǎn)類模板template<classElemType>structNode{//數(shù)據(jù)成員: ElemTypedata; //數(shù)據(jù)成分

Node<ElemType>*next; //指針成分//構(gòu)造函數(shù)模板: Node(); //無參數(shù)的構(gòu)造函數(shù)模板

Node(ElemTypee,Node<ElemType>*link= NULL);//已知數(shù)據(jù)成份和指針成份建立結(jié)構(gòu)};2.單鏈表的相關(guān)類模板//簡單線性鏈表類模板template<classElemType>classSimpleLinkList{protected://鏈表實(shí)現(xiàn)的數(shù)據(jù)成員:

Node<ElemType>*head; //頭結(jié)點(diǎn)指針//輔助函數(shù)模板: Node<ElemType>*GetElemPtr(intposition)const; //返回指向第position個(gè)結(jié)點(diǎn)的指針public://抽象數(shù)據(jù)類型方法聲明及重載編譯系統(tǒng)默認(rèn)方法聲明: SimpleLinkList(); //無參數(shù)構(gòu)造函數(shù)模板

virtual~SimpleLinkList(); //析構(gòu)函數(shù)模板

intLength()const; //求線性表長度

boolEmpty()const; //判斷線性表是否為空

voidClear(); //將線性表清空

voidTraverse(void(*visit)(constElemType&)) const; //遍歷線性表

boolGetElem(intposition,ElemType&e)const; //求指定位置的元素

boolSetElem(intposition,constElemType&e); //設(shè)置指定位置的元素值 boolDelete(intposition,ElemType&e);//刪除元素 boolDelete(intposition);//刪除元素

boolInsert(intposition,constElemType&e); //插入元素

SimpleLinkList(constSimpleLinkList<ElemType> &source); //復(fù)制構(gòu)造函數(shù)模板

SimpleLinkList<ElemType>&operator=(const SimpleLinkList<ElemType>&source); //重載賦值運(yùn)算符};3.單鏈表中的插入與刪除插入newPtr=newNode<ElemType>(e,temPtr->next);temPtr->next=newPtr;

template<classElemType>boolSimpleLinkList<ElemType>::Insert( intposition,constElemType&e)//操作結(jié)果：在線性表的第position個(gè)位置前插入元素e// position的取值范圍為1≤position≤Length()+1// position合法時(shí)返回true,否則返回false{ if(position<1||position>Length()+1) { //position范圍錯(cuò)

returnfalse; //位置不合法

} else { //position合法

Node<ElemType>*temPtr; temPtr=GetElemPtr(position-1); //取出指向第position-1個(gè)結(jié)點(diǎn)的指針

Node<ElemType>*newPtr; newPtr=newNode<ElemType>(e, temPtr->next); //生成新結(jié)點(diǎn)

temPtr->next=newPtr; //將temPtr插入到鏈表中

returntrue; }}刪除

nextPtr=temPtr->next; //nextPtr為temPtr的后繼

temPtr->next=nextPtr->next;//刪除結(jié)點(diǎn)

deletenextPtr; //釋放被刪結(jié)點(diǎn)在單鏈表中刪除含b的結(jié)點(diǎn)template<classElemType>BoolSimpleLinkList<ElemType>::Delete(intposition, ElemType&e)//操作結(jié)果：刪除線性表的第position個(gè)位置的元素,并用// e返回其值,position的取值范圍為// 1≤position≤Length(),position合法時(shí)返回// true,否則返回false{ if(position<1||position>Length()) { //position范圍錯(cuò)

returnfalse; } else { //position合法

Node<ElemType>*temPtr; temPtr=GetElemPtr(position-1); //取出指向第position-1個(gè)結(jié)點(diǎn)的指針

Node<ElemType>*nextPtr=temPtr->next; //nextPtr為temPtr的后繼

temPtr->next=nextPtr->next;//刪除結(jié)點(diǎn)

e=nextPtr->data;//用e返回被刪結(jié)點(diǎn)元素值

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

returntrue; }}二、循環(huán)鏈表(CircularList)循環(huán)鏈表是單鏈表的變形。循環(huán)鏈表最后一個(gè)結(jié)點(diǎn)的next指針不為NULL，而是指向了表的前端。為簡化操作，在循環(huán)鏈表中往往加入表頭結(jié)點(diǎn)。循環(huán)鏈表的特點(diǎn)是：只要知道表中某一結(jié)點(diǎn)的地址，就可搜尋到所有其他結(jié)點(diǎn)的地址。1.循環(huán)鏈表的概念2.循環(huán)鏈表示例//簡單循環(huán)鏈表類模板template<classElemType>classSimpleCircLinkList{protected://循環(huán)鏈表實(shí)現(xiàn)的數(shù)據(jù)成員: Node<ElemType>*head; //頭結(jié)點(diǎn)指針//輔助函數(shù)模板: Node<ElemType>*GetElemPtr(intposition)const; //返回指向第position個(gè)結(jié)點(diǎn)的指針3.循環(huán)鏈表的相關(guān)類模板public://抽象數(shù)據(jù)類型方法聲明及重載編譯系統(tǒng)默認(rèn)方法聲明: SimpleCircLinkList(); //無參數(shù)的構(gòu)造函數(shù)模板

virtual~SimpleCircLinkList(); //析構(gòu)函數(shù)模板

intLength()const; //求線性表長度

boolEmpty()const; //判斷線性表是否為空

voidClear(); //將線性表清空

voidTraverse(void(*visit)(constElemType&)) const; //遍歷線性表

boolGetElem(intposition,ElemType&e) const; //求指定位置的元素

boolSetElem(intposition,constElemType&e); //設(shè)置指定位置的元素值 boolDelete(intposition,ElemType&e);//刪除元素 boolDelete(intposition); //刪除元素

boolInsert(intposition,constElemType&e); //插入元素

SimpleCircLinkList(const SimpleCircLinkList<ElemType>&source); //復(fù)制構(gòu)造函數(shù)模板

SimpleCircLinkList<ElemType>&operator=(const SimpleCircLinkList<ElemType>&source); //重載賦值運(yùn)算符};4.循環(huán)鏈表的應(yīng)用——用循環(huán)鏈表求解約瑟夫問題約瑟夫問題的提法

n個(gè)人圍成一個(gè)圓圈，首先第1個(gè)人從1開始一個(gè)人一個(gè)人順時(shí)針報(bào)數(shù),報(bào)到第m個(gè)人，令其出列。然后再從下一個(gè)人開始，從1順時(shí)針報(bào)數(shù)，報(bào)到第m個(gè)人，再令其出列，…，如此下去,直到圓圈中只剩一個(gè)人為止。此人即為優(yōu)勝者。例如n=8m=3//文件路徑名:s2_5\alg.hvoidJosephus(intn,intm)//操作結(jié)果:n個(gè)人圍成一個(gè)圓圈，首先第1個(gè)人從1開始一// 個(gè)人一個(gè)人順時(shí)針報(bào)數(shù),報(bào)到第m個(gè)人，令其出列。// 然后再從下一個(gè)人開始，從1順時(shí)針報(bào)數(shù)報(bào)到第m// 個(gè)人，再令其出列，…，如此下去,直到圓圈中只// 剩一個(gè)人為止。此人即為優(yōu)勝者{ SimpleCircLinkList<int>la; //定義空循環(huán)鏈表

intpos=0; //報(bào)數(shù)到的人在鏈表中序號

intout,winer; for(intk=1;k<=n;k++)la.Insert(k,k); //建立數(shù)據(jù)成份為1,2,..,n的循環(huán)鏈表 cout<<"出列者:"; for(inti=1;i<n;i++) { //循環(huán)n-1次，讓n-1個(gè)個(gè)出列

for(intj=1;j<=m;j++) { //從1報(bào)數(shù)到m pos++; if(pos>la.Length()) pos=1; } la.Delete(pos--,out);//報(bào)數(shù)到m的人出列

cout<<out<<""; } la.GetElem(1,winer); //剩下的一個(gè)人為優(yōu)勝者

cout<<endl<<"優(yōu)勝者:"<<winer<<endl;}三、雙向鏈表

(DoublyLinkedList)1.雙向鏈表的概念雙向鏈表是指在前驅(qū)和后繼方向都能游歷(遍歷)的線性鏈表。雙向鏈表每個(gè)結(jié)點(diǎn)結(jié)構(gòu)：前驅(qū)方向后繼方向雙向鏈表通常