带头结点的单链表(2)

例：多项式p1为：18x17+9x8+4x2+3x多项式p2为：12x12+7x8+4x3多项式运算p1+p2的结果为：18x17+12x12+16x8+4x3+4x2+3x从上述的链表创建算法可以创建出两个对应的链表先利用两个指针，pa和pb，分别指向两个多项式的结点。为了体现功能的正常性，至少要编制遍历数据的函数.数据的逻辑结构设计和运算定义需要实现线性表的以下功能:1、创建单链表 2、删除链表中的某个结点 3、输出单链表(遍历) 4、释放结点所占空间5、查找第i个结点 6、插入一个结点 7、求链表的长度三. 数据的存储结构设计和算法设计(1).数据结构线性表的线性结构觉决定了它的性质：数据元素之间是一种线性关系，数据元素一个接一个的排列，除了最后一个数据，其他的数据面临的下一个数据有且仅有一个。五．附录．create()创建单链表，由用户输入各结点data域值，以０表示输入结束，最后返回建立的单链表头指针．．disp(nodetype *h)：输出单链表h的所有结点的data域的值．．len(nodetype *h)：返回单链表h的长度．．find(nodetype *h,int i):返回单链表h中第i个结点的指针．．ins(nodetype *h,int i,elemtype x)：在单链表h中第i个结点（i>=0）之后插入一个data域为x的结点，并返回插入结点后的单链表的头指针．．del(nodetype *h,int i):删除单链表h中第i个结点，并返回插入结点后的单链表的头指针．．dispose(nodetype *h):释放单链表h中所有结点占用的存储空间．。

（3）单链表的插入运算之------- ②前插操作：45③q p⑤④①X②SINSERTBEFORE（head,p,x） /*在带头结点的单链表head中,将值为X的新结点插入*P之前*/JD *head,*p;datatype x;{JD *q,*s;前插算法：前插算法的平均时间复杂度为：O（n）46s=（JD *）malloc(sizeof(JD));/*生成新结点*/s->data=x;q=head;/*从头指针开始*/While(q->next!=p) q=q->next;/*找*p的前趋结点*/s->next=p；q->next=s;/*将*s插入*p之 前*/} /*INSERTBEFORE */（3）单链表的基本运算之------- ③改进的前插算法算法思想：后插算法为O(1)，而前插算法为O(n)，改进后可在*p之后先插入新结点*s然后交换*s和*p的值。算法描述（思考）：47 后插法插入结点S后，交换*S和*p：交换值： { t=p->data; p->data=s->data;s->data=t; }交换指针：{ p=p->next }插入前 p… …sAX48插入后 p… …sxA(4)删除运算 删除单链表中*p的后继 算法描述：DeleteA(p)/*删除*p的后继结点*r,设*r存在*/JD *p;{JD * 单链表的基本运算49{JD *r;If (p->next!=null){ r=p->next; p->next=r->next;free(p);}}/*enddelete*/p存储池r 思考：（1）如何删除单链表中p结点本身？（2）如何删除单链表中p结点的前趋结点？例1-7：在单链表上实现线性表的删除运算Delete(L i)50算Delete(L,i)。

2)在判断是否到表尾时，是判断该结点链域的值是否是表头结点，当链域值等于表头指针时，说明已到表尾。2、在判断是否到表尾时，是判断该结点链域的值是否是表头结点，当链域值等于表头指针时，说明已到表尾。还是对于双向循环链表，要在连续的三个结点s,p,q中删除p结点，只需把s的右链域指针指向q，q的左链域指针指向s，并收回p结点就完成了。

双向链表的基本运算: 1、查找 假若我们要在一个带表头的双向循环链表中查找数据域为一特定值的某个结点时, 我们 同样从表头结点往后依次比较各结点数据域的值, ...。（注意：在使用这个函数获得尾结点指针时，必须在每次插入结点元素后重新获得，因为链表尾部结点是会随着结点的插入而发生变化）。这只需要修改输出链表的尾结点中的指针域，令其指向箱子链表的头，然后修改输出链表的尾指针，令其指向箱子链表的尾即可。

若要找某一结点的前趋，则：单链表 从头顺链找 O(n)59单链表：从头顺链找。O(n)单循环链表：可从任一已知结点出发查。O(n) 双向链表（Double linked list)----单链表的每个结点再增加一个指向其前趋的指针域prior，这样形成的链表有两条不同方向的链，称之为双（向）链表。特点：双链表一般也由头指针head唯一确定。每一结点均有60每一结点均有：数据域（data)左链域 （prior) 指向前趋结点. 右链域 （next) 指向后继结点。是一种对称结构（既有前趋，又有后继）。 （1）双向链表的分类： 非循环双向链表 循环双向链表此外，为了定义运算方便起见，还可添加一表头结点。 （2）双链表的结点类型描述61typedef struct dnode{datatype data;struct dnode *prior,*next;}dlinklist;dlinklist *head; (3)结点结构62 (4)双链表结构对称性描述：p->prior->next=p->next->prior=p即：结点*p的存储位置既存放在其前趋结点（* > i )的后继63既存放在其前趋结点（*p->prior)的后继指针域中；也存放在其后继结点（*p->next)的前趋指针域中。

 (5)双链表的基本运算：插入、删除、查找在单链表中，前插不如后插方便；删除某结点自身不如删除该结点的后继方便。64某结点自身不如删除该结点的后继方便而在双向链表中，上述的运算均十分方便。 (前)插入操作（将结点x插入*p之前）/*在带头结点的双链表中，将值为x的新结点插入到*p 之前。*/Dinsert (p,x)dlinklist *p;datatype x;{ dli kli t *65{ dlinklist *s;s=malloc(sizeof(dlinklist));s->data=x;s->prior=p->prior; s->next=p;p->prior->next=s; p->prior=s;} /*enddinsert*/③⑤px66①②③④sa⑥ 删除操作（在双向链表中删除p结点）Ddelete(p)dlinklist *p;{p->prior->next=p->next;p >next >prior=p >prior;67p->next->prior=p->prior;free(p);}/*endDdelete*/ 查找（在带头结点双向循环链表中查找结点x） 算法思想：从第一个结点开始（头结点的后继）依次比较每个结点的数据域的值，若找到结点x则返回指向该结点的指针；否则：68x则返回指向该结点的指针；否则：若又回到头结点，说明表中不存在头结点x，则返回空指针。

算法描述：参见教材描述的算法。 关于顺序表和链表的小结：（1）顺序是用数组实现的，而链表是用指针或“游标”来实现的。（2）当线性表的长度变化较大，难以估计其存储规模时， 益采用动态链表作为存储结构为佳 当线性表的长度变化不69存储结构为佳；当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。（基于空间的考虑） （3）顺序表是一种随机存取结构，对表中任一结点都可在O(1)时间内直接存取。而链表中的结点则需用从头指针开始顺链扫描。因此：若线性表的操作主要是查找，很少涉及到70插入、删除操作时，可采用顺序表结构。若要频繁地进行插入和删除操作，宜采用链表作为存储结构。若表的插入、删除操作主要发生在表的两端，则宜采用有尾指针的单循环链表。 2.4 线性表的应用举例一元多项式的表示及相加 一元多项式的表示：nn nx P x P x P P x P       22 1 0) () , , , , (2 1 0 nP P P P P    可用线性表P表示20000 10002 3 1 ) ( x x x S    但对S(x)这样的多项式浪费空间71一般emm nx P x P x P x Pe e     2 12 1) (其中 为非零系数） （iP em e e      2 1 0用数据域含两个数据项的线性表表示       em P e P e Pm ，， ， ， ，   2 12 1其存储结构可以用顺序存储结构，也可以用单链表 单链表的结点定义typedef struct node{ int coef,exp;struct node *next;}JD;typedef struct node{ int coef,exp;struct node *next;}JD;coef expnext8 717 89 22 8 ) (5 9 3 7 ) (Bx x x x A    一元多项式相加7217 78 75 22 11 7 ) ( ) ( ) (9 22 8 ) (x x x x B x A x Cx x x x B       -1A7031985 17 ^ -1B8122 7-9 8 ^ -1A7011 122 75 17 ^ 设p,q分别指向A,B中某一结点，p,q初值是第一结点比较p->exp与q->expp->exp < q->exp: p结点是和多项式中的一项p后移,q不动p->exp > q->exp: q结点是和多项式中的一项将q插在p之前,q后移,p不动> > 系数相加0：从A表中删去p, 运算规则73p->exp = q->exp: 系数相加p释放p,q，p,q后移0：修改p系数域,释放q，p,q后移直到p或q为NULL若q==NULL，结束若p==NULL，将B中剩余部分连到A上即可-1pa7031985 17 ^ ppre-1pa7031985 17 ^ p pre-1pa7011 1985 17 ^ p-1pa7011 1985 17 ^ ppre-1pa7011 1985 17 ^ p-1pa7011 1985 17 ^ p 算法描述74q-1pb8122 7-9 8 ^ q-1pb8122 7-9 8 ^ q-1pb8122 7-9 8 ^ pre q-1pb8122 7-9 8 ^ q=NULL -1pb8122 7-9 8 ^ preq=NULL -1pb8122 7-9 8 ^ pre-1pa7011 122 75 17 ^

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-96930-2.html