网站建设公司简介,wordpress注册按钮,罗岗网站建设公司,搜索引擎优化的完整过程基于双向链表的双向冒泡排序法 发布时间: 2018年11月26日 10:09 时间限制: 1000ms 内存限制: 128M 习题集源码中出现了 temp-next-prior p; 本人推断这里缺少预先的对temp-nextNULL这种情况的判定#xff0c;所以需加入一个判断语句解决。 此为非循环的双向链…基于双向链表的双向冒泡排序法 发布时间: 2018年11月26日 10:09 时间限制: 1000ms 内存限制: 128M 习题集源码中出现了 temp-next-prior p; 本人推断这里缺少预先的对temp-nextNULL这种情况的判定所以需加入一个判断语句解决。 此为非循环的双向链表末尾空指针没有前驱与循环双向链表有所不同。 描述 有n个记录存储在带头结点的双向链表中利用双向冒泡排序法对其按上升序进行排序请写出这种排序的算法。(注双向冒泡排序即相邻两趟排序向相反方向冒泡)。 输入 多组数据每组数据两行。第一行为序列的长度n第二行为序列的n个元素元素之间用空格分隔元素都为正整数。当n等于0时输入结束。 输出 每组数据输出一行为从小到大排序后的序列。每两个元素之间用空格隔开。 样例输入1 5
4 5 3 2 9
6
1 3 5 7 9 2
0 样例输出1 2 3 4 5 9
1 2 3 5 7 9 1 //双向冒泡最大沉底最小冒出2 #includeiostream3 using namespace std;4 typedef struct node5 {6 int data;7 struct node *prior, *next;8 }node, *LinkList;9 void TwoWayBubbleSort(LinkList L)
10 //对存储在带头结点的双向链表L中的元素进行双向起泡排序。
11 {
12 int exchange 1;//设标记
13 LinkList head L;//双向链表头算法过程中是向下起泡的开始结点
14 LinkList tail NULL;//双向链表尾算法过程中是向上起泡的开始结点
15 while(exchange)
16 {
17 LinkList p head-next;//p是工作指针指向当前结点
18 exchange 0;//假定本趟无交换
19 while (p-next ! tail)//向下(右)起泡一趟有一最大元素沉底
20 {
21 if (p-data p-next-data)//交换两结点指针涉及6条链
22 {
23 LinkList temp p-next; exchange 1;//有交换
24 p-next temp-next;
25 if(temp-next)temp-next-prior p;//先将结点从链表上摘下
26 //attention存在temp-nextNULL的可能NULL-prior无法访问
27 temp-next p; p-prior-next temp;//将temp插到p结点前
28 temp-prior p-prior; p-prior temp;
29 //p p-next;
30 }
31 else p p-next;//无交换指针后移
32 }
33 tail p;//准备向上起泡
34 p tail-prior;
35 while (exchangep-prior ! head)//向上(左)起泡一趟有一最小元素冒出
36 {
37
38 if (p-data p-prior-data)//交换两结点指针涉及6条链
39 {
40 LinkList temp p-prior; exchange 1;//有交换
41 p-prior temp-prior; temp-prior-next p;
42 //先将temp结点从链表上摘下
43 temp-prior p; p-next-prior temp;
44 //将temp插到p结点后(右)
45 temp-next p-next; p-next temp;
46 }
47 else p p-prior;//无交换指针前移
48 }
49 head p;//准备向下起泡
50 }
51 }
52 void Create(LinkList L, int n)
53 {
54 LinkList p, rear;
55 L new node;
56 L-next NULL;
57 L-prior NULL;
58 rear L;
59 while (n--)
60 {
61 p new node;
62 cinp-data;
63 p-next rear-next;
64 rear-next p;
65 p-prior rear;
66 rear p;
67 }
68 }
69 int main()
70 {
71 int n;
72 while (true)
73 {
74 cin n;
75 if (!n)break;
76 else
77 {
78 LinkList L;
79 Create(L, n);
80 TwoWayBubbleSort(L);
81 LinkList p L-next;
82 while (p-next)
83 {
84 cout p-data ;
85 p p-next;
86 }
87 cout p-data endl;
88 }
89
90 }
91 return 0;
92 } 转载于:https://www.cnblogs.com/wind-chaser/p/10049548.html
