陕西住房与城乡建设部网站,为学校网站做网站推广策划,百度首页排名优化公司,网站策划过程目录 前言
1.链表
1.1链表的概念 1.2链表的分类
1.2.1单向或双向
1.2.2.带头或者不带头
1.2.33. 循环或者非循环
1.3链表的实现 定义链表
总结 前言 前边我们学习了顺序表#xff0c;顺序表是数据结构中最简单的一种线性数据结构#xff0c;今天我们来学习链表#x…
目录 前言
1.链表
1.1链表的概念 1.2链表的分类
1.2.1单向或双向
1.2.2.带头或者不带头
1.2.33. 循环或者非循环
1.3链表的实现 定义链表
总结 前言 前边我们学习了顺序表顺序表是数据结构中最简单的一种线性数据结构今天我们来学习链表难度相较于顺序表会大幅增加非常考验大家对结构体、指针的理解。但是也不要害怕我会一一向大家解答疑惑本期的内容先给初学者预预热主要介绍在刚开始学习链表时需要注意的点、涉及的基础知识以及逻辑基础下期会将功能接口具体实现。 1.链表
1.1链表的概念 概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 逻辑图 而现实中的链表是这样的 通过图我们可以观察到链式数据结构在逻辑上是连续的在物理上不一定连续。链表的好处在于对内存更高效的使用加入一个节点就开辟一个节点的空间。
注意
链表的节点是在堆上开辟的程序不结束就不会主动释放。从堆上申请的空间是按照一定策略分配的两次申请的空间可能连续也可能不连续。 1.2链表的分类 链表主要分为以下几种
1.2.1单向或双向 单向的链表简称为单链表单链表只可以进行单向遍历而双向链表完美的弥补了这个缺陷可以向前遍历也可以向后遍历
1.2.2带头或者不带头 它们本质上并没有太大的区别在链表功能实现过程中有头节点的不需要对特殊节点进行特殊操作相对简单但对于大部分的刷题网站上链表的题目都是默认为无头节点的所以对于无头节点链表的理解更为重要。
1.2.3 循环或者非循环 循环链表可以用于解决一些特定的问题非循环链表一般用于普通的链表操作例如插入、删除、查找等。 虽然有这么多的链表的结构但是我们实际中最常用还是两种结构 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结 构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。 带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都 是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带 来很多优势实现反而简单了后面我们代码实现了就知道了。
1.3链表的实现 对于初学者来说我个人建议先从无头单向非循环链表学起因为在很多的刷题场景中都是单项无头非循环链表理解了它也可以帮助你更快的适应链表的刷题。今天我们主要从这种单链表讲起。 单链表的实现过程中会存在很多的坑对于初学者来说是很困难的我会一一列举帮助大家避免这些错误刚开始我会从基础知识层面进行逐个分析当然内容也会很多我会分期进行讲解。 定义链表
typedef int Datatype;
typedef struct SLNode
{Datatype data;SLNode* next;
}SLNode; 定义链表这里就迎来了第一个坑上述的这种形式很常见对于初学者来说这里就有一个坑这个链表定义的是否正确呢 这种方式是不正确的为什么typedef是重命名结构体是我们自定义类型SLNode是重命名后的名字但是这里需要注意这个重命名是从上述代码第六行结束后才开始生效在结构体中提前使用是不允许的。
正确的定义
typedef int Datatype;
typedef struct SLNode
{Datatype data;struct SLNode* next;
}SLNode; 定义之后就需要创建节点创建节点这里我们要明白我们是通过函数的形式来创建节点创建时顺便赋值初学者或许会有这样的疑问那为什么函数的类型是结构体指针类型例如
SLNode* NewNode(Datatype x)
{
} 为了后续节点的链接我们最后需要返回新建节点的地址而节点地址的类型就是SLNode* 函数的类型也只是函数的返回类型。 接下来就是功能实现
SLNode* NewNode(Datatype x)
{SLNode* newnode (SLNode*)malloc(sizeof(Datatype));if (newnode NULL){perror(malloc);exit(-1);}newnode-data x;newnode-next NULL;return newnode;
} 这里就迎来了第二个坑 这段代码哪里有问题 首先我们要清楚链表开辟空间是给谁开辟的链表的空间是给整个节点结构体开辟的而不是仅仅给数据开辟空间。 所以说这里malloc的大小应该是结构体的大小改为
SLNode* newnode (SLNode*)malloc(sizeof(SLNode));
就可以啦 在其他功能实现之前我们先理解以下打印链表的函数接口。
void SLprint(SLNode* phead)
{SLNode* cur phead;while (cur){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
} 打印链表首先需要遍历链表phead为链表的头指针但是一般情况下我们并不会直接的使用头指针去遍历因为那样可能会造成头节点的丢失所以我们需要创建另一个变量来接收头指针去执行遍历操作。我们要想让cur向后移动就只需把下一个节点的地址赋值给cur我们知道一个链表的节点内会存储着下一个节点的地址也就是当前节点中的next。注意这里的遍历需要好好的理解这是进行后续理解的前提。 理解完链表的的遍历接下我们来说说它们是如何将每个新建的节点链接的。初学链表可能会有这样的疑惑创建的节点是如何一个个链接起来的呢节点的链接是属于后续头插尾插等操作的内容但是为了解答大家内心的疑惑我们先写一个简单的测试接口来演示它是如何链接的
void test1()
{SLNode* plist NULL;//链表的头指针没有节点的情况下指向NULLint n 0;printf(请输入链表的长度\n);scanf(%d, n);printf(请输入数据\n);for (int i 0; i n; i){int val 0;scanf(%d, val);SLNode *newnode NewNode(val);//创建结构体指针变量来接收新节点的地址//头插的方式链接newnode-next plist;plist newnode;}SLprint(plist);
}int main()
{test1();return 0;
} 首先我们把头指针指向的内容可能是NULL也可能是第一个节点赋值给新节点。 初始情况下plist指向NULL把plist指向的内容赋值给新节点newnode的next指针域然后把整个新节点的地址赋给plist。 这样plist就成功指向了第一个节点。那么后续插入增加节点也是这样。假设上一步链接的节点地址是0x0012ff40。 把plist指向的节点地址赋值给新建节点newnode的next结构体内的成员。 然后把整个新节点的地址赋给plist。这样就通过头插将节点链接了。但是这里需要注意测试接口的操作是在同一个函数内进行创建头指针节点链接操作的不需要传值没有调用函数进行头插链接在后续实现头插尾插接口的过程中需要使用二级指针传参进行操作。 接着我们继续尾插操作的实现。 尾插的原理是什么找到最后一节点。 将新节点的地址赋给最后一个节点的next指针域就可以了。 注意新节点的next指针域在创建初始化时就已经置为NULL。 但这并不完整前边我们提到尾插也可以用来初始化那么对于没有节点的情况上述逻辑就无法使用了。所以我们需要特殊处理一下判断链表是否为NULL。
void SLPushBlack(SLNode* phead, Datatype x)
{SLNode* newnode NewNode(x);SLNode* tail *pphead;if (phead NULL){phead newnode;}else{while (tail-next)//找到最后一个节点{tail tail-next;}tail-next newnode;}
} 以上的逻辑可以这样实现那段代码是否正确呢这里就是遇到的第三个坑。运行测试一下我们会发现链表为空的时候没有插入数据。这是为什么呢 那是因为传进来的头节点是形参形参是实参的临时拷贝出了函数phead就被销毁了在函数内将新节点地址赋给形参 头节点并不会对实参中的头节点造成影响。那这里要想修改实参中头节点的指向就只能传头节点的地址二级指针通过实参中头指针的地址来修改头指针的指向。 所以正确的代码应该是
void SLPushBlack(SLNode** pphead, Datatype x)
{SLNode* newnode NewNode(x);SLNode* tail *pphead;if (*pphead NULL){*pphead newnode;}else{while (tail-next){tail tail-next;}tail-next newnode;}
}
//调用时要传结构体指针的地址
SLPushBlack(plist,100); 那或许会有人疑惑为什么链表不为的时候就不使用二级指针 这里我们总结一下使用二级指针是因为要修改结构体指针头指针的指向而链表不为空时只需要链接增加一个节点就好这时修改的是结构体成员的内容。
对头插操作进行实现 使用二级指针是因为要修改结构体指针头指针的指向那按照逻辑头插每次都是修改头指针的指向所以头插独立实现成一个函数时也需要二级指针尾插是只有第一次链表为空的时候需要二级指针而头插次次都需要二级指针。 注意前边测试的接口头插数据没有使用二级指针是因为创建头指针和修改头指针指向在同一个函数中不存在函数调用头指针。
前边我们已经了解头插的逻辑这里就不再讲解。代码实现
void SLPushFront(SLNode** pphead, Datatype x)
{SLNode* newnode NewNode(x);newnode-next *pphead;*pphead newnode;
} pphead就是指向plist头指针的指针*pphead就等价于plist。通过对pphead解引用找到plist头指针直接修改plist头指针的指向。 总结 本期内容主要介绍在刚开始学习链表时需要注意的点、涉及的基础知识以及逻辑基础一定要理解透彻否则后续的接口实现将会寸步难行好的本期内容到此就要结束啦希望对你有所帮助最后感谢阅读
