[其它课程]c2-线性表一.ppt

教学内容 线性表的类型定义 线性表的顺序表示和实现 线性表的类型定义 特点 存在唯一的被称为“第一个”的数据元素。即首元素或者头元素。 存在唯一的被称为“最后一个”的数据元素。即尾元素。 除首尾元素外，其他数据元素只有一个直接前驱和一个直接后继。 简言之，线性结构反映结点间的逻辑关系是一对一的。 线性表的类型定义 线性结构包括： 线性表、堆栈、队列、字符串、数组等。 其中最典型、最常用的是——线性表。 线性表 由n(n≥0)个数据元素a1 , a2, …an组成的有限序列。 其中数据元素的个数n定义为表的长度。 当n=0时称为空表。 线性表的类型定义 常常将非空的线性表(n0)记作： (a1，a2，…an) 这里的数据元素ai(1≤i≤n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。 线性表的类型定义 例1：分析26 个英文字母组成的英文表是什么结构。 分析：数据元素都是同类型（字母）， 元素间关系是线性的。 线性表的类型定义 例2 分析学生情况登记表是什么结构。 在复杂的线性表中，一个数据元素可以由若干个数据项组成。在这种情况下，常把数据元素称为记录，含有大量记录的线性表又称文件。 分析：数据元素都是同类型(记录)，元素间关系是线性的。 线性表的类型定义 线性表的逻辑结构： 线性表的类型定义 抽象数据类型定义 线性表的类型定义 抽象数据类型定义 线性表的类型定义 抽象数据类型定义 线性表的类型定义 算法2-1 线性表的类型定义 算法2-2 线性表的类型定义 线性表的类型定义 算法分析 上述两个算法的时间复杂度取决于抽象数据类型List定义中基本操作的执行时间。 假如GetElem和ListInsert这两个操作的执行时间和表长无关，LocateElem的执行时间和表长成正比 算法2-1的时间复杂度为O(ListLength(LA)*ListLength(LB)), 算法2-2的时间复杂度为O(ListLength(LA)+ListLength(LB)), 线性表的顺序表示和实现 顺序存储结构 把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。 顺序存储结构特点 逻辑上相邻的数据元素，其物理上也相邻； 物理顺序与逻辑顺序相同，可随机存取。 若已知表中首元素在存储器中的位置，则其 他元素存放位置亦可求出（利用下标i）。 线性表的顺序表示和实现 例： 线性表的顺序表示和实现 线性表的顺序表示和实现 高级程序设计语言中，数组类型也有随机存取的特性。所以通常用数组来描述数据结构中的顺序存储结构。 在此，由于线性表的长度可变，且所需最大存储空间随问题不同而不同，则在C语言中可用动态分配的一维数组。 线性表的顺序表示和实现 线性表的动态分配顺序存储结构 线性表的顺序表示和实现 算法2-3：初始化 在这种结构中，容易实现线性表的某些操作。 只是要特别注意C语言中数组下标从”0”开始，则表中第i个数据元素的下标是(i-1)。 线性表的顺序表示和实现 线性表的插入操作 线性表的插入操作是指在线性表的第i-1个元素和第i个数据元素之间插入一个新的元素。 插入新元素后线性表的数据元素ai-1和ai之间的逻辑关系发生了变化。 在线性表的顺序存储结构中，由于逻辑上相邻的数据元素在物理位置上也是相邻的，因此，除非i=n+1，否则必须移动元素才能反映这个逻辑关系的变化。 线性表的顺序表示和实现 线性表的顺序表示和实现 实现步骤： 将第n至第i位的元素向后移动一个位置； 将要插入的元素写到第i个位置； 表长加1。 注意事先应判断: 插入位置i是否合法? 表是否已满? 线性表的顺序表示和实现 算法2-4 Status ListInsert_Sq(SqList *L，int i ，ElemType e){ if(i1||iL.length+1) return ERROR; if(L.length=L.listSize){ newbase=(ElemType *)realloc (L.elem, (L.listsize+LISTINCREMENT)* sizeof(ElemType)); If(! newbase) exit(OVERFLOW); L.elem = newbase; L.li