老師課件描述線性表

主要內(nèi)容線性表的定義抽象鏈表類單鏈表循環(huán)鏈表線性表的定義線性表的邏輯結構線性表的順序存儲表示線性表的鏈式存儲表示線性表的邏輯結構線性表是n>=0個數(shù)據(jù)元素a1，a2……an-1，an的有序集合。表中每個元素ai在表中的位置僅取決于元素本身的序號i。當1<i<n時，ai的直接前驅(qū)為ai-1，ai的直接后繼為ai+1。也就是說，除表中第一個元素a1與最后一個元素an外，其他每個元素ai有且僅有一個直接前驅(qū)和一個直接后繼；第一個元素a1僅有一個直接后繼，最后一個元素an僅有一個直接前驅(qū)。上述這種結構的特點是數(shù)據(jù)元素之間存在一對一的關系，這種特點的數(shù)據(jù)結構稱為線性結構，也稱為線性表。一個線性表可以用一個標識符來命名。例如：L=(

a1，a2，a3……an-1，an

)注意：同一線性表中的元素必定具有相同的特性，都屬于同一數(shù)據(jù)對象。線性表中的數(shù)據(jù)元素在不同情況下可能有不同的具體含義。如

L1＝

(

1.2，-2.3，56，0，45.7

)L2＝

(

a，d，c，g，j，l

)在稍微復雜的線性表中，一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項組成。例如：學生名冊：010501黎明17男010502王煙18女010503曲柳17女010504何旦旦19男010505李美16女線性表的順序存儲方式在計算機內(nèi)部可以采用兩種不同方法來表示一個線性表，它們分別是順序表表示法和鏈表表示法。順序表示法的定義；元素的地址表示；順序表示法的優(yōu)、缺點。順序表示法的定義順序表示法用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素，這種存儲結構稱為線性表的順序存儲結構，并稱此時的線性表為順序表。線性表的順序表示順序映象——以x

的存儲位置和y

的存儲位置之間某種關系表示邏輯關系<x,y>。最簡單的一種順序映象方法是：令y的存儲位置和x的存儲位置相鄰。用一組地址連續(xù)的存儲單元依次存放線性表中的數(shù)據(jù)元素a1a2…ai-1ai…an線性表的起始地址

稱作線性表的基地址以“存儲位置相鄰”表示有序?qū)?lt;ai-1，ai即：LOC(ai)=LOC(ai-1)+C一個數(shù)據(jù)元素所占存儲量↑所有數(shù)據(jù)元素的存儲位置均取決于第一個數(shù)據(jù)元素的存儲位置LOC(ai)

=

LOC(a1)

+

(i-1)×C↑基地址邏輯地址數(shù)據(jù)元素存儲地址數(shù)據(jù)元素0k0Loc(k0)

k01k1Loc(k0)+c

k1………

…ikiLoc(k0)+i*c

ki……n-1kn-1Loc(k0)+(n-1)*c

kn-1線性表的順序存儲結構示意圖元素的地址表示假設線性表的每個元素占用C個存儲單元，那么，在順序存儲結構中，線性表的第i+1個數(shù)據(jù)元素ai+1的存儲位置與第i個數(shù)據(jù)元素ai的存儲位置之間滿足如下關系：LOC(ai+1)

=LOC(ai)+CLOC(ai)

=LOC(a0)+i*CLOC(a0)為線性表的首地址或基地址。以元素在計算機內(nèi)存中的“物理位置相鄰來表示線性表中數(shù)據(jù)元素之間的邏輯關系，只要確定了首地址，線性表中任意數(shù)據(jù)元

素都可以隨機存取順序表示法的優(yōu)缺點優(yōu)點：存儲密度大、空間利用率高；數(shù)據(jù)元素邏輯位置相鄰，物理位置也相鄰?？呻S機存取，所以稱為隨機存取結構。缺點：插入和刪除時要移動大量的元素；長度較大的線性表須按最大需要的空間來分配存儲空間。線性表的鏈式存儲表示鏈式存儲表示的定義鏈式存儲表示的實現(xiàn)鏈式存儲表示的特點線性表的鏈式表示用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素以元素(數(shù)據(jù)元素的映象)+指針(指示后繼元素存儲位置)=

結點(表示數(shù)據(jù)元素

或 數(shù)據(jù)元素的映象)以“結點的序列”表示線性表稱作鏈表數(shù)據(jù)域指針域結點：數(shù)據(jù)元素的存儲映象，由數(shù)據(jù)域和指針域構成設ai的存儲位置為p,則ai+1的地址q是：q=p->next;a1a2a3a4a5a6an^……鏈式存儲方式

鏈式存儲結構不要求邏輯上相鄰的數(shù)據(jù)元素在物理位置上也相鄰；鏈表：是用一組地址任意的存儲單元存放線性表的各個數(shù)據(jù)元素，通過保存直接后繼的存儲位置來表示元素之間的邏輯關系；所有的數(shù)據(jù)元素都分別保存在具有相同數(shù)據(jù)結構的結點中,結點是鏈表的基本存儲單位,結點與數(shù)據(jù)元素一一對應；每個結點在鏈表中使用一塊連續(xù)的存儲空間,而相鄰結點之間不必使用連續(xù)的存儲空間。鏈式存儲表示的特點邏輯上相鄰的元素對應的存儲位置是通過指針反映的，不要求物理上相鄰。進行插入、刪除運算時，只需修改被插入位置指針域。一般不預先分配好足夠的存儲空間以備使用，當有元素插入時，需臨時分配一個空的結點空間，填上信息，插入到線性鏈表中；當某個結點不再使用時，應將其存儲空間釋放。不足之處：每個結點設有一個指針域，存儲空間的開銷較大。抽象鏈表類線性鏈表的實現(xiàn)抽象鏈表類的定義抽象鏈表類中典型成員函數(shù)的實現(xiàn)鏈式存儲的實現(xiàn)數(shù)據(jù)元素的存儲結構－－結點 結點(表示數(shù)據(jù)元素的映象)=元素+指針(指示后繼元素的存儲位置)ai數(shù)據(jù)域data指針域next結點如果結點中只包含一個指針域，稱為單鏈表鏈表結點與組成鏈表是動態(tài)數(shù)據(jù)結構，通過指針（鏈）將結點鏈接在一起。結點包括兩部分：數(shù)據(jù)信息和鏈接結點的指針；結點分為表頭結點和表結點；指向鏈表表頭結點的指針(表頭指針，也稱為頭指針)；表頭結點(鏈表的第一個結點)，一般不存放數(shù)據(jù)元素的信息；表結點（數(shù)據(jù)結點，也稱為結點，保存數(shù)據(jù)信息）。鏈表的圖示NULL表頭指針表頭結點數(shù)據(jù)結點數(shù)據(jù)結點數(shù)據(jù)結點數(shù)據(jù)結點ListNode(){next

=Null;}//無參數(shù)，構造一個空結點ListNode(const

type

&item,ListNode<type>*next1=NULL)

//帶參數(shù)，構造一個非空結點{

data=item;

next=next1;}

//包含數(shù)據(jù)域和指針域type

data;

//結點的數(shù)據(jù)域ListNode

<type>

*next;

//結點的指針域};datanext鏈表結點類的定義template

<class

type>

class

ListNode{public:鏈表的常用操作獲取表頭指針；求鏈表的長度；尋找第i個數(shù)據(jù)元素；根據(jù)關鍵字值求數(shù)據(jù)元素在鏈表中的位置；插入數(shù)據(jù)元素；修改數(shù)據(jù)元素的值；刪除數(shù)據(jù)元素。抽象鏈表類的定義線性鏈表有3種：單鏈表、循環(huán)鏈表與雙向鏈表；抽象出上述三種線性鏈表的相同點（結點、指針和相同操作），建立一個抽象鏈表類，再由此抽象鏈表類派生出新的鏈表類（單鏈表和循環(huán)鏈表）；采用類模板機制；增加表頭結點，統(tǒng)一空表和非空表的操作。抽象鏈表類定義//抽象類鏈表的定義template<class

type>class

ablist{public:ListNode<type>*GetHead()//獲得表頭結點指針{

return

head;

}//取出鏈表中的第i個元素

type

Get(int

i);抽象鏈表類定義//將鏈表中第i個結點元素值設置為xbool

Set(type

x,int

i);//尋找數(shù)據(jù)元素值為value的結點地址

ListNode<type>*Find1(type

value);//尋找鏈表中第i個結點元素的地址ListNode<type>*Find(int

i);void

MakeEmpt();

//將鏈表置為空表//純虛函數(shù)，取得結點n的下一個結點位置

virtual

ListNode<type>*GetNext(ListNode<type>&n)=0;//純虛函數(shù)，將新元素value插入到第i個位置

virtual

int

Insert(type

value,

int

i)=0;//純虛函數(shù)，將新元素value插入到鏈表表頭處

virtual

int

Insert(type

value)=0;//純虛函數(shù)，將鏈表中第i個結點刪去

virtual

int

Remove(int

i)=0;//純虛函數(shù)，將元素值為value的結點刪去

virtual

int

Remove(type

value)=0;protected:

//鏈表的數(shù)據(jù)成員：頭指針和表長ListNode<type>

*head;intlength;};抽象鏈表成員函數(shù)的實現(xiàn)設置函數(shù)：將第i個結點數(shù)據(jù)元素值設為x。template<class

type>bool

ablist<type>::Set(type

x,

int

i){ListNode<type> *p

=

Find(i);

//尋找第i個結點位置if(p==NULL||p==head)

//i值不合法或為空表，返回falsereturn

false;elsep->data=x;

//修改第i個結點的數(shù)據(jù)元素值return

ture;}取值函數(shù)：返回第i個結點的數(shù)據(jù)元素值。template<class

type>type

ablist<type>::Get(int

i){

//尋找指向第i個結點位置

ListNode<type>

*p=Find(i);assert

(p

&&

p!=head);

//p不空也不為表頭return

p->data;

//返回第i個結點的數(shù)據(jù)元素值}清空鏈表：用q指向第一個結點，當鏈表不空時，循鏈逐個刪除，僅保留表頭結點。template<class

type>void

ablist<type>::MakeEmpty(){ListNode<type>

*q=head->next;int

i=1;

//鏈表不空，所以至少有一個結點

while(i++<=length)

//當鏈表不空時，刪去表中所有結點{ head->next=q->next;delete

q;

//循鏈逐個刪除，僅保留表頭結點

q=head->next;}length=0;}搜索數(shù)據(jù)元素值為value的結點template<class

type>ListNode<type>*ablist<type>::Find1(type

value){ListNode<type>

*p=head->next;int

i=1;

//循環(huán)條件包含空鏈表的情況

while

(i++<=length

&&

p->data!=value)p=p->next;

//循鏈找數(shù)據(jù)元素值value的結點

return

p;}定位函數(shù)：返回鏈表中第i個元素結點的地址

template<classtype>ListNode<type>*ablist<type>::Find(int

i){

if(i<0

||

i>length)

return

NULL;if(i==0)

return

head;

//i=0時返回表頭結點的地址ListNode<type>*p=head->next;//讓檢測指針p指向表中第1個結點int

j=1;while(p!=NULL

&&

j<i)

//循鏈掃描，至第i個結點地址{p=p->next;j++;}return

p;

//返回第i個結點地址}單鏈表單鏈表的定義單鏈表類的定義單鏈表常用成員函數(shù)的實現(xiàn)單鏈表的定義單鏈表的定義帶表頭結點的單鏈表單鏈表的定義單鏈表用一組任意的存儲單元來存儲線性表的各個數(shù)據(jù)元素，這些存儲單元可以是連續(xù)的，也可以是不連續(xù)的；為了表示線性表中每個元素與其直接后繼

元素之間的邏輯關系，單鏈表由一個個結

點組成，每個結點作為數(shù)據(jù)元素的存儲結

構，包含數(shù)據(jù)域（data）和指針域（next）兩部分。以線性表中第一個數(shù)據(jù)元素

的存a1a2a1

…

...

an^頭指針頭結點儲地址作為線性表的地址，稱作線性表的頭指針。有時為了操作方便，在第一個結點之前虛加一個“頭結點”，以指向頭結點的指針為鏈表的頭指針?？罩羔橆^線指性針表為空表時，頭結點的指針域為空ai-1aia2a1ai+1nan線性表的n個數(shù)據(jù)元素對應的n個結點通過鏈接方式鏈接成一個鏈表，每個結點只有一個指針域，所以稱為單鏈表?？梢詫⒕€性表（a1，a2，a3…….an-1，an）直觀地表示成用指針相鏈接的結點序列。head整個單鏈表可以由一個稱為頭結點的head來指出，標明單鏈表的首地址；當鏈表為空時，head

=NULL；單鏈表可以由頭結點指針唯一確定；鏈表中任意結點的存儲位置都可以從head開始，通過對鏈表進行遍歷得到；設p指向元素ai，則元素ai+1的地址q是：q=p->nextNULLhead表頭指針

表頭結點(不含數(shù)據(jù)結點的空鏈表)p表頭指針表頭結點帶表頭結點的單鏈表為了算法設計的方便，往往為每一個鏈表加上一個表頭結點。head數(shù)據(jù)結點name1NULL帶頭結點的單向鏈表ai-1aia2a1ai+1nanheadnhead空表怎樣判斷帶頭結點的單向鏈表是否為空表？如果：head->next==NULL成立，則為空表。等價：如果：head->next!=NULL成立，則不是空表。不帶頭結點的單向鏈表ai-1aia2a1ai+1nanheadNULLhead空表：head=NULL怎樣判斷不帶頭結點的單向鏈表是否為空表？如果：head==NULL成立，則為空表。等價：如果：head!=NULL成立，則不是空表。a3a4a2a5p->next

==結點之間的基本關系p

qrs則下列關系成立：qs

==q->

next->nextr->next

====p->

next->next->next通過當前結點p要訪問下一個結點，則指向下一個結點的指針為：p->next通過當前結點p要訪問下一個結點的下一個：p->next->nextint*anAge;

//定義整形指針anAge=new

int;//分配整形的內(nèi)存*anAge=71;//初始化int

*anAge=new

int

;int

*anAge=new

int

(71);用new分配內(nèi)存new的用法new

類型名T（初值列表）在內(nèi)存中用new分配一個整數(shù)new的返回值是內(nèi)存的地址，必須賦值給一個指針動態(tài)分配內(nèi)存delete的用法

delete

指針Pint

*anAge=new

int

(71);float

*

aSalary=new

float(5644.55);char

*

cityName=new

char[9];strcpy

(cityName,

“WestPort”);delete

anAge;delete

aSalary;delete

[

]cityName;釋放數(shù)組內(nèi)存必須使用方括號動態(tài)分配內(nèi)存用delete釋放內(nèi)存說明new和delete配對使用int

*pPoint;pPoint=new

int;*pPoint=72;delete

pPoint;pPoint=new

int;*pPoint=84;delete

pPoint;動態(tài)分配內(nèi)存注意對一個指針使用delete，它指向的內(nèi)存空間被釋放，而指針仍然存在。對一個指針使用delete，如果再次使用delete，將使程序崩潰。對指針賦為0（空指針），刪除空指針是安全的。Animal

*pDog=new

Animal;delete

pDog;pDog=0;delete

pDog;new

一個對象與對象相關的動態(tài)存儲new:調(diào)用構造函數(shù)delete:調(diào)用析構函數(shù)單鏈表類的定義單鏈表是簡單的鏈表，可以直接從抽象鏈表類派生出來，定義如下：class

List：public

ablist

<type>

{public：List（）

//構造函數(shù)，建立一個空鏈表{

head

=

new

ListNode

<type>；length

=

0；}//構造函數(shù)，用于通過一個現(xiàn)有鏈表建立新鏈表List（List

<type>

&

l）{

Copy（l）；}~List（）//析構函數(shù){MakeEmpty();delete

head;}

//將鏈表置空//將新元素插入在鏈表中第i個位置bool

Insert(type

value,

int

i);typeRemove(int

i);

//將鏈表中第i個結點刪去type

Remove1(type

value);//刪去表中值為value的結點//取得結點n的下一個結點位置

ListNode<type>

*GetNext(ListNode<type>

&n);List

<type>&

Copy(List

<type>

&

l);

//拷貝函數(shù)//重載賦值運算符,同類型鏈表賦值List

<type>&operator=(List

<type>&l);//重載輸出運算符friend

ostream

&

operator

<<(ostream

&,

List<type>&);};說明：（1）定義了兩個構造函數(shù),一個用來構造一個空鏈表，僅生成一個頭結點（頭結點數(shù)據(jù)域中可以為空，也可以來放一些和鏈表相關的數(shù)據(jù)），并將表頭head初始化為

NULL；另一個是利用一個現(xiàn)有鏈表建立新鏈表；析構函數(shù)用來回收元素結點所占的內(nèi)存；說明：對于在抽象鏈表中定義三個純虛函數(shù)：

Insert（type，int）、Remove（int）、Remove1（type）。在單鏈表中，應給出其具體實現(xiàn)，用來實現(xiàn)鏈表的插入、刪除操作；重載了二個運算符，賦值運算符用于同類型鏈表賦值，輸出運算符用于輸出一個鏈表；還有一個拷貝函數(shù)用于同類型單鏈表的拷貝。單鏈表常用成員函數(shù)實現(xiàn)在第i個位置插入一個新結點刪除鏈表指定位置i處的結點刪除數(shù)據(jù)元素為value的結點拷貝鏈表取得結點n的下一個位置重載賦值運算符*重載輸出運算符*在單鏈表第i個位置插入一個新結點基本原理:尋找插入點的前一個位置i-1;若為空表，應將表尾指針指向新結點;從內(nèi)存中申請一個新的空結點，將數(shù)據(jù)信息置于新結點的數(shù)據(jù)域內(nèi)。插入新結點步驟：定位——指針q指向第i-1個結點，指針p

指向需要插入的結點。鏈接后面指針——p->next=q->next;鏈接前面指針——q->next=p;D3D2D1D0^head

表頭結點

數(shù)據(jù)結點

數(shù)據(jù)結點

數(shù)據(jù)結點

數(shù)據(jù)結點pqxtemplate<classtype>bool List<type>::Insert(type

value，int

i){

ListNode<type>

*q=Find(i-1);

//定位插入點的前一位置if(q==NULL)return

false;

//i值不合理，返回false//創(chuàng)建新元素結點ListNode<type>

*p=

new

ListNode<type>

(value,p->next);assert(p);p->next=q->next;q->next=p;length++;return

true;

}刪除指定位置i處的結點利用Find(i-1)函數(shù)找到第i-1個元素結點；保留被刪結點的數(shù)據(jù)值，重新拉鏈(摘鏈)；若被刪結點為表尾結點時，修改表尾指針;最后應釋放被刪結點的內(nèi)存空間;將鏈表長度減1。D3D2D1D0^head

表頭結點數(shù)據(jù)結點數(shù)據(jù)結點數(shù)據(jù)結點數(shù)據(jù)結點pqx在鏈表中刪除第i個結點（基本原理）定位——指針p

指向第i-1

個結點，指針q指向被刪除的結點摘鏈——p->next=q->next;釋放

q節(jié)點——

delete q

;template<class

type>typeList<type>::Remove(int

i){

//p定位于第i-1個元素結點

ListNode<type>*p=Find(i-1),*q;assert(p

&&

p->next);

//p不為空且不為最后一個元素地址//q指向?qū)⒈粍h除的元素//重新鏈接（摘鏈）//保留被刪除結點的數(shù)據(jù)值//釋放被刪結點的空間q=p->next;p->next=q->next;typevalue=q->data;deleteq;length--;return

value;}刪除元素值為value的結點循鏈尋找數(shù)據(jù)值為value的前一結點；若已至表尾，且其值不為value，返回NULL；否則，重新拉鏈，將此結點斷開（摘鏈）；若被刪結點為表尾結點時，應修改表尾指針；回收被刪結點的內(nèi)存空間，將鏈表長度減1。template<class

type>type

List<type>::Remove1(type

value){

ListNode<type>*q，*p=head;//循鏈尋找數(shù)據(jù)值為value的前一結點while(p->next!=NULL

&&

p->next->data!=value)p=p->next;assert(p->next);q=p->next;//p不是表尾，繼續(xù)//q指向?qū)h除的元素p->next=q->next;

//重新接鏈，刪除此結點

delete

q;length--;return

value;

}拷貝鏈表：將鏈表l拷貝給當前鏈表對象算法：判斷鏈表l是否為空，若鏈表l為空，返回；若不空，為當前鏈表頭結點分配存儲空間；將鏈表l頭結點內(nèi)容復制給當前鏈表頭結點；循鏈進行結點間的賦值；賦值過程為：建立一個新結點、給結點賦值、將其鏈接到當前鏈表表尾，將當前鏈表指針p后移，再將鏈表l指針q后移。template<class

type>List<type>&

List<type>::Copy(List<type>

&l){ ListNode<type>

*p，*q，*r;length=l.length;

//復制鏈表長度

head=NULL;if(!l.head)

//若鏈表1為空，返回return

*this;//為當前鏈表頭結點分配存儲head=new

ListNode<type>;if(!head) return

*this;

//若分配失敗，返回

head->data=(l.head)->data;

//將鏈表1頭結點內(nèi)容復制給當前鏈表頭結點head->next=NULL;r=NULL;p=head;

//p指向當前鏈表頭//將q指向鏈表1的第二個結點

q=l.head->next;while(q)

//從第二個結點至鏈尾進行結點間的賦值//建立一個新結點//失敗，返回//給結點賦值{

r=new

ListNode<type>;if(!r) return

*this;r->data=q->data;r->next=NULL;p->next=r;

//將新結點鏈接到當前鏈表頭結點后面

p=p->next;

//當前鏈表指針后移，p指向第一個結點q=q->next;//鏈表1指針后移}return

*this;

}關于this指針this指針是一個隱含于每一個成員函數(shù)中的特殊指針。它指向正在被該成員函數(shù)操作的對象,也就是要操作該成員函數(shù)的對象。當對一個對象調(diào)用成員函數(shù)時，編譯程序先將對象的地址賦給this指針，然后調(diào)用成員函數(shù)，每次成員函數(shù)存取數(shù)據(jù)成員時，隱含使用this指針。通常不去顯式地使用

this指針來引用數(shù)據(jù)成員。同樣也可以使用*this來標識調(diào)用該成員函數(shù)的對象。關于this指針例：#include

<iostream.h>class

A{

public:A()

{

x=y=0;

}A(int

a,

int

b)

{

x=a;

y=b;

}void

copy(A

&aa); //對象引用作函數(shù)參數(shù)

void

print()

{cout<<x<<","<<y<<endl;}private:int

x,

y;};關于this指針void

A::copy(A

&aa){if

(this==&aa)return; //這個this是操作該成員函數(shù)的對象的地址，在這里是對象a2的地址*this=aa; //*this是操作該成員函數(shù)的對象，在這里是對象a2。//此語句是對象aa賦給a1，也就是aa具有的數(shù)據(jù)成員的值賦