资源描述：
《第2章 线性表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、简单数据结构第二章线性表8/29/202112.1线性表的定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4顺序表和链表的比较2.5一元多项式的表示及相加SchoolofComputerandCommunication算法与数据结构8/29/20212例、学生情况登记表如下：姓名学号性别年龄健康情况张790631男18健康王790632女20一般李790633男21健康赵790634男17神经衰弱……..……..…….…….…….8/29/20213一、线性表的定义线性表(LinearList)是由n(n≧0)个类型
2、相同的数据元素a1,a2,…,an组成的有限有序序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表（又称为空线性表）。SchoolofComputerandCommunication算法与数据结构8/29/20214一般将线性表记为：(a1，a2，…，an)SchoolofComputerandCommunication算法与数据结构线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a28/29/20215有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其
3、余的内部结点ai(2≦i≦n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。线性表是一种典型的线性结构。8/29/20216二、线性表的基本操作数据结构的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。SchoolofComputerandCommunication算法与数据结构8/29/202171.初始化线性表LInitList(&L)2.销毁线性表LDestoryList(&L)3.清空线性表LClearList(&L)4.求线性表L的长度ListLength(L)5.判断线性表L是否为空List
4、Empty(L)6.获取线性表L中的某个数据元素内容GetElem(L,i,&e)SchoolofComputerandCommunication算法与数据结构8/29/202187.查找值为e的数据元素LocateELem(L,e)8.在线性表L中插入一个数据元素InsList(&L,i,e)9.删除线性表L中第i个数据元素DelList(&L,i,&e)SchoolofComputerandCommunication算法与数据结构8/29/202192.1线性表的定义2.2线性表的顺序存储结构及实现2.3线性表的链式存储结构及实
5、现2.4顺序表和链表的比较2.5一元多项式的表示及相加SchoolofComputerandCommunication算法与数据结构8/29/2021102.2线性表的存储结构及实现一、线性表的存储结构(顺序表)二、顺序表数据类型描述三、顺序表上实现的基本操作四、顺序表应用举例五、优缺点分析SchoolofComputerandCommunication算法与数据结构8/29/202111一、顺序表把线性表的数据元素按逻辑顺序依次存放在一组地址连续的存储单元里。存储结构示意图：SchoolofComputerandCommunica
6、tion算法与数据结构8/29/202112SchoolofComputerandCommunication算法与数据结构8/29/202113特点：（1）存储单元连续；（2）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致；（3）随机存储结构；(4)存储的密度大。SchoolofComputerandCommunication算法与数据结构8/29/202114二、顺序表数据类型描述typedefstructSqlist{DataTypedata[MaxSize];/*将线
7、性表定义为一个一维数组*/intlength;//当前长度}Seqlist;SchoolofComputerandCommunication算法与数据结构#defineMaxSize100/*线性表存储空间的初始分配量*/8/29/202115三、顺序表上实现的基本操作1.查找操作1)按序号查找Data(L,i)DataTypeGetData(SeqListL,inti){/*查找线性表中的第i个元素*/If(i<1
8、
9、i>L.length)printf(“positionierror”);elsereturnL.data[i-
10、1];/*返回表中第i个元素L.data[i-1]*/}8/29/2021162)按值查找Locate(L,e)int Locate(SeqListL,DataTypee){ i=0;while((i<=L.length-1)&&(L
