数据结构之线性表

全文概要

线性表实现有两种方式，一种为顺序表，另一种为链表。本文分别介绍了顺序线性表、单向链表、双向链表和循环链表的基本结构，并给出了相应的C++类代码实现。

线性表(Linear List)

顺序表(Sequential List)

在顺序实现中，数据存储在一个长度为maxSize，数据类型为ElemType的数组中，并用count记录在数组中的线性表的实际元素个数。由于顺序表本质是个数组，故其中逻辑位置连续的结点，其物理存储空间也连续。

顺序表的类声明及定义如下：

单链表(Linked List)

单链表是一种最简单的线性表的链式存储结构，单链表也称为线性链表，用它来存储线性表时，每个数据元素用一个结点(node)来存储，一个结点由两个域组成，一个是存放数据元素的val，称为数据域，一个是存储指向此链表下一个结点的指针next，称为指针域。

单链表结点的类声明及定义如下：

单链表在表头通常会增加一个没有存储数据元素的结点，称之为”头结点“，在单链表中增加头结点虽然增加了存储空间，但算法实现更简单，效率更高。头结点的地址可从指针head找到，指针head也称为”头指针“，其它结点的地址则由其前驱结点的next域得到。

单链表用结点中的指针域来表示数据元素之间的逻辑关系，这样逻辑上相邻的两个元素并不要求物理存储位置也相邻。即在链表中，逻辑位置连续的结点，物理存储空间不必连续

简单线性链表(Simple Linked List)

线性链表简单实现为数据成员只有头指针。

简单线性链表的类声明及定义如下：

线性链表(Link List)

单链表简单实现基础上增加了表示当前位置的序号curPosition，指向当前位置的指针curPtr，以及元素总个数count。

线性链表的类声明及定义如下：

双向链表(Double Linked List)

前面介绍的单链表的结点结构中只有一个指向后继的指针域，即next，这样便只能从左往右进行查找其它结点，如要查找前驱，则只有从表头出发进行查找，效率较低，双向链表通过在其结点结构中存储两个指针域back和next，分别指向该结点前驱和后继。

双向链表结点的类声明及定义如下：

简单双向链表(Simple Double Linked List)

简单双向链表的类声明及定义如下：

双向链表(Double Linked List)

在双向链表简单实现基础上增加了表示当前位置的序号curPosition，指向当前位置的指针curPtr，以及元素总个数count。

双向链表的类声明及定义如下：

循环链表(Circular Linked List)

循环链表是另一种形式的线性表链式存储结构，它的结点结构与普通单链表相同，不同的是在循环链表中尾结点的next域不为空，而是指向起头结点，这样就将单链表首尾相接成为一个环。故而，循环链表判空的条件为：head->next == head。

简单循环链表(Simple Circular Linked List)

简单循环链表的类声明及定义如下：

循环链表(Circur Linked List)

在循环链表简单实现基础上增加了表示当前位置的序号curPosition，指向当前位置的指针curPtr，以及元素总个数count。

循环链表的类声明及定义如下：

参考资料

[1]数据结构与算法(C++版) - 唐宁九主编 [2]数据结构(用面向对象方法与C++语言描述) - 殷人昆主编