头结点链表的添加结点，删除结点，链表逆序，删除指定数据等操作的实现

//链表头文件

#ifndef __LINKLIST_H__
#define __LINKLIST_H__

#define FALSE 0
#define TRUE  1

typedef int LinkData;
typedef struct _node
{
	LinkData data;
	struct _node *next;
}Node;

//创建链表
Node* Create_List();

//尾插
int Insert_Last(Node *h, LinkData data);

//头插
int Insert_Head(Node *h, LinkData data);

//在第pos个结点处插入数据
int Insert_Pos(Node *h, int pos, LinkData data);

//删除第pos个结点
int Delete_Pos(Node *h, int pos);

//删除指定数据
int Delete_Data(Node *h, LinkData data);

//查找元素：如果有，返回元素位置
int Find_Element(Node *h, LinkData data, int *x);

//获取元素，通过位置获取
int Get_Element(Node *h, int pos, LinkData *x);

//链表长度
int List_Len(Node *h);

//清空所有结点
int Clean_List(Node *h);

//逆序
int Reverse_List(Node *h);

//显示链表信息
void Display(Node* h);

//销毁链表
int Destory(Node **h);

#endif 

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

//创建链表头结点
Node* Create_List()
{
	Node* list = (Node*)malloc(sizeof(Node)/sizeof(char));
	if (list == NULL)
		return NULL;
	
	list->next = NULL;
	
	return list;
}

//尾插
int Insert_Last(Node *h, LinkData data)
{
	if (h == NULL)
		return FALSE;
	
	Node* node = (Node*)malloc(sizeof(Node)/sizeof(char));
	if (node == NULL)
		return FALSE;
	
	node->data = data;
	node->next = NULL;
	
	Node* tmp = h;//
	//遍历链表,到最后一个结点
	while (tmp->next)
	{
		tmp = tmp->next;
	}
	tmp->next = node;//将新建结点接入链表
	
	return TRUE;
}

//头插
int Insert_Head(Node *h, LinkData data)
{
	if (h == NULL)
		return FALSE;
	
	Node* node = (Node*)malloc(sizeof(Node)/sizeof(char));
	if (node == NULL)
		return FALSE;
	
	node->data = data;
	node->next = h->next;
	h->next = node;
	
	return TRUE;
	
}


//在第pos个结点处插入数据
int Insert_Pos(Node *h, int pos, LinkData data)
{
	if (h == NULL || pos < 1)
		return FALSE;
	
	Node* node = (Node*)malloc(sizeof(Node)/sizeof(char));
	if (node == NULL)
		return FALSE;
	
	node->data = data;
	
	//寻找pos位置的前一个结点
	Node* tmp = h;
	int i;
	for (i = 0; i < pos-1; i++)
	{
		if (tmp == NULL)
			break;//插入位置越界
		tmp = tmp->next;
	}
	//检查插入位置
	if (tmp == NULL)
	{
		printf ("插入位置越界\n");
		return FALSE;
	}
	
	node->next = tmp->next;
	tmp->next = node;
	
	return TRUE;
}

//删除第pos个结点
int Delete_Pos(Node *h, int pos)
{
	if (h == NULL || pos < 1)
		return FALSE;
	
	//寻找pos位置的前一个结点
	Node* tmp = h;
	int i;
	for (i = 0; i < pos-1; i++)
	{
		if (tmp == NULL)
			break;//删除位置越界
		tmp = tmp->next;
	}
	//检查插入位置
	if (tmp == NULL)
	{
		printf ("删除位置越界\n");
		return FALSE;
	}
	
	Node *p = tmp->next;//记录要删结点的位置
	tmp->next = p->next;//越过要删结点，指向其后一个的结点
	free (p);//释放要删结点的空间
	
	return TRUE;
}


//删除指定数据
int Delete_Data(Node *h, LinkData data)
{
	if (h == NULL)
		return FALSE;
	
	Node* tmp = h;//要找前一个结点，不用h->next
	while (tmp->next)
	{
		if (tmp->next->data == data)
			break;
		tmp = tmp->next;
	}
	
	if (tmp->next == NULL)
	{
		printf ("未有该元素\n");
		return FALSE;
	}
	
	Node *p = tmp->next;//p指向要删元素所在结点
	tmp->next = p->next;
	free (p);
	
	return TRUE;
}


//查找元素：如果有，返回元素位置
int Find_Element(Node *h, LinkData data, int *x)
{
	if (h == NULL)
		return FALSE;
	
	Node *tmp = h->next;//找元素本身位置用h->next
	int k = 1;//元素位置从1开始
	while (tmp)
	{
		if (tmp->data == data)
		{
			*x = k;
			return TRUE;
		}
		k++;
		tmp = tmp->next;
	}
	
	printf ("未有该元素\n");
	return FALSE;
}

//获取元素，通过位置获取
int Get_Element(Node *h, int pos, LinkData *x)
{
	if (h == NULL || pos < 1)
		return FALSE;
	
	Node* tmp = h;
	int i;
	for (i = 0; i < pos; i++)
	{
		if (tmp == NULL)
			break;
		tmp = tmp->next;
	}
	//检查位置
	if (tmp == NULL)
	{
		printf ("位置越界\n");
		return FALSE;
	}
	else
	{
		*x = tmp->data;
	}
	
	return TRUE;
}


//链表长度
int List_Len(Node *h)
{
	if (h == NULL)
		return 0;
	
	Node *tmp = h;
	int count = 0;
	while (tmp->next)
	{
		count++;
		tmp = tmp->next;
	}
	
	return count;
}


//逆序
int Reverse_List(Node *h)
{
	//h->next 空表情况   h->next->next只有一个结点
	if (h == NULL || h->next == NULL || h->next->next == NULL)
		return FALSE;
	Node* pre = h->next;      //指向第一个结点
	Node* cur = h->next->next;//指向第二个结点
	Node* tmp = NULL;
	
	while (cur)
	{
		tmp = cur->next;//cur->next和tmp指向第三个结点
		cur->next = pre;//让第二个结点的next指针指向第一个结点
		
		pre = cur;      //pre的指向往后移一个位置
		cur = tmp;      //cur的指向也往后移一个位置
	}                 //即原先指向第一第二结点变为指向第二第三结点
	
	h->next->next = NULL;//原先第一个结点的做最后一个结点，其next要指向空
	h->next = pre;//头结点指向新的第一结点（原最后的结点）

	/*最后这两步不能颠倒，如果颠倒的话，h->next = pre; h->next->next = NULL; 意义就变为先让头结点h->next指向pre，再将pre的next置空（h->next = pre 所以 h->next->next = NULL 等价于 pre->next = NULL），链表就只剩一个结点，其余结点也没有释放内存，造成内存泄漏*/

	return TRUE;
}


//显示链表信息
void Display(Node* h)
{
	if (h == NULL)
		return;
	
	int count = 0;
	Node* tmp = h->next;
	while (tmp)
	{
		if (count++ % 4 == 0)//4个数据一组
			printf ("\n");
			
		printf ("%8d", tmp->data);
		tmp = tmp->next;
	}
	
	printf ("\n");
}

//清空所有结点
int Clean_List(Node *h)
{
	if (h == NULL)
		return FALSE;
	Node *tmp = h;
	while (tmp->next)
	{
		Delete_Pos(h, 1);//从头一直删
	}
	
	return 0;
}



//销毁链表
int Destory(Node **h)
{
	if (*h == NULL)
		return FALSE;
	Clean_List(*h);//清空结点
	
	free (*h);//释放头结点的空间
	*h = NULL;
	
	return TRUE;
}

//打印链表数据
void print(Node*h)
{
	if (h == NULL)
		return;
	
	Node*tmp = h->next;
	while(tmp)
	{
		printf("%-3c", tmp->data);
		tmp = tmp->next;
	}
	printf("\n");
	
}

//主函数，具体操作实践

#include <stdio.h>
#include "LinkList.h"

int main()
{
	//创建链表
	Node* h = Create_List();
	if (h == NULL)
	{
		printf ("创建失败\n");
		return -1;
	}
	
	int i;
	for (i = 0; i < 10; i++)
	{
		Insert_Last(h, i);
	}
	/*
	for (i = 0; i < 10; i++)
	{
		Insert_Head(h, i);
	}
	*/
	printf ("链表长度：%d\n",List_Len(h));
	
	Insert_Pos(h, 3, 1000);
	Display(h);
	
	int x;
	Find_Element(h, 3, &x);
	printf ("元素在第%d位上\n", x);
	Get_Element(h, 3, &x);
	printf ("位置上的元素是：%d\n", x);
	
	Delete_Pos(h, 3);
	Display(h);
	
	Delete_Data(h, 56);
	Display(h);
	
	Reverse_List(h);
	Display(h);
	
	Clean_List (h);
	printf ("链表长度：%d\n",List_Len(h));
	

	Destory(&h);
	Insert_Pos(h, 1, 1000);
	Display(h);
	
	return 0;
}