計算機資料補充

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

管態(tài)是指操作系統(tǒng)在運行系統(tǒng)的管理程序時所處的狀態(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)下運行，CPU在管態(tài)下可以執(zhí)行指令系統(tǒng)的全集。

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

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

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

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

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

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

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

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

程序也可以象征性地稱為處于進程的內(nèi)核態(tài)。因為中斷處理程序?qū)⑹褂卯斍斑M程的內(nèi)核棧。

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

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

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

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

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

有區(qū)別。

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

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

戶態(tài)。

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

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

userapi—>interrupt->kernelapi->interrupt

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

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

個運行級別，從0-3,0為最高級別,3為最低級別。

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

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

有很多了，不只是這一點。

操作系統(tǒng)下是利用這個特點，當操作系統(tǒng)自己的代碼運行時，CPU就切成0級，當用戶的

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

辦法做到。

當然，低級別的程序是沒法把自己升到高級別的,也就是說用戶程序運行在3級,他想把

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

所有的程序的運行,確保系統(tǒng)的安全了.平時把操作系統(tǒng)運行時的級別就叫內(nèi)核態(tài)（因為是

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

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

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

1

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

為3級，即最低級，然后才讓你運行，所以沒辦法，你只能在最低級運行了，因為沒辦法把自

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

因.

特權(quán)指令

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

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

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

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

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

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

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

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

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

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

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

一般說來，在單用戶，單任務的計算機中不具有也不需要特權(quán)指令，而在多用戶，多任

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

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

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

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

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

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

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

訪管指令

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

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

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

廣義指令

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

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

2

雙向鏈表

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

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

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

鏈表的操作

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

typedefstructDuLNode

(

ElemTypedata;

structDuLNode*prior,*next;

}DuLNode,*DuLinkList;

帶頭結(jié)點的雙向循環(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指向第一個結(jié)點*/

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

(

q=p->next;

free(p);

P=q；

)

3

free(*L);

*L=NULL;

)

重置鏈表為空表

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

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

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

(

q=p->next;

free(p);

P二q;

)

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

)

驗證是否為空表

StatusListEmpty(DuLinkListL)

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

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

returnTRUE;

else

returnFALSE;

)

元素的操作

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

intListLength(DuLinkListL)

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

inti=0;

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

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

4

i++；

p=p->next;

)

returni;

)

賦值

StatusGetElem(DuLinkListL,inti,ElemType*e)

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

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

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

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

(

p=p->next;

j++；

)

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

returnERROR;

*e=p->data;/*取第i個元素*/

returnOK;

)

查找元素

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

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

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

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

inti=0;

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

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ù)元素，且不是第一個，則用pre_e返回它

的前驅(qū)*/

/*否則操作失敗，pre_e無定義*/

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

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ù)元素，且不是最后一個，則用next_e返回

它的后繼，*/

/*否則操作失敗，next_e無定義*/

6

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

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

{

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

(

*next_e=p->data;

returnTRUE;

)

p=p->next;

)

returnFALSE;

)

查找元素地址

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

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

i個元素不存在，*/

/*返回NULL*/

intj;

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

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

returnNULL;

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

p=p->next;

returnp;

)

元素的插入

StatusListinsert(DuLinkListL,inti,ElemTypee)

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

為IWiW表長+1*/

/*改進算法2.18,否則無法在第表長+1個結(jié)點之前插入元素*/

7

DuLinkListp,s;

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

returnERROR;

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

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

returnERROR;

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

if(!s)

returnOVERFLOW;

s->data=e;

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

s->next=p->next;

p->next->prior=s;

p->next=s;

returnOK;

)

元素的刪除

StatusListDelete(DuLinkListL,inti,ElemType*e)

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

長*/

DuLinkListp;

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

returnERROR;

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

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

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é)點出發(fā)，正序?qū)γ總€數(shù)據(jù)元素調(diào)用函數(shù)visit。

*/

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

while(p!=L)

(

visit(p->data);

p=p->next;

)

printf(*\n*);

)

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

逆序查找

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

另加*/

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

while(p!=L)

(

visit(p->data);

p=p->prior;

)

printf("\n");

)

雙向鏈表模板

/*文件名：LinkedList.h

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

9

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

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

^pragmaonce

iiinclude<assert.h>

template<classT>

classLinkedList

(

private:

classNode

(

public:

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

Node*prior;//指向前一個結(jié)點

Node*next;//指向下一個結(jié)點

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

prior(pri){}

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

試可行

)；

Node*head;〃指向第一個結(jié)點

public:

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

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;}

〃獲取最后一個元素

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

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

voiddelLastElement(){

assert(!isEmpty());

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

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

)

〃修改最后一個元素

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指定的位置插入元素。原來position及后面的元素后移*/

template<classT>

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

(

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

Node*p=head;

while(position)

(

p=p->next;

position一-；

)

//此時p指向要插入的結(jié)點

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;

〃此時p指向要刪除元素

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;

)

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

template<classT>

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

(

Node*p=head-〉next;

while(p!=head)

(

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

數(shù)據(jù)

p=p->next;

14

}}

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

template<classT>

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

(

Node*p=head->prior;

while(p!=head)

(

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

數(shù)據(jù)

p=p->prior;

}}

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

函數(shù)是有限制的.重載它是為了客戶端代碼簡潔，因為從鏈表讀寫數(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)后，對象又剛好超出作用域再調(diào)用該函數(shù)

(

clearAllElement();

deletehead;

head=O;

})

循環(huán)鏈表

循環(huán)鏈表是另?種形式的鏈式存貯結(jié)構(gòu)。它的特點是表中最后個結(jié)點的指針域指向頭

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

分類：

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

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

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

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

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

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

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

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

循環(huán)鏈表的特點：循環(huán)鏈表的特點是無須增加存儲量，僅對表的鏈接方式稍作改變，

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

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

16

接成一個線性表（al,…，an,bl,?-?bm）的運算。

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

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

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

相應的算法如下：

LinkListConnect（LinkListA,LinkListB）

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

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

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

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

B->next=p;//@

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

）

注意：

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

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

指針或尾指針等。

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

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

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

單鏈表

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

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

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

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

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

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

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

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

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

元素。

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

單鏈表

17

1、鏈接存儲方法

鏈接方式存儲的線性表簡稱為鏈表（LinkedList）?

鏈表的具體存儲表示為：

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

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

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

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

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

注意：

鏈式存儲是最常用的存儲方式之一，它不僅可用來表示線性表，而且可用來表示

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

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

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

|data|next!

I______I_______l

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

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

注意：

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

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

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

圖

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

單鏈表中每個結(jié)點的存儲地址是存放在其前趨結(jié)點next域中，而開始結(jié)點無前

趨，故應設(shè)頭指針head指向開始結(jié)點。

注意：

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

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

終端結(jié)點無后繼，故終端結(jié)點的指針域為空，即NULL。

4、單鏈表的一般圖示法

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

18

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

就可以表示為下圖形式。

5、單鏈表類型描述

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

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

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

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

}ListNode;

typedefListNode*LinkList;

ListNode*p;

LinkListhead;

注意：

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

匕更明確)

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

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

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

指針變量結(jié)點變量

定義在變量說明部分顯式定義在程序執(zhí)行時，通過標準函數(shù)malloc生成

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

操作方式通過指針變量名訪問通過指針生成、訪問和釋放

①生成結(jié)點變量的標準函數(shù)

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

〃函數(shù)malloc分配一個類型為ListNode的結(jié)點變量的空間，并將其首地址放入

指針變量P中

②釋放結(jié)點變量空間的標準函數(shù)

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

③結(jié)點分量的訪問

利用結(jié)點變量的名字*P訪問結(jié)點分量

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

19

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

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

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

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

(*p).data的值一一p指針所指結(jié)點的data域的值

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

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

注意：

①若指針變量P的值為空(NULL),則它不指向任何結(jié)點。此時，若通過*p來

訪問結(jié)點就意味著訪問?個不存在的變量，從而引起程序的錯誤。

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

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

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

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

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

單鏈表的建立

鏈表操作中動態(tài)存儲分配要使用標準函數(shù)，先介紹一下這些函數(shù)。

(l)malloc(size)

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

(2)calloc(n,size)

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

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

(3)free(p)

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

或calloc()函數(shù)時所申請的存儲空間。

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

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

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

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

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

1.頭插法

20

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

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

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

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

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

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

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

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

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

2.尾插法

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

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

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

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

單鏈表c語言表示：

#include<stdio.h>

#include<stdlib.h>

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

(

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)〃輸入方式有待改進

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é)點

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)〃查找特定

值得前一個節(jié)點

(

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é)點

23

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

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