02 2 线性表1-顺序表.ppt

OS * 数据结构 深圳大学 计算机与软件学院 白鉴聪 * 第二章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示和实现 * 上节复习 数据、数据元素、数据对象、数据结构的概念，P4 四种数据结构：集合、线性、树形、图状 数据的物理结构和逻辑结构，P6 数据类型和抽象数据类型，P7 两者实质上是同一个概念 抽象数据类型用（D，S，P）三元组表示 数据对象、数据关系、基本操作 算法是对特定问题求解步骤的一种描述，是一有限长的操作序列 算法特性：有穷性、确定性、可行性、输入和输出 时间复杂度和空间复杂度 * 写出以下代码的时间复杂度 for (i=1; i POW（2, n）; i++) //POW(x, y)函数表示x的y次幂 a = a+100; c. for (i=1; i=n; i++) for (j=1; j=i; j++) a = a + 1; d. i = s = k = 1; while ( k = s ) { if (i=n) { i++; s*=i; } k ++; } 练习 * 2.1 线性表的类型定义 线性表概念 线性表是n个数据元素的有限序列 线性数据结构的特点 数据同一性，同一个线性表的数据属同一类数据对象 顺序性，数据之间存在序偶关系 (a1, a2,…ai-1, ai, ai+1,…an-1, an) 其中,ai是表中元素,i表示元素ai的位置,n是表的长度 * 2.2 线性表的类型定义 线性表概念 数据同一性 线性表中的元素具有相同的特性，属于同一数据对象，如： 26个字母的字母表: (A,B,C,D,…,Z) 近期每天的平均温度:(30℃, 28℃, 29℃,…) * 2.1 线性表的类型定义 线性表概念 数据的顺序性 存在惟一的一个被称作“第一个”的数据元素(如“１”) 存在惟一的一个被称作“最后一个”的数据元素(如“６”) 除第一个元素外，每个数据元素均只有一个前驱 除最后一个元素外，每个数据元素均只有一个后继(next)(如“1”的next是“2”, “2”的next是“3”) 1 2 3 4 5 6 * 2.1 线性表的类型定义 线性表的ADT定义 ADT List{ 数据对象：数据元素同属一个集合 数据关系：序偶关系 基本操作： Init创建、Destroy销毁、 Clear清空、Empty是否为空、 Length取表长度、Get取表元素、Locate查找元素 Prior取元素前驱、Next取元素后继 Insert插入元素、Delete删除元素 Traverse遍历表 } * 2.2 顺序表 顺序表概念 顺序表是线性表的顺序表示，用一组地址连续的存储单元依次存储线性表的数据元素 A B C D E … Y Z b b+1 b+2 b+3 b+4 … b+24 b+25 * 2.2 顺序表 顺序表的数据位置 顺序表数据元素的位置： LOC(a i) = LOC( a i-1 ) + l LOC(a i) = LOC(a1)+(i-1)*l l表示元素占用的内存单元数 a1 a2 … a i … … … an 1 2 … i … … … n b b+l … b+(i-1)*l … … … b+(n-1)*l idle * 2.2 顺序表 顺序表的定义 采用C语言中动态分配的一维数组表示顺序表 #define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量 #define LISTINCREMENT 10 // 线性表存储空间的分配增量 Typedef struct { ElemType *elem; // 存储空间基址 int length; // 当前长度 int listsize; // 当前分配的存储容量(元素数) } Sqlist; * 2.2 顺序表 顺序表的创建 Status InitList_Sq(Sqlist L) { L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if (!L.elem) exit(OVERFLOW); // 存储分配失败 L.l