如何建设淘宝客网站,seo专员招聘,wordpress 加入搜索,上海网站建设 报价一、栈(Stack)
1.栈的概念及其结构
栈是一种特殊的线性表#xff0c;在栈这个结构里#xff0c;越先存进去的数据越难取出来。 这个结构就像是一个只有一端有打开的容器#xff0c;越先放进去的球越在底部#xff0c;想要把底部的球拿出来#xff0c;就必须先把前面的求…一、栈(Stack)
1.栈的概念及其结构
栈是一种特殊的线性表在栈这个结构里越先存进去的数据越难取出来。 这个结构就像是一个只有一端有打开的容器越先放进去的球越在底部想要把底部的球拿出来就必须先把前面的求拿出来。像这种”先进后出“的结构就是栈。 对于栈来说我们只能在表尾进行插入或者删除表 2.栈的功能
栈的基本操作主要有栈的初始化、判空、判满、取栈顶元素、在栈顶进行插入和删除。在栈顶插入元素称为入栈在栈顶删除元素称为出栈。
我们常用栈这种数据结构实现深度搜索。
由于栈的特性我们只对栈顶进行取出元素或者是压入元素所以我们在实现栈的时候需要用一个top指针来指向栈顶元素的地址或者是栈顶元素后面的地址。
3.c语言代码模拟动态实现
Stack.h文件 这个文件用来声明功能函数以及栈结构体数据的定义。 #define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includestdlib.h
#includeassert.h
typedef int STDataType;
typedef struct Stack
{STDataType* _a;int _top; // 栈顶int _capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
//打印
void StackPrint(Stack* ps);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空如果为空返回非零结果如果不为空返回0
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
Stack.c文件 实现各种功能函数 #define _CRT_SECURE_NO_WARNINGS 1
#includeStack.h// 初始化栈
void StackInit(Stack* ps) {assert(ps);ps-_a NULL;ps-_capacity 0;ps-_top 0;
}// 销毁栈
void StackDestroy(Stack* ps) {assert(ps);free(ps-_a);ps-_a NULL;ps-_capacity 0;ps-_top 0;
}
// 入栈
void StackPush(Stack* ps, STDataType data) {assert(ps);if (ps-_top ps-_capacity) {STDataType* temp NULL;int newcap 0;if (ps-_capacity 0) {newcap 4;}else {newcap ps-_capacity * 2;}temp (STDataType*)realloc(ps-_a,sizeof(STDataType) * newcap);if (temp NULL) {perror(mallc:fail);}ps-_a temp;ps-_capacity newcap;}ps-_a[ps-_top] data;ps-_top;
}// 出栈
void StackPop(Stack* ps) {assert(psps-_top0);--ps-_top;//return ps-_a[--ps-_top];
}//打印
void StackPrint(Stack* ps) {assert(ps);printf(top%d cap%d\n, ps-_top, ps-_capacity);for (int i 0; i ps-_top; i) {printf(%d-, ps-_a[i]);}printf(\n);
}
// 获取栈顶元素
STDataType StackTop(Stack* ps) {assert(psps-_top0);return ps-_a[ps-_top - 1];
}
// 获取栈中有效元素个数
int StackSize(Stack* ps) {assert(ps);return ps-_top;
}
// 检测栈是否为空如果为空返回非零结果如果不为空返回0
int StackEmpty(Stack* ps) {assert(ps);return ps-_top 0;
}
test.c文件 测试栈的功能是否达到预期 #define _CRT_SECURE_NO_WARNINGS 1
#includeStack.hvoid test1() {Stack st;StackInit(st);StackPush(st, 1);StackPush(st, 2);StackPush(st, 3);StackPush(st, 4);StackPrint(st);printf(弹出栈顶元素\n);StackPop(st);StackPrint(st);int x StackTop(st);printf(获取栈顶元素 %d\n,x);StackPrint(st);printf(获取栈里有效元素个数 %d\n, StackSize(st));printf(栈是否为空%d\n, StackEmpty(st));StackDestroy(st);
}
int main() {test1();return 0;
}二、队列Queue
1、队列的概念及其结构 只在一端进行删除操作(出队)只在另一端进行添加操作入队--先进先出 这个结构就像是在模拟越先排队的人越先“打到饭”。理论上不允许插队 看上去像不像排队打饭的你呢
2.队列的功能 队列 的最主要用途是异步任务和通信两个方面 异步的思路主要用来缓解瞬间压力、耗时操作、并行任务等。 队列的基本功能是入队、出队、获得队列元素个数、判断队列是否为空等操作。
在算法中我们常用队列来实现广度优先遍历
3.c语言代码模拟
Queue.h文件 声明功能函数以及栈结构体数据的定义 #define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includestdlib.h
#includeassert.htypedef int QDataType;// 链式结构表示队列
typedef struct QListNode
{struct QListNode* _next;QDataType _data;
}QNode;// 队列的结构
typedef struct Queue
{QNode* _front;QNode* _rear;
}Queue;// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
//打印队列信息
void QueuePrint(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空如果为空返回非零结果如果非空返回0
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);
Queue.c文件 实现各种功能函数 #define _CRT_SECURE_NO_WARNINGS 1
#includeQueue.h// 初始化队列
void QueueInit(Queue* q) {assert(q);q-_front NULL;q-_rear NULL;
}
//创造节点
QNode* CreatNode(QDataType x) {QNode* newnode (QNode*) malloc(sizeof(QNode));if (newnode NULL) {perror(malloc:fail);}newnode-_next NULL;newnode-_data x;return newnode;
}// 队尾入队列
void QueuePush(Queue* q, QDataType data) {assert(q);QNode* newnode CreatNode(data);if (q-_rear NULL) {q-_frontq-_rear newnode;}else {q-_rear-_next newnode;q-_rear newnode;}
}// 队头出队列
void QueuePop(Queue* q) {assert(qq-_front!NULL);QNode* head q-_front;if (q-_front q-_rear) {q-_front q-_rear NULL;}else {q-_front q-_front-_next;}free(head);head NULL;
}
//打印队列信息
void QueuePrint(Queue* q) {assert(qq-_rear!NULL);QNode* cur q-_front;printf(队头指向%d 队尾指向%d\n, q-_front-_data, q-_rear-_data);while (cur ! NULL) {printf(%d-, cur-_data);cur cur-_next;}printf(\n);
}
// 获取队列头部元素
QDataType QueueFront(Queue* q) {assert(qq-_front!NULL);return q-_front-_data;
}// 获取队列队尾元素
QDataType QueueBack(Queue* q) {assert(qq-_rear!NULL);return q-_rear-_data;
}// 获取队列中有效元素个数
int QueueSize(Queue* q) {assert(q);int size_q 0;QNode* cur q-_front;while (cur) {size_q;cur cur-_next;}return size_q;
}// 检测队列是否为空如果为空返回非零结果如果非空返回0
int QueueEmpty(Queue* q) {assert(q);return q-_front NULL;
}
// 销毁队列
void QueueDestroy(Queue* q) {assert(qq-_front!NULL);QNode* cur q-_front;while (cur) {QNode* temp cur-_next;free(cur);cur temp;}q-_front q-_rear NULL;
}
test.c文件 测试队列功能 #define _CRT_SECURE_NO_WARNINGS 1
#includeQueue.hvoid test1() {Queue q;QueueInit(q);QueuePush(q, 1);QueuePush(q, 2);QueuePush(q, 3);QueuePush(q, 4);QueuePush(q, 5);QueuePrint(q);printf(弹出队头元素\n);QueuePop(q);QueuePrint(q);printf(队列元素个数%d\n, QueueSize(q));printf(队列队头元素%d 队尾元素%d\n, QueueFront(q), QueueBack(q));QueuePrint(q);QueueDestroy(q);printf(%p %p, q._front, q._rear);
}int main() {test1();return 0;
} 总结
栈和队列都是数据结构中比较基础同时也是必须深刻掌握的数据结构自己去模拟一遍它们的各种功能有利于加深自己对其的理解同时也能提高自己的代码思维。我认为对于初学者来说是打基础的一种很好的方式。
