数据结构的研究内容课件

N.沃思（NiklausWirth)教授提出：

程序=算法+数据结构电子计算机的主要用途：

早期：主要用于数值计算

后来：

处理逐渐扩大到非数值计算领域，能处理多种复杂的具有一定结构关系的数据数据结构的研究内容数据结构（DataStructure）是相互之间存在一种或多种特定关系的数据元素的集合。数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。数据组织数据结构的两个层次：逻辑结构---数据元素间抽象化的相互关系，与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。存储结构（物理结构）----数据元素及其关系在计算机存储器中的存储方式。线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树集合——数据元素间除“同属于一个集合”外，无其它关系图形结构——多个对多个，如图逻辑结构划分方法二线性结构书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表树形结构树形结构/(root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp文件系统的系统结构图树人机对弈关系（结构）？人机对奕问题树的遍历……..……..…...…...…...…...图结构图结构

21:57

多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图的着色顶点：一条通路连线：不能同时通行染色：有连线的两个顶点不能具有相同颜色渡河问题一个人带了一只狼、一只山羊和一棵白菜想要渡河。河上有一只独木船，每次除人外只能带一样东西，另外如果人不在时狼就要吃山羊，羊就要吃白菜。问应该怎样安排渡河，才能做到既把所有东西都带过河，而且在河上来回的次数又最少？设M代表人，W代表狼，S代表山羊，V代表白菜。渡河问题算法思想：用集合表示在某岸上的所有情况（16种）：[MWSV][MWS][MWV][MSV][WSV][MW][MS][MV][WS][WV][SV][M][S][V][空]剩下的10种情况,按若甲经过一次渡河可变成乙,那么就在甲与乙之间连一条边,由此得到如下图G:MWSVMWSMWVMSVMSMSWSV空

结论:在G中找一条连接顶点MWSV与空,并且包含边数最少的路.图的最短路径数据结构的两个层次：逻辑结构---数据元素间抽象化的相互关系，与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。存储结构（物理结构）----数据元素及其关系在计算机存储器中的存储方式。存储结构存储结构分为：顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系存储结构线性结构①只有一个首结点和尾结点；②除首尾结点外，其他结点只有一个直接前驱和一个直接后继。线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是线性表线性表的顺序存储元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序表线性表的链式存储1536元素21400元素11346元素3∧元素4h单链表单链表各结点由两个域组成：数据域：存储元素数值数据指针域：存储直接后继结点的存储位置1536元素214001346元素3∧元素4h数据结构的两个层次：逻辑结构---数据元素间抽象化的相互关系，与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。存储结构（物理结构）----数据元素及其关系在计算机存储器中的存储方式。

程序=算法+数据结构2512478936141234567892512479989361499插入251247893614251247893614251247893614顺序表插入（插在第i个结点之前）

（1）判断插入位置i是否合法。（2）判断顺序表的存储空间是否已满。（3）将第n至第i位的元素依次向后移动一个位置，空出第i个位置。（4）将要插入的新元素e放入第i个位置。（5）表长加1，插入成功返回OK。【算法步骤】251247893614123456789251247361425124736142512473614删除顺序表删除（删除第i个结点）

（1）判断删除位置i是否合法（合法值为1≤i≤n）。（2）将欲删除的元素保留在e中。（3）将第i+1至第n位的元素依次向前移动一个位置。（4）表长减1，删除成功返回OK。【算法步骤】将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间单链表插入（插在第i个结点之前）

思考：步骤4和5能互换么？

21:57

【算法步骤】（1）找到ai-1存储位置p（2）生成一个新结点*s（3）将新结点*s的数据域置为x（4）新结点*s的指针域指向结点ai（5）令结点*p的指针域指向新结点*s单链表删除（删除第i个结点）

【算法步骤】（1）找到ai-1存储位置p（2）临时保存结点ai的地址在q中，以备释放（3）令p->next指向ai的直接后继结点（4）将ai的值保留在e中（5）释放ai的空间用铁路调度站表示栈栈栈的定义和特点1.定义与线性表相同，仍为一对一关系2.逻辑结构只能在表的一端（栈顶）进行插入和删除运算的线性表后进先出（LIFO）3.运算规则关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同5.实现方式用顺序栈或链栈存储均可，但以顺序栈更常见4.存储结构a1a2……an顺序栈Sai……栈底base栈顶top低地址高地址压入：PUSH(an+1)弹出：POP(x)前提：一定要预设栈顶指针top！an+1顺序栈顺序栈的表示思考：栈空和栈满的条件？topAbasebasetopABABCtopbasetopbaseABCDbasetop3120(1)判断是否栈满，若满则出错(2)元素e压入栈顶(3)栈顶指针加1顺序栈进栈和出栈ABCtopbase(1)判断是否栈空，若空则出错(2)获取栈顶元素e(3)栈顶指针减1队列

队列是一种先进先出(FIFO)的线性表。

在表一端插入,在另一端删除a1a2a3an...入队列队头队尾a1a2a3an...队头队尾出队列a1a2a3an...队头队尾出队列a1a2a3an...队头队尾出队列队列的定义和特点1.定义用顺序队列或链队存储均可3.存储结构与线性表相同，仍为一对一关系2.逻辑结构只能在表的一端（队尾）进行插入，在另一端（队头）进行删除运算的线性表先进先出（FIFO）4.运算规则关键是编写入队和出队函数，具体实现依顺序队或链队的不同而不同5.实现方式Q.frontQ.rearJ5J6Q.front012345Q.rearJ5J6J1J2J3J4顺序队列存在的问题front=0rear=M时再入队—真溢出front0rear=M时再入队—假溢出解决的方法－－循环队列10Q.rearQ.front......实现：利用“模”运算入队：

base[rear]=x;rear=(rear+1)%M;出队：

x=base[front];front=(front+1)%M;

2023年10月24日

北京林业大学信息学院J4J5J6012345rearfrontJ9J8J7J7,J8,J9入队队空：front==rear队满：front==rear解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间：队空：front==rear

队满：(rear+1)%M==frontJ4J5J6012345rearfront012345frontJ4,J5,J6出队rear案例分析与实现案例1：数制的转换【算法步骤】①初始化一个空栈S。②

当十进制数N非零时，循环执行以下操作：把N与8求余得到的八进制数压入栈S；N更新为N与8的商。③

当栈S非空时，循环执行以下操作：弹出栈顶元素e；输出e。案例2：括号的匹配【算法步骤】①初始化一个空栈S。②设置一标记性变量flag，用来标记匹配结果以控制循环及返回结果，1表示正确匹配，0表示错误匹配，flag初值为1。③扫描表达式，依次读入字符ch，如果表达式没有扫描完毕或flag非零，则循环执行以下操作：若ch是左括号“[”或“(”，则将其压入栈；若ch是右括号“)”，则根据当前栈顶元素的值分情况考虑：若栈非空且栈顶元素是“(”，则正确匹配，否则错误匹配，flag置为0；若ch是右括号“]”，则根据当前栈顶元素的值分情况考虑：若栈非空且栈顶元素是“[”，则正确匹配，否则错误匹配，flag置为0。④退出循环后，如果栈空且flag值为1，则匹配成功，返回true，否则返回false。案例3：迷宫求解从入口出发，按某一方向向未走过的前方探索若能走通，则到达新点，否则试探下一方向;若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。求解思想：回溯法迷宫求解需要解决的问题：1、表示迷宫的数据结构2、试探方向3、栈的设计4、防止重复到达某点，避免发生死循环迷宫求解1、表示迷宫的数据结构表示一个m行n列迷宫：用maze[m][n]表示，0≤i<m,0≤j<nmaze[i][j]=0通路maze[i][j]=1不通改进：用maze[m+2][n+2]表示且maze[i][j]=1，i=0或m＋1,j=0或n＋1入口坐标为（1，1），出口坐标为（m，n）

迷宫求解012345678901111111111110010001012100100010131000011001410111000015100010000161010001001710111011018110001000191111111111迷宫的定义：#definem8

/*迷宫的