第02章线性表A.ppt

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

1、第1章绪论第2章线性表第3章栈和队列第4章串第5章数组和广义表第6章树和二叉树第7章图第9章查找第10章排序目录1数据结构课程的起点什么是线性结构？2线性结构的定义：若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。可表示为：（a1,a2,……,an）简言，线性结构反映结点间的逻辑关系是。特点①只有一个首结点和尾结点；特点②除首尾结点外，其他结点只有一个直接前驱和一个直接后继。线性结构包括：线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是------线性表一对一(1

2、:1)3第2章线性表2.1线性表的逻辑结构2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4应用举例4（a1,a2,…ai-1，ai,ai＋1，…,an）2.1线性表的逻辑结构线性表的定义：用数据元素的有限序列表示n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长。n≥0空表线性终点5（A,B,C,D,……,Z）学号姓名性别年龄班级012003010622陈建武男192003级电信科0301班012003010704赵玉凤女182003级电信科0302班

3、012003010813王泽男192003级电信科0303班012003010906薛荃男192003级电信科0304班012003011018王春男192003级电信科0305班：：：：：例2分析学生情况登记表是什么结构。分析：数据元素都是同类型（记录），元素间关系是线性的。分析：数据元素都是同类型（字母），元素间关系是线性的。注意：同一线性表中的元素必定具有相同特性！例1分析26个英文字母组成的英文表是什么结构。6“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。×是指各元素具有相同的数

4、据类型试判断下列叙述的正误：72.2线性表的顺序表示和实现2.2.1顺序表的表示2.2.2顺序表的实现2.2.3顺序表的运算效率分析82.2.1顺序表的表示用一组地址连续的存储单元依次存储线性表的元素。把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。线性表的顺序表示又称为顺序存储结构或顺序映像。顺序存储定义：顺序存储方法：特点：逻辑上相邻的元素，物理上也相邻可以利用数组V[n]来实现注意：在C语言中数组的下标是从0开始，即：V[n]的有效范围是从V[0]～V[n-1]91.逻辑上相邻的数据元素，其物理上也相邻；2.若已

5、知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组V[n]的下标）。设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为：LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a1)+L*（i-1）对上述公式的解释如图所示线性表顺序存储特点：10a1a2……aiai+1……an地址内容元素在表中的位序1i2n空闲区i+1Lb=LOC(a1)b+Lb+(i-1)Lb+(n-1)Lb+(max-1)LLOC(ai)=LOC(a1)+L*（

6、i-1）线性表的顺序存储结构示意图下标起点是111设有一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是98，则Ｍ[３]的第一个字节的地址是多少？答案：113但此题要注意下标起点是从0开始：LOC(M[3])=98+5×(4-1)=113解：已知地址计算通式为：LOC(ai)=LOC(a1)+L*（i-1）例112charV[30];voidbuild()/*字母线性表的生成，即建表操作*/{inti;V[0]='a';for(i=1;i<=n-1;i++)

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

8、rintf("%c",v[i]);printf("");}执行结果：abcdefghijklmnopqrstuvwxyz142.2.2顺序表的实现（或操作）数据结构的基本运算：修改、插入、删除、查找、排序1)修改:通过数组的下标便