单链表的C/C++实现方法——面向对象思想
参考视频:
https://www.bilibili.com/video/av73844865?from=search&seid=14703049787269972364
本文是学习了上面的视频总结而成。C代码参考实现,C++代码自主实现。
20200309 seafire
一个比喻
链表在内存中并不一定连续。他由多个节点组成,节点内部存储有数据,节点之间通过某种关系连接起来,从而组成了链表。
基于此,我们可以做个类比:
待存储的数据 –> 行李
节点 –> 火车车厢。既可以存放行李,也可以通过钩锁将各节车厢联系起来
链表 –> 火车控制室。要了解整个火车的情况,只需要知道火车头、火车尾,以及火车车厢的数目即可(甚至只要火车头就足够了。为了算法实现简洁,增加火车尾、火车车厢数目有时候可以在不遍历的情况下得到结果,在后面的代码中可以看到)。中间的火车车厢,都可以根据其他车厢推导出来
数据结构
从上面的比喻可以看出,要实现链表,基本的数据结构需要定义三种:
数据(行李)
节点(火车车厢)
链表(火车控制室)
实现上述三种对象以及操作他们的函数,就完成了链表的编写。这就是面向对象的思想。
C语言实现
C语言虽然一般认为是面向过程的语言,但是完成可以实现面向对象的代码。但是,受限于语言本身的特性,需要使用多级指针,因此代码理解起来有一定的难度。
为了代码清晰易懂,以及复用性方便,我们拆分出了多个文件。
数据
//data.h
#pragma once
//数据(行李)
struct Data{
int x;
int y;
char ch;
};
//函数声明:返回一个Data类型的值
struct Data creatData(int m, int n, int ch);
//data.c
#include "data.h"
//实现data.h中声明的函数,返回相应的值
struct Data creatData(int m, int n, int ch){
struct Data data;
data.x = m;
data.y = n;
data.ch = ch;
return data;
}
节点
//node.h
#pragma once
#include "data.h"
struct