//题目：1. 在链接存储结构下，完成以下线性表的操作：
//(1) 通过重复调用线性表插入函数(第二章课件p65)，写出创建线性链表的函数create_link()。
//(2) 调用create_link()创建线性链表并输出线性表的内容。
//【输入：线性表A=(a, b, c, d, e)，输入'0'时结束】
//(3) 把(1)所创建的线性链表改为循环链表并在任位置i开始输出链表。
//【如设位置i为3，则输出为：c, d, e, a, b】
//(4) 修改链表指针，把线性表顺序颠倒并输出。
//【输入：线性表A=(a, b, c, d, e)，则：输出为(e, d, c, b, a)
#include<stdlib.h>
#include<stdio.h>
//定义结构体类型
typedef struct node
#define N 100
{char data;
struct node*link;
}NODE;
//先回顾一下不用线性表插入函数的链表创建函数是怎样的
/^DE *create_link_list(int n)
//{int i;
/^DE *head,*p,q;
//if(n<=0)return(NULL);
//head=(NODE*)malloc(sizeof(NODE));
//p=head;
//for(i=1;i<n;i++)
//{scanf("%c",&(p->data));
//q=(NODE)malloc(sizeof(NODE));
//p->link=q;
//p=q;
//}
//scanf("%c",&(p->data));
//p->link=NULL;
//return(head);
//}
//链表插入函数：在由头指针(*head)所确定线性链表中，把值为x的元素插在第i(0≤i≤链表结点数)个位置上。
int link_ins(head,i,x)
NODE **head;//head存放头指针地址
int i,x;//i为插入位置，x为插入元素的值
{int j;
NODE *p,q;
if(q=(NODE)malloc(sizeof(NODE))==0)exit(0);
q->data=x;//创建要插入的新节点
if(i==1)//插入在第一个节点前
{q->link=*head;//这两行不能对调
*head=q;
return(0);
}
p=*head;j=1;
while(++j<i&&p->link!=NULL)//寻找插入的位置
p=p->link;//即第i-1个结点的地址
if(i<1||j<i)return(1);//i在不可以插入的位置上
else// 插入在任意一个结点上
{q->link=p->link;
p->link=q;
return(0);
}
}
//1-（1）写一个函数create_link()，多次调用link_ins()函数来创建线性链表
//注意到后面的小题中有要求输入0时程序要结束，所以我们编写程序的时候也要考察这个点
NODE create_link()//创建线性链表的函数返回的是结构体指针，所以采用NODE定义
{int w;
NODE head;
char x;//题目要求我们输入的量是字符型的
head=(NODE)malloc(sizeof(NODE));// 申请空间，定义头指针
printf("请输入第一个元素的值");
scanf("%c",&x);
getchar();
if(x=='0')return(NULL);//如果第一个元素出现0，返回空指针。
for(w=2; ;w++)//这里我们直接构建一个无限循环，直到输入0为止
{printf("请输入第%d个元素的值",&w);
scanf("%c",&x);
getchar();
if(x=='0')break;//循环里也要注意非0
link_ins(&head,w,x);//运用线性表插入函数，不断把生成的结点插入到链表的末尾，这里不用单独写NULL的程序，
//因为线性表插入函数中已经包含了插入点在线性表末尾的情况，会自动补上NULL
}
return(head);
}
//1-（2）调用create_link()并输出线性表的内容，该函数的参数为：目标链表头指针head
//我们定义函数print_link()，参数为:链表头指针名*head
void print_link(NODE *head)//在主程序中，我们输入一个线性链表的头指针
{NODE *p;
int i;
p=head;
for(i=1;;i++)
{
printf("%c",&p->data);
printf("->");
p=p->link;
while(p==NULL)break;}//用一个循环程序写出链表每一项的元素
}
//1-（3）把1-（1）中链表改写为循环链表，并在第i位输出链表
//先写一个程序change_link()把线性链表改写为循环链表；然后再写一个程序print2_link()，从第i位输出链表。
NODE *change_link(NODE *head)//在主程序中，我们输入一个线性链表的头指针
{NODE *p;
int i;
for(i=1;;i++)
{p=p->link;
while(p==NULL)break;
}
p=head;
return(head);
}
//接下来我们写一个输出链表的函数
void print2_link(NODE *head,int i)//在主程序中，我们输入一个循环链表的头指针和输出位置
{NODE *p,*q;
int m,n;
p=head;
for(m=1;m<i;m++)
p=p->link;//让活动指针p指向第i个结点
q=p;//把p的当前地址赋值给q
for(n=1;;n++)//写一个无限循环语句，从第i个结点开始输出data
{printf("%c",p->data);
printf("->");
p=p->link;
while(p==q)break;//当p回到第i个结点（用q标记）时，不再输出data
}
}
//1-（4）先颠倒线性表，再输出线性表的元素
void upside_link(NODE *head)//在主程序中，我们输入一个线性链表的头指针
{NODE *p,q;
int m,n;
int a[N];
p=head;//先计算线性链表的长度
for(m=1;;m++)
{p=p->link;
while(p==NULL)break;
}
//现在我们知道了线性链表的长度m,同时把指针p移动到链表末尾
//我们定义一个数组来存放这些链表的元素，再反向赋值给线性链表
for(n=0;n<m;n++)
{a[n]=p->data;
p=p->link;
}
q=head;
for(n=1;n<=m;n++)
{q->data=a[m-n];
q=q->link;
printf("%c",&q->data);//再打印这个已经反向的链表
}
}
//现在我们已经写完了四个函数，下面定义主函数：
main()
{NODE head, *head1;
int i;
printf("请输入i的值");
scanf("%d",&i);
head=create_link();//（1）创建一个线性表
print_link(head);//（2）输出线性表内容
head1=change_link(head);//（3）创建循环链表head1
print2_link(head1,i);//（3）在第i位输出循环链表
upside_link(head);//（4）颠倒线性表并输出线性表元素
}