文档介绍：2015考研计算机
《数据结构》重难点精讲
主讲：杨航空
考查目标
• 1、掌握数据结构的基本概念、基本原理和基本方法。
• 2、掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本
的时间复杂度与空间复杂度的分析。
• 3、能够数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++
语言设计与实现算法的能力。
第一章线性表
线性表这一章里面的知识点不多，但要做到深刻理解，能够应用相关知识点
解决实际问题。链表上插入、删除节点时的指针操作是选择题的一个常考点，诸
如双向链表等一些相对复杂的链表上的操作也是可以出现在综合应用题当中的。
（一）线性表的定义和基本操作
（二）线性表的实现
1. 顺序存储
2. 链式存储
3. 线性表的应用
难点讲解
一、线性表是具有相同数据类型的n(n≥0)个数据元素组成的有限序列。
理解线性表的要点是：
1）表中元素具有逻辑上的顺序性，在序列中各元素排列有其先后次序。各个数据
元素在线性表中的逻辑位臵只取决于其序号。
2）表中元素个数有限。
3）表中元素都是数据元素。就是说，每一个表元素都是不可再分的原子数据。
4）表中元素的数据类型都相同。这意味着每一个表元素占有相同数量的存储空间。
5）表中元素具有抽象性。就是说，仅讨论表元素之间的逻辑关系，不考虑元素究
竟表示什么内容。
难点讲解
二、顺序表中数据元素的插入
插入一个元素的基本步骤如下：
初始表：
1）将ai～an顺序向下移动，为新元素让出位臵；

2）将item臵入空出的第i个位臵；

3)修改表长。

在顺序表中进行插入运算的时间复杂度为O(n)
在等概率的情况下，任意位臵上插入一个元素，需要移动的元素次数为：
=(n+1)/2
难点讲解
三、顺序表中数据元素的删除
在顺序表中删除一个元素需要经过如下步骤：
初始表：
1）将第i个位臵上的元素删除；

2）将ai+1～an顺序向上移动；

3）修改表长。

在顺序表中进行插入运算的时间复杂度为O(n)
在等概率的情况下，任意位臵上删除一个元素，需要移动的元素次数为：
=(n+1)/2
难点讲解
四、顺序表中按值查找数据
最简单的方法就是从第一个元素a1起一次和item相比较，直到找到一个与item相
等的数据元素。
按值查找的评价比较次数为n，时间性能为O(n)。
五、顺序表效率分析
•时间效率分析：
算法时间主要耗费在移动元素的操作上，计算时间复杂度的基本操作：
T(n) = O(移动元素次数)
移动元素的个数取决于插入或删除元素的位臵。
•线性表顺序纯粹结构特点：逻辑关系上相邻的两个元素在物理存储位臵上也相邻；
优点：可以随机存取表中任一元素；
缺点：在插入、删除某一元素时，需要移动大量元素。
难点讲解
六、单链表在第1个结点前插入
核心语句： newnode - >link = first; first = newnode;

七、在单链表中间插入
核心语句： newnode- >link = p- >link; p- >link = newnode;
难点讲解
八、在链表末尾插入
核心语句： Newnode - >link = p->link; p->link = newnode;

九、删除不带头结点的单链表中或表尾元素
核心语句： q = p - >next; P - >next = q - >next; free(q);
难点讲解
十、删除不带头结点单链表中第一个元素
核心语句： Newnode - >link = p->link; p->link = newnode;

十一、删除带头结点的单链表
核心语句： p - > next = q - > next;