资源描述：
《《数学线性表》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章线性表线性表的类型定义线性表的顺序表示和实现线性表的链式表示和实现线性链表循环链表双向链表一元多项式的表示及相加10/2/20211第二章线性表（数据结构）线性结构的特点存在唯一的一个被称作“第一个”的数据元素。存在唯一的一个被称作“最后一个”的数据元素。除第一个之外，集合中的每个数据元素只有一个前驱。除最后一个之外，只有一个后驱。10/2/20212第二章线性表（数据结构）1线性表的类型定义最常用而且最简单的一种数据结构。是由n(n≥0)个类型相同的数据元素a1,a2,…，an组成的有限序列，记作（
2、a1,a2,…，ai-1，ai，ai+1，…，an）。这里的数据元素ai(1≤i≤n)只是一个抽象的符号，其具体含义在不同情况下可以不同，它既可以是原子类型，也可以是结构类型，但同一线性表中的数据元素必须属于同一数据对象。10/2/20213第二章线性表（数据结构）例：英文字母表(A,B,…,Z)就是一个简单的线性表，表中的每一个英文字母是一个数据元素，每个元素之间存在唯一的顺序关系，如在英文字母表字母B的前面是字母A，而字母B的后面是字母C。在较为复杂的线性表中，数据元素(dataelements)可由
3、若干数据项组成，如学生成绩表中，每个学生及其各科成绩是一个数据元素，它由学号、姓名、各科成绩及平均成绩等数据项(item)组成，常被称为一个记录(record)，含有大量记录的线性表称为文件(file)。数据对象（dataobject）是性质相同的数据元素集合。10/2/20214第二章线性表（数据结构）例学生健康情况登记表如下：姓名学号性别年龄健康情况王小林790631男18健康陈红790632女20一般刘建平790633男21健康张立立790634男17神经衰弱……..……..…….…….…….10/2
4、/20215第二章线性表（数据结构）线性表中元素的个数n，定义为线性表的长度，n=0时称为空表。线性表中相邻数据元素之间存在着序偶关系，即对于非空的线性表（a1,a2,…，ai-1,ai,ai+1,…,an），表中ai-1领先于ai，称ai-1是ai的直接前驱，而称ai是ai-1的直接后继。除了第一个元素a1外，每个元素ai有且仅有一个被称为其直接前驱的结点ai-1，除了最后一个元素an外，每个元素ai有且仅有一个被称为其直接后继的结点ai+1。可以对线性表进行访问、插入和删除等。10/2/20216第二章
5、线性表（数据结构）线性表的特点可概括如下同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。有序性：线性表中表中相邻数据元素之间存在着序偶关系。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。10/2/20217第二章线性表（数据结构）线性表总结由此可看出，线性表是一种最简单的数据结构，因为数据元素之间是由一前驱一后继的直观有序的关系确定；线性表又是一种最常见的数据结构，因为矩阵、数组、
6、字符串、堆栈、队列等都符合线性条件。10/2/20218第二章线性表（数据结构）线性表的抽象数据类型定义ADTLinearList{数据元素：D={ai
7、ai∈D0,i=1,2,…，n,n≥0，D0为某一数据对象}关系：Ｓ＝｛
8、ai,ai+1∈D0，i=1,2,…,n-1｝基本操作：（1）InitList（&L）操作前提：L为未初始化线性表。操作结果：将L初始化为空表。10/2/20219第二章线性表（数据结构）（2）DestroyList(&L)操作前提：线性表L已存在。操
9、作结果：将L销毁。（3）ClearList(&L)操作前提：线性表L已存在。操作结果：将表L置为空表。（4）ListEmpty（L）操作前提：线性表L已存在。操作结果：如果L为空表则返回真，否则返回假。10/2/202110第二章线性表（数据结构）（5）ListLength（L）操作前提：线性表L已存在。操作结果：如果L为空表则返回0，否则返回表中的元素个数。（6）LocateElem(L,e,compare())操作前提：表L已存在，e为合法元素值，compare是数据元素判定函数。操
10、作结果：返回L中第一个与元素e满足关系的数据元素的位置。（7）GetElem(L,i,&e)操作前提：表L存在，且i值合法，即1≤i≤ListLength（L）。操作结果：用e返回线性表L中第i个元素的值。10/2/202111第二章线性表（数据结构）（8）ListInsert(&L,i,e)操作前提：表L已存在，e为合法元素值且1≤i≤ListLength(L)+1。操作结果：在L中第i个位置插入新的数据元
