c语言链表的使用

一.链表与数组的比较

1.存储分配方式：
  数组一般采用一段连续的存储单元依次存储数组元素。而链表采用链式存储结构，用一组任意的存储单元存放链表元素。
2.时间复杂度比较：
  查找：数组O(1)；链表O(n)
  插入和删除：数组O(n)；链表O(1)
3.空间性能比较：
  数组存储结构需要预分配存储空间，分大了造成浪费，分小了容易发生溢出。链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。
  通过上面的对比，可以得出一些结论：数组适合需要频繁查找但很少进行插入和删除操作的情况；链表适合需频繁的插入和删除元素但很少查找的情况。另外，当所用元素个数变化较大或者根本不知道多大时，最好用链表结构，这样就不用考虑存储空间大小的问题。
  总之，数组和链表各有优缺点，有种互补的关系，要根据实际情况来选择合适的数据结构。由于数组较为简单，不做过多介绍，接下来详细介绍链表的使用方法。

二.链表的使用方法

对于链表的操作主要分为以下几部分：
1.链表整表的创建；
2.链表元素的读取；
3.链表元素的更改；
4.链表元素的插入；
5.链表元素的删除；
6.链表整表的删除；
下面进行详细的介绍：

/* 首先对于整个链表要定义一个Node节点 */
typedef struct Node {
    
	int data;                //数据域，存放该节点数据
	struct Node *next;       //指针域，存放下一个节点的地址
}*LinkList;                  //类型重命名

1.链表整表的创建

/** * @brief 创建一个链表，长度为n * * @param n:创建链表的长度 * * @return 首节点地址 * */
LinkList CreateListTail(int n)
{
    
	int i = 0;
	LinkList p, r, head;                       //其中r为始终指向尾节点，p为中间操作节点,head为保存该链表的首地址，作为最终的返回值
	r = (LinkList)malloc(sizeof(Node));        //给r分配一个Node大小的存储空间,作为线性链表的头，不存储数据
	head = r;                                  //将当前首地址赋给head,作为最后返回值
	for (i = 0; i < n; i++)
	{
    
		p = (LinkList)malloc(sizeof(Node));        //给p分配一个Node大小的存储空间
		p->data = i;                               //给p节点赋值
		r->next = p;                               //将r指向p，重要一步！！！
		r = p;                                     //将r地址后移，毕竟始终要指向链表尾地址
	}
	r->next = NULL;                                //待n个节点创建完毕后链表尾指向NULL
	return head;
}

2.链表元素的读取

/** * @brief 读取链表中第i个节点的数据（不算首节点） * * @param head:链表的首地址 * i:读取的位置 * *get_data:读取到的数据存放地址 * * @return 1:读取成功 * 0:读取失败 */
int GetElem(LinkList head, int i, int *get_data)
{
    
	int j=0;
	LinkList p;               //此处定义的p作为最终找到的节点的地址
	p = head->next;
	/*首先要找到需要的位置p*/
	while ( p && j < i)       //判断p部位空且j < i
	{
    
		p = p->next;          //让p指向下一个结点
		j++;
	}
	if (!p || j > i)          //如果p为NULL则没找到p，返回失败
    return 0;                 //第i个元素不存在，读取失败
    /*找到p以后指向以下操作*/
	*get_data = p->data;      //取第i个元素的数据到get_data地址
	return 1;                 //成功
}

3.链表元素的更改

/** * @brief 改写链表中第i个节点的数据（不算首节点） * * @param head:链表的首地址 * i:改变的位置 * change_data:要改变的数据 * * @return 1:改写成功 * 0:改写失败（可能要改写的位置超限） */
int ChangeElem(LinkList head, int i, int change_data)
{
    
	int j = 0;
	LinkList p;               //此处定义的p作为最终找到的节点的地址
	p = head->next;
	/*首先要找到需要的位置p*/
	while (p && j < i)
	{
    
		p = p->next;           //让p指向下一个结点
		j++;
	}
	if (!p || j > i)            //如果p为NULL则没找到p，返回失败
    return 0;                   //第i个元素不存在，读取失败
    /*找到p以后指向以下操作*/
	p->data = change_data;      //改变当前节点的数据
	return 1;                   //成功
}

4.链表元素的插入

/** * @brief 在链表中i处插入一个节点（从0开始） * * @param head:链表的首地址 * i:插入的位置 * insert_data:要插入节点的数据 * * @return 1:插入成功 * 0:插入失败（可能要插入的位置超限） */
int ListInsert(LinkList head, int i, int insert_data)
{
    
	int j = 0;
	LinkList p,s; 				//p为动态调用节点，s为需要插入的节点
	p = head;     

	/*首先要找到需要插入的节点的前一个节点p*/
	while (p && j < i)
	{
    
		p = p->next;            //让p指向下一个结点
		j++;
	}
	if (!p|| j > i)             //如果p为NULL则没找到p，返回失败
		return 0;               //第i个元素不存在，失败
	/*找到p以后指向以下操作*/
	s = (LinkList)malloc(sizeof(Node));   //1.给s分配一个Node大小的存储空间
	s ->data = insert_data;               //2.给s节点赋值
	s->next = p->next;                    //3.s->next指向之前的p->next，注意此时的p还没变
	p->next = s;                          //4.现在p->next指向s，至此完成了一个节点的插入
	return 1;                             //插入成功
}

5.链表元素的删除

/** * @brief 在链表中i处删除一个节点 * * @param head:链表的首地址 * i:删除的位置 * get_data:被回收位置p的数据 * * @return 1:删除成功 * 0:删除失败（可能要删除的位置超限） */
int ListDelete(LinkList head, int i, int *get_data)
{
    
	int j = 0;
	LinkList p,q;              //p为动态调用节点,用来指向需要查找的位置,q为临时缓存区
	p = head;                  //注意理解：此处为什么是p = head而不是p = head->next，因为找的是需要的前一个位置

	/*首先要找到需要删除的节点的前一个节点p*/
	while (p && j < i)
	{
    
		p = p->next;           //让p指向下一个结点
		j++;
	}
	if (!(p->next) || j > i)    //注意：此处一定要判断p->next是否为空！！！因为当前找的是前一个节点！！！
		return 0;               //i超限，失败
    /*找到p以后指向以下操作*/
	*get_data = p->next->data;  //将要删除的节点数据保存返回，注意此处p的位置是要删除节点的前一个节点
	q = p->next;                //把当前节点地址存一下给q,防止下面被改变了
	p->next = p->next->next;    //将该节点的前节点指向其后节点，也就是删除了
	free(q);                    //别忘了释放内存！！！
	return 1;                   //成功
}

6.链表整表的删除

/** * @brief 整个链表删除 * * @param head:链表的首地址 * * @return void */
void ClearList(LinkList head)
{
    
	LinkList p,q;                       
	p = head->next;
	while (p)
	{
    
		q = p->next;    //先把p的下一个节点地址备份在q中
		free(p);        //释放节点p内存
		p = q;          //令p后移
	}
	head->next = NULL;  //头结点指针域为空
}

7.main()函数

以上是链表的常用操作，下面写main()函数做功能性验证：

#include "stdio.h" 
#include "stdlib.h" 
//为了调试方便，添加以下两个函数
/** * @brief 打印出链表中的数据 * * @param head:链表的首地址 * n:链表的长度 * * @return void * */
void ShowLinkListData(LinkList head, int n)
{
    
	int i = 0;
	LinkList p= head;
	for (i = 0; i < n; i++)
	{
    
		p = p->next;                        //head指向下一个节点
		printf("%d ", p->data);
	}
}
/** * @brief 返回链表节点个数 * * @param head:链表的首地址 * * @return 链表节点个数 * */
int ListLength(LinkList head)
{
    
	int i = 0;
	LinkList p = head->next;    /* p指向第一个结点 */
	while (p)                   //直到节点地址为空时退出
	{
    
		i++;
		p = p->next;
	}
	return i;
}
/*主函数*/
int main()
{
    
	int i = 0;
	int get_data = 0;
	int result = 0;
	LinkList head;          //注意：不能再各函数中修改head头指针指向位置

	//创建一个链表，共有10个节点(还有一个是首节点，不做计算)
	head = CreateListTail(10);         
	printf("原始数据如下：");
	ShowLinkListData(head, 10);   //显示当前链表的数据
	printf("\n链表节点个数是：%d", ListLength(head));

	//获取链表中某个节点的数据
	result = GetElem(head,9,&get_data);         //获取该链表中第3个节点数据
	if(result) printf("\n\n获取数据成功：get_data=%d\n", get_data);
	else printf("\n\n不存在，获取失败!\n");

	//改写链表中第i个节点的数据（不算首节点）
	result = ChangeElem(head, 2, 222);         //改变链表中第2个节点的数据为222
	if (result) printf("\n改写成功，改写后数据如下：");
	else printf("\n位置超限，改写失败!");
    //改写之后再读看看
	ShowLinkListData(head, 10);   //显示当前链表的数据

	//在链表中i处插入一个节点
	result = ListInsert(head,10, 2222);     //在节点10插入2222
	if (result) printf("\n\n插入成功，插入后数据如下：");
	else printf("\n位置超限，插入失败！\n");
	//插入之后再读看看
	ShowLinkListData(head, 11);   //显示当前链表的数据
	printf("\n链表节点个数是：%d", ListLength(head));

	//在链表中删除某个节点
	result = ListDelete(head,10,&get_data);
	if(result) printf("\n\n删除成功，删除节点数据为：%d\n", get_data);
    else printf("\n超限，删除失败!\n");
	//改写之后再读看看
    ShowLinkListData(head,10);   //显示当前链表的数据
	printf("\n链表节点个数是：%d", ListLength(head));

	//整个链表删除
	ClearList(head);
	printf("\n\n链表节点个数是：%d\n", ListLength(head));

	system("pause");
	return 0;
}

8.程序执行结果

原始数据如下：0 1 2 3 4 5 6 7 8 9
链表节点个数是：10

获取数据成功：get_data=9

改写成功，改写后数据如下：0 1 222 3 4 5 6 7 8 9

插入成功，插入后数据如下：0 1 222 3 4 5 6 7 8 9 2222
链表节点个数是：11

删除成功，删除节点数据为：2222
0 1 222 3 4 5 6 7 8 9
链表节点个数是：10

链表节点个数是：0
请按任意键继续. . .

三.总结

  至此，链表的基本操作函数介绍完毕，足以应付一般用途，另外链表还分为静态链表、循环链表、双向链表，感兴趣可以去了解。