阅读量:0
笔记
栈
一.操作受限的线性表
1> 在之前的内容，无论是顺序表还是链表，都是详细处理的线性表，既可以在端点处进行操作，也可以在中间位置操作
2> 现实生活中，有很多并不需要在中间进行操作的序列，只在端点处进行操作，这样的线性表，我们称为操作受限的线性表
3> 根据不同的受限情况，线性表分为：栈、队列
4> 栈：插入和删除操作都只允许在同一端进行。
队列：插入和删除操作都只允许在异端进行。
二.栈的相关概念
1> 栈：操作受限的线性表，插入和删除只能在同一端进行，不能在中间进行相关操作
2> 允许操作的一端，称为栈顶，不允许操作的一端称为栈底
3> 特点：先进后出（后进先出）
例如：水杯容器、枪的弹夹
4> 栈的分类：根据存储方式的不同，分为顺序栈和链式栈
顺序栈：顺序存储的栈称为顺序栈
链式栈：链式存储的栈称为链式栈
三.顺序栈
定义结构：
typedef int datatype;
#define MAX 8;
typedef struct
{
datatype *data;
int top;
}Stack,*StackPtr;
四.链式栈
1> 链式存储的栈，称为链式栈
2> 对于单链表而言，我们可以使用，使用头插头删完成一个栈，或者尾插尾删完成链式栈
3> 头插头删：链表的头部就是栈顶，链表的尾部就是栈底（常用）
4> 尾插尾删：链表的尾部就是栈顶，链表的头部就是栈底
队列
一.队列介绍
1> 队列也是操作受限的线性表：所有操作只能在端点处进行，其删除和插入必须在不同端进行
2> 允许插入操作的一端称为队尾，允许删除操作的一端称为队头
3> 特点：先进先出（FIFO）
4> 分类：
顺序存储的队列称为顺序队列
链式存储的队列，称为链式队列
二.顺序队列
1> 使用一片连续存储的空间存储队列，并且给定两个变量，分别记录队头和队尾下标
2> 普通顺序队列使用中，存在“假溢满”现象
假溢满：队列中明明还有存储空间，但是由于队尾已经达到了数组的最大下标，不能在继续入队元素了
3> 为了解决“假溢满”现象，我们引入了循环顺序队列
三.循环顺序队列
1> 循环顺序队列：通过相关操作，当对头或队尾达到数组最大下标时，可以返回到下标为0的位置
2> 结构体类型：一个数组存储队列，两个变量分别存储队头和队尾的下标
注意：需要人为浪费一个存储空间，用于判满
#define MAX 8;
typedef int datatype
typedef struct
{
datatype data[MAX];
int front;
int tail;
}SeqQueue,*SeqQueuePtr;
四.链式队列
1> 链式存储的队列称为链式队列
2> 实现原理：
单向链表头插尾删实现：链表的头部就是队尾，链表的尾部就是队头
单向链表头删尾插实现：链表的头部就是队头，链表的尾部就是队尾
但是：上述操作中，都要用到链表尾部节点，都需要遍历整个链表完成，效率较低
此时，我们可以引入尾指针的概念，专门指向最后一个节点的指针。
3> 将一个头指针和一个尾指针封装成一个队列
4> 队列类型
typedef int datatype;
typedef struct Node
{
union
{
datatype data;
int len;
};
struct Node*next;
}Node,*NodePtr;
typedef struct
{
NodePtr head;
Nodeptr tail;
}Queue,*QueuePtr;
作业
使用栈，完成进制转换
输入：一个整数，进制数
输出：该数的对应的进制数
#include<myhead.h> #include"fun.h" int main(int argc, char const *argv[]) { int num=0; int flag=0; printf("请输入一个数：\n"); scanf("%d",&num); printf("请输入你要转换的进制：\n"); scanf("%d",&flag); StackPtr S=stack_create(); for (int i = 0; num!=0; i++) { stack_push(S,num%flag); num=num/flag; } printf("%d转换%d进制的结果为：\n",num,flag); stack_show(S); return 0; } #include<myhead.h> #include"fun.h" QueuePtr queue_create() { QueuePtr Q=(QueuePtr)malloc(sizeof(Queue)); if(NULL==Q) { printf("创建失败！\n"); return NULL; } NodePtr P=(NodePtr)malloc(sizeof(Node)); if(NULL==P) { printf("创建失败！\n"); free(Q); return NULL; } Q->head=P; Q->tail=P; P->len=0; P->next=NULL; printf("创建成功！\n"); return Q; } int queue_empty(QueuePtr Q) { return Q->head==Q->tail; } void queue_push(QueuePtr Q,datatype e) { if(NULL==Q) { printf("入列失败！\n"); return; } NodePtr P=(NodePtr)malloc(sizeof(Node)); if(NULL==P) { printf("入列失败！\n"); return; } P->data=e; P->next=NULL; Q->tail->next=P; Q->head->len++; Q->tail=P; printf("入列成功！\n"); } void queue_pop(QueuePtr Q) { if(NULL==Q||queue_empty(Q)) { printf("出列失败！\n"); return; } NodePtr P=Q->head->next; Q->head->next=P->next; free(P); P=NULL; if(Q->head->next==NULL) { Q->tail=Q->head; } Q->head->len--; printf("出列成功！\n"); } void queue_show(QueuePtr Q) { if(NULL==Q||queue_empty(Q)) { printf("遍历失败！\n"); return; } NodePtr P=Q->head; while(P->next) { P=P->next; printf("%d\t",P->data); } putchar(10); } int queue_size(QueuePtr Q) { if(NULL==Q) { return -1; } return Q->head->len; } void queue_destroy(QueuePtr Q) { if(NULL==Q) return; while(!queue_empty(Q)) { queue_pop(Q); } free(Q->head); Q->head=Q->tail=NULL; free(Q); Q=NULL; printf("销毁成功！\n"); } #ifndef _FUN_H_ #define _FUN_H_ typedef int datatype; typedef struct Node { union { datatype data; int len; }; struct Node *next; }Node,*NodePtr;//定义节点类型 typedef struct { NodePtr head; NodePtr tail; }Queue,*QueuePtr;//定义队列类型 QueuePtr queue_create(); int queue_empty(QueuePtr Q); void queue_push(QueuePtr Q,datatype e); void queue_pop(QueuePtr Q); void queue_show(QueuePtr Q); int queue_size(QueuePtr Q); void queue_destroy(QueuePtr Q);