英语原文共 18 页，剩余内容已隐藏，支付完成后下载完整资料
第二章
列表
列表，也可以称为序列，是将元素按照特定的线性顺序进行存储的容器，它是由所执行的操作决定的的。列表可支持的基本操作包括，检索元素，插入和移除指定位置的元素。栈和队列是特殊类型的列表，在它们中，插入和移除元素只能在序列的头部或序列的尾部进行。序列的基本实现可通过数组和链表的方式来得到。
2.1 列表的抽象数据类型（ADT）
列表是一个指定类型的零个或多个元素的序列。
a1, a2, . . . , an (n ge; 0)
n：列表的长度
a1:列表中的第一个元素
an:列表中的最后一个元素
n=0：空的列表
元素可以根据元素自己在列表中的位置进行线性排序。正如我们所说ai在ai 1之前的位置，ai 1跟随着ai 的位置，ai位于i的位置处。
让我们假定以下几项内容：
L ：型元件类型的对象的列表
X ：这种类型
P ：类型位置
END(L)：返回之后的位置的函数在列表L最后位置
定义以下操作：
- Insert (x, p, L)
在列表L的p位置上插入x元素
如果p=END(L),则在末尾插入x元素
如果L没有位置p，则结果为未定义
- Locate (x, L)
在L上返回x元素
返回END（L），如果x元素不存在的话
3. Retrieve (p, L)
在L上的位置p返回元素
如果p不存在或者p=END(L),则结果为未定义
4. Delete (p, L)
在L的位置p删除元素
当p= EN D（L）或者不存在，则结果为未定义
5. Next (p, L)
紧接着位置p返回位置
- Prev (p, L)
先于位置p返回位置
7. Makenull (L)
使L到成为一个空表，并返回位置EN D（L）
8. First (L)
返回L上的第一个位置
9.Printlist (L)
输出L的元素出现的顺序
2.1.1 使用列表抽象数据类型的程序
下面给出的程序是被用来实现列表抽象数据类型的独立的数据结构。这是面向对象的编程封装的概念下的一个例子。
目的：
去除列表中的所有重复的元素
已知：
1.表L的元素是指元素类型
2.函数same(X, Y)，其中，x和y是元素类型，若x和y的元素类型相同，则函数返回true，反之，则函数返回返回false
3. p和q的类型为位置
p：位于L的当前位置
q：向前移动并寻找相同的元素
在C语言中表达的伪代码：
{
p = first (L) ;
while (p! = end(L)) {
q = next(p, L) ;
while (q! = end(L)) {
if (same (retrieve (p,L), retrieve (q, L))))
delete (q,L);
else
q = next (q, L) ;
}
p = next (p, L) ;
}
}
2.2 列表的实现
列表有许多种可能的实现方法。常用的实现方法包括：
1.数组
2.指针（单链表和双向链表等）
3.光标（整数指针数组）
2.2.1 列表的数组实现
在这里，列表中的元素被存储在数组中（连续的）的单元内。
列表是由两个成员组成的结构：
成员1：一个由单元构成的数组
成员2：末端位置 – 记录列表中最后一个元素的位置
这些位置具有整数的类型，且它们的取值范围从0到最大长度-1
# define maxlength 1000
typedef int elementtype; /lowast; elements are integers lowast;/
typedef struct list–tag {
elementtype elements [maxlength];
int last;
} list–type;
end(L)
int end (list–type lowast;ℓp)
{
return (ℓp → last 1)
}
Insert (x, p,L)
void insert (elementtype x ; int p ; list–type lowast;ℓp) ;
{
int v; /lowast; running position lowast;/
if (ℓp → last gt;= maxlength–1)
error (“list is full”)
elseif ((p lt; 0) || (p gt; ℓp → last 1))
error (position does not exist)
else
for (q = ℓp → last ; q lt;= p, q--)
ℓp → elements [q 1] = ℓp → elements [q] ;
ℓp → last = ℓp → last 1 ;
ℓp → elements [p] = x
}
Delete (p, L)
void delete (int p ; list–type lowast;ℓp)
{
int q ; /lowast; running position lowast;/
if ((p gt; ℓp → last) || (p lt; 0))
error (“position does not exist”)
else /lowast; shift elements lowast;/ {
ℓp → last minus;minus; ;
for (q = p ; q lt;= ℓp → last; q )
ℓp → elements [q] = ℓp → elements [q 1]
}
}
图2.1 单链表
Locate (x, L)
int locate (element type lowast;x ; list–type lowast;ℓp)
{
int q ;
for (q = 0 ; q lt;= ℓp → last ; q )
if (ℓp → elements [q] = = x]
return (q) ;
return (ℓp → last 1) /lowast; if not found lowast;/
}
2.2.2 列表的指针实现
在这些列表的数组实现中：
1.我们必须使用内存中的连续空间存储列表元素
2.插入以及删除元素时必须要先移动列表元素
指针虽然克服了上述的局限，但是需要到用额外的空间来存储指针。
单链表的实现
一个元素为a1, a2, hellip;, an的列表如图2.1
在此我们约定：位置i代表一个指针，它指向一个单元，该单元内的指针指向包含元素ai的那个单元（i取值为1, 2, hellip; , N）。 即
- 位置1是指向列表头部的指针
图2.2 在单链表中插入元素
- END(L)是指向列表L的最后一个单元的指针
- 如果位置ai只是一个指向包含位置ai元素单元的指针，那么
- 位置1将表示列表头部的内存地址
- END(L)将会成为一个空指针
- Insert(X, P, L): 见图2.2
- Delete(X, L): 见图2.3
2.2.3 双向链表的实现
* 使搜索的效率提高一倍
* 需要和单元数量相等的额外指针(见图2.4)；因此，插入元素和删除元素时会更加耗时，因为涉及到这些指针的赋值。
图2.3 在单链表中删除元素
图2.4 双链表结构
2.3 栈
- 栈是一种特殊的列表，所有的元素插入和元素删除都在同一端进行，即栈顶。
- 栈ADT是List ADT的其中一个特例。它也被称为一个LIFO列表或者下推列表。
典型的堆栈ADT操作有以下几种：
1.makenull（S）创建一个新的空栈
2. top (S) 返回堆栈的顶部的元素。
与检索操作相同retrieve（first（S），S）
3. pop (S) 删除堆栈的顶部元件
与删除操作相同 deletes(first (S), S)
4. push (x, S) 在堆叠S的顶端插入元素x
与插入操作相同 Inserts(x, first (S), S)
5.empty (S) 如果S是空的，则返回真，否则将会返回假
堆栈是一种自然来实现的子程序或过程调用和递归的数据结构。
栈的实现：数组以及指针都可以使用。参见图2.5和2.6
图2.5：堆栈ADT的数组实现方式
图2.6：链表实现栈的ADT
堆栈指针的实现：下面的代码提供了用于执行堆栈操作的指针。参见图2.7和2.8的对单链栈的push以及pop操作。
typedef struct node-tag {
item-type info ;
struct node-tag lowast; next ;
} node-type ;
typedef struct stack-tag {
node-type lowast; top ;
} stack-type ;
stack-type stack ; /lowast; define a stack lowast;/
stack-type lowast; sp = amp; stack ; /lowast; pointer to stack lowast;/
node-type lowast;np ; /lowast;
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[152640]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
