“算法与数据结构”-线性表.ppt

数 据 结 构 主讲人：李志芳 主讲单位：软件技术教研室 时间：2008~2009第二学期 线性表 知 识 点 线性数据结构的基本特征和基本运算 难 点 循环队列的特点及判断溢出的条件 利用本章的基本知识设计有效的算法解决与线性相关的应用问题 要 求 熟练掌握以下内容： 线性表顺序存储结构的基本运算和基本应用 线性表链式存储结构的基本运算和基本应用 了解以下内容： 线性表运算时间复杂性分析 数组与线性表 线性结构是软件设计中最常用也是最基本的一种数据结购，线性表是其中最基本的一种。 线性表L是n个具有相同数据类型元素a1，a2，a3，…，an组成的有限序列，记做L=（ a1，a2，a3，…，an ），其中n=0，为表的长度；当n=0时为空表，记做L=（）。 特点： 对线性表的某个元素ai来说，称其前面的元素ai-1为ai的直接前驱，称其后面的元素ai+1为ai元素的直接后继。 当i=1，2，…，n-1时，ai有且仅有一个直接后继；当i=2，3，…，n时，ai有且仅有一个直接前驱。 a1是线性表的第一个元素，an是线性表的最后一个元素，ai是线性表的第i个元素，称i为数据元素ai在线性表中的确定位置。 线性表 线性表的基本操作 初始化线性表initial_List(L)：建立线性表的初始结构，建空表。 求表的长度List_length(L)：求表中元素的个数。 按序号取元素get_element(L，i)：取出表中序号为i的元素。 按值查询List_locate(L，x)：取出指定值为x的元素。 插入元素 List_insert(L，I，x)：在表L的第i个位置上插入值为x的元素。 删除元素List_delete(L，i)：删除表L中序号为i的元素。 判空表List_empty(L)：判断表是否为空返回布尔值。 表置空List_clear(L)：将表中的元素个数设置为0。 线性表 线性表的存储方法—顺序存储 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。 设线性表的每个元素需占用m个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足一定的关系 LOC(ai+1)= LOC(ai)+m 则线性表的第i个元素的存储位置为 LOC(ai)= LOC(a1)+(i-1)*m 其中LOC(a1)是线性表的第一个数据元素a1的存储位置，通常称为起始地址（基地址）。 线性表 线性表的存储方法—顺序存储 存储地址 内存状态 序号 顺序表运算的实现 初始化 void initial_list(seqlist *L) { L-listlen=0;} 求表长 int list_length(seqlist *L) { return L-listlen;} 按序号求元素的值 void get_element(seqlist L,int i,int *x) { if(i1 || iL.listlen) error(“超出范围”)； else *x=L.data[i-1]；} 查找运算 int List_locate(seqlist L, int x) {int i; for(i=0;iL.listlen;i++) if(L.data[i]==x) return i+1; return 0; } 顺序表运算的实现 插入算法的实现 顺序表运算的实现 void List_insert(seqlist *L, int x, i) { int j; if(L-listlen==maxlen) printf(“溢出！”); else if (i1||iL-listlen+1) printf(“i值错！\n”); else { for (j=L-listlen-1 ; j=i-1 ; j--) L-data[j+1]=L-data[j]; /*将第i个及其后面元素后移*/ L