发布时间: 2018年11月26日 10:09 时间限制: 1000ms 内存限制: 128M
习题集源码中出现了 temp->next->prior = p; 本人推断这里缺少预先的对temp->next==NULL这种情况的判定，所以需加入一个判断语句解决。
此为非循环的双向链表，末尾空指针没有前驱，与循环双向链表有所不同。
描述
有n个记录存储在带头结点的双向链表中，利用双向冒泡排序法对其按上升序进行排序，请写出这种排序的算法。(注：双向冒泡排序即相邻两趟排序向相反方向冒泡)。
输入
多组数据，每组数据两行。第一行为序列的长度n，第二行为序列的n个元素（元素之间用空格分隔，元素都为正整数）。当n等于0时，输入结束。
输出
每组数据输出一行，为从小到大排序后的序列。每两个元素之间用空格隔开。
样例输入1
54 5 3 2 961 3 5 7 9 20
样例输出1
2 3 4 5 91 2 3 5 7 9
1 //双向冒泡，最大沉底，最小冒出 2 #include3 using namespace std; 4 typedef struct node 5 { 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->next=NULL的可能，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 (exchange&&p->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 cin>>p->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 }