双链表排序函数c语言,C语言单链表三种排序方法

双向链表的排序...（用c语言编写程序）？

#include

#include

struct node

{

int data;

struct node* next;

struct node* prev;

};

struct node* create_list(int n)

{

struct node *head = null;

struct node *p = null, *q = null;

int i = 0, data = 0;

for (i = 0; i n; i++)

{

printf("请输入结点%d的值：", i+1);

scanf("%d", data);

p = (struct node*)malloc(sizeof(struct node));

p-next = null;

p-data = data;

if (i == 0)

{

head = p;

p-prev = null;

}

else

{

p-prev = q;

q-next = p;

}

q = p;

}

return head;

}

void free_list(struct node* head)

{

struct node* p = head;

struct node* q = null;

while (p != null)

{

q = p;

p = p-next;

delete q;

}

}

void display_list(struct node* head)

{

struct node* p = head;

while (p != null)

{

printf("%d ", p-data);

p = p-next;

}

printf("\n");

}

struct node* get_max_node(struct node* node)

{

struct node* max_node = node;

while (node != null)

{

if (node-data max_node-data)

{

max_node = node;

}

node = node-next;

}

return max_node;

}

void swap_node(struct node* node1, struct node* node2)

{

int temp;

if (node1 == node2)

{

return;

}

temp = node1-data;

node1-data = node2-data;

node2-data = temp;

}

void sort_list(struct node* head)

{

struct node* max_node = null;

struct node* current = null;

current = head;

while (current != null)

{

max_node = get_max_node(current);

swap_node(current, max_node);

current = current-next;

}

}

int main()

{

struct node *head = null;

int n = 0;

printf("请输入双向链表的结点个数：");

scanf("%d", n);

head = create_list(n);

display_list(head);

sort_list(head);

display_list(head);

free_list(head);

return 0;

}

相关问答

Q1: 求高手做个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==NULLtwo-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-datamax)

{

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();

}

Q2: c语言数据结构（双向链表排序）

#includestdio.h

#includemalloc.h

#define ElemType int

int count=0;

typedef struct DulNode

{

ElemType data;

DulNode *prior;

DulNode *next;

}DulNode,*DulLinkList;

//初始化链表，结束后产生一个头结点指针

void InitDLList(DulLinkList *L)

{

(*L)=(DulLinkList)malloc(sizeof(DulNode));

(*L)-next=*L;

(*L)-prior=(*L)-next;

}

//对链表进行插入操作

void ListInsert(DulLinkList *L)

{

int i=0,n;

ElemType temp;

DulNode *s,*p;

p=(*L)-next;

printf("请输入插入元素数量：\n");

scanf("%d",n);

count=n;

printf("请输入%d个自然数\n",n);

while(in)

{

scanf("%d",temp);

s=(DulNode*)malloc(sizeof(DulNode));

s-data=temp;

while((p!=(*L))(p-datatemp))//查找所要插入的位置

{

p=p-next;

}

s-prior=p-prior;//新节点的插入

s-next=p;

p-prior-next=s;

p-prior=s;

p=(*L)-next;//将指针回指到链表第一个非空节点，主要是为了下次查找插入位置

i++;

}

}

void Display(DulLinkList L)

{

DulNode *p;

p=L-next;

printf("双向链表中的数据为:\n");

while(p!=L)

{

printf("%d ",p-data);

p=p-next;

}

printf("\n");

}

void Sort(DulLinkList *L)

{

ElemType temp;

DulNode *p,*q;

p=(*L)-next;

q=(*L)-prior;

if(count%2!=0)

q=q-prior;

p=p-next;

while(p!=q)

{

temp=p-data;

p-data=q-data;

q-data=temp;

p=p-next;

if(p!=q) //第二题只需交换节点数据

q=q-prior;//这几个if else语句需要仔细

else

break;

if(p!=q)

p=p-next;

else

break;

if(p!=q)

q=q-prior;

else

break;

}

}

void main()

{

DulLinkList L;

InitDLList(L);//初始化链表

ListInsert(L);//顺序插入数据

Display(L);//显示结果

Sort(L);//第二题操作

Display(L);//第二题输出结果

}

Q3: 双向链表排序c语言程序设计

/************************************************************************/

/*

文件名 doublelnk.h

作用 定义必要的结构体，并对双向链表的操作函数做声明

*/

/************************************************************************/

#ifndef DList_H

#define DList_H

typedef  int Item;

typedef struct Node * PNode;

typedef PNode Position;

/*定义节点类型*/

typedef struct Node

{

Item id; /*编号*/

Item data; /*数据域*/

PNode previous; /*指向前驱*/

PNode next; /*指向后继*/

}Node;

/*定义链表类型*/

typedef struct

{

PNode head; /*指向头节点*/

PNode tail; /*指向尾节点*/

int size;

}DList;

enum enumSortType

{

ID,

DATA

};

/*分配值为i的节点，并返回节点地址*/

Position MakeNode(Item id, Item data);

/*释放p所指的节点*/

void FreeNode(PNode p);

/*构造一个空的双向链表*/

DList* InitList();

/*摧毁一个双向链表*/

void DestroyList(DList *plist);

/*将一个链表置为空表，释放原链表节点空间*/

void ClearList(DList *plist);

/*返回头节点地址*/

Position GetHead(DList *plist);

/*返回尾节点地址*/

Position GetTail(DList *plist);

/*返回链表大小*/

int GetSize(DList *plist);

/*返回p的直接后继位置*/

Position GetNext(Position p);

/*返回p的直接前驱位置*/

Position GetPrevious(Position p);

/*将pnode所指节点插入第一个节点之前*/

PNode InsFirst(DList *plist,PNode pnode);

/*将链表第一个节点删除并返回其地址*/

PNode DelFirst(DList *plist);

/*获得节点的数据项*/

Item GetItem(Position p);

/*设置节点的数据项*/

void SetItem(Position p,Item i);

/*删除链表中的尾节点并返回其地址，改变链表的尾指针指向新的尾节点*/

PNode Remove(DList *plist);

/*在链表中p位置之前插入新节点S*/

PNode InsBefore(DList *plist,Position p,PNode s);

/*在链表中p位置之后插入新节点s*/

PNode InsAfter(DList *plist,Position p,PNode s);

/*返回在链表中第i个节点的位置*/

PNode LocatePos(DList *plist,int i);

void ListTraverse(DList *plist,void (*visit)(Node));

/*对双向链表按照执行的排序方式进行排序*/

void SortDLnk(DList * plist, enumSortType sortType);

void SortDLnkbyID(DList * plist);

void SortDLnkbyData(DList * plist);

void swapnode(PNode anode, PNode bnode);

#endif

/************************************************************************/

/*

文件名 doublelnk.cpp

作用 对双向链表的操作函数进行具体实现

*/

/************************************************************************/

#include"doublelnk.h"

#includemalloc.h

#includestdlib.h

/*分配值为i的节点，并返回节点地址*/

Position MakeNode(Item id, Item data)

{

PNode p = NULL; 

p = (PNode)malloc(sizeof(Node));

if(p!=NULL)

{

p-id =id;

p-data = data;

p-previous = NULL;

p-next = NULL;

}

return p;

}

/*释放p所指的节点*/

void FreeNode(PNode p)

{

free(p);

}

/*构造一个空的双向链表*/

DList * InitList()

{

DList *plist = (DList *)malloc(sizeof(DList));

PNode head = MakeNode(0, 0); 

if(plist!=NULL)

{

if(head!=NULL)

{

plist-head = head;

plist-tail = head;

plist-size = 0;

}

else

return NULL;

}

return plist;

}

/*摧毁一个双向链表*/

void DestroyList(DList *plist)

{

ClearList(plist);

free(GetHead(plist));

free(plist);

}

/*判断链表是否为空表*/

int IsEmpty(DList *plist)

{

if(GetSize(plist)==0GetTail(plist)==GetHead(plist))

return 1;

else

return 0;

}

/*将一个链表置为空表，释放原链表节点空间*/

void ClearList(DList *plist)

{

PNode temp,p;

p = GetTail(plist);

while(!IsEmpty(plist))

{

temp = GetPrevious(p);

FreeNode(p);

p = temp;

plist-tail = temp;

plist-size--;

}

}

/*返回头节点地址*/

Position GetHead(DList *plist)

{

return plist-head;

}

/*返回尾节点地址*/

Position GetTail(DList *plist)

{

return plist-tail;

}

/*返回链表大小*/

int GetSize(DList *plist)

{

return plist-size;

}

/*返回p的直接后继位置*/

Position GetNext(Position p)

{

return p-next;

}

/*返回p的直接前驱位置*/

Position GetPrevious(Position p)

{

return p-previous;

}

/*将pnode所指节点插入第一个节点之前*/

PNode InsFirst(DList *plist,PNode pnode)

{

Position head = GetHead(plist);

if(IsEmpty(plist))

plist-tail = pnode;

plist-size++;

pnode-next = head-next;

pnode-previous = head;

if(head-next!=NULL)

head-next-previous = pnode;

head-next = pnode;

return pnode; 

}

/*将链表第一个节点删除,返回该节点的地址*/

PNode DelFirst(DList *plist)

{

Position head = GetHead(plist);

Position p=head-next;

if(p!=NULL)

{

if(p==GetTail(plist))

plist-tail = p-previous;

head-next = p-next;

head-next-previous = head;

plist-size--;

}

return p;

}

/*获得节点的数据项*/

Item GetItem(Position p)

{

return p-data;

}

/*设置节点的数据项*/

void SetItem(Position p,Item i)

{

p-data = i;

}

/*删除链表中的尾节点并返回地址，改变链表的尾指针指向新的尾节点*/

PNode Remove(DList *plist)

{

Position p=NULL;

if(IsEmpty(plist))

return NULL;

else

{

p = GetTail(plist);

p-previous-next = p-next;

plist-tail = p-previous;

plist-size--;

return p;

}

}

/*在链表中p位置之前插入新节点s*/

PNode InsBefore(DList *plist,Position p,PNode s)

{

s-previous = p-previous;

s-next = p;

p-previous-next = s;

p-previous = s;

plist-size++;

return s;

}

/*在链表中p位置之后插入新节点s*/

PNode InsAfter(DList *plist,Position p,PNode s)

{

s-next = p-next;

s-previous = p;

if(p-next != NULL)

p-next-previous = s;

p-next = s;

if(p = GetTail(plist))

plist-tail = s;

plist-size++;

return s;

}

/*返回在链表中第i个节点的位置*/

PNode LocatePos(DList *plist,int i)

{

int cnt = 0;

Position p = GetHead(plist);

if(iGetSize(plist)||i1)

return NULL;

while(++cnt=i)

{

p=p-next;

}

return p;

}

/*依次对链表中每个元素调用函数visit()*/  

void ListTraverse(DList *plist,void (*visit)(Node))  

{  

Position p = GetHead(plist);  

if(IsEmpty(plist))  

exit(0);  

else  

{  

while(p-next!=NULL)  

{  

p = p-next;  

visit(*p);            

}         

}  

}  

void SortDLnk(DList * plist, enumSortType sortType)

{

switch(sortType)

{

case ID:

SortDLnkbyID(plist);

break;

case DATA:

SortDLnkbyData(plist);

break;

}

}

void SortDLnkbyID(DList * plist)

{

PNode head = plist-head;

Node tmpnode;

Position currnode = head;

Position bianlinode;

while ((currnode=currnode-next) != NULL)

{

bianlinode =currnode;

while((bianlinode=bianlinode-next) != NULL)

{

if (currnode-id  bianlinode-id)

{

swapnode(currnode, bianlinode);

}

}

}

}

void SortDLnkbyData(DList * plist)

{

PNode head = plist-head;

Node tmpnode;

Position currnode = head;

Position bianlinode;

while ((currnode=currnode-next) != NULL)

{

bianlinode =currnode;

while((bianlinode=bianlinode-next) != NULL)

{

if (currnode-data  bianlinode-data)

{

swapnode(currnode, bianlinode);

}

}

}

}

void swapnode(PNode anode, PNode bnode)

{// 这里面要特别注意防止前驱节点是头结点和后驱节点是Null的情况

Node tmpnode;

tmpnode.id = anode-id;

tmpnode.data = anode-data;

anode-id = bnode-id;

anode-data = bnode-data;

bnode-id = tmpnode.id;

bnode-data = tmpnode.data;

}

/************************************************************************/

/*

文件名 program.cpp

作用 对双向链表的操作函数进行测试

*/

/************************************************************************/

#include"doublelnk.h"

#includestdio.h

void print(Node node)

{

printf("数据项: id=%d, data=%d \n",node.id, node.data);

}

int main()

{

DList *plist = NULL;

PNode p = NULL;

plist = InitList();

p = InsFirst(plist,MakeNode(12, 23));

InsBefore(plist,p,MakeNode(2, 54));

InsAfter(plist,p,MakeNode(3, 34));

printf("p前驱位置的值为%d\n",GetItem(GetPrevious(p)));

printf("p位置的值为%d\n",GetItem(p));

printf("p后继位置的值为%d\n",GetItem(GetNext(p)));

printf("遍历输出各节点数据项:\n");

ListTraverse(plist,print);

printf("按照ID排序后遍历输出:\n");

SortDLnk(plist, ID);

ListTraverse(plist,print);

printf("按照Data排序后遍历输出:\n");

SortDLnk(plist, DATA);

ListTraverse(plist,print);

printf("除了头节点该链表共有%d个节点\n",GetSize(plist));

FreeNode(DelFirst(plist));

printf("删除第一个节点后重新遍历输出为:\n");

ListTraverse(plist,print);

printf("除了头节点该链表共有%d个节点\n",GetSize(plist));

DestroyList(plist);

printf("链表已被销毁\n");

return 0;

}

程序总共分三部分， 分别是双向链表的头文件、源文件和测试程序

建立工程后，分别建立相应的文件并添加相应代码应该就可以

下面的图片是我的运行效果（声明：程序中很多代码参考了以为前辈的代码）

Q4: C语言双向链表排序

既然是选择排序，在交换最小节点与当前节点，也就是调用 reverse() 之后，当前节点应该后移一个，所以将 p = i 去掉即可，因为外层 for 循环已经有 p = p-pnext