#include<stdio.h>
#include<iostream>
#define ERROR 0
#define OK 1
typedef int ElemType;
typedef struct Node //结构类型定义
{
ElemType data;
struct Node * next;
}Node, *Linklist; /*Linklist为结构指针类型*/
void InitList(Linklist *L) /*初始化单链表*/
{
*L = (Linklist)malloc(sizeof(Node)); /*建立头结点*/
(*L)->next = NULL; /*建立空的单链表L*/
}
void CreateFromHead(Linklist L) /*用头插法建立单链表*/
{
Node *s;
char c;
int flag = 1;
while (flag) /*flag初值为1，当输入“#”时，置flag为0，建立表结束*/
{
c = getchar();
if (c != '#')
{
s = (Node*)malloc(sizeof(Node)); /*建立新结点s*/
s->data = c;
s->next = L->next; /*将s结点插入表头*/
L->next = s;
}
else flag = 0;
}
}
int changgelist(Linklist L)
{
Node *p1, *pre, *p, *q;
if (L->next == NULL)
return ERROR;
p1 = L->next; /*p1指向表中第一元素*/
pre = p1;
p = p1->next;
/*顺次从p开始取结点，比p1->data小的插在头结点之后，比p1->data大的结点不作处理，继续检测其后续结点*/
while (p)
{
q = p->next;
if (p->data >= p1->data)
{
pre = p;
p = q;
}
else
{
pre->next = p->next;
p->next = L->next;
L->next = p;
p = q;
}
}
return OK;
}
void main()
{
Linklist l;
Node *p;
InitList(&l);
printf("建立单链表,请输入链表数据,以#结束!\n");
CreateFromHead(l);
p = l->next;
printf("建立的单链表为:\n");
while (p != NULL)
{
printf("%c ", p->data);
p = p->next;
}
changgelist(l);
p = l->next;
printf("\n改变后的单链表为:\n");
//printf("%c", p->data);
p = l->next;
while (p != NULL)
{
printf("%c ", p->data);
p = p->next;
}
}
