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

链表结点的数据域包括：序号、数值。功能：1、输入一个双向链表;2、显示此双向链表所有结点；3、对此双向链表分别按序号或数值进行排序；4、删除双向链表中的结点。... 链表结点的数据域包括：序号、数值。
功能：
1、输入一个双向链表;
2、显示此双向链表所有结点；
3、对此双向链表分别按序号或数值进行排序；
4、删除双向链表中的结点。展开

 我来答

3个回答

#热议# 应届生在签三方时要注意什么？

qimingxingwen
2013-09-10 · TA获得超过432个赞

知道小有建树答主

回答量：269

采纳率：50%

帮助的人：183万

我也去答题访问个人页

关注

展开全部

/************************************************************************/
/*
	文件名		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"
#include<malloc.h>
#include<stdlib.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)==0&&GetTail(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(i>GetSize(plist)||i<1)
		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"
#include<stdio.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;
}

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

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

下面的图片是我的运行效果（声明：程序中很多代码参考了以为前辈的代码http://blog.csdn.net/hopeyouknow/article/details/6716177）

已赞过 已踩过<

评论收起

xoaxa
2013-09-10 · TA获得超过8610个赞

知道大有可为答主

回答量：6415

采纳率：72%

帮助的人：3473万

我也去答题访问个人页

关注

展开全部

请输入链表结点数 : 5

序号 : 60357

数据 : 8693

序号 : 63415

数据 : 3487

序号 : 38419

数据 : 2685

序号 : 65478

数据 : 6303

序号 : 87657

数据 : 3628

60357 : 8693

63415 : 3487

38419 : 2685

65478 : 6303

87657 : 3628

65478 : 6303

38419 : 2685

63415 : 3487

60357 : 8693

排序后 :

87657 : 3628

65478 : 6303

63415 : 3487

60357 : 8693

38419 : 2685

60357 : 8693

63415 : 3487

65478 : 6303

87657 : 3628

请按任意键继续. . .

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
	unsigned sn;
	int data; 
	node *prior,*next; 
}*DLinkList; 

DLinkList CreateList(int n) {  // 创建双向环形链表
	DLinkList p,q,head;
	head = p = (DLinkList)malloc(sizeof(node));
	head->sn = 0;
	head->data = 0;
	for(int i = 0;i < n;i++) {
		p->next = (DLinkList)malloc(sizeof(node));
		if(p->next== NULL) {
			printf("申请动态内存失败。\n");
			break;
		}
		printf("序号 : ");
		scanf("%u",&p->next->sn);
		printf("数据 : ");
		scanf("%d",&p->next->data);
		p->next->next = head;  // 始终保持环形连接
		p->next->prior = p;    // 新结点的反向链接
		p = p->next;           // 为连接新节点做准备
	}
	head->prior = p;// 头结点的prior指向最后的结点，是实现双向环形链表的最后一步
	return head;
}

void Print(DLinkList head) {  // 顺向输出链表数据
	DLinkList p;
	p = head->next;
	while(p != head) {
		printf("%u : %d\n",p->sn,p->data);
		p = p->next;
	}
	printf("\n");
}

void SortSN(DLinkList head) { // 按序号升排序 
	DLinkList p = head,q,pt;
	q = p->next;
	while(p->next != head) {
		while(q->next != head) {
			if(q->next->sn > p->next->sn) {
				pt = p->next;
				p->next = q->next;
				q->next = q->next->next;
				q->next->prior = q;
				p->next->next = pt;
				pt->prior = p->next;
				pt->prior->prior = p;
			}
			else q = q->next;
		}
		p = p->next;
	}
}

void DCprint(DLinkList head) {  // 反向输出链表数据
	DLinkList p = head->prior;
	while(p != head) {
		printf("%u : %d\n",p->sn,p->data);
		p = p->prior;
	}
	printf("\n");
}

void Deleteheap(DLinkList head) {  // 释放占用的堆空间
	DLinkList p,q;
	p = head;
	q = p->next;
	while(q != head) {
		p = q;
		q = p->next;
		free(p);
	}
	free(head);
}

int main () {
	DLinkList head; 
	int n;
	printf("请输入链表结点数 : ");
	scanf("%d",&n);
	head = CreateList(n);
	Print(head);
	DCprint(head);
	SortSN(head);
	printf("排序后 :\n"); 
	Print(head);
	DCprint(head);
	Deleteheap(head);
	return 0;
}

更多追问追答

追问

这个有错诶。。。

追答

有什么样的错误呢？请具体点。
建议仔细观察代码上面数据的输入过程。

本回答被网友采纳

已赞过 已踩过<

评论收起

QQ啊438129436
2013-09-09

知道答主

回答量：36

采纳率：0%

帮助的人：7.6万

我也去答题访问个人页

关注

展开全部

C语言

程序，

严格

已赞过 已踩过<

评论收起

更多回答（1）

推荐律师服务：若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询

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

其他类似问题

为你推荐：