线性数据结构线性表的应用要点.ppt

数据结构@UESTC 电子科技大学 · 计算机科学 · 数据结构与算法 · 数据结构@UESTC 电子科技大学 · 计算机科学 · 数据结构与算法 · 数据结构与算法 主讲：林劼 副教授 电子科技大学 计算机学院 顺序与链式存储结构比较 顺存储结构的特点 逻辑上相邻的元素，其物理位置也相邻； 可随机存取表中任一元素 必须按最大可能长度预分存储空间，存储空间利用率低，表的容量难以扩充，是一种静态存储结构 插入删除时，需移动大量元素，平均移动元素为n/2 链式存储结构的特点 逻辑上相邻的元素，其物理位置不一定相邻；元素之间的邻接关系由指针域指示 是非随机存取存储结构；对链表的存取必须从头指针开始 是一种动态存储结构； 插入删除运算非常方便；只需修改相应指针值 2.1.5 线性表的应用 存储结构选择原则 各有优缺点，选择那一种存储结构由实际问题中的主要因素决定 (1)基于存储空间的考虑：线性表的长度或存储规模难以估计时，或数据元素动态变化较大时，使用链表 (2)基于运算时间的考虑：经常做的是访问数据元素操作，插入删除操作极少时用顺序表 (3)基于实现的考虑：顺序表的实现较为简单，链表的实现较为复杂 1. 线性表倒置 问题：把线性表(a1，a2，…,an) 变为(an，an-1，…,a1) 算法： 算法1：对应数据元素相交换，如a1与an交换、a2与an-1交换等等 算法2：前驱后继关系改变，即倒置前a1是a2的前驱、a2是a1后继，倒置后a1是a2的后继、a2是a1前驱，…… 实现： 顺序表上实现 单链表上实现 1. 线性表倒置 在顺序表上按算法1（对应数据元素相交换）实现P.41： void List_Reverse(ListPtr L){ int i=1, j=L-length; ElemType temp; while (ij){ temp=L-elem[i]; L-elem[i]=L-elem[j]; L-elem[j]=temp; i++; j--; } } 思考： 能否用for循环？ 1. 线性表倒置 在单链表上按算法2（前驱后继关系互换）实现P.42： void List_Reverse(ListPtr L){ ListNodePtr q, p=(*L)-next; /*p指向第一个数据结点*/ (*L)-next=NULL; /*将原链表置为空表*/ while (p){ q=p; p=p-next; q-next=(*L)-next; /*插到头结点的后面*/ (*L)-next=q; } } 线性表元素按照访问频度排序 问题：设计一个在线性表中实现Locate运算的函数，使得线性表中所有结点按访问频度递减的顺序排列，以使访问频繁高的结点总是靠近表头 分析：运算主要包括 查找 如果该元素比前一个频繁，则需要将其向前移动，也就是插入和删除操作 结构选择 查找：顺序或者链式均可；插入删除：链式存储 综合：选择链式 哪种链式结构呢？ 涉及前驱操作：双向链表 线性表元素按照访问频度排序 选用带头结点的双向链表L，每个结点有4部分： 指向前驱结点的指针prior 指向后继结点的指针next 存放数据的成员data 记载访问频度freq，初始时所有结点的freq都为0。 首先在链表中查找指定数据，如找到，将其freq加1，然后向前寻找freq大于它的结点，并在该结点后面进行插入。 prior freq data next 线性表元素按照访问频度排序 void Locate ( DuList L, ElemType x ) { pNode p = L-next, q; while ( p p-data != x ) p = p-next; /*定位*/ if ( p ) { /*链表中存在x*/ p-freq++; /*该结点的访问频度加1*/ q = p; /*从链表中摘下这个结点*/ if(p-prior) p-prior-next = p-next; if(p-next) p-next-prior = p-proir; p =q-prior; while ( p != L q-freq p-freq ) /*寻找插入位置*/ p = p-prior; q-next = p-next; /*插入在p之后*/ q-prior = p; if(p-next)p