电子2-3线性表

1物料管理1数据结构2物料管理2数据结构学时数：48（32＋16）学分：3教材：严蔚敏等，数据结构（C语言版），清华大学出版社，1997年4月（配题集）参考书：[1]殷人昆等，数据结构（用面向对象方法与C++描述），清华大学出版社，1999年7月。￥26[2]殷人昆等，数据结构习题解析，清华大学出版社，2002年4月。￥26[3]李春保，数据结构习题与解析（C语言篇），清华大学出版社，2001年1月。￥28[4]丁宝康等，数据结构自学考试指导，清华大学出版社，2001年5月。￥233物料管理3数据结构内容安排章内容学时章内容学时1绪论27图62线性表48动态存储管理略3栈和队列69查找44串（自学）210内部排序45数组和广义表（自学）411外部排序略6树和二叉树612文件略实验：课内上机（16规定内容）+课外上机（24平时作业中编程题验证）4物料管理4数据结构数据结构课程的内容逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构5物料管理5数据结构线性结构的定义：若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。→可表示为：（a1,a2,……,an）简言之，线性结构反映结点间的逻辑关系是的。特点①只有一个首结点和尾结点；特点②除首尾结点外，其他结点只有一个直接前驱和一个直接后继。线性结构包括：线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是------线性表一对一(1:1)6物料管理6数据结构第2章线性表2.1线性表的逻辑结构2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4应用举例7物料管理7数据结构（a1,a2,…ai-1，ai,ai＋1，…,an）2.1线性表的逻辑结构线性表的定义：用数据元素的有限序列表示n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长。n≥0空表线性终点8物料管理8数据结构（A,B,C,D,……,Z）学号姓名性别年龄班级012003010622陈建武男192003级电子0301班012003010704赵玉凤女182003级电子0302班012003010813王泽男192003级电子0303班012003010906薛荃男192003级电子0304班012003011018王春男192003级电子0305班：：：：：例2分析学生情况登记表是什么结构。分析：数据元素都是同类型（记录），元素间关系是线性的。分析：数据元素都是同类型（字母），元素间关系是线性的。注意：同一线性表中的元素必定具有相同特性！例1分析26个英文字母组成的英文表是什么结构。9物料管理9数据结构“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。×是指各元素具有相同的数据类型试判断下列叙述的正误：10物料管理10数据结构2.2线性表的顺序表示和实现2.2.1顺序表的表示2.2.2顺序表的实现2.2.3顺序表的运算效率分析11物料管理11数据结构2.2.1顺序表的表示用一组地址连续的存储单元依次存储线性表的元素。把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。线性表的顺序表示又称为顺序存储结构或顺序映像。顺序存储定义：顺序存储方法：特点：逻辑上相邻的元素，物理上也相邻可以利用数组V[n]来实现注意：在C语言中数组的下标是从0开始，即：V[n]的有效范围是从V[0]～V[n-1]12物料管理12数据结构1.逻辑上相邻的数据元素，其物理上也相邻；2.若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组V[n]的下标）。设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为：LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a1)+L*（i-1）对上述公式的解释如图所示线性表顺序存储特点：13物料管理13数据结构a1a2……aiai+1……an地址内容元素在表中的位序1i2n空闲区i+1Lb=LOC(a1)b+Lb+(i-1)Lb+(n-1)Lb+(max-1)LLOC(ai)=LOC(a1)+L*（i-1）线性表的顺序存储结构示意图14物料管理14数据结构设有一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是９８，则Ｍ[３]的第一个字节的地址是多少？113但此题要注意下标起点略有不同：LOC(M[3])=98+5×(4-1)=113解：已知地址计算通式为：LOC(ai)=LOC(a1)+L*（i-1）例115物料管理15数据结构课堂讨论：顺序表的“宏观”算法该如何书写？———采用抽象数据类型来表示顺序表的存储结构是一维数组，如果插入的元素个数超过数组定义的长度怎么办？———采用动态分配的一维数组16物料管理16数据结构线性表的定义（见教材P19）ADTList{数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R1={ai–1,ai|ai–1,ai∈D,i=2,…,n}基本操作：初始化、撤销、清空、判空；求表长、表头、表尾、前趋、后继；读元素、查找（含定位）、遍历；插入、删除}ADTList17物料管理17数据结构线性表的基本操作如何表示？（见教材P19）InitList(&L);//建空表，初始化DestoryList(&L);//撤销表，释放内存intLengthList(L);//求表中元素个数，即表长POSITIONLocateElem(L,ElemTypee，compare());PriorElem(L,cur_e,&pre_e);//求当前元素e的前驱NextElem(L,cur_e,&next_e);//求当前元素e的后继ListInsertBefore(&L,i,e);//把e插入到第i个元素之前ListDelete(&L,i,&e);//删除第i个元素并“看”此元素ListTraverse(L,Visit());//“看”表中全部元素（遍历）初始化、撤销、清空、判空；求表长、表头、表尾、前趋、后继；读元素、查找（含定位）、遍历；插入、删除18物料管理18数据结构动态数组如何实现（见教材P22和P24）#defineList_Init_Size100//初始空间#defineList_Increment10//分配增量…………L.listsize=List_Init_Size;If(L.length=L.listsize){…………L.listsize＋=List_Increment;};P23的malloc()函数与P24的realloc()函数有什么不同？19物料管理19数据结构动态数组简介先为顺序表空间设定一个初始分配量，一旦因插入元素而空间不足时，可为顺序表增加一个固定长度的空间增量。#defineLIST_INIT_SIZE100//存储空间的初始分配量#defineLISTINCREMENT10//存储空间的分配增量Typedefstruct{ElemType*elem;//表基址(用指针*elem表示）intlength;//表长度（表中有多少个元素）intlistsize;//当前分配的表尺寸（字节单位）}SqList;注：三个分量可简写为：L.elemL.lengthL.listsize存储结构描述如下（见教材P22）：20物料管理20数据结构sizeof(x)算符的意思是：计算变量x的长度(字节数)malloc(m)函数的意思是：新开一片大小为m字节的连续空间，并把该区首址作为函数值。StatusInitList_Sq(SqList&L)//创建一个空线性表{L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));If(!L.elem)exit(OVERFLOW);//分配失败，结束程序L.length=0;//暂无元素放入，空表L.listsize=LIST_INIT_SIZE;//表尺寸=初始分配量ReturnOK;}//InitList_Sq动态创建一个空顺序表的算法：21物料管理21数据结构2.2.2顺序表的实现（或操作）数据结构的基本运算：插入、删除、查找、排序22物料管理22数据结构realloc(*p,newsize)函数的意思是：新开一片大小为newsize的连续空间，并把以*p为首址的原空间数据都拷贝进去。动态顺序表的插入算法StatusListInsert_Sq(SqList&L,inti,ElemTypee){//在顺序线性表中第i个位置之前插入新的元素eif(i1oriL.length+1)returnERROR;//检验i值的合法性if(L.length≥L.listsize)//若表长超过表尺寸则要增加尺寸{newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(newbase=NULL)exit(OVERFLOW);//分配失败则退出并报错L.elem=newbase;//重置新基址L.listsize=L.listsize+LISTINCREMENT;}//增加表尺寸23物料管理23数据结构q=&L.elem[i-1];//q为插入位置。这是没有头结点的情况for(p=L.elem[L.length-1];p=q;--p)*(p+1)=*p;//插入位置及之后的元素统统后移,p为元素位置*q=e;//插入e++L.length;//增加1个数据元素，则表长+1returnOK;}//ListInsert_Sq动态数组的核心是realloc(void*ptr,newsize)函数！24物料管理24数据结构在线性表的第i个位置前插入一个元素的示意图如下：121321242830427712132124252830427712345678123456789插入2525物料管理25数据结构动态顺序表的删除算法StatusListDelete_Sq(SqList&L,inti,ElemType&e){//在顺序表L中删除第i个元素，用e返回其值if(i1oriL.length)returnERROR;//i值不合法，返回p=&L.elem[i-1];//p是被删除元素的位置e=*p;//被删除元素的值赋给eq=L.elem+L.length-1;//q是表尾的位置for(++p;p=q;p++)*(p-1)=*p;//待删元素后面的统统前移--L.length;//表长-1returnOK;}//ListDelete_Sq26物料管理26数据结构123456789121321242528304277123456781213212428304277删除顺序表中某个指定的元素的示意图如下：顺序表插入和删除的完整程序请同学们自编。27物料管理27数据结构链式存储结构2.2节小结线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻；优点：可以随机存取表中任一元素，方便快捷；缺点：在插入或删除某一元素时，需要移动大量元素。解决问题的思路：改用另一种线性存储方式：28物料管理28数据结构顺序表操作的典型例子（自学）教材例2-1：求两个线性表的“并”，即：LAULB=?算法至少有两种：①LA和LB都是无序表，则从LB中取元素逐一与LA中所有元素比较，相同则不插入LA；②若LA和LB已经是有序表，则“归并”的时间效率可以大大提高。29物料管理29数据结构2.2.3顺序表的运算效率分析算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基本操作（最深层语句频度）T(n)=O(移动元素次数)而移动元素的个数取决于插入或删除元素的位置.思考：若插入在尾结点之