数据结构2-线性表

1、线性表的定义线性表的顺序存储结构线性表的链式存储结构单链表、双向链表、循环链表线性表的应用一元多项式的表示和相加第2章 线性表线性表的定义线性表的顺序存储结构线性表的链式存储结构单链表、双向链表、循环链表线性表的应用一元多项式的表示和相加1线性表的定义线性表是 n 个数据元素的有限序列线性表的特点：存在唯一的一个被称为“第一个”的数据元素存在唯一的一个被称为“最后一个”的数据元素除第一个之外，每一个数据元素都有唯一的前驱除最后一个外，每一个数据元素都有唯一的后继线性表的表示形式：(a1, a2, a3, ., an)线性表的长度：其中的数据元素的个数n线性表的位序：数据元素 ai 在线性表中的

2、位置 i线性表的抽象数据类型定义：ADT List2线性表的顺序表示和实现线性表的顺序表示是用一组地址连续的存储单元依次存储线性表的数据元素特点：为表中相邻的数据元素赋以相邻的存储位置，即以计算机内物理位置相邻来表示线性表中数据元素的逻辑关系随机存取，数据元素ai的存储位置 LOC (ai ) 满足： LOC (ai ) = LOC (a1 ) +（i-1)*l 其中LOC (a1 ) 称基地址，l：每个元素占用的存储单元数3用一维数组表示的动态分配顺序存储结构# define LIST-INIT-SIZE 100# define LISTINCREMENT 10typedef struct

3、ElemType *elem; /存储空间基址int length; /线性表的现有长度int listsize; /当前分配的空间大小Sqlist; 此种结构下，线性表操作的实现4顺序表操作的小结：顺序表的 ListLength、GetElem、PreElem、NextElem等操作都是时间复杂度为 O(1)的操作。而 ListInsert、ListDelete、LocateElem等操作都是复杂度为 O(n)的操作。其中插入、删除操作的主要工作量花在元素移动上，查找操作花在元素的比较中。插入、删除操作移动元素的多少与操作的位置有关：在表尾操作无需移动元素，而在表头操作需移动所有元素，平均约

4、移动一半的元素。5线性表的链式存储结构线性表的链式存储结构是用一组任意的存储单元存储线性表的数据元素，而以指针来指示元素间的逻辑关系特点：每个结点由两个域组成存储其本身信息的数据域和指示其后继存储位置的指针域因所设指针只指后继，此结构称单链表整个链表的存取必须从头指针开始6链表的头指针可以指向链表的第一个结点，也可以指向附加的头结点在单链表中，要取得第 i 个数据元素，必须从头指针出发，依次取得第1、2、 i-1个数据元素的位置，再由第i-1个结点的后继指针才能确定第 i 个结点的位置。所以，这是一种顺序存取的存储结构。单链表的最后一个元素的后继指针为空指针（NULL）单链表的结构图：7单链表

5、的类型描述： Typedef struct Lnode ElemType data;struct Lnode *next; LNode, *LinkList;其中，LNode为结点类型：若p为指向某个结点的指针，则p-data存储结点信息，p-next为指向其后继的指针LinkList为指向结点的指针，一般指单链表的头指针8单链表的操作ListInsert 的实现ListDelete的实现CreateList的实现MergeList的实现9作 业1、编写算法，实现顺序表L的就地逆置。2、设顺序表L中的数据元素递增有序。编写算法，将x插入到顺序表的适当位置，以保持该表的有序性。3、编写算法，实现

6、单链表L的就地逆置。4、假设单链表A、B均递增有序，试编写算法将A、B两表归并成一个非递增有序的单链表C，并要求利用原表的结点空间构造C表。10循环链表线性表的另一种链式存储结构特点：表中最后一个结点的指针域指向头结点，整个链表形成一个环与单链表的不同：从链表的任一结点出发均可找到其他结点链表操作结束的循环条件不再是p或 p- next= =NULL，而是p或 p- next= =head（头指针）。11循环链表的操作基本和单链表一致。但由于其特点，在循环链表中设立尾指针而不是头指针，将会使某些操作简化，如将两个带尾指针的循环链表合并，这一操作只需改变两个指针值即可，复杂度为O（1）。12双向

7、链表链表中的每个结点带两个指针域：除了指向后继的next外，还设一个指向前驱的指针prior。这样，从链表的某一结点出发，既可顺着next指针往后寻找，也可顺着prior指针往前。类C语言的形式描述：Typedef struct DuLnode ElemType data;struct DuLnode *next, *prior ; DuLNode, *DuLinkList;13双向链表的结点结构：操作特性：d-next-prior = = d = = d- prior-next（d为DuLNode型指针） 具体操作：ListLength、GetElem、LocateElem等操作仅涉及一个方

8、向上的指针，其操作与单链表的相似；但插入、删除操作需修改两个方向的指针。操作的复杂度为O(n)。14算法参考顺序表的逆置。void invert ( SqList &L) for (i=0; i= (L.length / 2); i+)L .elem iL .elem L.length -1 i ; 15在有序的顺序表中插入x，使表仍有序Status InsertOrder(SqList &a, elemtype x)if (a.length= =a.listsize) return(OVERFLOW); i=a.length-1; while (i=0 &x=i+1;j-)a.elemi+1=a.elemi; a.elemi+1=x; a.length+; return OK;16以链式存储结构将两个递增的有序表合并为一个非递增的有序表。Void in-Union ( Linklist &La, Linklist &Lb) Linklist pa, pb, p; pa=La-next; pb=Lb-next; La-next=Null; free (Lb); While ( pa & pb ) if (pa-data data) p=pa; pa=pa-next; else p=pb; pb=pb-next; p-next = La-next