资源描述：
《数据结构(c)第2章线性表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章线性表第1章介绍了几种基本逻辑结构：线性结构、树形结构和图结构。线性结构是最简单、最基本的数据结构，本章讨论线性表的基本概念、存储结构以及相关运算。主要内容：线性表的基本概念线性表的顺序存储结构及实现线性表的链表存储结构及实现线性表的应用NCU-ZQP12.1线性表的基本概念现实中存在大量线性表的实例。例如：大写英文字母表：(A,B,C,…,Y,Z)；一周中7天(星期一，星期二，…，星期日)；MP3播放器中的若干个歌曲的目录。怎样查找自己喜欢的歌曲？怎样输入新的曲目？删除过时曲目？这就是本节所研究的内容：线性表及其运算。NCU-ZQP22.1.1线性表的
2、定义线性表（LinearList）是n(n≥0)个数据元素的有限序列。记作：(a1，a2，…，an)ai(1≤i≤n)属于同一数据对象，具有相同的数据类型。n代表表长，即线性表中数据元素的个数。当n=0时，线性表为空表。对于ai:当1＜i≤n时，它有一个直接前驱ai−1；当1≤i＜n时，它有一个直接后继ai+1。NCU-ZQP32.1.2线性表的抽象数据类型ADTLinear_list{数据对象：D={ai
3、ai∈ElemSet,i=1,2,…,n,n≥0；}数据关系：R={
4、ai-1,ai∈D,i=2,3,…,n}基本操作：初始化空线性表;求线性表
5、表长;取线性表的第i个元素;在线性表的第i个位置插入元素x;删除线性表的第i个元素;修改线性表中的第i个元素;按某种要求重排线性表中各元素的顺序;按某个特定值查找线性表中的元素;等等;}ADTLinear_list;NCU-ZQP42.2线性表的顺序存储结构及实现为了用计算机解决线性表问题，需要考虑数据信息如何在计算机内存储。计算机可以用多种不同的方法来存储数据信息，常用的方法是顺序存储结构和链式存储结构。NCU-ZQP52.2.1线性表的顺序存储结构顺序存储结构是最简单常用的方法。顺序存储结构也称为向量存储。向量是内存中一批地址连续的存储单元。线性表的顺序存储结构，
6、要求逻辑上相邻的数据元素在物理位置上也一定是相邻的，如图所示。NCU-ZQP6假设a1的地址为LOC(a1)，每个元素占L个字节（本例L为2），ai的存放地址为：LOC(ai) =LOC(a1) +L*(i−1)只要确定了线性表存储的起始位置，线性表中任一数据元素的位置都可确定，可以随机存取。特点：逻辑上相邻—物理地址相邻；可以随机存取数据；NCU-ZQP7为了更好地体现信息隐蔽原则以及数据抽象原则，一维数组elem[]和线性表的长度length封装在一个结构体中。constintMAXSIZE=100;typedefintElemType;structSqList0
7、{ElemTypeelem[MAXSIZE];//一维数组intlength;//表的实际长度}SqList0就是顺序存储结构的类型标识符。在高级语言环境中使用一维数组来模拟实现顺序存储结构。NCU-ZQP81．在类中使用静态一维数组静态一维数组是指在声明定义数组时，所给出数组的大小是确定的。数组的大小留有余地。constintMAXSIZE=100;typedefintElemType;classSqList1{private:ElemTypeelem[MAXSIZE];//一维数组intlength;//线性表长度public:………;//其他成员函数;}；在面向
8、对象的程序设计中，通常将数据元素的存储结构和对数据的操作封装在一个类之中。NCU-ZQP92．在类中使用动态一维数组动态一维数组是指在声明定义数组时用指针表示，数组的大小没有确定。在数据成员中除数组elem、表长length还给出表的容量maxlen。classSqList2{private:ElemType*elem；//用指针表示一维数组intlength;//表的实际长度intmaxlen;//表的最大长度，容量public:………;//其他成员函数};在面向对象的程序设计中，通常将数据元素的存储结构和对数据的操作封装在一个类之中。NCU-ZQP102.2.2顺
9、序表类定义顺序表类是指采用顺序存储结构来表示线性表的类。线性表采用顺序存储结构，其数组和线性表长可以作为类的数据成员。线性表各种操作的处理可以作为类的函数成员，且大多是公有函数，目的是提供类对外部的接口供调用。一个简明的顺序表类：SqList。NCU-ZQP11//顺序表类SqList的定义typedefintElemType;//数据元素的类型constintMAXSIZE=100;//数组的容量classSqList{private:ElemTypeelem[MAXSIZE];//数组intlength;//线性表长public:SqList(v
