数据结构-第2章-线性表演示课件

.,第2章 线性表,2.1 线性表的逻辑结构 2.2 线性表的顺序存储结构表示2.3 线性表元素的操作2.4 线性表应用举例2.5 小结 习题2,.,2.1 线性表的逻辑结构,2.1.1 线性表的定义线性表是由n个数据元素的有限序列(a1，a2，an)组成的，其中每一个数据元素ai的具体含义可以按不同的情况和要求定义具体的内容，它可以是一个数、一个符号、一串文字，甚至是其他更复杂的信息。例如，英文字母表(A, B, C, , X, Y, Z)是一个线性表，其中的数据元素是单个字母。又如，某企业职工的姓名可构造成一个线性表，表中元素是姓名。以上的线性表类型主要表示单一的数据元素。较复杂的线性表中，一个数据元素可以由若干个数据项组成。我们常把由多个数据项组成的数据元素称作记录(Record)。,.,例如，一个班级某门学科的成绩单可构成一个线性表，如表2-1所示，表中每一个记录包含三个数据项：学号、姓名、数据结构。其中用以区别各个记录或数据元素的数据项的值称为关键字(KEY)。在表2-1中，关键字可选用学号，因为学号可以惟一地标识每一个学生，从而排除了选姓名时同名同姓的非惟一性。综合上述例子，我们可以用如下形式来描述线性表：一个线性表是n(n0)个数据元素a1，a2，an的有限序列。若n=0，则表示一个空表，表示无数据元素；若n0，则每个ai代表一个结点，除a1和an外，有且仅有一个直接前趋和一个直接后继数据元素，,.,即ai(其中1 i=i; j-) vj+1=vj;/* 从表末元素到序号为i的元素逐个下移 */ vi=t; /* 新元素插入 */ n+;/* 修正表长 */ else vl=t; n=1; /* 表空，插入元素为线性表的第一个元素 */ ,.,2.3.2 线性表元素删除操作 图2-5给出了在有序线性表中删除一个元素的框图，其中被删除元素所在的第i个位置已经给出。,.,图2-5 有序线性表的删除,.,下面给出有序线性表删除一个元素的算法，被删除的元素被保留在out中以防丢失。/* 有序线性表元素的删除 */DELEGLIST(v, i, n)/* v是有序线性表，i是被删除元素的位置，n是线性表的长度 */ int j; out=vi; for(j=i;j=n-1; j+) vj=vj+1;/* 从i+1到n位置上的元素逐个上移 */ n-;,.,2.3.3 线性表元素定位操作图2-6(a)所示的是无序线性表，其数据元素在线性表中的存放是任意的；图2-6(b)所示的是有序线性表，其数据元素的排列按英文字母的字母顺序从小到大存放。有序线性表有如下特点，设V为有序线性表，数据元素ai值的相邻关系为ai-1aiai+1。图2-7所示是在无序线性表上进行查找的流程图。,.,图2-6 无序和有序线性表(a) 无序线性表；(b) 有序线性表,.,图2-7 无序线性表的查找算法框图,.,无序线性表的查找算法如下：/* 无序线性表的查找算法 */ ESEARCH(v,n,t)/* v是无序线性表，n是线性表的长度，t是被查找的记录 */ int i; vn+1=t; /* 建立无序查找的结束标志 */ i=1; while(vi!=t) i+;,.,if(i=n) return(search, true); else return(search, false);图2-8给出了有序线性表的查找算法框图。,.,图2-8 有序线性表的查找算法框图,.,有序线性表的查找算法如下： /* 有序线性表的查找算法 */EGSEARCH(v, n,t )/* v是有序线性表，n是线性表的长度，t是被查找的记录 */char search6; int i; vn+1=;/* 设置查找的结束标志 */ i=1;,.,while(vit) i+; if(vi=t) printf(search,true); else printf(search, false);,.,2.4 线性表应用举例,图2-9给出了在有序线性表中查找并删除数据元素t的程序流程框图。,.,图2-9 在线性表中查找并删除元素t,.,下面给出相应的算法。A1(v, n,