第2章线性表A.ppt

《第2章线性表A.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、上堂课要点回顾数据结构课程——涉及数学、计算机硬件和计算机软件数据结构定义——指互相有关联的数据元素的集合，用D_S=(D,S)或S=(D,R)表示。数据结构内容——数据的逻辑结构、存储结构和运算算法效率指标——时间效率和空间效率1数据结构课程的内容逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构2第2章线性表第3章栈和队列第4章串第5章数组和广义表线性结构若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继。可表示为：（a1,a2,……,an）线性结构的定义：（逻辑、存储和运算）3线性结构的特点：①只有一个

2、首结点和尾结点；②除首尾结点外，其他结点只有一个直接前驱和一个直接后继。线性结构表达式：（a1,a2,……,an）线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是------线性表简言之，线性结构反映结点间的逻辑关系是一对一的见第2章4第2章线性表2.1线性表的逻辑结构2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4应用举例作业5（a1,a2,…ai-1，ai,ai＋1，…,an）2.1线性表的逻辑结构1.线性表的定义：用数据元素的有限序列表示n=0时称为数据元素线性起点ai的直接前驱ai的直接后继下标，是元素的序号，表示元

3、素在表中的位置n为元素总个数，即表长空表线性终点6例1分析26个英文字母组成的英文表（A,B,C,D,……,Z）学号姓名性别年龄班级2001011810205于春梅女182001级电信016班2001011810260何仕鹏男182001级电信017班2001011810284王爽女182001级通信011班2001011810360王亚武男182001级通信012班：：：：：例2分析学生情况登记表数据元素都是记录;元素间关系是线性数据元素都是字母;元素间关系是线性同一线性表中的元素必定具有相同特性7练：判断下列叙述的正误：1.数据的逻辑结构是指数据元素之间的逻辑

4、关系，是用户按使用需要建立的。2.线性表的逻辑结构定义是唯一的，不依赖于计算机。3.数据结构是指相互之间存在一种或多种关系的数据元素的全体。4.线性结构反映结点间的逻辑关系是一对一的。一维向量是线性表，但二维或N维数组不是。“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。√×√√××82.2线性表的顺序表示和实现2.2.1顺序表的表示2.2.2顺序表的实现2.2.3顺序表的运算效率分析本节小结作业92.2.1顺序表的表示用一组地址连续的存储单元依次存储线性表的元素，可通过数组V[n]来实现。把逻辑上相邻的数据元素存储在物

5、理上相邻的存储单元中的存储结构。线性表的顺序表示又称为顺序存储结构或顺序映像。顺序存储定义：顺序存储方法：简言之，逻辑上相邻，物理上也相邻10线性表顺序存储特点：1.逻辑上相邻的数据元素，其物理上也相邻；2.若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标）。计算方法是（参见存储结构示意图）：设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为：LOC(ai)=LOC(a1)+L*（i-1）LOC(ai+1)=LOC(ai)+L注意：C语言中的数组的下标从0开始，

6、即：V[n]的有效范围是V[0]～V[n-1]11线性表的顺序存储结构示意图a1a2……aiai+1……an地址内容元素在表中的位序1i2n空闲区i+1Lb=LOC(a1)b+Lb+(i-1)Lb+(n-1)Lb+(max-1)L12一个一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是９８，则Ｍ[３]的第一个字节的地址是113例1因此：LOC(M[3])=98+5×(3-0)=113解：地址计算通式为：LOC(ai)=LOC(a1)+L*（i-1）13用数组V来存放26个英文字母组成的线

7、性表（a，b，c，…，z），写出在顺序结构上生成和显示该表的C语言程序。voidbuild()/*字母线性表的生成，即建表操作*/{inti;V[0]='a';for(i=1;i<=n-1;i++)V[i]=V[i-1]+1;}核心语句：法1V[i]=V[i-1]+1;法2V[i]=’a’+i;法3V[i]=97+i;例214voidmain(void)/*主函数，字母线性表的生成和输出*/{n=26;/*n是表长，是数据元素的个数，而不是V的实际下标*/build();display();}voiddisplay()/*字母线性表的显示，即读表操作*/{inti

8、;for(