一.栈stack后进先出1.限定仅在表尾进行插入或删除操作的线性表。因此栈的表尾端称为栈顶表头端称为栈顶。不含元素的空表称为空栈。设,称为栈底元素为栈顶元素栈中元素按依次入栈退栈的第一个元素应为栈顶元素。2.栈是限制插入和删除操作只能在一个位置进行的表该位置是表的末端叫做栈顶top)。对栈的基本操作有进栈和出栈前者相当于插入后者则是删除最后插入的元素。3.栈的顺序结构实现#includestdio.h #define MAXSIZE 100 //定义栈的最大容量为100便于后续修改 typedef int ElemType;//给int类型起别名便于后续修改 typedef struct{ ElemType data[MAXSIZE];//数组用于存储栈中元素 int top;//栈顶指针记录栈顶元素在数组中的下标。初始为-1表示栈空 }Stack;//定义一个结构体Stack表示顺序栈1初始化//初始化 void initStack(Stack *s){ s-top-1; } //接受一个栈指针s将栈顶指针top设置为-1表示栈为空2判断栈是否为空//判断栈是否为空 int isEmpty(Stack *s){ if(s-top-1){ printf(空\n); return 1; }else{ return 0; } }3进栈/压栈//进栈/压栈 int push(Stack *s,ElemType e){ //接受指针s和要入栈的元素e if(s-topMAXSIZE-1){ //判断是否满栈 printf(满了\n); return 0; } s-top;//指针向上挪一位 s-data[s-top]e;//将e存入新的栈顶的位置 return 1;//入栈成功 }4出栈//出栈 ElemType pop(Stack *s,ElemType *e){ 接收指针s和指针e用于存储出栈元素 if(s-top-1){ //判断是否为空 printf(空\n); return 0; } *es-data[s-top];//将栈顶元素的值赋给*e通过指针带回给调用者 s-top--;//栈顶指针下移一位逻辑上删除栈顶元素 return 1; }5获取栈顶元素//获取栈顶元素 int getTop(Stack *s,ElemType *e){ if(s-top-1){ printf(空\n); return 0; } *es-data[s-top];//将栈顶元素的值赋给*e但不修改栈顶指针 return 1; }6测试//测试 int main(){ Stack s;//定义一个栈变量s initStack(s); push(s,10); push(s,20); push(s,30); ElemType e; pop(s,e); printf(%d\n,e); getTop(s,e); printf(%d\n,e); return 0; }7栈的顺序结构初始化--动态内存分配#includestdio.h #includestdlib.h//标准库头文件 #define MAXSIZE 100 //定义栈的最大容量为100便于后续修改 typedef int ElemType;//给int类型起别名便于后续修改 typedef struct{ ElemType *data; int top; }Stack;//定义一个结构体Stack表示动态顺序栈 //动态初始化 Stack *initStack(){ //定义一个函数返回一个指向动态分配栈的指针 Stack *s(Stack *)malloc(sizeof(Stack));//为栈结构体本身分配内存并将地址赋给指针s s-data(ElemType *)malloc(sizeof(ElemType)*MAXSIZE);//为存储数据的数组分配MAXSIZE个ElemType大小的内存并将地址赋给s-data s-top-1;//初始化栈顶指针为-1 return s;//返回指向这个动态栈的指针 }//释放内存 void destoryStack(Stack *s){ if(s!NULL){ if(s-data!NULL){ free(s-data);//先释放数组数据 } free(s);//再释放栈结构体 } } //测试 int main(){ Stack *sinitStack(); push(s,10); push(s,20); push(s,30); ElemType e; pop(s,e); printf(%d\n,e); getTop(s,e); printf(%d\n,e); destoryStack(s); sNULL; return 0; }4.栈的链式结构#includestdio.h #includestdlib.h typedef int ElemType; typedef struct stack{ ElemType data; struct stack *next; }Stack; //初始化 Stack *initStack(){ Stack *s(Stack *)malloc(sizeof(Stack));//为头节点分配内存并将地址赋给指针s s-data0; s-nextNULL;//栈为空 return s;//返回指向这个头节点的指针 } //判断栈是否为空 int isEmpty(Stack *s){ //接收栈头节点指针s if(s-nextNULL){ printf(空\n); return 1; }else{ return 0; } } //进栈/压栈头插法 int push(Stack *s,ElemType e){ Stack *p(Stack *)malloc(sizeof(Stack)); p-datae; p-nexts-next; s-nextp; return 1; } //出栈 int pop(Stack *s,ElemType *e){ if(s-nextNULL){ printf(空\n); return 0; } *es-next-data; Stack *qs-next; s-nextq-next; free(q); return 1; } //获取栈顶元素 int getTop(Stack *s,ElemType *e) { if(s-nextNULL){ printf(空\n); return 0; } *es-next-data; return 1; } //测试 int main(){ Stack *sinitStack(); push(s,10); push(s,20); push(s,30); ElemType e; pop(s,e); printf(%d\n,e); getTop(s,e); printf(%d\n,e); return 0; }5.例题二.队列1.队列是一种先进先出的线性表。它只允许在表的一端进行插入而在另一端删除元素。在队列中允许插入的一端称为队尾允许删除的一端称为队头。假设队列为qa1,a2,...,an)那么a1就是队头元素an就是队尾元素。队列中的元素是按照a1,a2,...,an的顺序进入的退出队列也只能按照这个顺序依次退出也就是说只有在a1,a2,...都离开队列后an才能退出。2.队列的顺序结构#includestdio.h #define MAXSIZE 100 typedef int ElemType; typedef struct{ ElemType data[MAXSIZE]; int front; int rear; }Queue; //初始化 void initQueue(Queue *Q){ Q-front0; Q-rear0; } //判断队列是否为空(判断rear与front是否相等) int isEmpty(Queue *Q){ if(Q-frontQ-rear){ printf(空\n); return 1; }else{ return 0; } } //出队 ElemType dequeue(Queue *Q){ if(Q-frontQ-rear){ printf(空\n); return 0; } ElemType eQ-data[Q-front]; Q-front; return e; } //队尾满了调整队列 int queueFull(Queue *Q){ if(Q-front0){ int stepQ-front; for(int iQ-front;iQ-rear;i){ Q-data[i-step]Q-data[i]; } Q-front0; Q-rearQ-rear-step; return 1; }else{ printf(真的满了\n); return 0; } } //入队 int equeue(Queue *Q,ElemType e){ if(Q-rearMAXSIZE){ if(!queueFull(Q)){//满了无法入队 return 0; } } Q-data[Q-rear]e; Q-rear; return 1; } //获取队头数据 int getHead(Queue *Q,ElemType *e){ if(Q-frontQ-rear){ printf(空\n); return 0; } *eQ-data[Q-front]; return 1; } //测试 int main(){ Queue q; initQueue(q); equeue(q,10); equeue(q,20); equeue(q,30); equeue(q,40); equeue(q,50); printf(%d\n,dequeue(q)); printf(%d\n,dequeue(q)); ElemType e; getHead(q,e); printf(%d\n,e); return 0; }1判断队列是否为空判断队尾是否等于队头2调整队列3动态内存分配#includestdio.h #includestdlib.h #define MAXSIZE 100 typedef int ElemType; typedef struct{ ElemType *data; int front;//表示队头指针此处为数组下标 int rear;//数组下标 }Queue; //初始化 Queue *initQueue(){ Queue *Q(Queue *)malloc(sizeof(Queue)); Q-data(ElemType *)malloc(sizeof(ElemType)*MAXSIZE); Q-front0; Q-rear0; return Q;//将队头和队尾下标置为0 } //判断队列是否为空(判断rear与front是否相等) int isEmpty(Queue *Q){ if(Q-frontQ-rear){ printf(空\n); return 1; }else{ return 0; } } //出队 ElemType dequeue(Queue *Q){ if(Q-frontQ-rear){ printf(空\n); return 0; } ElemType eQ-data[Q-front];//取出队头元素赋值给临时变量e Q-front; return e; } //队尾满了调整队列 int queueFull(Queue *Q){ if(Q-front0){ //如果队头下标大于0说明前面有空闲空间 int stepQ-front;//定义偏移量step等于当前队头下标 for(int iQ-front;iQ-rear;i){ Q-data[i-step]Q-data[i]; }//从队头到队尾元素前移step个位置 Q-front0;//队头下标重置为0 Q-rearQ-rear-step; return 1; }else{ printf(真的满了\n); return 0; } } //入队 int equeue(Queue *Q,ElemType e){ if(Q-rearMAXSIZE){ if(!queueFull(Q)){//满了无法入队 return 0; } } Q-data[Q-rear]e; Q-rear; return 1; } //获取队头数据 int getHead(Queue *Q,ElemType *e){ if(Q-frontQ-rear){ printf(空\n); return 0; } *eQ-data[Q-front]; return 1; } //测试 int main(){ Queue *qinitQueue(); equeue(q,10); equeue(q,20); equeue(q,30); equeue(q,40); equeue(q,50); printf(%d\n,dequeue(q)); printf(%d\n,dequeue(q)); ElemType e; getHead(q,e); printf(%d\n,e); return 0; }3.循环队列(1)动画演示满满队列rear1)%MAXSIZEfront空队列rearfront队尾(rear1)%MAXSIZE队尾指针总是指向队尾元素的下一个位置满了此处MAXSIZE72代码实现#include stdio.h #define MAXSIZE 5 // 队列最大容量实际有效存储为4牺牲1个单元判满 // 1. 类型定义 typedef int ElemType; typedef struct { ElemType data[MAXSIZE]; int front; // 队头指针指向队头元素 int rear; // 队尾指针指向队尾元素的下一个空闲位置 } SqQueue; // 2. 初始化队列 void InitQueue(SqQueue *Q) { Q-front 0; Q-rear 0; } // 3. 判断队列是否为空 int IsEmpty(SqQueue *Q) { return Q-front Q-rear; } // 4. 判断队列是否为满核心牺牲一个单元 int IsFull(SqQueue *Q) { return (Q-rear 1) % MAXSIZE Q-front; } // 5. 入队操作 // 返回值1成功0失败队列满 int EnQueue(SqQueue *Q, ElemType e) { if (IsFull(Q)) { printf(队列已满入队失败\n); return 0; } Q-data[Q-rear] e; // 将元素放入队尾 Q-rear (Q-rear 1) % MAXSIZE; // 队尾循环后移 return 1; } // 6. 出队操作标准设计输出型参数传值返回值传状态 // 返回值1成功0失败队列空 int DeQueue(SqQueue *Q, ElemType *e) { if (IsEmpty(Q)) { printf(队列为空出队失败\n); return 0; } *e Q-data[Q-front]; // 取出队头元素 Q-front (Q-front 1) % MAXSIZE; // 队头循环后移 return 1; } // 7. 获取队头元素不出队 int GetHead(SqQueue *Q, ElemType *e) { if (IsEmpty(Q)) { printf(队列为空无法获取队头\n); return 0; } *e Q-data[Q-front]; return 1; } // 8. 打印队列辅助函数遍历循环队列 void PrintQueue(SqQueue *Q) { if (IsEmpty(Q)) { printf(队列为空\n); return; } printf(当前队列元素); int i Q-front; // 循环条件未遍历到队尾 while (i ! Q-rear) { printf(%d , Q-data[i]); i (i 1) % MAXSIZE; } printf(\n); } // 主函数测试 int main() { SqQueue q; InitQueue(q); ElemType e; // 用于存储出队/队头元素 // 测试入队MAXSIZE5最多入队4个 EnQueue(q, 10); EnQueue(q, 20); EnQueue(q, 30); EnQueue(q, 40); PrintQueue(q); // 输出10 20 30 40 // 测试队列满 EnQueue(q, 50); // 提示队列已满 // 测试出队 DeQueue(q, e); printf(出队元素%d\n, e); // 输出10 PrintQueue(q); // 输出20 30 40 // 测试循环特性出队后再入队利用空闲空间 EnQueue(q, 50); PrintQueue(q); // 输出20 30 40 50 // 测试取队头 GetHead(q, e); printf(当前队头%d\n, e); // 输出20 return 0; }3举例4.队列的链式结构1动画演示初始化入队头节点不存储有效数据只是用来同一链表操作。头节点指向的下一个节点才存储有效数据。注只要是带头节点不管是链表还是队列头节点都不存有效数据。出队如何方便理解将节点想象成一个快递盒分为左右两部分。左边写着data用来装真正的东西右边写着next用来贴一张地址条告诉下一个盒子在哪。2代码#includestdio.h #includestdlib.h #define MAXSIZE 100 typedef int ElemType; typedef struct QueueNode{ ElemType data; struct QueueNode *next; }QueueNode; typedef struct{ QueueNode *front;//队头指针 QueueNode *rear;//队尾指针 }Queue; //初始化 Queue *initQueue(){ //初始化一个空链表并返回队列指针 Queue *q(Queue *)malloc(sizeof(Queue));//申请一块内存存放队列结构体用指针q指向它 QueueNode *node(QueueNode *)malloc(sizeof(QueueNode));//申请一块内存存放头节点用指针node指向它 node-data0; node-nextNULL; q-frontnode;//队头指针指向头节点 q-rearnode;//队尾指针也指向头节点表示队列为空 return q;//返回初始化好的队列指针 } //判断队列是否为空(判断rear与front是否相等) int isEmpty(Queue *q){ if(q-frontq-rear){ printf(空\n); return 1; }else{ return 0; } } //出队 ElemType dequeue(Queue *q,ElemType *e){//从队头删除一个元素并将其值存入*e QueueNode *nodeq-front-next;//node指向要出队的结点 *enode-data;//把出队节点的数据存入*e q-front-nextnode-next; if(q-rearnode){//如果出队的节点是最后一个节点 q-rearq-front; } free(node); return 1;//出队成功 } //入队 void equeue(Queue *q,ElemType e){//将元素e插入队尾 QueueNode *node(QueueNode *)malloc(sizeof(QueueNode)); node-datae; node-nextNULL;//新节点的next指针置空因为它将成为新的队尾 q-rear-nextnode;//让当前队尾节点的next指向新节点 q-rearnode;//更新队尾指针让它指向新节点 } //获取队头数据 ElemType getHead(Queue *q){ if(isEmpty(q)){ printf(空\n); return 0; } return q-front-next-data;//用front位置固定 } //测试 int main(){ Queue *qinitQueue(); equeue(q,10); equeue(q,20); equeue(q,30); equeue(q,40); equeue(q,50); ElemType e; dequeue(q,e); printf(出队%d\n,e); dequeue(q,e); printf(出队%d\n,e); printf(%d\n,getHead(q)); return 0; }5.双端队列三.关于return的小结1.什么时候return 1表示成功/真/对/做完了eg入队成功/出队成功/判断条件成立/初始化成功2.什么时候return 0表示失败/假/错/没做完/空/满只要函数做不了就return 0eg队列空出不了队/队列满进不去/条件不成立/获取队头失败3.什么时候return只有一种情况就是函数返回值是void