帮忙做道C语言的题:双向链表的排序？C语言双向链表排序

本文目录

• 帮忙做道C语言的题:双向链表的排序
• C语言双向链表排序

帮忙做道C语言的题:双向链表的排序

#include 《stdio.h》
typedef struct Link/*双向链表结构体*/
{
int data;
struct Link *lift;
struct Link *right;
}linkx,*linky;
linky Init();/*建立双向链表*/
void PrLink(linky p);/*输出双向链表*/
linky Sort(linky head);/*对双向链表排序*/
linky Swap(linky head,linky one,linky two);/*任意交换双向链表两个结点的地址*/
void main(void)
{
linky head;
head=Init();
head=Sort(head);
PrLink(head);
}
linky Init()/*建立链表*/
{
linky p,q,head;
int n=0;
head=p=q=(linky)malloc(sizeof(linkx));
clrscr();
printf("please input 10 num: ");
scanf("%d",&p-》data);/*输入数据*/
head-》lift=NULL;
n++;
while(n!=10)/*一直输入到规定的数字个数停止*/
{
q=p;
p=(linky)malloc(sizeof(linkx));
scanf("%d",&p-》data);/*输入数据*/
q-》right=p;
p-》lift=q;
n++;
}
p-》right=NULL;
return(head);
}
linky Swap(linky head,linky one,linky two)/*任意交换两个结点*/
{linky temp;
if(one-》lift==NULL&&two-》right==NULL)/*首和尾巴的交换*/
{
if(one-》right==two)/*只有两个结点的情况下*/
{
two-》right=one;
two-》lift=NULL;
one-》lift=two;
one-》right=NULL;
head=two;
}
else/*有间隔的首尾交换*/
{
one-》right-》lift=two;
two-》lift-》right=one;
two-》right=one-》right;
one-》lift=two-》lift;
two-》lift=one-》right=NULL;
head=two;/*尾结点成为头结点*/
}
}
else if(two-》right==NULL)/*尾和任意一个交换*/
{
if(one-》right==two)/*交换最后两个结点*/
{
one-》lift-》right=two;
two-》lift=one-》lift;
two-》right=one;
one-》lift=two;
one-》right=NULL;
}
else/*和前面其他结点交换*/
{
temp=two-》lift;
temp-》right=one;
one-》lift-》right=two;
one-》right-》lift=two;
two-》lift=one-》lift;
two-》right=one-》right;
one-》lift=temp;
one-》right=NULL;
}
}
else if(one-》lift==NULL)/*头和任意一个交换*/
{
if(one-》right==two)/*交换头两个结点*/
{
two-》right-》lift=one;
one-》right=two-》right;
one-》lift=two;
two-》right=one;
two-》lift=NULL;
head=two;
}
else/*头结点和后面其他结点交换*/
{
temp=one-》right;
temp-》lift=two;
one-》lift=two-》lift;
one-》right=two-》right;
two-》lift-》right=one;
two-》right-》lift=one;
two-》right=temp;
two-》lift=NULL;
head=two;/*交换的结点成为头结点*/
}
}
else/*当中的任意两个交换*/
{
if(one-》right==two)/*交换连在一起的两个结点*/
{
temp=one-》lift;
one-》lift-》right=two;
one-》right-》lift=two;
one-》lift=two;
one-》right=two-》right;
two-》right-》lift=one;
two-》right=one;
two-》lift=temp;
}
else/*交换隔开的两个结点*/
{
one-》lift-》right=two;
one-》right-》lift=two;
one-》lift=two-》lift;
temp=one-》right;
one-》right=two-》right;
two-》lift-》right=one;
two-》right-》lift=one;
two-》right=temp;
two-》lift=one-》lift;
}
}
return(head);
}
linky Sort(linky head)/*对链表排序*/
{
linky i,j,t,p;
int max;
p=head;
for(i=p;i-》right!=NULL;i=i-》right)/*用选择法的思想对这些结点排序*/
{
max=i-》data;
for(j=i-》right;j!=NULL;j=j-》right)
if(j-》data《max)
{
max=j-》data;
t=j;
}
if(max!=i-》data)/*如果没有找到比i小的结点*/
{
head=Swap(head,i,t);/*因为最终返回的是头结点,而头结点又有可能变化,所以每次头结点返回*/
i=t;
}
}
return(head);
}
void PrLink(linky p)/*输出链表*/
{
linky q;
printf("Now the link: ");
do
{
q=p;
printf("%d ",p-》data);
p=p-》right;
free(q);/*释放输出结点*/
}
while(p!=NULL);
getch();
}

C语言双向链表排序

删除节点就是把某个节点从链表中取出,释放掉内存,把它前后节点再相连;
序号就是节点的位置,比如头结点就是1,头结点的下一个节点就是2以此类推;
数值就是随便一个数,比如每个节点都有一个int类型的变量,按这个变量的值从小到大或从大到小排序;