双向链表的结构体,包括一个前驱节点的指针、一个后继节点的指针以及一个存储数据的data域,initList函数初始化单节点的双链表,addList函数采用头插入方法添加一个节点到双链表中,sort函数实现了对双链表的排序,采用头插入方式建成的双链表的头结点(存储65535的那个节点)必然在末尾(其实双链表没有首尾之说,只是把它当作末尾),排序的时候,1.首先从该节点处,每次查找前驱节点,并记录data获取链表中data最大的节点,并记录指向这个节点的指针和其值。2.将此节点采用头插入的方式插入到链表中(注意要先删除这个节点在链表中的位置)3.再次从头节点处,通过前驱节点遍历整个链表(此时要去掉第一次找到的最大值)找到最大值。
typedef struct node{
int data;
struct node *prior,*next;
}Link;
void initList(Link *head){//初始化头结点
head->next = head;
head->prior = head;
head->data = 65535;
}
void addList(Link *head,int data){//创建链表
Link *tmp;
tmp = (Link *)malloc(sizeof(Link));
tmp->data = data;
tmp->next = head->next;
head->next->prior = tmp;
head->next = tmp;
tmp->prior= head;
}
void sort(Link *head){
Link *p,*tmp,*flag;
int max;
p = (Link *)malloc(sizeof(Link));
tmp = (Link *)malloc(sizeof(Link));
flag = (Link *)malloc(sizeof(Link));
tmp = head->prior;
max = tmp->data;
flag = tmp;
p = tmp->prior;
while(p->data != 65535){//找到值最大的节点并且标记
if(p->data > max){
max = p->data;
flag = p;
flag->data = max;
}
p = p->prior;
}
if(flag->data!=head->next->data)
{//交换最大值点到头节点后
flag->prior->next = flag->next;
flag->next->prior = flag->prior;
flag->next = head->next;
flag->prior = head;
head->next->prior = flag;
head->next = flag;
}
while(head->prior->data != flag->data){
tmp = head->prior;//重新寻找时总是从表尾,也就是头结点的前驱开始。
p = tmp->prior; //从后往前寻找
while(p->data != flag->data){//找到要交换的节点
if(p->data > tmp->data){
tmp = p;
}
p = p->prior;
}
{//交换两个节点
tmp->prior->next = tmp->next;
tmp->next->prior = tmp->prior;
tmp->next = head->next;
tmp->prior = head;
head->next->prior = tmp;
head->next = tmp;
}
}
}
主函数的调用代码就比较简单了。
int _tmain(int argc, _TCHAR* argv[])
{
Link *head,*p;
head =(Link *)malloc(sizeof(Link));
p =(Link *)malloc(sizeof(Link));
int i;
int a[15]={7,4,2,7,5,8,6,3,2,4,5,7,98,3,4};
initList(head);
for(i=0;i<15;i++){
addList(head,a[i]);
}
p = head->next;
while(p->data!=65535){
printf(“%d<–>”,p->data);
p = p->next;
}
printf(“\n”);
sort(head);
p = head->next;
while(p->data!=65535){
printf(“%d<–>”,p->data);
p = p->next;
}
printf(“\n”);
getchar();
}
今天的文章双向链表排序分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/7728.html