计算机资料补充

管态和目态

管态是指操作系统在运行系统的管理程序时所处的状态。此状态下可以执行任何指令，

包括特权指令。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