数据结构汇总.ppt

数 据 结 构 Data Structure 数据的逻辑结构： 含义：反映数据元素之间逻辑关系的数据结构。包含两方面的信息： 第一，表示数据元素的信息； 第二，表示各数据元素之间的前后件关系。 例1： B=(D,R)，其中D是数据对象，R是该对象中所有数据成员之间的关系的有限集合。若有 D={1,2,3,4},R={(1,2),(2,3),(3,4)}，则我们可以用图的形式画出该数据结构B： 例2：家庭成员数据结构：B=(D,R), D={父亲，儿子，女儿}，R={（父亲，儿子），（父亲，女儿）}，则图形表示如下： 例3：课程关系数据结构：B=(D,R), D={教师1，教师2，班级1，班级2，班级3}，R={（教师1，班级1），（教师1，班级3），（教师2，班级1），（教师2，班级2），（教师2，班级3）}，则图形表示如下： 数据的逻辑、物理结构 数据的逻辑结构—只抽象反映数据元素的逻辑关系 数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现 分为： 顺序存储结构 借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系 链式存储结构 借助指示元素存储地址的指针表示数据 元素间的逻辑关系 2. 线性表 线性表的类型定义 线性结构特点：在数据元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个前驱 除最后一个外，集合中的每个数据元素均只有一个后继 线性表是一种典型的线性结构。 数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。 2.1 顺序表上基本运算的实现 在c语言中，顺序表用一维数组来实现存储。 算法： 插入 删除 定义：线性表的插入是指在第I（1?i ? n+1）个元素之前插入一个新的数据元素x，使长度为n的线性表 线性表的插入是指在表的第i个位置上插入一个值为 x 的新元素，插入后使原表长为 n的表: (a1，a2，... ，ai-1，ai，ai+1，... ，an) 成为表长为 n+1 表: (a1，a2，...，ai-1，x，ai，ai+1，...，an　) 。 i 的取值范围为1=i=n+1 。 顺序表上完成这一运算则通过以下步骤进行： (1) 将ai～an 顺序向下移动，为新元素让出位置； (2) 将 x 置入空出的第i个位置； (3) 修改 last 指针(相当于修改表长)，使之仍指向最后一个元素。 算法如下： for(j=n;j=i;j--) a[j+1]=a[j]; //元素后移 a[i]=x; //插入元素 n++; //表长度增加1 删除 定义：线性表的删除是指将第i（1?i ? n）个元素删除，使长度为n的线性表 算法如下： for(j=i;jlen;j++) a[j]=a[j+1]; //元素前移 len--; //表长度减1 2.2 线性表的链式实现和表示 线性链表 线性链表的存储结构 单链表的基本运算 插入 删除 线性表的链式存储结构 特点： 用一组任意的存储单元存储线性表的数据元素 利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素 每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息 结点 数据域：元素本身信息 指针域：指示直接后继的存储位置 线性链表 实现 单链表的基本运算 插入 删除 单链表的插入 单链表的删除 3. 栈和队列 栈 栈是特殊的线性表，是操作受限的线性表，称限定性DS 栈定义 栈（stack） 栈的定义和特点 定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈 特点：先进后出（FILO）或后进先出（LIFO） 堆栈操作？？？？？？ 栈的存储实现和运算实现 由于栈是运算受限的线性表，因此线性表的存储结构对栈也是适用的，只是操作不同而已。 顺序栈 链栈 约定：栈顶指针指向栈顶元素。 3.2 队列 队列是特殊的线性表，是操作受限的线性表，称限定性DS 3.2.1 队列的定义 队列的定义及特点 定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表 队尾(rear)——允许插入的一端 队头(front)——允许删除的一端 队列特点：先进先出(FIFO) 顺序队列出入队 循环队列 计算循环队列元素个数方法： 若frontrear: 元素个数= rear-front 若frontrear 元素个数=n-（front-rear）