学习笔记 C语言数据结构

发布日期: 2021-05-17

更新日期: 2021-05-19

文章字数: 2.8k

阅读次数:

作者: LightningMaster

C语言实现堆栈和队列

堆栈实现（顺序结构）

base称为栈底指针，在顺序栈中，它始终指向栈底的位置，若base的值为NULL，则表明栈结构不存在。

top称为栈顶指针，其初值指向栈底，即top=base可作为栈空的标记。每当插入新的栈顶元素时，指针top增1；删除栈顶元素时，指针top减1，因此，非空栈中的栈顶指针始终在栈顶元素的下一个位置上。

栈顶指针和栈中元素之间地关系

定义堆栈

#define stack_maxSize 100    // 存储空间初始分配量
#define stack_increment 10    // 存储空间分配增量

typedef struct
{
	int* base;    // 栈底
	int* top;    // 栈顶
	int stackMaxSize;    // 当前已分配地存储空间
}SqStack;

初始化堆栈

/*创建堆栈*/
void Inistack(SqStack& S)
{
	S.base = (int*)malloc(stack_maxSize * sizeof(int));    // 分配空间
	if (!S.base)
		exit(0);
	S.top = S.base;
	S.stackMaxSize = stack_maxSize;
}

判断堆栈是否为空

/*判断堆栈是否为空*/
int isStackEmpty(SqStack S)
{
	if (S.base == S.top)
		return 0;
	else
		return 1;
}

取栈顶元素

/*取栈顶元素*/
int getTop(SqStack S)
{
	/*判断非空*/
	if (!isStackEmpty(S))
		return 0;
	return *(S.top - 1);
}

压入堆栈

/*压入堆栈*/
void push_Stack(SqStack& S, int e)
{
	if (S.top - S.base >= S.stackMaxSize)
	{
		int* temp = (int*)realloc(S.base, (S.stackMaxSize + stack_increment) * sizeof(int));
		if (!temp)
			exit(0);
		S.base = temp;
		S.top = S.base + S.stackMaxSize;
		S.base += stack_increment;
	}
	*S.top++ = e;
}

弹出栈顶元素

/*弹出栈顶元素*/
int pop_stack(SqStack& S)
{
	int temp;
	if (!isStackEmpty(S))
		return 0;
	temp = *--S.top;
	return temp;
}

清空栈元素，不释放空间

/*清空堆栈元素，不释放空间*/
void clear_stack(SqStack& S)
{
	if (!isStackEmpty(S))
		return ;
	S.top = S.base;
	printf("清空完成！\n");
}

打印堆栈内容

/*打印堆栈内容*/
void show_stack(SqStack S)
{
	if (!isStackEmpty(S))
		return;
	while (S.top != S.base)
	{
		printf("%d\t", *--S.top);
	}
	printf("\n");
}

返回堆栈元素个数

/*返回堆栈元素个数*/
int show_NumOfStack(SqStack S)
{
	return (S.top - S.base);
}

销毁堆栈，释放空间

/*销毁堆栈，释放空间*/
void destroy_stack(SqStack& S)
{
	if (S.base)
	{
		free(S.base);
		S.base = S.top = NULL;
		printf("销毁成功！\n");
	}
	else
		printf("销毁失败！\n");
}

完整代码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<malloc.h>
#include <stdlib.h>


#define stack_maxSize 100
#define stack_increment 10


typedef struct
{
	int* base;
	int* top;
	int stackMaxSize;
}SqStack;


/*创建堆栈*/
void Inistack(SqStack& S)
{
	S.base = (int*)malloc(stack_maxSize * sizeof(int));
	if (!S.base)
		exit(0);
	S.top = S.base;
	S.stackMaxSize = stack_maxSize;
}


/*判断堆栈是否为空*/
int isStackEmpty(SqStack S)
{
	if (S.base == S.top)
		return 0;
	else
		return 1;
}


/*取栈顶元素*/
int getTop(SqStack S)
{
	/*判断非空*/
	if (!isStackEmpty(S))
		return 0;
	return *(S.top - 1);
}


/*压入堆栈*/
void push_Stack(SqStack& S, int e)
{
	if (S.top - S.base >= S.stackMaxSize)
	{
		int* temp = (int*)realloc(S.base, (S.stackMaxSize + stack_increment) * sizeof(int));
		if (!temp)
			exit(0);
		S.base = temp;
		S.top = S.base + S.stackMaxSize;
		S.base += stack_increment;
	}
	*S.top++ = e;
}


/*弹出栈顶元素*/
int pop_stack(SqStack& S)
{
	int temp;
	if (!isStackEmpty(S))
		return 0;
	temp = *--S.top;
	return temp;
}


/*清空堆栈元素，不释放空间*/
void clear_stack(SqStack& S)
{
	if (!isStackEmpty(S))
		return ;
	S.top = S.base;
	printf("清空完成！\n");
}


/*打印堆栈内容*/
void show_stack(SqStack S)
{
	if (!isStackEmpty(S))
		return;
	while (S.top != S.base)
	{
		printf("%d\t", *--S.top);
	}
	printf("\n");
}


/*返回堆栈元素个数*/
int show_NumOfStack(SqStack S)
{
	return (S.top - S.base);
}


/*销毁堆栈，释放空间*/
void destroy_stack(SqStack& S)
{
	if (S.base)
	{
		free(S.base);
		S.base = S.top = NULL;
		printf("销毁成功！\n");
	}
	else
		printf("销毁失败！\n");
}


int main()
{
	SqStack myStack;
	Inistack(myStack);
	for (int i = 0; i < 10; i++)
	{
		push_Stack(myStack, i);
	}
	show_stack(myStack);
	for (int i = 0; i < 10; i++)
	{
		push_Stack(myStack, i);
	}
	show_stack(myStack);
	destroy_stack(myStack);
	show_stack(myStack);
	return 0;
}

堆栈实现（链式结构）

定义

typedef struct StackNode
{
	int data;
	struct StackNode* next;
}StackNode, *LinkStack;

初始化

/*初始化*/
void InitStack(LinkStack& S)
{
	S = NULL;
}

判断非空

/*判断是否为空*/
int isEmpty(LinkStack S)
{
	if (S == NULL)
		return 0;
	return 1;
}

进栈

/*进栈*/
void pushStack(LinkStack& S, int x)
{
	StackNode* p = new StackNode;
	p->data = x;
	p->next = S;
	S = p;
}

出栈

/*出栈*/
int popStack(LinkStack& S)
{
	if (!isEmpty(S))
		exit(0);
	StackNode* p = new StackNode;
	int x = S->data;
	p = S;
	S = S->next;
	delete p;
	return x;
}

取栈顶元素

/*取栈顶元素*/
int getTop(LinkStack S)
{
	if (!isEmpty(S))
		exit(0);
	return S->data;
}

打印

/*打印*/
void showStack(LinkStack S)
{
	if (!isEmpty(S))
		exit(0);
	StackNode* p = new StackNode;
	p = S;
	while (p != NULL)
	{
		printf("%d\t", p->data);
		p = p->next;
	}
	printf("\n");
}

完整代码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<malloc.h>
#include <stdlib.h>


typedef struct StackNode
{
	int data;
	struct StackNode* next;
}StackNode, *LinkStack;


/*初始化*/
void InitStack(LinkStack& S)
{
	S = NULL;
}


/*判断是否为空*/
int isEmpty(LinkStack S)
{
	if (S == NULL)
		return 0;
	return 1;
}


/*进栈*/
void pushStack(LinkStack& S, int x)
{
	StackNode* p = new StackNode;
	p->data = x;
	p->next = S;
	S = p;
}


/*出栈*/
int popStack(LinkStack& S)
{
	if (!isEmpty(S))
		exit(0);
	StackNode* p = new StackNode;
	int x = S->data;
	p = S;
	S = S->next;
	delete p;
	return x;
}


/*取栈顶元素*/
int getTop(LinkStack S)
{
	if (!isEmpty(S))
		exit(0);
	return S->data;
}


/*打印*/
void showStack(LinkStack S)
{
	if (!isEmpty(S))
		exit(0);
	StackNode* p = new StackNode;
	p = S;
	while (p != NULL)
	{
		printf("%d\t", p->data);
		p = p->next;
	}
	printf("\n");
}


int main()
{
	LinkStack S;
	InitStack(S);
	for (int i = 0; i < 10; i++)
	{
		pushStack(S, i);
	}
	showStack(S);
	printf("%d\n", popStack(S));
	showStack(S);
	return 0;
}

队列实现（顺序结构）

循环队列

定义队列

#define mSize 5


typedef struct queue
{
	int front;    // 队头元素的前一单元的位置下标
	int rear;     // 队尾元素的位置下标
	int maxSize;  // 队列空间的最大容量
	int* element; // 队列元素的数组首地址
}Queue;

初始化队列

/*创建队列*/
void initQueue(Queue& Q)
{
	Q.maxSize = mSize;
	Q.element = (int*)malloc(sizeof(int) * mSize);
	Q.front = Q.rear = 0;
}

销毁队列，释放空间

/*销毁队列，释放空间*/
void destroy_Queue(Queue& Q)
{
	free(Q.element);
	Q.maxSize = -1;
	Q.front = Q.rear = -1;
}

清除队列

/*清除队列*/
void clear_queue(Queue& Q)
{
	Q.front = Q.rear = 0;
}

判断非空

/*判断非空*/
int isQueueEmpty(Queue Q)
{
	return Q.front == Q.rear;
}

判断已满

/*判断已满*/
int isQueueFull(Queue Q)
{
	return ((Q.rear + 1) % Q.maxSize == Q.front);
}

获取队头元素

/*获取队头元素*/
void getFront(Queue Q)
{
	if (isQueueEmpty(Q))
		exit(0);
	printf("%d\n", Q.element[(Q.front + 1) % Q.maxSize]);
}

队尾插入

/*队尾插入*/
void enQueueRear(Queue& Q, int temp)
{
	if (isQueueFull(Q))
		exit(0);
	Q.rear = (Q.rear + 1) % Q.maxSize;
	Q.element[Q.rear] = temp;
}

队头删除

/*队头删除*/
void deQueueFront(Queue& Q)
{
	if (isQueueEmpty(Q))
		exit(0);
	Q.front = (Q.front + 1) % Q.maxSize;
}

打印队列

/*打印队列*/
void show_Queue(Queue Q)
{
	int p = Q.front;
	while (p != Q.rear)
	{
		printf("%d\t", Q.element[++p]);
	}
	printf("\n");
}

完整代码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<malloc.h>
#include <stdlib.h>

#define mSize 5


typedef struct queue
{
	int front;
	int rear;
	int maxSize;
	int* element;
}Queue;


/*创建队列*/
void initQueue(Queue& Q)
{
	Q.maxSize = mSize;
	Q.element = (int*)malloc(sizeof(int) * mSize);
	Q.front = Q.rear = 0;
}


/*销毁队列，释放空间*/
void destroy_Queue(Queue& Q)
{
	free(Q.element);
	Q.maxSize = -1;
	Q.front = Q.rear = -1;
}


/*清除队列*/
void clear_queue(Queue& Q)
{
	Q.front = Q.rear = 0;
}


/*判断非空*/
int isQueueEmpty(Queue Q)
{
	return Q.front == Q.rear;
}


/*判断已满*/
int isQueueFull(Queue Q)
{
	return ((Q.rear + 1) % Q.maxSize == Q.front);
}


/*获取队头元素*/
void getFront(Queue Q)
{
	if (isQueueEmpty(Q))
		exit(0);
	printf("%d\n", Q.element[(Q.front + 1) % Q.maxSize]);
}


/*队尾插入*/
void enQueueRear(Queue& Q, int temp)
{
	if (isQueueFull(Q))
		exit(0);
	Q.rear = (Q.rear + 1) % Q.maxSize;
	Q.element[Q.rear] = temp;
}


/*队头删除*/
void deQueueFront(Queue& Q)
{
	if (isQueueEmpty(Q))
		exit(0);
	Q.front = (Q.front + 1) % Q.maxSize;
}


/*打印队列*/
void show_Queue(Queue Q)
{
	int p = Q.front;
	while (p != Q.rear)
	{
		printf("%d\t", Q.element[++p]);
	}
	printf("\n");
}


int main()
{
	Queue myQueue;
	initQueue(myQueue);
	for (int i = 0; i < 4; i++)
	{
		enQueueRear(myQueue, i);
	}
	show_Queue(myQueue);
	destroy_Queue(myQueue);
	show_Queue(myQueue);
	return 0;
}

队列实现（链式结构）

定义

typedef struct QNode
{
	int data;
	struct QNode* next;
}QNode, *QueuePtr;


typedef struct
{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;

初始化

/*初始化*/
void InitQueue(LinkQueue& Q)
{
	Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
	if (!Q.front)
		exit(0);
	Q.front->next = NULL;
}

判断是否为空

/*判断是否为空*/
int isEmpty(LinkQueue Q)
{
	return (Q.front == Q.rear);
}

销毁

/*销毁*/
void destroyQueue(LinkQueue& Q)
{
	if (isEmpty(Q))
		exit(0);
	while (Q.front)
	{
		Q.rear = Q.front->next;
		free(Q.front);
		Q.front = Q.rear;
	}
}

取队头元素

/*取队头元素*/
int getFront(LinkQueue Q)
{
	if (isEmpty(Q))
		exit(0);
	return Q.front->next->data;
}

入队

/*入队*/
void enQueue(LinkQueue& Q, int x)
{
	QNode* p = (QueuePtr)malloc(sizeof(QNode));
	if (!p)
		exit(0);
	p->data = x;
	p->next = NULL;
	Q.rear->next = p;
	Q.rear = p;
}

出队

/*出队*/
int deQueue(LinkQueue& Q)
{
	if (isEmpty(Q))
		exit(0);
	QNode* p = (QueuePtr)malloc(sizeof(QNode));
	p = Q.front->next;
	int x = p->data;
	Q.front->next = p->next;
	if (Q.rear == p)
		Q.rear = Q.front;
	free(p);
	return x;
}

打印

/*打印*/
void show_Queue(LinkQueue Q)
{
	if (isEmpty(Q))
		exit(0);
	QNode* p = (QueuePtr)malloc(sizeof(QNode));
	p = Q.front->next;
	while (p != NULL)
	{
		printf("%d\t", p->data);
		p = p->next;
	}
	printf("\n");
}

完整代码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<malloc.h>
#include <stdlib.h>


typedef struct QNode
{
	int data;
	struct QNode* next;
}QNode, *QueuePtr;


typedef struct
{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;


/*初始化*/
void InitQueue(LinkQueue& Q)
{
	Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
	if (!Q.front)
		exit(0);
	Q.front->next = NULL;
}


/*判断是否为空*/
int isEmpty(LinkQueue Q)
{
	return (Q.front == Q.rear);
}


/*销毁*/
void destroyQueue(LinkQueue& Q)
{
	if (isEmpty(Q))
		exit(0);
	while (Q.front)
	{
		Q.rear = Q.front->next;
		free(Q.front);
		Q.front = Q.rear;
	}
}


/*取队头元素*/
int getFront(LinkQueue Q)
{
	if (isEmpty(Q))
		exit(0);
	return Q.front->next->data;
}


/*入队*/
void enQueue(LinkQueue& Q, int x)
{
	QNode* p = (QueuePtr)malloc(sizeof(QNode));
	if (!p)
		exit(0);
	p->data = x;
	p->next = NULL;
	Q.rear->next = p;
	Q.rear = p;
}


/*出队*/
int deQueue(LinkQueue& Q)
{
	if (isEmpty(Q))
		exit(0);
	QNode* p = (QueuePtr)malloc(sizeof(QNode));
	p = Q.front->next;
	int x = p->data;
	Q.front->next = p->next;
	if (Q.rear == p)
		Q.rear = Q.front;
	free(p);
	return x;
}


/*打印*/
void show_Queue(LinkQueue Q)
{
	if (isEmpty(Q))
		exit(0);
	QNode* p = (QueuePtr)malloc(sizeof(QNode));
	p = Q.front->next;
	while (p != NULL)
	{
		printf("%d\t", p->data);
		p = p->next;
	}
	printf("\n");
}


int main()
{
	LinkQueue Q;
	InitQueue(Q);
	for (int i = 0; i < 10; i++)
	{
		enQueue(Q, i);
	}
	show_Queue(Q);
	printf("%d\n", deQueue(Q));
	show_Queue(Q);
	return 0;
}