Go转型——数据结构初级（三）

**1**.链式线性表 从之前的例题来看，线性表的顺序存储结构如果需要插入和删除i（1<=i<=n）元素，需要移动大量元素，所以我们可以看一下线性表另一种表示方式——链式存储结构。它不要求逻辑上相邻的元素物理位置也相邻，因此，链式存储结构没有顺序线性表的缺点，同样，它也失去了顺序线性表可随机存储的优点。 线性链表的特点是，使用一组任意的存储单元存储线性表的数据元素（遮住存储单元可以是连续的，也可以是不连续的），因此为了表示数据元素a(i)和其直接后继元素a(i+1)之间的逻辑关系，对于数据元素a(i)来说，除了要保存自身存储的数据信息，还需要存储一个指示其直接后继的信息（即直接后继的存储位置），这两部分结合起来组成数据元素a(i)的存储映像，称为**结点**。它包含两个域，其中，包含自身存储的数据信息的域叫做数据域，包含直接后继的存储信息的域叫做**指针域**。指针域中存储的信息叫做指针或链。 n个结点（a(i)的存储映像（1<=i<=n））连接成链表。即为线性表的链式结构，又因为一个结点中只包含一个指针域，故又称为线性链表或单链表。  用线性链表表示线性表时，数据元素之间的逻辑关系是有结点中的指针指示的。换句话说，指针为数据元素之间的逻辑关系的映像。则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻，由此，这种存储结构为**非顺序映像**或**链式映像**。  由上述可见，单链表可由头指针唯一指定，上述单链表头指针为H，它指向表中第一个结点，若H为“空”(L=NULL)，所表示的线性表为“空”表，其长度n为“零”。有时，我们在单链表的第一个结点之前附设一个结点，称之为头结点。头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等累的附加信息，头结点的指针域存储指向第一个数据元素的指针（即第一个元素节点的存储位置）。如下图所示：  在线性表的顺序存储结构中，由于逻辑上相邻的两个元素在物理位置上也相邻，所以任何元素的存储位置都可以从线性表的起始位置计算得到。但是在单链表中，任意两个元素存储位置之间没有固定的联系。然而，每个元素的存储位置都包含在它直接前驱结点的信息中心。例如，P是指向线性表中第i个数据元素a（i）的指针，则P->Next是第i+1个数据元素（结点a（i+1））的指针。换句话说，如果P->Data=a(i)，那么P->Next->Data=a（i+1）。因此在单链表中，取得第i个数据元素必须从头指针出发寻找。因此，单链表是非随机存取的存储结构。  **2**.链式表的插入删除  为插入数据元素X，首先要生成数据域为x的结点，然后插入在单链表中，我们需要修改a的指针域，令其指向结点x。而x中的指针域应指向结点b，从而实现3个元素之间的逻辑变化。假设s为指向结点x的指针，则上面指针修改可以用语句概括： `s ->next=p->next; p->next = s` 还是以上图为例，我们添加数据元素X后，又想把他删除，我们应该怎么做？答案是，我们只需修改结点a的指针域，令其指向b即可，语句概括为： `p->next=p ->next->next` 链式线性表插入、删除实现如下如所示：    **3**.线性链表的合并 将两个有序列表合并为一个有序列表，例如，我们现在有头指针为La和Lb的单链表分别为有序线性表LA和LB的存储结构，现在将LA和LB合并得到LC。我们应该怎么做。 **4**.静态链表的操作 我们可借用一维数组来描述链表，其类型如下说明：   这种方法适用于没有指针类型的高级编程语言中使用链表，数组中一个分量可以看作是一个结点，第零**分量**可以看作是头结点。我们用游标（也就是指示器cur）来代替指针指示结点在数组中的相对位置，插入和删除操作如下图所示。我们可以看到，这种存储方式要预先分配一个很大的空间，但在做线性表的插入删除时，不需要移动元素，仅需要修改指针（这里的指针指得是游标）。它仍然具有链式存储结构的优点，为了区分指针类型表述的线性链表，我们将其称为**静态链表**。