单链表的实现【02】:Student-Management-System

一、问题引入

单链表的实现【01】:Student-Management-System 只体现了项目功能实现,未对代码部分做出说明。
故新增随笔进行补充说明代码部分。

重构代码,迭代版本:Student Mangement System(Version 2.0)

二、解决过程

基于单链表实现就离不开链表的几个重要概念:头结点、首元结点、头指针

2-1 链表概念

线性表链式存储结构的特点是:用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。
根据链表结点所含指针个数、指针指向和指针连接方式,可将链表分为单链表、循环链表、双向链表、二叉链表、十字链表、邻接表、邻接多重表等

本随笔基于单链表实现,这里重点介绍它。

? 不带附加结点(即头结点)的单链表
单链表的实现【02】:Student-Management-System

? 带附加结点(即头结点)的单链表
单链表的实现【02】:Student-Management-System

  • 首元结点:指链表中存储第一个数据元素a1的结点

  • 头结点:在首元结点之前附设的一个结点,其指针域指向首元结点

  • 头指针:指向链表中第一个结点的指针

    若链表设有头结点,则头指针所指结点为线性表的头结点;

    若链表不设头结点,则头指针所指结点为该线性表的首元结点

单链表的实现【02】:Student-Management-System

? 链表增加头结点的作用如下:

(1)便于首元结点的处理增加了头结点后,首元结点的地址保存在头结点(即其“前驱” 结点)的指针域中,则对链表的第一个数据元素的操作与其他数据元素相同,无需进行特殊处理。

(2)便于空表和非空表的统一处理当链表不设头结点时,假设L 为单链表的头指针,它应该指向首元结点,则当单链表为长度n 为0 的空表时, L 指针为空(判定空表的条件可记为:L== NULL)。

? 为了提高程序的可读性,在此对同一结构体指针类型起了两个名称,LinkList 与LNode* , 两者本质上是等价的。通常习惯上用LinkList 定义单链表,强调定义的是某个单链表的头指针;用LNode *定义指向单链表中任意结点的指针变量

2-2 链表实现

  • 结构体定义
#define ERROR -1     // 错误
#define OK 0         // 成功
#define OVERFLOW -2  // 溢出

#define TRUE 1       // 真
#define FALSE 0      // 假

typedef struct
{
	char stu_name[10];     // 学生姓名
	char stu_sex[10];      // 学生性别
	int  stu_age;          // 学生年龄
	int  stu_id;           // 学生学号
}Student_T;

typedef Student_T ElemType;

typedef struct LNode_T
{
	ElemType data;         // 结点数据域
	struct LNode_T *next;  // 结点指针域
}LNode_T, *LinkList_T;     //LinkList_T 为指向结构体LNode_T的指针类型
  • 单链表的初始化
int list_init(LinkList_T *L)
{
	// 构造一个空的单链表
	// 生成新结点作为头结点,用头指针*L(即单链表L)指向头结点
	*L = (LNode_T *)malloc(sizeof(LNode_T));
	if (NULL == *L)
		exit(OVERFLOW);
	memset(*L, 0, sizeof(LNode_T));
	(*L)->next = NULL;
	return OK;
}
  • 单链表的销毁
int list_destory(LinkList_T *L)
{
	// 释放所有结点(包括头结点)空间
	LNode_T *temp;
	while (*L)
	{
		temp = *L;
		*L = (*L)->next;
		free(temp);
	}
	return OK;
}
  • 单链表的查找(匹配学号查找结点)
LNode_T * list_locate(LinkList_T L, int stu_id)
{
	// p指向首元结点
	LNode_T *p = L->next;
	LNode_T *q = NULL;
	while (p != NULL)
	{
		if (stu_id == p->data.stu_id)
		{
			q = p;
			break;
		}
		p = p->next;
	}
	return q;
}
  • 单链表的结点更新
int list_update(LinkList_T L, int stu_id, const char *stu_name)
{
	int result = ERROR;
	LNode_T *p_node = list_locate(L, stu_id);
	if (NULL != p_node)
	{
		strcpy(p_node->data.stu_name, stu_name);
		result = OK;
	}
	return result;
}
  • 单链表的删除(匹配学号删除结点)
int list_delete(LinkList_T *L, int stu_id)
{
	// p指向头结点
	LNode_T *p;
	LNode_T *q;
	int is_found = ERROR;
	for (q = NULL, p = *L; p != NULL; q = p, p = p->next)
	{
		if (stu_id == p->data.stu_id)
		{
			q->next = p->next;
			free(p);
			is_found = OK;
			break;
		}
	}
	return is_found;
}
  • 创建单链表(尾插法)
int list_create_r(LinkList_T *L, ElemType elem)
{
	// r指向头结点
	LNode_T *r = (*L);
	while (r->next != NULL)
	{
		r = r->next;
	}
	LNode_T *p = (LNode_T *)malloc(sizeof(LNode_T));
	p->data = elem;
	p->next = NULL;
	r->next = p;
	return OK;
  • 单链表的遍历
int list_traverse(LinkList_T L)
{
	// p指向首元结点
	LNode_T *p;
	for (p = L->next; p != NULL; p = p->next)
	{
		printf("%d %s %s %d\n", p->data.stu_id, p->data.stu_name,
			p->data.stu_sex, p->data.stu_age);
	}
	return OK;
}

三、反思总结

单链表的实现过程,需要考虑是否附加头结点,有头结点和没有头结点的实现会有所不同

单链表的操作可以独立封装,根据具体的应用场景可以进行二次封装

四、参考引用

数据结构第二版:C语言版 【严蔚敏】 第二章 线性表(链表)

原文链接:https://www.cnblogs.com/caojun97/p/17268928.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:单链表的实现【02】:Student-Management-System - Python技术站

(0)
上一篇 2023年4月18日
下一篇 2023年4月18日

相关文章

  • C4D怎么建模三维立体的摩天轮?

    当我们要建模三维立体的摩天轮时,通常需要经过以下步骤: 步骤一:创建摩天轮主体的外形 这个步骤可以用多边形建模实现。我们可以先创建轮廓线,然后再为其赋予一个融合体(Extrude)属性来进行外形建模。这里我们用一个圆形作为轮廓线的基础。具体步骤如下: 打开C4D,再打开新建一个工程。 将“多边形建模”界面的开关打开。(然后,将视图模式切换至左视图模式) 将圆…

    C 2023年5月22日
    00
  • C++基本算法思想之递推算法思想

    C++基本算法思想之递推算法思想 什么是递推算法 递推算法又称为递归算法,是常用于求解问题的一种算法思想。它通过求出问题的一个基本情况,然后通过逐步迭代、递推,从而得到问题的一个规模更大的解。通俗的说,就是将一个大问题分解成多个相对较小的问题,通过依次解决每个小问题最终得到大问题的解。 如何实现递推算法 递推算法可以通过编写递归代码进行实现,也可以通过循环实…

    C 2023年5月22日
    00
  • 详解C语言中sizeof如何在自定义函数中正常工作

    当在C语言中定义一个结构体或是自定义的类型时,可以使用sizeof关键字来计算该类型所占的字节数。但是,在自定义函数中使用sizeof有些时候可能不会正常工作,这是由于sizeof是在编译时计算的,而不是运行时计算的。 为了解决这个问题,我们可以使用指针来传递数据。我们可以将指针的大小视为常量,这样在编译时就可以正确计算大小。下面,我来详细讲解在自定义函数中…

    C 2023年5月23日
    00
  • C++高精度算法的使用场景详解

    C++高精度算法的使用场景详解 什么是高精度算法 高精度算法是指一种可以处理大数的算法。它是在计算机科学领域中的一种重要算法,可以解决一些需要精度极高的问题,如加密等。在 C++ 中,我们可以使用字符串来表示大数,然后通过基本的字符串操作实现高精度运算。 使用场景 高精度算法适用于处理数据量较大的问题,如以下场景: 1. 大数运算 在普通算法中,如果数据太大…

    C 2023年5月22日
    00
  • C++智能指针模板应用详细介绍

    C++智能指针模板应用详细介绍 智能指针的概念 在C++中,当我们使用new创建了一个对象时,需要手动的调用delete来释放内存。但是,如果在某个地方忘记释放内存,就会导致内存泄漏问题。为了避免这个问题,我们可以使用智能指针来管理内存。 一个智能指针是一个类,它行为像一个指针,但它还额外提供了内存管理的功能。智能指针类会通过在构造函数中调用new和在析构函…

    C 2023年5月22日
    00
  • C 程序 查找数组元素的总和

    C程序 查找数组元素的总和 简介 本程序通过输入一个包含n个数的整型数组,求出数组中所有元素的总和。 使用攻略 编译环境 本程序使用C语言编写,建议使用gcc编译器,在Linux环境下执行。 输入数组 程序使用scanf函数从标准输入中读入数组元素,用户需输入n个整型数值,以空格或换行符分隔。 示例输入: 5 1 2 3 4 5 程序设计 本程序使用for循…

    C 2023年5月9日
    00
  • C语言中程序如何调用Python脚本

    在C语言中,我们可以通过调用Python解释器来执行Python脚本。实现这个功能需要使用到Python标准库中的Python.h头文件和相关函数。 下面是完整的攻略,包含两个实例: 1. 准备Python解释器 在C语言中调用Python脚本之前,我们需要先准备好Python解释器。具体步骤如下: 安装Python解释器 首先我们需要安装Python解释器…

    C 2023年5月23日
    00
  • Python基础之面向对象进阶详解

    Python基础之面向对象进阶详解攻略 概述 面向对象编程是 Python 编程中重要的支柱之一。Python 中的一切都是对象,如字符串,列表,元组等等都是对象,并且这些对象可以通过面向对象编程方式进行扩展和操作。本文将详细讲解 Python 面向对象编程的高级概念和技术。 面向对象编程基础 在掌握 Python 面向对象进阶概念之前,需要对 Python…

    C 2023年5月23日
    00
合作推广
合作推广
分享本页
返回顶部