我们知道,链表是一种经典的数据结构,在很多地方都会使用到.而链表中最基础且经典的就是但链表和双链表了.今天总结一下链表在c语言中的实现.
- 链表的出现
我们知道,在c语言中,有基本数据类型,自定义类型和数组..其中数组用来存储同类型数据的集合.但是数组确是十分不方便的,数组的大小在定义时要事先给出.编译系统会更具数组元素类型和数组元素的大小静态的分配一片连续的内存空间.这片内存空间却不能在程序执行过程中进行调整.所以我们常常以最大需求来定义数组.这样会导致内存空间的浪费或空间不足的尴尬.
所以,为了达到动态内存分配的目的,存储同种类型数据的集合.链表的形式出现了.链表将连续的和非连续的内存空间联系起来(指针域或者地址域).基本思路就是:在存放当前数据的时候,顺便存储下一条数据的首地址这样就实现了将各个不连续的数据串成"链".如此,就可实现把不同的数据存放在非连续或者连续的内存区域.
-
单链表
正如链表的概念:
单链表的每个数据由两部分组成,数据域以及指针域(地址域),数据域用来存放各种数据,指针域用来指向下一条数据.当然,一张单链表必须具备一个头指针才能让我们找到他们,所以通常的,我们都会为链表添加一个头指针来指向链表的开始,也就是头结点.头指针抛去了数据域,只存放头指针的地址,只是起到指向的作用,这一点,在数组,字符数组中就有体现,他们在c语言中的读取与操作都是通过其首地址实现的.我们在使用调试的时候就会发现,他们的首个数据是带有一个地址信息的.
c语言中链表是用结构体来实现的.我们知道,c语言不像高级语言,不支持面向对象,可以自定义类和对象,而是直接通过结构体来定义自定义类型,C语言通过这种方式来描述众多的复杂类型数据.解决实际问题的.
- 单链表的定义:
我们知道c语言中是使用指针变量来存放一种类型数据的首地址的,所以这里单链表的结构体定义,有点类似与递归的定义,在结构体中定义一个结构体指针变量,来指向下一个结构体指针的首地址.
// 定义学生结构体
struct Student
{
char id[20]; //id
char name[20]; //姓名
char sex[3]; // 性别
int age; // 年纪
int Grade; // 成绩
};
// 定义一个学生单链表类型,当然数据域你也可以不嵌套结构体直接写也没有问题.
struct StuLinklist
{
Student student; //数据域
StuLinklist* next; // 指针域
};
- 双链表
很容易理解,根据链表的概念,我们可以看出单链表与双链表的最根本的区别就是,双链表使用了两个指针域分别用来指向了前一个数据,和后一个数据.双链表的出现是显而易见的.使用单链表的时候,我们只能向下索取,而不能向上索取,只能通过循环遍历来获取对应位置的数据,这无疑是十分不方便的,所以双链表出现了.这使得我们在操作一个双链表数据的时候非常的方便.
- 双链表的定义:
相同的,我们只需要在结构体中多声明一个结构体指针指向上一个结构体数据就可以了.
// 双链表
struct Humanity
{
// 数据域
char name[20];
int age;
char sex;
// 指针域
Humanity* previous;
Humanity* nxet;
};
当然,这里只是简单的了解下双链表,比较在使用上还是单链表较为常用.特别对于c语言来说,初学链表.以单链表为切入点,更加容易.也能够提高你对双链表的理解.毕竟它们原理类似.
在本章,只结合结构体,单链表,文件读取,总结下单链表在c语言中的使用,和单链表结合文件存取的使用.如何将链表式数据保存到文件中,如何从文件中读取单链表数据.基于这几点,了解通透了的话,基本就可以解决绝大部分基于文件操作的控制台信息管理系统的程序设计了.
- 单链表的使用
单链表的使用最基本,最常用的无非就是初始化,增删改查,求表长,销毁等操作.
需要注意的是单链表的单向访问性,注定了对单链表子节点的访问必须从头开始.
- 初始化
相当于创建一个空节点(数据域为空,指针域也为空).
// 创建一个空节点
StuLinklist* mcreate(){
// 创建一个单链表节点.
StuLinklist* H = (StuLinklist*)malloc(sizeof(StuLinklist));
if (!H)
{
printf("创建失败");
getchar();
exit(0);
}
else { // 初始化
H->next = NULL;
}
return H;
}
初始化了一个带头指针(H)的空的头结点.
- 插入
我们根据单链表的性质.插入只需要三步,创建一个新节点.将插入前一个节点指向新节点,将新节点的指针域指向后一个节点.
// 在第i个位置插入一个新的节点
bool minsert(StuLinklist* p, int i,Student stu){
int j = 0;
// 定义temp指针变量循环遍历指针,初始化为被插入链表p.
StuLinklist* temp=p;
//循环遍历找到i-1的位置
while (temp && j<i-1)
{
temp = temp->next;
j++;
}
// 判断i为空或i<1(i=0)
if (!temp || j>i-1)
{
return 0; // 插入失败
}
else {
// 创建一个新节点
StuLinklist* s = mcreate();
// 更新数据域为传入的stu
s->student = stu;
// 更改节点的指针域插入节点s
s->next = temp->next;
temp->next = s;
return 1; //插入成功
}
}
- 删除第i个节点
道理和插入是相同的,指针域的更改不同,并且要释放掉内存空间而已:
// 删除第i个位置上的节点,且暂时保存其中的数据.
bool mdeletelist(StuLinklist* p, int i, Student* stu) {
int j = 0;
// 定义temp指针变量循环遍历指针,初始化为被插入链表p.
StuLinklist* temp = p;
//循环遍历找到i的位置
while (temp->next && j < i-1)
{
temp = temp->next;
j++;
}
// 判断i为空或i<1(i=0)
if (!temp || j > i - 1)
{
return 0; // 插入失败
}
else {
// 创建一个新节点
StuLinklist* s = mcreate();
// 使s指向第i个位置(要删除的位置)
s = temp->next;
//用stu参数暂时保存即将删除的数据.
*stu = s->student;
//让temp.next指向i后面的一位.
temp->next = s->next;
//删除节点,释放掉s指向的第i个位置的节点空间
free(s);
return 1; //删除成功
}
}
- 遍历输出和获取链表长度
通过插入和删除,我们明白了链表的核心,就是遍历.我们对链表的操作基本都是基于遍历的基础之上的.
// 遍历链表输出
void printlist(StuLinklist* p) {
StuLinklist* temp;
temp = p;
while (temp)
{
Student s = temp->student;
printf("%s%s%s%d%d\n", s.id, s.name, s.sex, s.age, s.Grade);
temp = temp->next;
}
}
// 遍历获取链表长度
int mgetlength(StuLinklist* p) {
int j = 0;
StuLinklist* temp=p;
while (temp)
{
temp = temp->next;
j++;
}
return j;
}
当然,如果你想把功能写全,还可以设计查找函数,匹配函数.等等.这些同样,都是基于链表的遍历的.只要你理解了链表的遍历,相信这些函数你都可以很轻松的实现.
- 向指定文件中写入数据块
文件读写的详细操作和原理,流程.都将在另一篇中进行总结.本篇只总结其中两种最常用的,基于数据块(也就是结构体,数组,等)两种读写方式:
- 写入数据块: fwrite函数
/*
r只读(打开),r+读写(不存在返回空,读写从头开始,写时覆盖).
w只写(打开或建立文件,内容全部消失).w+读写(打开或新建,读写可以通过位置函数定义)
a追加数据.(打开或新建),a+(读写,位置可以定义) 以上都对文本文件进行操作.
rb,rb+,wb,wb+,ab,ab+都是对二进制文件操作.
*/
//结构体写入文件:fwrite.
bool mwritefile(const char* file,StuLinklist* p) {
// 声明一个文件指针
FILE* fp;
// 二进制文件追加的方式打开文件.
fopen_s(&fp,file,"ab");
if (!p)
{
return 0; //写入失败.
}
else{
fwrite(p,sizeof(StuLinklist),1,fp);
fclose(fp); // 关闭文件流
return 1;
}
}
- 读取数据块:fread函数
// 结构体读取文件:fread
bool mreadfile(const char* file, StuLinklist* p) {
// 声明一个文件指针
FILE* fp;
// 二进制文件追加的方式打开文件.
fopen_s(&fp, file, "rb");
if (!p)
{
return 0; //读取失败.
}
else {
fread(p, sizeof(StuLinklist), 1, fp);
fclose(fp); // 关闭文件流
return 1; // 读取成功
}
}
主函数:
int main()
{
// 初始化一个学生
Student student = {
"1001","小明","男",14,87
};
// 创建并初始化一个空节点(其实就是为p分配内存空间)
StuLinklist* p = mcreate();
// 将变量student赋值给空节点.
p->student = student;
//定义一个新的空学生.初始化为p节点的student
Student student2 = p->student;
// 尝试直接输出student
// printf("%s%s%c%d%d\n", p->student); 错误,嵌套的坏处也就意味着不能直接访问嵌套结构体里的成员了.
printf("%s%s%s%d%d\n", student2.id, student2.name, student2.sex, student2.age, student2.Grade);
//-------//
// 初始化第三个学生.
Student student3 = {
"1001","小王","女",13,89
};
if (minsert(p,1,student3)){
printf("插入成功");
}
else {
printf("插入失败");
}
// 遍历输出链表
printlist(p);
// 声明一个student用来暂存删除节点的数据
Student stu2;
// 删除一个节点,再次遍历输出
mdeletelist(p, 1,&stu2);
printlist(p);
// 输出暂存的stu2
printf("%s%s%s%d%d\n", stu2.id, stu2.name, stu2.sex, stu2.age, stu2.Grade);
// 获取链表长度
printf("%d",mgetlength(p));
// -------------//
// 声明读写文件的位置
const char* file = "linktest.bin";
// 写入文件
if (mwritefile(file, p)) {
printf("写入成功");
}
else {
printf("写入失败");
}
// 声明一个单链表变量
StuLinklist s;
Student st;
// 读取文件
if (mreadfile(file,&s))
{
printf("读取成功");
st = s.student;
printf("%s%s%s%d%d\n", st.id, st.name, st.sex, st.age, st.Grade);
}
else {
printf("读取失败");
}
}
结果:
2019.12.25
16:00
