表、栈、队列

1. 表 List

1.1 List ADT
struct Node;
typedef struct Node* PtrToNode;
typedef PtrToNode List;		// 通常用一个节点来代表一个空表
typedef PtrToNode Position;
typedef int ElementType;

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);
void DeleteList(List L);

struct Node
{
	ElementType Element;
	Position Next;
};

1.1.1 创建与测试空表
int IsEmpty( List L )
{
	return L->Next == NULL;
}

1.1.2 测试当前位置是否链表的末尾
int IsLast( Position P, List L )
{
	return P->Next == NULL;
}

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

1.1.4 查找前驱节点
Position FindPrevous(ElementType X, List L)
{
	Position P;
	P = L;
	while ( P->Next!=NULL && P->Next->Element!=X )
		P = P->Next;
	return P;
}

1.1.5 删除元素
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( P );
	}
}

1.1.6 插入
void Insert(ElementType X, List L, Position P) // 在P的后面插入
{
	Position TmpCell = malloc( sizeof(struct Node) );
	if(NULL == TmpCell) return;
	TmpCell->Element = X;
	TmpCell->Next = P->Next;
	P->Next = TmpCell;
}

1.1.7 删除链表
void DeleteList(List L)
{
	Position P, Tmp;
	P = L->Next;
	L->Next = NULL;
	while (P)
	{
		Tmp = P->Next;
		free(P);
		P = Tmp;
	}
}

2. 堆栈

数据对象集: 一个有0个或多个元素的有穷线性表, 具有LIFO性质

操作集
Stack CreateStack(int MaxSize);//生成空堆栈,其最大长度为MaxSize
int IsFull(Stack S, int MaxSize); // 判断堆栈S是否已满
void Push(Stack S, ElementType item); // 将元素Item压入堆栈
int IsEmpty(Stack S); // 判断堆栈S是否为空
ElementType Pop(Stack S); // 删除并返回栈顶元素

2.1 栈的顺序存储实现
通常由一个一维数组和一个记录栈顶元素位置的变量组成
typedef struct SNode* Stack;
struct SNode
{
	ElementType Data[MaxSize];
	int top;
}

2.1.1 入栈
void Push( Stack S, ElementType item )
{
	if( S->Top == MaxSize-1 ){
		Error("Full");
	}
	else{
		S->Data[++(S->Top)] = item;
	}
}

2.1.2 出栈
ElementType Pop( Stack S )
{
	if( S->Top == -1 ){
		return ERROR;
	}else{
		return (S->Data[(S->Top)--]);
	}
}

2.2 堆栈的链式存储实现
栈的链式存储结构实际上就是一个单链表,叫做链栈。插入和删除操作只能在链栈的栈顶进行，栈顶在表头一侧。
typedef struct SNode* Stack;
struct SNode{
	ElementType Data;
	strtuct SNode* Next;
}

2.2.1 创建
Stack CreateStack()
{
	Stack S;
	S = (Stack)malloc(sizeof(struct SNode));
	S->Next = NULL;
	return S;
}
2.2.2 判空
int IsEmpty( Stack S )
{
	return ( S->Next == NULL );
}
2.2.3 Push
void Push( ElementType item, Stack )
{
	struct SNode* TmpCell;
	TmpCell = (struct SNode*)malloc( sizeof(struct SNode) );
	TmpCell->Next = S->Next;
	TmpCell->Next = S->Next;
	S->Next = TmpCell;
}
2.2.4 Pop
ElementType Pop(Stack S)
{
	struct SNode* FirstCell;
	ElementType TopElem;
	if ( IsEmpty( S ) ){
		return ERROR;
	}else{
		FirstCell = S->Next;
		S->Next = FirstCell->Next;
		TopElem = FirstCell->Element;
		free(FirstCell);
		return TopElem;
	}
}

3. 队列 Queue

只能在一端插入另一端删除，具有FIFO性质。
数据对象集: 一个有0个或多个元素的有穷线性表

ADT
Queue CreateQueue( int MaxSize ); // 生成长度为MaxSize的空队列
int IsFull( Queue Q, int MaxSize ); // Q是否已满
void AddQ( Queue Q, ElementType item ); // 将元素item插入队列Q中
int IsEmptyQ( Queue Q ); // 队列是否为空
ElementType DeleteQ( Queue Q ); // 将队头元素从队列中删除并返回

3.1 队列的顺序存储实现
struct QNode{
	ElementType Data[MaxSize];
	int rear;	// 队为
	int front; // 队头
}
typedef struct QNode* Queue;

逻辑上实现循环队列的操作
int IsFull( Queue Q, int MaxSize )
{// 加1取余, 循环利用空间
	return ( (Q->rear+1) % MaxSize == Q->front );
}

void AddQ( Queue Q, ElementType item)
{
	if ( IsFull(Q) ) return;
	Q->rerar = (Q->rear+1) % MaxSize;
	Q->Data[Q->rear] = item;
}

int IsEmptyQ( Queue Q )
{
	return ( Q->front == Q->rear );
}
ElementType DeleteQ( Queue Q )
{
	if ( IsEmpty() ) return ERROR;
	Q->front = (Q->front+1) % MaxSize;
	return Q->Data[Q->front];
}


3.2 队列的链式存储实现
队列的链式存储结构也可以用一个单链表实现。插入和删除操作分别在链表两头进行。队头在表头,队尾在表尾。
struct Node{
	ElementType Data;
	struct Node* Next;
}
typedef struct Node* Position;
struct QNode{ /*队列结构*/
	Position rear; /*指向队尾节点*/
	Position front;/*指向队头节点*/
	int MaxSize; /*队的最大容量*/
};
typedef struct QNode* Queue;

// 判空
int IsEmpty( Queue Q )
{
	return ( Q->front == NULL );
}
// 出队
ElementType DeleteQ( Queue Q )
{
	Position FrontCell;
	ElementType FrontElem;
	if ( IsEmpty( Q ) )
		return ERROR;
	FrontCell = Q->front;
	if( Q->front == Q->rear ) /*若队列只有一个元素*/
		Q->front = Q->rear = NULL; /*删除队列后为空*/
	else
		Q->front = Q->front->Next;
	FrontElem = FrontCell->Data;

	free( FrontCell );
	return;
}