数据结构之顺序表.ppt

SCIE,UniversityofElectronicScienceandTechnologyofChina,1,第二章线性结构,线性表堆栈队列串二维数组,SCIE,UniversityofElectronicScienceandTechnologyofChina,2,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学生成绩表,SCIE,UniversityofElectronicScienceandTechnologyofChina,3,2.1线性表,逻辑结构：元素及元素之间的关系为线性；,（1）有且仅有一个开始节点（该节点只有一个直接后继节点，没有直接前趋节点）,（2）有且仅有一个结束节点（该节点只有一个直接前趋节点，没有直接后继节点）,（3）其余节点有且仅有一个直接前趋和一个直接后继,SCIE,UniversityofElectronicScienceandTechnologyofChina,4,2.1线性表,线性表不同的实现方式：2.1.1顺序表数组存储顺序表定义顺序表基本操作：遍历、插入、删除顺序表算法分析2.1.2单链表2.1.3双向链表链接存储2.1.4循环链表,SCIE,UniversityofElectronicScienceandTechnologyofChina,5,2.1.1顺序表,一、定义采用顺序存储结构的线性表通常称为顺序表用一组地址连续的存储单元依次存储线性表的数据元素。,内存,存储地址,元素序号,12in,特点：实现逻辑上相邻物理地址相邻随机存取,Loc(a1)Loc(a1)+kLoc(a1)+(i-1)*kLoc(a1)+(n-1)*k,SCIE,UniversityofElectronicScienceandTechnologyofChina,6,2.1.1顺序表,可以借助于高级程序设计语言中的数组来表示：数组的下标与元素在线性表中的序号相对应。顺序表说明：typedefstructlist_typeelemtypedataMAXNUM;intlength;list_type;list_typelist;问题:如何获得第i的数据元素？list.datai0ilength,SCIE,UniversityofElectronicScienceandTechnologyofChina,7,2.1.1顺序表,二、顺序表的基本操作遍历（查询）插入删除,SCIE,UniversityofElectronicScienceandTechnologyofChina,8,2.1.1顺序表,遍历运算问题描述在第1个元素到第length个元素依次取值,a1a2aian,SCIE,UniversityofElectronicScienceandTechnologyofChina,9,2.1.1顺序表,for(i=0;ilength-1;j=location;j-)table-dataj+1=table-dataj;,table-datalocation=new_node;,table-length=table-length+1;,if(table-length=MAXNUM)error(1);else,if(locationtable-length)error(2);else,locationlocation1;,SCIE,UniversityofElectronicScienceandTechnologyofChina,15,2.1.1顺序表,voiderror(intnumber)switch(number)case1:printf(“thetableisfull”);break;case2:printf(“cantinsertatlocation”);break;default:printf(“unknownerror”);,SCIE,UniversityofElectronicScienceandTechnologyofChina,16,2.1.1顺序表,an,ai,删除运算问题描述：删除第i个元素算法实现分析,a1,a2,ai,an,ai1,a1,a2,ai1,ai+1,删除算法是否与插入算法一样有个方向和过程的问题？,SCIE,UniversityofElectronicScienceandTechnologyofChina,17,2.1.1顺序表,for(j=i;ji;j-)table.dataj-1=table.dataj;,关键技术分析从an开始逐个向前，每个元素向前移动从ai1开始逐个向后，每个元素向前移动,a1,a2,ai+1,ai,an,ai-1,an,an,an,for(j=table.length-1;ji;j-)table.dataj-1=table.dataj;,a1,a2,ai-1,ai,ai+1,an,for(j=i;jlength=table-length-1;,if(table-lengthlength)error(4);else,locationlocation1;,table-dataj=table-dataj+1;,SCIE,UniversityofElectronicScienceandTechnologyofChina,21,2.1.1顺序表,voiderror(intnumber)switch(number)case1:printf(“thetableisfull”);break;case2:printf(“cantinsertatlocation”);break;case3:printf(“thetableisempty”);break;default:printf(“unknownerror”);,SCIE,UniversityofElectronicScienceandTechnologyofChina,22,2.1.1顺序表,编写算法的一般步骤：1、分析问题描述输入，输出及模块功能等2、分析算法实现的总体框架，关键问题的突破方法3、核心算法的实现4、算法补充完善，如：增加算法有效性的保护措施越界判断等,SCIE,UniversityofElectronicScienceandTechnologyofChina,23,2.1.1顺序表,数组顺序存储结构的特点元素随机获取特性。存取时间短，存取时间与位置无关算法效率（时间复杂度）：元素更动的搬移性平均N/2次的搬移算法效率,O(1),O(n),SCIE,UniversityofElectronicScienceandTechnologyofChina,24,2.1.1顺序表,例：设线性表的元素个数为N，请计算插入一个节点需要移动的节点的平均个数？,观察：在表首插入一个节点，需要搬移的节点个数为,在ai处插入一个节点，则需要搬移的节点个数为,a1,a2,ai-1,ai,an,ai+1,在a1后插入一个节点，需要搬移的节点个数为,在各处插入节点的概率为,平均搬移节点个数为,N,1,N,N,1,(N-1),N,1,(N-2