C語言又一個單連結清單的實作

#ifndef List_H
#define List_H
typedef int Item;/*定義資料項類型*/
typedef struct node * PNode;/*定義節點指針*/

typedef struct node/*節點的定義*/
{
	Item item;  /*資料域*/
	PNode next; /*鍊域*/
	
}Node;

typedef  PNode Position;
typedef  PNode List;

List MakeEmpty(List L);
/*
功能
生成空連結清單L
*/
int IsEmpty(List L);
/*
功能
判定連結清單是否為空
*/
int IsLast(Position P);
/*
功能
判定位置P的節點是否為尾節點
*/
Position Find(Item X,List L);
/*
功能
在連結清單L中查找資料項為X的第一個節點
*/
void Delete(Item X,List L);
/*
功能
在連結清單L中删除資料項為X的第一個節點
*/
Position FindPrevious(Item X,List L);
/*
功能
在連結清單L中查找資料項為X的第一個節點的前驅位置
*/
Position FindNext(Item X,List L);
/*
功能
在連結清單L中查找資料項為X的第一個節點的後繼位置
*/
void Insert(Item X,List L,Position P);
/*
功能
在連結清單L中P位置插入資料項為X的節點
*/
void DeleteList(List L);
/*
功能
删除連結清單L初頭節點外的所有節點
*/
Position Header(List L);
/*
功能
獲得連結清單L中頭節點位置
*/
Position First(List L);
/*
功能
獲得連結清單L中第一個資料節點的位置
*/
Position Advance(Position P);
/*
功能
獲得P位置的後繼節點位置
*/
Item Retrieve(Position P);
/*
功能
獲得P位置節點的資料項
*/
#endif
           

實作如下

#include"List.h"
#include<malloc.h>
#include<stdlib.h>
/*
List MakeEmpty(List L)
參數
L 要生成的空連結清單名
傳回值
傳回生成的空連結清單名
功能
生成空連結清單
*/
List MakeEmpty(List L)
{
	L = (PNode)malloc(sizeof(Node));
	L->item = 0;
	L->next = NULL;
	return L;
}

/*
int IsEmpty(List L)
參數
L 要判定的連結清單名
傳回值
若L為空傳回1，否則傳回0
功能
判斷連結清單L是否為空
*/
int IsEmpty(List L)
{
	return L->next == NULL;
}
/*
int IsLast(Position P)
參數
P 要判定的位置
傳回值
若P為為最後一個節點則傳回1，否則傳回0
功能
判斷位置P的節點是否是連結清單最後一個節點
*/
int IsLast(Position P)
{
	return P->next == NULL;
}

/*
Position Find(Item X,List L)
參數
X 要查找的資料項
L 要查找的連結清單
傳回值
若X在L中存在則傳回第一個比對節點的位置，否則傳回NULL
功能
判斷位置P的節點是否是連結清單最後一個節點
*/
Position Find(Item X,List L)
{
	Position P;
	P = L->next;
	while( P!=NULL && P->item != X )
	{
		P = P->next;
	}
	return P;
}
/*
void Delete(Item X,List L)
參數
X 要删除的資料項
L 要删除節點所在的連結清單
傳回值
無
功能
在連結清單L中删除查找到的第一個資料項為X的節點
*/
void Delete(Item X,List L)
{
	Position P,temp;	/*讀者請思考，temp為什麼是必要的？*/
	P = FindPrevious(X,L);
	if(!IsLast(P))
	{
		temp = P->next;
		P->next = temp->next;
		free(temp);
	}
}
/*
Position FindPrevious(Item X,List L)
參數
X 要查找的資料項
L 要查找的連結清單
傳回值
若X在L中存在則傳回第一個比對節點的前驅位置，否則傳回NULL
功能
傳回連結清單L中資料項為X的節點的前驅節點位置
*/
Position FindPrevious(Item X,List L)
{
	Position P;
	P = L;
	while(P->next!=NULL && P->next->item != X)
		P = P->next;
	return P;
}
/*
Position FindNext(Item X,List L)
參數
X 要查找的資料項
L 要查找的連結清單
傳回值
若X在L中存在則傳回第一個比對節點的後繼位置，否則傳回NULL
功能
傳回連結清單L中資料項為X的節點的後繼節點位置
*/
Position FindNext(Item X,List L)
{
	Position P;
	P = L;
	while(P!=NULL && P->item != X)
		P = P->next;
	return P;
}
/*
void Insert(Item X,List L,Position P)
參數
X 要插入的資料項
L 要插入的連結清單
傳回值
無
功能
在連結清單L中P位置之後插入資料項為X的新節點
*/
void Insert(Item X,List L,Position P)
{
	Position temp;
	temp = malloc(sizeof(Node));
	if(temp==NULL)
		exit(0);
	temp->item = X;
	temp->next = P->next;
	P->next = temp;
}
/*
void DeleteList(List L)
參數
L 要删除節點的連結清單
傳回值
無
功能
删除連結清單L中除了頭節點之外的所有節點
*/
void DeleteList(List L)
{
	Position P,temp;
	P = L->next;
	L->next = NULL;
	while( P!=NULL)
	{
		temp = P->next;
		free(P);
		 P = temp;
	}
}
/*
Position Header(List L)
參數
L 要查找的連結清單
傳回值
傳回連結清單L的頭節點位置
功能
傳回頭節點
*/
Position Header(List L)
{
	return L;
}
/*
Position First(List L)
參數
L 要查找的連結清單
傳回值
若連結清單非空則傳回第一個資料節點，否則傳回NULL
功能
傳回第一個資料節點位置
*/
Position First(List L)
{
	if(L->next!=NULL)
	return L->next;
}
/*
Position Advance(Position P)
參數
P 目前節點位置
傳回值
若P位置後繼節點存在則傳回其位置，否則傳回NULL
功能
獲得位置P後繼節點位置
*/
Position Advance(Position P)
{
	if(P!=NULL)
	return P->next;
}
/*
Item Retrieve(Position P)
參數
P 目前節點位置
傳回值
若P非空則傳回其資料項的值
功能
傳回P位置的資料項
*/
Item Retrieve(Position P)
{
	if(P!=NULL)
	return P->item;
}
           

測試如下

#include"List.h"
#include<stdlib.h>
int main()
{
	List list=NULL;
	Position p; 
	int i;
	list = MakeEmpty(list);
	printf("已生成空連結清單list\n");
	if(IsEmpty(list))
	printf("經檢驗list是個空連結清單\n");

	p = list;
	for(i=0;i<5;i++)
	{
		Insert(i*i,list,p);		
		p = Advance(p);
		printf("已插入的值為%d新節點\n",Retrieve(p));
	}
	p = FindNext(9,list);
	printf("資料項為9的節點後繼的資料項值為%d\n",Retrieve(p));
	
	p = FindPrevious(9,list);
	printf("資料項為9的節點前驅的資料項值為%d\n",Retrieve(p));

	Delete(9,list);
	
	p = list;
	for(i=0;i<4;i++)
	{	
		p = Advance(p);
		printf("删除資料項為9的節點剩下的節點值為%d\n",Retrieve(p));
	}
	
	DeleteList(list);
	printf("已删除連結清單list的是以資料節點\n");
	if(IsEmpty(list))
	printf("經檢驗list是個空連結清單\n");

}