[笔记]指针与双向链表
双向链表:可进行双向访问
单链表中,每个结点有一个指向其后继结点的指针,整个单链表只沿着一个方向操作,那么双向链表,顾名思义,在它的结点中,不仅包含直接后继结点的地址指针,还包含它的直接前驱结点地址指针
我们来看一段代码,从代码中去了解链表的创建与链接(下列使用双向循环链表)
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
void init_f(void);/*初始化链表,创建第一空结点为HEAD*/
void insert_f(void);/*插入函数*/
void delete_f(void);/*删除函数*/
void display_f(void);/*输出函数*/
void modify_f(void);/*修改函数*/
struct student
{
char name[20];
int score;
struct student* llink;/*结点左链接*/
struct student* rlink;/*结点右链接*/
};
struct student* ptr, * head, * tail, * current_n, * prev;
int main()
{
char option1;
init_f();
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':
insert_f();
break;
case '2':
delete_f();
break;
case '3':
display_f();
break;
case '4':
modify_f();
break;
case '5':
printf("欢迎使用\n");
return 0;
}
}
}
void init_f(void)/*设一head,将左右链接均指向自身*/
{
ptr = (struct student*)malloc(sizeof(struct student));
strcpy(ptr->name, "0");
ptr->llink = ptr;
ptr->rlink = ptr;
head = ptr;
tail = ptr;
}
/*按分数高低添加*/
void insert_f(void)
{
char s_temp[4];
ptr = (struct student*)malloc(sizeof(struct student));
printf("\n学生姓名:");
gets(ptr->name);
printf("学生分数:");
gets(s_temp);
ptr->score = atoi(s_temp);
prev = head;
current_n = head->rlink;
while ((current_n != head) && (current_n->score = ptr->score))
{
prev = current_n;
current_n = current_n->rlink;
}
ptr->rlink = current_n;
ptr->llink = prev;
prev->rlink = ptr;
current_n->llink = ptr;
printf("添加成功");
}
void delete_f(void)
{
char del_name[20], ans;
int count = 0;
if (head->rlink == head)
{
printf("\n没有该学生信息");
}
else
{
printf("\n输出删除学生的姓名:");
gets(del_name);
prev = head;
current_n = head->rlink;
while ((current_n != head) && (strcmp(current_n->name, del_name) != 0))
{
prev = current_n;
current_n = current_n->rlink;
}
if (current_n != head)
{
printf("确定是否删除Y/N");
ans = _getch();
if (ans == 'Y' || ans == 'y')
{
prev->rlink = current_n->rlink;
current_n->rlink->llink = prev;
free(current_n);
printf("\n 学生%s已经删除", del_name);
}
}
else
printf("\n未找到该学生信息");
}
}
void modify_f(void)
{
int count = 0;
char n_temp[20], s_temp[4];
if (head->rlink == head)
{
printf("\n没有学生信息");
}
else
{
printf("请输入需要修改的学生姓名:\n");
gets(n_temp);
current_n = head->rlink;
while ((current_n != head) && (strcmp(current_n->name, n_temp) != 0))
{
prev = current_n;
current_n = current_n->rlink;
}
if (current_n != head)
{
printf("\n***********************************\n");
printf("学生姓名:%s\n", current_n->name);
printf("学生分数:%d\n", current_n->score);
printf("***********************************\n");
printf("请输入新的学生分数:");
gets(s_temp);
current_n->score = atoi(s_temp);
printf("\n修改后\n");
printf("学生姓名:%s\n", current_n->name);
printf("学生分数:%d\n", current_n->score);
}
else
{
printf("\n未找到%s的学生信息", n_temp);
}
}
}
void display_f(void)
{
int count = 0;
if (head->rlink == head)
{
printf("\n未找到学生信息\n");
}
else
{
current_n = head->rlink;
while (current_n != head)
{
printf("\n-----------------------\n");
printf("\n学生姓名:%s\n", current_n->name);
printf("学生分数:%d\n", current_n->score);
printf("-----------------------\n");
count++;
current_n = current_n->rlink;
if (count % 20 == 0)
{
_getch();
}
}
}
printf("\n共找到%d名学生信息", count);
}
我们继续一个函数一个函数的剖析
先看结构体定义:
- 与单链不同的是,结构体内多了一个结点,分为了左右链接结点
- 同时程序定义了五个指针型结构体变量,通过这五个指针来操作链表
- 程序首先为ptr开辟了一段内存
- 随后将ptr的数据域中的name赋值为0
- 将ptr的左右指针指向自身
- 然后将head指针指向ptr,tail指针指向ptr
此函数位于主函数开头,从这儿我们可以知道,ptr(1)作为头结点,head始终指向头结点
在初始化的时候,左右两指针指向它本身
这时候一个双向链表就创建好了,我们来看看它如何链接结点
注:在下列模拟中,ptr每一次分配的内存是没有名字的,为了直观的理解代码运作过程,结合图形,我将会将第一次ptr分配的称作ptr(1),第二次ptr创建的称作ptr(2)
第一次创建:
第一步,为ptr分配一片内存, 创建一个新的结点
然后将数据载入进入,我们输入:Axuan,99
再操作prev和current_n指针,看图操作:
- 让prev管理头结点,然后让current_n管理头结点的右指针域
为了不引起歧义,ptr管理此内存,指向的是它开辟内存的首地址
此时current_n所指向的为ptr(1),prev所指向的为ptr(1)
接下来进入循环判断,current不为空,输入的数据要大于current_n所管理的数据
(循环作用于找到正确的节点)不断让prev指向下一个节点,current指向下一个节点的右指针域
不进入循环,这时候重点来了!链接两个结点!先看代码!
操作新开辟结点的(左右)指针域:
我们看第一段和第二段语句,先操作ptr的右指针域
让他等于current_n(前置结点的右指针域)
再操作ptr的左指针域,让他等于prev(前置结点)
我们再操作一下prev的右指针域!prev->rlink=ptr
(让前置结点的右指针域指向新结点)
让current_n所管理(指向)的区域:current_n->llink=ptr
(让后置节点的左指针域指向新结点)
完成了结点的链接!
我们来整理一下图:
- head作为指向头结点的指针,它始终指向头结点通过它可以更好的管理整个链表!带头结点与不带头结点的区别和优劣会在后边详细讲解。
- current_n指向的是头结点的右指针域。(管理后置结点)
- prev指向的是头结点。(管理当前节点)
- 通过这两个结点,来操作左右指针域的链接,从上图可以看到:
- 先让ptr的右指针域指向前置节点的指针域(current_n)
- 再让ptr的左指针域指向前置结点,完成两结点的链接
在这儿就可以知道:
- 右指针域的作用是用于链接下一个结点(后置结点)
- 左指针域的作用是用于链接上一个结点(前置结点)
那么在结点内并可以访问前置结点和后置结点
这儿可以直观的了解到单双两链表的不同之处
单向链表插入: 所有功能只需要操作一个当前节点和后置节点(操作两个指针域)
- 双向链表插入:除了需要考虑当前节点和后置节点,还需要考虑前置结点,在链接和删除的时候,如果是循环链表,则需要将尾结点的指针域指向头结点(操作四个指针域)
涉及多个指针操作,具体请看:补充笔记(双向链表基础操作)
插入:第二次创建链接
我们再一次的调用insert_f()函数,再创建一个新的节点。
假设这次输入的数据为:Bxuan,78
我们依旧从头结点开始,让prev管理头结点, 让current管理头结点的右指针域
从图可知,current_n所管理的是ptr(2),进入循环后判断头结点后是有数据的,则判断头结点后的数据是否大于新结点的数据,99>78
进入循环,让两个操作指针移位,这时prev和current_n指向的是ptr(2)和ptr(1),因为是循环列表,则表尾要链接表头
再次进入循环,显然表头是不存储数据域的,则将ptr(3)进行尾插
还是操作新结点的左右两个指针域
- 将右指针域指向前置节点的右指针域
- 将左指针链接前置结点
这时再将前置节点的右指针域链接ptr
由于是循环链表,所以每一次的插入都要改变表头和表尾的链接,最后再将表头的左指针域链接新结点
就完成了新结点的链接
第三次创建
通过上两次的链接,我们已经明白了双向链表是如何插入的,到这里在巩固一下,进行的三次的模拟
- 第一步:当然还是分配内存,形成新的节点
- 第二步:当然是输入数据域
- 第三步:当然是初始化两个操作指针,还是从表头开始
程序要求的是降序排列,则进入循环后首先判断头结点后是否有数据
再遍历整个链表找到正确的位置插入
第一遍循环,99>85,将两个操作指针移到下一位:prev跟着current_n一个管理着ptr(2)一个管理ptr(3),再进入循环判断ptr(3)内78要小于85,不进入循环,则找到了正确位置,进行插入
重复之前的动作,新操作新结点,让新结点链接前置和后置
- 再让新结点的前置的右指针域链接新结点
- 让新结点的后置结点的左指针域链接新结点
就完成了结点的链接
删除节点
上面我们了解了如何添加结点,如何在指定位置添加,无非就是操作指针域而已,其实删除节点也特简单
程序是按名字进行删除的,则我们准备一个临时数组
先判断头结点后是否有数据
如果有,则进入else语句,初始化操作指针,假设我们要输入Cxuan
利用while遍历来查找链表内是否有这个数据
有两种结束可能,第一个是遍历到头了还是没满足第二个结束条件,就是整条链表内都没该数据
第二种就是找到了这个数据,可以进行删除
我们用if排除第一种可能,找到了数据,经过while循环,prev已经指向了ptr(2),current_n已经指向了ptr(4)
这时先断开需要删除的结点与前置结点和后置节点的联系
- 让prev的右指针域指向ptr(3)
- 让ptr(3)的左指针域指向ptr(2)
- 最后回收ptr(4)
整理一下图片:
修改节点
得知了删除和增加的原理后,剩下的功能就很容易了
先判断头结点后是否有数据
如果有,则通过循环找到符合条件的节点,移动操作指针
然后通过操作指针修改需要修改的值,即可
查找节点:
这个就是从头节点开始遍历所有节点依次输出数据,计数变量count自增,每输出20个数据停止
总结
- 这里我们只是简单的了解结点的链接和删除通过遍历实现各项功能
- 详细的链表运用会在数据结构中讲解
- 主要需要掌握的是指针域的操作,头指针指向头结点,头结点中可存放数据也可不存放
- 循环链表的表尾右指针域需要指向表头,当然表头的左指针域需要指向表尾
- 而简单的双向链表则只需要将表头左指针域指向空,表尾右指针域指向空
接下来我们来了解堆栈的实现