管態和目態

管態是指操作系統在運行系統的管理程序時所處的狀態。此狀態下可以執行任何指令，

包括特權指令。CPU的狀態屬于程序狀態字PSW的一位，管態又稱特權狀態、系統態或核

心態。通常，操作系統在管態下運行，CPU在管態下可以執行指令系統的全集。

目態是指操作系統在運行系統的應用程序所處的狀態。只允許應用程序訪問自己的內存空

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

程序只能執行非特權指令。用戶程序只能在目態下運行。

當一個任務（進程）執行系統調用而陷入內核代碼中執行時，我們就稱進程處于內核運

行態（或簡稱為內核態）。此時處理器處于特權級最高的（0級）內核代碼中執行。當進程

處于內核態時，執行的內核代碼會使用當前進程的內核棧。每個進程都有自己的內核棧。當

進程在執行用戶自己的代碼時，則稱其處于用戶運行態（用戶態）。即此時處理器在特權級

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

程序也可以象征性地稱為處于進程的內核態。因為中斷處理程序將使用當前進程的內核棧。

這與處于內核態的進程的狀態有些類似。

1、用系統調用時進入核心態。Linux對硬件的操作只能在核心態，這可以通過寫驅動

程序來控制。在用戶態操作硬件會造成coredump.

2、要注意區分系統調用和一般的函數。系統調用由內核提供，如read。、write。、

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

有區別。

3、一般情況：系統調用運行在核心態，函數運行在用戶態。但也有一些函數在內部使

用了系統調用（如fopen）,這樣的函數在調用系統調用是進入核心態，其他時候運行在用

戶態。

大概是當用戶程序調用系統的API時，就產生中斷，進入內核態的API,處理完成后，

用中斷再退出，返回用戶態的調用函數。

userapi—>interrupt->kernelapi->interrupt

簡單來講一個進程由于執行系統調用而開始執行內核代碼，我們稱該進程處于內核態中.

一個進程執行應用程序自身代碼則稱該進程處于用戶態。intelx86架構的CPU分為好幾

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

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

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

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

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

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

辦法做到。

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

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

所有的程序的運行,確保系統的安全了.平時把操作系統運行時的級別就叫內核態（因為是

操作系統內核運行時的狀態），而且普通用戶程序運行時的那個級別叫用戶態...

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

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

1

者?，由于你的程序都是由操作系統來加載的,所以當它把你加載上來后,就把你的運行狀態設

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

己從低級上升到高級，這就是操作系統在內核態可以管理用戶程序，殺死用戶程序的原

因.

特權指令

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

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

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

這得從CPU指令系統（用于控制CPU完成各種功能的命令）的特權級別說起。在CPU的所

有指令中，有一些指令是非常危險的，如果錯用，將導致整個系統崩潰。比如：清內存、設

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

所以，CPU將指令分為特權指令和非特權指令，對于那些危險的指令，只允許操作系統及其

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

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

特權指令如果錯用，將導致整個系統崩潰。比如：清內存、設置時鐘等。如果所有的程

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

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

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

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

創建和切換等。

系統調用命令

系統調用是用戶程序請求操作系統為其服務的惟一形式，在UNIX中把系統調用稱為程

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

序根據trap的類型轉向相應的處理程序

訪管指令

訪管指令是一條可以在目態下執行的指令，用戶程序中凡是要調用操作系統功能時就安

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

程序的執行，而讓操作系統來為用戶服務

廣義指令

廣義指令是指VC或者其他一些編程環境提供的庫函數，這些庫函數集成了操作系統提

供的系統調用，比如API

2

雙向鏈表

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直

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

驅結點和后繼結點。一般我們都構造雙向循環鏈表。

鏈表的操作

線性表的雙向鏈表存儲結構

typedefstructDuLNode

(

ElemTypedata;

structDuLNode*prior,*next;

}DuLNode,*DuLinkList;

帶頭結點的雙向循環鏈表的基本操作

voidInitList(DuLinkList*L)

{/*產生空的雙向循環鏈表L*/

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

if(*L)

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

else

exit(OVERFLOW);

)

銷毀雙向循環鏈表L

voidDestroyList(DuLinkList*L)

(

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

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

(

q=p->next;

free(p);

P=q；

)

3

free(*L);

*L=NULL;

)

重置鏈表為空表

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

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

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

(

q=p->next;

free(p);

P二q;

)

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

)

驗證是否為空表

StatusListEmpty(DuLinkListL)

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

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

returnTRUE;

else

returnFALSE;

)

元素的操作

計算表內元素個數

intListLength(DuLinkListL)

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

inti=0;

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

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

4

i++；

p=p->next;

)

returni;

)

賦值

StatusGetElem(DuLinkListL,inti,ElemType*e)

{/*當第i個元素存在時，其值賦給e并返回OK,否則返回ERROR*/

intj=l;/*j為計數器*/

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

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。是數據元素判定函數*/

/*操作結果：返回L中第1個與e滿足關系compare。的數據元素的位序。*/

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

inti=0;

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

while(p!=L)

5

i++；

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

returni;

p=p->next;

)

return0;

)

查找元素前驅

StatusPriorElem(DuLinkListL,ElemTypecure,ElemType*pree)

{/*操作結果：若cur_e是L的數據元素，且不是第一個，則用pre_e返回它

的前驅*/

/*否則操作失敗，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)

{/*操作結果：若cur_e是L的數據元素，且不是最后一個，則用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,返回頭結點的地址。若第

i個元素不存在，*/

/*返回NULL*/

intj;

DuLinkListp=L;/*p指向頭結點*/

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

returnNULL;

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

p=p->next;

returnp;

)

元素的插入

StatusListinsert(DuLinkListL,inti,ElemTypee)

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

為IWiW表長+1*/

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

7

DuLinkListp,s;

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

returnERROR;

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

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

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)

{/*刪除帶頭結點的雙鏈循環線性表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))

{/*由雙鏈循環線性表L的頭結點出發，正序對每個數據元素調用函數visit。

*/

DuLinkListp=L->next;/*p指向頭結點*/

while(p!=L)

(

visit(p->data);

p=p->next;

)

printf(*\n*);

)

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

逆序查找

{/*由雙鏈循環線性表L的頭結點出發，逆序對每個數據元素調用函數visitOo

另加*/

DuLinkListp=L->prior;/*p指向尾結點*/

while(p!=L)

(

visit(p->data);

p=p->prior;

)

printf("\n");

)

雙向鏈表模板

/*文件名：LinkedList.h

*功能：實現雙向鏈表的基本功能

9

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

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

^pragmaonce

iiinclude<assert.h>

template<classT>

classLinkedList

(

private:

classNode

(

public:

Tdata;〃數據域，不要求泛型T的實例類有無參構造函數

Node*prior;//指向前一個結點

Node*next;//指向下一個結點

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

prior(pri){}

Node0:data(data){}〃泛型T的實例類的復制構造函數將被調用.在Vc2010測

試可行

)；

Node*head;〃指向第一個結點

public:

〃初始化：構造一個空結點，搭建空鏈

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

〃獲取元素總數

intelementToatal()const;

〃判斷是否為空鏈

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

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

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的指針設置

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

〃重載□函數

11

T&operator[](intindex);

〃清空鏈表

voidclearAHElement();

〃銷毀鏈表

^LinkedList();

)；

/*返回元素總數*/

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指向要插入的結點

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;

)

/*正向遍歷，以鏈表中每個元素作為參數調用visit函數*/

template<classT>

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

(

Node*p=head-〉next;

while(p!=head)

(

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

數據

p=p->next;

14

}}

/*反向遍歷，以鏈表中每個元素作為參數調用Visit函數*/

template<classT>

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

(

Node*p=head->prior;

while(p!=head)

(

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

數據

p=p->prior;

}}

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

函數是有限制的.重載它是為了客戶端代碼簡潔，因為從鏈表讀寫數據是最常用的*/

template<classT>

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

(

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

提條件

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;〃收尾工作

)

/*析構函數，若內存足夠沒必要調用該函數*/

template<classT>

LinkedList<T>::^LinkedList()

(

if(head)〃防止用戶顯式析構后，對象又剛好超出作用域再調用該函數

(

clearAllElement();

deletehead;

head=O;

})

循環鏈表

循環鏈表是另?種形式的鏈式存貯結構。它的特點是表中最后個結點的指針域指向頭

結點，整個鏈表形成一個環。

分類：

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

或開始結點即可。

(2)多重鏈的循環鏈表一一將表中結點鏈在多個環上。

帶頭結點的單循環鏈表：判斷空鏈表的條件是head-head->next;

僅設尾指針的單循環鏈表：用尾指針rear表示的單循環鏈表對開始結點al和終端結

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

多采用尾指針表示單循環鏈表。帶尾指針的單循環鏈表可見下圖。

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

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

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

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

16

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

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

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

指針表示的單循環鏈表上實現，則只需修改指針，無須遍歷，其執行時間是0（1）。

相應的算法如下：

LinkListConnect（LinkListA,LinkListB）

{〃假設A,B為非空循環鏈表的尾指針

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

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

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

B->next=p;//@

returnB;〃返回新循環鏈表的尾指針

）

注意：

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

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

指針或尾指針等。

②在單鏈表中，從一已知結點出發，只能訪問到該結點及其后續結點，無法找到

該結點之前的其它結點。而在單循環鏈表中，從任一結點出發都可訪問到表中所有結

點，這一優點使某些運算在單循環鏈表上易于實現。

單鏈表

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

以元素（數據元素的映象）+指針（指示后繼元素存儲位置）=結點（表示數據元

素或數據元素的映象）

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

循環單鏈表是單鏈表的另一種形式，其結構特點鏈表中最后一個結點的指針域不

再是結束標記，而是指向整個鏈表的第一個結點，從而使鏈表形成一個環。和單鏈表

相同，循環鏈表也有帶頭結點結構和不帶頭結點結構兩種，帶頭結點的循環單鏈表實

現插入和刪除操作較為方便。

單鏈表是一種順序存取的結構，為找第i個數據元素，必須先找到第iT個數據

元素。

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

單鏈表

17

1、鏈接存儲方法

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

鏈表的具體存儲表示為：

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

也可以是不連續的）

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

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

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

注意：

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

各種非線性的數據結構。

2、鏈表的結點結構

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

|data|next!

I______I_______l

data域一存放結點值的數據域

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

注意：

①鏈表通過每個結點的鏈域將線性表的n個結點按其邏輯順序鏈接在一起的。

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

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

圖

3、頭指針head和終端結點指針域的表示

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

趨，故應設頭指針head指向開始結點。

注意：

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

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

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

4、單鏈表的一般圖示法

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

18

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

就可以表示為下圖形式。

5、單鏈表類型描述

typedefcharDataType;//假設結點的數據域類型為字符

typedefstructnode{〃結點類型定義

DataTypedata;〃結點的數據域

structnode*next;〃結點的指針域

}ListNode;

typedefListNode*LinkList;

ListNode*p;

LinkListhead;

注意：

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

匕更明確)

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

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

6、指針變量和結點變量

指針變量結點變量

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

取值非空時，存放某類型結點實際存放結點各域內容的地址

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

①生成結點變量的標準函數

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

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

指針變量P中

②釋放結點變量空間的標準函數

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

③結點分量的訪問

利用結點變量的名字*P訪問結點分量

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

19

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

④指針變量P和結點變量*P的關系

指針變量P的值一一結點地址

結點變量*P的值一一結點內容

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

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

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

注意：

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

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

②有關指針類型的意義和說明方式的詳細解釋

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

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

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

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

單鏈表的建立

鏈表操作中動態存儲分配要使用標準函數，先介紹一下這些函數。

(l)malloc(size)

在內存的動態存儲區申請一個長度為size字節的連續空間。

(2)calloc(n,size)

在內存的動態存儲區申請n個長度為size字節的連續空間，函數返回值為分配

空間的首地址。若此函數未被成功執行，函數返回值為。。

(3)free(p)

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

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

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

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

另請讀者注意，調用動態存儲分配函數返回的指針是指向void類型或char類型

的指針，在具體使用時，要根據所指向的數據進行強制類型轉換。

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

1.頭插法

20

單鏈表是用戶不斷申請存儲單元和改變鏈接關系而得到的一種特殊數據結構，將

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

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

由于鏈表的長度是隨機的，故用一個while循環來控制鏈表中結點個數。假設每

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

函數實現，需設立-申請單元指針，但mallocO函數得到的指針并不是指向結構體的

指針，需使用強制類型轉換，將其轉換成結構體型指針。剛開始時，鏈表還沒建立，

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

鏈表建立的過程是申請空間、得到數據、建立鏈接的循環處理過程。

2.尾插法

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

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

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

尾插法最先得到的是頭結點。

單鏈表c語言表示：

#include<stdio.h>

#include<stdlib.h>

structlinknode〃建立鏈表節點

(

intdata;〃需要更通用的數據類型

structlinknode*next;

);

structlink

(

structlinknode*head;

structlinknode*tail;

);

structlinknode*create()〃創建鏈表，接受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)〃查找特定的值

的節點

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

值得前一個節點

(

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)〃在頭部

添加節點

23

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

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