数据结构Chapter_02 线性表.ppt

算法与数据结构; 数据的逻辑结构 ;;;;;;;抽象数据类型线性表的定义如下：; 基本操作：; InitList( L ) ; 结构销毁操作;ListEmpty( L ); ListEmpty( L ) ;ListLength( L ); PriorElem( L, cur_e, pre_e ) ;NextElem( L, cur_e, next_e );GetElem( L, i, e );LocateElem( L, e);加工型操作 ;ClearList( L ); ListInsert( L, i, e );ListDelete(L, i, e);;;;;;;;;;;;;; * ;;线性表的基本操作在顺序表中的实现;;;;;;;;例如：顺序表;;; O( n );线性表操作 ListInsert(L, i, e)的实现：; (a1, …, ai-1, ai, …, an) 改变为 (a1, …, ai-1, e, ai, …, an);算法1：在线性表中指定位置前插入一个元素 ;内存;图 线性表插入前后的状况 (a)插入前n=8; (b)插入后n=9;;;;;考虑移动元素的平均情况:;插入 算法时间复杂度为:;线性表操作 ListDelete(L, i, e)的实现：; (a1, …, ai-1, ai, ai+1, …, an) 改变为 (a1, …, ai-1, ai+1, …, an);;;;;考虑移动元素的平均情况:;删除 算法时间复杂度为:;;;;知识回顾(3);;;;; 用一组地址任意的存储单元存放线性表中的数据元素。;;; * ;;;;;;;;;;;LNode *p;;;;;;;;;;;;复杂度分析;;;ai-1; 因此，在单链表中第 i 个结点之前进行插入的基本操作为: 找到线性表中第i-1个结点，然后修改其指向后继的指针。;; * ;;线性表的操作ListDelete (L, i, e)在链表中的实现:; 在单链表中删除第 i 个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。;;;;; * ;;如何从线性表得到单链表？ (创建单链表);;;;;;思考;不带头结点的单链表(自学); 1 建立单链表: 设成员数据域为字符型 （1）头插法建表：依次插入新结点，并置于表头;头插法建立单链表;头插法建立单链表 linklist *CREATELIST() { char ch; linklist *head,*s; head＝NULL; ch＝getchar(); while (ch!=‘$’) { s＝malloc(sizeof(linklist)); s-data＝ch; s-next＝head; head＝s; ch＝getchar(); } return(head);};(2) 尾插法建表：插入的新结点置于表尾 产生一个新结点； 新结点的数据域为插入字符； 原尾结点（由尾指针指定）的指针域为新结点； 尾指针指向新结点； 新结点的指针域为空;尾插法建立单链表;linklist *CREATELISTR() { char ch; linklist *head,*s,*r; head＝NULL; r＝NULL; ch＝getchar(); while(ch!=‘$’) { s＝malloc(sizeof(linklist)); s-data＝ch; if (head==NULL) head＝s; else r-next＝s; r＝s; ch＝getchar(); };单链表的插入 第一种情况：在第一个结点前插入 第二种情况：在链表末尾插入 第三种情况：在链表中间插入 ;删除 第一种情况: 删除表中第一个元素 第二种情况: 删除表中或表尾元素 ;单链表特点 它是一种动态结构，整个存储空间为多个链表共用 不需预先分配空间 指针占用额外存储空间 不能随机存取，查找速度慢;知识回顾(4);;循环链表;采用尾指针的循环链表;;两循环链表的链接;两循环链表的链接 linklist *CONNECT(li