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

数据结构与算法主讲：林劼副教授

电子科技大学计算机学院顺序与链式存储结构比较顺存储结构的特点逻辑上相邻的元素，其物理位置也相邻；可随机存取表中任一元素必须按最大可能长度预分存储空间，存储空间利用率低，表的容量难以扩充，是一种静态存储结构插入删除时，需移动大量元素，平均移动元素为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：voidList_Reverse(ListPtrL){inti=1,j=L->length; ElemTypetemp; while(i<j){ temp=L->elem[i]; L->elem[i]=L->elem[j]; L->elem[j]=temp; i++;j--;

}}思考：能否用for循环？1.线性表倒置在单链表上按算法2（前驱后继关系互换）实现P.42：voidList_Reverse(ListPtrL){ListNodePtrq,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大于它的结点，并在该结点后面进行插入。priorfreqdatanext线性表元素按照访问频度排序voidLocate(DuListL,ElemTypex){

pNodep=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->next->prior=q; p->next=q;

} else Error("Notfound!\n"); /*没找到*/}priorfreqdatanexttypedefstructnode{ElemTypedata;intfreq;structnode*prior,*next;}*DuList,*pNode;思考：能否不要第二个循环？一元多项式的表示和相加一元多项式逻辑结构选择要存放的是系数和相应的指数，为一个数据元素次序关系（？）线性表存储结构选择顺序表如何存？链表如何存？各自的优点/缺点？运算/操作有哪些？综合考虑的结果是：在计算机中，可以用一个线性表来表示:P=(p0,p1,…，pn)一元多项式但是对于形如

S(x)=1+3x10000–2x20000的多项式，上述表示方法是否合适？一元多项式的表示和相加一般情况下的一元稀疏多项式可写成：

Pn(x)=p1xe1+p2xe2+┄+pmxem其中：pi

是指数为ei

的项的非零系数，

0≤e1<e2<┄<em=n可用线性表表示：（（p1,e1）,(p2,e2),...,(pm,em)）

P999(x)=7x3-2x12-8x999例如:

((7,3),(-2,12),(-8,999))ADTPolynomial{

数据对象：

数据关系：抽象数据类型一元多项式的定义如下：D＝{ai|ai∈TermSet,i=1,2,...,m,m≥0TermSet中的每个元素包含一个表示系数的实数和表示指数的整数

}R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n

且ai-1中的指数值＜ai中的指数值，按指数的升幂有序

}链表定义typedefstructnode{//多项式类型的表示

floatcoef;//某项的系数

intexpn;//某项的指数

structnode

*next;//某项的后继指针}

node,polynomial;//

多项式类型定义完成typedefpolynomial*p1,*p2;//定义了两个多项式23-37612315625-4537712913-814hahbhtpapbPA:2x3-3x7+6x12+3x15+6x25PB:-4x5+3X7+7X12+9X13-8X1413作业一2.6习题（P80）一、选择题1----4二、填空题1----4三、简答题1----2四、算法设计题1----2回顾：线性表：n个相同元素的有限序列DS=（D，L，O，S）线性表的逻辑结构L：1对1（前驱、后继）线性表的基本操作O：创建、取元素、插入、删除等线性表的存储结构S：顺序、链式（单链表、双向链表、循环、双向循环）数据结构关联图

串n个字符的有限序列前驱后继数数据元素限制线