动态链表和静态链表

方式一：链表通常可以使用 结构体+指针 来实现[ 动态链表 ]

这是第一种实现方式，但是这种方式有一些弊端，比如链表添加节点需要 new 一个新的 Node ，new是非常慢的过程，还消耗内存资源。算法题中链表的大小一般是100万级别，单单new出100万个节点就已经会超时了。

方式二：数组模拟链表[ 静态链表 ] 每一个节点提前准备好，没有指针的语言中可以使用

好处：快！而且普通链表的功能比如排序也都有，就是实现起来麻烦一点~。

特点：链表的实现也是可以不借助指针的。

单链表往往需要 head 来指向第一个节点；但是双链表不需要 head ，而是直接使用两个数(0,1)来表示初始左右节点，但是这两个节点里面没有值，注意idx需要从 2 开始。

Acwing: 双链表

实现一个双链表，双链表初始为空，支持 5 种 *** 作：

在最左侧插入一个数；

在最右侧插入一个数；

将第 k 个插入的数删除；

在第 k 个插入的数左侧插入一个数；

在第 k 个插入的数右侧插入一个数

现在要对该链表进行 M 次 *** 作，进行完所有 *** 作后，从左到右输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如 *** 作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。

实现一个双链表，双链表初始为空，支持 5 种 *** 作：

在最左侧插入一个数；

在最右侧插入一个数；

将第 k 个插入的数删除；

在第 k 个插入的数左侧插入一个数；

在第 k 个插入的数右侧插入一个数

现在要对该链表进行 M 次 *** 作，进行完所有 *** 作后，从左到右输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如 *** 作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。

给你些资料吧~仔细看，看完就明白链表了

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一>num&&pl一>next!一NULL)/*pl指向的不是所要找的结点,并且后面还有结点点*/

{p2=p1pl=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一>num>pl一>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=p0p0一>next=NULL}/*使p0指向的结点作为第一个结点*/

else

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

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

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

p0—>next=p1}

else

{pl一>next=p0p0一>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

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

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

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

---