計(jì)算機(jī)資料補(bǔ)充

管態(tài)和目態(tài)

管態(tài)是指操作系統(tǒng)在運(yùn)行系統(tǒng)的管理程序時(shí)所處的狀態(tài)。此狀態(tài)下可以執(zhí)行任何指令，

包括特權(quán)指令。CPU的狀態(tài)屬于程序狀態(tài)字PSW的一位，管態(tài)又稱特權(quán)狀態(tài)、系統(tǒng)態(tài)或核

心態(tài)。通常，操作系統(tǒng)在管態(tài)下運(yùn)行，CPU在管態(tài)下可以執(zhí)行指令系統(tǒng)的全集。

目態(tài)是指操作系統(tǒng)在運(yùn)行系統(tǒng)的應(yīng)用程序所處的狀態(tài)。只允許應(yīng)用程序訪問(wèn)自己的內(nèi)存空

間。這樣能夠保證應(yīng)用程序運(yùn)行時(shí)系統(tǒng)的安全。目態(tài)又稱常態(tài)或用戶態(tài)，機(jī)器處于目態(tài)時(shí)，

程序只能執(zhí)行非特權(quán)指令。用戶程序只能在目態(tài)下運(yùn)行。

當(dāng)一個(gè)任務(wù)（進(jìn)程）執(zhí)行系統(tǒng)調(diào)用而陷入內(nèi)核代碼中執(zhí)行時(shí)，我們就稱進(jìn)程處于內(nèi)核運(yùn)

行態(tài)（或簡(jiǎn)稱為內(nèi)核態(tài)）。此時(shí)處理器處于特權(quán)級(jí)最高的（0級(jí)）內(nèi)核代碼中執(zhí)行。當(dāng)進(jìn)程

處于內(nèi)核態(tài)時(shí)，執(zhí)行的內(nèi)核代碼會(huì)使用當(dāng)前進(jìn)程的內(nèi)核棧。每個(gè)進(jìn)程都有自己的內(nèi)核棧。當(dāng)

進(jìn)程在執(zhí)行用戶自己的代碼時(shí)，則稱其處于用戶運(yùn)行態(tài)（用戶態(tài)）。即此時(shí)處理器在特權(quán)級(jí)

最低的（3級(jí)）用戶代碼中運(yùn)行。當(dāng)正在執(zhí)行用戶程序而突然被中斷程序中斷時(shí)，此時(shí)用戶

程序也可以象征性地稱為處于進(jìn)程的內(nèi)核態(tài)。因?yàn)橹袛嗵幚沓绦驅(qū)⑹褂卯?dāng)前進(jìn)程的內(nèi)核棧。

這與處于內(nèi)核態(tài)的進(jìn)程的狀態(tài)有些類似。

1、用系統(tǒng)調(diào)用時(shí)進(jìn)入核心態(tài)。Linux對(duì)硬件的操作只能在核心態(tài)，這可以通過(guò)寫驅(qū)動(dòng)

程序來(lái)控制。在用戶態(tài)操作硬件會(huì)造成coredump.

2、要注意區(qū)分系統(tǒng)調(diào)用和一般的函數(shù)。系統(tǒng)調(diào)用由內(nèi)核提供，如read。、write。、

open。等。而一般的函數(shù)山軟件包中的函數(shù)庫(kù)提供，如sin（）、cos（）等。在語(yǔ)法上兩者沒

有區(qū)別。

3、一般情況：系統(tǒng)調(diào)用運(yùn)行在核心態(tài)，函數(shù)運(yùn)行在用戶態(tài)。但也有一些函數(shù)在內(nèi)部使

用了系統(tǒng)調(diào)用（如fopen）,這樣的函數(shù)在調(diào)用系統(tǒng)調(diào)用是進(jìn)入核心態(tài)，其他時(shí)候運(yùn)行在用

戶態(tài)。

大概是當(dāng)用戶程序調(diào)用系統(tǒng)的API時(shí)，就產(chǎn)生中斷，進(jìn)入內(nèi)核態(tài)的API,處理完成后，

用中斷再退出，返回用戶態(tài)的調(diào)用函數(shù)。

userapi—>interrupt->kernelapi->interrupt

簡(jiǎn)單來(lái)講一個(gè)進(jìn)程由于執(zhí)行系統(tǒng)調(diào)用而開始執(zhí)行內(nèi)核代碼，我們稱該進(jìn)程處于內(nèi)核態(tài)中.

一個(gè)進(jìn)程執(zhí)行應(yīng)用程序自身代碼則稱該進(jìn)程處于用戶態(tài)。intelx86架構(gòu)的CPU分為好幾

個(gè)運(yùn)行級(jí)別，從0-3,0為最高級(jí)別,3為最低級(jí)別。

針對(duì)不同的級(jí)別，有很多的限制，比如說(shuō)傳統(tǒng)的in,oul指令，就是端口的輸入輸出指

令，在0級(jí)下是可以用的，但在3級(jí)下就不能用，你用就產(chǎn)生陷阱，告訴你出錯(cuò)了，當(dāng)然限制還

有很多了，不只是這一點(diǎn)。

操作系統(tǒng)下是利用這個(gè)特點(diǎn)，當(dāng)操作系統(tǒng)自己的代碼運(yùn)行時(shí)，CPU就切成0級(jí)，當(dāng)用戶的

程序運(yùn)行是就只讓它在3級(jí)運(yùn)行，這樣如果用戶的程序想做什么破壞系統(tǒng)的事情的話，也沒

辦法做到。

當(dāng)然，低級(jí)別的程序是沒法把自己升到高級(jí)別的,也就是說(shuō)用戶程序運(yùn)行在3級(jí),他想把

自己變成0級(jí)自己是做不到的，除非是操作系統(tǒng)幫忙，利用這個(gè)特性,操作系統(tǒng)就可以控制

所有的程序的運(yùn)行,確保系統(tǒng)的安全了.平時(shí)把操作系統(tǒng)運(yùn)行時(shí)的級(jí)別就叫內(nèi)核態(tài)（因?yàn)槭?/p>

操作系統(tǒng)內(nèi)核運(yùn)行時(shí)的狀態(tài)），而且普通用戶程序運(yùn)行時(shí)的那個(gè)級(jí)別叫用戶態(tài)...

當(dāng)操作系統(tǒng)剛引導(dǎo)時(shí)，CPU處于實(shí)模式,這時(shí)就相當(dāng)于是0級(jí)，于是操作系統(tǒng)就自動(dòng)得到

最高權(quán)限,然后切到保護(hù)模式時(shí)就是0級(jí),這時(shí)操作系統(tǒng)就占了先機(jī),成為了最高級(jí)別的運(yùn)行

1

者?，由于你的程序都是由操作系統(tǒng)來(lái)加載的,所以當(dāng)它把你加載上來(lái)后,就把你的運(yùn)行狀態(tài)設(shè)

為3級(jí)，即最低級(jí)，然后才讓你運(yùn)行，所以沒辦法，你只能在最低級(jí)運(yùn)行了，因?yàn)闆]辦法把自

己從低級(jí)上升到高級(jí)，這就是操作系統(tǒng)在內(nèi)核態(tài)可以管理用戶程序，殺死用戶程序的原

因.

特權(quán)指令

所謂特權(quán)指令是指具有特殊權(quán)限的指令，由于這類指令的權(quán)限最大，所以如果使用不當(dāng)，

就會(huì)破壞系統(tǒng)或其它用戶信.息.因此為了安全起見，這類指令只能用于操作系統(tǒng)或其它系統(tǒng)

軟件，而一般不直接提供給用戶使用。

這得從CPU指令系統(tǒng)（用于控制CPU完成各種功能的命令）的特權(quán)級(jí)別說(shuō)起。在CPU的所

有指令中，有一些指令是非常危險(xiǎn)的，如果錯(cuò)用，將導(dǎo)致整個(gè)系統(tǒng)崩潰。比如：清內(nèi)存、設(shè)

置時(shí)鐘等。如果所有的程序都能使用這些指令，那么你的系統(tǒng)一天死機(jī)n回就不足為奇了。

所以，CPU將指令分為特權(quán)指令和非特權(quán)指令，對(duì)于那些危險(xiǎn)的指令，只允許操作系統(tǒng)及其

相關(guān)模塊使用，普通的應(yīng)用程序只能使用那些不會(huì)造成災(zāi)難的指令。形象地說(shuō)，特權(quán)指令就

是那些兒童不宜的東東，而非特權(quán)指令則是老少皆宜。

特權(quán)指令如果錯(cuò)用，將導(dǎo)致整個(gè)系統(tǒng)崩潰。比如：清內(nèi)存、設(shè)置時(shí)鐘等。如果所有的程

序都能使用這些指令，那么你的系統(tǒng)-天死機(jī)n回就不足為奇了。

一般說(shuō)來(lái)，在單用戶，單任務(wù)的計(jì)算機(jī)中不具有也不需要特權(quán)指令，而在多用戶，多任

務(wù)的計(jì)算機(jī)系統(tǒng)中，特權(quán)指令卻是不可缺少的。它主要用于系統(tǒng)資源的分配和管理，包括改

變系統(tǒng)的工作方式，檢測(cè)用戶的訪問(wèn)權(quán)限，修改虛擬存儲(chǔ)器管理的段表，頁(yè)表和完成任務(wù)的

創(chuàng)建和切換等。

系統(tǒng)調(diào)用命令

系統(tǒng)調(diào)用是用戶程序請(qǐng)求操作系統(tǒng)為其服務(wù)的惟一形式，在UNIX中把系統(tǒng)調(diào)用稱為程

序員接口。UNIX規(guī)定用戶程序用捕俘（trap）指令請(qǐng)求系統(tǒng)服務(wù)，UNIX核心中的中斷捕俘程

序根據(jù)trap的類型轉(zhuǎn)向相應(yīng)的處理程序

訪管指令

訪管指令是一條可以在目態(tài)下執(zhí)行的指令，用戶程序中凡是要調(diào)用操作系統(tǒng)功能時(shí)就安

排一條訪管指令。當(dāng)處理器執(zhí)行到訪管指令時(shí)就產(chǎn)生一個(gè)中斷事件（自愿中斷），暫停用戶

程序的執(zhí)行，而讓操作系統(tǒng)來(lái)為用戶服務(wù)

廣義指令

廣義指令是指VC或者其他一些編程環(huán)境提供的庫(kù)函數(shù)，這些庫(kù)函數(shù)集成了操作系統(tǒng)提

供的系統(tǒng)調(diào)用，比如API

2

雙向鏈表

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直

接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開始，都可以很方便地訪問(wèn)它的前

驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。一般我們都構(gòu)造雙向循環(huán)鏈表。

鏈表的操作

線性表的雙向鏈表存儲(chǔ)結(jié)構(gòu)

typedefstructDuLNode

(

ElemTypedata;

structDuLNode*prior,*next;

}DuLNode,*DuLinkList;

帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表的基本操作

voidInitList(DuLinkList*L)

{/*產(chǎn)生空的雙向循環(huán)鏈表L*/

*L=(DuLinkList)maHoc(sizeof(DuLNode));

if(*L)

(*L)->next=(*L)->prior=*L;

else

exit(OVERFLOW);

)

銷毀雙向循環(huán)鏈表L

voidDestroyList(DuLinkList*L)

(

DuLinkListq,p=(*L)->next;/*p指向第一個(gè)結(jié)點(diǎn)*/

while(p!=*L)/*p沒到表頭*/

(

q=p->next;

free(p);

P=q；

)

3

free(*L);

*L=NULL;

)

重置鏈表為空表

voidClearList(DuLinkListL)/*不改變L*/

{DuLinkListq,p=L->next;/*p指向第一個(gè)結(jié)點(diǎn)*/

while(p!=L)/*p沒到表頭*/

(

q=p->next;

free(p);

P二q;

)

L->next=L->prior=L;/*頭結(jié)點(diǎn)的兩個(gè)指針域均指向自身*/

)

驗(yàn)證是否為空表

StatusListEmpty(DuLinkListL)

{/*初始條件：線性表L已存在

if(L->next==L&&L->prior==L)

returnTRUE;

else

returnFALSE;

)

元素的操作

計(jì)算表內(nèi)元素個(gè)數(shù)

intListLength(DuLinkListL)

{/*初始條件：L已存在。操作結(jié)果：*/

inti=0;

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

while(p!=L)/*p沒到表頭*/

4

i++；

p=p->next;

)

returni;

)

賦值

StatusGetElem(DuLinkListL,inti,ElemType*e)

{/*當(dāng)?shù)趇個(gè)元素存在時(shí)，其值賦給e并返回OK,否則返回ERROR*/

intj=l;/*j為計(jì)數(shù)器*/

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

while(p!=L&,&j<i)

(

p=p->next;

j++；

)

if(p==L||j>i)/*第i個(gè)元素不存在*/

returnERROR;

*e=p->data;/*取第i個(gè)元素*/

returnOK;

)

查找元素

intLocateElem(DuLinkListL,ElemTypee,Status(*compare)(ElemType,ElemType))

{/*初始條件：L已存在，compare。是數(shù)據(jù)元素判定函數(shù)*/

/*操作結(jié)果：返回L中第1個(gè)與e滿足關(guān)系compare。的數(shù)據(jù)元素的位序。*/

/*若這樣的數(shù)據(jù)元素不存在，則返回值為0*/

inti=0;

DuLinkListp=L->next;/*p指向第1個(gè)元素*/

while(p!=L)

5

i++；

if(compare(p->data,e))/*找到這樣的數(shù)據(jù)元素*/

returni;

p=p->next;

)

return0;

)

查找元素前驅(qū)

StatusPriorElem(DuLinkListL,ElemTypecure,ElemType*pree)

{/*操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是第一個(gè)，則用pre_e返回它

的前驅(qū)*/

/*否則操作失敗，pre_e無(wú)定義*/

DuLinkListp=L->next->next;/*p指向第2個(gè)元素*/

while(p!=L)/*p沒到表頭*/

(

if(p->data==cur_e)

(

*pree=p->prior->data;

returnTRUE;

)

p=p->next;

)

returnFALSE;

)

查找元素后繼

StatusNextElem(DuLinkListL,ElemTypecur_e,ElemType*next_e)

{/*操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回

它的后繼，*/

/*否則操作失敗，next_e無(wú)定義*/

6

DuLinkListp=L->next->next;/*p指向第2個(gè)元素*/

while(p!=L)/*p沒到表頭*/

{

if(p->prior->data-cur_e)

(

*next_e=p->data;

returnTRUE;

)

p=p->next;

)

returnFALSE;

)

查找元素地址

DuLinkListGetElemP(DuLinkListL,inti)/*另加*/

{/*在雙向鏈表L中返回第i個(gè)元素的地址。i為0,返回頭結(jié)點(diǎn)的地址。若第

i個(gè)元素不存在，*/

/*返回NULL*/

intj;

DuLinkListp=L;/*p指向頭結(jié)點(diǎn)*/

if(i<0||i>ListLength(D)/*i值不合法*/

returnNULL;

for(j=l;j<=i;j++)

p=p->next;

returnp;

)

元素的插入

StatusListinsert(DuLinkListL,inti,ElemTypee)

{/*在帶頭結(jié)點(diǎn)的雙鏈循環(huán)線性表L中第i個(gè)位置之前插入元素e,i的合法值

為IWiW表長(zhǎng)+1*/

/*改進(jìn)算法2.18,否則無(wú)法在第表長(zhǎng)+1個(gè)結(jié)點(diǎn)之前插入元素*/

7

DuLinkListp,s;

if(i<l||i>ListLength(L)+l)/*i值不合法*/

returnERROR;

p=GetElemP(L,i-1);/*在L中確定第i個(gè)元素前驅(qū)的位置指針p*/

if(!p)/*p-NULL,即第i個(gè)元素的前驅(qū)不存在(設(shè)頭結(jié)點(diǎn)為第1個(gè)元素的前驅(qū))*/

returnERROR;

s=(DuLinkList)malloc(sizeof(DuLNode));

if(!s)

returnOVERFLOW;

s->data=e;

s->prior=p;/*在第iT個(gè)元素之后插入*/

s->next=p->next;

p->next->prior=s;

p->next=s;

returnOK;

)

元素的刪除

StatusListDelete(DuLinkListL,inti,ElemType*e)

{/*刪除帶頭結(jié)點(diǎn)的雙鏈循環(huán)線性表L的第i個(gè)元素，i的合法值為IWiW表

長(zhǎng)*/

DuLinkListp;

if(i<l)/*i值不合法*/

returnERROR;

p=GetElemP(L,i);/*在L中確定第i個(gè)元素的位置指針p*/

if(!p)/*p=NULL,即第i個(gè)元素不存在*/

returnERROR;

*e=p->data;

p->prior->next=p->next;

p->next->prior=p->prior;

8

free(p);

returnOK;

)

正序查找

voidListTraverse(DuLinkListL,void(*visit)(ElemType))

{/*由雙鏈循環(huán)線性表L的頭結(jié)點(diǎn)出發(fā)，正序?qū)γ總€(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit。

*/

DuLinkListp=L->next;/*p指向頭結(jié)點(diǎn)*/

while(p!=L)

(

visit(p->data);

p=p->next;

)

printf(*\n*);

)

voidListTraverseBack(DuLinkListL,void(*visit)(ElemType))

逆序查找

{/*由雙鏈循環(huán)線性表L的頭結(jié)點(diǎn)出發(fā)，逆序?qū)γ總€(gè)數(shù)據(jù)元素調(diào)用函數(shù)visitOo

另加*/

DuLinkListp=L->prior;/*p指向尾結(jié)點(diǎn)*/

while(p!=L)

(

visit(p->data);

p=p->prior;

)

printf("\n");

)

雙向鏈表模板

/*文件名：LinkedList.h

*功能：實(shí)現(xiàn)雙向鏈表的基本功能

9

*注意：為了使最終程序執(zhí)行得更快，僅在Debug模式下檢測(cè)操作合法性。

*另外不對(duì)內(nèi)存分配失敗作處理，因一般情況下應(yīng)用程序有近2GB真正可用的空間*/

^pragmaonce

iiinclude<assert.h>

template<classT>

classLinkedList

(

private:

classNode

(

public:

Tdata;〃數(shù)據(jù)域，不要求泛型T的實(shí)例類有無(wú)參構(gòu)造函數(shù)

Node*prior;//指向前一個(gè)結(jié)點(diǎn)

Node*next;//指向下一個(gè)結(jié)點(diǎn)

Node(constT&element,Node*&pri,Node*&nt):data(element),next(nt),

prior(pri){}

Node0:data(data){}〃泛型T的實(shí)例類的復(fù)制構(gòu)造函數(shù)將被調(diào)用.在Vc2010測(cè)

試可行

)；

Node*head;〃指向第一個(gè)結(jié)點(diǎn)

public:

〃初始化：構(gòu)造一個(gè)空結(jié)點(diǎn)，搭建空鏈

LinkedList():head(newNode()){head->prior=head->next=head;}

〃獲取元素總數(shù)

intelementToatal()const;

〃判斷是否為空鏈

boolisEmpty()const{returnhead==head->next?true:false;}

〃將元素添加至最后，注意node的指針設(shè)置

voidaddToLast(constT&element){

Node*ne=newNode(element,head->prior,head);

10

head->prior=head->prior->next=ne;}

〃獲取最后一個(gè)元素

TgetLastElement()const{assert(!isEmpty());returnhead->prior->data;}

〃刪除最后一個(gè)元素，注意node的指針設(shè)置

voiddelLastElement(){

assert(!isEmpty());

Node*p=head->prior->prior;

deletehead->prior;head->prior二p;p->next=head;

)

〃修改最后一個(gè)元素

voidalterLastEmlent(constT&newElement){

assert(!isEmpty());

head->prior->data=newElement;

)

〃插入元素

voidinsertElement(constT&element,intposition);

〃獲取元素

TgetElement(intindex)const;

〃刪除元素

TdelElement(intindex);

〃修改元素

voidalterElement(constT&Newelement,intindex);

〃查找元素

intfindElement(constT&element)const;

〃正序遍歷

voidTraverse(void(*visit)(T&element));

〃逆序遍歷

voidTraverseBack(void(*visit)(T&element));

〃重載□函數(shù)

11

T&operator[](intindex);

〃清空鏈表

voidclearAHElement();

〃銷毀鏈表

^LinkedList();

)；

/*返回元素總數(shù)*/

template<classT>

intLinkedList<T>::elementToatal()const

(

intTotal=0;

for(Node*p=head->next;p!=head;p=p->next)++Total;

returnTotal;

)

/*在position指定的位置插入元素。原來(lái)position及后面的元素后移*/

template<classT>

voidLinkedList<T>::insertElement(constT&element,intposition)

(

assert(position>0&,&position<=elementToatal()+1);

Node*p=head;

while(position)

(

p=p->next;

position一-；

)

//此時(shí)p指向要插入的結(jié)點(diǎn)

Node*pNew=newNode(element,p->prior,p);

p->priorz:p->prior->next=pNew;

)

12

/*返回找到的元素的副本*/

template<classT>

TLinkedList<T>::getElement(intindex)const

(

assert(index>0&&index<=elementToatal()&&!isEmpty());〃位置索引是否

合法，鏈表是否空

Node*p=head->next;

whi1e(--index)p=p->next;

returnp->data;

)

/*刪除指定元素，并返回它*/

template<classT>

TLinkedList<T>::delElement(intindex)

(

assert(index>0&&index<=elementToatal()&&!isEmpty());//位置索引是否

合法，鏈表是否空

Node*del=head->next;

whi1e(―index)del=del->next;

〃此時(shí)p指向要?jiǎng)h除元素

del->prior->next=del->next;

del->next->prior=del->prior;

TdelData=del->data;

deletedel;

returndelData;

)

/*用Newelement代替索引為index的元素*/

template<classT>

voidLinkedList<T>::alterElement(constT&Newelement,intindex)

(

assert(index>0&&index<=elementToatal()&&!isEmpty());〃位置索引是否

13

合法，鏈表是否空

Node*p=head->next;

whi1e(--index)p=p->next;

p->data=Newelement;

)

/*找到返回元素的索引，否則返回o*/

template<classT>

intLinkedList<T>::findElement(constT&element)const

(

Node*p=head->next;

inti=0;

while(p!=head)

(

i++；

if(p->data==element)returni;

p=p->next;

)

return0;

)

/*正向遍歷，以鏈表中每個(gè)元素作為參數(shù)調(diào)用visit函數(shù)*/

template<classT>

voidLinkedList<T>::Traverse(void(*visit)(T&element))

(

Node*p=head-〉next;

while(p!=head)

(

visit(p->data);〃注意此時(shí)外部visit函數(shù)有權(quán)限修改LinkedList〈T》的私有

數(shù)據(jù)

p=p->next;

14

}}

/*反向遍歷，以鏈表中每個(gè)元素作為參數(shù)調(diào)用Visit函數(shù)*/

template<classT>

voidLinkedList<T>::TraverseBack(void(*visit)(T&element))

(

Node*p=head->prior;

while(p!=head)

(

visit(p->data);〃注意此時(shí)外部visit函數(shù)有權(quán)限修改LinkedList<T>的私有

數(shù)據(jù)

p=p->prior;

}}

/*返回鏈表的元素引用，并可讀寫.實(shí)際上鏈表沒有口意義上的所有功能。因此口

函數(shù)是有限制的.重載它是為了客戶端代碼簡(jiǎn)潔，因?yàn)閺逆湵碜x寫數(shù)據(jù)是最常用的*/

template<classT>

T&LinkedList<T>::operator[](intindex)

(

assert(index>0&&index<=elementToatal()&&!isEmpty());〃□函數(shù)使用前

提條件

Node*p=head->next;

whi1e(--index)p=p->next;

returnp->data;

)

/*清空鏈表*/

template<classT>

voidLinkedList<T>::clearAllElement()

{

Node*p=head->next,*pTemp=0;

while(p!=head)

15

pTemp=p->next;

deletep;

p=pTemp;

)

head->priorz:head->next=head;〃收尾工作

)

/*析構(gòu)函數(shù)，若內(nèi)存足夠沒必要調(diào)用該函數(shù)*/

template<classT>

LinkedList<T>::^LinkedList()

(

if(head)〃防止用戶顯式析構(gòu)后，對(duì)象又剛好超出作用域再調(diào)用該函數(shù)

(

clearAllElement();

deletehead;

head=O;

})

循環(huán)鏈表

循環(huán)鏈表是另?種形式的鏈?zhǔn)酱尜A結(jié)構(gòu)。它的特點(diǎn)是表中最后個(gè)結(jié)點(diǎn)的指針域指向頭

結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。

分類：

(1)單循環(huán)鏈表一一在單鏈表中，將終端結(jié)點(diǎn)的指針域NULL改為指向表頭結(jié)點(diǎn)

或開始結(jié)點(diǎn)即可。

(2)多重鏈的循環(huán)鏈表一一將表中結(jié)點(diǎn)鏈在多個(gè)環(huán)上。

帶頭結(jié)點(diǎn)的單循環(huán)鏈表：判斷空鏈表的條件是head-head->next;

僅設(shè)尾指針的單循環(huán)鏈表：用尾指針rear表示的單循環(huán)鏈表對(duì)開始結(jié)點(diǎn)al和終端結(jié)

點(diǎn)an查找時(shí)間都是0(1)。而表的操作常常是在表的首尾位置上進(jìn)行，因此，實(shí)用中

多采用尾指針表示單循環(huán)鏈表。帶尾指針的單循環(huán)鏈表可見下圖。

注意：判斷空鏈表的條件為rear==rear->next;

循環(huán)鏈表的特點(diǎn)：循環(huán)鏈表的特點(diǎn)是無(wú)須增加存儲(chǔ)量，僅對(duì)表的鏈接方式稍作改變，

即可使得表處理更加方便靈活。

【例】在鏈表上實(shí)現(xiàn)將兩個(gè)線性表(al,a2,…，an)和(bl,b2,…，bm)連

16

接成一個(gè)線性表（al,…，an,bl,?-?bm）的運(yùn)算。

分析：若在單鏈表或頭指針表示的單循環(huán)表上做這種鏈接操作，都需要遍歷第一

個(gè)鏈表，找到結(jié)點(diǎn)an,然后將結(jié)點(diǎn)bl鏈到an的后面，其執(zhí)行時(shí)間是0（n）。若在尾

指針表示的單循環(huán)鏈表上實(shí)現(xiàn)，則只需修改指針，無(wú)須遍歷，其執(zhí)行時(shí)間是0（1）。

相應(yīng)的算法如下：

LinkListConnect（LinkListA,LinkListB）

{〃假設(shè)A,B為非空循環(huán)鏈表的尾指針

LinkListp=A->next;//①保存A表的頭結(jié)點(diǎn)位置

A->next=B->next->next;〃②B表的開始結(jié)點(diǎn)鏈接到A表尾

free（B->next）;〃③釋放B表的頭結(jié)點(diǎn)

B->next=p;//@

returnB;〃返回新循環(huán)鏈表的尾指針

）

注意：

①循環(huán)鏈表中沒有NULL指針。涉及遍歷操作時(shí)，其終止條件就不再是像非循環(huán)

鏈表那樣判別P或p->next是否為空，而是判別它們是否等于某一指定指針，如頭

指針或尾指針等。

②在單鏈表中，從一已知結(jié)點(diǎn)出發(fā)，只能訪問(wèn)到該結(jié)點(diǎn)及其后續(xù)結(jié)點(diǎn)，無(wú)法找到

該結(jié)點(diǎn)之前的其它結(jié)點(diǎn)。而在單循環(huán)鏈表中，從任一結(jié)點(diǎn)出發(fā)都可訪問(wèn)到表中所有結(jié)

點(diǎn)，這一優(yōu)點(diǎn)使某些運(yùn)算在單循環(huán)鏈表上易于實(shí)現(xiàn)。

單鏈表

單鏈表簡(jiǎn)介：用組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。

以元素（數(shù)據(jù)元素的映象）+指針（指示后繼元素存儲(chǔ)位置）=結(jié)點(diǎn)（表示數(shù)據(jù)元

素或數(shù)據(jù)元素的映象）

以“結(jié)點(diǎn)的序列”表示線性表??稱作線性鏈表（單鏈表）

循環(huán)單鏈表是單鏈表的另一種形式，其結(jié)構(gòu)特點(diǎn)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不

再是結(jié)束標(biāo)記，而是指向整個(gè)鏈表的第一個(gè)結(jié)點(diǎn)，從而使鏈表形成一個(gè)環(huán)。和單鏈表

相同，循環(huán)鏈表也有帶頭結(jié)點(diǎn)結(jié)構(gòu)和不帶頭結(jié)點(diǎn)結(jié)構(gòu)兩種，帶頭結(jié)點(diǎn)的循環(huán)單鏈表實(shí)

現(xiàn)插入和刪除操作較為方便。

單鏈表是一種順序存取的結(jié)構(gòu)，為找第i個(gè)數(shù)據(jù)元素，必須先找到第iT個(gè)數(shù)據(jù)

元素。

因此，查找第i個(gè)數(shù)據(jù)元素的基本操作為：移動(dòng)指針，比較j和i

單鏈表

17

1、鏈接存儲(chǔ)方法

鏈接方式存儲(chǔ)的線性表簡(jiǎn)稱為鏈表（LinkedList）?

鏈表的具體存儲(chǔ)表示為：

①用一組任意的存儲(chǔ)單元來(lái)存放線性表的結(jié)點(diǎn)（這組存儲(chǔ)單元既可以是連續(xù)的，

也可以是不連續(xù)的）

②鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點(diǎn)間的邏

輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲(chǔ)指示其后繼結(jié)點(diǎn)的地址（或位置）信

息（稱為指針（pointer）或鏈（link））

注意：

鏈?zhǔn)酱鎯?chǔ)是最常用的存儲(chǔ)方式之一，它不僅可用來(lái)表示線性表，而且可用來(lái)表示

各種非線性的數(shù)據(jù)結(jié)構(gòu)。

2、鏈表的結(jié)點(diǎn)結(jié)構(gòu)

I------1-------1

|data|next!

I______I_______l

data域一存放結(jié)點(diǎn)值的數(shù)據(jù)域

next域一存放結(jié)點(diǎn)的直接后繼的地址（位置）的指針域（鏈域）

注意：

①鏈表通過(guò)每個(gè)結(jié)點(diǎn)的鏈域?qū)⒕€性表的n個(gè)結(jié)點(diǎn)按其邏輯順序鏈接在一起的。

②每個(gè)結(jié)點(diǎn)只有一個(gè)鏈域的鏈表稱為單鏈表（SingleLinkedList）。

【例】線性表（bat,cat,eat,fat,hat,jat,lat,mat）的單鏈表示如示意

圖

3、頭指針head和終端結(jié)點(diǎn)指針域的表示

單鏈表中每個(gè)結(jié)點(diǎn)的存儲(chǔ)地址是存放在其前趨結(jié)點(diǎn)next域中，而開始結(jié)點(diǎn)無(wú)前

趨，故應(yīng)設(shè)頭指針head指向開始結(jié)點(diǎn)。

注意：

鏈表由頭指針唯一確定，單鏈表可以用頭指針的名字來(lái)命名。

【例】頭指針名是head的鏈表可稱為表heado

終端結(jié)點(diǎn)無(wú)后繼，故終端結(jié)點(diǎn)的指針域?yàn)榭眨碞ULL。

4、單鏈表的一般圖示法

由于我們常常只注重結(jié)點(diǎn)間的邏輯順序，不關(guān)心每個(gè)結(jié)點(diǎn)的實(shí)際位置，可以用箭

18

頭來(lái)表示鏈域中的指針，線性表(bat,cat,fat,hat,jat,lat,mat)的單鏈表

就可以表示為下圖形式。

5、單鏈表類型描述

typedefcharDataType;//假設(shè)結(jié)點(diǎn)的數(shù)據(jù)域類型為字符

typedefstructnode{〃結(jié)點(diǎn)類型定義

DataTypedata;〃結(jié)點(diǎn)的數(shù)據(jù)域

structnode*next;〃結(jié)點(diǎn)的指針域

}ListNode;

typedefListNode*LinkList;

ListNode*p;

LinkListhead;

注意：

①*LinkList和ListNode是不同名字的同一個(gè)指針類型(命名的不同是為了概念

匕更明確)

②*LinkList類型的指針變量head表示它是單鏈表的頭指針

③ListNode類型的指針變量p表示它是指向某一結(jié)點(diǎn)的指針

6、指針變量和結(jié)點(diǎn)變量

指針變量結(jié)點(diǎn)變量

定義在變量說(shuō)明部分顯式定義在程序執(zhí)行時(shí)，通過(guò)標(biāo)準(zhǔn)函數(shù)malloc生成

取值非空時(shí)，存放某類型結(jié)點(diǎn)實(shí)際存放結(jié)點(diǎn)各域內(nèi)容的地址

操作方式通過(guò)指針變量名訪問(wèn)通過(guò)指針生成、訪問(wèn)和釋放

①生成結(jié)點(diǎn)變量的標(biāo)準(zhǔn)函數(shù)

p=(ListNode*)malloc(sizeof(ListNode))；

〃函數(shù)malloc分配一個(gè)類型為L(zhǎng)istNode的結(jié)點(diǎn)變量的空間，并將其首地址放入

指針變量P中

②釋放結(jié)點(diǎn)變量空間的標(biāo)準(zhǔn)函數(shù)

free(p)；〃釋放p所指的結(jié)點(diǎn)變量空間

③結(jié)點(diǎn)分量的訪問(wèn)

利用結(jié)點(diǎn)變量的名字*P訪問(wèn)結(jié)點(diǎn)分量

方法一：(*p).data和(*p).next

19

方法二：p->data和p->next

④指針變量P和結(jié)點(diǎn)變量*P的關(guān)系

指針變量P的值一一結(jié)點(diǎn)地址

結(jié)點(diǎn)變量*P的值一一結(jié)點(diǎn)內(nèi)容

(*p).data的值一一p指針?biāo)附Y(jié)點(diǎn)的data域的值

(*p).next的值----*p后繼結(jié)點(diǎn)的地址

*((*p).next)------*p后繼結(jié)點(diǎn)

注意：

①若指針變量P的值為空(NULL),則它不指向任何結(jié)點(diǎn)。此時(shí)，若通過(guò)*p來(lái)

訪問(wèn)結(jié)點(diǎn)就意味著訪問(wèn)?個(gè)不存在的變量，從而引起程序的錯(cuò)誤。

②有關(guān)指針類型的意義和說(shuō)明方式的詳細(xì)解釋

可見，在鏈表中插入結(jié)點(diǎn)只需要修改指針。但同時(shí)，若要在第i個(gè)結(jié)點(diǎn)之前插

入元素，修改的是第『1個(gè)結(jié)點(diǎn)的指針。

因此，在單鏈表中第i個(gè)結(jié)點(diǎn)之前進(jìn)行插入的基本操作為：

找到線性表中第i-1個(gè)結(jié)點(diǎn)，然后修改其指向后繼的指針。

單鏈表的建立

鏈表操作中動(dòng)態(tài)存儲(chǔ)分配要使用標(biāo)準(zhǔn)函數(shù)，先介紹一下這些函數(shù)。

(l)malloc(size)

在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)申請(qǐng)一個(gè)長(zhǎng)度為size字節(jié)的連續(xù)空間。

(2)calloc(n,size)

在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)申請(qǐng)n個(gè)長(zhǎng)度為size字節(jié)的連續(xù)空間，函數(shù)返回值為分配

空間的首地址。若此函數(shù)未被成功執(zhí)行，函數(shù)返回值為。。

(3)free(p)

釋放由指針P所指向的存儲(chǔ)單元，而存儲(chǔ)單元的大小是最近一次調(diào)用mallocO

或calloc()函數(shù)時(shí)所申請(qǐng)的存儲(chǔ)空間。

在頭文件V'stdlib.h”中包含了這些函數(shù)的信息，使用這些函數(shù)時(shí)需在程序開

頭用文件包含指令#include"stdlib.h”指明。

另請(qǐng)讀者注意，調(diào)用動(dòng)態(tài)存儲(chǔ)分配函數(shù)返回的指針是指向void類型或char類型

的指針，在具體使用時(shí)，要根據(jù)所指向的數(shù)據(jù)進(jìn)行強(qiáng)制類型轉(zhuǎn)換。

單鏈表的建立有頭插法、尾插法兩種方法。

1.頭插法

20

單鏈表是用戶不斷申請(qǐng)存儲(chǔ)單元和改變鏈接關(guān)系而得到的一種特殊數(shù)據(jù)結(jié)構(gòu)，將

鏈表的左邊稱為鏈頭，右邊稱為鏈尾。頭插法建單鏈表是將鏈表右端看成固定的，鏈

表不斷向左延伸而得到的。頭插法最先得到的是尾結(jié)點(diǎn)。

由于鏈表的長(zhǎng)度是隨機(jī)的，故用一個(gè)while循環(huán)來(lái)控制鏈表中結(jié)點(diǎn)個(gè)數(shù)。假設(shè)每

個(gè)結(jié)點(diǎn)的值都大于0，則循環(huán)條件為輸入的值大于。。申請(qǐng)存儲(chǔ)空間可使用mallocO

函數(shù)實(shí)現(xiàn)，需設(shè)立-申請(qǐng)單元指針，但mallocO函數(shù)得到的指針并不是指向結(jié)構(gòu)體的

指針，需使用強(qiáng)制類型轉(zhuǎn)換，將其轉(zhuǎn)換成結(jié)構(gòu)體型指針。剛開始時(shí)，鏈表還沒建立，

是一空鏈表，head指針為NULL。

鏈表建立的過(guò)程是申請(qǐng)空間、得到數(shù)據(jù)、建立鏈接的循環(huán)處理過(guò)程。

2.尾插法

若將鏈表的左端固定，鏈表不斷向右延伸，這種建立鏈表的方法稱為尾插法。

尾插法建立鏈表時(shí)，頭指針固定不動(dòng)，故必須設(shè)立一個(gè)搜索指針，向鏈表右邊延伸，

則整個(gè)算法中應(yīng)設(shè)立三個(gè)鏈表指針，即頭指針head、搜索指針p2、申請(qǐng)單元指針pl,

尾插法最先得到的是頭結(jié)點(diǎn)。

單鏈表c語(yǔ)言表示：

#include<stdio.h>

#include<stdlib.h>

structlinknode〃建立鏈表節(jié)點(diǎn)

(

intdata;〃需要更通用的數(shù)據(jù)類型

structlinknode*next;

);

structlink

(

structlinknode*head;

structlinknode*tail;

);

structlinknode*create()〃創(chuàng)建鏈表，接受INT型值

intdatas;

structlinknode*head,*temp,*tai1;

head=tail=NULL;

21

while(scanf(〃％d",&datas)==l)〃輸入方式有待改進(jìn)

temp=(structlinknode*)maHoc(sizeof(structlinknode));

if(temp二二NULL)

printf(''allocateerro!z，);

else

(

temp->data=datas;

temp->next=NULL;

if(head二二NULL)

head=tai1=temp;

else

(

tail->next=temp;

tail=temp;

}})

returnhead;

)

voidprint(structlinknode*head)〃打印鏈表

(

structlinknode*p;

p=head;

while(p)

(

printf(，，%d\tz，,p->data);

p=p->next;

}}

structlinknode*find(structlinknode*head,intdatas)〃查找特定的值

的節(jié)點(diǎn)

22

structlinknode*p;

p=head;

while(p->data!=datas&&p->next!=NULL)

(

p=p->next;

)

if(p->data==datas)

returnp;

else

returnNULL;

)

structlinknode*findAhead(structlinknode*head,intdatas)〃查找特定

值得前一個(gè)節(jié)點(diǎn)

(

structlinknode*p,*q;

q=NULL;

p=head;

while(p->data!=datas&&p->next!=NULL)

(

Q=P；

p=p->next;

)

if(p->data==datas)

returnq;

else

returnNULL;

)

structlinknode*enterTohead(structlinknode*head,intdatas)〃在頭部

添加節(jié)點(diǎn)

23

{〃改變了頭節(jié)點(diǎn)指針，需重新賦值

structlinknode*enter;

enter=(structlinknode*)malloc(sizeof(struct1inknode));

if(enter==NULL)

printf(''allocateerro!z，);

enter->data=datas;

enter->next=NULL;

if(head二二NULL)

head=enter;

else

(

enter->next=head;

head=enter;

)

returnhead;

)

structlinknode*enter