第二章线性表1

1,第1章绪论第2章线性表第3章栈和队列第4章串第5章数组和广义表第6章树和二叉树第7章图第9章查找第10章排序,目录,数据结构课程的起点：,什么是线性结构？,3,线性结构的定义：,若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。可表示为：（a1,a2,an）,简言之，线性结构反映结点间的逻辑关系是的。,特点只有一个首结点和尾结点；特点除首尾结点外，其他结点只有一个直接前驱和一个直接后继。,线性结构包括：线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是-,线性表,一对一(1:1),4,第2章线性表,2.1线性表的逻辑结构2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4应用举例,5,（a1,a2,ai-1，ai,ai1，,an）,2.1线性表的逻辑结构,线性表的定义：用数据元素的有限序列表示,n=0时称为,数据元素,线性起点,ai的直接前趋,ai的直接后继,下标，是元素的序号，表示元素在表中的位置,n为元素总个数，即表长。n0,空表,线性终点,6,（A,B,C,D,Z）,例2分析学生情况登记表是什么结构。,分析：数据元素都是同类型（记录），元素间关系是线性的。,分析：数据元素都是同类型（字母），元素间关系是线性的。,注意：同一线性表中的元素必定具有相同特性！,例1分析26个英文字母组成的英文表是什么结构。,7,2.2线性表的顺序表示和实现,2.2.1顺序表的表示2.2.2顺序表的实现2.2.3顺序表的运算效率分析,8,2.2.1顺序表的表示,用一组地址连续的存储单元依次存储线性表的元素。,把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。,线性表的顺序表示又称为顺序存储结构或顺序映像。,顺序存储定义：,顺序存储方法：,特点：,逻辑上相邻的元素，物理上也相邻,可以利用数组Vn来实现,注意：在C语言中数组的下标是从0开始，即：Vn的有效范围是从V0Vn-1,9,1.逻辑上相邻的数据元素，其物理上也相邻；2.若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组Vn的下标）。,设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为：LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a1)+L*（i-1）,对上述公式的解释如图所示,线性表顺序存储特点：,10,地址内容元素在表中的位序,1,i,2,n,空闲区,i+1,L,b=LOC(a1),b+L,b+(i-1)L,b+(n-1)L,b+(max-1)L,LOC(ai)=LOC(a1)+L*（i-1）,线性表的顺序存储结构示意图,11,设有一维数组，下标的范围是到，每个数组元素用相邻的个字节存储。存储器按字节编址，设存储数组元素的第一个字节的地址是，则的第一个字节的地址是多少？,113,但此题要注意下标起点略有不同：LOC(M3)=98+5(4-1)=113,解：已知地址计算通式为：,LOC(ai)=LOC(a1)+L*（i-1）,例1,12,charV30;voidbuild()/*字母线性表的生成，即建表操作*/inti;V0=a;for(i=1;i=n-1;i+)Vi=Vi-1+1;,核心语句：法1Vi=Vi-1+1;法2Vi=a+i;法3Vi=97+i;,例2,用数组V来存放26个英文字母组成的线性表（a，b，c，z），写出在顺序结构上生成和显示该表的C语言程序。,13,voidmain(void)/*主函数，字母线性表的生成和输出*/intn=26;/*n是表长，是数据元素的个数，而不是V的实际下标*/build();display();,voiddisplay()/*字母线性表的显示，即读表操作*/inti;for(i=0;i=i;j-)aj+1=aj;ai=x;n+;,/元素后移一个位置,/插入x,/表长加1,核心语句：,2)插入,16,在线性表的第i个位置前插入一个元素的示意图如下：,插入25,17,实现步骤：将第i+1至第n位的元素向前移动一个位置；表长减1。注意：事先需要判断，删除位置i是否合法?应当有1in或i=1,n,删除线性表的第i个位置上的元素,for(j=i+1;j=L.listsize)L.listsize=List_Increment;,P23的malloc()函数与P24的realloc()函数有什么不同？,25,动态数组简介,先为顺序表空间设定一个初始分配量，一旦因插入元素而空间不足时，可为顺序表增加一个固定长度的空间增量。,#defineLIST_INIT_SIZE100/存储空间的初始分配量#defineLISTINCREMENT10/存储空间的分配增量TypedefstructElemType*elem;/表基址(用指针*elem表示）intlength;/表长度（表中有多少个元素）intlistsize;/当前分配的表尺寸（字节单位）SqList;,注：三个分量可简写为：L.elemL.lengthL.listsize,存储结构描述如下（见教材P22）：,26,线性表的定义（见教材P19）,ADTList数据对象：D=ai|aiElemSet,i=1,2,n,n0数据关系：R1=|ai1,aiD,i=2,n基本操作：,初始化、撤销、清空、判空；求表长、表头、表尾、前趋、后继；读元素、查找（含定位）、遍历；插入、删除,ADTList,27,线性表的基本操作如何表示？（见教材P19）,InitList(/“看”表中全部元素（遍历）,初始化、撤销、清空、判空；求表长、表头、表尾、前趋、后继；读元素、查找（含定位）、遍历；插入、删除,28,sizeof(x)算符的意思是：计算变量x的长度(字节数),malloc(m)函数的意思是：新开一片大小为m字节的连续空间，并把该区首址作为函数值。,StatusInitList_Sq(SqList/InitList_Sq,动态创建一个空顺序表的算法：,29,realloc(*p,newsize)函数的意思是：新开一片大小为newsize的连续空间，并把以*p为首址的原空间数据都拷贝进去。,动态顺序表的插入算法StatusListInsert_Sq(SqList/检验i值的合法性,if(L.lengthL.listsize)/若表长超过表尺寸则要增加尺寸newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);,if(newbase=NULL)exit(OVERFLOW);/分配失败则退出并报错L.elem=newbase;/重置新基址L.listsize=L.listsize+LISTINCREMENT;/增加表尺寸,30,q=/插入e,+L.length;/增加1个数据元素，则表长+1,returnOK;/ListInsert_Sq,动态数组的核心是realloc(void*ptr,newsize)函数！,31,动态顺序表的删除算法StatusListDelete_Sq(SqList/i值不合法，返回,p=/被删除元素的值赋给e,q=L.elem+L.length-1;/q是表尾的位置for(+p;p=q;p+)*(p-1)=*p;/待删元素后面的统统前移,-L.length;/表长-1,returnOK;/ListDelete_Sq,32,顺序表操作的典型例子,教材例2-1：求两个线性表的“并”，即：LAULB=?,算法至少有两种：LA和LB都是无序表，则从LB中取元素逐一与L