ITeye博客

单链表的插入与删除

mmdev · 2011-12-21 17:19 · Markdown

参考:http://www.itxyz.net/3jk/c/2010/0820/11016.html

最近不是太忙,整理些东西,工作也许用得到。

在链表这种特殊的数据结构中,链表的长短需要根据具体情况来设定,当需要保存数据时向系统申请存储空间,并将数据接入链表中。对链表而言,表中的数据可以依此接到表尾或连结到表头,也可以视情况插入表中;对不再需要的数据,将其从表中删除并释放其所占空间,但不能破坏链表的结构。这就是下面将介绍的链表的插入与删除。

1. 链表的删除

如创建一个学生学号及姓名的单链表,即节点包括学生学号、姓名及指向下一个节点的指针,链表按学生的学号排列。再从键盘输入某一学生姓名,将其从链表中删除。

首先定义链表的结构:

从链表中删除一个节点有三种情况,即删除链表头节点、删除链表的中间节点、删除链表的尾节点。题目给出的是学生姓名,则应在链表中从头到尾依此查找各节点,并与各节点的学生姓名比较,若相同,则查找成功,否则,找不到节点。由于删除的节点可能在链表的头,会对链表的头指针造成丢失,所以定义删除节点的函数的返回值定义为

返回结构体类型的指针。

2. 链表的插入

首先定义链表的结构:

在建立的单链表中,插入节点有三种情况,如图所示;

插入的节点可以在表头、表中或表尾。假定我们按照以学号为顺序建立链表,则插入的节点依次与表中节点相比较,找到插入位置。由于插入的节点可能在链表的头,会对链表的头指针造成修改,所以定义插入节点的函数的返回值定义为返回结构体类型的指针。节点的插入函数如下:

实例:

创建包含学号、姓名节点的单链表。其节点数任意个,表以学号为序,低学号的在前,高学号的在后,以输入姓名为空作结束。在此链表中,要求删除一个给定姓名的节点,并插入一个给定学号和姓名的节点。

运行结果:

评论(0)

暂无评论。

评论功能维护中,当前仅展示历史评论。