链表基础知识总结,链表的使用

链表基础知识

超级幼稚的课本基础知识“摘抄”。

先建立一个结构体：

1.建立链表

基本思想就是先建立一个头节点，让头指针head和尾指针tail指向该节点，设置指针域为null（链表结尾的标志）然后创建一个新的节点，将pnew指向它，将实际数据放在其数据域中，指针域为Null。将其插入到tail的后边再将tail指向pnew所指的节点。

2.链表的插入操作

在第i个后插入新的节点，基本思想为：先建立一个新的指针指向 head所指的节点，然后循环寻找第i个节点，将新节点的指针域指向第i 个节点的后继节点，再将第i 个节点的指针域指向新节点。

3.链表的删除操作

基本思想为：首先判断删除的是那个节点，因为头节点不可删除。在新定义p,q指针，循环寻找第i个节点，q指向p的后继节点即要删除的节点，再将p的指针域指向q的后继节点，最后不要忘记释放被删除的节点q。

4.节点的输出操作

基本思想：新定义的P 指针，从头指针开始循环输出，直到其指针域为null。

5.链表的销毁操作

基本思想：新定义p,q指针，p从头节点开始，q指向p的后继指针，然后将p的指针域指向q的后继指针，这样q节点被删除了，然后释放q节点的内存。最后适当头节点的内存。

我是c语言的初学者（自学）学到链表是看不太懂了，现求简单一点的链表的入门知识

首先，链表知识中的关键是指针。

所谓指针，是指一个用以保存内存位置的变量。

内存地址空间：

对于C程序来说，整个运算环境（计算机）中最重要的就是内存：内存有地址空间，其中每个地址唯一指定了一个字节的位置。

C程序的变量有几种，其中可以保存各种类型的数据，包括几种大小不同的整数、浮点数、组合的结构、联合等，每个变量都要在内存中占据某个位置的内存，其数量与其类型有关。

另一方面，既然每个变量都有内存位置（地址），那么这种地址也可以保存在变量中。这种变量就是指针。一个指针可以保存指向某个变量的地址，这极大地增加了C语言的灵活性。

链表：

对于表来说，简单的数组形式是把其表项挨个存储的，但对其插入和删除比较麻烦。如果每个表项都含有一个指向下一个表项的指针，那么在插入和删除是指要改动指针的值使其指向合适的新位置就可完成这些操作，这就是链表的基本原理。

数组顺序表挨个访问元素可以用下标递增或指针递增的方式进行，而连表挨个访问元素可以用指针不断替换为表项的“下一个”指针进行。数组顺序表要添加删除表项需要移动所有所涉及的表项，但链表只需在其相应位置维护几个指针就可完成。很明显，虽然链表灵活性比较大，但每个表项都要由程序员维护其存储的创建和删除，且不能进行随机访问（就是直接访问其中第N个表项的能力）只能从头移动到其位置。

链表的知识

链表的知识，涉及数据结构和指针

非一言能尽。

给个参考资料：谭浩强 《C程序设计》

第十章 结构和共用体 10.7 用指针处理链表：

10.7 用指针处理链表

10.7.1链标概述

链表是一种常见的重要的数据结构.它是动态地进行存储分配的一种结构.我们知道,用数组存放数据时,

必须事先定义固定的长度(即元素个数).比如,有的班级有100人,而有的班只有30人,如果要用同一个数组先后存放不同班级的学生数据,则必须定义长度为100的数组.如果事先难以确定一个班的最多人数,则必须把数组定得足够大,以能存放任何班级的学生数据.显然这将会浪费内存.链表则没有这种缺点,它根据需要开辟内存单元.图10.11表示最简单的一种链表(单向链表)的结构.链表有一个"头指针"变量,图中以head表示,它存放一个地址.

该地址指向一个元素.链表中每一个元素称为"结点",每个结点都应包括两个部分:一为用户需要用的实际数据,二为下一个结点的地址.课以看出,head指向第一个元素;第一个元素又指向第二个元素;……,直到最后一个元素,该元素不再指向其它元素,它称为'表尾",它的地址部分放一个"NULL"(表示"空地址").链表到此结束.

可以看到:链表中各元素在内存中可以不是连续存放的.要找某一元素,必须先找到上一个元素,根据它提供的下一元素地址才能找到下一个元素.

如果不提供"头指针"(head),则整个链表都无法访问.链表如同一条铁链一样,一环扣一环,中间是不能断开的.打个通俗的比方:幼儿园的老师带领孩子出来散步,老师牵着第一个小孩的手,第一个小孩的另一只手牵着第二个孩子,……,这就是一个"链",最后一个孩子有一只手空着,他是"链尾".要找这个队伍,必须先找到老师,然后顺序找到每一个孩子.

可以看到,这种链表的数据结构,必须利用指针变量才能实现

.即:一个结点中应包含一个指针变量,用它存放下一结点的地址.

前面介绍了结构体变量,它包含若干成员.这些成员可以是数值类型,字符类型,数组类型,也可以是指针类型.这个指针类型可以是指向其它结构体类型数据,也可以指向它所在的结构体类型.例如:

struct student

{int num;

float score;

struct student *next;

next是成员名,它是指针类型的,它指向struct student类型数据(这就是next所在的结构体类型).用这种方法可以建立链表.见图10.12.

其中每一个结点都属于struct student类型,它的成员next存放下一结点的地址,程序设计人员可以不必具体知道地址值,

只要保证将下一个结点的地址放到前一结点的成员next中即可.

请注意:上面只是定义了一个struct student类型,并未实际分配存储空间.前面讲过,链表结构是动态地分配存储的,即在需要时才开辟一个结点的存储单元.怎样动态地开辟和释放存储单元呢 C语言编译系统的库函数提供了以下有关函数.

1.malloc(size) 在内存的动态存储区中分配一个长度为size的连续空间.

此函数的值(即"返回值")是一个指针,它的值是该分配域的起始地址.如果此函数未能成功地执行,则返回值为0.

2.calloc(n,size) 在内存的动态区存储中分配n个长度为size的连续空间.函数返回分配域的起始地址;如果分配不成功,返回0.

3.free(ptr) 释放由ptr指向的内存区.ptr是最近一次调用ca11或ma11oc函数时返回的值.

上面三个函数中,参数n和size为整型,ptr为字符型指针.

请注意:许多C版本提供的malloc和call0c函数得到的是指向字符型数据的指针.新标准C提供的ma110c和ca11oc函数规定为void*类型.

有了本节所介绍的初步知识,下面就可以对链表进行操作了(包括建立链表,插入或删除链表中一个结点等).有些概念需要在后面的应用中逐步建立和掌握.

10.7.2建立链表

所谓建立链表是指从无到有地建立起一个链表,即一个一个地输入各结点数据,并建立起前后相链的关系.下面通过一个例子来说明如何建立一个链表.

[例10.7]写一函数建立一个有5名学生数据的单向链表.

先考虑实现此要求的算法(见图10. 13).

设三个指针变量:head,p1,p2,它们都指向结构体类型数据.先用mal1oc函数开辟一个结点,并使p1,p2指向它.

然后从键盘读人一个学生的数据给pl所指的结点.我们约定学号不会为零,如果输入的学号为0,则表示建立链表的过程完成,该结点不应连接到链表中.先使head的值为NULL(即等于0),这是链表为"空"时的情况(即head不指向任何结点,链表中无结点),以后增加一个结点就使head指向该结点.

如果输入的pl一num不等于0,而且输入的是第一个结点数据(n=1)时,则令head=p1,

即把p1的值赋给head,也就是使head也指向新开辟的结点(图10.14).P1所指向的新开辟的结点就成为链表中第一个结点.然后再开辟另一个结点并使p1指向它,接着读入该结点的数据(见图10.15(a)).如果输入的p1-num!=0,则应链入第2个结点(n=2),由于n!=1,则将p1的值赋给p2--next,也就是使第一个结点的next成员指向第二个结点(见图10.15(b)).接着使p2=p1,

也就是使p2指向刚才建立的结点,见图10.15(c).再开辟一个结点并使pl指向它,并读入该结点的数据(见图10.16(a)),在第三次循环中,由于n=3(n!=1),又将pl的值赋给p2一next,也就是将第3个结点连接到第2个结点之后,并使p2=p1,使p2指向最后一个结点(见图10.16(b).

再开辟一个新结点,并使pl指向它,

输入该结点的数据(见图10.17(a)).由于pl一num的值为0,不再执行循环,此新结点不应被连接到链表中.此时将NULL赋给p2一next,见图10.17(b).建立链表过程至此结束,pl最后所指的结点未链入链表中,第3个结点的next成员的值为NULL,它不指向任何结点.虽然pl指向新开辟的结点,但从链表中无法找到该结点.

建立链表的函数可以如下:

#define NULL 0

#define LEN sizeof(struct student)

struct student

{1ong num;

float score;

struct student *next;

};

int n;

struct student *creat()

/*此函数带回一个指向链表头的指针*/

{struct student *head;

struct student *p1, *p2;

n=0;

p1=p2=(struct student*)mal1oc(LEN);/*开辟一个新单元*/

scanf("%ld,%f",pl一num,pl一score);

head=NULL:

while (pl一num!=0)

{n=n十1;

if(n==1) head=pl;

else p2一next=p1;

p2=pl;

pl=(struct student*)malloc(LEN);

scanf("%1d,%f",p1--num,pl一score);

}

p2一next=NULL;

return(head);

}

请注意:

(1)第一行为#define命令行,令NULL代表0,用它表示"空地址".第二行令LEN代表struct student结构体类型数据的长度,

sizeof是"求字节数运算符".

(2)第9行定义一个creat函数,它是指针类型,即此函数带回一个指针值,它指向一个struct student类型数据.实际上此creat函数带回一个链(3)malloc(LEN)的作用是开辟一个长度为LEN的内存区,LEN已定义为sizeof(struct student),即结构体struct student的长度.在一般系统中,malloc带回的是指向字符型数据的指针.

而p1,p2是指向struct student类型数据的指针变量,二者所指的是不同类型的数据,这是不行的.因此必须用强制类型转换的方法使之类型一致,在malloc (LEN)之前加了"(struct student*)",它的作用是使malloc返回的指针转换为指向struct student类型数据的指针.注意"*"号不可省略,否则变成转换成struct student类型了,而不是指针类型了.

(4)最后一行return后面的参数是head(head已定义为指针变量,指向struct student类型数据).因此函数返回的是head的值,也就是链表的头地址.

(5)n是结点个数.

(6)这个算法的思路是:让pl指向新开的结点,p2指向链表中最后一个结点,把pl所指的结点连接在p2所指的结点后面,用"p2一next=pl"来实现.

我们对建立链表过程作了比较详细的介绍,

读者如果对建立链表的过程比较清楚的话,对下面介绍的删除和插入过程也就比较容易理解了.

10.7.3输出链麦

将链表中各结点的数据依次输出.这个问题比较容易处理.首先要知道链表头元素的地址,也就是要知道head的值.然后设一个指针变量p,先指向第一个结点,输出p所指的结点,然后使p后移一个结点,再输出.直到链表的尾结点.

「例10.8]写出输出链表的函数print.

void print(head)

struct student *head;

{struct student *p;

printf("\nNow,These%drecords are:\n",n);

p=head;

if(head!=NULL)

do

{printf("%ld%5.1f\",p一num,p—score);

p=p一next;

}while(p!=NULL);

算法可用图10.18表示.

其过程可用图10.19表示.p先指向第一结点,在输出完第一个结点之后,p移到图中p'虚线位置,指向第二个结点.程序中p=p一next的作用是:将p原来所指向的结点中next的值赋给p,

而p一next的值就是第二个结点的起始地址.将它赋给p就是使p指向第二个结点.

head的值由实参传过来,也就是将已有的链表的头指针传给被调用的函数,在print函数中从head所指的第一个结点出发顺序输出各个结点.

10.7.4 对链麦的删除操作

已有一个链表,希望删除其中某个结点.怎样考虑此问题的算法呢,先打个比方:

一队小孩(A.B.C.D.E)手拉手,如果某一小孩(C)想离队有事,而队形仍保持不变.只要将C的手从两边脱开,B改为与D拉手即可,见图10.20.图10.20(a)是原来的队伍,图10.20(b)是c离队后的队伍.

与此相仿,从一个链表中删去一个结点,并不是真正从内存中把它抹掉,而是把它从链表中分离开来,即改变链接关系即可.

[例10.9]写一函数以删除指定的结点.

我们以指定的学号作为删除结点的标志.例如,输入89103表示要求删除学号为89103的结点.解题的思路是这样的:从p指向的第一个结点开始,检查该结点中的num值是否等于输入的要求删除的那个学号.如果相等就将该结点删除,如不相等,就将p后移一个结点,再如此?下去,直到遇到表尾为止.

可以设两个指针变量pl和p2,先使pl指向第一个结点(图10.21(a)).如果要删除的不是第一个结点,

则使pl后指向下一个结点(将pl一next赋给pl),在此之前应将pl的值赋给p2,使p2指向刚才检查过的那个结点,见图10.21(b).如此一次一次地使p后移,直到找到所要删除的结点或检查完全部链表都找不到要删除的结点为止.如果找到某一结点是要删除的结点,还要区分两种情况:①要删的是第一个结点(pl的值等于head的值,如图10.21(a)那样),则应将pl一next赋给head.见图10.21(c).

这时head指向原来第二个结点.第一个结点虽然仍存在,但它已与链表脱离,因为链表中没有一个元素或头指针指向它.虽然p1还指向它,它仍指向第二个结点,但仍无济于事,现在链表的第一个结点是原来第二个结点,原来第一个结点"丢失".②如果要删除的不是第一个结点,则将pl一next赋给p2一next,见图10.21(d).p2一next原来指向pl指向的结点(图中第二个结点),现在p2一next改为指向p1一next所指向的结点

(图中第三个结点).pl所指向的结点不再是链表的一部分.

还需要考虑链表是空表(无结点)和链表中找不到要删除的结点的情况.

图10.22表示解此题的算法.

删除结点的函数del如下:

struct student *del(head,num)

struct student *head;

1ong num;

{struct student *p1,*p2;

if(head==NULL) {printf("\nlist null!\n");goto end;}

p1=head;

whi1e (num!=pl一numpl一next!一NULL)/*pl指向的不是所要找的结点,并且后面还有结点点*/

{p2=p1;pl=pl一next;}/*后移一个结点*/

if (num==pl一num) /*找到了*/

{if (n1==head) head=pl一next;/*若pl指向的是头结点,把第二个结点地址赋予head*/

e1se p2一next=pl一next;/*否则将下一结点地址赋给前一结点地址*\

printf("delete:%ld\n",num);

n=n-1;

}

else printf("%ld not been found!\n",num);/*找不到该结点*/

end:

return(head);

}

函数的类型是指向struct student类型数据的指针,

它的值是链表的头指针.函数参数为head和要删除的学号num.head的值可能在函数执行过程中被改变(当删除第一个结点时).

10.7.5对链表的插入操作

将一个结点插入到一个已有的链表中.设已有的链表中各结点中的成员项num(学号)是按学号由小到大顺序排列的.

用指针变量p0指向待插入的结点,pl指向第一个结点.见图10.23(a).

将p0一num与pl一num相比较,如果p0一numpl一num,则待插入的结点不应插在pl所指的结点之前.此时将pl后移,并使p2指向刚才pl所指的结点,见图10.23(b).再将p1一num与p0一num比.如果仍然是p0一num大,则应使pl继续后移,直到p0一numnum为止.这时将p0所指的结点插到pl所指结点之前.但是如果p1所指的已是表尾结点,则pl就不应后移了.如果p0一num比所有结点的num都大,

则应将p0所指的结点插到链表末尾.

如果插入的位置既不在第一个结点之前,又不在表尾结点之后,则将p0的值赋给p2一next,即使p2一next指向待插入的结点,然后将pl的值赋给p0-next,即使得p0一next指向pl指向的变量.见图10.23(c).可以看到,在第一个结点和第二个结点之间已插入了一个新的结点.

如果插入位置为第一结点之前(即pl等于head时),

则将p0赋给head,将p1赋给p0-next.见图10.23(d).如果要插到表尾之后,应将p0赋给pl一next,NULL赋给p0一next,见图10.23(e).

以上算法可用图10.24表示.

[例10. 10]插入结点的函数insert如下.

struct student *insert(head,stud)

struct student *head,*stud:

{struct student *p0,*p1,*p2;

pl=head;/*使pl指向第一个结点*/

p0=stud;/*p0指向要插入的结点*/

if (head==NULL)/*原来是空表*/

{head=p0;p0一next=NULL;}/*使p0指向的结点作为第一个结点*/

else

{while ((p0一numpl一num)(pl一next!=NULL))

{p2=p1;p1=pl一next;}/*p2指向刚才pl指向的结点,p1后移一个结点*/

if(p0-numnext=p0;/*插到p2指向的结点之后*/

p0—next=p1;}

else

{pl一next=p0;p0一next=NULL;}}/*插到最后的结点之后*/

n=n+1; /*结点数加1*/

return(head);

}

函数参数是head和stud.stud也是一个指针变量,从实参传来待插入结点的地址给stud.语句p0=stud的作用是使p0指向待插入的结点.

函数类型是指针类型,函数值是链表起始地址head.

将以上建立,输出,删除,插入的函数组织在一个程序中,用main函数作主调函数.可以写出以下main函数.

main()

{struct student *head,stu;

1ong de1_num;

printf("input records:\n");

head=creat(); /*返回头指针*/

print(head); /*输出全部结点*/

printf("\ninput the deleted 0number:");

scanf("%ld",de1_mum);/*输入要删除的学号*/

head=del(head,de1_num);/*删除后的头地址*/

print(head); /*输出全部结点*/

prinif("/ninput the inserted record:")/*输入要插入的记录*/

scanf("%ld,%f",stu.num,stu.score);

head=insert(head,stu);/*返回地址*/

print(head);

}

此程序运行结果是正确的.

它只删除一个结点,插入一个结点.但如果想再插入一个结点,重复写上程序最后四行,即共插入两个结点.运行结果却是错误的.

input records:(建立链表)

89101,90

89103,98

89105,76

0,0

Now,These 3 records are:

89101 90.0

89103 98.0

89105 76.0

inpu the deleted number:

89103 (删除)

delete:89103

Now,These 2 records are:

89101 90.0 89105 76.0

input the inserted record:89102

90 (插入第一个结点)

Now,These 3 records are:

89101 90.0

89102 90.0

89105 76.0

input the inserted record:89104,99/(插入第二个结点)

Now,The 4 records are:

89101 90.0

89104 99.0

89104 99.0

89104 99.0

...

...

(无终止地输出89104的结点数据)

请读者将main与insert函数结合起来考察为什么会产生以上运行结果.

出现以上结果的原因是:stu是一个有固定地址的变量.第一次把stu结点插入到链表中.第二次若再用它来插入第二个结点,就把第一次结点的数据冲掉了.

实际上并没有开辟两个结点.读者可根据insert函数画出此时链表的情况.为了解决这个问题,必须在每插入一个结点时新开辟一个内存区.我们修改main函数,使之能删除多个结点(直到输入要删的学号为0),能插入多个结点(直到输入要插入的学号为0).

main函数如下:

main()

{struct student *head,*stu;

1ong de1_num;

printf("input records:/n");

head=creat();

print (head);

printf("/ninput the deleted number:");

scanf("%1d",del_num);

while (de1_num!=0)

{head=del(head,del_num);

print(head);

printf("input the deleted number:");

scanf("%ld",del_num);

printf("\ninput the inserted record:");

stu=(struct student*)malloc(LEN);

scanf("%1d,%f,",stu一num,stu一scor);

while (stu一num!=0)

{head=insert(head,stu):

print(head);

prinif("input the inserted record:");

stu=(struct student*)malloc(LEN);

scanf("%1d,%f,stu一num,stu一score);

}

}

sum定义为指针变量,在需要插入时先用malloc函数开辟一个内存区,将其起始地址经强制类型转换后赋给stu,然后输入此结构体变量中各成员的值.对不同的插入对象,stu的值是不同的,每次指向一个新的结构体变量.在调用insert函数时,实参为head和stu,将已建立的链表起始地址传给insert函数的形参,将stu(既新开辟的单元的地址)传给形参stud,函数值返回经过插入之后的链表的头指针(地址).

运行情况如下:

input records:

89101,99

89103,87

89105,77

0,0

Now, These 3 records are.

89101 99.0

89103 87.0

89105 77.0

input the deleted number:89103

delete:89103

Now,These 2 records are:

89101 99.0

89105 77.0

input the de1eted number:89105

delete:89105

Now,These l records are:

89101 99.0

input the de1eted number:0

1nput the inserted record:89104,87

NOw,These 2 records are:

89101 99.0

89104 87.0

input the inserted record:89106,65

Now,These 3 records are:

89101 99.0

89104 87.0

89106 65.0

input the inserted record:0,0

对这个程序请读者仔细消化.

指针的应用领域很宽广,除了单向链表之外,还有环形链表,双向链表.此外还有队列,树,栈,图等数据结构.

有关这些问题的算法可以学习《数据结构课程,在此不作详述.

C语言中有关链表的基础知识

举个例子：假设你想到C的家中拿一样东西，但你不知道C家的地址，不过，你知道A家的地址，A家有B的地址，B有C的地址，

所以，你到A处找到B的地址，再去B处找到C的地址，就知道C的地址了。链表就是这个意思，每一个元素都保存有下一个元素的地址，根据这个地址，你可以依次找到最后一个元素，故形成了一个链。

这个代码，重点就在于结构体，结构体名是：node

其中包含两个成员变量，一个是

int类型的数据，一个就是

例子中的

“

地址

”，这个

“

地址

”

是一个变量的地址，而这个变量又是你定义的结构体

node

的存储位置，而这个变量又包含两个变量（int数据和

“

地址

”

），这样就形成了链表。

以后你会知道这种

‘

地址

’

就是一种变量

叫

指针。