链表的创建、遍历、查找、插入、删除

温馨提示

可以画图来模拟链表操作，其中要注意指针的指向，注意指针赋值的先后关系。

一、链表的创建（头插法、尾插法）

1、准备工作：
引入头文件及创建基本数据结构

#include<stdio.h>
#include<stdlib.h>	//提供 malloc 和 free 函数

typedef struct node{ //typedef 是重新定义数据类型 struct node
	int data;
	struct node *next;
}NODE,*PNODE;

2、头插法：

//头插法创建链表
PNODE HeadInsert(int n)
{
	int i,temp;
	PNODE head,p;
	head = (PNODE)malloc(sizeof(NODE));
	head->next = NULL;
	for(i = 0;i < n;i++)
	{
		scanf("%d",&temp);
		p = (PNODE)malloc(sizeof(NODE));
		p->data = temp;
		p->next = NULL;
		//头插法，顺序不能换 
		p->next = head->next;
		head->next = p;
		
	}
	return head; 
 } 
 

输入数据的顺序和表中数据的顺序是相反的。

输入顺序： 0 1 2 3 4 5 6 7 8 9
表中顺序： 9 8 7 6 5 4 3 2 1 0

3、尾插法：

 //尾插法创建链表
PNODE TailInsert(int n)
{
	int i,temp;
	PNODE head,p,tail;
	head = (PNODE)malloc(sizeof(NODE));
	head->next = NULL;
	tail = head; //tail指向尾节点，现在尾节点是head 
	for(i = 0;i < n;i++)
	{
		scanf("%d",&temp);
		p = (PNODE)malloc(sizeof(NODE));
		p->data = temp;
		p->next = NULL;
		//尾插法，节点增加后，尾指针要再次指向尾节点 
		tail->next = p;
		tail = p; //也可以 tail = tail->next; 
	}
	return head; 
 } 

二、链表的遍历与查找

1、顺序查找并打印链表

void PrintList(PNODE L) //顺序打印表中数据
{
	PNODE p;
	p = L;
	if(p->next == NULL)	//这种是含头节点链表的输出方法
	{
		printf("表中没有数据，只有一个头节点！\n");
		return ;
	}
	p = p->next;	//p指针指向第一个数据节点 
	while(p != NULL)
	{
		printf("%d ",p->data);
		p = p->next;	//p指针指向下一个数据节点 
	}
}

2、按值查找

//按值查找 
PNODE ValueSearch(PNODE Head,int key)
{
	PNODE p;
	p = Head;
	if(p->next == NULL)
	{
		printf("表中没有数据，只有一个头节点！\n");
		return Head;
	}
	p = p->next;	//p指针指向第一个数据节点 
	while(p != NULL)
	{
		if(p->data == key)
			return p;	//查找成功，返回指向该节点的指针 
			
		p = p->next;	//p指针指向下一个数据节点 
	}
	return NULL;	//查找失败，返回NULL 
/*	简洁版
PNODE ValueSearch(PNODE Head,int key)
{ 
	PNODE p = Head->next;	//指向第一个节点
	while(p != NULL && p->data != key)	
		p = p->next;	//p指针指向下一个数据节点 
	return p；	//查找成功，返回对应节点；查找失败，返回NULL 
}
*/ 
}

3、按序号查找

//按序号查找 
PNODE NumberSearch(PNODE Head,int n)
{
	int i;
	PNODE p;
	p = Head;
	if(p->next == NULL || n == 0)
	{
		printf("表中没有数据，只有一个头节点！\n");
		return Head;
	}
	p = p->next;	//p指针指向第一个数据节点 
	i = 1;			//这里不把头节点算进来 
	while(p != NULL)
	{
		if(i == n)
			return p;	//查找成功，返回指向该节点的指针 
			
		p = p->next;	//p指针指向下一个数据节点 
		i++; 
	}
	return NULL;	//查找失败，返回NULL 
}

三、链表的插入

void Insert(PNODE Head,int n,int key)
{
	int i;
	PNODE p,q;
	p = Head;
	if(p->next == NULL || n == 0)
	{
		printf("表中没有数据，只有一个头节点！\n");
		return ;
	}
	p = p->next;	//p指针指向第一个数据节点 
	i = 1;			//这里不把头节点算进来 
	while(p != NULL)
	{
		if(i == n)
		{
			q = (PNODE)malloc(sizeof(NODE));
			q->data = key;
			//顺序不能换 
			q->next = p->next;
			p->next = q;
			
			printf("插入成功！\n");
			return ;
		}		
		p = p->next;	//p指针指向下一个数据节点 
		i++; 
	}
	 
}

四、链表的删除

//删除第i个元素 
void Delete(PNODE Head,int n) 
{
	int i;
	PNODE p,q;
	p = Head;
	if(p->next == NULL || n == 0)
	{
		printf("表中没有数据，只有一个头节点！\n");
		return ;
	}
	p = p->next;	//p指针指向第一个数据节点 
	i = 1;			//这里不把头节点算进来 
	while(p != NULL)
	{
		if(i == n-1 && p->next !=NULL)	//找到删除节点的前一个节点 ，p指向它 
		{
			//顺序不能变 ，单向链表不能直接找到上一节点 
			q = p->next;	// q 指向删除节点 
			free(p->next);		//释放删除节点 
			p->next = q->next; 		//前一节点指向后一节点 
			
			printf("删除成功！\n");
			return ;
		}		
		p = p->next;	//p指向下一个节点 
		i++; 
	}
}