文档介绍：第3章线性表线性表是一种最简单的线性结构。线性结构的特点是:在非空的有限集合中,存在唯一的一个被称为“第一个”的数据元素,存在唯一的一个被称为“最后一个”的数据元素。第一个元素没有直接前驱元素,最后一个没有直接后继元素,其它元素都有唯一的前驱元素和唯一的后继元素。线性表有两种存储结构:顺序存储结构和链式存储结构。本章重点和难点:1、顺序表和单链表的基本操作实现2、,记为(a1,a2,…,ai-1,ai,ai+1,…,an)。其中,这里的数据元素可以是原子类型也可以是结构类型。线性表的数据元素存在着序偶关系,即数据元素之间具有一定的次序。在线性表中,数据元素ai-1在ai的前面,ai又在ai+1的前面,我们把ai-1称为ai的直接前驱元素,ai称为ai+1的直接前驱元素。ai称为ai-1的直接后继元素,ai+1称为ai的直接后继元素。。,例如,“China”、“Science”、“Structure”。其中每一个英文字母就是一个数据元素,每个数据元素之间存在着唯一的顺序关系。如“China”中字母’C’后面是字母’h’,字母’h’后面是字母’i’。在较为复杂的线性表中,一个数据元素可以由若干个数据项组成,,数据元素也称为记录。。{a1,a2,…,an},元素类型为DataType。数据元素之间的关系是一对一的关系。除了第一个元素a1外,每一个元素有且只有一个直接前驱元素,除了最后一个元素an外,每一个元素有且只有一个直接后继元素。(1)InitList(&L):初始化操作,建立一个空的线性表L。(2)ListEmpty(L):若线性表L为空,返回1,否则返回0。(3)GetElem(L,i,&e):返回线性表L的第i个位置元素值给e。(4)LocateElem(L,e):在线性表L中查找与给定值e相等的元素,如果查找成功返回该元素在表中的序号表示成功,否则,返回0表示失败。(5)InsertList(&L,i,e):在线性表L中的第i个位置插入新元素e。(6)DeleteList(&L,i,&e):删除线性表L中的第i个位置元素,并用e返回其值。(7)ListLength(L):返回线性表L的元素个数。(8)ClearList(&L):将线性表L清空。:顺序存储结构和链式存储结构。。线性表中第i+1个元素的存储位置LOC(ai+1)和第i个元素的存储位置LOC(ai)之间满足以下关系:LOC(ai+1)=LOC(ai)+m第i个元素的存储位置与第一个元素a1的存储位置满足以下关系:LOC(ai)=LOC(a1)+(i-1)*m其中,第一个元素的位置LOC(a1)称为起始地址或基地址。,将这种方法存储的线性表称为顺序表。顺序表具有以下特征:逻辑上相邻的元素,在物理上也是相邻的。每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数()。只要确定了第一个元素的起始位置,线性表中的任一元素都可以随机存取,因此,线性表的顺序存储结构是一种随机存取的存储结构。。#defineListSize100typedefstruct{ DataTypelist[ListSize]; intlength;}SeqList;其中,DataType表示数据元素类型,list用于存储线性表中的数据元素,length用来表示线性表中数据元素的个数,SeqList是结构体类型名。(1)初始化线性表。voidInitList(SeqList*L)/*初始化线性表*/{L->length=0; /*把线性表的长度置为0*/}(2)判断线性表是否为空。intListEmpty(SeqListL)/*判断线性表是否为空,线性表为空返回1,否则返回0*/{if(==0) /*线性表的长度