声明:此一系列博客为阅读《数据结构与算法分析--C语言描述》(Mark Allen Weiss)笔记,部分内容参考自网络;转载请注明出处。
1、表
表是最简单的数据结构,是形如A1、A2、A3、A4、...、AN的表,表的大小为N。大小为0的表为空表。
2、表的简单数组实现
对表的所有操作都可以通过使用数组来实现。但是数组实现的表有两个缺点:(1)需要对表大小的最大值进行估计,通常需要估计的大一些,因此会浪费大量的空间;(2)、插入和删除操作是昂贵的。这个是显而易见的,当插入Ai时,i到N的所有元素都需要往后移动一个位置以空出空间来存放Ai,因此这两种操作最坏的情况为O(N)。所以,简单数组一般不用来实现表。
3、链表
链表由一系列不必在内存中连续的结构组成,每一个结构均含有表元素和指向本元素后继元的结构的指针,称之为Next指针。这样,就可以允许表可以不连续存储,从而避免了插入和删除的线性开销。表的示意图如下:
删除命令可以通过修改一个指针来实现,比如上图,要删除A2,只需要修改A1指向A2的指针,将其直接指向A3即可;插入命令需要使用一次malloc操作得到一个新的结构。比如要在A2和A3之间插入一个新结构X,则先申请X的内存,让A2的Next指针指向X,X的Next指针指向A3即可。以下为具体的程序实现细节。在程序实现时,有别于上图的是,有一个表头,它没有具体的数据,只有一个指针,指向第一个数据单元。
首先,在.h文件中给出需要的声明
#ifndef _LIST_H
#define _LIST_H struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position; List MakeEmpty(List L);
int IsEmpty(List L);
int IsLast(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); #endif
各个函数的作用由其命名即可清晰的看出。
下面是各个函数的实现,都比较简单
/* 首先是具体的Node节点的定义*/
struct Node
{
ElementType Element;
Position Next;
}; /* Return true if L is empty */ int IsEmpty(List L)
{
return (L->Next == NULL);
} /* Return True if p is last position in list L*/
/* Parameter L is unused in this implemention*/
/* 参数L在这个实现中并没有使用,写在这里,作者的意图应该是易于以后的扩展*/
int IsLast(Position P, List L)
{
return (P->Next == NULL);
}
Find 函数返回元素X所在的Node的指针;FindPrevious 返回X的前驱元的指针
/* Return postion 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;
} /* NULL if not found */
Position FindPrevious(ElementType X, List L)
{
Position P; P = L;
while(P->Next != NULL && P->Next->Element != X)
P = P->Next; if(P->Next == NULL)
return NULL; return P;
}
Delete 函数删除表中的元素X,这里规定,例程删除第一次出现的X,如果X不再表中,就什么都不做。
/*Delete first occurrence of X from a list */ void Delete(ElementType X, List L)
{
Position P, TmpCell; P = FindPrevious(X, L);
if(P != NULL)
{
TmpCell = P->Next;
P ->Next = TmpCell->Next;
Free(TmpCell);
} }
Insert函数实现将X插入链表中。书中的实现方法传入了一个位置,供X插入。在这里,我将X插入到表中第一个元素位置,即表头后的一个位置
/* Insert X into List*/ void Insert(ElementType X, List L)
{
Position TmpCell; TmpCell = malloc(sizeof(Struct Node));
if(TmpCell == NULL)
return; TmpCell->Element = X;
TmpCell->Next = L->Next;
L->Next = TmpCell;
}
DeleteList 函数删除链表
/*这个程序不同于书中的程序,此处删除了表头;书中的程序保留了表头*/ void DeleteList(List L)
{
Position P; while(L != NULL)
{
P = L;
L = L->Next;
free(P);
}
}
4、双链表/循环列表
双链表的实现非常简单,即在结构体中添加一个指针域,指向该单元的前一个单元即可。它可以非常简单的实现表的倒序扫描。同时,它简化了删除操作,因为你不在需要获得前驱单元的指针,这个信息是现成的。
循环列表让最后的单元反过来指向的一个单元,可以有表头,也可以没有表头。