拼多多网站建设方案,珠海网站建设技术支持,在线整合营销推广,国内外ai设计素材网站一、栈
1.1、栈的基本概念
1.1.1、栈的定义
栈#xff08;Stack#xff09;#xff1a;是只允许在一端进行插入或删除的线性表。首先栈是一种线性表#xff0c;但限定这种线性表只能在某一端进行插入和删除操作。 栈顶#xff08;Top#xff09;#xff1a;线性表允许…
一、栈
1.1、栈的基本概念
1.1.1、栈的定义
栈Stack是只允许在一端进行插入或删除的线性表。首先栈是一种线性表但限定这种线性表只能在某一端进行插入和删除操作。 栈顶Top线性表允许进行插入删除的那一端。栈底Bottom固定的不允许进行插入和删除的另一端。空栈不含任何元素的空表。
1.1.2、栈的操作
void STInit(ST* ps); //初始化栈
void STDestory(ST* ps); //销毁栈
bool STEmpty(ST* ps); //判断是否为空
void STPush(ST* ps, STDataType x); //入栈
void STPop(ST* ps); //出栈
STDataType STTop(ST* ps); //取栈顶元素
int STSize(ST* ps); //返回栈元素个数 1.2、栈的顺序存储结构
采用顺序存储的栈称为顺序栈它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素同时附设一个指针top指示当前栈顶元素的位置。
栈的顺序存储结构可描述为
动态存储结构
typedef struct Stack
{STDataType *a;int top;int capacity; //容量
}ST;
静态存储结构
//静态存储结构
#define N 10
typedef struct Stack
{STDataType data[N];int top;
}ST;
顺序栈的函数实现
1.初始化栈
void STInit(ST* ps) //初始化栈
{assert(ps);ps-a NULL;ps-top 0;ps-capacity 0;
}2.销毁栈
void STDestory(ST* ps) //销毁栈
{assert(ps);free(ps-a);ps-a NULL;ps-top 0;ps-capacity 0;
}
3.判断是否为空
bool STEmpty(ST* ps) //判断是否为空
{assert(ps);return (ps-top 0);
}
4.入栈
void STPush(ST* ps, STDataType x) //入栈
{assert(ps);//扩容if (ps-top ps-capacity){int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tem (STDataType*)realloc(ps-a,sizeof(STDataType)* newcapacity);if (tem NULL){perror(malloc);exit(-1);}ps-a tem;ps-capacity newcapacity;}ps-a[ps-top] x;ps-top;
}
5.出栈
void STPop(ST* ps) //出栈
{assert(ps);assert(ps-top0);--ps-top;
}
6.取栈顶元素
STDataType STTop(ST* ps) //取栈顶元素
{assert(ps);assert(ps-top 0);return ps-a[ps-top-1];
}7.返回元素个数
int STSize(ST* ps) //返回栈元素个数
{assert(ps);return ps-top ;
}
1.3、栈的链式存储结构
1、链栈
采用链式存储的栈称为链栈链栈的优点是便于多个栈共享存储空间和提高其效率且不存在栈满上溢的情况。通常采用单链表实现并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头节点Lhead指向栈顶元素如下图所示。 对于空栈来说链表原定义是头指针指向空那么链栈的空其实就是topNULL的时候。
链栈的结构代码如下
/*栈的链式存储结构*/
/*构造节点*/
typedef struct StackNode{ElemType data;struct StackNode *next;
}StackNode, *LinkStackPrt;
/*构造链栈*/
typedef struct LinkStack{LinkStackPrt top;int count;
}LinkStack;2、链栈的进栈
对于链栈的进栈push操作假设元素值为e的新节点是stop为栈顶指针。
代码如下
/*插入元素e为新的栈顶元素*/
Status Push(LinkStack *S, ElemType e){LinkStackPrt p (LinkStackPrt)malloc(sizeof(StackNode));p-data e;p-next S-top; //把当前的栈顶元素赋值给新节点的直接后继S-top p; //将新的结点S赋值给栈顶指针S-count;return OK;
}3、链栈的出栈
链栈的出栈pop操作也是很简单的三句操作。假设变量p用来存储要删除的栈顶结点将栈顶指针下移以为最后释放p即可。
代码如下
/*若栈不空则删除S的栈顶元素用e返回其值并返回OK否则返回ERROR*/
Status Pop(LinkStack *S, ElemType *e){LinkStackPtr p;if(StackEmpty(*S)){return ERROR;}*e S-top-data;p S-top; //将栈顶结点赋值给pS-top S-top-next; //使得栈顶指针下移一位指向后一结点free(p); //释放结点pS-count--;return OK;
}二、队列
2.1、队列的基本概念
2.1.1、队列的概念
队列queue是只允许在一端进行插入操作而在另一端进行删除操作的线性表。 队列是一种先进先出First In First Out的线性表简称FIFO。允许插入的一端称为队尾允许删除的一端称为队头。 队头Front允许删除的一端又称队首。队尾Rear允许插入的一端。空队列不包含任何元素的空表。
2.1.2、队列的基本操作 void QueueInit(Que* pq); //初始化队列
void QueueDestory(Que* pq); //销毁队列
bool QueueEmpty(Que* pq); //判断队列是否为空
void QueuePush(Que* pq, QDataType x);//进队列
void QueuePop(Que* pq); //出队列
QDataType QueueFront(Que* pq); //取队头元素
QDataType QueueBack(Que* pq); //取队尾元素
int QueueSize(Que* pq); //返回元素个数
2.2、队列的顺序存储结构
队列的顺序实现是指分配一块连续的存储单元存放队列中的元素并附设两个指针队头指针 front指向队头元素队尾指针 rear 指向队尾元素的下一个位置。
2.2.1、顺序队列
队列的顺序存储类型可描述为:
typedef int QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head; //队头指针QNode* tail; //队尾指针int size; //元素个数
}Que;
初始状态队空条件Q-front Q-rear 0。 进队操作队不满时先送值到队尾元素再将队尾指针加1。 出队操作队不空时先取队头元素值再将队头指针加1。 如图d队列出现“上溢出”然而却又不是真正的溢出所以是一种“假溢出”。
2.2.2、循环队列 解决假溢出的方法就是后面满了就再从头开始也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。 当队首指针Q-front MAXSIZE-1后再前进一个位置就自动到0这可以利用除法取余%来实现。 那么循环队列队空和队满的判断条件是什么呢 显然队空的条件是 Q-front Q-rear 。若入队元素的速度快于出队元素的速度则队尾指针很快就会赶上队首指针如图( d1 所示此时可以看出队满时也有 Q -front Q - rear 。 为了区分队空还是队满的情况有三种处理方式 1牺牲一个单元来区分队空和队满入队时少用一个队列单元这是种较为普遍的做法约定以“队头指针在队尾指针的下一位置作为队满的标志”如图 ( d2 所示。
队满条件 (Q-rear 1)%Maxsize Q-front队空条件仍 Q-front Q-rear队列中元素的个数 (Q-rear - Q -front Maxsize)% Maxsize 2类型中增设表示元素个数的数据成员。这样队空的条件为 Q-size O 队满的条件为 Q-size Maxsize 。这两种情况都有 Q-front Q-rear。
3类型中增设tag 数据成员以区分是队满还是队空。tag 等于0时若因删除导致 Q-front Q-rear 则为队空tag 等于 1 时若因插入导致 Q -front Q-rear 则为队满。
循环队列基本算法
1循环队列的顺序存储结构
typedef int ElemType; //ElemType的类型根据实际情况而定这里假定为int
#define MAXSIZE 50 //定义元素的最大个数
/*循环队列的顺序存储结构*/
typedef struct{ElemType data[MAXSIZE];int front; //头指针int rear; //尾指针,若队列不空指向队列尾元素的下一个位置
}SqQueue;2循环队列的初始化
/*初始化一个空队列Q*/
Status InitQueue(SqQueue *Q){Q-front 0;Q-rear 0;return OK;
}3循环队列判队空
/*判队空*/
bool isEmpty(SqQueue Q){if(Q.rear Q.front){return true;}else{return false;}
}4求循环队列长度
/*返回Q的元素个数也就是队列的当前长度*/
int QueueLength(SqQueue Q){return (Q.rear - Q.front MAXSIZE) % MAXSIZE;
}5循环队列入队
/*若队列未满则插入元素e为Q新的队尾元素*/
Status EnQueue(SqQueue *Q, ElemType e){if((Q-rear 1) % MAXSIZE Q-front){return ERROR; //队满}Q-data[Q-rear] e; //将元素e赋值给队尾Q-rear (Q-rear 1) % MAXSIZE; //rear指针向后移一位置若到最后则转到数组头部return OK;
}6循环队列出队
/*若队列不空则删除Q中队头元素用e返回其值*/
Status DeQueue(SqQueue *Q, ElemType *e){if(isEmpty(Q)){return REEOR; //队列空的判断}*e Q-data[Q-front]; //将队头元素赋值给eQ-front (Q-front 1) % MAXSIZE; //front指针向后移一位置若到最后则转到数组头部
}到这里栈和队列的基本问题就解释完了相信多多少少会解决大家心头的疑问在数据结构的学习中应当善于思考多画图死磕代码注意细节将伪代码转换为代码这样才能很好的掌握数据结构的有关知识共勉加油
