资源描述：
《第2章_线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第2章线性表2.1线性表的基本概念2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4应用举例12.1线性表的基本概念１、线性表它是一种最简单的线性结构。是一种可以在任意位置进行插入和删除数据元素操作的，由n（n≥0)个相同类型数据元素a0,a1,…,an-1组成的线性结构。23（a0,a1,…ai-1，ai,ai＋1，…,an-1）线性表的逻辑结构：n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长。n≥0空表线性终点（A,B,C,D,……,Z）4学号姓名性别年龄班级012003010622陈建武男1
2、92003级电信0301班012003010704赵玉凤女182003级电信0302班012003010813王泽男192003级电信0303班012003010906薛荃男192003级电信0304班012003011018王春男192003级电信0305班：：：：：例2分析学生情况登记表是什么结构。分析：数据元素都是同类型（记录），元素间关系是线性的。分析：数据元素都是同类型（字母），元素间关系是线性的。注意：同一线性表中的元素必定具有相同特性！例1分析26个英文字母组成的英文表是什么结构。２、线性表抽象数据类型它包括两个方面：数据集合：｛a0,a1,…,an-1｝ai的数据
3、类型为DataType操作集合：(1)ListInitiate(L)初始化线性表(2)ListInsert(L,i,x)插入数据元素(3)ListLength(L)求当前数据元素个数(4)ListDelete(L,i,x)删除数据元素(5)ListGet(L,i,x)取数据元素等53、线性表的存储结构(1)顺序存储结构（P21）:它是使用一片地址连续的有限内存单元空间存储数据元素的一种计算机存储数据方法。特点：(任意两个在逻辑上相邻的数据元素在物理位置上也必然相邻)逻辑上相邻的元素，物理上也相邻。(2)链式存储结构(P27):它是把数据元素和指针定义成一个存储体，使用指针把发生联
4、系的数据元素链接起来的一种计算机存储数据方法。特点：任意两个在逻辑上相邻的数据元素在物理上不一定相邻，数据元素的逻辑次序是通过链中的指针链接实现的。62.2线性表的顺序表示和实现7一、顺序表的存储结构二、顺序表的实现三、顺序表的运算效率分析一、顺序表的存储结构表示1、顺序表：用一组地址连续的存储单元依次存储线性表的各个数据元素。即采用顺序存储结构的线性表。它通常采用静态数组实现数据元素的存储。8可以利用数组V[n]来实现注意：在C语言中数组的下标是从0开始，即：V[n]的有效范围是从V[0]～V[n-1](1)逻辑上相邻的数据元素，其物理上也相邻；(2)若已知表中首元素在存储器中
5、的位置，则其他元素存放位置亦可求出（利用数组V[n]的下标）。9设首元素a0的存放地址为LOC(a0)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为：LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a0)+L*i对上述公式的解释如图所示2、线性表顺序存储特点：10a0a1……aiai+1……an-1地址内容元素在表中的位序0i1n-1空闲区i+1Lb=LOC(a0)b+Lb+iLb+(n-1)Lb+(MaxSize-1)LLOC(ai)=LOC(a0)+L*i3、线性表的顺序存储结构示意图设有一维数组Ｍ，下标的范围是０到９
6、，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是９８，则Ｍ[３]的第一个字节的地址是多少？11113LOC(M[3])=98+5×3=113解：已知地址计算通式为：LOC(ai)=LOC(a0)+L*i例112charV[30];voidbuild()/*字母线性表的生成,即建表操作*/{inti;V[0]='a';for(i=1;i<=n-1;i++)V[i]=V[i-1]+1;}程序2-1用数组V来存放26个英文字母组成的线性表（a，b，c，…，z），写出在顺序结构上生成和显示该表的C语言程序。13voidmain()/*主函数
7、，字母线性表的生成和输出*/{intn=26;/*n是表长，是数据元素的个数，而不是V的实际下标*/build();display();}voiddisplay()/*字母线性表的显示，即读表操作*/{inti;for(i=0;i<=n-1;i++)printf("%c",v[i]);printf("");}出错了：为何呢？应定义为全局变量执行结果：abcdefghijklmnopqrstuvwxyz二、顺序表的实现（或操作）14数据结构的基本运算：修改、插入、删除、查找、排
