单链表的4种简单操作——建立、输出、删除、插入_·定义main函数,调用给出的建立、输出、插入、删除等函数,验证单链表的设计思

参阅于谭版C语言程序设计（第五版）第9章第9题

此题的建立和输出操作延用教材中例题提到过的算法，而删除和插入操作均为个人想法，由于此时还未系统性学习数据结构和算法，可能并不是最优的算法，待日后学习数据结构和算法后再来改进。

• 建立

  我们可以定义一个creat函数来实现，参数列表为空，返回值类型为结点（结构体）指针，通过调用此函数得到所建立链表的头指针。

  其算法的大致思想是通过定义两个结点指针p1和p2，p1不断的指向我们新创建的结点，p2不断的指向链表表尾结点（或者说不断的更新表尾结点），然后就可以通过p1、p2进行操作从而使新结点和表尾结点之间建立联系。

• 输出

  定义一个print函数，参数列表为结点指针，返回值为空。通过调用Input函数，将链表头指针作实参传入。

  算法思想：先判断链表是否为空链表，若不为空链表，则打印输出第一个结点的数据，然后不断的使形参指针指向后个结点并输出，直到指针指向NULL。

• 删除

  定义del函数，参数列表中参数1为结点指针，参数2为整型变量，返回值类型为结点指针。通过调用此函数，将链表头指针和要删除的结点序号作实参传入，返回删除指定结点后的链表头指针。

  算法思想：如果要删除的结点为第一个结点，则使第一个结点的next成员置NULL，再使头指针指向第二个结点。如果要删除的结点为第二个节点及后续结点，则可以先找到要删除位置前个位置的结点指针并记下，那么删除位置的结点指针后推一位即可得到，也将其记下，再使前个位置的next指向删除位置的next，然后使删除位置的next置NULL。那么又如何找到删除位置前个位置呢，从第一个结点开始指，每次指向都往后移一次，循环n-2次（n为要删除结点的序号），例如，若要删除第2个结点，由于开始时指向第一个结点，所以不用后移，循环n-2即2-2=0次。

• 插入

  定义insert函数，参数类型和返回值类型与del函数相同。

  算法思想：与删除结点的算法类似，只要找到两个结点（插入位置的结点及其前个位置的结点）即可完成插入操作，此外要定义一个新结点变量并输入数据作为我们要插入的结点。首先，使插入位置的前个结点的next成员指向新结点，然后使新结点的next成员指向插入位置的结点。

总结：不管是删除还是插入，只要找到两个结点（即要删除或插入位置及其前个位置的结点）就可以完成这类操作，那么又如何找到这个关键的位置呢？可以通过循环不断的使“搜索指针”往后指（这个指针用于找到某个我们指定位置的结点，所以我习惯于将其称之为搜索指针，便于我们记忆），这个循环的次数由传入的整型参数（我们要增删的位置序号）决定。