资源描述：
《数据结构 第 2 章 线性表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、线性表1、线性表的定义和性质及基本运算2、线性表的顺序存储结构3、线性表的链式存储结构4、多项式的代数运算教学内容线性结构的特点：除第一个之外的数据元素均只有一个前驱;存在唯一的一个被称作“第一个”的数据元素;除最后一个之外的数据元素均只有一个后继。数据元素的非空有限集存在唯一的一个被称作“最后一个”的数据元素;法学系8523101国贸系8522105工商系8523150计算机系8521088会计系8525789统计系8528136外语系8523026例：“第一个”数据元素“最后一个”数据元素直接前驱直接后继2.1线性表的类型定义线性表(Linear_List)
2、：由n(n0)个数据元素a1,a2,…,an组成的有限并且有序的序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表。非空的线性表(n>0)常记作：(a1,a2,…,ai-1,ai,ai+1,…,an)例1：26个英文字母组成的字母表：（A,B,C,…,Z）例2：某校从1978年到1983年各种型号的计算机拥有量的变化情况：（6,17,28,50,92,188）数据元素为数字i为数据元素ai的位序。这里的数据元素ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。数据元素为字符指线性表中的每一个元素都有自己的位置（position）
3、。例3：学生健康情况登记表：姓名学号性别年龄健康情况王小林790631男18健康陈红790632女20一般刘建平790633男21健康张立立790634男17神经衰弱……..……..…….…….…….数据元素(结点、记录)由5个数据项(字段、域)组成。文件(file)线性表中的数据元素可以是各种各样的，但同一线性表中的元素必定具有相同特性（属于同一数据对象）。线性表中的数据元素之间存在着序偶关系。从以上例子可看出线性表（非空）的逻辑特征是：1、有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2，a1叫表头元素；2、有且仅有一个终端
4、结点an，它没有直接后继，而仅有一个直接前趋an-1，an叫表尾元素；3、其余的内部结点ai(2in-1)都有且仅有一个直接前趋ai–1和一个直接后继ai+1。ADTList{抽象数据类型线性表的定义：参看P19。数据对象：D＝{ai
5、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
6、ai-1,ai∈D,i=2,...,n}基本操作：（线性表的基本操作很多，为讨论方便起见，在此将它归为四类。）{结构初始化}任何数据结构在被使用之前都必须进行“初始化”，它类似于编程中使用的变量都必须先有定义。InitList(&L)操
7、作结果：构造一个空的线性表L。{销毁结构}任何数据结构不再使用时都必须进行“结构销毁”，其实质为“释放”它所占有的存储空间。DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。{引用型操作}ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE。操作的结果不改变线性表中的数据元素，也不改变数据元素之间的关系。ListLength(L)初始条件：线性表L已存在。操作结果：返回L中元素个数。若cur_e是线性表L中第一个数据元素，则它的前驱pre_e为“空元素”。NextElem(L,c
8、ur_e,&next_e)初始条件：线性表L已存在。操作结果：若cur_e是L中的数据元素，则用next_e返回它的后继，否则操作失败，next_e无定义。PriorElem(L,cur_e,&pre_e)初始条件：线性表L已存在。操作结果：若cur_e是L中的数据元素，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。若cur_e是线性表L中最后一个数据元素，则它的后继next_e为“空元素”。GetElem(L,i,&e)初始条件：线性表L已存在，1≤i≤LengthList(L)。操作结果：用e返回L中第i个元素的值。此操作通常称为“定位函数”，
9、这是一种广义的定位函数写法，以compare()作为判定的条件，参数e和线性表中数据元素具有相同类型。较多场合是以“相等”作为判定条件，此时可省略函数参数，且操作结果为：若线性表中存在与e值相同的数据元素，则返回第一个这样的元素在表中的位序，否则返回函数值为0。LocateElem(L,e,compare())初始条件：线性表L已存在，compare()是元素判定函数。操作结果：返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回0。ListTraverse(L,visit())初始条件：线性表L已存在，visit()为元素的访问
10、函数。操作结果：依次对L
