单链表及其基础操作详解

单链表一般由链表头和链表节点组成，两者一般由两种不同的结构体组成，其差别就是链表头结构体相对于链表节点结构体，是没有数据域的，取而代之的是链表的一些参数数据。本文所讲的链表头结构体和链表节点结构体一样。

// 链表节点结构体
typedef struct node
{
	void* data;
	struct node* next;
}NODE_T;	

//链表头结构体（无数据域）
typedef struct Listhead
{
	NODE_T* next;
}HEAD_T;

链表特点是空间内存不连续，因为节点是地址是离散的，是由指针串联起来，所以，对于链表的中间部分数据的删除和增添就比较方便，相比较与数组来说。
链表的基础操作
初始化节点

NODE_T* Initnode();

NODE_T* Initnode()
{
	NODE_T* head = malloc(sizeof(NODE_T));		//malloc一个链表头大小的空间
	if(head != NULL) printf("create err!\n");
	else 
	{
		memset(head,0,sizeof(NODE_T));			//对于链表头进行清零操作
		head->next = NULL;
	}
	return head;
}

链表长度计算

int ListCount(NODE_T* head);

int ListCount(NODE_T*head)
{
	NODE_T* tmp = head;
	int count=0;
	while(tmp->next != NULL)
	{
		count++;
		tmp=tmp->next;
	}
	return count;
}

链表尾部插入节点（尾插法）

void ListAddNodeBack(NODE_T* head,void* data);

void ListAddNodeBack(NODE_T* head, void* data)
{
	//新建节点，将参数赋值
	NODE_T* node = malloc(sizeof(NODE_T));
	memset(node,0,sizeof(NODE_T));

	node->data = data;
	node->next = NULL;
	//遍历到链表尾
	while(head->next != NULL)
	{
		head = head->next;
	}
	//尾插新的节点
	head->next = node;
}

链表头部插入节点（头插法）

void ListAddNodeBack(NODE_T* head,void* data);

void ListAddNodeFront(NODE_T* head, void* data)
{
	//新建节点，将参数赋值
	NODE_T* node = malloc(sizeof(NODE_T));
	memset(node,0,sizeof(NODE_T));

	node->data = data;
	node->next = NULL;
	//在链表第一个节点前插入
	node->next = head->next;
	head->next = node->next;
}

链表成员删除

int ListDelNode(NODE_T* head, int indax);

int ListDelNode(NODE_T* head, int indax)
{
	int pos=0;
	NODE_T* tmp=NULL;

	while(head->next!=NULL)
	{
		pos++;
		if(pos==indax)
		{
			tmp=head->next;
			head->next=tmp->next;
			free(tmp->data);
			free(tmp);
			return 1;
		}
		head=head->next;
	}
	return 0;
}

查找指定位置链表成员

NODE_T* FindList(NODE_T* head, int indax);

NODE_T* FindList(NODE_T* head, int indax)
{
	int pos = 0;
	NODE_T* hd = NULL;
	hd = head;
	while(hd->next != NULL)
	{
		pos++;
		if(pos == indax)
		{
			return hd->next;
		}
		hd = hd->next;
	}
	return NULL;
}

修改指定位置的节点数据

int ChangeListNode(NODE_T* head, void* data, int indax);

int ChangeListNode(NODE_T* head, void* data, int indax)
{
	int pos;
	NODE_T* hd;
	hd = head;
	while(hd->next != NULL)
	{
		pos++;
		if(pos == indax)
		{
			hd->data = data;
			return 1;		
		}
		hd = hd->next;
	}
	return 0;
}

链表逆序

NODE_T *Listreverse(NODE_T* head);

NODE_T *Listreverse(NODE_T* head)
{
	if(head->next == NULL || head->next->next == NULL)return head;
	
	NODE_T* p1 = head->next;
	NODE_T* p2 = head->next->next;
	NODE_T* P3 = NULL;
	
	while(p2 != NULL)
	{
		p3 = p2->next;
		p2->next = p1;
		if(p1 == head->next)
		{
			p1->next = NULL;
		}
		p1=p2;
		p2=p3;
	}
	head->next = p1;
	return head;
}

链表到文件

void ListToFile(char* filename, NODE_T* head, int leng);

void ListToFile(char* filename, NODE_T* head, int leng)				
{
	FILE* fp = fopen(filename,"w+");					//w+是读写加创建，如果打开的文件是空，不存在的，那么就会创建一个新的文件
	while(head->next!=NULL)
	{
		fwrite(head->next->data,leng,1,fp);				//fwrite是指从(因为通用链表他会指向任何结构体)data结构中读取长度为leng的数据到文件fp中
		head=head->next;
	}
	fclose(fp);
}

文件到链表

void ListToFile(char* filename, NODE_T* head, int leng);

void FileToList(char* filename, NODE_T* head, int leng)				//因为是通用的链表所以这里的长度是可以根据外面传进来的决定，那么就可以传许多种不同的数据
{
	FILE* fp = fopen(filename,"r+");					//可读可写，但是不可以创建新的文件				
	void* data = NULL;
	int ret=0;

	while(1)
	{
		data = malloc(leng);							
		memset(data,0,leng);
		ret = fread(data,leng,1,fp);					//fread函数，每次读取一次，读取了多少光标都会向后面移多少
		if(ret==0)			//fread返回值为读取标志位，如果读取数据不为空，则返回1，如果读取数据为空，则返回0
		{
			break;			//读取没有数据了，跳出循环
		}
		ListAddNode(head,data);							//通用链表添加，将读取的数据存到链表中
	}
	fclose(fp);				//关闭文件
}