链式存储结构：数据结构第二章详解

数据结构-链式存储结构 链式存储结构是一种常见的数据存储方式，它可以用来存储线性表的数据元素。在链式存储结构中，每个数据元素都被存储在一个独立的存储单元中，这些存储单元可以是连续的，也可以是不连续的，甚至是零散的分布在内存的任意位置上的。 链式存储结构的特点是链表中元素的逻辑次序与物理次序不一定相同。为了表示数据元素之间的逻辑关系，可以在存储自己内容的同时也存储下一个元素的地址。存储数据元素的域称为数据域，存储直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。 链式存储结构的基本组成部分是结点(Node)，它由数据域和指针域组成。n个结点(ai(1≤i≤n)的存储映象链结成一个链表，即为线性表。把链表中第1个结点的存储位置叫头指针。最后一个元素意味着没有直接后继规定最后一个结点指针为空(通常用NULL或^表示)。 链式存储结构有多种类型，如单链表、双链表、循环链表等。单链表是一种最简单的链式存储结构，它由一个头结点和多个数据结点组成。头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息，头结点的指针域存储指向线性表第1个元素的结点。 单链表的优点是可以方便地对链表进行操作，如插入、删除等操作。单链表也可以用头指针名字来命名。讨论1：如何表示空表？讨论2：在链表中设置头结点有什么好处？①有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其它结点的操作就统一了②便于空表和非空表的统一处理。 链式存储结构的其他类型还有双链表、循环链表等。双链表是一种链式存储结构，它在每个结点中都存储了前一个元素和后一个元素的地址。循环链表是一种特殊的链式存储结构，它的最后一个结点的指针域指向头结点，从而形成一个环形结构。 链式存储结构是一种灵活的数据存储方式，它可以用来存储线性表的数据元素。链式存储结构的优点是可以方便地对链表进行操作，如插入、删除等操作。但是，链式存储结构也存在一些缺点，如查询速度较慢等。 小结： * 链式存储结构是一种灵活的数据存储方式。 * 链式存储结构可以用来存储线性表的数据元素。 * 链式存储结构的特点是链表中元素的逻辑次序与物理次序不一定相同。 * 链式存储结构有多种类型，如单链表、双链表、循环链表等。 总结： 链式存储结构是一种常见的数据存储方式，它可以用来存储线性表的数据元素。链式存储结构的优点是可以方便地对链表进行操作，如插入、删除等操作。但是，链式存储结构也存在一些缺点，如查询速度较慢等。链式存储结构是一种灵活的数据存储方式，它可以满足不同的应用需求。