网站设计论文开题报告,网站改版 被百度k,建设彩票网站制作,简述网站推广方式目录
文章目录
前言
一、栈
1.1 栈的概念及结构
1.2 栈的实现
1.2.1. 支持动态增长的栈的结构
1.2.2 初始化栈
1.2.3 入栈
1.2.4 出栈
1.2.5 获取栈顶元素
1.2.6 获取栈中有效元素个数
1.2.7 检查栈是否为空
1.2.8 销毁栈
二、队列
2.1 队列的概念及结构
2.2 队…
目录
文章目录
前言
一、栈
1.1 栈的概念及结构
1.2 栈的实现
1.2.1. 支持动态增长的栈的结构
1.2.2 初始化栈
1.2.3 入栈
1.2.4 出栈
1.2.5 获取栈顶元素
1.2.6 获取栈中有效元素个数
1.2.7 检查栈是否为空
1.2.8 销毁栈
二、队列
2.1 队列的概念及结构
2.2 队列的实现
2.2.1 队列的结构
2.2.2 初始化队列
2.2.3 入队
2.2.4 出队
2.2.5 获取队头元素
2.2.6 获取队尾元素
2.2.7 获取队列中有效元素个数
2.2.8 检查队列是否为空
2.2.9 销毁队列
总结 一、栈
1.1 栈的概念及结构
栈Stack是一种线性数据结构它可以看作是一种特殊的列表。栈只能在一端进行插入和删除操作这一端被称为栈顶Top。栈按照后进先出LIFO, Last In First Out的原则进行操作即最后一个进栈的元素最先被弹出。栈可以用数组或链表实现。栈的主要操作包括压栈进栈/入栈Push和弹栈出栈Pop还有取栈顶元素Top和判断栈是否为空Empty等。栈在编程中常用于函数调用、表达式求值、括号匹配等场景。 1.2 栈的实现
栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。所以我们这里使用数组实现栈。用数组实现也分为静态的和动态的静态的实际中一般不实用所以我们实现动态的。
1.2.1. 支持动态增长的栈的结构
这里我们声明一个结构体一个成员为指针a用来存放开辟空间的首地址即动态数组一个成员top用来存放栈顶位置还有一个成员capacity用来存放开辟的空间大小方便数组扩容。
代码如下
typedef int StDataType;typedef struct Stack
{StDataType* a;int top; // 标识栈顶位置的int capacity;
}St;
1.2.2 初始化栈
将结构体中的指针a赋值为NULL将capacity赋值为0将top赋值为0表示top指向栈顶元素的下一个位置也可以赋值为-1表示top指向栈顶元素这里我们使用第一种。
代码如下
void StInit(St* pst)
{assert(pst);pst-a NULL;pst-capacity 0;//表示top指向栈顶元素的下一个位置pst-top 0;//表示top指向栈顶元素如果为-1后面的代码也要改//pst-top -1;
}
1.2.3 入栈
入栈之前要先判断开辟的空间满了没如果满了可以使用realloc函数重新分配数组大小然后再将元素插入top所指向的位置最后将top1。
代码如下
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-a, newCapacity * sizeof(StDataType));if (tmp NULL){perror(realloc fail);exit(-1);}pst-a tmp;pst-capacity newCapacity;}pst-a[pst-top] x;pst-top;
}
1.2.4 出栈
先要确保栈中有元素可以使用断言如果有则只需要top-1就行。
代码如下
void StPop(St* pst)
{assert(pst);assert(pst-top 0);pst-top--;
}
1.2.5 获取栈顶元素
先确保栈中有元素然后直接返回top-1所指向位置的元素即可。
代码如下
StDataType StTop(St* pst)
{assert(pst);assert(pst-top 0);return pst-a[pst-top - 1];
}
1.2.6 获取栈中有效元素个数
因为top指向栈顶元素的下一个位置其大小刚好为元素的个数所以直接返回top即可。
代码如下
int StSize(St* pst)
{assert(pst);return pst-top;
}
1.2.7 检查栈是否为空
判断top是否为0为0即为空。
代码如下
bool StEmpty(St* pst)
{assert(pst);return pst-top 0;
}
1.2.8 销毁栈
先将动态分配的内存释放了再将结构体中的成员赋值为初始化栈时所赋值的值就行。
代码如下
void StDestroy(St* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-top 0;pst-capacity 0;
} 二、队列
2.1 队列的概念及结构
队列Queue是一种遵循先进先出First In First OutFIFO原则的数据结构即最先插入队列的元素最先被取出。队列具有两个端点一个是队头Head一个是队尾Tail入队操作enqueue在队尾进行出队操作dequeue在队头进行。队列的应用领域很广例如实现任务调度、消息传递、缓冲区等。常见队列的实现包括单向队列、双向队列和循环队列等。我们这里主要讨论单向队列。 2.2 队列的实现
我们这里实现的是最基础的单向队列双向队列和循环队列各位读者可另行了解。队列也可以数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低因为要整体把元素往前移时间复杂度为O(n)虽然在算法中用数组模拟实现队列可以使用头尾双指针使时间复杂度变成O(1),但这样做出队的同时也把空间浪费了。
2.2.1 队列的结构
因为使用链表实现队列所以先声明一个队列的结点的结构体其成员跟链表的声明一致有两个成员一个为数据val另一个为next指针。然后为了后面实现的方便再声明一个队列结构体其成员包括队头指针phead和队尾指针ptail以及一个记录队列大小的整形size。
代码如下
typedef int QDataType;typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;
2.2.2 初始化队列
将队头指针phead和队尾指针ptail赋值为NULL将size赋值为0。
代码如下
void QueueInit(Queue* pq)
{assert(pq);pq-phead pq-ptail NULL;pq-size 0;
}
2.2.3 入队
先动态申请一个新结点将要入队的元素赋给新结点的val再将新结点的next指针指向NULL。然后判断这个队列是否为空如果为空则将队头指针phead和队尾指针ptail都指向新结点如果不为空则只要改变队尾指针ptail就行即先将队尾指针ptail指向的结点的next指针指向新结点再将队尾指针ptail指向新结点。最后将size1就行了。
代码如下
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newNode (QNode*)malloc(sizeof(QNode));if (newNode NULL){perror(malloc fail);exit(-1);}newNode-val x;newNode-next NULL;if (pq-phead NULL){pq-phead pq-ptail newNode;}else{pq-ptail-next newNode;pq-ptail newNode;}pq-size;
}
2.2.4 出队
先要确保队列中有结点可以使用断言。然后再判断队列中是否只有一个结点如果是则释放这个结点后要将队头指针phead和队尾指针ptail都指向NULL如果不是则只需要将队头指针phead指向它所指向的结点的下一个结点并将它原来所指向的结点释放就行。最后将size-1。
代码如下
void QueuePop(Queue* pq)
{assert(pq);assert(pq-phead);if (pq-phead pq-ptail){free(pq-phead);pq-phead pq-ptail NULL;}else{QNode* tmp pq-phead;pq-phead pq-phead-next;free(tmp);}pq-size--;
}
2.2.5 获取队头元素
先确保队列有结点再返回队头指针phead所指向的结点的值val。
代码如下
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq-phead);return pq-phead-val;
}
2.2.6 获取队尾元素
先确保队列有结点再返回队尾指针ptail所指向的结点的值val。
代码如下
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq-ptail);return pq-ptail-val;
}
2.2.7 获取队列中有效元素个数
直接返回size。
代码如下
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}
2.2.8 检查队列是否为空
判断队头指针phead是否为NULL。
代码如下
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead NULL;
}
2.2.9 销毁队列
先遍历释放队列中的每一个结点再将队列结构体中的成员赋值为初始化队列时所赋值的值就行。
代码如下
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;
} 总结
以上就是关于栈和队列的基本概念和操作。通过这篇文章希望大家能够更好地理解关于栈和队列的原理和实现并在实际编程中灵活运用它们。
