专门做饥饿营销的网站,wordpress时光轴,龙岩律师在线咨询,服务器网站搬家例2.5 已知单链表H#xff0c;写一算法将其倒置。即实现如图2.22的操作。(a)为倒置前#xff0c;(b)为倒置后。 算法思路#xff1a;依次取原链表中的每个结点#xff0c;将其作为第一个结点插入到新链表中去#xff0c;指针p用来指向当前结点#xff0c;p为空时结束。 算…例2.5 已知单链表H写一算法将其倒置。即实现如图2.22的操作。(a)为倒置前(b)为倒置后。 算法思路依次取原链表中的每个结点将其作为第一个结点插入到新链表中去指针p用来指向当前结点p为空时结束。 算法如下 1 void reverse (Linklist H)2 { 3 LNode *p;4 pH-next; /*p指向第一个数据结点*/5 H-nextNULL; /*将原链表置为空表H*/6 while (p) /*p结点不为空循环*/7 { 8 qp; /*用另一个结点q存储p结点的信息*/9 pp-next; /*不断后移*/
10 q-nextH-next; /*将当前结点插到头结点的后面*/
11 H-nextq; /*将头结点与当前结点相连*/
12 }
13 } 算法2.15 该算法只是对链表中顺序扫描一边即完成了倒置所以时间性能为O(n)。例2.6 已知单链表L写一算法删除其重复结点即实现如图2.23的操作。(a)为删除前(b)为删除后。算法思路用指针p 指向第一个数据结点从它的后继结点开始到表的结束找与其值相同的结点并删除之p 指向下一个依此类推p 指向最后结点时算法结束。 算法如下 1 void pur_LinkList(LinkList H)2 { 3 LNode *p,*q,*r;4 pH-next; /*p指向第一个结点*/5 if(pNULL) 6 return;7 while (p-next)8 { 9 qp;
10 while (q-next) /* 从*p的后继开始找重复结点*/
11 {
12 if (q-next-datap-data)
13 {
14 rq-next; /*找到重复结点用r指向删除*r */
15 q-nextr-next;
16 free(r);
17 }
18 else
19 qq-next;
20 }
21 pp-next; /*p指向下一个继续*/
22 }
23 } 算法2.16 该算法的时间性能为O(n2)。例2.7 设有两个单链表A、B其中元素递增有序编写算法将A、B归并成一个按元素值递减允许有相同值有序的链表C要求用A、B中的原结点形成不能重新申请结点。算法思路利用A、B两表有序的特点依次进行比较将当前值较小者摘下插入到C表的头部得到的C表则为递减有序的。 算法如下 1 LinkList merge(LinkList A,LinkList B)2 /*设A、B均为带头结点的单链表*/3 { 4 LinkList C; 5 LNode *p,*q;6 pA-next; /*A的第一个结点*/7 qB-next; /*B的第一个结点*/8 CA; /*C表的头结点*/9 C-nextNULL; /*C表置空*/
10 free(B); /*释放B的头结点*/
11 while (pq) /*p和q结点都存在*/
12 {
13 if(p-dataq-data) /*从原AB表上摘下较小者*/
14 {
15 sp; /*临时结点s指向p*/
16 pp-next;
17 }
18 else
19 {
20 sq;
21 qq-next;
22 }
23 s-nextC-next; /*C表的第一个结点赋给结点s的后继*/
24 C-nexts; /*将结点s赋给C表头结点的后继*/
25 }
26 if (pNULL)
27 pq;
28 while (p) /* 将剩余的结点一个个摘下插入到C表的头部*/
29 {
30 sp;
31 pp-next;
32 s-nextC-next;
33 C-nexts;
34 }
35 } 算法2.17 该算法的时间性能为O(mn)。转载于:https://www.cnblogs.com/chunlanse2014/articles/4439661.html
