清華大佬耗費三個月吐血整理的幾百G的資源，免費分享！....>>>

單鏈表的各種方法，包括帶頭結點和不帶頭結點兩種

/*
   頭文件說明：單鏈表實現，函數名后帶_WithOutHead表示不帶頭結點的單鏈表
   而正常函數名則表示帶頭結點，事實上更多是帶頭結點的
*/
#ifndef SINGLE_LINKLIST_H
#define SINGLE_LINKLIST_H

#include <stdio.h>
#include <stdlib.h>

typedef int DataType;

typedef struct Link{
	DataType data;
	struct Link* next;
}*LinkList, LNode;

/*
函數原型聲明如下：
void InitLinkList(LinkList *l);						// 初始化
int LinkListLen(LinkList l);						// 求鏈表長度
LNode* GetElem(LinkList l, int i);					// 按序號查找
LNode* LocateElem(LinkList l, DataType e);			// 按值查找
int LinkListInsert(LinkList* l, int i, DataType e);	// 插入結點
int LinkListDelete(LinkList* l, int i);				// 刪除結點
void ClearLinkList(LinkList *l);					// 置空鏈表
void CreateLinkList(LinkList *l, int n);			// 創建鏈表
void DispLinkList(LinkList l);						// 輸出鏈表
*/

void InitLinkList(LinkList *l){				// 帶頭結點的初始化方法
	(*l) = (LinkList)malloc(sizeof(LNode));
	(*l) -> next = NULL;
}


void InitLinkList_WithOutHead(LinkList *l){	// 不帶頭結點的初始化方法
	(*l) = NULL;
}

/*
   函數：LinkListLen()
   功能：求出鏈表的長度
   輸入輸出：參數是鏈表頭結點的指針，返回值是鏈表長度
   變量說明：
*/
int LinkListLen(LinkList l){
	int length = 0;
	LinkList p = l;

	while(p -> next){
		length++;
		p = p -> next;
	}
	return length;
}

int LinkListLen_WithOutHead(LinkList l){
	int length = 0;
	LinkList p = l;

	while(p){
		length++;
		p = p -> next;
	}
	return length;
}

/*
   函數：GetElem()
   功能：獲取鏈表序號為i的節點
   輸入輸出：參數l是鏈表頭結點指針，i是所要獲取的節點的序號
   變量說明：
*/
LNode* GetElem(LinkList l, int i){
	int num = 1;
	LinkList p = l -> next;

	if(i > LinkListLen(l)){
		printf("所要獲取的位置序號大于鏈表長度，鏈表長度為%d\n", LinkListLen(l));
		return NULL;
	}
	while(p && num < i){
		p = p -> next;
		num++;
	}

	return p;		
}

LNode* GetElem_WithOutHead(LinkList l, int i){
	int num = 1;
	LinkList p = l;

	if(i > LinkListLen_WithOutHead(l)){
		printf("所要獲取的位置序號大于鏈表長度，鏈表長度為%d\n", LinkListLen_WithOutHead(l));
		return NULL;
	}
	while(p && num < i){
		p = p -> next;
		num++;
	}
	return p;
}
/*
   函數：LocateElem()
   功能：按值查找
   輸入輸出：參數l為鏈表頭結點指針，e為要查找的節點數據，返回值是已找到的節點的地址
   變量說明：
*/
LNode* LocateElem(LinkList l, DataType e){
	LinkList p = l;

	while(p){
		p = p -> next;
		if(p -> data == e)
			return p;
	}
	return NULL;
}

LNode* LocateElem_WithOutHead(LinkList l, DataType e){
	LinkList p = l;

	while(p){
		if(p -> data == e)
			return p;
		p = p -> next;
	}
	return NULL;
}
/*
   函數：LinkListInsert()
   功能：在鏈表中序號為i的位置插入數據為e的節點
   輸入輸出：參數l為鏈表頭結點指針的地址，i為序號，e為數據，返回值為插入操作的布爾值
   變量說明：
*/
int LinkListInsert(LinkList* l, int i, DataType e){
	LinkList p = (*l);
	LinkList pr = (LinkList)malloc(sizeof(LNode));
	int num = 1;

	if(i > LinkListLen(*l) || i < 1){
		printf("要插入的序號位置大于鏈表長度或小于1，鏈表長度為%d\n", LinkListLen(*l));
		return 0;
	}
	while(num < i && p -> next){
		num++;
		p = p -> next;
	}
	pr -> data = e;
	pr -> next = p -> next;
	p -> next = pr;

	return 1;
}

int LinkListInsert_WithOutHead(LinkList *l, int i, DataType e){
	LinkList p = (*l);
	LinkList pr = (LinkList)malloc(sizeof(LNode));
	int num = 1;

	if(i > LinkListLen_WithOutHead(*l) || i < 1){
		printf("要插入的序號位置大于鏈表長度，鏈表長度為%d\n", LinkListLen_WithOutHead(*l));
		return 0;
	}
	while(num < i - 1 && p){
		num++;
		p = p -> next;
	}
	pr -> data = e;
	pr -> next = p -> next;
	p -> next = pr;

	return 1;
}
/*
   函數：LinkListDelete()
   功能：刪除鏈表中序號為i的節點
   輸入輸出：參數l是鏈表頭結點指針的地址值，i是要刪除的節點序號,返回值是刪除操作的布爾值
   變量說明：
*/
int LinkListDelete(LinkList* l, int i){
	LinkList p = (*l) -> next;
	LinkList pr = NULL;
	int num = 1;

	if(i > LinkListLen(*l)){
		printf("要刪除的節點序號大于鏈表長度了，鏈表長度為%d\n", LinkListLen(*l));	
		return 0;
	}
	while(num < i - 1 && p){
		p = p -> next;
		num++;
	}
	pr = p -> next;
	p -> next = p -> next -> next;
	free(pr);

	return 1;
}

int LinkListDelete_WithOutHead(LinkList* l, int i){
	LinkList p = (*l);
	LinkList pr = NULL;
	int num = 1;

	if(i > LinkListLen_WithOutHead(*l)){
		printf("要刪除的節點序號大于鏈表長度了，鏈表長度為%d\n", LinkListLen_WithOutHead(*l));
		return 0;
	}
	while(num < i - 1 && p){
		p = p -> next;
		num++;
	}
	pr = p -> next;
	p -> next = p -> next -> next;
	free(pr);

	return 1;
}
/*
   函數：ClearLinkList()
   功能：用于清除鏈表
   輸入輸出：參數為鏈表頭結點的指針的地址，無返回值
   變量說明：p用于動態指向鏈表節點，pr用于釋放內存
*/

void ClearLinkList(LinkList *l){
	LinkList p = (*l);
	LinkList pr = NULL;

	while(p){
		pr = p;
		p = p -> next;
		free(pr);
	}
	(*l) -> next = NULL;
}

void ClearLinkList_WithOutHead(LinkList *l){
	LinkList p = (*l);
	LinkList pr = NULL;

	while(p){
		pr = p;
		p = p -> next;
		free(pr);
	}
	(*l) = NULL;
}

/*
   函數：CreateLinkList()
   功能：創建鏈表
   輸入輸出：參數是鏈表頭結點的指針的地址l，和要創建的節點個數n，無返回值
   變量說明：i用于循環語句臨時變量，p用于動態指向鏈表節點，pr用于申請內存空間
*/

void CreateLinkList(LinkList *l, int n){
	DataType input_data;
	int i = 0;
	LNode *p = (*l);
	LNode *pr = NULL;
	
	for(i = 0; i < n; i++){
		printf("Now input the %d data :", i);		
		scanf("%d", &input_data);								// 此處輸入數據使用DataType類型

		pr = (LinkList)malloc(sizeof(LNode));
		pr -> data = input_data;
		pr -> next = NULL;
		p ->next = pr;
		p = p -> next;
	}
}

void CreateLinkList_WithOutHead(LinkList *l, int n){
	DataType input_data;
	int i;
	LinkList p = (*l);
	LinkList pr = NULL;

	if(p == NULL){
		printf("Now input the 0 data :");
		scanf("%d", &input_data);
		pr = (LinkList)malloc(sizeof(LNode));
		pr -> data = input_data;
		pr -> next = NULL;
		(*l) = pr;				// 切記此處不應該是p = pr，因為p只是指向*l而不能代表*l
	}
	for(i = 1; i < n; i++){
		printf("Now input the %d data :", i);
		scanf("%d", &input_data);

		pr = (LinkList)malloc(sizeof(LNode));
		pr -> data = input_data;
		pr -> next = NULL;
		// 注意這頗為巧妙的2句代碼
		p -> next = pr;
		p = p -> next;
	}
}
/*
   函數：DispLinkList()
   功能：輸出鏈表所有元素
   輸入輸出：參數是鏈表頭結點，無返回值
   變量說明：i用于顯示序號，p用于動態指向鏈表的節點
*/


void DispLinkList_WithOutHead(LinkList l){
	LinkList p = l;
	int i = 0;

	while(p){
		printf("The %d data = %d\n", i++, p -> data);
		p = p -> next;
	}
}

void DispLinkList(LinkList l){							
	LinkList p = l -> next;
	int i = 0;

	while(p){
		printf("The %d data = %d\n", i++, p -> data);
		p = p -> next;
	}
}
#endif