[笔记]指针与单向链表
前言:妈的老子终于写到链表来了!!!!进入数据结构了!!!卧槽我好想快点写完然后写Linux啊!!!!此文引用了CSDN的部分文章,进行整理,侵权立删
本文重点,请认真阅读!
为什么要使用链表
在未学习链表时,我们常用的存储数据的方式无非就是数组。使用数组存储数据的好处就是查询快,但是它的弊端也很明显:
- 使用前需声明数组的长度,一旦声明长度就不能更改
- 插入和删除操作需要移动大量的数组元素,效率慢
- 只能存储一种类型的数据.
而链表则可以实现以上这些数组所不具备的功能,此时引入了结构体来实现创建链表的操作。
链表的特点:
- n个节点离散分配
- 每一个节点之间通过指针相连
- 每一个节点有一个前驱节点和一个后继节点
- 首节点没有前驱节点,尾节点没有后继节点
首先先定义一个简单的结构体
struct link
{
int data;//声明数据域
struct link* p; //定义指针域,存储直接后继的节点信息
};
数据域的内容可以自己指定,指针域用来存放下一个节点的地址。
单向链表:只能单方向进行(补充笔记)
首节点:存放第一个有效数据的节点
头节点:在单链表的第一个结点之前附设一个结点,它没有直接前驱,称之为头结点,头结点的数据域可以不存储任何信息,指针域指向第一个节点(首节点)的地址。头结点的作用是使所有链表(包括空表)的头指针非空
头指针:指向头节点的指针
尾节点:存放最后一个有效数据的节点
尾指针:指向尾节点的指针
这张图可以全部说明单向链表惹
其实在咱们学习结构体自引用的时候就接触到了链表 ,只不过在自引用的同时多出了头指针。在等待用户输入值前,头指针指向空,待用户输入值后,头指针指向该节点,判断该结点的指针域是否还有数据,若为NULL,则将它设为尾结点。
每一次的添加数据,指针都将在堆内申请一片对应结构体的内存空间,将此次存储的值存入此内存空间内,由于在堆内,程序结束之前,不释放会会一直存在,在增改删查里边就很好理解了:利用循环遍历链表,实现不同的操作
结构体一般为全局变量类型,因为在实现不同功能的时候,都需要调用它,结构体分为数据域和指针域两个区域,利用指针申请节点
当类型名过长时,一般使用typedef为结构体创建别名,方便调用
还是利用代码讲解通俗易懂:
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<string.h>
/*------------声明功能函数----------------*/
void insere_func(void);
void sort_func(void);
void delete_func(void);
void display_func(void);
void modify_func(void);
void anykey_func(void);
/*-----------创建结构体与链表节点----------*/
struct student
{
char name[20];
int score;
struct student* next;
};
struct student* ptr,
* head,
* current,
* prev;
/*---------------定义主函数----------------*/
int main()
{
char option1;
/*定义头指针,头指针指针域指向NULL*/
head = (struct student*)malloc(sizeof(struct student));
head->next = NULL;
/*创建一个死循环*/
while (1)
{
printf("\n");
printf("***********************\n");
printf("1.插入\n");
printf("2.删除\n");
printf("3.查看\n");
printf("4.修改\n");
printf("5.退出\n");
printf("***********************\n");
printf("请输入序号后按下回车");
option1 = _getche();
switch (option1)
{
case '1':
insere_func();
break;
case '2':
delete_func();
break;
case '3':
display_func();
break;
case '4':
modify_func();
break;
case '5':
printf("欢迎使用\n");
return 0;
}
}
}
/*---------------定义功能函数-------------------*/
/*添加是以分数的高低加以排序*/
void insere_func(void)
{
char s_temp[4];
ptr = (struct student*)malloc(sizeof(struct student));
printf("\n");
printf("Student name:");
gets(ptr->name);
printf("Student score:");
gets(s_temp);
ptr->score = atoi(s_temp);
prev = head;
current = head->next;
while ((current != NULL) && (current->score>ptr->score))
{
prev = current;
current = current->next;
}
ptr->next = current;
prev->next = ptr;
printf("添加成功\n");
}
void delete_func(void)
{
char del_name[20], ans;
printf("删除学生姓名:");
gets(del_name);
prev = head;
current = head->next;
while ((current != NULL) && (strcmp(current->name, del_name) != 0))
{
prev = current;
current = current->next;
}
if (current != NULL)
{
printf("是否确定删除(Y/N)");
ans =_getche();
if (ans == 'Y' || ans == 'y')
{
prev->next = current->next;
free(current);
}
}
else
{
printf("没找到关于%s的信息", del_name);
}
}
void modify_func(void)
{
char n_temp[20], s_temp[4];
printf("需要调整的学生姓名:");
gets(n_temp);
current = head->next;
while ((current != NULL) && (strcmp(current->name, n_temp)) != 0)
{
prev = current;
current = current->next;
}
if (current != NULL)
{
printf("\n");
printf("\n*****************************\n");
printf("学生姓名:%s\n", current->name);
printf("学生分数:%d\n", current->score);
printf("\n*****************************\n");
printf("请输出新的分数:%d");
gets(s_temp);
current->score = atoi(s_temp);
printf("修改后:\n");
printf("学生姓名:%s\n", current->name);
printf("学生分数:%d\n", current->score);
}
else
{
printf("未找到学生信息\n");
}
}
void display_func(void)
{
int count = 0;
if (head->next == NULL)
{
printf("没有记录学生");
}
else
{
printf("\n");
printf("\tNAME\tSCORE\n");
printf("-------------------\n");
current = head->next;
while (current != NULL)
{
printf("\t%-10s\t%3d\n", current->name,current->score);
count++;
current = current->next;
if (count % 20 == 0)
{
_getch();
}
}
printf("-------------------\n");
printf("总共找到%d条学生记录", count);
}
}
代码较长,我们一个函数一个函数的讲,头文件和函数前置声明就不做剖析了
程序定义了一个结构体:
- 结构体类型为student(数据域)
- name为成员,char数组类型(数据域)
- socre为成员,int类型(数据域)
- next为结构体自引用,为结构体指针类型(指针域)
随后结构体又定义了四个指针变量:看图
我们给这四个指针做一个功能的分析:
- ptr:用于创建新的节点
- head:用于指向头结点
- current:用于操作下一个节点
- prev:用于操作当前节点
进入正题:
option1用于输入字符,选择功能调用函数,这个不做详细讲解
重点到它为head分配了一片student结构体的内存,并且将head的指针域指向为NULL,这时head指向的这片区域形成头结点
这时程序中抽象为图
当我们输入1时,执行insere_func();函数,这个函数是个无返回值,无参数的函数,只能用于实现功能!我们继续剖析这个函数:
我们先看函数前部分,这儿定义了一个char类型的数组s_temp咱们不管它,输入字符用的
第一次:
重点到ptr,这儿它为ptr申请了一段结构体指针类型的内存空间!
ptr = (struct student*)malloc(sizeof(struct student));
这时咱们再往下看
- 这时程序要求用户输入,分别存储进ptr的数据域中的成员:name数组与score
- 假设我们输入的为:Axuan,99
- 如下图:
输入完成后,这时ptr所指向的内存是有数据的,我们来看下面这段语句
这时将prev指向头结点的首地址,current指向头结点的指针域,如下图
在这儿比较绕了,深度剖析一下,current和prev均用于操作头结点。不同之处是prev用于操作当前节点,current用于操作下一个节点
我们来看下面的语句:
执行循环有两个要求,第一个是在头结点后有数据,第二个要求是首元节点中的score数值要大于新节点的score,显然程序的定义是头节点不存放数据,那么第一次输入,头节点是没有连接新的节点的
继续看下一个,这时将新的节点插入进去
- 第一步:将新节点的指针域指向需要插入位置的后置节点
- 第二步:将新节点的前置结点的指针域指向新节点
先看第一句,如图:
由于是第一次输入,头节点后是没链接节点的,所以current所指向为空,这时需要插入新的节点,所以将新节点的指针域指向需要插入位置的后置节点,但是后边没得了,就指向了NULL
再看第二句:
prev->next=ptr,当新节点的指针域操作完毕后,我们需要将需要插入位置的前置节点的指针域指向新节点。
红色线条是最后执行的!到这儿第一次的输入就完毕了
线条太多?我们把线条全部擦一下:
这样我们可以理解了吧!
第二次:
这时主函数中的while是一个死循环,在执行了第一次insere_func();函数后,再次执行!
除了ptr所指向的内存是因为我们动态分配,存放于堆内,其他的数据:s_temp作为一个局部变量在第一次执行结束后已经释放
那么我们这是ptr依旧是指向刚刚那片内存,但是!!它仅仅是指向,要明白,ptr是一个指针,指针是一个变量,它的值是可以改变的!!!
在这之前,它的值是刚刚分配的那片内存的地址!!我们没有释放!!也就是说,在程序结束之前,第一次的数据一直会保存于那片内存!!
再一次的定义了一个s_temp变量后,我们又到了创建新节点的这一步
看图:
看到这粉嫩的小箭头了没(它再一次的重复之前的动作分配了结构体大小的内存,并交给ptr管理)ptr指向了刚刚分配的那段内存!!
这时继续重复刚刚输入的数据,我们这次输入Bxuan,105
我们来看语句:
prev继续指向头节点,current继续指向头节点的指针域
这时进入循环,由于有了第一次创建与链接,这时头结点后是有链接节点的
但第二个条件不满足,current管理的是首元结点(第一组),第一组成员score小于第二组score,所以不执行循环(程序开头有个注释:/添加是以分数的高低加以排序/)
直接到下面的:
不满足循环,就让这个结点插入到头结点后,先让新结点链接后置节点,让新结点的指针域指向后置节点
在让当前节点的指针域指向新节点
为了更加易懂,我加上了第一组第二组
prev->next=ptr,由于第二组分数是大于第一组分数的,所以这儿让第二组成为首元节点,插入到第一组和头结点之间
到这时,第二组的添加也完成了,我们继续把图片整理下
有没有像一个小火车!~一节车厢连着一节车厢!
第三次
经过前面两次,最后一次我就直接到输入数据这儿开讲了
假设我们再次输入Cxuan,100
这儿又为ptr分配了一片同样的内存,然后将数据载入进去
一样没变,prev管理着头结点,current管理着首元节点
这时要注意了,current不为NULL,且100要小于105,进入循环
这时将两个指针向后移动,分别管理下一个结点和下一个结点的指针域
prev管理了头结点后的节点,current管理了prev的指针域
然后再次进行循环判断,这时current还是不为空,它指向第一组,头指针取到current->score就是第一组中的score作比较,结果是100>99则不执行循环!找到了正确的插入位置
然后进行下一语句:
pte->next是第三组的指针域,让他等于第二组的指针域
prev->next=ptr,然后第二组的指针域,让他指向第三组
最后我们再一次的整理!让各位了解的更加透彻
注意:内存不是连续的!
第一函数总结:
第一个函数实现了添加以及排序功能,这排序是不是很熟悉?这就是最常用最简单的插入排序,拿出一个数,对后面的每一个数做比较,如果满足,则交换两者位置,如果不满足,则将这个数放到前数后面。
与之前学的相比,之前利用数组实现是顺序结构,这次只不过利用链式结构实现,实现的原理就是在prev与current指针上,一个管理当前结点,一个管理后置节点
通俗点说就是操作指针域实现各项功能
prev作用于修改当前节点,current作用于修改下一节点!
为什么头结点数据域内不存储数据,因为头节点用于相邻其他节点,打个比方来说,头节点就和火车头一样,头结点可以使用,只是在链表节点的插入,删除操作中极为不便,尤其是双向链表,逻辑通用性不强,处理不好很容易出错
对头指针以及头节点的疑问请看:头指针与头结点补充笔记
while循环的作用是一直在寻找正确的节点进行插入,并让current指向它,如果current指向的节点满足条件,则通过prev进行修改这个节点,通过current修改下一节点
学习到这里,我对单向链表有了一个大致的了解,通过其他功能函数学习逐渐完善!
功能函数(删除节点)
我们继续着结构体声明,定义,主函数定义完头指针,头结点后,录入函数输入数据后,接上图做讲解
先看代码:
首先程序定义了两个char类型的元素,一个del_name[20]为数组,ans为普通变量,然后使用gets进行输入数据
prev指向头,current指向 头指针域,从头开始,到这里是否对头节点有点模糊的理解了?
假设,我们要删除Cxuan这个数据,这是通过名字来遍历链表,符合要求的时候执行循环体内的删除
当current->next与输入的字符串相等的时候,就不执行,如果不相等,则:
移至下一个节点,我们按图来看,不满足条件,则将指针移到下一个节点,依旧是判断current所指向的区域
再进入循环,current->name是Cxuan
则不满足条件,跳出循环
执行if语句
当我们确定删除后
prev->next就指向current->next了,我们用图了解它的运作情况
因为要删除包含Cxuan的节点,则要将Cxuan之前的节点与之后的节点相邻,按照图上来说,就是将第三组清楚,将第二组与第一组相邻
此时current还是指向第一节点的指针域,指向第三组,然后free(current)
去释放这段内存,那么就完成了删除的工作
这时这一步也就算完成了!
整体简单来说就是,先将current指向链表的第一个存放有数据的节点,接着利用while循环找出欲删除的节点,将prev指向current节点的下一个节点,并回收current节点
其实理解并不难,current指针一直在遍历链表,从头节点的指针域开始遍历,再让prev指向刚刚走过的节点,进而得以控制两节点!
功能函数(修改节点)
我们继续着结构体声明,定义,主函数定义完头指针,头结点后,录入函数输入数据后,删除一个数据,接上图做讲解
此时程序当中的走向如图所示,我们看代码:
先定义了两个数组,第一个数组我们可以从代码知道用于查找,第二个数组我们可以知道是用于存放临时数据
一样,current指向头结点的指针域,指向第一节点:
然后利用while循环来遍历链表,找到符合条件的节点,假设我们存入n_temp中的值为Axuan
进入判断条件,都满足,则进入循环
将prev和current移至下一个节点
再次进入循环,这时strcmp判断两字符串相等,则不进入循环,进入下一语句
这时你需要输入新的数据载入临时变量s_temp中,再将他转换十进制整型(atoi)存入current此时指向节点的score成员中去
这时s_temp的值会替换掉原有的值,假设我们输入78
修改后:
就完成了数据的修改
功能函数(遍历节点)
这应该是一个最简单的了,我们接着上图继续讲解
然后看代码:
这儿首先判断了头节点后节点是否存在数据,咱们是有数据的,就进入下一段,三个打印就不说了
current=head->next,这时我们可爱的current指针又登场了,它继续指向第一节点
然后进入while循环遍历链表:
输出节点内的成员后,count作为计数变量,自增一位,然后指针指向下一节点继续进行循环
如果存放到20个节点后结束运算,这一步可有可无,这儿就不细讲了。运行图:
到这儿对单向链表已经有了一个简单的理解,咱们进入双向链表