数据结构之顺序表.ppt

EI Dept.,Huazhong University of Science and Technology SCIE, University of Electronic Science and Technology of China * 第二章 线性结构 线性表 堆栈 队列 串 二维数组 SCIE, University of Electronic Science and Technology of China * 2.1线性表 线性表的定义 线性表是n个相同类型数据元素的有限线性序列，通常记为（a1, a2,a3,……,an）。 线性表特点： 各元素数据类型必须相同 数据ai可以是数字、字符和记录等 例1 (1,1,2,3,5,8,13); 例2 (Sun，Mon，The，wed，Thu，Fri，Sat） 例3 学生成绩表 学号 姓名 成绩 001 丁一 87 002 马二 80 … … … SCIE, University of Electronic Science and Technology of China * 2.1线性表 逻辑结构：元素及元素之间的关系为线性； （1）有且仅有一个开始节点（该节点只有一个直接后继节点，没有直接前趋节点） （2）有且仅有一个结束节点（该节点只有一个直接前趋节点，没有直接后继节点） （3）其余节点有且仅有一个直接前趋和一个直接后继 SCIE, University of Electronic Science and Technology of China * 2.1线性表 线性表不同的实现方式： 2.1.1顺序表 数组存储 顺序表定义 顺序表基本操作： 遍历、插入、删除 顺序表算法分析 2.1.2单链表 2.1.3双向链表 链接存储 2.1.4循环链表 SCIE, University of Electronic Science and Technology of China * 2.1.1顺序表 一、定义 采用顺序存储结构的线性表通常称为顺序表 用一组地址连续的存储单元依次存储线性表的数据元素。 内存 存储地址 元素序号 1 2 i n a1 a2 … ai … an 特点： 实现逻辑上相邻—物理地址相邻 随机存取 Loc(a1) Loc(a1)+k … Loc(a1)+(i-1)*k … Loc(a1)+(n-1)*k SCIE, University of Electronic Science and Technology of China * 2.1.1顺序表 可以借助于高级程序设计语言中的数组来表示：数组的下标与元素在线性表中的序号相对应。 顺序表说明： typedef struct list_type{ elemtype data[ MAXNUM ]; int length; }list_type; list_type list; 问题: 如何获得第i的数据元素？ list.data[i] 0≤i ≤ length SCIE, University of Electronic Science and Technology of China * 2.1.1顺序表 二、顺序表的基本操作 遍历（查询） 插入 删除 …… SCIE, University of Electronic Science and Technology of China * 2.1.1顺序表 遍历运算 问题描述 在第1个元素到第length个元素依次取值 a1 a2 … ai … an SCIE, University of Electronic Science and Technology of China * 2.1.1顺序表 for( i = 0; i table.length; i++ ){ } typedef struct list_type{ elemtype data[ MAXNUM ]; int length; }list_type; list_type table; table.data[ i ] 。。。 SCIE, University of Electronic Science and Technology of China * 2.1.1顺序表 插入运算 问题描述 在第i个元素前插入一个新元素new_node。 a1 a2 ai-1 ai an …… a1 a2 ai-1 new node a