数据结构——线性表之链式存储

刺骨的言语ヽ痛彻心扉 2022-06-16 22:19 247阅读 0赞

# 数据结构——线性表之链式存储 #

## 1、单链表 ##

由于链式存储的物理存储单元不一定是连续的，所以除了需要存储元素本身的信息外，还需要存储其后继元素的地址信息，以此保证线性表中元素之间的逻辑关系。因此每个结点包括两个域：数据域和指针域，由于链表的指针域只有一个故称为单链表。每个指针指向后继元素的存储位置，当头节点的指针域为NULL时，链表为空。

![SouthEast][]![SouthEast 1][]

单链表的实现代码：[学生信息操作系统][Link 1]

## 2、循环单链表 ##

将单链表的最后一个元素的指针指向头结点就成了循环单链表，循环单链表为空时head->next = head。

![SouthEast 2][]![SouthEast 3][]

循环单链表的实现代码：[约瑟夫环问题][Link 2]

## 3、双向链表 ##

双向链表的每个结点都有两个指针域，一个指向前驱元素的存储地址，一个指向后继元素的存储地址。最后一个元素的next指针指向头结点，而头结点的prior指针指向最后一个元素。判断双向链表为空的条件是head->next = head或者head->prior = head。

> ![SouthEast 4][]
> 
> 双向链表的实现代码：[双向链表实现][Link 3]

## 4、静态链表 ##

单链表、循环链表、双向链表都是通过malloc和free函数分配和释放结点的，成为动态链表，而像java这种语言就不支持指针类型，因此有大牛就提出了静态链表的想法，来实现动态链表的功能。

静态链表使用一维数组描述，用游标来模拟指针，即使用游标来模拟指针的作用用来指向后继元素,游标的值表示后继元素的数组下标，并且用来存储数据的一维数组的首位不存放元素。

> ![SouthEast 5][]
> 
> 静态链表的实现代码：[JAVA实现静态链表][JAVA]

[SouthEast]: https://img-blog.csdn.net/20170410131711844?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXFfMjk3MjE0MTk=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 1]: /images/20220617/79ea6da9d0c44197bc217356f01f5987.png
[Link 1]: http://blog.csdn.net/qq_29721419/article/details/69665069
[SouthEast 2]: https://img-blog.csdn.net/20170410132943642?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXFfMjk3MjE0MTk=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 3]: /images/20220617/570c5121fd314f9fb6afd4dfad10399e.png
[Link 2]: http://blog.csdn.net/qq_29721419/article/details/69666723
[SouthEast 4]: /images/20220617/1740d9e0d527451c9ba7c7740c56206d.png
[Link 3]: http://blog.csdn.net/qq_29721419/article/details/69992157
[SouthEast 5]: /images/20220617/6aa096710bc84d298d0133bb3d82a962.png
[JAVA]: http://blog.csdn.net/qq_29721419/article/details/70038099