首页 > 编程学习 > 【数据结构】结构体与链表

【数据结构】结构体与链表

发布时间:2022/11/10 7:34:55

前言

学习数据结构的链表章节,如果对结构体的基础知识掌握不牢,就很难理解,下面先带大家理解结构体知识基础

结构体知识基础

析 :类型,变量名

  • 数据类型:int char
  • 变量名:arr ch str name a x(等一些有含义或者常用的名称)

结构体类型的定义

struct  结构体类型名
{
   数据类型名1    成员名1;
   数据类型名1    成员名1;
   ...

   数据类型名n    成员名n;

};

我们自己定义的结构体类型地位上等价于int char,只是用起来稍微麻烦些

结构体变量的定义

间接定义法

struct  结构体类型名
{
   数据类型名1    成员名1;
   数据类型名1    成员名1;
   ...

   数据类型名n    成员名n;

};
struct 结构体类型名 变量名;

直接定义法

struct  结构体类型名
{
   数据类型名1    成员名1;
   数据类型名1    成员名1;
   ...

   数据类型名n    成员名n;

}变量名;

重命名结构体

typedef是类型定义的意思。typedef struct 是为了使用这个结构体方便。

  • 若struct LNode {};这样来定义结构体的话。在申请变量LNode 时,需要这样写,struct LNode n;
  • 若用typedef,可以这样写,typedef struct LNode{}LNode; 。在申请变量时就可以这样写,LNode n;
typedef struct Student
{
   int a;

}Stu;
//如果没有typedef就必须用struct Student stu1;来声明
//如果有typedef就可以用Stu stu1;来声明
//这里的“类型名”Stu实际上就是struct Student的别名

单链表

单链表分为两个部分:数据域结构域,简单来看就是结构体与指针的结合体,与递归的思想密不可分。

模板

typedef struct Lnode
{
	ElemType data; //节点数据域 
	struct Lnode;  //节点指针域 
}Lnode,*LinkList; //LinkList为指向struct Lnode的指针

// 这里的 Lnode,*LinkList 都是类型名,struct Lnode 的不同表达形式 
LinkList L; //定义链表L 
LNode *p;   //定义节点指针 

小贴士:

  • ElemType只是类型的统称 ,可以代表char int float......数据结构更注重方法,不针对特定的语言
  • LinkList L 与LNode *L等价,但是后者不常用
  • LNode *p 与LinkList p等价,但是后者不常用

初始化

头结点会在单链表的第一个结点之前附加一个结点,数据域可以不设任何信息,也可以记录表长等信息,指针域指向线性表的第一个元素结点
头指针

通常会用头指针来标识一个单链表,不管带不带头结点,头指针始终指向单链表的第一个结点

void InitList(LinkList &L)
{
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
}

程序解释:

LinkList &L:在调用函数时,实参一般不会被形参改变,但是在C++中,使用引用 & ,之后形参就可以影响实参了,LinkList L、LinkList& L、和LinkList *L这三者的区别

malloc(sizeof(LNode)),动态获取LNode的字节数,从而开辟新的空间,返回LinkList类型,详细解释请查看,malloc函数详解

单链表的销毁

//销毁
void DestoryList_L(LinkList &L)
{
	LNode *p;
	while (L)
	{
		p=L;
        L=L->next;
		free(p);
	}
}

注意事项:

因为单链表使用的空间是我们使用malloc动态开辟的,所以是需要我们手动去释放的。

但是要注意,对于单链表空间的释放,我们不能做到像顺序表那样一次性就释放掉,因为顺序表空间是一块连续的空间,但是,链表是一个一个结点构成的,一个结点malloc一次,它们不一定连续的空间,所以我们要一个结点一个结点的释放。

持续更新中...

Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式