数据结构 第二章 线性表.ppt

1、第二章 线性表,2.1线性表 2.2线性表的顺序表示与实现（顺序表 ） 2.2线性表的链式表示与实现链表 2.3.1单链表 2.3.2循环链表 2.3.3双链表 2.4一元多项式的表示与实现,2.1线性表的类型定义,1、定义： n（0）个数据元素的有限序列，记作（a1, ai-1, ai, ai+1, an） 其中,ai 是表中数据元素，n 是表长度。 特点: 同一线性表中元素具有相同特性。 相邻数据元素之间存在序偶关系。 除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。 除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。 举例：1）字母表，2）学生记录表,2、抽象数据类型线性

2、表定义：,ADT LIST 数据对象：D:=ai | aiElemSet, i=1,2,n, n0 数据关系： R=|ai-1,aiD, i=2,3,n 数据操作：InitList( P21算法复杂度说明,例2-1 假设利用两个线性表La和Lb分别表示两个集合A和B（即：线性表中的数据元素即为集合中的成员），现要求一个新的集合AAB。输入：线性表La、线性表Lb输出：变化了的Launion( 3若不存在，则插入之。算法：算法2.1 P20,ListLength GetElem,LocateElem,ListInsert,void union(List / union,T(na, nb) =O(

3、nb*na), na、nb表示La表和Lb表的长度,基于ADT List的算法设计 例2-2 已知线性表La和Lb中的数据元素按值非递减有序排列，要求将La和Lb归并成一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排列。输入：线性表La、线性表Lb(均按值非递减有序排列) 输出：Lc(按值非递减有序排列) merge(La, Lb, typedef struct ElemType * elem; /存储空间基址 int length; /当前元素个数 int listsize; SeqList,4、顺序表基本运算 初始化 void InitList ( SeqList ,插入,25 3

4、4 57 16 48 09 63 ,0 1 2 3 4 5 6 7,50,插入 x,25 34 57 50 16 48 09 63 ,0 1 2 3 4 5 6 7,50,i,顺序表插入时，平均数据移动次数AMN在各表项 插入概率相等时,2.2 插入操作的实现(分析设计),插入操作算法设计(算法2.4) 参数：顺序表 合法的位置：i:1.L.length+1 上溢及处理： 上溢发生的条件：L.lengthL.listsize， 处理：先申请一个有一定增量的空间：申请成功则原空间的元素复制到新空间，修改L.listsize，再进行插入工作；否则报错退出。,2.2 插入操作的实现(算法分析),时间

5、复杂度 频次最高的操作：移动元素 上溢时，空间的再分配与复制(realloc操作)分摊到每次插入操作中 若线性表的长度为n，则： 最好情况：插入位置i为n+1，此时无须移动元素，T(n)=O(1); 最坏情况：插入位置i为1，此时须移动n个元素， T(n)=O(n); 平均情况：假设pi为在第i个元素之前插入一个元素的概率，则：插入时移动次数的期望值：等概率时，即 ， T(n) = O(n),顺序表的插入 int listInsert_sq ( SeqList ,插入操作的实现(算法2.4),Status ListInsert_Sq( SqList (书上采用指针形式),为什么要引入newba

6、se?,空间分配失败时，避免将原空间地址丢失!,删除,25 34 57 50 16 48 09 63 ,16,删除 x,25 34 57 50 48 09 63 ,0 1 2 3 4 5 6 7,顺序表删除平均数据移动次数AMN在各表项 删除概率相等时,2.2删除操作的实现(分析设计),算法设计(算法2.5) 参数：顺序表 合法的位置：i:1.L.length 下溢及处理： 下溢发生的条件：L.length0 处理：隐含在i的条件中,顺序表的删除 int listDelete_sq ( SeqList ,删除操作的实现(算法),算法设计(算法2.5) Status ListDelete_Sq(

7、 SqList （书上采用指针形式),按值查找：找x在表中的位置，若查找成功，返回表项的位置，否则返回-1 int LocateElem_sq ( SeqList L, ElemType e ,(*campare)(ElemType, ElemType) 见p26; ,按值查找 算法2.6,int LocateElem(SqList L,ElemType e,Status(*compare)(ElemType,ElemType) /* 初始条件：顺序线性表L已存在，compare()是数据元素判定函数(满足为1，否则为0) */ /* 操作结果：返回L中第1个与e满足关系compare()的数

8、据元素的位序。 */ /* 若这样的数据元素不存在，则返回值为0。算法2.6 */ ElemType *p; int i=1; /* i的初值为第1个元素的位序 */ p=L.elem; /* p的初值为第1个元素的存储位置 */ while(i=L.length ,求表的长度 int listLength_sq ( SeqList L ) return L.length; 提取函数：在表中提取第 i 个元素的值 Getelem_sq ( SeqList L, int i, ElemType ,顺序表的应用: 顺序表的归并,void mergelist_sq ( SeqList La, Seq

9、List Lb, SeqList typedef struct Lnode /链表结点 ElemType Data; /结点数据域 struct Lnode * next; /结点链域 Lnode, * LinkList; (与 typedef LNode * LinkList; 等价表述） LinkList L ; /链表头指针,基本操作的实现 取第i个元素： GetElem_L(LinkList L, int i, ElemType j = 0; while ( p -next!= NULL ) /能否把条件改为p!= NULL p = p-next; j+;/ 后移指针并计数j retu

10、rn(j); ,2.3.1 单链表求长度1,T(n) =O(n),计算单链表长度（2）,int ListLength_L ( LinkList L ) LNode *p = L-next; /指针 p 指示第一个结点 int count = 0; while ( p != NULL ) /逐个结点检测 p = p-next; count+; return count; ,插入:在链表中间插入 s-next = p-next; p-next = s；,(插入前) (插入后),s,p,s,p,算法描述 status listInsert_L ( LinkList p-next = q-next;

11、free(q);,删除前,删除后,算法描述 satus listDelete_L ( LinkList LinkList head = /建立表头结点 (LinkList) malloc (sizeof (LNode); ListNode *q, *r = head; while ( (ch = getchar( ) ) != n ) q = (LNode *) malloc (sizeof(LNode); q-data = ch; /建立新结点 r -next = q; r =q; /插入到表末端 r -next = NULL; return head; ,按值查找,int LocateEl

12、em_L ( LinkList L, ElemType e ,(*campare)(ElemType, ElemType) /在链表中从头搜索其数据值为e的结点 ListNode * p = L-next; /指针 p 指示第一个结点 while ( p != NULL ,有序链表的归并,void mergelist_L ( LinkList La, LinkList Lb, LinkList /静态链表大小 typedef int ElemType; typedef struct /静态链表结点 ElemType data; int cur; componet,slinklistMaxSiz

13、e; Slinklist s; /静态链表头指针,静态链表上算法操作注意事项(与单链表比较)：,头结点：i=0;（p=L） 第一个结点：s0.cur,(LNEXT); 移动：i=si.cur;(p=p-next;) 结尾判断：i=0;(p=null) 结点值：Si.data;(p-data),静态链表的基本运算,int LocateElem_SL ( SLinkList S, ElemType e) 见书P32算法2.13 静态链表上的算法作为自学内容！,2.3.2、循环链表 (Circular List),特点:最后一个结点的 link 指针不为NULL，而是指向头结点。只要已知表中某一结点

14、的地址，就可搜寻所有结点的地址。 存储结构:链式存储结构 带表头结点的循环链表,an-1,H,a1,a0,H,(空表),(非空表),循环链表使用尾指针可以简化一些操作,循环链表上算法操作注意事项(与单链表比较)：,完全类似 结尾判断：P=H; (p=null)； 最后一个结点判断： P-next= =H; (P-next =null)； 算法完全类似编写,2.3.3、双向链表 (Doubly Linked List),双向链表结点结构：,prior data next,指向直接前驱 指向直接后继,非空表 空表,L,L,双向循环链表的定义,typedef int ElemType; typede

15、f struct duLnode ElemType data; struct duLnode * prior, * next; DuLNode; typedef DuLNode * DuLinkList; 定义变量：DuLinkList d, H,L;,双向循环链表的基本运算：,建立空的双向循环链表 void CreateDubLinkList (DubLinkList /表头结点的链指针指向自己 ,计算双向循环链表的长度,int ListLength_DuL (DubLinkList L ) /计算带表头结点的双向循环链表的长度 DuLNode * p = L-next; int count

16、 = 0; while ( p != L ) p = p-next; count+; return count; ,双向循环链表的插入 (非空表),q-prior = p; q-next = p-next; p-next = q; q-next-prior = q;,在结点 *p 后插入25,L,L,31,48,15,p,p,31,48,25,15,q,双向循环链表的插入 (空表),q-prior = p; q-next = p-next; p-next = q; q-next-prior = q;,在结点 *p 后插入25,int ListInsert_DuL ( DuLinkList p

17、= va-next; int j = 1; / 初始化，p指向第一个结点，j为计数器 while (p!=va / GetElem_L,双向循环链表的删除,p-next-prior = p-prior; p-prior-next = p-next;,(非空表),删除48,first,first,31,48,15,p,31,15,双向循环链表的删除,p-next-prior = p-prior; p-prior-next = p-next;,first,31,p,删除31,int ListDelete_DuL( DuLinkList int expn term,ElemType; Typedef Linklist Polynomial;,创立多项式：