NOIP高中信息技术竞赛资料 - -数据结构(3)

第2章 线性表

图2(a)是执行Insert运算之前的情况。我们要在指针p所指的单元之后插入一个新元素x。图2(b)是执行Insert运算以后的结果，其中的虚线表示新的指针。在上述Insert算法中，位置变量p指向单链表中一个合法位置，要插入的新元素x应紧接在p所指单元的后面。指针p的合法性应在执行Insert运算之前判定。往一个单链表中插入新元素通常在表头或表尾进行，因此p的合法性容易判定。Insert运算所需的时间显然为O(1)。

(2)Delete(p)

功能:从表L中删除位置p的下一元素。例如，当L为a1,a2,…,an时，执行Delete(p)后，L变为a1,a2,…,ap-1,ap+1,…,an 。当L中没有位置p或p=End(L)时，该运算无定义。实现:p.next=p.next.next;

这个过程很简单，其指针的修改如图3所示。

若要从一个表中删除一个元素x，但不知道它在表中的位置，则应先用Locate(x,L)找出指示要删除的元素的位置，然后再用Delete删除该位置指示的元素。Delete过程所需的时间显然也为O(1)。

2.静态链表 静态链表：用游标指示数组单元地址的下标值，它属整数类型数组元素是记录类型，记录中包含一个表元素和一个作为游标的整数；具体说明如下:

type jid=record

data:datatype; next:integer; end;

var alist=array[0..maxsize] of jid

游标即我们可以用游标来模拟指针, 对于一个表L，我们用一个整型变量Lhead(如Lhead=0)作为L的表头游标。。这样，我们就可以用游标来模拟指针，实现单链表中的各种运算。当i>1时，表示第i个位置的位置变量pi的值是数组alist中存储表L的第i-1个元素next值,用p:=alist(p).next后移。照此，我们虽然是用数组来存储表中的元素，但在作表的插人和删除运算时，不需要移动元素，只要修改游标，从而保持了用指针实现表的优点。因此，有时也将这种用游标实

第2章 线性表

现的表称为静态链表。

3.循环链表

循环链表是另一种链式存储结构，特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。因此，可由表中任一结点出发均可找到表中其他结点。如图6所示的是一个单链的循环链表或简称为单循环链表。 (a)非空表

(b)空表

图6单循环链表

在单循环链表上实现表的各种运算的算法与单链表的情形是类似的。它们仅在循环终止条件上有所不同:前者是p或p^.next指向表头单元；后者是p或p^.next指向空(nil)。在单链表中我们用指向表头单元的指针表示一个表L，这样就可以在O(1)时间内找到表L中的第一个元素。然而要找到表L中最后一个元素就要花O(n)时间遍历整个链表。在单循环链表中，我们也可以用指向表头单元的指针表示一个表L。但是，如果我们用指向表尾的指针表示一个表L时，我们就可以在O(1)时间内找到表上中最后一个元素。同时通过表尾单元中指向表头单元的指针，我们也可以在O(1)时间内找到表L中的第一个元素。在许多情况下，用这种表示方法可以简化一些关于表的运算。

4.双链表

单循环链表中，只有一个指示直接后继的指针域，虽然从任一单元出发，可以找到其前驱单元，但需要O(n)时间。如果我们希望能快速确定表中任一元素的前驱和后继元素所在的单元，可以在链表的每个单元中设置两个指针，一个指向后继，另一个指向前驱，形成图8所示的双向链表或简称为双链表。

图8 双链表

由于在双链表中可以直接确定一个单元的前驱单元和后继单元，我们可以用一种更自然的方式表示元素的位置，即用指向双链表中第i个单元而不是指向其前一个单元的指针来表示表的第i个位置。

双链表的单元类型定义如下。

第2章 线性表

和单链的循环表类似，双链表也可以有相应的循环表。我们用一个表头单元将双链表首尾相接，即将表头单元中的previous指针指向表尾，并将表尾单元的next指针指向表头单元，构成如图9所示的双向循环链表。

图9 双向循环链表

下面仅以双向循环链表为例给出三种基本运算的实现。

(1)在双向循环链表L的位置p处插入一个新元素x的过程Insert可实现如下。

上述算法对链表指针的修改情况见图10。

图10 在双向循环链表中插入一个元素

算法Insert中没有检查位置p的合法性，因此在调用Insert之前应保证位置p的合法性。由于插入通常是在表的头尾两端进行的，所以容易检查位置p的合法性。

第2章 线性表

(2)从双向循环链表L中删除位置p处的元素可实现如下:

上述算法对链表指针的修改情况见图11。

图11 从双向循环链表中删除一个元素

5.链表的应用

例1：求 (A-B)U(B-A)其中A,B代表两个集合（用静态链表） 例2 求p1(x)+p2(x) (两个多项式的和） 练习题：

1.约瑟夫问题:

有M个猴子围成一圈，每个有一个编号，编号从1到M。打算从中选出一个大王。经过协商，决定选大王的规则如下：从第一个开始，每隔N个，数到的猴子出圈，最后剩下来的就是大王。

要求：从键盘输入M，N，编程计算哪一个编号的猴子成为大王。(程序） 2.求多项式的减与乘法.(程序）

第3章 栈

第3章 栈

栈是一种特殊的线性表，它的逻辑结构与线性表相同，只是其运算规则较线性表有更多的限制，故又称它为运算受限的线性表。

3.1 栈的概念及运算

栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。向栈中插入元素称为进（入）栈，从栈中删除元素称为退（出）栈。

通常插入、删除的这一端称为栈顶，由于元素的进栈和退栈，使得栈顶的位置经常是变动的，因此需要用一个整型量Top指示栈顶的位置，通常称Top 为栈顶指针；另一端称为栈底。

当表中没有元素时称为空栈，即Top=-1。

栈的修改是按后进先出的原则进行。每次删除的总是当前栈中“最新”的元素，即最后插入的元素，而最先插入的是被放在栈的底部，要到最后才能删除。。

假设一个栈S中的元素为an,an-1,..,a1，则称a1为栈底元素，an为栈顶元素。栈中的元素按a1 ,a2,..,an-1,an的次序进栈。在任何时候，出栈的元素都是栈顶元素。换句话说，栈的修改是按后进先出的原则进行的，如图1所示。因此，栈又称为后进先出(Last In First Out)表，简称为LIFO表。所以，只要问题满足LIFO原则，就可以使用栈。

图1

栈的运算：为一种抽象数据类型，常用的栈运算有: 运算 含义 inistack(S) 使S成为一个空栈。 getTop(S) 这是一个函数，函数值为S中的栈顶元素。 Pop(S) 从栈S中删除栈顶元素，简称为抛栈。 Push(S,x) 在S的栈顶插入元素x，简称为将元素x入栈。

这是一个函数。当S为空栈时，函数值为true，

Empty(S)

否则函数值为false。

3.2 栈的存储与实现

1.顺序栈及基本操作的实现

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库NOIP高中信息技术竞赛资料 - -数据结构(3)在线全文阅读。