#include<stdio.h>

#include<stdlib.h>

#include"LinkList.h"

//创建单链表

void CreateList(LinkList L,DataType a[],int n){

	int i;

	for(i=1;i<=n;i++)

		InsertList(L,i,a[i-1]);

}

//用链表实现选择排序。

将链表分为两段，p指向应经排序的链表部分。q指向未排序的链表部分

void SelectSort(LinkList L){

	ListNode *p,*q,*t,*s;

	p=L;

	while(p->next->next!=NULL){		//用q指针进行遍历链表

		for(s=p,q=p->next;q->next!=NULL;q=q->next)

			if(q->next->data<s->next->data)

				s=q;			//假设q指针指向的元素值小于s指向的元素值，则s=q

		if(s!=q){		//假设*s不是最后一个结点，则将s指向的结点链接到p指向的链表后面

			t=s->next;		//将结点*t从q指向的链表中取出

			s->next=t->next;

			t->next=p->next;	//将结点*t插入到p指向的链表中

			p->next=t;

		}

		p=p->next;

	}

}

void main_Select(){

	LinkList L,p;

	int n=8;

	DataType a[]={45,67,21,98,12,39,81,53};

	InitList(&L);

	CreateList(L,a,n);

	printf("排序前：\n");

	for(p=L->next;p!=NULL;p=p->next)

		printf("%d ",p->data);

	printf("\n");

	SelectSort(L);

	printf("排序后：\n");

	for(p=L->next;p!=NULL;p=p->next)

		printf("%d ",p->data);

	printf("\n");

	system("pause");

}

//链表的插入排序

void InsertSort(LinkList L){

	ListNode *p=L->next;

	ListNode *pre,*q;

	L->next=NULL;	//初始时，已排序链表为空

	while(p!=NULL){		//p是指向待排序的结点

		if(L->next==NULL){	//假设*p是第一个结点。则插入到L，并令已排序的最后一个结点的指针域为空

			L->next=p;

			p=p->next;

			L->next->next=NULL;

		}else{		//p指向待排序的结点，在L指向的已经排好序的链表中查找插入位置

			pre=L;

			q=L->next;

			while(q!=NULL&&q->data<p->data){	//在q指向的有序表中寻找插入位置

				pre=q;

				q=q->next;

			}

			q=p->next;		//q指向p的下一个结点。保存待排序的指针位置

			p->next=pre->next;	//将结点*p插入到结点*pre的后面

			pre->next=p;		//p指向下一个待排序的结点

			p=q;

		}

	}

}

void main_Insert(){

	LinkList L,p;

	int n=8;

	DataType a[]={87,34,22,93,102,56,39,21};

	InitList(&L);

	CreateList(L,a,n);

	printf("排序前：\n");

	for(p=L->next;p!=NULL;p=p->next)

		printf("%d ",p->data);

	printf("\n");

	InsertSort(L);

	printf("排序后：\n");

	for(p=L->next;p!=NULL;p=p->next)

		printf("%d ",p->data);

	printf("\n");

	system("pause");

}

void main(){

	main_Select();

	main_Insert();

}

//单链表

#pragma once

#include<stdio.h>

#include<stdlib.h>

typedef int DataType;

typedef struct Node

{

	DataType data;	//数据域

	struct Node *next;	//指针域

}ListNode,*LinkList;

//将单链表初始化为空。

动态生成一个头结点。并将头结点的指针域置为空

void InitList(LinkList *head){

	if((*head=(LinkList)malloc(sizeof(ListNode)))==NULL)

		exit(-1);

	(*head)->next=NULL;

}

//推断单链表是否为空，就是通过推断头结点的指针域是否为空

int ListEmpty(LinkList head){

	if(head->next==NULL)

		return 1;

	else

		return 0;

}

//查找单链表中第i个结点。查找成功返回该结点的指针表示成功；否则返回NULL表示失败

ListNode *Get(LinkList head,int i){

	ListNode *p;

	int j;

	if(ListEmpty(head))

		return NULL;

	if(i<1)

		return NULL;

	j=0;

	p=head;

	while(p->next!=NULL&&j<i){

		p=p->next;

		j++;

	}

	if(j==i)

		return p;

	else

		return NULL;

}

//查找线性表中元素值为e的元素，查找成功将相应元素的结点指针返回。否则返回NULL表示失败

ListNode *LocateElem(LinkList head,DataType e){

	ListNode *p;

	p=head->next;

	while(p){

		if(p->data!=e)

			p=p->next;

		else

			break;

	}

	return p;

}

//查找线性表中元素值为e的元素，查找成功将相应元素的序号返回，否则返回0表示失败

int LocatePos(LinkList head,DataType e){

	ListNode *p;

	int i;

	if(ListEmpty(head))

		return 0;

	p=head->next;

	i=1;

	while(p){

		if(p->data==e)

			return i;

		else{

			p=p->next;

			i++;

		}

	}

	if(!p)

		return 0;

}

//在单链表中第i个位置插入一个结点。结点的元素值为e。插入成功返回1，失败返回

int InsertList(LinkList head,int i,DataType e){

	ListNode *p,*pre;

	int j;

	pre=head;

	j=0;

	while(pre->next!=NULL&&j<i-1){

		pre=pre->next;

		j++;

	}

	if(!pre){

		printf("wrong place\n");

		return 0;

	}

	if((p=(LinkList)malloc(sizeof(ListNode)))==NULL)

		exit(-1);

	p->data=e;

	p->next=pre->next;

	pre->next=p;

	return 1;

}

//删除单链表中的第i个位置的结点。删除成功返回1。失败返回0

int DeleteList(LinkList head,int i,DataType *e){

	ListNode *pre,*p;

	int j;

	pre=head;

	j=0;

	while(p->next!=NULL&&pre->next->next!=NULL&&j<i-1){

		pre=pre->next;

		j++;

	}

	if(j!=i-1){

		printf("delete wrong place\n");

		return 0;

	}

	p=pre->next;

	pre->next=p->next;

	free(p);

	return 1;

}

int ListLength(LinkList head){

	ListNode *p;

	int count=0;

	p=head;

	while(p->next!=NULL){

		p=p->next;

		count++;

	}

	return count;

}

void DestroyList(LinkList head){

	ListNode *p,*q;

	p=head;

	while(p!=NULL){

		q=p;

		p=p->next;

		free(q);

	}

}