Question

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

1、给定自然数n，与一组实数序列a1，a2，a3，…，a n-1，an。
用C写算法，采用双向链表使所给实数序列递增排列。

2、给定自然数n，与一组实数序列a1，a2，a3，…，a n-1，an。
用C写算法，使其功能为：使原实数序列中，其位于奇数位置各实数按照递增排列，且仍位于有序化后的新实数序列中的奇数位置；而原实数序列中，其位于偶数位置各实数按照递减排列，且仍位于有序化后的新实数序列中的偶数位置。
=============
数据结构初学，希望得到你的帮助，能把注释写全些，一定加分。
如果有条件的话，请测试下～3Q
分不多，谢意浓～

Answer 1

#include<stdio.h>
#include<malloc.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(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("双向链表中的数据为:\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);//第二题输出结果
}

Answer 2

#include
<stdio.h>
#include
<stdlib.h>
typedef
struct
node{
float
data;
struct
node
*pre;
struct
node
*next;
}*DoubleNode;
void
sort_DoubleNode(DoubleNode
&head,
float
data)
{
DoubleNode
node
=
(DoubleNode)malloc(sizeof(struct
node));
DoubleNode
p,q;
node->data
=
data;
if(head
==
NULL)
{
head
=
node;
head->next
=
NULL;
head->pre
=
NULL;
return;
}
p
=
head;
while(p
!=
NULL
&&
p->data
<
data)
{
q
=
p;
p
=
p->next;
}
if(p
==
head)
{
node->next
=
head;
node->pre
=
NULL;
head
->pre
=
node;
head
=
node;
}
else{
q->next
=
node;
node->pre
=
q;
node->next
=
p;
if(p
!=
NULL)
p->pre
=
node;
}
}
void
out_DoubleNode(DoubleNode
&head)
{
DoubleNode
p
=
head;
while(p
!=
NULL)
{
printf("%.4f
",
p->data);
p
=
p->next;
}
printf("\n");
}
void
main()
{
int
n;
float
data;
DoubleNode
head
=
NULL;
scanf("%d",
&n);
for(int
i=0;
i<n;
++i)
{
scanf("%f",
&data);
sort_DoubleNode(head,
data);
}
out_DoubleNode(head);
}
/*
15
23.4
4.5
56
67
7.5
90
8.97
90.6
25.6
145
856
10.2
0.36
54.6
56.1
*/
第二题：
测试数据同第一题
#include
<stdio.h>
#include
<stdlib.h>
typedef
struct
node{
float
data;
struct
node
*pre;
struct
node
*next;
}*DoubleNode;
bool
bigger(float
a,
float
b)
{
return
(a
>
b);
}
bool
smaller(float
a,
float
b)
{
return
(a
<
b);
}
void
sort_DoubleNode(DoubleNode
&head,
float
data,
bool
(*comp)(float
a,
float
b))
{
DoubleNode
node
=
(DoubleNode)malloc(sizeof(struct
node));
DoubleNode
p,q;
node->data
=
data;
if(head
==
NULL)
{
head
=
node;
head->next
=
NULL;
head->pre
=
NULL;
return;
}
p
=
head;
while(p
!=
NULL
&&
comp(p->data,
data))
{
q
=
p;
p
=
p->next;
}
if(p
==
head)
{
node->next
=
head;
node->pre
=
NULL;
head
->pre
=
node;
head
=
node;
}
else{
q->next
=
node;
node->pre
=
q;
node->next
=
p;
if(p
!=
NULL)
p->pre
=
node;
}
}
void
merge_DoubleNode(DoubleNode
&head,
DoubleNode
&head1,
DoubleNode
&head2)
{
DoubleNode
p
=
head2;
head
=
head1;
if(head1
==
NULL
||
head2
==
NULL)
return;
while((head1->next
!=
NULL)
&&
(head2
!=
NULL))
{
p
=
head2->next;
head1->next->pre
=
head2;
head2->next
=
head1->next;
head2->pre
=
head1;
head1->next
=
head2;
head1
=
head2->next;
head2
=
p;
}
if((head1->next
==
NULL)
&&
(head2
!=
NULL))
{
head1->next
=
head2;
head2->pre
=
head1;
}
}
void
out_DoubleNode(DoubleNode
&head)
{
DoubleNode
p
=
head;
while(p
!=
NULL)
{
printf("%.4f
",
p->data);
p
=
p->next;
}
printf("\n");
}
void
main()
{
int
n;
float
data;
DoubleNode
head
=
NULL;
DoubleNode
head1
=
NULL;
DoubleNode
head2
=
NULL;
scanf("%d",
&n);
for(int
i=0;
i<n;
++i)
{
scanf("%f",
&data);
if((i+1)%2
==
0)
sort_DoubleNode(head2,
data,
&bigger);
else
sort_DoubleNode(head1,
data,
&smaller);
}
merge_DoubleNode(head,
head1,
head2);
out_DoubleNode(head);
}
/*
15
23.4
4.5
56
67
7.5
90
8.97
90.6
25.6
145
856
10.2
0.36
54.6
56.1
*/

Answer 3

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

typedef struct node{
float data;
struct node *pre;
struct node *next;
}*DoubleNode;

void sort_DoubleNode(DoubleNode &head, float data)
{
DoubleNode node = (DoubleNode)malloc(sizeof(struct node));
DoubleNode p,q;
node->data = data;
if(head == NULL)
{
head = node;
head->next = NULL;
head->pre = NULL;
return;
}

p = head;
while(p != NULL && p->data < data)
{
q = p;
p = p->next;
}
if(p == head)
{
node->next = head;
node->pre = NULL;
head ->pre = node;
head = node;
}
else{
q->next = node;
node->pre = q;
node->next = p;
if(p != NULL) p->pre = node;
}
}

void out_DoubleNode(DoubleNode &head)
{
DoubleNode p = head;
while(p != NULL)
{
printf("%.4f ", p->data);
p = p->next;
}
printf("\n");
}

void main()
{
int n;
float data;
DoubleNode head = NULL;
scanf("%d", &n);

for(int i=0; i<n; ++i)
{
scanf("%f", &data);
sort_DoubleNode(head, data);
}

out_DoubleNode(head);
}
/*
15
23.4 4.5 56 67 7.5 90 8.97 90.6 25.6 145
856 10.2 0.36 54.6 56.1
*/

第二题： 测试数据同第一题
#include <stdio.h>
#include <stdlib.h>

typedef struct node{
float data;
struct node *pre;
struct node *next;
}*DoubleNode;

bool bigger(float a, float b)
{
return (a > b);
}

bool smaller(float a, float b)
{
return (a < b);
}

void sort_DoubleNode(DoubleNode &head, float data, bool (*comp)(float a, float b))
{
DoubleNode node = (DoubleNode)malloc(sizeof(struct node));
DoubleNode p,q;
node->data = data;
if(head == NULL)
{
head = node;
head->next = NULL;
head->pre = NULL;
return;
}

p = head;
while(p != NULL && comp(p->data, data))
{
q = p;
p = p->next;
}
if(p == head)
{
node->next = head;
node->pre = NULL;
head ->pre = node;
head = node;
}
else{
q->next = node;
node->pre = q;
node->next = p;
if(p != NULL) p->pre = node;
}
}

void merge_DoubleNode(DoubleNode &head, DoubleNode &head1, DoubleNode &head2)
{
DoubleNode p = head2;
head = head1;
if(head1 == NULL || head2 == NULL) return;
while((head1->next != NULL) && (head2 != NULL))
{
p = head2->next;
head1->next->pre = head2;
head2->next = head1->next;
head2->pre = head1;
head1->next = head2;
head1 = head2->next;
head2 = p;
}
if((head1->next == NULL) && (head2 != NULL))
{
head1->next = head2;
head2->pre = head1;
}
}

void out_DoubleNode(DoubleNode &head)
{
DoubleNode p = head;
while(p != NULL)
{
printf("%.4f ", p->data);
p = p->next;
}
printf("\n");
}

void main()
{
int n;
float data;
DoubleNode head = NULL;
DoubleNode head1 = NULL;
DoubleNode head2 = NULL;
scanf("%d", &n);

for(int i=0; i<n; ++i)
{
scanf("%f", &data);
if((i+1)%2 == 0) sort_DoubleNode(head2, data, &bigger);
else sort_DoubleNode(head1, data, &smaller);
}

merge_DoubleNode(head, head1, head2);

out_DoubleNode(head);
}
/*
15
23.4 4.5 56 67 7.5 90 8.97 90.6 25.6 145
856 10.2 0.36 54.6 56.1
*/

Answer 4

实际关于这样的问题来百度问比较浪费时间
推荐一个网站csdn，在国内程序员中很火的,上面有很多牛人

http://community.csdn.net/