weixin_43667308的博客

I. 单向链表的C语言实现

作为一种基本的数据结构，链表经常在程序开发过程中使用. 对于C语言，链表的实现主要取决于结构和指针，因此本文的相关内容和过程都需要具有C语言中的指针和结构的基础.

链表是一种线性存储数据的结构. 存储内容在逻辑上是连续的，但不一定是物理上的. 单向链表的组成包括链表头（head）和许多链表元素（节点），链表的基本操作实际上是添加，删除，修改，检查.

首先谈谈单链表的C语言实现方法. 为了实现单向链表，首先定义一个结构:

/ *定义表示链接列表的结构指针/

结构列表{

int id; /标识此元素以便于搜索/

char data [20]; /链表中包含的元素* /

下一个结构列表； /指向下一个链接列表的指针* /

};

让我们写一个程序来实现链表的基本操作. 该程序的功能是首先分配几个链表元素（节点），然后为这些链表元素分配初始值. 分配初始值后，将这些链表元素按顺序添加到链表中，最后按顺序打印出这些元素的数据字段. . （注意: 该程序实现存储在链表头部的数据；为了确保每个元素的id字段不同，定义了一个全局静态数据成员list_id；在Linux下使用gcc进行编译）. 步骤如下:

/* 包含的头文件 */

#include

#include

/ *定义表示链接列表的结构指针/

结构列表{

int id; /标识此元素以便于搜索/

char data [20]; /链表中包含的元素* /

下一个结构列表； /指向下一个链接列表的指针* /

};

/ *定义链接列表头* /

静态结构体列表* list_head = NULL;

/ *为了确保每个链接列表元素的id不同，该id被故意定义为全局静态变量* /

static int list_id = 0;

/ **在聊天列表的末尾插入指定的元素

/ **遍历链表并打印链表每个元素中包含的数据

/ *主要功能，程序的入口* /

int main（int argcc ++链表，char * argv []）

{

int i = 0;

结构列表* lists = NULL;

/* 分配10个元素 */
lists = malloc(sizeof(struct list) * 10);
if(NULL == lists)
{
	printf("malloc error!\n");
	return -1;
}
/* 将分配的10个元素依次填充数据并加入到链表当中 */
for(i = 0; i < 10; i++)
{
	lists[i].id = list_id++;
	sprintf(lists[i].data, "TECH-PRO - %d", i);
	list_add(&list_head, &lists[i]);
}
/* 遍历链表，把链表中每个元素的信息都打印出来 */
list_print(&list_head);
return 0;
}

第二，单向链表的基本操作

链表的基本操作实际上是链表中元素的操作. 链表的基本操作包括链表中节点元素的添加，删除，修改和查看. 简单来说，它们就是添加，删除，修改和检查.

2.1在单向链接列表中添加元素

在链表中添加元素时，首先确定链表是否为空. 如果为空，则直接将要添加的元素分配到链接列表的开头. 否则，它将遍历链接列表以找到下一个空节点，然后将元素插入到列表的末尾.

用于插入链表的程序代码:

/**	将指定元素插入到聊表尾部
  * 	head	: 表示要插入元素的链表的头部的地址
  *	list    : 表示要插入到链表中的元素
  */
static void list_add(struct list **head, struct list *list)
{
	struct list *temp;
 
	/* 判断链表是否为空 */
	if(NULL == *head)
	{
		/* 为空 */
		*head = list;
		(*head)->next = NULL;
	}
	else
	{
		/* 不为空 */
		temp = *head;
		while(temp)
		{
			if(NULL == temp->next)
			{
				temp->next = list;
				list->next = NULL;
			}
			temp = temp->next;
		}
	}
}

主要功能字段中的以下代码:

struct list temp_list;
 
/* 填充这个结构体并加入链表当中 */
	temp_list.id = list_id++;
	sprintf(temp_list.data, "temp_list");
	list_add(&list_head, &temp_list);

2.2删除单链列表中的元素

在链表的基本操作中，删除链表中的元素节点相对复杂. 首先，有必要确定链接列表是否为空. 当链接列表不为空时，有必要确定要删除的元素是否为头节点. 如果将下一个元素直接分配给头节点，则必须遍历整个列表. 链表找到要删除的节点元素. （注意: 此算法实现的删除操作是通过元素节点的id字段执行的. ）

用于删除链接列表节点的程序代码:

/**	将指定元素从链表尾部删除
  * 	head	: 表示要删除元素的链表的头部的地址
  *	id      : 表示要删除元素的标识
  *	返回值  : 0-成功，-1-失败
  */
static int list_del(struct list **head, int id)
{
	struct list *temp, *p;
	temp = *head;
 
	if(NULL == temp)
	{
		/* 链表为空 */
		printf("链表为空!\n");
		return -1;
	}
	else
	{
		/* 判断匹配的元素是否为链表头部的元素 */
		if(id == temp->id)		/* 是链表头部 */
		{
			*head = temp->next;
			return 0;
		}
		else					/* 不是链表头部 */
		{
			while(temp->next)
			{
				p = temp;
				temp = temp->next;
 
				if(id == temp->id)
				{
					p->next = temp->next;
					return 0;
				}
			}	
			return -1;
		}
	}
 
	return -1;
}

在主函数中添加以下代码:

/* 删除链表中开始位置、中间位置、尾部的元素 */
	list_del(&list_head, 0);
	list_del(&list_head, 5);
	list_del(&list_head, 10);

编译程序的结果: 删除元素0、5和10:

2.3修改单链列表中的指定元素

修改链接列表中的元素. 通过遍历链接列表中的元素c ++链表，可以找到要修改的元素并修改其内容. 修改链接列表的元素相对容易. （注意: 要修改的元素的定位是通过id字段完成的）

修改链表中元素的过程如下:

/**	将指定id的元素所定义的内容进行修改
  * 	head	: 表示要改变元素的链表的头部的地址
  *	id      : 表示要改变元素的标识
  *	content : 表示要改变的内容
  *	返回值  : 0-成功，-1-失败
  */
static int list_chg(struct list **head, int id, char *content)
{
	struct list *temp;
 
	temp = *head;	/* 将链表的头部赋值给临时聊表变量 */
 
	while(temp)		/* 对链表进行轮询 */
	{
		if(id == temp->id)
		{
			memset(temp->data, 0, sizeof(temp->data));
			sprintf(temp->data, "%s", content);
			temp->data[strlen(content)] = '\0';
			return 0;
		}
		temp = temp->next;
	}
	return -1;
}

在主函数中添加以下代码:

/* 改变id为4的元素所对应的值为 "change!!!" */
	list_chg(&list_head, 4, "change!!!");

2.4对单向链表元素的查询操作

查询链表中的元素，并根据链表的标题遍历链表.

链接列表中用于查询的程序代码:

/**	将指定id的元素所定义的内容进行查找
  * 	head	: 表示要查询元素的链表的头部的地址
  *	id      : 表示要查询元素的标识
  *	返回值  : 0-成功，-1-失败
  */
static int list_query(struct list **head, int id)
{
	struct list *temp;
 
	temp = *head;	/* 将链表的头部赋值给临时聊表变量 */
 
	while(temp)		/* 对链表进行轮询 */
	{
		if(id == temp->id)
		{
			printf("list %d : %s\n", temp->id, temp->data);
			return 0;
		}
		temp = temp->next;
	}
 
	/* 没有找到元素 */
	printf("not finding!\n");
	
	return -1;
}

附录: 单向链表基本操作的完整过程.

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-236242-1.html