网站建设申请表,淳化网站制作,设计网站推荐p,wordpress添加域名1.前言
哈喽大家好啊#xff0c;今天博主继续为大家带来数据结构与算法的学习笔记#xff0c;今天是关于栈和队列#xff0c;未来博主会将上一章《顺序表与链表》以及本章《栈与队列》做专门的习题应用专题讲解#xff0c;都会很有内容含量 #xff0c;欢迎大家多多支持今天博主继续为大家带来数据结构与算法的学习笔记今天是关于栈和队列未来博主会将上一章《顺序表与链表》以及本章《栈与队列》做专门的习题应用专题讲解都会很有内容含量 欢迎大家多多支持你的鼓励是我最大的动力我们码上见
2.正文
2.1栈
2.1.1结构定义
栈是一种特殊的线性数据结构它的操作顺序是后进先出。栈只允许在栈顶进行元素的插入入栈和删除出栈操作而栈底则通常不直接访问。
2.1.2特点 后进先出最后进入栈的元素会最先被取出。操作限制只能在栈顶进行数据的添加和删除操作。应用场景常用于管理函数调用的返回地址、表达式求值、括号匹配等。 2.1.3基本操作 入栈Push将元素添加到栈顶新元素成为栈顶元素。出栈Pop从栈顶移除元素栈顶指针下移之前的栈顶元素不再可访问。获取栈顶元素Peek/Top查看栈顶元素的值但不移除它。判断栈是否为空如果栈中没有元素则栈为空。获取栈的大小返回栈中元素的数量。栈的初始化为栈分配初始空间并设置栈顶指针。栈的销毁释放栈所占用的空间。 2.1.4栈的俩种实现方式
栈的实现方式主要有两种基于数组的顺序栈和基于链表的链式栈。顺序栈利用一组地址连续的存储单元存放数据元素并通过一个栈顶指针来指示当前栈顶元素的位置。链式栈则通过链表来实现其中链表的头部或尾部作为栈顶。
2.2队列 2.2.1结构定义
队列是一种遵循先进先出原则的数据结构。它只允许在一端队尾进行元素的插入入队而在另一端队头进行元素的删除出队。
2.2.2特点 基本包含的元素size指容量head头指针tail尾指针 先进先出FIFO队列中的元素必须按照它们进入队列的顺序离开队列。这是队列最重要的特性。 只允许在队尾插入元素新元素必须添加到队列的末尾这称为入队操作。 只允许在队头删除元素只能删除队列最前面的元素这称为出队操作。 额外注意队尾的指针是一个空指针是不指向任何元素的。 2.2.3队列的假溢出以及循环队列 队列假溢出出现原因队列假溢出是指在用数组模拟的顺序队列中尽管队列中实际还有空闲位置但由于队尾指针已经指向了数组的最大下标位置而队头指针并未指向数组的最小下标的前一位置此时若尝试进行入队操作则会出现上溢现象即无法将新元素加入队列但实际上队列并未真正存满。这种现象就被称为队列的假溢出。 解决方法创建循环队列即当队尾指针到达数组的末尾时它会回到数组的开头继续移动。在循环队列中可以通过判断队尾指针的下一个位置与队头指针的相对关系来确定队列是否已满或为空。具体地如果 (rear1)%MAXSIZEfront则队列满如果 frontrear则队列空。其中MAXSIZE是队列的最大容量。 2.2.3队列顺序表的实现
#include stdio.h
#include stdlib.h
#include time.htypedef struct vector {int size, count;int *data;//总大小,元素数量
//指针指向连续的存储区
} vector;
//初始化
vector *getNewVector(int n) {vector *p (vector *)malloc(sizeof(vector));p-size n;//存储上限p-count 0;p-data (int *)malloc(sizeof(int) * n);return p;
}int expand(vector *v) {if (v NULL) return 0;printf(expand v from %d to %d\n, v-size, 2 * v-size);int *p (int *)realloc(v-data, sizeof(int) * 2 * v-size);if (p NULL) return 0;v-data p;v-size * 2;return 1;
}
//插入操作
int insert(vector *v, int pos, int val) {if (pos 0 || pos v-count) return 0;if (v-size v-count !expand(v)) return 0;for (int i v-count - 1; i pos; i--) {v-data[i 1] v-data[i];}v-data[pos] val;v-count 1;return 1;
}
//销毁操作
int erase(vector *v, int pos) {if (pos 0 || pos v-count) return 0;for (int i pos 1; i v-count; i) {v-data[i - 1] v-data[i];}v-count - 1;return 1;
}void output_vector(vector *v) {int len 0;for (int i 0; i v-size; i) {len printf(%3d, i);}printf(\n);for (int i 0; i len; i) printf(-);printf(\n);for (int i 0; i v-count; i) {printf(%3d, v-data[i]);}printf(\n);printf(\n\n);return ;
}
//删除操作
void clear(vector *v) {if (v NULL) return ;free(v-data);free(v);return ;
}int main() {srand(time(0));#define MAX_OP 20vector *v getNewVector(2);for (int i 0; i MAX_OP; i) {int op rand() % 4, pos, val, ret;switch (op) {case 0:case 1:case 2:pos rand() % (v-count 2);//为了可以看到插入到非法位置时程序的反应val rand() % 100;ret insert(v, pos, val);printf(insert %d at %d to vector %d\n, val, pos, ret);break;case 3:pos rand() % (v-count 2);ret erase(v, pos);printf(erase item at %d in vector %d\n, pos, ret);break;}output_vector(v);}clear(v);return 0;
}
2.2.4队列链表的实现
#include stdio.h
#include stdlib.h
#include time.h#define DL 3
#define STR(n) #n
#define DIGIT_LEN_STR(n) % STR(n) dtypedef struct Node {int data;struct Node *next;
} Node;Node *getNewNode(int val) {Node *p (Node *)malloc(sizeof(Node));p-data val;p-next NULL;return p;
}Node *insert(Node *head, int pos, int val) {Node new_head, *p new_head, *node getNewNode(val);new_head.next head;for (int i 0; i pos; i) p p-next;node-next p-next;p-next node;return new_head.next;
}void clear(Node *head) {if (head NULL) return ;for (Node *p head, *q; p; p q) {q p-next;free(p);}return ;
}void output_linklist(Node *head, int flag 0) {int n 0;for (Node *p head; p; p p-next) n 1;for (int i 0; i n; i) {printf(DIGIT_LEN_STR(DL), i);printf( );}printf(\n);for (Node *p head; p; p p-next) {printf(DIGIT_LEN_STR(DL), p-data);printf(-);}printf(\n);if (flag 0) printf(\n\n);return ;
}int find(Node *head, int val) {Node *p head;int n 0;while (p) {if (p-data val) {output_linklist(head, 1);int len n * (DL 2) 2;for (int i 0; i len; i) printf( );printf(^\n);for (int i 0; i len; i) printf( );printf(|\n);return 1;}n 1;p p-next;}return 0;
}int main() {srand(time(0));#define MAX_OP 7Node *head NULL;for (int i 0; i MAX_OP; i) {int pos rand() % (i 1), val rand() % 100;printf(insert %d at %d to linklist\n, val, pos);head insert(head, pos, val);output_linklist(head);}int val;while (~scanf(%d, val)) {if (!find(head, val)) {printf(not found\n);}}clear(head);return 0;
}
3.小结
今天的分享到这里就结束了哦数据结构与算法的学习真是让人受益匪浅就是有点费脑子哈哈哈大家一起加油如果大家有帮助的话不要忘了点点关注点点赞哦。
