数据结构考研分类复习真题 第十章 答案[32]

typedef struct node

{ ElemType data;

struct node *prior*next;

}node*DLinkedList;

void TwoWayBubbleSort(DLinkedList la)

//对存储在带头结点的双向链表la中的元素进行双向起泡排序

{int exchange=; // 设标记

DLinkedList ptemptail;

head=la //双向链表头算法过程中是向下起泡的开始结点

tail=null; //双向链表尾算法过程中是向上起泡的开始结点

while (exchange)

{p=head>next; //p是工作指针指向当前结点

exchange=; //假定本趟无交换

while (p>next!=tail) // 向下(右)起泡一趟有一最大元素沉底

if (p>data>p>next>data) //交换两结点指针涉及条链

{temp=p>next; exchange=;//有交换

p>next=temp>next;temp>next>prior=p //先将结点从链表上摘下

temp>next=p; p>prior>next=temp; //将temp插到p结点前

temp>prior=p>prior; p>prior=temp;

}

else p=p>next; //无交换指针后移

tail=p; //准备向上起泡

p=tail>prior;

while (exchange && p>prior!=head) //向上(左)起泡一趟有一最小元素冒出

if (p>data<p>prior>data) //交换两结点指针涉及条链

{temp=p>prior; exchange=; //有交换

p>prior=temp>prior;temp>prior>next=p //先将temp结点从链表上摘下

temp>prior=p; p>next>prior=temp; //将temp插到p结点后(右)

temp>next=p>next; p>next=temp;

}

else p=p>prior; //无交换指针前移

head=p; //准备向下起泡

}// while (exchange)

} //算法结束

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []