|
本题添加时间：2023/4/3 12:59:00 |
|
圆梦客服：王老师 19139051760(微信同号) 19139051760(微信同号) |
|
有n个记录存储在带头结点的双向链表中，现用双向冒泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向冒泡排序即相邻两趟排序向相反方向冒泡）。
|
答案是:typedef struct node { ElemType data; struct node *prior,*next; }node，*DLinkedList; void TwoWayBubbleSort(DLinkedList la) //对存储在带头结点的双向链表la中的元素进行双向起泡排序。 {int exchange=1; // 设标记 DLinkedList p,temp,tail; head=la //双向链表头，算法过程中是向下起泡的开始结点 tail=null; //双向链表尾，算法过程中是向上起泡的开始结点 while (exchange) {p=head->next; //p是工作指针，指向当前结点 exchange=0; //假定本趟无交换 while (p->next!=tail) // 向下（右）起泡，一趟有一最大元素沉底 if (p->data>p->next->data) //交换两结点指针，涉及6条链 {temp=p->next; exchange=1;//有交换 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->dataprior->data) //交换两结点指针，涉及6条链 {temp=p->prior; exchange=1; //有交换 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) } //算法结束
出自
河南理工大学数据结构 联大系统
太原理工大学
|
更多试题>>>>
1、试以单链表为存储结构，实现简单选择排序算法
2、对22个记录的有序表作折半查找，查找失败时，至少需要比较___个关键字。
3、m阶B-树的非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树。
A.正确
B.错误
4、分别写出在散列表中插入和删除关键字为K的一个记录的算法，设散列函数为H，解决冲突的方法为链地址法。
5、假设一棵平衡二叉树的每个结点都表明了平衡因子b，试设计一个算法，求平衡二叉树的高度。
|
