数据结构课件ex2章节幻灯片.ppt

算法: status shlingklist ( linklist L) { p=L; WHILE (p-next != L) { P-next-prior=p; p=p-next; } L-prior=p; } 题2.38 在双向循环链表的结点中，增加一个访问频度的数据域 freq，编写算法实现 LOCATE(L,x)。 注意算法的实施要点： （1）算法的基本操作应该是在链表中进行有哪些信誉好的足球投注网站, 直至( p==L || p-data==x )为止; （2）在访问频度 freq 增 1 之后，需将该结点调整到适当位置。向前有哪些信誉好的足球投注网站直至找到一个访问频度大于它的结点为止。 访问频度 返回指向被访结点的指针。 （3）调整结点位置 = 删除 + 插入 返回 p=L-next; // L为双向链表的头指针 while (p!=L p-data!=x) p=p-next; // 有哪些信誉好的足球投注网站元素值为 x 的结点*p if (p==L) return NULL; q=p-priou; while (q!=L q-freqp-freq) q=q-priou; //有哪些信誉好的足球投注网站访问频度不小于它的结点*q 将结点 *p 从当前位置上删除; 之后将结点 *p 插入在结点 *q 之后; return p; 题 2.41 void Difference_L( LinkedPoly pa ) { // pa 为指向稀疏多项式循环链表的头指针， // 本算法将链表改变为该多项式的导函数 p = pa-next; pre = pa; while ( p !=pa ) { if ( p-data.exp != 0) { p-data.coef*=p-data.exp-- ; pre = p; } else { // 删除零次项 pre-next = p-next; delete p; }//else p = pre-next; }//while }//Difference_L 返回 p=q=hlink-next; while (p) { p-next=hlink-next; hlink-next=p; q=q-next; p=q; } q=p; q-next=NULL; p=p-next; p-next=hlink; q-next=p; free(p-next); 第二章主要内容 线性表的类型定义 线性表的两种存储结构的定义 顺序表和链表的各种操作的算法描述及其时间复杂度的分析 有序表类型及有序表操作的实现 顺序表 查询 插入 删除 i=0; while (iva.length va.elem[i]!=x) i++; for ( j=va.length; j=i; j-- ) va.elem[j]=va.elem[j-1]; va.length++; for (j=i; jva.length; j-- ) va.elem[j-1]=va.elem[j]; va.length--; 单链表 查询 插入 删除 p=ha-next; while ( p!=NULL p-data!=x ) p=p-next; s=new LNode; s-next=p-next; p-next=s; q=p-next; p-next=q-next; delete(q); j=1; j i ｊ＋＋ 双链表 查询 插入 删除 p=ha-next; while ( p!=NULL p-data!=x ) p=p-next; s=new Lnode; s-next=p-next; p-next=s; q=p-next; p-next=q-next; delete(q); s-next-prior=s; s-prior=p; p-next-prior=p; 有序表操作的特点 1. 查询的结果同时得到插入的位置 i=0; while (iva.length va.elem[i]x) i++; 链表 p=ha; while ( p!=NULL p-next-datax ) p=p-next; 顺序表 2. 所有操作必须考虑其“有序”的特点 初始化处理; while ( 表A不空 表B不空 ) { ………… } ;