十大购物网站排行榜,苏州三石网络科技有限公司,河南专业网站建设公司首选,苏州建设网站的公司目录
栈
基本概念
栈的常见基本操作
栈的存储 ✌栈的基本操作实现
栈的构建
栈的初始化
入栈
打印栈
出栈
获取栈顶元素 获取栈的有效元素个数
判断栈是否为空 销毁栈 队列
基本概念
队列的常见基本操作
✌队列的基本操作实现
队列的构建
初始化
入队列
出…
目录
栈
基本概念
栈的常见基本操作
栈的存储 ✌栈的基本操作实现
栈的构建
栈的初始化
入栈
打印栈
出栈
获取栈顶元素 获取栈的有效元素个数
判断栈是否为空 销毁栈 队列
基本概念
队列的常见基本操作
✌队列的基本操作实现
队列的构建
初始化
入队列
出队列 获取头部元素
获取队尾元素
获取有效元素个数
判断是否为空
销毁队列 栈
基本概念 定义 是只允许在一端进行插入或删除的线性表 栈顶线性表允许进行插入删除的那一端。空栈不含任何元素的空表。 栈是先进后出的的线性表 栈的常见基本操作 InitStack(S) 初始化一个空栈S。StackEmpty(S) 判断一个栈是否为空若栈为空则返回true否则返回false。Push(S, x) 进栈栈的插入操作若栈S未满则将x加入使之成为新栈顶。Pop(S, x) 出栈栈的删除操作若栈S非空则弹出栈顶元素并用x返回。GetTop(S, x) 读栈顶元素若栈S非空则用x返回栈顶元素。DestroyStack(S) 栈销毁并释放S占用的存储空间“”表示引用调用。 栈的存储 栈的存储方式有两种顺序栈和链栈即栈的顺序存储和链式存储。 采用顺序存储的栈称为顺序栈它利用一组地址连续的存储单元存放自栈底到栈顶的元素同时附设一个指针top指示当前栈顶的位置。 ✌栈的基本操作实现
栈的构建 因为使用的是顺序栈所以可以定义动态增长的数组既然是数组了自然有空间是否足够的问题所以要定义个容量 capacity栈顶top // 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* arr; int top; // 栈顶int capacity; // 容量
}Stack;
栈的初始化 这里的top可以定义成0或者-1不过后面的操作需要稍微变化 // 初始化栈
void StackInit(Stack* ps)
{assert(ps);assert(ps);ps-arr NULL;ps-capacity 0;ps-top -1; //表示栈顶元素
}
入栈 这里注意top的不同因为是顺序栈所以要检查容量是否足够 // 入栈
void StackPush(Stack* ps, STDataType data)
{//检查容量if (ps-top 1 ps-capacity) //top表示的是栈顶元素先top,再插入的所以检查1位置是否可用{int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* newnode (STDataType*)realloc(ps-arr,sizeof(STDataType) * newcapacity);assert(newnode); //七匹狼式检查是否开辟成功ps-arr newnode;ps-capacity newcapacity;}ps-top;ps-arr[ps-top] data;
}
打印栈
//打印
void StackPrint(Stack* ps)
{assert(ps);int i ps-top;while (i0){printf(%d , ps-arr[i]);i--;}printf(\n);
}
出栈
// 出栈
void StackPop(Stack* ps)
{assert(ps);assert(ps-top 0);ps-top--;
}
获取栈顶元素
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);assert(ps-top 0);return ps-arr[ps-top];
} 获取栈的有效元素个数
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);assert(ps-top 0);return ps-top 1;
}
判断栈是否为空
// 检测栈是否为空如果为空返回非零结果如果不为空返回0
bool StackEmpty(Stack* ps)
{assert(ps);if (ps-top 0) //为空{return true;}else{return false;}
}销毁栈
// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps);ps-capacity 0;ps-top -1;free(ps-arr);ps-arr NULL;
} 队列
基本概念
定义队列queue是只允许在一端进行插入操作而在另一端进行删除操作的线性表。 队列是一种先进先出First In First Out的线性表简称FIFO。允许插入的一端称为队尾允许删除的一端称为队头。 队列的常见基本操作 InitQueue(Q) 初始化队列构造一个空队列Q。QueueEmpty(Q) 判队列空若队列Q为空返回true否则返回false。EnQueue(Q, x) 入队若队列Q未满将x加入使之成为新的队尾。DeQueue(Q, x) 出队若队列Q非空删除队头元素并用x返回。GetHead(Q, x) 读队头元素若队列Q非空则将队头元素赋值给x。 ✌队列的基本操作实现
队列的构建
typedef int QueueDataType;
// 链式结构表示队列
typedef struct QueueNode
{QueueDataType val;struct QueueNode* next;
}QNode;// 队列的结构
typedef struct Queue
{QNode* head;QNode* tail;int size; //队列的长度大小
}Queue;
初始化
// 初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq-head NULL;pq-tail NULL;pq-size 0;
}
入队列
// 队尾入队列
void QueuePush(Queue* pq, QueueDataType data)
{assert(pq);//开辟空间QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL) //检查是否开辟成功{perror(malloc fail);return;}newnode-val data;newnode-next NULL;if (pq-tail NULL) //空队列情况{pq-tail pq-head newnode; }else{pq-tail-next newnode; //链接新结点pq-tail newnode; //队尾 更新位置}pq-size; //长度
}
出队列
// 队头出队列
void QueuePop(Queue* pq)
{assert(pq);QNode* tmp pq-head;pq-head pq-head-next;free(tmp);tmp NULL;if (pq-head NULL) //此时链表已经为空队尾tail是野指针{pq-tail NULL;}pq-size--;
} 获取头部元素
// 获取队列头部元素
QueueDataType QueueFront(Queue* pq)
{assert(pq);assert(pq-head); //检查队头不为空说明有数据存放return pq-head-val;
}
获取队尾元素
// 获取队列队尾元素
QueueDataType QueueBack(Queue* pq)
{assert(pq);assert(pq-tail); //检查队尾不为空说明有数据存放return pq-tail-val;
}
获取有效元素个数
// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}
判断是否为空
// 检测队列是否为空如果为空返回非零结果如果非空返回0
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-head NULL;
}
销毁队列
// 销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* tmp pq-head;while (tmp){QNode* next tmp-next;free(tmp);tmp NULL;tmp next;}pq-head pq-tail NULL;pq-size 0;
}
