typedef struct SNode{
	void *pdata;	//存儲(chǔ)數(shù)據(jù)，這個(gè)數(shù)據(jù)可以是任意類(lèi)型
	struct SNode *next;	//節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)地址
}SNode;
typedef struct SNode*  SLink;	//定義一個(gè)鏈表

//創(chuàng)建一個(gè)鏈表
SLink create_slink();
//初始化一個(gè)鏈表
void init_slink(SLink *link);
//判斷鏈表是否為空
bool is_empty(SLink link);
//獲得鏈表存儲(chǔ)的個(gè)數(shù)
size_t size(SLink link);
//插入元素  元素存儲(chǔ)在pdata,一共size個(gè)字節(jié)
int insert(SLink link,size_t index,void *pdata,size_t size);
//獲得指定下標(biāo)的節(jié)點(diǎn)元素，并且返回其地址
void *get(SLink link,size_t index);
//刪除一個(gè)節(jié)點(diǎn)
int remove_data(SLink link,size_t index);
//鏈表逆序
SLink reverse(SLink link);
//清空鏈表
void clear(SLink link);
//銷(xiāo)毀鏈表
void destroy(SLink link);
//遍歷鏈表(通過(guò)函數(shù)指針完成用戶(hù)需要的要求)
void foreach(SLink link,void (*func)(const void *));
//通過(guò)值查找某個(gè)節(jié)點(diǎn)
void *find(SLink link,void *pdata,int (*compare)(const void *,const void*));
//通過(guò)值刪除所有需要?jiǎng)h除的節(jié)點(diǎn)
int remove_all(SLink link,void *pdata,int (*compare)(const void *,const void *));
//鏈表排序，通過(guò)冒泡排序
void sort(SLink link,int (*compare)(const void *,const void *));

static SNode *create_node(void *pdata,size_t size,SNode *next){
	SNode *node = malloc(sizeof(SNode));	//先用malloc申請(qǐng)一塊動(dòng)態(tài)內(nèi)存
	if(pdata == NULL){	//如果傳進(jìn)來(lái)的數(shù)據(jù)地址為null
		node->pdata = NULL;	
	}else{
		node->pdata = malloc(size);	//否則為數(shù)據(jù)也申請(qǐng)一塊大小為size的動(dòng)態(tài)內(nèi)存，
		memcpy(node->pdata,pdata,size);	//把pdata指向的數(shù)據(jù)通過(guò)memcpy拷貝到node->pdata里去，拷貝size個(gè)字節(jié)
	}
	node->next = next;	//讓節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)
	return node;	//返回這個(gè)節(jié)點(diǎn)
}

SLink create_slink(){
	//return create_node(NULL,0,NULL);
	SNode *head = create_node(NULL,0,NULL);		
	return  head;
}

void init_slink(SLink *link){
	*link = create_node(NULL,0,NULL);	//同樣調(diào)用生成節(jié)點(diǎn)的靜態(tài)方法
}

bool is_empty(SLink link){
	return link->next == NULL;	
}

}
size_t size(SLink link){
	size_t cnt = 0;	//用來(lái)記錄節(jié)點(diǎn)個(gè)數(shù)
	SNode *node = link->next;	//從首節(jié)點(diǎn)開(kāi)始算起
	while(node != NULL){	//遍歷這個(gè)鏈表
		++cnt;
		node = node->next;
	}
	return cnt;
}

static SNode *get_prev_node(SLink link,size_t index){	//獲得前一個(gè)節(jié)點(diǎn)
	SNode *node = link;//從頭結(jié)點(diǎn)開(kāi)始找，比如我們插入在鏈表首插入一個(gè)節(jié)點(diǎn)就是插入到頭結(jié)點(diǎn)后面
	//我們?cè)阪湵砦膊迦胍粋€(gè)節(jié)點(diǎn)就是當(dāng)node->next為null的時(shí)候插入
	size_t i;
	for(i=0;i<index && node != NULL;i++){
		node = node->next;	
	}
	return node;	//這里的返回值可能為null,比如當(dāng)node為尾結(jié)點(diǎn)的時(shí)候,它的node->next就為null
}

int insert(SLink link,size_t index,void *pdata,size_t size){
	if(pdata == NULL){	//如果沒(méi)有傳進(jìn)來(lái)數(shù)據(jù)，那就插入失敗
		return -1;	
	}
	SNode *prev = get_prev_node(link,index);
	if(prev == NULL){	//獲得插入位置的前一個(gè)節(jié)點(diǎn),當(dāng)它為Null時(shí)也不能插入數(shù)據(jù)，
		return -1;	
	}
	SNode *node = create_node(pdata,size,prev->next);	//調(diào)用生成節(jié)點(diǎn)的靜態(tài)方法生成一個(gè)節(jié)點(diǎn),
	//并且傳入pdata,size,如上圖所示,新插入的節(jié)點(diǎn)的next指向的是原本前一個(gè)節(jié)點(diǎn)prev的next
	prev->next = node; //把prev->next重新指向新插入的節(jié)點(diǎn),這樣插入就完成了
	//完成了new節(jié)點(diǎn)旁邊兩條線(xiàn)的鏈接工作
	//prev->next = create_node(pdata,size,prev->next);
	return 0;
}

void *get(SLink link,size_t index){
	SNode *node = link->next;	//這里我們不能從頭結(jié)點(diǎn)開(kāi)始遍歷，因?yàn)轭^結(jié)點(diǎn)并不存儲(chǔ)數(shù)據(jù)所以只能從首節(jié)點(diǎn)開(kāi)始遍歷
	size_t i;
	for(i=0;i<index && node != NULL;i++){
		node = node->next;	
	}
	if(node == NULL){
		return NULL;	
	}
	return node->pdata;	//遍歷完成并且返回這個(gè)數(shù)據(jù)的地址即可
}

static void remove_node(SNode *prev){	//這里的prev為需要被刪除的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
	SNode *node = prev->next;	//記錄被刪除的節(jié)點(diǎn)
	SNode *next = node->next;	//記錄被刪除的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
	free(node->pdata);
	free(node);
	prev->next = next;
}

int remove_data(SLink link,size_t index){
	SNode *prev = get_prev_node(link,index);	//獲得被刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
	if(link == NULL || prev == NULL || prev->next == NULL){
	//如果鏈表不存在或者被刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)不存在或者被刪除的節(jié)點(diǎn)不存在，那就刪除失敗
		return -1;	
	}
	remove_node(prev);
	return 0;
}

SLink reverse(SLink link){
	if(link==NULL || link->next == NULL || link->next->next == NULL){	
	//如果鏈表不存在或者只存在頭結(jié)點(diǎn)或者只存在一個(gè)節(jié)點(diǎn),那么我們就不需要進(jìn)行逆序操作
		return link;	
	}	
	SNode *prev = link->next;//記錄第一個(gè)節(jié)點(diǎn)	
	SNode *curr = link->next->next;//記錄第二個(gè)節(jié)點(diǎn)
	SNode *next;
	while(curr != NULL){	//只要當(dāng)前節(jié)點(diǎn)不為空就繼續(xù)執(zhí)行下去
		next = curr->next;	//記錄curr的下一個(gè)節(jié)點(diǎn)
		curr->next = prev;	//讓指針?lè)催^(guò)來(lái)指向，即當(dāng)前節(jié)點(diǎn)的指針指向前一個(gè)節(jié)點(diǎn)
		prev = curr;	//然后往后移
		curr = next;
	}
	//最后還有兩條線(xiàn)沒(méi)有連上
	//即以前的首節(jié)點(diǎn)（即上圖的節(jié)點(diǎn)1）的next應(yīng)該指向null,首節(jié)點(diǎn)再變?yōu)閜rev，即上圖的節(jié)點(diǎn)5
	link->next->next = NULL;	//
	link->next = prev;
	return link;
}

void clear(SLink link){
	SNode *node = link->next;	//從首節(jié)點(diǎn)開(kāi)始遍歷
	while(node != NULL){
		SNode *next = node->next;		//記錄需要被釋放的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
		free(node->pdata);
		free(node);
		node = next;
	}
	link->next = NULL;
}

void destroy(SLink link){
	clear(link);	
	free(link);
}

void foreach(SLink link,void (*func)(const void *)){
	SNode *node = link->next;	//從首節(jié)點(diǎn)開(kāi)始遍歷
	for(;node != NULL; node = node->next){
		func(node->pdata);	//把節(jié)點(diǎn)的數(shù)據(jù)傳給func這個(gè)函數(shù)，
		//然后用戶(hù)需要對(duì)這個(gè)數(shù)據(jù)進(jìn)行什么樣的處理由用戶(hù)自己決定，不僅僅是局限于把這些數(shù)據(jù)給打印出來(lái)
		//這樣的好處是對(duì)數(shù)據(jù)的處理更加靈活了
	}
}

void *find(SLink link,void *pdata,int (*compare)(const void *,const void*)){
	SNode *node = link->next;	//從首節(jié)點(diǎn)開(kāi)始查找
	for(;node != NULL; node = node->next){
		if(compare(node->pdata,pdata)==0){	//如果該節(jié)點(diǎn)的數(shù)據(jù)和帶查找的數(shù)據(jù)相等
			return node->pdata;		//那就返回這個(gè)數(shù)據(jù)的地址
		}	
	}
	return NULL;	//如果沒(méi)有找到就返回null
}

int compare(const void* v1,const void* v2){
	Stu *stu1 = (Stu *)v1;
	Stu *stu2 = (Stu *)v2;
	return v1->no-v2->no;
}

int remove_all(SLink link,void *pdata,int (*compare)(const void *,const void *)){	
	SNode *prev = link;
	int cnt = 0;
	while(prev->next != NULL){
		if(compare(prev->next->pdata,pdata)==0){	//找到待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
			remove_node(prev);	//刪除該節(jié)點(diǎn)
			cnt++;	//刪除的個(gè)數(shù)++
		}else{
			prev = prev->next;	//否則沒(méi)找到就是往下繼續(xù)查找
		}
	}
	return cnt>0?0:-1;
}

void sort(SLink link,int (*compare)(const void *,const void *)){
	if(link->next == NULL || link->next->next == NULL){
		return;	
	}	

	size_t i;
	SNode *tail = NULL;
	SNode *n = link->next;
	for(;n != NULL;n = n->next){
		SNode *node;
		bool swap = false;
		for(node = link->next;node->next != tail;node = node->next){
			SNode *prev = node;
			SNode *next = prev->next;
			if(compare(prev->pdata,next->pdata)>0){
			//這里選擇的排序方式或者進(jìn)行排序的元素
				swap(prev->pdata,next->pdata);
				swap = true;
			}
		}
		tail = node;
		if(!swap){
			break;	
		}
	}
}

int cmopare(const void *v1,const void* v2){
	Stu *s1 = (Stu *)v1;
	Stu *s2 = (Stu *)v2;
	return strcmp(s1->name,s2->name);
}