单链表的插入与删除
参考:http://www.itxyz.net/3jk/c/2010/0820/11016.html
最近不是太忙,整理些东西,工作也许用得到。
在链表这种特殊的数据结构中,链表的长短需要根据具体情况来设定,当需要保存数据时向系统申请存储空间,并将数据接入链表中。对链表而言,表中的数据可以依此接到表尾或连结到表头,也可以视情况插入表中;对不再需要的数据,将其从表中删除并释放其所占空间,但不能破坏链表的结构。这就是下面将介绍的链表的插入与删除。
1. 链表的删除
如创建一个学生学号及姓名的单链表,即节点包括学生学号、姓名及指向下一个节点的指针,链表按学生的学号排列。再从键盘输入某一学生姓名,将其从链表中删除。
首先定义链表的结构:
从链表中删除一个节点有三种情况,即删除链表头节点、删除链表的中间节点、删除链表的尾节点。题目给出的是学生姓名,则应在链表中从头到尾依此查找各节点,并与各节点的学生姓名比较,若相同,则查找成功,否则,找不到节点。由于删除的节点可能在链表的头,会对链表的头指针造成丢失,所以定义删除节点的函数的返回值定义为
返回结构体类型的指针。
2. 链表的插入
首先定义链表的结构:
在建立的单链表中,插入节点有三种情况,如图所示;

插入的节点可以在表头、表中或表尾。假定我们按照以学号为顺序建立链表,则插入的节点依次与表中节点相比较,找到插入位置。由于插入的节点可能在链表的头,会对链表的头指针造成修改,所以定义插入节点的函数的返回值定义为返回结构体类型的指针。节点的插入函数如下:
实例:
创建包含学号、姓名节点的单链表。其节点数任意个,表以学号为序,低学号的在前,高学号的在后,以输入姓名为空作结束。在此链表中,要求删除一个给定姓名的节点,并插入一个给定学号和姓名的节点。
运行结果: