数据结构第二章线性表

1、第二章 线性表n2.1 线性表的类型定义n2.2 线性表的顺序表示和实现n2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表n2.4 一元多项式的表示及相加线性结构：是一个数据元素的有序集例如（A，B，C，D，E，Z） （32，25，76，28，96）注：1、一个数据元素的集合 2、这些数据元素是有序的线性结构的特征：1、唯一的“第一个元素”2、唯一的“最后一个元素”3、除最后一个元素外，所有元素都有唯一的后继4、除第一个元素外，所有元素都有唯一的前驱2.1 线性表的类型定义一、线性表(Linear List) ：由n(n)个数据元素(结点)a1，

2、a2， an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n0)记作： (a1，a2，an) 例1、26个英文字母组成的字母表 （A，B，C、Z）例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。 （6，17，28，50，92，188）二、抽象数据类型的线性表的定义ADT List数据对象： D=ai|aiElem Set ，i=1，2，3n，n=0数据关系： R1=| ai-1，ai D，i=，2，3，n基本操作n基本操作：1、结构初始化InitList（&L）结果：构造一个空的线性表L2、销毁结构DestroyList

3、（&L）初始条件：线性表L已经存在结果：销毁线性表L3、引用型操作ListEmpty（L）；ListLength（L）PriorElem（L.cur_e, &pre_e）；NextElem（ L.cur_e, &next_e ）；GetElem（L，e，&e）；LocateElem(L，e，compare（）);ListTraverse（L，visit（）4、加工型操作ClearList（&L）PutElem（L，i，&e）ListInsert(&L，i，e)ListDelete (&L，i，&e ）注：1、InitLis

4、t（ &L ）和ClearList（ &L ）的区别2、除了初始化操作外，每一个操作都有一个初始条件和操作结果3、任何一种抽象数据类型，都包含有初始化操作和销毁操作例2-1 利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=AB。算法：1、从线性表LB中依次取得每个数据元素 GetElem（LB，i）e 2、依值在线性表LA中进行查访 LocateElem（LA，e，equal（） 3、若不存在，则插入到LA中 ListInsert（LA，n+1，e） void union(List &La，List Lb) La-len=Listlength(La

5、); Lb-len=Listlength(Lb); for(I=1;I=Lb-len;I+) GetElem(lb，I，e); if(!LocateElem(la，e，equal() Listinsert(la，+la-len，e) 例2-2 已知一个非纯集合B，试构造一个纯集合A，使A中只包含B中所有值各不相同的数据元素算法1： void purge (List &La，List Lb) InitList (La); La-len=Listlength(La); Lb-len=Listlength(Lb); for(I=1;I=Lb-len;I+) GetElem(lb，I，e);

6、if(!LocateElem(la，e，equal() +la-len; Listinsert(la，la-len，e) 算法2： 1、先对原表进行排序 2、然后插入 void purge(List &La，List Lb) InitList(La); La-len=Listlength(La); Lb-len=Listlength(Lb); for(I=1;I=Lb-len;I+) GetElem(lb，I，e); if（ListEmpty（La）|！Equal（en，e） Listinsert(la，+la-len，e)； en=e； 例2-3 巳知线性表LA和线性表LB中的数据元

7、素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。 此问题的算法如下：void mergelist(list la，list lb，list &lc) InitList(lc); I=j=1;k=0; la-len=ListLength(la); lb-len=ListLength(lb); while(I=la-len)&(j=lb-len) GetElem(la，I，ai); GetElem(lb，j，bj);void mergelist(list la，list l b，list &lc) InitList(lc

8、); i=j=1;k=0; la-len=ListLength(la); l b-len=ListLength(lb); while(i=la-len)&(j=lb-len) GetElem(la，i，ai); GetElem(lb，j，bj);if(ai=bj) ListInsert(lc，+k，ai);+i; else ListInsert(lc，+k，bj);+j; while(I=la-len) GetElem(la，i+，ai); ListInsert(lc，+k，ai); while(j=l b-len) GetElem(l b，j+，bj); ListInsert(lc，

9、+k，bi); 2.2 线性表的顺序存储结构一、线性表的顺序映像1、线性表的顺序映像:把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。 假设线性表的每个元素需占用c个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC( a i+1)和第i个数据元素的存储位置LOC(a I )之间满足下列关系： LOC(a i+1)=LOC(a i)+c 线性表的第i个数据元素ai的存储位置为： LOC (ai)=LOC(a1)+(i-1)*c a1 a2 a3 ai-1 ai an结论：所有数据元素的存储位

10、置均取决于第一个数据元素的存储位置。2、顺序映像的c语言描述 # define LIST_INIT_SIZE 100 # define LISTINCREMENT 10 typedef struct ElemType *elem; int length; int listsize; Sqlist;注：1、由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型。 2、线性表的长度是可以变化的，但是在设计的时候先给定一个值，相应的存储空间的大小是这个值的倍数二

11、、 顺序表上实现的基本操作1、线性表的初始化操作 Status InitList_Sq(SqList &L) L.elem=(ElemType *)malloc (LIST_INIT_SIZE* sizeof(ElemType); If (!L.elem) exit(OVERFLOW); L.length=0; L.Listsize= LIST_INIT_SIZE: return OK; 2、LocateElem（L，e，compare()） Int LocateElem_sq(SqList L,ElemType e, Status (*compare)(ElemType , Elem

12、Type) i=1; p=L.elem; while(i=L.length & !(*compare)(*p+ , e) +i; if (i next ;j=1; while(p& jnext; j+; if (!p | jpos) return error; e=p-data; return ok; （2）按值查找Status GetElem(linklist L, int key，ElemType &e) p=Lnext; while( p & pdata!=key) p=pnext; if (!p) return error; else return p;

13、 该算法的执行时间亦与输入实例中的的取值key有关，其平均时间复杂度的分析类似于按序号查找，也为O(n)。2、ListInsert（&L, i, e） P29基本操作：找到线性表中第i-1 个结点，修改其指向后继的指针，并且插入新结点3、ListDelete（ &L, i, &e ）P30基本操作：找到线性表中第i-1 个结点，修改其指向后继的指针，并释放删除的结点4、CreatList（LinkList &L）（1）尾插法建表 该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表尾上，直到读入结束标志

14、为止。Void Create_L(LinkList &L, int n) L=(LinkList)malloc(sizeof(LNode); L-next=null; p=L; for (i=1;idata); pnext=q; p=q; p-next=null; return (L); （2）头插入法该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。 void CreatList_L(LinkList &L, int n) L=(LinkList)malloc(sizeof (LNode

15、); L-next=Null; for (i=n;i0;-i) p=(LinkList)malloc(sizeof(LNode); scanf(&p-data); p-next=L-next; L-next=p; 5、用上述定义的单链表实现线性表的操作时，存在的问题：（1）单链表的表长是一个隐含的值（2）在单链表的最后，一个元素最后插入元素时，需要遍历整个链表（3）在链表中，元素的“位序”概念淡化，结点的“位置”概念强化。改进链表的设置：增加“表长”，“表尾指针”，“当前位置的指针”三个数据域三、一个带头结点的线性表类型1、结点结构：Typedef struct LNode ElemT

16、ype data; struct LNode *next; *Link, *Position;2、链表类型：Typedef struct Link head,tail; Int len; Link current; LinkList;3、基本操作：(1) InitList（LinkList & L）(2) DestroyList(LinkList &L)(3) Prior (LinkList L) ; Next(LinkList L); GetCurElem(LinkList L); LocatePos(LinkList L , int i); LocateElem(LinkL

17、ist L,ElemType e, compare(); ListTraverse(LinkList L, Status (*visit)();(4)ClearList(LinkList &l); SetCurElem(LinkList &L,ElemType e); Append(LinkList &L, Link s) InsAfter( LinkList &L ,ElemType e); DelAfter(LinkList &L ,ElemType *e)Status InsAfter (LinkList &L, ElemType e) i

18、f (!L.current) return Error; if (!MakeNode(s,e) return Error; s-next=L.current-next; L.current-next=s; return ok;四、循环链表 循环链表时一种头尾相接的链表。最后一个结点的指针指向第一个结点的链表。单循环链表：在单链表中，将终端结点的指针域NULL改为指向表头结点的或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。 为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。如下图所示： a1 an .head 非空表 空表例

19、、在链表上实现将两个线性表(a1，a2，a3，an)和(b1，b2，b3，bn)链接成一个线性表的运算。 linklist connect(linklist taila，linklist tailb) linklist p=tailanext; tailanext=(tailbnext)next free(tailbnext); tailbnext=p; return(tailb); 五、双链表1、双向链表(Double linked list):在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。形式描述为： typedef struct DulNode ElemType data; struct DulNode *prior，*next; DulNode,*DulNode; 设指针p指向某一结点， (pprior)next=p=(pnext)prior即结点*