混子数据结构学习之第二章线性表链式表示之基本操作代码实现
2022-01-03 本文已影响0人
那个混子
"磨棱角，褪优越，沉下心"
"不止于心动，更付诸于行动，执行力！“
前言
接着前面学，没有在2021年完成代码的梳理，被中断了，今天接着搞一下。知识点都是连续的，需要回顾上一篇的内容点。按最简单的来，单链表开始学相关的初始化、判断是否为空、销毁等基本操作，主要是理解思路和代码的实现。这一部分需要复习一下指针相关的知识点，涉及的指针多。
线性表的链式结构
理解
单链表的程序定义
通过链表的概念和基本定义理解，我们应该要想到一样的，使用结构体来定义，涉及到地址问题，要想到指针类型。下面给出定义
typedef int ElemType;//数据域的数据类型
typedef struct
{
ElemType date;//结点的数据域
struct Node* next;//结点的指针域
}Node, //结点的数据类型
*LinkList;//Node型的指针
分析：
- 假设p是指向线性表第i个元素的指针，则该结点a的数据域我们可以用
p->data来表示，p->data的值是一个数据元素，结点ai的指针域可以用p->next来表示，p->next的值是一个指针。p->next指向谁呢?当然是指向第i+1个元素，即指向a(i+1)的指针。
也就是说，如果p->data=ai那么p->next>data=ai+1。
- 上述代码的实现定义，指针域，我们这个地址指向的是相同类型的结点，所以这里就是需要定义为对应的数据类型。
- 数据域可能不单只有那么一个元素，可能有许多元素，只需要修改·
ElemType即可，根据情况，例如存储一个学生信息，那么元素就可能有姓名、年龄、学号等等。
单链表的基本操作
注：这里默认按照带头结点的单链表进行学习！
一、初始化
算法步骤：
- 生成新结点作头结点，用头指针L指向头结点。
- 将头结点的指针域置空。
代码实现
//---带头结点的单链表初始化
//unsigned char InitList_L(LinkList &L) L = new LNode; C语言不支持该用法，引用是针对C++的用法
unsigned char InitList_L(LinkList *L)//等价于Node **L，二级指针
{
*L = (LinkList)malloc(sizeof(Node));//开辟结点的存储空间，建立头结点
(*L)->next = NULL;//建立空的单链表
return OK;
}
注意点：（重要！！！！）
- 在初始化过程中，需要修改头指针，因此要用到二级指针传递头指针的地址，这样才能修改头指针。这与普通变量类似，当需要修改普通变量的值，需传递其地址。使用二级指针，很方便就修改了传入的结点一级指针的值。 如果用一级指针，则只能通过指针修改指针所指内容，却无法修改指针的值，也就是指针所指的内存块。
- 若一个变量想通过函数来改变本身的值，将本身作为参数传递是不成功的，只有传递本身的指针（地址）才能达到这样的效果。
- 一般情况，向函数传递指针类型的参数，可以让函数改变指针指向的内容，并将改变的效果返回；这里要改变指针变量L本身的值，使它指向新开辟的内存空间L = (LinkList)malloc(sizeof(LNode))，而不是要改变L所指向的内容的值，所以，要么向函数传递L的引用，要么传递指向L的指针（指向指针的指针）
-
引用的用法是C++里面的语法，C语言不支持引用&。
C语言是不支持引用的
二、判断链表是否为空
空表：链表中无元素，称为空链表（头指针和头结点仍然在）。
//-----判断链表是否为空
unsigned char ListEmpty(LinkList L)
{
if(L->next)//非空
{
return FALSE;
}
else//空表
{
return OK;
}
}
注意：
- 这里的判断，判断指针域是否为空，可以类比顺序表中判断长度理解。
三、单链表的销毁
算法思路
从头指针开始，依次释放所有结点。
暂存下一个结点，释放当前结点，依次循环
- 让p指向头结点
- 把头结点的next值修改成，现在第一个有效节点的next成员的值。
-
然后再释放p。
代码实现
//--------单链表的销毁：链表销毁后不存在
//p = head->next;head->next = p->next;free(p);
unsigned char DestroyList_L(LinkList *L)//需要传入二级指针，等同于Node **L
{
Node *p;//或LinkList p;
while((*L))
{
p = (*L);//p指向当前的第一个结点（首元结点）
(*L) = (LinkList)(*L)->next;//移动存储下一个结点
free(p);//释放当前
//delete p (C++写法)
//printf("正在删除\n");//测试用
}
//printf("删除完成\n"); //测试用
return OK;
}
注意点：上述代码先释放头结点，然后依次释放，判断的是头结点是否为空。
综合代码
主要介绍学习了带头结点的单链表的两个重要的操作，链表的初始化（新建链表）、链表的销毁操作。下面给出可以运行的全部代码，后续的其他操作在这个基础上进行验证。
说明
- 开发环境：VC++2010
- 语言：C语言
- 测试：能够正常运行，无错误
#include<stdio.h>
#include <stdlib.h> // malloc, free, rand, system
#define OK 1
#define FALSE 0
typedef int ElemType;//数据域的数据类型
typedef struct
{
ElemType date;//结点的数据域
struct Node* next;//结点的指针域
}Node, //结点的数据类型
*LinkList;//结点的指针类型
//---带头结点的单链表初始化
//unsigned char InitList_L(LinkList &L) L = new LNode; C语言不支持该用法，引用是针对C++的用法
unsigned char InitList_L(LinkList *L)//等价于Node **L，二级指针
{
*L = (LinkList)malloc(sizeof(Node));//开辟结点的存储空间，建立头结点
(*L)->next = NULL;//建立空的单链表
return OK;
}
//-----判断链表是否为空
unsigned char ListEmpty(LinkList L)//这里只需传入一级指针即可，不涉及到指针的改变
{
if(L->next)//非空
{
return FALSE;
}
else//空表
{
return OK;
}
}
//--------单链表的销毁：链表销毁后不存在
//p = head->next;head->next = p->next;free(p);
unsigned char DestroyList_L(LinkList *L)//需要传入二级指针，等同于Node **L
{
Node *p;//或LinkList p;
while((*L))
{
p = (*L);//p指向当前的第一个结点（首元结点）
(*L) = (LinkList)(*L)->next;//移动存储下一个结点
free(p);//释放当前
//delete p (C++写法)
//printf("正在删除\n");//测试用
}
//printf("删除完成\n"); //测试用
return OK;
}
void main()
{
LinkList L;//定义链表L
int choice, ans;
while(1)
{
printf("线性表的链式表示和实现(菜单)：\n");
printf("1、单链表的初始化 2、单链表的销毁\n");
printf("请输入菜单序号：\n");
scanf("%d", &choice);
switch(choice)
{
case 1:
ans = InitList_L(&L);
if(ans)
{
printf("初始化成功\n");
}
else
{
printf("初始化失败\n");
}
break;
case 2:
ans = DestroyList_L(&L);
if(ans)
{
printf("单链表已销毁\n");
}
else
{
printf("单链表销毁失败\n");
}
break;
}
}
}
总结
通过对单链表的理解，结合软件程序设计，掌握如何去定义链表以及最基本的两个操作初始化和销毁。这里面涉及到C语言的基本知识的理解。
- 值传递中的两种方式：自身传递、地址传递的区别，这个后续会写一下。
- 链表中的二级指针的用法，由于像创建链表、销毁这些都是涉及到变量的新建和删除问题，变量是要发生改变的，这里的变量就是链表的地址，故需要使用指针的指针的方式。
- malloc、sizeof的再次熟悉和使用。
好了，就写到这里了，睡觉了，明天要上班搬砖！！
参考资料：
青岛大学.王卓.数据结构与算法
《数据结构 C语言版》.严蔚敏
《大话数据结构》.程杰
若上述描述有问题或者歧义的，欢迎与我反馈交流，共同进步学习！
欢迎关注本人微信公众号：那个混子
记录自己学习的过程，分享乐趣、技术、想法、感悟、情感！
单片机类嵌入式交流学习可加企鹅群：120653336
