基础的表ADT

表的概述

  • 形如A1,A2,A3…
  • 操作合集
    1. PrintList
    2. MakeEmpty
    3. Find
    4. Insert
    5. Delete

表的简单数组实现

分析:

  • PrintList和Find操作线性时间
  • Find操作常数时间
  • Insert和Delete操作效率低下

    所以一般不用数组实现

链表的指针实现

设计思路

  • 在内存中不必相连
  • 每个结构包含表元素和指向该元素后继元的指针

    即实现了快速Insert和Delete操作

    实现代码

    类型声明

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    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) ;
    Positiom Find(ElementType X, List L) ;
    void Delete(ElementType X, List L) ;
    Position FindPrevios(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) ;

    struct Node
    {
    ElemenType Element ;
    Position Next ;
    }

测试是否为空表

1
2
3
4
int IsEmpty(List L)
{
return L->Next == NULL ;
}

测试是否为链表末尾

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

Find函数,寻找元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Position Find(List L,Element X)
{
Position P ;
P = L->Next ;
while(P->Element X != X && P != NULL)
P = P->Next ;

return P ;
}

//FindPrevious函数
Position FindPrevios(List L, Element X)
{
Position P ;
P = L ;
while(P->Next->Element != X && P->Next != NULL)
P = P->Next ;

return P ;
}

Delete函数,删除元素

1
2
3
4
5
6
7
8
9
10
11
void Delete(Element X, List L)
{
Position P ,TmpCell;
P = FindPrevious(L, X) ;
if(!IsLast(P,L)
{
TmpCell = P->Next ;
P->Next = TmpCell->Next ;
free(TmpCell) ;
}
}

Insert函数,插入元素

1
2
3
4
5
6
7
8
9
10
11
12
void Insert(Element X, List L, Position P)
{
Position TemCell ;
TemCell = malloc(sizeof(struct Node)) ;
if(TemCell = NULL)
{
printf("内存不足") ;
}
TmpCell->Element = X ;
TmpCell->Next = P->Next ;
P->Next = TmpCell ;
}

DeleteList函数,删除表

1
2
3
4
5
6
7
8
9
10
11
void DeleteList(List L)
{
Position P ,Tmp ;
P = L->Next ;
while(P != NULL)
{
Tmp = P->Next ;
free(P) ;
P = Tmp ;
}
}

双链表

  • 在结点结构中增加一个指向前一个结点的指针
  • 简化了删除操作,插入和删除的开销增加一倍

循环链表

  • 在双链表的基础上增加一个表尾指向表头和表头指向表尾的指针

十字链表

  • 可用数组实现,但浪费空间效率低下
  • 链表实现:每行每列都有一个表头指向该行该列

链表的游标实现

许多语言,如Java,并不支持指针,就可以游标(cursor)实现法

设计思路

  1. 全局结构体数组模拟指针法,对于数组的任何单元,其数组下标来代表一个地址
  2. 使用一个数组来模拟malloc和free
  3. 数组0管理着链表的空闲内存

类型声明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
typedef int PtrToNode ;
typedef PtrToNode List ;
typedef PtrToNode Position ;

//L为表头
//初始化
void InitializeCursorSpace(void)

//操作函数声明
List MakeEmpty(List L) ;
int IsEmpty(List L) ;
int IsLast(Position P, List L) ;
Positiom Find(ElementType X, List L) ;
void Delete(ElementType X, List L) ;
Position FindPrevios(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) ;

struct Node
{
ElemenType Element ;
Position Next ;
}

struct Node CursorSpace[Spacesize] ;

游标法中的malloc和free函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Position CursorAlloc(void)
{
Position P ;
P = CursorSpace[0].Next ;
CursorSpace[0].Next = CursorSpace[P].Next ;

return P ;
}

void CursorFree(Position P)
{
CursorSpace[P].Next = CursorSpace[0].Next ;
CursorSpace[0].Next = P ;
}

初始化

1
2
3
4
5
6
7
8
9
void InitializeCursorSpace(Void)
{
int i ;
for(i = 0;i < SpaceSize; i++)
{
CursorSpace[i].Next = i + 1;
}
CursorSpace[i] = 0 ;
}

判断链表是否为空和是否为末尾

1
2
3
4
5
6
7
8
9
int IsEmpty(List L) //L为表头,CursorSpace数组为全局变量
{
return CursorSpace[L].Next == 0 ;
}

int IsLast(Position P)
{
return CursorSpace[P].Next == 0;
}

Find函数 //游标实现

1
2
3
4
5
6
7
8
9
Position Find(Element X,List L)
{
Position P ;
P = CursorSpace[L].Next ;
while(P && CursorSpace[P] != X)
P = CursorSpace[P].Next ;

return P ;
}

Delete函数 //游标实现

1
2
3
4
5
6
7
8
9
10
11
void Delete(ElementType X, List L)
{
Position P, TmpCell ;
P = FindPrevious(X,L) ;
if(!IsLast(P))
{
TmpCell = CursorSpace[P].Next ;
CursorSpace[P].Next = CursorSpace[TmpCell].Next ;
CursorFree(TmpCell) ;
}
}

Insert函数 //游标实现

1
2
3
4
5
6
7
8
9
10
11
12
void Insert(Element X, List L, Position P)
{
Position TmpCell ;
TmpCell = CursorAlloc() ;
if(TmpCell == 0)
{
printf("链表数组空间不足") ;
}
CursorCell[TmpCell].Element = X ;
CursorCell[TmpCell].Next = CursorSpace[P].Next ;
CursorSpace[P].Next = TmpCell ;
}

总结

  • 表就是一种顺序结构
  • 支持查找删除插入等操作
  • 主要有两种常见的实现方法
    1. 指针法
    2. 游标法
  • 有最基本的链表,还有双链表,循环链表,十字链表。比较特殊的有栈和队列。(下一篇)
  • 应用:
    1. 多项式计算 //链表
    2. 学生选课系统 //十字链表