《C和指针》读书笔记(第十二章 使用结构和指针)

这篇具有很好参考价值的文章主要介绍了《C和指针》读书笔记(第十二章 使用结构和指针)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

0 简介

纸上得来终觉浅,绝知此事要躬行。前几章学习了结构体、联合体和指针的相关知识。本章就是对这些知识的综合应用。

书中是以链表作为实例的,严格意义上来说,链表属于数据结构与算法的相关内容,关于这方面的知识,想学习的同学推荐《大话数据结构》这本书。书中的内容在通俗易懂的同时,又不乏严谨性。

链表,顾名思义,就是像铁链一样,环环相扣的表。链表是由节点 一个个连起来的,每个节点由两部分组成,分别是数据指向下一个节点的指针(数据可能不止一个,但是一般的教材和资料的举例中都是一个)。

比较遗憾的是,在本书中,仅仅给了链表的插入操作相关程序,但如果没有了链表的创建删除(非必需,但最好有)程序,书中的实例是无法运行的。因此,在我们本篇文章中,特意添加了其他所需的相关程序。

书中部分插图有误,请注意甄别。

本章内容提要:
《C和指针》读书笔记(第十二章 使用结构和指针),c语言,开发语言,数据结构

1 链表

如上所述,链表是一种数据结构,由一个个节点构成,通常节点是动态分配的,根据结构的不同,可分为单链表、双链表和环形链表等。本章重点介绍单链表和双链表。

2 单链表

在单链表中,每个节点包含一个指向链表下一个节点的指针。链表最后一个节点的指针字段为NULL,提示链表后面不再有其他节点。我们来看个单链表的示意图:
《C和指针》读书笔记(第十二章 使用结构和指针),c语言,开发语言,数据结构
root节点又叫根节点,链表就是基于此进行创建的。链表的创建分成两种,一种是头插法,一种是尾插法

2.1 在单链表中插入

链式的结构,使得链表在插入和删除新数据的时候比数组效率高很多(平均速度),所以链表的插入操作显得尤为重要。本章重点讲了单链表的插入操作。

2.1.1 初次尝试

标题取的不是很准确,更加准确地说,应该是在单链表中插入节点。我们将书中第一个版本的程序完善后,得到了如下的内容:

先定义节点,声明相关函数,所以定义.h文件如下:

#pragma once
typedef struct NODE {
	struct NODE *link;
	int value;
}Node;

int sll_insert(Node *current, int new_value);

然后定义插入函数,添加如下的.c文件

#include <stdlib.h>
#include <stdio.h>
#include "sll_node.h"
#define FALSE 0
#define TRUE 1
int sll_insert(Node *current, int new_value)
{
	Node *previous = (Node *)malloc(sizeof(Node));
	Node *new;
	while (current->value < new_value) 
	{
		previous = current;
		current = current->link;
	}
	new = (Node *)malloc(sizeof(Node));
	if (new == NULL)
		return FALSE;
	new->value = new_value;

	new->link = current;
	previous->link = new;

	return TRUE;
}

最后写主函数,添加如下的.c文件:

#include <stdlib.h>
#include <stdio.h>
#include "sll_node.h"
//单链表的整表创建
void CreateList(Node *L, int n, int *point)
{
	Node *p1, *r;
	int i;
	r = L;
	for (i = 0; i < n; i++)
	{
		p1 = (Node *)malloc(sizeof(Node));
		p1->value = point[i];
		r->link = p1;
		r = p1;
	}
	r->link = NULL;
}
//单链表的整表删除
void  ClearList(Node *L)
{
	Node *p, *q;
	p = L->link;
	while (p != NULL)
	{
		q = p->link;
		free(p);
		p = q;
	}
	L->link = NULL;
	printf("clear all\n");
}
int main()
{
	int ele[10];
	//链表数值设置
	for (int i = 0; i < 10; i++)
	{
		ele[i] = i * 5;
	}
	//定义根指针
	Node *p = (Node *)malloc(sizeof(Node));
	//定义第一个节点的指针
	Node *new_head = NULL;
	//创建链表
	printf("原始链表:\n");
	CreateList(p, 10, ele);
	//读取并打印链表
	new_head = p->link;

	while (new_head->link != NULL)
	{
		printf("%d->\t", new_head->value);
		new_head = new_head->link;
	}
	printf("%d", new_head->value);
	printf("\n");
	//插入值为8的节点
	sll_insert(p, 8);
	//再次读取并打印链表
	printf("插入节点后的链表:\n");
	new_head = p->link;
	while (new_head->link != NULL)
	{
		printf("%d->\t", new_head->value);
		new_head = new_head->link;
	}
	printf("%d", new_head->value);
	printf("\n");
	//删除整个链表
	ClearList(p);
	system("pause");
	return 0;
}

打印输出如下:
《C和指针》读书笔记(第十二章 使用结构和指针),c语言,开发语言,数据结构
可以看到,已经将节点插入到了所需的位置(位置由节点的值确定),看看节点的具体插入过程(为简便起见,只画出前三个节点)。

我们需要先找到正确的插入位置:

	while (current->value < new_value) 
	{
		previous = current;
		current = current->link;
	}

这部分代码很好理解,如果当前值比新值小,则继续前往下一个节点。如图所示:
《C和指针》读书笔记(第十二章 使用结构和指针),c语言,开发语言,数据结构
直到当前值大于或等于新值:
《C和指针》读书笔记(第十二章 使用结构和指针),c语言,开发语言,数据结构

然后我们再想办法插入新值:

	new->value = new_value;

	new->link = current;
	previous->link = new;

共分成3步:

  1. 将要插入的值赋给新创建的节点。
  2. 将新节点的指针指向当前节点。
  3. 前一个节点的指针指向新节点。

具体过程如下图所示:
《C和指针》读书笔记(第十二章 使用结构和指针),c语言,开发语言,数据结构
至此,链表的新节点插入完成。

2.1.2 优化插入函数

书中这里的优化指的是,若是将一个比第一个节点更小的值传入链表,则会导致程序无法运行,因为传入的是第一个节点。但我们并不存在这个问题,因为我们传入的是根节点。

仅仅有一个小小的地方需要优化,就是在寻找插入位置之前,更改保证当前指针不是空指针,否则不会存在value。 修改后的程序如下所示(仅展示修改部分):

	while (current != NULL && current->value < new_value)
	{
		previous = current;
		current = current->link;
	}

2.1.3 在指定位置插入节点(补充)

此外,还有一种插入方法,就是在指定的位置插入节点。实现起来也并不困难。

// 在指定位置插入节点
void sll_insertNode(Node** head, int data, int position) 
{
	if (*head == NULL || position <= 1) {
		// 如果链表为空或插入位置为头部,则直接在头部插入节点
		Node* newNode =  sll_createLinkedList(data);
		newNode->link = *head;
		*head = newNode;
	}
	else {
		// 否则在指定位置插入节点
		Node* temp = *head;
		int currentPosition = 1;

		while (currentPosition < position - 1 && temp->link != NULL) {
			temp = temp->link;
			currentPosition++;
		}

		if (currentPosition < position - 1) {
			printf("插入位置超出链表长度\n");
			return;
		}

		Node* newNode = sll_createLinkedList(data);
		newNode->link = temp->link;

		temp->link = newNode;
	}
}

2.2 其他链表操作

当然,对于链表本身而言,不仅仅只有插入操作,还包含了整个链表的创建删除。已经在上述代码中有所体现。

2.2.1 单链表的创建

单链表的创建有两种方法,分别是头插法尾插法。上述的例子中采用了尾插法,因为这样更符合我们的常规思维。

//单链表的整表创建
void CreateList(Node *L, int n, int *point)
{
	Node *p1, *r;
	int i;
	r = L;
	for (i = 0; i < n; i++)
	{
		p1 = (Node *)malloc(sizeof(Node));
		p1->value = point[i];
		r->link = p1;
		r = p1;
	}
	r->link = NULL;
}

链表的创建过程如下图所示(仅仅给出了前两个节点的创建过程,后面操作类似):
《C和指针》读书笔记(第十二章 使用结构和指针),c语言,开发语言,数据结构

2.2.2 单链表的删除

删除分成两部分,一部分是删除指定位置的节点,另一部分是删除整个链表,前者程序稍微难一些。

2.2.2.1 删除指定位置的节点

同在指定位置插入一样。删除前要先找到位置(当然是前一个节点的位置)。然后再将前一个节点的link指针绕过要删除的节点,直接跳到下一个节点,再删除当前节点,操作完成。

// 删除指定位置的节点
void sll_deleteNode(Node** head, int position)
{
	if (*head == NULL) {
		return;
	}

	Node* temp = *head;
	int currentPosition = 1;
	//找到该节点的前一个节点
	while (currentPosition < position - 1 && temp->link != NULL) {
		temp = temp->link;
		currentPosition++;
	}

	if (currentPosition < position - 1 || temp->link == NULL) {
		printf("删除位置超出链表长度\n");
		return;
	}
	//如果删除头节点,则该节点后移,否则无法访问该链表
	if (temp == *head) {
		*head = temp->link;
	}
	//获取当前节点指针,否则到时候无法获取
	Node* next_free = temp->link;
	//调整指针位置
	temp->link = temp->link->link;

	free(next_free);
}
2.2.2.2 删除整个链表

删除整个链表就很简单了,逐个访问下一个节点,并删除当前节点即可。

//单链表的整表删除
void sll_deleteLinkedList(Node** head)
{
	Node* current = *head;
	Node* next;

	while (current != NULL) {
		next = current->link;
		free(current);
		current = next;
	}

	*head = NULL;
}

3 双链表

单链表的替代方案就是双链表。在一个双链表中,每个节点都包含两个指针——指向前一个节点的指针指向后一个节点的指针。这可以使我们以任何方向遍历双链表,甚至可以忽前忽后地在双链表中访问。下图展示了一个双链表。
《C和指针》读书笔记(第十二章 使用结构和指针),c语言,开发语言,数据结构

3.1 在双链表中插入

3.1.1 按顺序插入

与单链表相比,双链表肯定要难一些,因为需要修改更多的指针。但其基本思想还是不变的,那就是先找需要插入的位置,然后将新节点插入。

先定义节点:

typedef struct NODE {
	struct NODE *fwd;
	struct NODE *bwd;
	int value;
}Node;

再定义插入函数,较之于单链表,双链表要复杂一些:

int dll_insert(Node *rootp, int value)
{
	Node *this;
	Node *next;
	Node *newnode;
	//查看value是否已经存在于链表中,如果是就返回
	//否则,为新值创建一个节点
	for (this = rootp; (next = this->fwd) != NULL; this = next)
	{
		if (next->value == value)
			return 0;
		if (next->value > value)
			break;
	}
	newnode = (Node *)malloc(sizeof(Node));
	if (newnode == NULL)
		return FALSE;
	newnode->value = value;
	//把新值添加到链表中
	if (next != NULL)
	{
		//情况1或2:并非位于链表尾部
		if (this != rootp)         /*情况1:并非位于链表的起始位置*/
		{
			newnode->fwd = next;
			this->fwd = newnode;
			newnode->bwd = this;
			next->bwd = newnode;
		}
		else                       /*情况2:位于链表的起始位置*/
		{
			newnode->fwd = next;
			rootp->fwd = newnode;
			newnode->bwd = NULL;
			next->bwd = newnode;
		}
	}
	else
	{
		//情况3或4:位于链表的尾部
		if (this != rootp)
		{
			newnode->fwd = NULL;
			this->fwd = newnode;
			newnode->bwd = this;
			rootp->bwd = newnode;
		}
		else
		{
			newnode->fwd = NULL;
			rootp->fwd = newnode;
			newnode->bwd = NULL;
			rootp->bwd = newnode;
		}
	}
	return TRUE;
}

最后是主函数的相关程序:

#include <stdlib.h>
#include <stdio.h>
#include "dll_node.h"
int main()
{
	Node* head = NULL;
	// 创建链表(只有头节点,值为0)
	head = dll_createLinkedList(0);

	//插入节点
	dll_insert(head, 5);
	dll_insert(head, 10);
	dll_insert(head, 15);
	dll_insert(head, 20);

	// 删除指定位置的节点
	dll_deleteNode(&head, 3);

	// 打印链表
	dll_printLinkedList(head);

	// 删除整个链表
	dll_deleteLinkedList(&head);
	system("pause");
	return 0;
}

参考单链表,多链表的程序便不难看懂。

另外还有链表的打印函数:

void dll_printLinkedList(Node* head) {
	Node* temp = head;
	while (temp != NULL) {
		printf("%d ", temp->value);
		if (temp->fwd != NULL)
			printf("->");
		temp = temp->fwd;
	}
}

打印输出:
《C和指针》读书笔记(第十二章 使用结构和指针),c语言,开发语言,数据结构
可以看到,在创建完链表之后,再插入需要的值,最后再将第三个值为10的节删除,就变成了上面的样子。

3.1.2 在指定位置插入节点(补充)

当然,如果想在指定位置插入节点也是可以的:

void dll_insertNode(Node** head, int data, int position) {
	if (*head == NULL || position <= 1) {
		// 如果链表为空或插入位置为头部,则直接在头部插入节点
		Node* newNode = createLinkedList(data);
		newNode->fwd = *head;
		if (*head != NULL) {
			(*head)->bwd = newNode;
		}
		*head = newNode;
	}
	else {
		// 否则在指定位置插入节点
		Node* temp = *head;
		int currentPosition = 1;

		while (currentPosition < position - 1 && temp->fwd != NULL) {
			temp = temp->fwd;
			currentPosition++;
		}

		if (currentPosition < position - 1) {
			printf("插入位置超出链表长度\n");
			return;
		}

		Node* newNode = createLinkedList(data);
		newNode->bwd = temp;
		newNode->fwd = temp->fwd;

		if (temp->fwd != NULL) {
			temp->fwd->bwd = newNode;
		}

		temp->fwd = newNode;
	}
}

3.2 其他链表操作

3.2.1 双链表的创建

与单链表类似,双链表也有相同的操作,比如整个链表的创建删除

链表的创建程序:

Node* dll_createLinkedList(int data) 
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	if (newNode == NULL) {
		printf("内存分配失败\n");
		exit(1);
	}
	newNode->value = data;
	newNode->bwd = NULL;
	newNode->fwd = NULL;
	return newNode;
}

程序比较好理解,分配一个节点的内存,并得到指向该节点的指针,赋初值,前后均无节点连接。

3.2.2 双链表的删除

3.2.2.1 删除指定位置的节点

对于双链表来说,由于一个节点同时涉及到两个指针,因此删除指定位置的节点相对来说比较难,具体如下。

// 删除指定位置的节点
void dll_deleteNode(Node** head, int position)
{
	if (*head == NULL) {
		return;
	}

	Node* temp = *head;
	int currentPosition = 1;

	while (currentPosition < position && temp != NULL) {
		temp = temp->fwd;
		currentPosition++;
	}

	if (currentPosition < position || temp == NULL) {
		printf("删除位置超出链表长度\n");
		return;
	}

	if (temp == *head) {
		*head = temp->fwd;
	}

	if (temp->bwd != NULL) {
		temp->bwd->fwd = temp->fwd;
	}

	if (temp->fwd != NULL) {
		temp->fwd->bwd = temp->bwd;
	}

	free(temp);
}

其中最重要的只有4行:

	if (temp->bwd != NULL) {
		temp->bwd->fwd = temp->fwd;
	}

	if (temp->fwd != NULL) {
		temp->fwd->bwd = temp->bwd;
	}

直接让需要删除的节点的前后节点可相互访问,然后再删除当前节点,删除结束。

3.2.2.2 删除整个链表

双链表的删除程序:

void deleteLinkedList(Node** head) 
{
	Node* current = *head;
	Node* next;

	while (current != NULL) {
		next = current->fwd;
		free(current);
		current = next;
	}

	*head = NULL;
}

删除函数也比较好理解,先找到下一个节点,再将当前节点内存释放。这个顺序是不能反的,否则释放完之后,无法获取下一个节点的指针,将导致删除失败。

在此程序中并不需要关注bwd指针,当我们释放当前节点内存后,其bwd指针自然也就没有了意义,存储该指针的内存被释放,可以存储其他信息。

4 总结

单链表是一种使用指针来存储值的数据结构。链表中的每个节点包含一个字段,用于指向链表的下一个节点。

双链表中的每个节点包含两个link字段:其中一个指向链表的下一个节点,另一个指向链表的前一个节点。

除此之外,常见的还有循环链表等数据结构,不过这些都不是很常见。掌握了链表的创建,删除,插入,查找方法(删除不难),就基本上掌握了本章的全部内容。

书中给的链表插入操作是按照顺序插入,而在很多实际案例中,都是按照预先规定的位置插入节点的。这里会有一些差别。而在本文中,两种方法都分别进行了阐述。

---------------------------------------end---------------------------------------文章来源地址https://www.toymoban.com/news/detail-654505.html

到了这里,关于《C和指针》读书笔记(第十二章 使用结构和指针)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 第十二章 外观模式

    `

    2023年04月25日
    浏览(40)
  • 第十二章:泛型(Generic)

    目录 12.1:为什么要有泛型? 12.2:在集合中使用泛型 12.3:自定义泛型结构 12.4:泛型在继承上的体现 12.5:通配符的使用 12.1:为什么要有泛型?         泛型:(标签)允许在定义类、接口时候通过一个标识来表示类中某个属性的类型或者是某个方法的返回值及参数类

    2024年02月07日
    浏览(40)
  • 第十二章 elk

    1、ELK可以帮助我们解决哪些问题 日志分布在多台不同的服务器上,业务一旦出现故障,需要一台台查看日志 单个日志文件巨大,无法使用常用的文本工具分析,检索困难; 2、架构设计分析 Filebeat和Logstash ELK架构中使用 Logstash收集、解析日志 ,但是Logstash对 内存、cpu、io等资

    2024年02月13日
    浏览(33)
  • 第十二章 sys模块

    什么是Python 解释器 当编写Python 代码时,通常都会得到一个包含Python 代码的以.py 为扩展名的文件。要运行编写的代码,就需要使用Python 解释器去执行.py 文件。因此,Python 解释器就是用来执行Python 代码的一种工具。常见的Python 解释器有以下几种: CPython:Python 的官方解释器

    2024年02月09日
    浏览(41)
  • 【vue2第十二章】ref和$refs获取dom元素 和 vue异步更新与$nextTick使用

    为什么会有 ref 和 $refs? 因为在vue页面中使用dom查找元素,不管你是不是在子组件里面查找,查找的都是整个页面的元素,如果你想查找单独组件里面的元素是不容易实现的,除非把每个组件的class写成独一无二,但是在日常开发中,一个vue页面不知道会有多少组件,所以出

    2024年02月09日
    浏览(41)
  • python 第十二章 面向对象

    第一章 初识python 第二章 变量 第三章 基础语句 第四章 字符串str 第五章 列表list [] 第六章 元组tuple ( ) 第七章 字典dict {} 第八章 集合set {} 第九章 常用操作 第十章 函数 第十一章 文件操作 理解面向对象 面向对象是一种抽象化的编程思想,很多编程语言中都有的一种思想。

    2024年02月13日
    浏览(47)
  • 【OpenCV】第十二章: 图像轮廓

    第十二章: 图像轮廓 图像边缘和图像轮廓的区别 前面我们在图像形态学操作里,用cv2.morphologyEx()这个函数实现图像梯度的提取,就是用膨胀图像-腐蚀图像,获取一个图像中前景图像的边缘。还有我们的礼帽黑帽一定程度也能提取图像的边缘信息。 我们还在图像梯度里面详细

    2024年02月04日
    浏览(61)
  • 第十二章 Transform组件(下)

    上一章节中我们介绍了Transform组件的属性和方法。我们发现 Transform 中有right,up和forward,而 Vector3 类中也有right,up和forward,他们是一回事嘛?我们使用Forward来说明两者之间的区别。我们知道,改变游戏对象的position位置,就可以形成移动效果。如果我们让游戏对象沿着for

    2024年02月01日
    浏览(35)
  • 11.第十二章.采购管理

    1、基于组织的经营目标和经营政策展开项目采购相应的运营活动,包括采购战略合作管理、釆购过程管理、采购管理技术和工具等3个方面。 2、企业仅依靠自身无力应对激烈的竞争。因此,必须摈弃“以企业为中心”的传统管理模式,代之以现代战略合作的管理模式。战略合

    2024年02月04日
    浏览(37)
  • C国演义 [第十二章]

    力扣链接 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 给定一个代表每个房屋存放金额的非负整数数组,计算你

    2024年02月17日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包