数学和计算机科学板块_辛酸网

数据结构与算法3

BY TSherry

链表

线性表的另一种储存方式就是链式存储下次的链表。不同于顺序表，链表中的每一个元素或者说结点在物理上一般都是隔开的。我可以说一个结点a在其位置&a处（这里的&是C语言里的取地址符），另一个结点b在其位置&b处。也需逻辑上a和b就是挨着的，a后面紧跟着b，但&a+sizeof(a)≠&b。如果你知道一个结点的地址，你是不能通过算术运算得到后面所有结点的地址的，也就不可能以算术的方式找到后面所有的结点。所以每一个结点的位置都必须写在一个地方，我们读取那个地方就知道了后面元素的地址，例如，你可以写在其它的结点处。链表也是分种类的，就最简单的单链表而言，一般的，后一个元素的地址写在前一个结点的内部。这样，当你找到前一个结点时，你可以从该结点内的记录读出下一个结点在哪里，就此实现从前往后的遍历。只不过最后一个结点因为没有更靠后的了，其下一个结点指针就为空，也就是NULL。
下面是C语言中，针对单链表最简单的结点定义：

typedef struct{
	DataType v;
	node* next;
}node;

现在想象一下，有这么个空教室，每个桌子上面都有一张纸。首先，我告诉你张三的座位在哪里，你去对应的桌子一看，那张纸条上写着：“猥琐”二字，再细看，下面有一行小字“下一个：第x行y列”。于是你跑过去到指定位置一看，发觉这是李四的座位，桌子上有“可爱”二字，下面有行小字“下一个：第m行n列”。你又跑过去看。就这样，只要我把纸条上的内容安排得合理，再告诉你当一个人的座位在哪里，你就能知道这个班级里所有学生的特点。只是在最后一个人的纸条上，那行小字写的是“下一个，没了。”

首尾指针

为了方便，我们能设两个指针，一个头指针front，一个尾指针，分别指向链表的首尾。可是在上图所示的单链表里，如果这个链表是空的，也就是一个实际的元素有没有，会发生什么？你怎么知道这个链表是空的呢？显然是front为空的时候。其实学术界和业界一般不这么搞，出于管理方面的考虑，人们会专门设置一个头结点，front指向的是头结点，而头结点自身不具备自身的值，只是会以其next指向链表要实际存储的元素中最前面的那个。而尾指针rear一般就是指向最后一个元素。这时，若链表内只有一个元素则front->next和rear都指向这个元素；若链表是空的，则至少还有头结点，此时front->next==NULL，而front和rear都会指向头结点。故这种链表的判空条件为front==rear。

建立链表

链表的建立有两种情况，一种是按照结点的逻辑顺序，一个一个建立结点，然后将之前最靠后的结点，其next指向它，rear滑过去，曰尾插法；另一种是按照结点逻辑顺序的相反顺序，先做好最后一个结点，让头结点指向它，然后反过来将前面的结点插入在头结点和头结点的next所直接指向的结点之间，曰首插法。无论是那种方法，都需要先拥有头结点。

链表操作

如图，在链表中有指针p指向一个元素，p之后还有一个元素，我们要在二者之间插入一个元素，用q指向。如果我们先让p->next=q，那么q->next指向什么呢？插入元素时不能让后面的结点都丢失掉。所以最好先获取后面那个元素的地址，即q->next=p->next，然后p->next=q，此时从p所指元素的next，原本的向后的箭头就被覆盖了。只是你也能提前设置另一个指针变量记下那个元素的地址，就不怕上述问题，只是多消耗了内存。注意，内存分配有动态和静态的两种，静态分配是程序正式运行前甚至编译时就定下来的，而动态分配则是执行相应的指令才临时开辟出来，且即使是在局部，当局部的复合语句或是函数等结束后，无专门的指令，这片内存也不会释放。动态开辟内存在C语言中一般是用malloc函数，而C++中多为new关键字。内存释放在C语言中一般是free函数，而C++中多为delete关键字。

删除元素时，你可获取被删元素的前一个元素之地址，用next套next赋值一下就行了。例如有指针p指向一个元素，现在需要删去该元素的下一个元素，一句p->next=p->next->next就完事。只是为了节省内存，最好先执行q=p->next，然后释放被删结点所占内存，free(q)。由此我们可以发现，当给定要插入或删除之元素，附近的元素地址时，只需要短短几句指令，而不需要让其它大量元素发生移动。因为链表是利用指针跳着存储的，插入删除其实就是改变了指针的关系而已。所以链表的插入删除非常快，顶多在寻找附近元素时费点劲。但反过来，要查找和修改的话，由于我们一般不会在一开始就知道那么多指针的值，所以为了找到对应元素我们只好遍历整个链表，这就浪费了时间。因此，在线性表的存储中，需要多次大量插入删除的就用链表，否则就是顺序表。

双向和循环链表

双向链表就是每一个结点除了有一个next指向下一个元素外，还有一个指针指向前一个元素。循环链表就是最后一个结点的next指向最前面的结点（多为头结点）。这二者的操作和上面的略有不同但是并不复杂，无非多费点内存，多处理几个箭头。