考研专业课之统考计算机蓝宝书(4)

1.4 线性表的链式存储和运算实现

1.4.1 单链表

链表是由一个个结点构成的，结点定义如下：

痛常我们用"头指针"来标识一个单链表，如单链表L、单链表H等，是指某链表的第一个结点的地址放在了指针变量 L、H 中， 头指针为"NULL"则表示一个空表。

1.4.2 单链表上基本运算的实现

1. 建立单链表
(1) 在链表的头部插入结点建立单链表
注意：在链表的头部插入，读入数据的顺序和线性表中的逻辑顺序是相反的。
算法如下：

在上面的算法中，第一个结点的处理和其它结点是不同的，原因是第一个结点加入时链表为空，它没有直接前驱结点，它的地址就是整个链表的指针， 需要放在链表的头指针变量中；而其它结点有直接前驱结点，其地址放入直接前驱结点的指针域。"第一个结点"的问题在很多操作中都会遇到，如在链表中插入结点时，将结点插在第一个位置和其它位置是不同的，在链表中删除结点时，删除第一个结点和其它结点的处理也是不同的，等等，为了方便操作，有时在链表的头部加入一个"头结点"，头结点的类型与数据结点一致，标识链表的头指针变量L中存放该结点的地址，这样即使是空表，头指针变量L也不为空了。头结点的加入使得"第一个结点"的问题不再存在，也使得"空表"和"非空表"的处理成为一致。

头结点的加入完全是为了运算的方便，它的数据域无定义，指针域中存放的是第一个数据结点的地址，空表时为空。

• ·2010年迦思佑考研6000词逻辑辨证记忆
• ·2010年迦思佑张纪元考研6000词汇记忆课堂录音
• ·10版研究生英语难句过关-盘内容
• ·【VIP专享】2009新东方考研英语复试听力(音频+讲义)
• ·沪江考研原创：和我一起突破考研长难句1-33
• ·胡敏考研英语词汇-读故事记单词（09最新版）MP3
• ·2010淘金高阶考研英语词汇词典版MP3
• ·2010考研英语阅读理解精读100篇（高分版）文本下载
• ·2009年考研英语大纲词汇
• ·2010考研英语万能作文MP3

• 麦考瑞内部雅思7-7.5分部分题库
• 一月速背6000单词
• 英语口语需要自然流露
• 7月名师讲座
• 点滴积累学英语系列之一