数据结构与算法分析表ADT

表：连续存储；链表：非连续存储，为了避免插入和删除的线性开销；

1.链表的声明：

 1 #ifndef _List_H
 2 struct Node;
 3 typedef struct Node *PtrToNode;
 4 typedef PtrToNode List;
 5 typedrf PtrToNode  Position;
 6 
 7 List MakeEmpty(List L);
 8 int IsEmpty(List L);
 9 int IsLast(Position P,List L);
10 Position Find(ElementType X,List L);
11 .
12 .
13 .
14 .
15 .
16 .
17 #endif
18 
19 struct Node
20 {
21 　　ElementType Element;
22 　　Position Next;
23 }

2.测试一个链表是否是空表

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

3.测试当前位置是否是链表的末尾函数

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

4.查找函数

1 Position Find(ElemetType X,List L)
2 {
3   Position P;
4   P=L->Next;
5   while(P!=NULL&&P->Element!=X)
6   　　P=P->Next;
7 　　return P;        
8 }

5.删除函数

 1 void Delete(ElementType X,List L)
 2 {
 3 　　Position P,TemCell;
 4　　 P=FindPrevious(X,L);
 5 　　if(!IsLast(P,L))
 6 　　{
 7 　　　　TemCell =P->Next;
 8 　　　　P->Next=TemCell->Next;
 9 　　　　free(TemCell);
10 　　}
11 }
12 
13 Position FindPrevious(ElementType X,List L)
14 {
15 　　Position P;
16 　　P=L;
17 　　while(P->Next!=NULL&&P->Next->Element!=X)
18 　　　　P=P->Next;
19 　　return P;
20 }

6.插入函数

 1 void Insert(ElementType X,List L,Position P)
 2 {
 3 　　PositionTemCell;
 4 　　TemCell=malloc(sizeof(struct Node));
 5 　　if(TemCell==NULL)
 6　　　　 FatalError("Out of space!!!");
 7 　　TemCell->Element=X;
 8 　　TemCell->Next=P->Next;
 9 　　P->Next=TemCell;
10 }

7.删除表

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