函数：求有头结点单链表长度

来源：蜘蛛抓取(WebSpider) 时间：2022-07-07 06:27 标签： 单链表的长度是什么

输入一个正整数 n(0<n<=9)和一组(n个)升序的整数，建立单向链表，再输入一个整数 x，把 x 插入到这组数据中，使该组数据仍然有序。

输入输出示例：括号内为说明

p=q;//将p移到链表的下一个位置上，以便下一次的串联 head=q;//如果替换了第一个数，记得要修改头节点

请编写程序实现单链表插入、删除结点等基本算法。给定一个单链表和一系列插入、删除结点的操作序列，输出实施上述操作后的链表。单链表数据域值为整数。

输入第1行为1个正整数n，表示当前单链表长度；第2行为n个空格间隔的整数，为该链表n个元素的数据域值。第3行为1个正整数m，表示对该链表施加的操作数量；接下来m行，每行表示一个操作，为2个或3个整数，格式为0 k d或1 k。0 k d表示在链表第k个结点后插入一个数据域值为d的结点，若k=0则表示表头插入。1 k表示删除链表中第k个结点，此时k不能为0。注：操作序列中若含有不合法的操作（如在长度为5的链表中删除第8个结点、删除第0个结点等），则忽略该操作。n和m不超过100000。

输出为一行整数，表示实施上述m个操作后的链表，每个整数后一个空格。输入数据保证结果链表不空。

p=q;//将p移到链表的下一个位置上，以便下一次的串联 int m;//为对链表的操作数量 
请编写创建链表和输出链表的函数。对于以下数据结点的结构定义，
针对带头结点的链表，请编程完成以下功能。
输入数据包含若干组命令和数据，一组数据中的第1个字符代表命令，
接下来的是该命令需要的数据。
(2)如果命令是A，后跟一个整数data，功能为向链表尾部追加一个数据data,
(3)如果命令是C，后跟一个整数N，再跟N个整数，功能为向链表尾部追加N个
(4)如果命令是P，功能遍历输出链表中所有数据，数据间用一个空格分隔,对应

以上为上一题目的内容，在此基础上，增加设计如下功能： 

(5)如果命令是N，后跟一个整数n和d，功能为向链表的第n个位置插入数据d,
(6)如果命令是F，后跟一个整数d，功能为在链表查找数据d,返回其位序，若
(7)如果命令是D，后跟一个整数n，功能为删除链表第n个位置的数据,可通过

若干组命令和数据，很多命令和数据写在一起请注意识别。

根据输入命令输出相应内容，详见输出样例。

p=head->next;//因为这是一个带头结点的链表，所以head实际上是没有数的，它指向的才存了第一个数
  • 若已建立下面的链表结构，指针 p、q 分别指向图中所示结点，则不能将 q 所指结点插入到链表末尾的语句是（C ）。

如果问的是链表长度，也等同于求节点的数量，那么当然是算的。

但是头结点是使单链表操作更容易实现的而存在的，一般单链表求长度问的都是元素的数目，这是一般是不算的。你可以参考一下以下一个求链表长度的函数:

学生党个人理解，有错误希望批评指正

线性表是一种十分基础且重要的数据结构，它主要包括以下内容：

接下来，我将对这四种数据结构做一个详细的总结，其中对链表实现了十几种常见的操作。希望对你有所帮助。

数组(Array)是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
注意点：①.数组是一种线性表；②.连续的内存空间和相同类型的数据
由于第二个性质，数组支持 “随机访问”，根据下表随机访问的时间复杂度为O(1);但与此同时却使得在数组中删除，插入数据需要大量的数据搬移工作。

低效的“插入”和“删除”

假如数组的长度为n，我们需要将一个数据插入到数组的第k个位置，我们需要将第k~n位元素都顺序地往后挪动一位。
最好情况时间复杂度为O(1),此时对应着在数组末尾插入元素;
最坏情况时间复杂度为O(n),此时对应着在数组开头插入元素;
平均情况时间复杂度为O(n),因为我们在每个位置插入元素的概率相同，故(1+2+3+……+n)/n=O(n);
但是根据我们的需求，有一个特定的场景。如果数组的数据是有序的，那么我们在插入时就一定要那么做；但是如果数组中存储的数据并没有任何规律，数组只是被当成一个存储数据的集合，我们可以有一个取巧的方法：
直接将第k个元素搬移到数组元素的最后，把新的数据直接放入第k个位置即可（是不是很简单啊），这时插入元素的复杂度为O(1)。

和插入操作一样，为了保证内存的连续性，删除操作也需要搬移数据。
最好情况时间复杂度为O(1),此时对应着删除数组末尾的元素;
最坏情况时间复杂度为O(n),此时对应着删除数组开头的元素;
平均情况时间复杂度为O(n),因为我们删除每个位置的元素的概率相同，故(1+2+3+……+n)/n=O(n);
当然，在某些特殊情况下，我们并不一定非要进行复杂的删除操作。我们只是将需要删除的数据记录，并且假装它以经被删除了。直到数组没有更多空间存储数据时，我们再触发一次真正的删除操作即可。

这其实就和生活中的垃圾桶类似，垃圾并没有消失，只是被“标记”成了垃圾，而直到垃圾桶塞满时，才会清理垃圾桶。

在 C 语言中，只要不是访问受限的内存，所有的内存空间都是可以自由访问的。如果疏忽会造成严重的后果。当然，Java会自动检测。

  • 单链表根据索引插入结点
  • 单链表删除指定索引的结点
  • 单链表实现元素查找，返回是否存在布尔值
  • 单链表删除指定索引的后续节点

单链表根据索引插入结点

//完成节点的插入操作 //返回真正的链表头节点地址

单链表删除指定索引的结点

//完成节点的删除操作

单链表实现元素查找，返回是否存在布尔值

单链表删除指定索引的后续节点

//利用两个指针，fast和slow，它们之间差k个位置，判断如果fast.Nest=null,也就代表着slow这个位置就是倒数第k个结点

1.基于数组实现的顺序栈

//基于数组实现的顺序栈 //初始化数组，申请一个大小为n的数组空间 //数组空间不足，直接返回false，入栈失败 //栈为空，直接返回-1; //返回下标为count-1的数组元素，并且栈中元素个数count减一

//定义了结点的嵌套类

  • 基于数组实现的普通队列
  • 基于数组实现的循环队列

1.基于数组实现的普通队列

//数组：items，数组大小：n //head表示队头下标，tail表示队尾下标 //入队(一),基础版 //如果tail==n，表示队列末尾已经没有空间了 //入队（二），改进版 //如果tail==n，表示队列末尾已经没有空间了

2.基于链表实现的队列

//基于链表实现的队列 //定义了结点的嵌套类 //向表尾添加元素,即入队

3.基于数组实现的循环队列

//head表示队头下标，tail表示队尾下标

文章代码太多，我本来是希望分成几篇文章写的，但是由于一些原因，最终放在了一起，略显臃肿。代码都是经过测试用例测试过的，应该不会有错误。

如果体验不太好，可以移步我的,里面观感较好。

题外话：对于算法初学者，推荐一本十分 nice 的书籍 《算法第四版》，里面各种配图十分详细。如果你需要电子版文件，后台回复算法4即可获得下载链接。后台回复 算法01 送你一份 算法与数据结构思维导图。最后，希望我们一起进步，一起成长！

我要回帖

更多关于 单链表的长度是什么 的文章

 

随机推荐