线性数据结构线性表的应用

1、数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 数据结构与算法数据结构与算法 主讲主讲：林劼：林劼 数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 顺序与链式存储结构比较顺存储结构的特点顺存储结构的特点n逻辑上相邻的元素，其物逻辑上相邻的元素，其物理位置也相邻；理位置也相邻；n可随机存取表中任一元素可随机存取表中任一元素n必须按最大可能长度预分必须按最大可能长度预分存储空间，存储空间利用存储空间，存储空间利用率低，表的容量难以扩充率低，表的容量难以扩充，是一种静态存储结构，是一种

2、静态存储结构n插入删除时，需移动大量插入删除时，需移动大量元素，平均移动元素为元素，平均移动元素为n/2n/2链式存储结构的特点链式存储结构的特点 逻辑上相邻的元素，其物逻辑上相邻的元素，其物理位置不一定相邻；元素理位置不一定相邻；元素之间的邻接关系由指针域之间的邻接关系由指针域指示指示 是非随机存取存储结构；是非随机存取存储结构；对链表的存取必须从头指对链表的存取必须从头指针开始针开始 是一种动态存储结构；是一种动态存储结构； 插入删除运算非常方便；插入删除运算非常方便；只需修改相应指针值只需修改相应指针值数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与

3、算法数据结构与算法 2.1.5 线性表的应用线性表的应用 n存储结构选择原则存储结构选择原则 各有优缺点，选择那一种存储结构由实际问题中各有优缺点，选择那一种存储结构由实际问题中的主要因素决定的主要因素决定 n(1)基于存储空间的考虑：线性表的长度或存储基于存储空间的考虑：线性表的长度或存储规模难以估计时，或数据元素动态变化较大时，规模难以估计时，或数据元素动态变化较大时，使用链表使用链表n(2)基于运算时间的考虑：经常做的是访问数据基于运算时间的考虑：经常做的是访问数据元素操作，插入删除操作极少时用顺序表元素操作，插入删除操作极少时用顺序表n(3)基于实现的考虑：顺序表的实现较为简单，基于实

4、现的考虑：顺序表的实现较为简单，链表的实现较为复杂链表的实现较为复杂 数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 1. 线性表倒置线性表倒置 n问题：把线性表问题：把线性表(a1，a2，,an) 变为变为(an，an-1，,a1) n算法：算法：n算法算法1：对应数据元素相交换，如：对应数据元素相交换，如a1与与an交换、交换、a2与与an-1交换等等交换等等 n算法算法2：前驱后继关系改变，即倒置前：前驱后继关系改变，即倒置前a1是是a2的前驱、的前驱、a2是是a1后继，倒置后后继，倒置后a1是是a2的后继、的后继、a2是是a1前

5、驱，前驱， n实现：实现：n顺序表上实现顺序表上实现n单链表上实现单链表上实现数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 1. 线性表倒置线性表倒置 在顺序表上按算法在顺序表上按算法1（对应数据元素相交换）实现（对应数据元素相交换）实现P.41：void List_Reverse(ListPtr L) int i=1, j=L-length; ElemType temp; while (ielemi; L-elemi=L-elemj; L-elemj=temp; i+; j-; 思考：思考：能否用能否用for循环？循环？数据结构数据

6、结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 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

7、; 数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 线性表元素按照访问频度排序线性表元素按照访问频度排序n问题：设计一个在线性表中实现问题：设计一个在线性表中实现Locate运算的函数，使得运算的函数，使得线性表中所有结点按访问频度递减的顺序排列，以使访问线性表中所有结点按访问频度递减的顺序排列，以使访问频繁高的结点总是靠近表头频繁高的结点总是靠近表头 n分析：运算主要包括分析：运算主要包括n查找查找n如果该元素比前一个频繁，则需要将其向前移动，也就如果该元素比前一个频繁，则需要将其向前移动，也就是插入和删除操作是插入和删除操作n结构选

8、择结构选择n查找：顺序或者链式均可；插入删除：链式存储查找：顺序或者链式均可；插入删除：链式存储n综合：选择链式综合：选择链式n哪种链式结构呢？哪种链式结构呢？n涉及前驱操作：双向链表涉及前驱操作：双向链表数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 线性表元素按照访问频度排序线性表元素按照访问频度排序n选用带头结点的双向链表选用带头结点的双向链表L，每个结点有，每个结点有4部分：部分：指向前驱结点的指针指向前驱结点的指针prior指向后继结点的指针指向后继结点的指针next存放数据的成员存放数据的成员data记载访问频度记载访问频度

9、freq，初始时所有结点的，初始时所有结点的freq都为都为0。n首先在链表中查找指定数据，如找到，将其首先在链表中查找指定数据，如找到，将其freq加加1，然后向前寻找然后向前寻找freq大于它的结点，并在该结点后面进行大于它的结点，并在该结点后面进行插入。插入。 prior freqdatanext数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 线性表元素按照访问频度排序线性表元素按照访问频度排序void Locate ( DuList L, ElemType x ) pNode p = L-next, q;while ( p &a

10、mp; 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;/*插入在插入在

11、p之后之后*/ q-prior = p; if(p-next)p-next-prior = q; p-next = q;else Error( Not found!n);/*没找到没找到*/prior freqdatanexttypedef struct nodeElemType data; int freq;struct node *prior,*next;*DuList, *pNode;思考：思考：能否不要第二个循环？能否不要第二个循环？数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 一元多项式的表示和相加一元多项式的表示和相加 n

12、一元多项式一元多项式n逻辑结构选择逻辑结构选择n要存放的是系数和相应的指数，为一个数据元素要存放的是系数和相应的指数，为一个数据元素n次序关系（？）次序关系（？）n线性表线性表n存储结构选择存储结构选择n顺序表如何存？顺序表如何存？n链表如何存？链表如何存？n各自的优点各自的优点/缺点？缺点？n运算运算/操作有哪些？操作有哪些？n综合考虑的结果是：综合考虑的结果是：数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 nnnxpxpxppxp.)(2210 在计算机中，可以用一个线性表来表示在计算机中，可以用一个线性表来表示: P = (p0

13、, p1, ，pn)一元多项式一元多项式但是对于形如但是对于形如 S(x) = 1 + 3x10000 2x20000的多项式，上述表示方法是否合适？的多项式，上述表示方法是否合适？一元多项式的表示和相加一元多项式的表示和相加 数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 一般情况下的一般情况下的一元稀疏多项式一元稀疏多项式可写成：可写成： Pn(x) = p1xe1 + p2xe2 + + pmxem其中：其中：pi 是指数为是指数为ei 的项的非零系数，的项的非零系数， 0 e1 e2 em = n可用线性表表示：可用线性表表示：

14、（p1, e1）, (p2, e2), ., (pm,em) ）数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 P999(x) = 7x3 - 2x12 - 8x999例如例如: ( (7, 3), (-2, 12), (-8, 999) )数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 ADT Polynomial 数据对象数据对象： 数据关系数据关系：抽象数据类型一元多项式的定义如下：抽象数据类型一元多项式的定义如下：D ai | ai TermSet, i=1,2,.,m,

15、 m0 TermSet 中的中的每个元素包含一个每个元素包含一个 表示系数的实数和表示指数的整数表示系数的实数和表示指数的整数 R1 |ai-1 ,aiD, i=2,.,n 且且ai-1中的指数值中的指数值ai中的指数值，中的指数值，按指数的升幂有序按指数的升幂有序 数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 链表定义链表定义typedef struct node / 多项式类型多项式类型的表示的表示 float coef; / 某项的某项的系数系数 int expn; / 某项的某项的指数指数 struct node *next;

16、 / 某项的后继某项的后继指针指针 node,polynomial; / 多项式类型定义完成多项式类型定义完成typedef polynomial *p1,*p2; /定义了两个多项式定义了两个多项式数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 2 3 -3 7 6 123 156 25-4 5 3 7 7 12 9 13-8 14 hahbhtpapbPA: 2x3-3x7+6x12+3x15+6x25PB: -4x5+3X7+7X12+9X13-8X1413数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学

17、 数据结构与算法数据结构与算法 作业一作业一 2.6习题（习题（P80）一、选择题一、选择题1-4二、填空题二、填空题1-4三、简答题三、简答题1-2四、算法设计题四、算法设计题1-2数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 回顾：线性表：回顾：线性表：n个相同元素的有限序列个相同元素的有限序列DS=（D，L，O，S）线性表的逻辑结构线性表的逻辑结构L：1对对1（前驱、后继）（前驱、后继）线性表的基本操作线性表的基本操作O：创建、取元素、插入、删除等创建、取元素、插入、删除等线性表的存储结构线性表的存储结构S：顺序、链式顺序、链式（单链表、双向链（单链表、双向链表、循环、双向循环）表、循环、双向循环）数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 数据结构关联图数据结构关联图 串串n n个字符的有限序列个字符的有限序列前驱后继数前驱后继数数据元素限制数据元素限制线性表的变型线性表的变型带头结点、循环、双向带头结点、循环、双向结点变化结点变化2.22.2栈栈 插入、删除限插入、删除限定在一端进行定在一端进行的线性表的线