• 3.1 抽象数据类型(Abstract Data Type，ADT)
• 3.2 表(List)ADT
  • 3.2.1 表的简单数组实现
  • 3.2.2 链表(linked list)
  • 3.2.3 程序设计细节
  • 3.2.5 双链表(doubly linked list)
  • 3.2.6 循环链表(circular linked list)
  • 3.2.7 例子
  • 3.2.8 链表的游标(cursor)实现

3.1 抽象数据类型(Abstract Data Type，ADT)

模块(module)化程序设计：每个模块是一个逻辑单位并执行某个特定的任务，它通过调用其他模块而使本身保持很小。（程序设计基本法则之一——例程不应超过一页）
抽象数据类型是一些操作的集合。对于集合ADT，我们可以有并(union)、交(intersection)、求大小(size)以及取余(complement)等操作。或者也可以只要两种操作——并和查找(find)，这两种操作又在该集合上定义了一种不同的ADT。

3.2 表(List)ADT

我们将处理形如\(A_1，A_2，A_3，…，A_N\)的普通表，其大小为\(N\)。

空表(empty list)：大小为0的表

我们称\(A_i\)后继\(A_{i-1}\)，前驱\(A_{i+1}\)。(\(1<i<N\))
\(A_1\)的前驱元与\(A_N\)的后继元不被定义。
元素\(A_i\)在表中的位置为\(i\)。

一些常见操作：PrintList，MakeEmpty，Find，Insert，Delete，FindKth，Next，Previous……

3.2.1 表的简单数组实现

对于表大小未知或表很大的情况，一般不用简单数组来实现表。(插入和删除费用昂贵)

PrintList、Find：\(O(N)\)
FindKth：\(O(1)\)
Insert、Delete：\(O(N)\)

3.2.2 链表(linked list)

为了避免插入和删除的线性开销，链表由一系列不必在内存中相连的结构组成。每一个结构均含有表元素和指向包含该元素后继元的指针(Next指针)。最后一个单元的Next指针指向NULL；该值由C定义并且不能与其他指针混淆。ANSI C规定NULL为零。

PrintList、Find：\(O(N)\)
FindKth：\(O(N)\)（多个FindKth指令也只需遍历一次链表）
Insert：一次malloc调用+两次指针调整
Delete：修改一个指针（需要记住被删除元素前驱元）

3.2.3 程序设计细节

• 为解决无法从起始端插入或删除的问题，引入表头(header)或哑节点(dummy node)的概念。
  

链表的类型声明：

#ifndef _List_H

struct Node;
typedef struct Node *PtrToNode;
typedef struct PtrToNode List;
typedef struct PtrToNode Position;

List MakeEmpty( List L );
int IsEmpty( List L );
int IsLast( Position P, List L );
Position Find( ElementType X, List L );
void Delete( ElementType X, List L );
Position FindPrevious( ElementType X, List L );
void Insert( ElementType X, List L, Position P );
void DeleteList( List L );
Position Header( List L );
Position First( List L );
Position Advance( Position P );
ElementType Retrieve( Position P );

#endif /* _List_H */

/* Place in the implementation file */

struct Node
{
	ElementType Element;
	Position Next;
};

具体函数实现：

/* Make L empty */

List
MakeEmpty( List L )
{
	if( L != NULL )
		DeleteList( L );
	L = malloc( sizeof( struct Node ) );
	if( L == NULL )
		FatalError( "Out of memory!" );
	L->Next = NULL;
	return L;
}

/* Return true if L is empty */

int
IsEmpty( List L )
{
	return L->Next == NULL;
}

/* Return true if P is the last position in list L */
/* Parameter L is unused in this implementation */

int
IsLast( Position P, List L )
{
	return P->Next == NULL;
}

/* Return Position of X in L; NULL if not found */

Position
Find( ElementType X, List L )
{
	Position P;
	P = L->Next;
	while( P != NULL && P->Element != X)
		P = P->Next;
	return P;
}

/* Delete first occurrence of X from a list */
/* Assume use of a header node */

void Delete( ElementType X, List L )
{
	Position P, TmpCell;
	P = FindPrevious( X, L );
	if( !IsLast( P, L ) )
	{
		TmpCell = P->Next;
		P->Next = TmpCell->Next;
		free( TmpCell );
	｝
}

/* If X is not found, then Next field of returned */
/* Position is NULL */
/* Assumes a header */

Position
FindPrevious( ElementType X, List L )
{
	Position P;
	P = L;
	while( P->Next != NULL && P->Next->Element != X )
		P = P->Next;
	return P;
}

/* Insert (after legal position P) */
/* Header implementation assumed */
/* Parameter L is unused in this implementation */

void
Insert( ElementType X, List L, Position P)
{
	Position TmpCell;
	TmpCell = malloc( sizeof( struct Node ) );
	if( TmpCell == NULL )
		FatalError( "Out of space!!!" );
	TmpCell->Element = X;
	TmpCell->Next = P->Next;
	P->Next = TmpCell;
}

/* Delete L */

void
DeleteList( List L )
{
	Position P, Tmp;
	P = L->Next;
	L->Next = NULL;
	while( P != NULL )
	{
		Tmp = P->Next;
		free( P );
		P = Tmp;
	}
}

/* Return Header */

Position
Header( List L )
{
	return L;
}

/* Return first pointer */

Position
First( List L )
{
	return L->Next;
}

/* return next pointer */

Position
Advance( Position P )
{
	return P->Next;
}

/* return element */

ElementType
Retrieve( Position P )
{
	return P->Element;
}

3.2.5 双链表(doubly linked list)

多了附加的链的开销，增加了空间需求，使得插入和删除的开销增加一倍（双向指针都需要被修改）；但简化了删除操作（不必记忆前继元）。

3.2.6 循环链表(circular linked list)

让最后的单元反过来直指第一个单元。

3.2.7 例子

• 多项式ADT
• 基数排序(radix sort)/卡式排序(card sort)
• 多重表

3.2.8 链表的游标(cursor)实现

不使用指针的链表。