实训任务——链表

01

前言

链表操作是我们在学习过程中的一大难点，也是一个非常重要的知识点，因为在之后C语言学习的过程中，很多结构模式图都可以在链表的基础上进行延伸。在初次接触的时候，可能会有很多人不能理解每一步的操作过程。

基本上每一本学习C语言的书上都会有基本链表的讲解，以及源代码，所以在这里我不会再讲链表的建立方式。而主要讲怎样在有序链表中插入数数据，希望大家能在此基础上去解题，而不是只依赖与答案

02

题目

3-1. 从键盘输入一组整数，创建单向链表，并输出链表中的数据。（10分）

样例输入：2 5 7 6 3 4

样例输出：2 5 7 6 3 4

（此题跳过）

3-2. 从键盘输入两组由小到大的整数，每组数据创建一个链表。然后将两个链表合并，合

并后的链表仍然保持由小到大的顺序。最后输出合并后的链表。（15分）

样例输入：1 2 5 9 20 25 30 35

3 4 7 8 23

样例输出： 1 2 3 4 5 7 8 9 20 23 25 30 35

（只讲如何在已有链表中插入一个数据）

03

思路

首先我们需要创建一条链表（做上面题目时，我们可以指定为A链表，或者B链表），输入一个新的数据，从初始链表中寻找他应该存放的位置。实际上谭浩强老师的那本书上有插入方法的源程序，可是很多同学可能并不理解为什么要想那样操作，我当时学的时候也并不懂那段插入程序的意思。后来自己画了画示意图。就什么都理解了

插入的过程我们要把它拆分为两个部分。

第一部分：在链表的头位置插入一个数据

第二部分：在链表中间和末尾位置插入一个数据

首先说说第一部分（在头位置插入数据)

其次是第二部分（在中间和末尾插入数据）

以上两部是不可以交换的，而很多新手可能并不理解为什么，包括我自己刚学的时候也不能理解。实际上，我们在操作时只有一个变量来表示前后的两个数据，如果先执行第二步，第一步指向的时候就变成了自身循环指向，p的next指针指向了自己。

而在末尾插入数据时，也有两步，也就是把末尾数据的next指针指向新开辟的内存空间p。p的next指针指向NULL即可.

04

源程序

在一条已知链表中插入一个数据的程序:

第一部分：头文件，定义结构体与函数声明

第二部分：简单链表的建立

第三部分：插入一个数据

05

后话

在写实际题目时，我们必须要确定一个主链表，每次插入值的时候不能跨链表指向，因为两个链表使用的结构体不同；所以每次在主链表中插入数据时，必须要使用动态内存分配，开辟一块与主链表相同的结构体空间才行。