第六讲（数据结构概述）.ppt

数据结构概述 程序=数据结构+算法 对于程序设计来说： 编程语言是工具； 数据结构是基础； 算法设计是方法。 几种常见的数据结构模型 物理结构(存储结构) 线性表的两种存储方式 1、顺序存储结构 顺序存储结构是指用一组地址连续的存贮单元依次存储线性表的元素，通常用数组实现。数组的物理实现是一块连续的存储空间，它是按首址（表中第1个元素的地址）位移来访问每一个元素。 队列 三、队列的基本操作 （1）初始化队列 * 信息学奥赛进阶教程（第六讲） 数据结构（data structure） 是相互之间存在一种或多种特定关系的 数据元素的集合。 特性 结构名 数据元素间的关系 图例 数据之间的逻辑关系，称逻辑结构 数据元素属于 或不属于集合 集合 结构松散； 用其他结构代替 数据元素一个对 一个 线性结构 结构简单 数据元素一个 对多个 树形结构 结构复杂 数据元素多个 对多个 图状结构 结构复杂 1 顺序结构：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 物理结构：数据结构在计算机中的存储方式。 逻辑上关联的数据元素，物理存储结构中相邻。 2 链式结构 ：借助元素存储地址的指针(pointer）表示数据元素之间的逻辑关系 。 逻辑上关联的数据元素，物理存储结构中不一定相邻。 用高级语言中的数据类型(数组、动态变量)来描述 算法的设计取决于所选定的数据（逻辑）结构，而算法的 实现依赖于所采用的存储结构。 树、图 非线性结构 线性表、栈、队列、串、数组、广义表 线性结构 由n个数据元素的有限序列 除头元素外，每个元素都有一个前趋 除尾元素外，每个元素都有一个后继 线性结构的特点 最简单的线性结构是线性表 2、链式存储结构 在链式存储结构的线性表中，逻辑上相邻的两元素，其物理位置不要求相邻。采用动态指针。数组元素和动态变量的类型一般采用记录类型，数据域存储结点的值，指针域存储后件的数组下标或地址。最后一个结点的指针域的值为0或nil。 …… type jid=record data:integer; next:integer; end; var alist：array[1..100] of jid; 静态链表: 用数组模拟指针,实现单链表的各种操作，下标为地址。 {定义结点的结构} {可容纳100个结点} next data 数据域 指针域 有如下的数据：80 25 66 99 33 55 下标 1 5 2 3 4 6 7 …… 0 6 5 4 3 2 55 33 99 66 25 80 数据域 指针域 下标 1 5 2 3 4 6 7 a[i].data a[i].next i 值为0时为普通的静态链表； 值为1时为循环的静态链表。 插入一个数：80 25 66 99 56 33 55 …… 0 6 4 3 2 55 33 99 66 25 80 数据域 指针域 下标 1 5 2 3 4 6 7 j n a[n].next:=a[j].next; a[j].next:=n; 5 …… 0 6 4 3 2 55 33 99 66 25 80 数据域 指针域 下标 1 5 2 3 4 6 7 j n 56 7 5 插入后 删除一个数：80 25 66 99 56 33 55 …… 5 0 6 7 4 3 2 56 55 33 99 66 25 80 数据域 指针域 下标 1 5 2 3 4 6 7 j j指针指向当前节点； a[j].next a[j].next表示当前节点的后继结点 …… 5 0 6 7 4 4 2 56 55 33 99 66 25 80 数据域 指针域 下标 1 5 2 3 4 6 7 a[j].next：= a[a[j].next].next; j a[j].next 删除后 7(8-3)、猴子选大王 题目：有x个猴子围成一圈，每个有一个编号，编号从1到y。打算从中选出一个大王。经过协商，决定选大王的规则如下：从第一个开始，数到n的猴子出圈，最后剩下来的就是大王。 要求：从键盘输入x，y，编程计算哪一个编号的猴子成为大王。 …… 1 7 6 5 4 3 2 7 6 5 4 3 2 1 指针域 下标 1 5 2 3 4 6 7 数据域 …… 1 7 6 5 4 3 2 指针域 下标 1 5 2 3 4 6 7 下标 同时表示 数据域 循环链表 简化链表结构： 让某只猴子出圈（例如：第3只）： j指针指向当前节点； a[j]表示当前节点的后继结点 j a[j] …… 1 7 6 5 4 3 2 指针域 下标 1 5 2