chain.c

已知一个双向链表

/*已知一个双向链表，从第二个元素开始已经呈递增有序，随意
  输入几个数字，把第一个数字插进去，条件的是呈递增有序*/

#include <stdio.h> 
#include <conio.h> 
#define len sizeof( node ) 

typedef struct Node 
{float k; 
 struct Node *head; 
 struct Node *next; 
}node; 

node *creatlist() /* Head 变量不是头结点,是用来标记第一个结点的位置 */ 
{float data; 
 node *p,*q,*Head; 
 char c; 
 printf("input the first number at discretion,and then input other which is increased:\n"); 
 scanf("%f,%c",&data,&c); 
 p=(node*)malloc(len); 
 Head=p; 
 p->k=data; 
 while( c!='\n' ) 
 { 
  scanf("%f%c",&data,&c); /* 输入数据 */ 
  q=(node*)malloc( len ); 
  q->k=data; 
/*构建双向链表*/ 
  p->next=q;  
  q->head=p; 
  q->next=NULL; 
  p=q; 
 } 
return Head; 
} 

node *treat( node *Head ) /* 插入时分三种情况,在前面,中间,最后*/ 
{ 
 node *p,*q; 
 float temp; /* 用于储存中间变量,用来转换 */ 
 if( (Head->next)->k >= Head->k ) return Head; /* 如果整串数字本身已经有序了,就不用排序了 */ 
 p=Head;  
 q=Head;       /* 独立为一个变量 */ 
 p=Head->next;    /* 此处删除了第一个节点.将第一个节点独立为变量q.Head指向了第二个节点 */ 
 Head=p; 
 while( !(q->k >= p->k&& q->k < (p->next)->k)&& p->next!=NULL ) /* 当元素大于前一个而小于后一个,就在这个位置插入q */ 
 p=p->next;   /* 如果条件是真,加上!后变假了,就可以跳出循环. */ 
 if( p->next==NULL ) /* 如果第一个是最大的,那么上式会一直找到最后,此时只要将其连在最后面就可以了 */ 
 { 
  p->next=q; 
  q->next=NULL; 
  q->head=p; 
 } 
 else 
 { 
  q->next=p->next; 
  (p->next)->head=q; 
  q->head=p; 
  p->next=q; 
 } 
 return Head; 
} 

main() 
{ 
 node *p,*q,*Head; 
 Head=creatlist(); 
 Head=treat( Head ); 
 p=Head; 
 while( p!=NULL )/* 输出数据 */ 
 { 
  printf("%f ",p->k); 
  p=p->next; 
 } 
getch(); 
}