双向链表排序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("
");
}
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;
}
#include
#include
#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("请输入插入元素数量:
");
scanf("%d",&n);
count=n;
printf("请输入%d个自然数
",n);
while(i<n)
{
scanf("%d",&temp);
s=(DulNode*)malloc(sizeof(DulNode));
s->data=temp;
while((p!=(*L))&&(p->data<temp))//查找所要插入的位置
{
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("双向链表中的数据为:
");
while(p!=L)
{
printf("%d ",p->data);
p=p->next;
}
printf("
");
}
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);//第二题输出结果
}
/************************************************************************/
/*
文件名 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
",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
",GetItem(GetPrevious(p)));
printf("p位置的值为%d
",GetItem(p));
printf("p后继位置的值为%d
",GetItem(GetNext(p)));
printf("遍历输出各节点数据项:
");
ListTraverse(plist,print);
printf("按照ID排序后遍历输出:
");
SortDLnk(plist, ID);
ListTraverse(plist,print);
printf("按照Data排序后遍历输出:
");
SortDLnk(plist, DATA);
ListTraverse(plist,print);
printf("除了头节点该链表共有%d个节点
",GetSize(plist));
FreeNode(DelFirst(plist));
printf("删除第一个节点后重新遍历输出为:
");
ListTraverse(plist,print);
printf("除了头节点该链表共有%d个节点
",GetSize(plist));
DestroyList(plist);
printf("链表已被销毁
");
return 0;
}
程序总共分三部分, 分别是双向链表的头文件、源文件和测试程序
建立工程后,分别建立相应的文件并添加相应代码应该就可以
下面的图片是我的运行效果(声明:程序中很多代码参考了以为前辈的代码http://blog.csdn.net/hopeyouknow/article/details/6716177)
/*
请输入链表结点数 : 5
序号 : 60357
数据 : 8693
序号 : 63415
数据 : 3487
序号 : 38419
数据 : 2685
序号 : 65478
数据 : 6303
序号 : 87657
数据 : 3628
60357 : 8693
63415 : 3487
38419 : 2685
65478 : 6303
87657 : 3628
87657 : 3628
65478 : 6303
38419 : 2685
63415 : 3487
60357 : 8693
排序后 :
87657 : 3628
65478 : 6303
63415 : 3487
60357 : 8693
38419 : 2685
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("申请动态内存失败。
");
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
",p->sn,p->data);
p = p->next;
}
printf("
");
}
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
",p->sn,p->data);
p = p->prior;
}
printf("
");
}
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("排序后 :
");
Print(head);
DCprint(head);
Deleteheap(head);
return 0;
}
C语言
程序,
严格
双向链表排序c语言程序设计
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...
如何将链表中的数据按升序排列?(用c语言编写)不用数组,形参是该链表...
include <stdio.h>#include <stdlib.h>struct node{ int data; struct node * next;};typedef struct node NODE;typedef struct node * PNODE;void outlist( PNODE );void sortlist( PNODE h, int num );int main ( ){ int num=1; PNODE head; head = (PNODE)malloc...
C语言如何对链表的数进行排序?
L=Creat();printf("初始化的单链表数据序列为:\\n");for(S=L;S!=NULL;S=S->next)printf("%d ",S->data);Sort(L);printf("\\n按递增顺序排序后的序列为:\\n");for(K=L;K!=NULL;K=K->next)printf("%d==>",K->data);return 0;} ...
用C语言写一个有序链表,链表类型为字符串.
p->next = NULL;\/\/ 输出随机数链表 for (p = head; p != NULL; p = p->next)printf("%d ", p->data);printf("\\n");\/\/ 对链表排序 BubbleSort(head);\/\/ 输出以排序的链表 for (p = head; p != NULL; p = p->next)printf("%d ", p->data);printf("\\n");\/\/ 释放...
关于C语言链表排序的问题
(n == 1)head = p1;elsep2->next = p1;p2 = p1;p1 = (struct number*)malloc(sizeof(struct number));scanf("%d", &p1->num);} p2->next = NULL;return (head);} void print(struct number *head) \/\/链表从小到大排序,并输出{struct number *p1, *p2, *p;int i, j,...
c语言链表排序问题,程序如下。t->next = p->next;p->next = q->next...
q->next = t->next; \/\/将t的下一个节点交给q的下一个节点。\/\/这是交换p和q的下一个节点,修改next值。\/\/结构体可以直接赋值的,也就是第一个三行交换,不仅交换了数值StudentID,应该也同时交换了next指针,所以后面三行其实是还原next指针的,否则上面的for循环,就换乱了。简单的做法,应该...
求一个C语言单链表的排序函数,很急很急
用选择排序就行,代码如下。链表结构如下:typedef struct Node { T value;struct Node *link;}Node;void selectSort(Node *node){ Node *cur; \/*当前节点*\/ Node *next; \/*遍历未排序节点*\/ Node *min; \/*指向未排序节点中最小节点*\/ T temp;\/*从头节点的下一个节点开始,一直到倒数第二...
求高手做个c语言设计一个双向链表的排序
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 ...
在数据结构中用c语言怎么编写用单链表将26个字母排序的程序?
typedef struct node { char num;struct node *next;}list;void Bubble_sort(list *L);\/\/链表的冒泡排序 void Dis_list(list *L);\/\/遍历单链表 int main(){ \/\/建表 list *r,*s,*p;int n=26;\/\/存储数据的个数 s=NULL;for(int i='Z';i>='A';i--){ r=(list *)malloc(size...
C语言,链表怎么从大到小排序
{temp=tp->next->value;tp->next->value=tp->value;tp->value=temp;} } } 以上是冒泡法对链表排序的例子;\/\/输出答案的函数 void answer(data *p){ while(p!=NULL) { cout<value<<endl;p=p->next;} } 以上是遍历链表的函数p是链表的头指针 ...
当涂龙复方: #include <malloc.h> #include <stdio.h> 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("请输入...
铁东区18856648803: 求高手做个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,...
铁东区18856648803: C语言双向链表排序 - ?
当涂龙复方: 删除节点就是把某个节点从链表中取出,释放掉内存,把它前后节点再相连; 序号就是节点的位置,比如头结点就是1,头结点的下一个节点就是2以此类推; 数值就是随便一个数,比如每个节点都有一个int类型的变量,按这个变量的值从小到大或从大到小排序;
铁东区18856648803: C语言双向链的排序 - ?
当涂龙复方: 链表结构定义 typedef struct node { char data[19+1]; struct node *llink; struct node *rlink;/*上一个,下一个*/ }; /*创建链表*/ int creat_list(struct node *h) { /* if((h=(struct node *)malloc(sizeof(struct node)))==NULL) { printf("不能分配内存空间!");...
铁东区18856648803: C语言 双向链表 快速排序?
当涂龙复方: 我说一下想法你看行不行 直接在链表中排序太麻烦,不如把关键字和指针单独抽取出来放到一个结构体数组中 然后对这个数组进行排序,排好后按相应指针顺序输出链表元素即可 在输入规模不大的情况下增加了一些空间代价,但是却可使代码简化不少,应该是可行的. 当然直接交换双向链表中的两个元素也非难事.
铁东区18856648803: 求c语言双向循环链表的一个应用例子?
当涂龙复方: 排序做例子. 比如.有10个数.从大到小排序成有序数组a[0]~a[9] 这时如果加入第11个数时要要保序新的数组有序,假设这个值要插在第a[n] n<9; 那就意味 着插入前要把a[n]-a[9]的位置向后移一位,在插入a[n] 这样.要操作的指令就多了. ...
铁东区18856648803: 用c++语言实现双向链表的排序 - ?
当涂龙复方: #include #include struct _Node { int data; struct _Node *next;};typedef struct _Node Node;// 交换两个结点的数据void SwapNodeData(Node *p1, Node *p2) { int temp = p1->data; p1->data = p2->data; p2->data= temp;}// 冒泡排序对链表进行排序...
铁东区18856648803: C语言链表如何排序?
当涂龙复方: 可以把链表设计成循环链表,用冒泡排序 在排序前设计一个交换标记,如在循环过程中有交换,则修改这个标记变量,如果在一次循环(当前节点为刚开始时节点,表示循环了一次)中,交换标记没有被修改,则表明该数列已排好序. 现在给...
铁东区18856648803: C语言、双向链表 - ?
当涂龙复方: #include <stdio.h> #include <string.h> struct person { char name[10]; int number; person *next; person *last; }; person *p,*q,*start=NULL,*end; void insert(int num,char nam[10])//插入函数,按姓名的首字母顺序插入链表中的. { q=new person; if (start...
铁东区18856648803: 使用C语言实现双向链表的建立、删除和插入 - ?
当涂龙复方: #include #include struct list{int data;struct list *next;struct list *pre; }; typedef struct list node; typedef node *link; link front=NULL,rear,ptr,head=NULL; link push(int item){link newnode=(link)malloc(sizeof(node));newnode->data=item;if(head==...