C語言小結之鏈表

鏈表的學習

在數據結構中有一種結構叫做線性表，線性表是儲存一個線性數據的表格，本文就簡要的介紹一下線性表的構成。

一、線性表的定義
定義：由同種類型數據元素構成的有序數列的線性結構
長度、表頭、表尾
List
線性表的形式有兩種：一種是數組構成的表，另一種是鏈表。
所謂數組形成的表就是一個數組，如下定義所示

typedef struct{
	ElementType Data[];
	int last;
}List

從上面可以看出一個線性表類型要包括一組數據和數據的最末尾。
這樣有一個弊端，就是在對線性表插入時需要對其後面的所有元素挪動位置。
故我們採取另一種方式，也就是鏈表的結構
結構如下：

typedef struct Node{
	ElementType Data;
	struct Node *Next;
}List;

二、鏈表基本功能實現
（1）求表的長度

void Length(List *Ptrl)
{
	List *p = Ptrl;
	int j =0;//記錄數量
	while(p)//結束符號為NULL
	{
		p = p->Next;
		j++;
	}
	return j;
}

（2）查找
按序號查找

List *FindKth(int K,List *Ptrl)
{
	List *p = Ptrl;
	int i = 1;
	while(p != NULL && i <K)
	{
	 	P = P->Next;
		i++;
	}
	if(i == K)
		return p;
	else 
		return NULL;
	
}

按值查找

List *Find(Element Data,List *Ptrl)
{
	List *p = Ptrl;
	while(p != NULL && p->Data != Data)
	{
		p = p->Next;
	}//找不到就是NULL
	return p;
}

（3）插入元素
在鏈表中某個位置插入某個元素
所以入口參數為元素內容、位置、鏈表。
出口參數為新的鏈表。

List *Insert(ElementType X,int i,List* Ptrl){
	List *p,*s;//新鏈表和舊鏈表
	//首先判斷參數是否有效
	p = FindKth(i-1,Ptrl);//獲取i-1號節點
	if(p == NULL)
	{
		printf("參數錯誤");
		return NULL;
	}
	else
	{
		//如果在表頭插入元素
		if(i == 1){//重新申請一片空間
			s = (List*)malloc(sizeof(List));
			s->Data = X;
			s->Next = Ptrl;
			return Ptrl;
		}
		else{
			s = (List*)malloc(sizeof(List));
			s->Data = X;//交接工作  新節點插入
			s->Next = p->Next;
			p->Next = s;
			return Ptrl;
		}
	}
}

（4）刪除元素
List* Delete(int i, List *PtrL)
1、先找到鏈表的第 i-1 個結點，用p 指向；
2、再用指針s 指向要被刪除的結點：P的下一個節點
3、然後修改指針，刪除s 所指結點;
4、最後釋放s 所指結點的空間。

List* Delete(int i, List *PtrL)
{
	List *p,*s;//新舊鏈表
	//判斷數據有效性
	p = FindKth(i-1,Ptrl);//獲取i-1號節點
	if(p == NULL)
	{
		printf("參數錯誤");
	}
	else{
		if(i == 1){//在頭部插入元素
			p = p->next;
			free(s);
			return Ptrl;
		}
		else{
			s = p->Next;
			p->Next = s->Next;
			free(s);
			return Ptrl;
		}
	}
}

註意：在進行指針操作時要記住判斷是否為空；