资源描述：
《数据结构讲义(第二章线性表x).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构第二章线性表主要内容线性表的概念及定义1线性表的顺序存储2线性表的链式存储3线性表的应用42§2.1线性表的概念及定义线性表(LinearList)：是由n(n≥0)个类型相同的数据元素a1,a2,…，an组成的有限序列，记做：L=(a1,a2,…，ai-1，ai，ai+1，…，an)数据元素的逻辑特性：数据元素之间的先后顺序为“一对一”的关系。ai-1领先于ai则ai-1是ai的直接前驱元素ai-1落后于ai则ai是ai-1的直接后继元素除a1外，每个元素有且仅有一个直接前驱元素除an外，每个元素有且仅有一个直接后继元素线
2、性表中数据元素的个数n(n≥0)称为线性表的长度（n=0时，该线性表称为空表）3线性表的前驱与后继a1a2a3a4a5数据元素直接前驱直接后继前驱后继a1无a2无a2,a3,a4,a5a2a1a3a1a3,a4,a5a5a4无a1,a2,a3,a4无a3a2a3a1,a2a4,a5a4a3a5a1,a2,a3a54顺序表——线性表的顺序存储结构例：（34,23,67,43）34236743存储要点用一段地址连续的存储单元依次存储线性表中的数据元素§2.2线性表的顺序存储顺序表——线性表的顺序存储结构例：（34,23,67,43）34
3、236743存储空间的起始位置用什么属性来描述顺序表？顺序表的容量（最大长度）§2.2线性表的顺序存储顺序表——线性表的顺序存储结构例：（34,23,67,43）34236743如何实现顺序表的内存分配？顺序表一维数组§2.2线性表的顺序存储0…i-2i-1…n-1Max-1a1…ai-1ai…an空闲顺序表一般情况下，(a1，a2，…,ai-1，ai,…,an)的顺序存储：数组的长度Max线性表的长度Length数组的长度大于等于当前线性表的长度§2.2线性表的顺序存储如何求得任意元素的存储地址？0…i-2i-1…n-1Max-1
4、a1…ai-1ai…an空闲顺序表一般情况下，(a1，a2，…,ai-1，ai,…,an)的顺序存储：cLoc(ai)Loc(a1)§2.2线性表的顺序存储0…i-2i-1…n-1Max-1a1…ai-1ai…an空闲Loc(ai)=Loc(a1)+(i-1)×c顺序表一般情况下，(a1，a2，…,ai-1，ai,…,an)的顺序存储：cLoc(ai)Loc(a1)§2.2线性表的顺序存储顺序表——随机存取顺序表中数据元素的存储地址是其序号的线性函数，只要确定了存储顺序表的起始地址，计算任意一个元素的存储地址的时间是相等的，具有这一
5、特点的存储结构称为随机存取（randomaccess）结构§2.2线性表的顺序存储§2.2线性表的顺序存储线性表的顺序存储：是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。采用顺序存储结构的线性表通常称为顺序表。a1a2a3a4a5……a1a2a3a4a5逻辑位置：物理位置：12顺序表类的声明constintMaxSize=100;template//模板类cla
6、ssSeqList{public:SeqList();//构造函数SeqList(DataTypea[],intn);~SeqList();//析构函数intLength();DataTypeGet(inti);intLocate(DataTypex);voidInsert(inti,DataTypex);DataTypeDelete(inti,DataTypex);private:DataTypedata[MaxSize];intlength;};2.2.2顺序表的实现2.2.2顺序表的实现constintMaxSize=100;
7、templateclassSeqList1{private:DataTypedata[MaxSize];//一维数组intlength;//线性表长度public:………;//成员函数;}；a1a2a3…alength…data[0]data[1]data[2]data[length-1]lengthMaxSize1.在类中使用静态一维数组静态一维数组是指在声明定义数组时，所给出数组的大小是确定的。数组的大小留有余地。142.2.1顺序表存储结构templateclassS
8、eqList2{private:DataType*data；//用指针表示一维数组intlength;//表的实际长度intmaxlen;//表的最大长度，容量public:………;//成员函数};2．在类中使用动态一维数组动态一维数
