#include<stdio.h>
#include<stdlib.h>
struct link *appendnode(struct link *head);
void displaynode(struct link *head);
void deletememory(struct link *head);
struct link
{	
	int data;
	struct link *next;
};
int main()
{	int i=0;
	char c;
	struct link *head=NULL;/*链表头指针*/
	printf("DO you want to append a new node(Y/N)?");
	scanf(" %c",&c);
	while(c=='Y'||c=='y')
	{
		head=appendnode(head);/*向head为头指针的链表末尾添加节点*/
		displaynode(head);
		printf("DO you want to append a new node(Y/N)?");
		scanf(" %c",&c);
		i++;
	} 
	printf("%d new nodes have been append\n",i);
	deletememory(head);/*释放所有动态分配的内存*/
}
/*函数功能：新建一个节点并添加到链表末尾，返回添加节点后的链表的头指针*/
struct link *appendnode(struct link *head)
{
		struct link *p=NULL,*pr=head;
		int data;
		p=(struct link *)malloc(sizeof(struct link));/*让p指向新建节点*/
		if(p==NULL)/*若为新建节点申请内存失败，则退出程序*/
		{
			printf("no enough memory to allocate\n");
			exit(0);
		} 
		if(head==NULL)/*若原链表为空*/
		{
			head=p;/*将新建节点置为头节点*/
		}
		else /*若原列表为非空，则将新建节点添加到表尾*/
		{
			while(pr->next!=NULL)/*若未到表尾，则移动pr直到pr指向表尾*/
			{
				pr=pr->next;/*让pr指向下一个节点*/
			}
			pr->next=p;/*让末节点的指针域指向新建节点*/
		}
		printf("输入节点数据");
		scanf("%d",&data);//输入节点数据
		p->data=data;/*将新建节点的数据域赋值为输入节点的数据值*/
		p->next=NULL;/*将新建节点置为表尾*/
		return head;/*返回添加节点后的链表的头指针*/	
} 
/*函数功能：显示链表中所有节点的节点号和该节点的数据项的内容*/
void displaynode(struct link *head)
{
	struct link *p=head;
	int j=1;
	while(p!=NULL)/*若不是表尾，则循环打印节点的值*/
	{
		printf("%5d%10d\n",j,p->data);/*打印第j个节点的数据*/
		p=p->next;/*让p指向下一个节点*/
		j++;
	}
}
/*函数功能：释放head指向的链表中所有节点占用的内存*/
void deletememory(struct link *head)
{
	struct link *p=head,*pr=NULL;
	while(p!=NULL)/*若不是表尾，则释放节点占用的内存*/
	{
		pr=p;/*让pr中保存当前节点的指针*/
		p=p->next;/*让p指向下一个节点*/
		free(pr);/*释放pr指向的当前节点占用的内存*/
	}
}

/*函数功能：从head指向的链表中删除一个节点，返回删除节点后的链表的头指针*/
struct link *deletenode(struct link *head,int nodedata)
{
	struct link *p=head,*pr=head;
	if(head==NULL)/*若链表为空表，则退出程序*/
	{
		printf("link table is empty!\n");
		return(head);
	} 
	while(nodedata!=p->data && p->next!=NULL)/*未找到且未到表尾*/
	
	{
		pr=p;/*在pr中保存当前节点的指针*/
		p=p->next;/*p指向当前节点的下一个节点*/
	}	
	if(nodedata==p->data) /*若当前节点的节点值为nodedata,找到待删除的节点*/
	{
		if(p==head)/*若待删除的节点为头节点*/
		{
			head=p->next;/*则让头指针指向待删除节点p的下一节点*/
		}
		else/*若待删节点不是头节点*/
		{
			pr->next=p->next;/*让前一节点的指针域指向待删节点的下一节点*/
		} 
		free(p);/*释放已删除节点分配的内存*/ 
    }
	else /*找到表尾仍未发现节点值为nodedata的节点*/
	{
		printf("this node has not been found!\n");
	} 
	return head;/*返回删除节点后的链表指针head的值*/ 
} 
/*向节点值已按升序排序的链表中插入一个新的节点的程序如下*/
struct link *insertnode(struct link *head,int nodedata) 
{
	struct link *pr=head,*p=head,*temp=NULL;
	p=(struct link *)malloc(sizeof(struct link));/*让p指向待插入的节点*/
	if(p==NULL)/*若为新建节点申请内存失败，则退出程序*/
	{
		printf("no enough memory!\n");
		exit(0);
	} 
	p->next=NULL;/*为待插入节点的指针域赋值为空指针*/
	p->data=nodedata;/*为待插入节点的数据域赋值为nodedata*/
	if(head==NULL)/*若原列表为空表*/
	{
		head=p;/*待插入节点作为头节点*/
	}
	else /*若原列表为非空*/
	{/*若未找到待插入节点的位置且未到表尾，则继续找*/
		while(pr->data < nodedata && pr->next !=NULL)
		{
			temp=pr;/*让temp中保存当前节点的指针*/
			pr=pr->next;/*pr指向当前节点的下一节点*/
		}
		if(pr->data >= nodedata) 
		{
			if(pr==head)/*若在当前节点插入新节点*/
			{
				p->next-head;/*将新节点的指针域指向原列表的头节点*/ 
				head=p;/*让head指向新节点*/ 
			} 
			else /*若在链表中间插入新节点*/ 
			{
				pr=temp;
				p->next=pr->next;
				pr->next=p;
			} 
		}
		else /*若在表尾插入新节点*/
		{
			pr->next=p;/*让末节点的指针域指向新节点*/
		}
	} 
	return head;/*返回插入新节点后的链表头指针head的值*/ 
}