有没有医学生做课件的网站,在线crm平台,天山网站,微信h5制作小程序有哪些栈和队列
一栈
1.栈的顺序存储结构
特点#xff1a;先进后出
栈是一种只能在一端进行插入或删除操作的线性表。
表中允许插入删除操作的一端为栈顶#xff08;top#xff09;#xff0c;表的另一端为栈底#xff08;bottom#xff09;#xff0c; 1 结构体的定义
…栈和队列
一栈
1.栈的顺序存储结构
特点先进后出
栈是一种只能在一端进行插入或删除操作的线性表。
表中允许插入删除操作的一端为栈顶top表的另一端为栈底bottom 1 结构体的定义
#include stdio.h
typedef int ElemType;
#define MAX_SIZE 100typedef struct {int data[MAX_SIZE]; // 用于存储栈中的元素int top; // 栈顶指针指向栈顶元素的索引
} SqStack;
2 初始化栈
栈顶指针赋值为-1
void InitStack(SqStack *s) {s (SqStack *) malloc(sizeof(SqStack));//申请一个顺序栈空间s-top -1;//栈顶指针赋值为-1
}
3 销毁栈
释放节点空间
void DestroyStack(SqStack *s) {free(s);
}
4 判断栈是否为空
指针为-1
bool StackEmpty(SqStack *s) {return (s-top -1);
}
5 进栈
先判断栈是否为满
注意先将指针再对栈顶元素进行赋值
bool PushStack(SqStack *s, ElemType e) {if (s-top MAX_SIZE - 1) {//栈满的情况return false;}s-top;s-data[s-top] e;//先加再赋值(s-data[s-top])return true;
}
6 出栈
先对栈元素赋值再将栈顶指针--
bool Pop(SqStack *s, ElemType e) {if (s-top -1) {//栈空的情况return false;}es-data[s-top];s-top--;return true;
}
7 获取栈顶元素
bool GetTop(SqStack *s,ElemType e){if (s-top-1)return false;es-data[s-top];return true;
}
补充共享栈
顺序栈采用一个数组存放栈中的元素。如果需要用到两个类型相同的栈这时若为它们各自开辟一个数组空间极有可能出现这样的情况第一个栈已经满了再进栈就溢出了而另一个栈还有许多的空间。共享栈是为了更有效地利用存储空间两个栈的空间相互调节只有在整个存储空间被占满时才会发生上溢。其存储数据的时间复杂度均为O(1),所以对存取效率没有什么影响。栈空条件栈0空为top-1;栈1空为top1MaxSize.栈满条件toptop1-1元素进栈操作进栈0操作为top0data[top0]x;进栈1操作为top1--data[top1]x元素出栈操作出栈0操作为xdata[top0];top0--出栈1操作为xdata[top1]top1在上述操作中data数组表示共享栈的存储空间top0和top1分别为两个栈的栈顶指针这样该共享栈通过data,top0和top1来标识也可以将他们设计为一个结构体类型。 2.栈的链式存储结构 栈中的数据元素的逻辑关系呈线性关系所以栈可以像线性表一样采用链式存储结构
链栈通过单链表实现
不存在栈满上溢的情况可以一直添加。
typedef struct linknode
{//定义链表节点数据ElemType data;//定义指针域,单链表的后继指针域struct linknode *next;
}LiStack;
栈的四要素 栈空的条件
s-nextNULL
bool StackEmpty(LiStack *s)
{return(s-next NULL);
} 栈满的条件
链栈不存在满的情况 进栈的条件
将带新元素的节点插入
//定义链表节点指针
LiStack *p;
//为新节点申请空间
p (LiStack *)malloc(sizeof(LiStack));
//为新节点的数据区赋值
p - data e;
//头插法
//将新节点后继指针指向下一个节点 ,下一个节点插入前存放在头结点的后继指针
p - next s -next;
//然后将头结点的后继指针指向新节点
s-next p; 出栈的条件
将栈顶节点删除
//传入要出栈的链栈 , 传入要出栈的指针元素
bool Pop(LiStack *s , ElemType e)
{//用指针指向要出栈的元素,就是头结点的后继节点LiStack *p;//如果s-next 为空,则表明为空栈 ,无法出栈元素if(s-next NULL){return false;}//如果经过上面条件的验证,s-next不为空,则接着往下走//先定位要出栈的元素p s-next; //头结点的后继节点e p-data; //栈顶数据传出//开始删除头结点的后继节点 p,也就是头结点指向要删除节点的下一个节点s-next p-next;//然后释放 p 空间free(p);return true;
}
二 队列
特点先进先出
队列只允许在一端进行插入另一端进行删除允许插入的时队尾允许删除的时队头
插入元素称为入队删除元素称为出队。 1 顺序队列
用一组地址连续的存储单元以此存放从队头到队尾的数据元素称为顺序队列。需要附设两个指针一个队头指针front一个队尾指针(rear)分别指向队头队尾。 初始时front和rear均为-1元素进队rear加1front指向队首元素的前一位置队满条件rearMaxSize-1队空条件frontrear进队操作元素进队rear,data[rear]e出队操作元素出队front,edata[front]
顺序队中实现队列的基本运算算法
结构体声明
typedef struct {ElemType data[MaxSize];//存放队中元素int front,rear;//队头和队尾指针
}SqQueue;
1 初始化
构造一个空队列q将front和rear指针均设置为初始状态-1
void InitQueue(SqQueue *q){q(sqQueue *)malloc(sizeof(SqQueue));q-frontq-rear-1;
}
2 入队
在队不满的情况下先将队尾指针rear再将元素添加到该位置
bool enQueue(SqQueue *q, ElemType e) {if (q-rear MaxSize - 1)return false;q-rear;q-data[q-rear] e;return true;
}
3 出队
在队不空的情况下将队首元素front再将该位置的元素赋值给e
bool deQueue(SqQueue *q, ElemType e) {if (q-front q-rear)return false;q-front;e q-data[q-front];return true;
}
2 环形队列 这是因为采用了rearMaxSize-1作为队满条件的缘故当出现这种情况可能会出现还有空间没有填满的情况。这种情况称为假溢出。 解决方案环形队列 实际上地址一定是连续的不可能是环形的这里是通过逻辑方式实现环形队列
rear(rear1)%MaxSizefront(front1)%MaxSize 队空条件rearfront队满条件(rear1)%MaxSizefront进队操作rear(rear1)%MaxSize,并且将e放在rear处出队操作front(front1)%MaxSize将front位置e取出这种情况下会比原先少放一个元素
相关计算 3 链队
采用链表存储的称为链队。 相关操作 单链表中数据节点类型DataNode声明如下
typedef struct qnode{ElemType data;struct qnode *next;
}DataNode;
链队节点类型LinkQuNode声明如下
typedef struct {DataNode *front;DataNode *rear;
}LinkQuNode;
链队四要素
链队为空的判断条件frontrearNULL链队为满的判断条件不考虑链队插入的判断条件将含e的单链表节点插入至链表结尾链队删除的判断条件将单链表的首元节点删除
代码实现
#include stdio.h
#include cstdlibtypedef int ElemType;
typedef struct qnode {ElemType data;//存放元素struct qnode *next;//下一个节点指针
} DataNode;//数据节点的类型typedef struct {DataNode *front;DataNode *rear;
} LinkQuNode;
初始化
void InitQueue(LinkQuNode *q) {q (LinkQuNode *) malloc(sizeof(LinkQuNode));q-front q-rear NULL;
}
判断是否为空
bool QueueEmpty(LinkQuNode *q) {return (q-rear NULL);
}
进队列
bool enQueue(LinkQuNode *q, ElemType e) {DataNode *p;p (DataNode *) malloc(sizeof(DataNode));p-data e;p-next NULL;if (q-rear NULL)q-front q-rear p;else {q-rear-next p;q-rear p;}return true;
}
出队列
bool deQueue(LinkQuNode *q, ElemType e) {DataNode *t;if (q-rear NULL)return false;t q-front;if (q-front q-rear)q-front q-rear NULL;elseq-front q-front-next;e t-data;free(t);return true;
}
4 双端队列
所谓双端队列是指两端都可以进行进队和出队的操作的队列将队列的两端分别成为前端和后端两端都可以进队和出队。
