数据结构-第2章线性表.ppt

第二章线性表考虑：通过上面两个例子可以看出：逻辑结构是数据组织的某种“本质性”的东西：（1）逻辑结构与数据元素本身的形式、内容无关。（2）逻辑结构与数据元素的相对位置无关。（3）逻辑结构与所含数据元素的个数无关。算法的设计取决于选定的逻辑结构，而算法的实现依赖于采用的存储结构总结：1、线性表（Linear_List）的定义：线性表L是n(n=0)个相同类型数据元素a1,…，an-1,an构成的有限序列，相邻数据元素之间存在着序偶关系。 L=(a1，a2，…，ai?1，ai，ai+1，…，an)2、线性结构的特点：A1没有前驱，只有一个后继；An没有后继，只有一个前驱；Ai（i≠1或n）有一个前驱，一个后继。课堂练习1、判断题(1)集合与线性表的区别在于是否按关键字排序。（）(2)线性表中每个元素都有一个直接前驱和一个直接后继。（）(3)线性表就是顺序存储的表。（）(4)取线性表的第i个元素的时间同i的大小有关。（）课堂练习2、设计一个算法，将顺序表中的所有元素逆置，给出时间复杂度。voidreverse(ListlistA){ listALenght=ListLength(listA); for(i=1;i=listALenght/2;i++) { getElem(listA,i,e1) getElem(listA,listALenght-i+1,e2) setElem(listA,i,e2); setElem(listA,listALenght-i+1,e1) }}课堂练习3、设计一个算法，将顺序表中的所有元素值为x（参数给定）的元素删除，给出时间复杂度。voiddeleteWith(ListlistA,ElemTypex){ listALenght=ListLength(listA); for(i=1;i=listALenght;i++) { getElem(listA,i,e) if(e==x)ListDelete(listA,i,e); }}2.2.1线性表的顺序表示1、线性表的顺序表示(顺序表)： 是指在内存中用一组地址连续的一块存储单元顺序存放线性表的各元素，用这种存储形式存储的线性表称为顺序表。2、顺序表的地址关系：用k表示数据元素的长度（占用的存储单元数）LOC(ai)表示顺序表第i个元素的地址，则顺序表整体在内存中的位置用第1个元素的地址表示：LOC(a1)，称为线性表的起始地址或基地址。第i个元素的地址：LOC(ai)=LOC(a1)＋(i-1)×k3、顺序存储结构是随机存取的存储结构特点：用元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑结构。这种机内表示称作线性表的顺序存储结构，称这种存储结构的线性表表为顺序表。由于可以通过位置（i）来定位线性表中任意一个元素的地址： LOC(ai)=LOC(a1)＋(i-1)×k。所以又称为随机存储结构。2.2.2线性表的顺序存储结构由于C或C++语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。 2.2.3顺序表的操作实现顺序表的访问操作容易实现，可随机存取元素。但插入和删除操作主要是移动元素。1、（a）初始化操作(动态分配数组)算法思想：构造一个空表。设置表的起始位置、表长及可用空间。算法：StatusInitList_Sq(SqListL){ L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); If(!L.elem)exit(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE; ReturnOK;}//InitList_Sq1、（b）初始化操作(静态数组)算法思想：设置表长。算法：StatusInitList_Sq(SqListL){ L.length=0; ReturnOK;}//InitList_Sq2、插入操作算法思想：在第i个位置上插入一个新元素，将第n至（i+1）个元素逐一向后移动一个位置。算法：StatusListInsert_Sq(SqListL,inti,ElemTypee){//在顺序表L的第I个位置之前插入元素e。//i的合法值1=i=L.length+1if(i1||iL.