5. 数据结构与算法分析学习笔记¶
Data Structures and Algorithm Analysis in C Second Edition
（美）Mark Allen Weiss 著 冯舜玺 译
原书第2版 机械工业出版2004.1（2016年10月第1版第32次印刷）
5.1. 第1章 引论¶
5.2. 第2章 算法分析¶
5.3. 第3章 表、栈和队列¶
5.3.1. 抽象数据类型¶
程序模块化
程序—模块（module）
抽象数据类型（abstract data type ADT）是一些操作的集合。
5.3.2. 表 ADT¶
空表 empty list
Ai+1后续Ai;
Ai-1（i<N）前驱Ai（i>1）;
5.3.2.1. 表的简单数组实现¶
5.3.2.2. 链表¶
链表 linked list
每一个结构（结构体）均含有表元素和指向包含该元素后继元的结构的指针。next指针，最后一个单元的next指针指向null；
指针变量就是包含存储另外某个数据的地址的变量。
5.3.2.3. 程序设计细节¶
增加标志结点
表头 header 或哑结点 dummy node
#ifndef _List_H
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
List MakeEmpty( List L );
int IsEmpty( List L );
int IsLast( Position P, List L );
Position Find( ElemenType X, List L );
void Delete( ElemenType X,List L );
Position FindPrevious( ElemenType X,List L );
void Insert( ElemenType X,List L, Position P );
void DeleteList( List L );
Position Header( List L );
Position First( List L );
Position Advance( Position P );
ElemenType Retrieve( Position P );
#endif /* _List_H*/
/* Place in the implementation file */
struct Node
{
ElemenType Element;
Position Next;
};
链表的类型声明
/* 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( ElemenType X, List L )
{
Position P;
/* 1*/ P = L->Next;
/* 2*/ while( P != NULL && P->Element != X )
/* 3*/ P = P->Next;
/*4 */ return P;
}
Find 例程
/* Delete first occurrence of X from a list */
/* Assume use of a header node */
void
Delete( ElemenType X,List L )
{
Position P, TmpCell;
P = FindPrevious( X,L );
if( !IsLast( P,L )) /*Assumption of header use */
{ /*X is found; delete it */
TmpCell = P->Next;
P->Next = TmpCell->Next; /* Bypass delete cell */
free( TmpCell );
}
}
链表的删除例程
/* If X is not found,then Next field of return */
/* Position is NULL */
/* Assumes a header */
Position
FindPrevious( ElemenType X, List L )
{
Position P;
/* 1*/ P = L;
/* 2*/ while( P->Next != NULL && P->Next->Element != X )
/* 3*/ P = P->Next;
/* 4*/ return P;
}
FindPrevious—为与Delete 一起使用的Find例程
/* Insert (after legal position P */
/* Header implementation assumed */
/* Parameter L is unused in this implementation*/
void
Insert(ElemenType X, List L, Position P )
{
Position TmpCell;
/* 1*/ TmpCell = malloc( sizeof( struct Node ));
/* 2*/ if( TmpCell == NULL )
/* 3*/ FatalError( "Out of space!!!");
/* 4*/ TmpCell->Element = X;
/* 5*/ TmpCell-Next = P->Next;
/* 6*/ P->Next = TmpCell;
/* */
}
链表的插入例程