c语言链表详解填空题 求大佬

来源：蜘蛛抓取(WebSpider) 时间：2022-10-24 03:44 标签： c语言链表详解

今天将给大家讲述链表的学习心得。学习数据结构，毋庸置疑链表必须学好，后面的栈、队列、树、图都是以链表为基础的；链表的种类很多，有单链表、双链表、循环链表、非循环链表；在此，我们以非循环单链表为例，来讲链表的创建、求长度、排序、插入和排序。

链表我的理解要包含以下特征：

（1）.由n个节点离散分配；

（2）.每个节点通过指针连接

（3）每一个节点由一个前驱节点和一个后驱节点

（4）.首节点没有前驱节点，尾节点没有后驱节点；

满足上面的4条，我们就称为链表；链表既然由很多个节点，那节点又由什么组成？节点由两个部分组成，一是数据域，用来存放有效数据；二是指针域，用来指向下一个节点；下面用C语言来构建链表数据结构，首先应该构造出节点，然后再把所有的节点连起来，就构成了链表；

typedef 只是给数据类型取个别名，即 typedef 数据类型 别名；我们知道struct Node 是我们定义的数据类型；

在创建链表之前，我们需要需要了解一下专业术语：

首节点：存放第一个有效数据的节点；

尾节点：存放最后一个有效数据的节点；

头节点：头节点的数据类型与首节点的数据类型相同，并且头节点是首节点前面的那个节点，并不存放有效数据；头节点的存在只是为了方便链表的操作。

头指针：指向头节点的指针；

尾指针：指向尾节点的指针；

首先，我们应该创建一个头节点，并用头指针指向它，用C语言描述：用malloc向计算机申请一块内存，并定义一个指向与头节点数据类型相同的指针（一定要判断申请内存是否成功）；

然后，要知道要创建链表的长度，用一个循环来每次创建一个节点，并把每个节点连在一起；

假如我们要在头节点phead后面插入节点p：

这样就可以了吗？ 想想我们就可以发现，当我们要插入多个节点时，头节点始终指向最后添加的一个数据，以前的节点通过头指针此时已经找不到了；我们定义一个尾指针pTail，始终用来指向链表的结尾，每次只在pTail后面添加节点。

（1）定义一个尾指针pTail，并初始化，使它指向头节点，即pTail=pHead；

（2）在pTail后面添加节点，修改指针：

假如要在节点2的前面插入节点p，我们首先要找到节点2的前驱节点1，假设现在q指针指向节点1，则

假如要删除节点2，只需要把节点1指针域指针指向节点3，但不要忘记释放节点2所占的内存，否则将会造成内存泄漏；首先必须找到节点2的前驱节点1，假设p指向节点1。

快速排序和冒泡排序的思想对于链表这个数据结构同样适用，下面是一个用选择排序来实现链表的排序；

和数组排序很像，只是这里需要两个指针p、q不停地移动，来获取链表中的数据元素；

喜欢此篇文章或觉得这篇文章对你有帮助的读者可以点播关注或者转发，私信小编001即可获得小编自己整理的一份2018最新的C/C++资料和0基础入门教程，欢迎初学和进阶中的小伙伴

无论是顺序存储结构还是链式存储结构，在内存中进行存放元素的时候，不仅需要存放该元素的相关信息，还需要存放该元素和其他元素之间的关系，而我们之前所学的顺序表“与生俱来”的物理结构自然地能够表达出元素和元素之间的关系，不需要额外的信息去表达元素和元素之间的关系，而对于链式存储这种非顺序存储的结构，需要额外附加指针去表示这种关系。

每个结点除了存放数据元素外，还要存储指向下一个节点的指针。

优点：不要求大片连续空间，改变容量方便

缺点：不可随机存取，要耗费一定空间存放指针

除了上述这种方法外，我们还可以先先声明LinkNode为结构体类型，在使用该类型的时候，将对应的变量定义为指针即可。

单链表分为带头结点和不带头结点，我们一般主要学习带头结点的。

在所有的操作之前，我们首先需要建立一个空的单链表，那么首先需要做的就是分配头结点。

“头插法”顾名思义就是将元素插入到头结点之后，插入一次好像和我们通常所讲的插入没什么区别，但多次这样插到头结点之后，也就是“第一个真正的节点”，那么是不是会产生一种现象，它最终的存储数据和我们所插入时的顺序是相反的。

printf("请输入你要插入的元素个数：");

“尾插法”顾名思义就是将元素插入到表尾，也就是我们普通的插入，那么怎么要找到表尾的位置呢？在顺序表中，我们完全可以利用它顺序存储结构的天然特性，通过下标即可以找到，但是单链表是没有办法的，我们只有两种方式，要么循环遍历，要么尝试在表尾的地方做个标记。

那么那种方法是好的呢？

答案是第二种！循环遍历的方式，如果只插入一个元素看似没什么问题，但如果多次的重复遍历循环无疑增加了时间复杂度，这显然不是好的方法。

第二个方法就不存在时间复杂度的问题，只需要在表尾位置做个标记，使它永远指向表尾即可。

printf("请输入你要插入的元素个数："); r = s;//s为当前的表尾指针，将他的值赋值给r----使r永远指向表尾

既然要删除某个元素，那么首先我们需要保证这个元素是非NULL，其次，我们还需要保证它前面的那个节点也是非NULL，为什么呢？因为如果将该元素从链表中删除后，只有前面节点非NULL的情况下，才可以实现后续元素和前面子表的连接。

printf("不存在我们要删除的元素！"); printf("不存在我们要删除的元素！"); free(q);//需要及时的将删除了的元素空间进行释放

其他的基本操作都是很常规化的，这里就不单独的进行解释了，需要注意的点，我会在文章结尾部分的完整代码的注释中展出。

printf("请输入你要插入的元素和位序：（元素和位序之间用逗号隔开）\n");

如下所示的代码顺序不能发生改变，否则会出现无法和后面的节点；

我要回帖

更多关于 c语言链表详解 的文章

 

随机推荐