手机门户网站建设,网页设计与制作项目教程黑马程序员,网站建设_,网络推广网站怎么做 目录
编辑 一、栈
1.1栈的概念及结构
1.2栈的实现
1、实现支持动态增长的栈
2、初始化栈
3、入栈
4、出栈
5、获取栈顶元素
6、检测栈是否为空
7、获取栈中有效元素个数
8、销毁栈
9、测试
1.3源码
二、队列
2.1队列的概念及结构… 目录
编辑 一、栈
1.1栈的概念及结构
1.2栈的实现
1、实现支持动态增长的栈
2、初始化栈
3、入栈
4、出栈
5、获取栈顶元素
6、检测栈是否为空
7、获取栈中有效元素个数
8、销毁栈
9、测试
1.3源码
二、队列
2.1队列的概念及结构
2.2队列的实现
1、链式结构表示队列
2、队列的结构
3、初始化队列
4、队尾入队列
5、队头出队列
6、获取队列队头元素
7、获取队列队尾元素
8、获取队列中有效元素个数
9、检测队列是否为空
10、销毁队列
11、测试
2.3源码 一、栈
1.1栈的概念及结构 栈是一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。出栈栈的删除操作叫做出栈出数据也在栈顶。 1.2栈的实现 栈的实现一般可以使用数组或者链表实现 对于链表而言又有双向链表和单链表如果用双向链表实现栈顶既可以是尾也可以是头。如果用单链表实现栈顶只能是头因为单链表尾插容易尾删却比较麻烦而头插头删都很容易。相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。 1、实现支持动态增长的栈
typedef int STDataType;typedef struct stack
{STDataType* arr;int top; //栈顶int capacity; //容量
}ST;
2、初始化栈 因为这个结构体肯定不可能为空所以我们直接先断言它。然后这里还有一个要特别注意的点如果我们初始化时top给0那top指向的就是栈顶元素的下一个位置如果top给-1那top就指向栈顶元素。 void STInit(ST* pst)
{assert(pst);pst-arr NULL;pst-capacity 0;//表示top指向栈顶元素的下一个位置pst-top 0;表示top指向栈顶元素//pst-top -1;
}
3、入栈 入栈时如果空间不够先扩容因为top此时是指向栈顶元素的下一个位置所以我们直接将要入栈的元素x放在top位置然后让top指向下一个位置就行。 void STPush(ST* pst, STDataType x)
{assert(pst);//扩容if (pst-top pst-capacity){int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* tmp (STDataType*)realloc(pst-arr, sizeof(STDataType) * newcapacity);if (tmp NULL){perror(realloc fail);return;}pst-arr tmp;pst-capacity newcapacity;}pst-arr[pst-top] x;pst-top;//如果top初始化时为-1入栈时就要top先再将元素放进去//pst-top;//pst-arr[pst-top] x;
}
4、出栈 在出栈时要注意如果top为0就不能在删除了所以要断言一下。 void STPop(ST* pst)
{assert(pst);assert(pst-top 0);pst-top--;
}
5、获取栈顶元素 因为top是指向栈顶元素的下一个位置所以要获取栈顶元素只需要top-1就行。 STDataType STTop(ST* pst)
{assert(pst);assert(pst-top 0);return pst-arr[pst-top - 1];
}
6、检测栈是否为空 如果栈为空那top就等于0表达式的结果就为真如果表达式的结果为假就代表栈不为空。 bool STEmpty(ST* pst)
{assert(pst);return pst-top 0;
}
7、获取栈中有效元素个数
int STSize(ST* pst)
{assert(pst);return pst-top;
}
8、销毁栈
void STDestroy(ST* pst)
{assert(pst);free(pst-arr);pst-arr NULL;pst-top pst-capacity 0;
}
9、测试
int main()
{ST s;STInit(s);STPush(s, 1);STPush(s, 2);STPush(s, 3);STPush(s, 4);STPush(s, 5);while (!STEmpty(s)){printf(%d , STTop(s));STPop(s);}printf(\n);STDestroy(s);return 0;
} 1.3源码 Stack.h #include stdio.h
#include assert.h
#include stdlib.h
#include stdbool.htypedef int STDataType;typedef struct stack
{STDataType* arr;int top; //栈顶int capacity; //容量
}ST;//初始化
void STInit(ST* pst);
//销毁栈
void STDestroy(ST* pst);
//入栈
void STPush(ST* pst, STDataType x);
//出栈
void STPop(ST* pst);
//获取栈顶元素
STDataType STTop(ST* pst);
//检测栈是否为空如果为空返回真如果不为空返回假
bool STEmpty(ST* pst);
//获取栈中有效元素个数
int STSize(ST* pst); Stack.c #include stack.h//初始化
void STInit(ST* pst)
{assert(pst);pst-arr NULL;pst-capacity 0;//表示top指向栈顶元素的下一个位置pst-top 0;//表示top指向栈顶元素//pst-top -1;
}//销毁栈
void STDestroy(ST* pst)
{assert(pst);free(pst-arr);pst-arr NULL;pst-top pst-capacity 0;
}//入栈
void STPush(ST* pst, STDataType x)
{assert(pst);//扩容if (pst-top pst-capacity){int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* tmp (STDataType*)realloc(pst-arr, sizeof(STDataType) * newcapacity);if (tmp NULL){perror(realloc fail);return;}pst-arr tmp;pst-capacity newcapacity;}//如果top初始化时为0入栈时就要先将元素放进去再将toppst-arr[pst-top] x;pst-top;//如果top初始化时为-1入栈时就要top先再将元素放进去//pst-top;//pst-arr[pst-top] x;
}//出栈
void STPop(ST* pst)
{assert(pst);assert(pst-top 0);pst-top--;
}//获取栈顶元素
STDataType STTop(ST* pst)
{assert(pst);assert(pst-top 0);return pst-arr[pst-top - 1];
}//检测栈是否为空如果为空返回真如果不为空返回假
bool STEmpty(ST* pst)
{assert(pst);return pst-top 0;
}//获取栈中有效元素个数
int STSize(ST* pst)
{assert(pst);return pst-top;
}
二、队列
2.1队列的概念及结构 队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出 FIFO(First In First Out)的特点。 入队列进行插入操作的一端称为队尾出队列进行删除操作的一端称为队头 2.2队列的实现 队列也可以数组和链表的结构实现但使用链表的结构实现会更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低。 1、链式结构表示队列
typedef int QDataType;//链式结构表示队列
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;2、队列的结构 因为队列需要队头和队尾两个指针所以为了方便管理我们可以把它俩放在一个结构体里边。 typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;
3、初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq-phead pq-ptail NULL;pq-size 0;
}
4、队尾入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-val x;newnode-next NULL;if (pq-ptail NULL){pq-ptail pq-phead newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}5、队头出队列 出队时得考虑两种情况一种是队列为空另一种是队列中只有一个节点如果队列为空我们只需断言一下就行。如果队列中只有一个节点我们先保存当前节点然后让头指针指向下一个节点接着free掉保存的节点这时如果头指针是指向空的我们就把尾指针也置空。 void QueuePop(Queue* pq)
{assert(pq);//空assert(pq-phead);QNode* del pq-phead;pq-phead pq-phead-next;free(del);del NULL;if (pq-phead NULL){pq-ptail NULL;}pq-size--;
}
6、获取队列队头元素
QDataType QueueFront(Queue* pq)
{assert(pq);//空assert(pq-phead);return pq-phead-val;
}
7、获取队列队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);//空assert(pq-ptail);return pq-ptail-val;
}
8、获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}
9、检测队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead NULL;
}10、销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}
11、测试
int main()
{Queue q;QueueInit(q);QueuePush(q, 1);QueuePush(q, 2);QueuePush(q, 3);QueuePush(q, 4);QueuePush(q, 5);while (!QueueEmpty(q)){printf(%d , QueueFront(q));QueuePop(q);}printf(\n);QueueDestroy(q);return 0;
} 2.3源码 Queue.h #include stdio.h
#include assert.h
#include stdlib.h
#include stdbool.htypedef int QDataType;//链式结构表示队列
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;//队列的结构
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;//初始化队列
void QueueInit(Queue* pq);
//队尾入队列
void QueuePush(Queue* pq, QDataType x);
//队头出队列
void QueuePop(Queue* pq);
//获取队列队头元素
QDataType QueueFront(Queue* pq);
//获取队列队尾元素
QDataType QueueBack(Queue* pq);
//获取队列中有效元素个数
int QueueSize(Queue* pq);
//检测队列是否为空
bool QueueEmpty(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq); Queue.c #include queue.h//初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq-phead pq-ptail NULL;pq-size 0;
}//队尾入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-val x;newnode-next NULL;if (pq-ptail NULL){pq-ptail pq-phead newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}//队头出队列
void QueuePop(Queue* pq)
{assert(pq);//空assert(pq-phead);QNode* del pq-phead;pq-phead pq-phead-next;free(del);del NULL;if (pq-phead NULL){pq-ptail NULL;}pq-size--;
}//获取队列队头元素
QDataType QueueFront(Queue* pq)
{assert(pq);//空assert(pq-phead);return pq-phead-val;
}//获取队列队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);//空assert(pq-ptail);return pq-ptail-val;
}//获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}//检测队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead NULL;
}//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}
