# include <stdio.h>
# include <malloc.h>

typedef struct Node{
	int data;
	struct Node * next;
} Node ,* PNODE;

PNODE create_list();
void show_list(PNODE);
int size_list(PNODE);
void sort_list(PNODE);
bool insert_list(PNODE,int,int);
int delete_list(PNODE,int,int *);
int main(void){
	PNODE pHead = create_list();
	show_list(pHead);
	int size = size_list(pHead);
	printf("\n");
	printf("链表对应的长度是：%d\n",size);
	// 然后来进行排序
	sort_list(pHead);
	show_list(pHead); 
	printf("\n");
	insert_list( pHead,5,555);
	show_list(pHead); 
	printf("------------------\n");
	int i=-1;
	delete_list(pHead,3,&i);
	show_list(pHead); 
	printf("对应的值是：%d\n",i);
	return 0;
}

PNODE create_list(){
	PNODE pHead = (PNODE)malloc(sizeof(Node));
	PNODE tmp = pHead;
	printf("请输入链表的长度的：\n");
	int len;
	scanf("%d",&len);
	int i,val;
	for(i=0;i<len;i++){
		printf("请输入第%d个元素的值：\n",i+1);
		scanf("%d",&val);
		PNODE pNew = (PNODE)malloc(sizeof(Node));
		pNew->data=val;
		pNew->next=NULL;
		tmp->next=pNew;
		tmp=pNew;
	}
	return pHead;
}

void show_list(PNODE pHead){
	PNODE p = pHead->next;
	while(NULL!=p){
		printf("%d  ",p->data);
		p = p->next;
	}
}

int size_list(PNODE pHead){
	int i = 0;
	PNODE p = pHead->next;
	while(NULL!=p){
		i++;
		p = p->next;
	}
	return i;
}

void sort_list(PNODE pHead){
	int i,j,k;
	int size = size_list(pHead);
	PNODE p,q;
	for(i=0,p=pHead->next;i<size-1;i++,p=p->next){
		for(j=i+1,q=p->next;j<size;j++,q=q->next){
			if(p->data>=q->data){
				k=	p->data;
				p->data=q->data;
				q->data=k;
			}
		}
	}
}

bool insert_list(PNODE pHead,int pos,int val){
	PNODE p = pHead;
	int i = 0;
	while(NULL!=p&&i<pos-1){
		p=p->next;
		i++;
	}
	if(i>pos-1||p==NULL){
		return false;
	}
	PNODE t = (PNODE)malloc(sizeof(Node));
	t->data=val;
	t->next=p->next;
	p->next=t;
	return true;
}


int  delete_list(PNODE pHead,int pos,int * val){
	PNODE p = pHead;
	int i = 0;
	while(NULL!=p&&i<pos-1){
		p=p->next;
		i++;
	}
	if(i>pos-1||p==NULL){
		return false;
	}
	PNODE tmp = p->next;
	*val = tmp->data;
	p->next = tmp->next;
	free(tmp);
	return *val;
}