C/C++丨结构(struct) and 链表(linked list)
第7章 结构and链表
注：本文参考中国铁道出版社《C语言程序设计（第三版）》书写
主要用于记录学习中的重点要点，欢迎指出错误
同时也欢迎交流学习～
7.1 结构类型(struct) and 结构变量
7.1.0 引入
解决实际应用问题时,常常需要这样一种数据对象进行处理
它们由 多项成员 组成,并且 各成员的数据类型 常不同
C语言引入了 结构类型 来对这类数据进行描述
然后通过 结构变量 (也称共用体) 来表示这样的数据
7.1.1 结构类型
1. 结构类型的定义方式
定义一个 结构类型 的一般形式:
struct 标识符
{
成员说明表
};
其中,关键字struct引出结构类型的定义,与 标识符 一起组成 结构类型的标记
花括号内部用于结构类型的 全体成员 的说明,指明该结构类型的各个成员的 数据类型 and 名称
每个成员变量的说明形式为:
类型 标识符;
2. 关于结构类型的补充
一个结构体可以有多个成员同一个结构体中的成员不可重名一个结构体的成员的类型可以为: 基本数据类型 and 数组 and 其他已经定义的结构类型不要忘记结构体定义最后要加上;C语言中struct 标识符才相当于结构类型的名称,单独的标识符不可以表示结构类型,除非采用typedef的方法
(在我的编译环境下测试属实,会显示"未定义的标识符"报错)
C++中在,在不会引起混淆(例如结构类型与结构变量同名)的情况下,引用结构类型可以不用struct来引导,建议采用C++的方法C++的结构体(or类)是支持成员函数的概念的,但是C中只能通过某些方法间接实现
3. 结构类型的一个实例
struct Date
{
int day ;
int month ;
int year ;
};
struct student
{
int number ;
char name[ 20 ] ;
char sex ;
Date birthday ;
char address[ 40 ] ;
};
上述代码段先定义了一个结构类型Date,再定义了一个结构类型
名为struct student,成员有number and name and sex and birthday and address 共5个
其中注意birthday的数据类型为结构类型Date,因而student是一个简单的嵌套的结构类型
这种嵌套结构再之后表示实际应用中为表达复杂的数据结构,会很常用
7.1.2 结构变量
1. 结构变量的概念
结构类型定义中,详细给出类型的每个成员的 名称 and 类型
但 结构类型定义 只是表明这样一个数据类型的"模式",并非一个实际的特定的 数据实体 ,因而其本身不要求分配存储单元
程序若要使用结构类型所描述的数据信息,必须先定义 结构变量
而 结构变量 作为一个实际的数据实体,是需要占据内存的来存储结构类型所描述的具体数据的
2. 对于结构变量的一些理解
结构类型 之于 结构变量 就相当于描述文本,而 结构变量 才能实际存储数据
可以理解为语言给出的 基础数据类型(例如int) 之于 变量 的关系
实际上在C++语法下,定义结构变量的方式也是很类似的
只不过结构类型要由基础数据类型构成,不是那么的"基础"
3. 结构变量的定义方式
定义结构变量的主要的两种的方式:
先定义结构类型,再声明结构变量
一般形式:
struct 结构类型名 标识符表; /* C语法 */
结构类型名 标志符表; /* C++语法 */
标识符表中每个标识符是对应结构变量的名称
每个结构变量的成员的 名称 and 个数 and 数据类型 均与结构类型定义中的一致
补充:
结构变量的内存占用等于结构定义中的各个成员所占的内存之和
在定义结构类型的同时定义结构变量
一般形式:
struct 标识符
{
成员说明表 ;
} 标识符表 ;
其中:
struct后的标识符 是结构类型的名称
标识符表中的标识符 是结构变量的名称
注:
此时struct后的标识符是允许略去的 (但相当于之后没法通过这个结构类型的名称来定义了,因此良好的编程习惯建议我们不要这么做!)
4. 结构变量的初始化
定义结构变量时还可以给它初始化,也就是给它赋上初值
此时,要按照结构类型定义中 成员的顺序 逐一给出各成员的初值
以下通过一个实例进行说明:
struct Point
{
int x ;
int y ;
} p1 = { 20 , 50 } , p2 ;
Point p3 = { 10 , 40 } , p4 ;
5. 关于以上内容的注意点
分辨 结构类型名 and 结构变量名
相当于分辨 int and int类型的变量
结构变量初始化的时间
存储类别 and 存储期 and 作用域 的相关在结构变量上同样适用
这告诫我们不要因为是结构变量就忘了初始化的重要性
可以为结构类型创建对应类型的指针
和基础数据类型是基本一致的
称其为指向结构的指针变量,简称 结构指针
定义形式与一般的指针也很像,例如以下实例:
Date *pd , date3 ; /*采用了C++的句法*/
pd = &date3 ;
不难理解,一个结构变量应该是占一整块连续的内存空间,而取地址符号取得就是这一块内存的首地址
7.1.3 结构变量的引用
结构被定义后,就可以引用该结构变量和结构的成员变量
1. 引用结构变量
两种方法:
结构变量名直接引用指向结构变量的指针间接引用
注:结构类型也可以作为函数的形参的类型
2. 引用结构成员
三种方法:
结构变量 and 成员运算符
一般形式:
结构变量名.成员名
点符号.就是结构的成员运算符,优先级最高的运算符之一
引用方式与一般的变量名基本一致,可以正常进行i/o and 赋值 and 运算 etc
结构指针 and 指针运算符
一般形式:
指针变量名->成员名
双字符->就是指针运算符,注意要紧密相连,优先级与.相同,也是最高优先级的运算符
结构指针 and 成员运算符
一般形式
(* 指针变量名).成员名
不难理解,就是正常解引用得到指针所指的结构变量,再把* 指针变量名当成一整个结构变量来用就对了
3. 引用 结构变量 or 结构成员 时的注意点
不可以直接对结构变量进行输入 or 输出,而只允许对结构成员变量进行输入 or 输出结构成员本身也是一个结构类型的变量,注意多次引用结构成员
7.2 结构数组
C程序设计中,一般用结构类型描述个体的信息结构,用数组表示个体的集合
当数据的元素是结构变量时,这种数组就称为 结构数组
7.2.1 结构数组的定义
有着与定义结构变量的方法类似的两种方法
就相当于在标识符之后再加[元素个数],构成一个结构数组
比较易于理解,此处从略
7.2.2 结构数组的引用
类似于引用结构成员,也有三种方式
都是类似的,同样从略
7.3 结构 and 函数
C语言中,结构也被允许作为函数的形参
将一个结构传递给函数有三种方式:传递单个成员 or 传递整个结构 or 传递指向结构的指针
传递 单个成员 or 整个结构 给函数仍然符合传非指针变量到函数的逻辑(形参与实参分离)
7.3.1 结构成员作为函数参数
与其他基本数据类型的传递方法相同
从略
7.3.2 结构作为函数参数
使用结构作为实参传递给一个函数,实际上将其所有的成员都传给了被调用函数的形参
注意:传结构实参到函数的形参,此形参可以了解为属于函数的局部变量
7.3.3 结构指针作为函数参数
C语言也支持指向结构的指针作为函数的形参,此时传入的实参时结构的地址或是指向结构的指针变量
值得注意的是,此方法的作用:除了可以修改结构实参的值之外,还可以减小调用函数时的结构形参的内存占用和传值计算开销,以减少系统开销且提高效率
7.3.4 上述三节的总结
对 结构 and 接构成员 and 结构指针 作为函数参数的相关总结:
结构 or 结构成员 作为函数参数是 值传递方式结构指针 作为函数参数是 地址传递方式,间接传入实参,并且提供了读写实参结构的方式
7.3.5 函数返回结构类型值
C语言中,结构类型值也被允许作为函数的返回值
此外完全可以与基础数据类型的用法类似,不多赘述
7.4 链表(linked list)
此处介绍链表的处理技术
主要内容：链表的概念 and 动态变量的生成与释放 and 链表的基本操作及程序设计方法
7.4.1 链表的概念
1. 链表的基本性质以及相关定义
链表的元素个数可按需任意增删
链表元素的后继元素也可以由元素中的成分指定，且可以更改
具有类似链表这样特性的数据结构称为动态数据结构
而链表则是最简单的动态数据结构
2. 链表的基础结构
单链表
一个"头指针"，一般以"head"称呼，指向链表的第一个表元
每个表元包含两部分：数据数据信息 and 指向后继表元的指针
不难理解，这种结构的链表只能知道后继元素的地址，而找不到前面的元素
直观来理解就是单向的，因此称为单链表
一般称链表的第1个表元为"首表元"，最后1个表元为"尾表元"
注意：
一般将 指向后继表元的指针 命名为"next"一个表元都无的链表为空链表，头指针指向NULL尾表元的next指针一般来说一定要记得指向NULL，否则容易出大问题(实际推荐每次创建新表元的时候都如此初始化)单链表的每个表元在内存中的存放位置是可以任意的
双链表
当我们要求链表的每一个表元都可以方便地知道它的 前驱表元 and 后继表元 时
不难理解的是，此时链表的每个表元需要包含两个指针：指向前驱表元的指针 and 指向后继表元的指针
此时插入表元也自然会比单链表上的操作更复杂一些
3. 链表 vs 数组
主要有以下几个方面的区别：
数组元素个数在定义时固定
链表表元为运行时程序动态地向程序申请的，可以增减数组的元素顺序关系由下标确定(顺序线性存储表，在内存中必须是相邻的一整块内存空间，更深层次的内容此处不多涉及)
链表表元的顺序关系由表元的指针成员实现在数组中插入或删除元素，需要移动部分元素的存储位置
在链表中 插入 or 删除 表元，不需要移动表元，只需要改变指针指向
7.4.2 动态变量
1. 基础概念 and 实例引入
动态数据结构中的数据对象是一种结构变量，包含一些成员存储信息 and 存储指针的成员
一般来说，比较简单的情况是结构包含指向与自己同类型结构的指针
实例：
struct intNode
{
int value ; /* 成员存储信息 */
inNode *next ; /* 存放后继表元的指针(C++风格定义方式) */
};
如上例子中有两个成员，分别为整形变量value and 指向结构类型intNode的指针变量next(此处也称自引用结构)
注：这种有成员引用自身的结构类型定义中，引用自身的成员只能是指针类型
2. 重要相关函数
动态数据结构中的变量称为 动态变量
动态变量可由程序调用库函数来来显式地随意 生成 and 释放
C语言中
主要使用 malloc() and calloc() 两个库函数用于生成动态变量
使用 free() 来释放动态变量
均在库 stdlib.h 中
malloc()
调用格式：
void *malloc( unsigned size )
功能解析：
向系统申请size个B的存储空间
如果成功，则返回所分配的连续空间的指针
若因动态存储区域内存余量不足，无法成功分配，则返回0(NULL)值
注意：
malloc()返回值为 void类型 的指针值，但是程序需要将该返回值强制转换为某种特定的指针类型一般将上述调用作为赋值运算符的右值，以赋值左变的指针变量动态变量没有标识符，因而只可以通过指针引用
calloc()
调用格式：
void *calloc(unsigned n ,unsigned size)
功能解析：
向系统申请n块size个B的存储空间
返回值的方式malloc()相同
注意：
calloc()除了比malloc()多一个参数外，还会给分配的空间完成清0的工作
相较而言malloc()则不会特别去做此步骤简单来讲，calloc()与malloc()的差别可以简化为申请多个 or 单个 动态变量的差别按照2中的理解方式，calloc（）所赋值的指针变量应该是指向该种动态变量数组的第一个元素，也就是说可以通过以前所了解的指针访数组的各种方式来访问这一串元素
free()
调用格式：
void free( void *ptr )
功能解析：
释放由ptr所指向的存储块
注意：ptr的值必须是malloc() or calloc() 被调用时的返回值，即动态申请内存得到的一块连续存储空间的指针
3. 单链表上的基础操作
主要包括：建立空的单链表 and 创建一个表元 and 遍历单链表 and 查找指定值的表元 and 向单链表插入一个表元 and 在单链表中删除一个表元 and etc
后续以以下实例开展说明：
struct stuS
{
int number ;
char name[ 20 ] ;
int score ;
stuS *next ;
};
stuS *head , *p , *p1 , *p2 ;
建立空链表创建一个表元遍历链表在链表中查找表元在链表中插入新表元从链表中删除表元
(未完待续)