欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

表、栈、队列

程序员文章站 2022-05-23 11:08:03
...

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;
}