数据结构与算法

一、相关概念 结点：根节、叶节点、分支结点、兄弟结点、父子结点 边、路径 结点深度、高度、层数 根节点为第 0 层 深度指从根节点到该节点的边的数量 高度指从此节点到叶节点的结点数量 满二叉树、完全二叉树 满二叉树指除了度为 0 的叶节点就是度为 2 的分支节点 完全二叉树指只有最下面的两层度是小于 2 的，且最下面的结点都集中在左侧 扩充二叉树 二叉树性质

模式串 next 向量计算： 字符串比较 int mystrcmp(const char* str1, const char* str2){ int i = 0; while(str1[i] == str2[i] && str1[i] != '\0'){ i++; } return str1[i] - str2[i]; }

一、队列的应用 只要满足先来先服务特性的应用均可采用队列作为其数据组织方式或中间数据结构 调度或缓冲 消息缓冲器 邮件缓冲器 计算机硬设备之间的通信也需要队列作为数据缓冲 操作系统的资源管理 宽度优先搜索 广度优先搜索：搜索该步的所有可能状态，再进一步考虑后面的各种情况；（队列应用） 树的层次遍历 深度优先搜索：沿某一状态走下去，不行再回头。（栈应用） 树的先序、中序、后续遍历 二、农夫过河问题 问题抽象： “人狼羊菜”乘船过河 只有人能撑船，船只有两个位置（包括人） 狼羊、羊菜不能在没有人时共处 数据抽象： 对每个角色的位置进行描述，农夫、狼、羊和菜，四个目标依次各用一位，目标在起始岸位置：0，目标岸：1。如 0110 表示农夫、白菜在起始岸，而狼、羊在目标岸（此状态为不安全状态） 用整数 status 表示上述四位二进制描述的状态，如整数 0x08 表示的状态 1000，整数 0x0F 表示的状态 1111 如何从上述状态中得到每个角色所在位置？ bool farmer(int status){ return ((status & 0x08) != 0); } bool wolf(int status){ return ((status & 0x04) !...

栈的物理实现有 顺序队列 和 链式队列 一、顺序队列 用向量存储队列元素，用两个变量分别指向队列的前端(front)和尾端(rear) 关键是如何防止假溢出 队列溢出 上溢 下溢 假溢出：当 rear = mSize-1 时，再作插入运算就会产生溢出，如果这时队列的前端还有许多空位置，这种现象称为假溢出 循环队列 为了解决假溢出的问题，需要采用循环队列的方式： % mSize 另外一个问题就是如何区分空队列还是满队列？空一个队列空间，空队列状态时，令 front = rear，若 (rear + 1) % mSize == front，我们认为此时队列已满，但实际上 rear 指向的空间并没有被利用 循环队列类定义 template <class T> class arrQueue: public Queue<T> { private: int mSize; // 存放队列的数组的大小 int front; // 表示队头所在位置的下标 int rear; // 表示待入队元素所在位置的下标 T *qu; // 存放类型为T的队列元素的数组 public: // 队列的运算集 arrQueue(int size) { // 创建队列的实例 mSize = size + 1; // 浪费一个存储空间，以区别队列空和队列满 qu = new T[mSize]; front = rear = 0; } ~arrQueue() { // 消除该实例，并释放其空间 delete[] qu; } } // 入队操作 template<class T> bool arrQueue<T> :: enQueue(const T item) { // item入队，插入队尾 if (((rear + 1 ) % mSize) == front) { cout << "队列已满，溢出" << endl; return false; } qu[rear] = item; rear = (rear + 1) % mSize; // 循环后继 return true; } // 出队操作 bool arrQueue<T> :: deQueue(T& item) { // 返回队头元素并从队列中删除 if ( front == rear) { cout << "队列为空" << endl; return false; } item = qu[front]; front = (front + 1) % mSize; // 这里并没有真的删除队列空间的元素，而是把头指针循环后移 return true; } 二、链式队列 用单链表方式存储，队列中每个元素对于链表中的一个结点...

一、队列 队列特点 访问受限的线性表 先进先出 插入在一端进行，删除在另一端进行 主要元素 队头 队尾 主要操作 入队列 出队列 取队首元素 判断队列是否为空 二、队列的抽象数据类型 template <class T> class Queue { // 队列的运算集 public: // 变为空队列 void clear(); // 将item插入队尾，成功则返回真，否则返回假 bool enQueue(const T item); // 返回队头元素并将其从队列中删除，成功则返回真 bool deQueue(T & item); // 返回队头元素，但不删除，成功则返回真 bool getFront(T & item); // 返回真，若队列已空 bool isEmpty(); // 返回真，若队列已满 bool isFull(); }; 三、队列的实现方式 队列的物理实现又分为顺序队列和链式队列