没有合适的资源?快使用搜索试试~ 我知道了~
首页计算机专业基石:数据结构讲义与实用辅导
计算机专业基石:数据结构讲义与实用辅导
![](https://csdnimg.cn/release/wenkucmsfe/public/img/star.98a08eaa.png)
《数据结构讲义》是一本针对计算机专业基础课程——数据结构的辅导教材,由作者根据多年教学经验编撰而成。作者以通俗易懂、直接简练的语言风格编写,旨在帮助学生理解和记忆复杂的概念,尤其关注于那些在专升本考试中常见的知识点。书中内容丰富,包括线性表、栈与队列、串、树和二叉树、图、查找表、内部排序等核心章节,不仅涵盖了教材《数据结构》(严蔚敏版)的内容,还配有各类习题及参考答案,旨在促进学生实践能力和理论知识的结合。 在编写过程中,作者注重实用性和互动性,书中语言可能不够严谨,但通过引号标注和脚注的方式进行说明,便于读者理解。作者强调这本书应与《数据结构》教材配套使用,并且考虑到习题的多样性,挑战性超越了专升本考试的要求,旨在帮助学生扩展知识视野。 作者特别感谢张志老师、李永干老师和谭业武老师的支持与贡献,以及隆坤的鼓励,他们共同推动了这本书的成形。书的前言部分还提供了复习提示,指导学生如何高效复习和准备课程。每个章节都按照基础知识、算法和习题的结构组织,确保内容全面且易于消化。 《数据结构讲义》是一本实用的辅助教材,适合计算机专业的学生和教师,无论是作为学习资料还是教学工具,都能提供有价值的帮助。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/4780213/bg10.jpg)
www.juanjuantx.com 3. 单链表——线性表的链式存储结构之一
- 13 -
}
// 在单链表 L 中查找元素 x
// 若找到,返回该元素的位序;否则返回 0
int Find ( LinkList L, DataType x )
{
p = L->next; j = 1;
while ( p!=NULL ) {
if ( p->data == x ) return j; // 找到 x
p = p->next; j++; // 计数器随指针改变
}
return 0; // 未找到
}
前一个算法的另一种写法:
p = L->next;
while ( p && p->data!=x )
p = p->next;
if ( p && p->data==x ) return p;
else return 0;
或者
p = L->next;
while ( p && p->data!=x ) p = p->next;
return p; // 为什么
3°. 查找第 i 个元素
LinkList Get ( LinkList L, int i )
{
p = L->next; j = 1;
while ( p && j<i ) {
p = p->next; j++;
}
if ( p && j==i ) return p;
else return 0;
}
4°. 查找第 i-1 个元素
p = L; j = 0;
while ( p && j<i-1 ) {
p = p->next; j++;
}
if ( p && j==i-1 ) return p;
else return 0;
![](https://csdnimg.cn/release/download_crawler_static/4780213/bg11.jpg)
www.juanjuantx.com 3. 单链表——线性表的链式存储结构之一
- 14 -
(6) 插入算法 ListInsert(&L,i,x)
技巧:画图辅助分析。
思路:
先查找第 i-1 个元素
若找到,在其后插入新结点
bool
10
ListInsert ( LinkList &L, int i, DataType x )
{
// 查找第 i-1 个元素 p
p = L; j = 0;
while ( p && j<i-1 ) {
p = p->next; j++;
}
// 若找到,在 p 后插入 x
if ( p && j==i-1 ) {
s = (LinkList) malloc(sizeof(LNode));
s->data = x;
s->next = p->next; // ①
p->next = s; // ②
return true; // 插入成功
}
else
return false; // 插入失败
}
注意:
a) 要让 p 指向第 i-1 个而不是第 i 个元素(否则,不容易找到前驱以便插入)。
b) 能够插入的条件: p && j==i-1 。即使第 i 个元素不存在,只要存在第 i-1 个元
素,仍然可以插入第 i 个元素。
c) 新建结点时需要动态分配内存。
s = (LinkList) malloc(sizeof(LNode));
若检查是否分配成功,可用
if ( s==NULL ) exit(1); // 分配失败则终止程序
d) 完成插入的步骤:①②。技巧:先修改新结点的指针域。
(7) 删除算法 ListDelete(&L,i,&x)
思路:
先查找第 i-1 个元素
若找到且其后存在第 i 个元素,则用 x 返回数据,并删除之
10
这里返回 true 表示正确插入,返回 false 表示插入失败。
a
i-1
·
-
插入前
执行①之后
执行②之后
·
-
p
x
s
a
i-1
·
-
·
-
p
x
·
-
s
a
i-1
·
-
·
-
p
x
·
-
s
①
②
①
![](https://csdnimg.cn/release/download_crawler_static/4780213/bg12.jpg)
www.juanjuantx.com 3. 单链表——线性表的链式存储结构之一
- 15 -
bool ListDelete ( LinkList &L, int i, int &x )
{
// 查找第 i-1 个元素 p
p = L; j = 0;
while ( p && j<i-1 ) {
p = p->next; j++;
}
//若存在第 i 个元素,则用 x 返回数据,并删除之
if ( p && j==i-1 && p->next ) { // 可以删除
s = p->next; // ①
p->next = s->next; // ②
x = s->data;
free (s);
return true;
}
else
return false;
}
注意:
a) 要求 p 找到第 i-1 个而非第 i 个元素。为什么?
b) 能够进行删除的条件: p && j==i-1 && p->next 。条件中的 p->next 就是要保证
第 i 个元素存在,否则无法删除。若写成 p->next && j==i-1 也不妥,因为此时(循环
结束时)可能有 p==NULL,所以必须先确定 p 不空。技巧:将条件中的“大前提”放
在前面。该条件也不可以写成 p->next && p && j==i-1,因为先有 p!=0 才有 p->next,
上式颠倒了这一关系。
c) 释放结点的方法。 free(s);
d) 完成删除的步骤:①②。
(8) 建立链表的两种方法
思路:
建立空表(头结点);
依次插入数据结点(每次插入表尾得(a
1
,a
2
,…,a
n
),每次插入表头得(a
n
,…,a
2
,a
1
))。
1°. 顺序建表
void CreateLinkList ( LinkList &L, int n)
{
// 建立空表
L = (LinkList) malloc(sizeof(LNode));
L->next = NULL; // 空表
p = L; // 用 p 指向表尾
// 插入元素
for ( i=0; i<n; i++ ) {
scanf ( x );
a
i-1
·
-
删除前
a
i
·
-
p
·
-
s
a
i-1
·
-
执行①之后
a
i
·
-
p
·
-
①
s
a
i-1
·
-
执行②之后
a
i
·
-
p
·
-
①
②
![](https://csdnimg.cn/release/download_crawler_static/4780213/bg13.jpg)
www.juanjuantx.com 4. 循环链表
- 16 -
s = (LinkList) malloc(sizeof(LNode));
s->data = x;
// 插入表尾
s->next = p->next;
p->next = s;
p = s; // 新的表尾
}
}
2°. 逆序建表
void CreateLinkList ( LinkList &L, int n)
{
// 建立空表
L = (LinkList) malloc(sizeof(LNode));
L->next = NULL; // 空表
// 插入元素
for ( i=0; i<n; i++ ) {
scanf ( x );
s = (LinkList) malloc(sizeof(LNode));
s->data = x;
// 插入表头
s->next = L->next;
L->next = s;
}
}
4. 循环链表
(1) 特点
最后一个结点的指针指向头结点。
(2) 类型定义
同单链表。
(3) 基本形态
空表:L->next == L。
非空表。
(4) 与单链表的联系
判断表尾的方法不同:单链表用 p==NULL;循环链表用 p==L。
其余操作相同。
a
n
C
B
A
(
b
)
(a
)
E
a
1
L
...
L
![](https://csdnimg.cn/release/download_crawler_static/4780213/bg14.jpg)
www.juanjuantx.com 6. 顺序表与单链表的比较
- 17 -
5. 双向循环链表
(1) 特点
一个结点包含指向后继(next)和指向前驱(prior)两个指针,两个方向又分别构成循环链
表。
(2) 类型定义
typedef struct DuLNode {
DataType data;
struct DuLNode *prior, *next; // 两个指针
} DuLNode, *DuLinkList;
(3) 基本形态
空表:用后向指针判断 L->next == L,或者用前向指针判断 L->prior == L。
非空表。
(4) 与单链表和循环链表的联系
最大不同:前驱容易求得,可以向前遍历。
判断表尾的方法与循环链表相同:p==L。
插入和删除时需要修改两个方向的指针。
(5) 插入和删除
需要修改两个方向的指针。例如:(见下表)
表 2.2 双向循环链表的插入和删除
p 之后插入 s
p 之前插入 s
删除 p 之后继 s
删除 p
s->next = p->next;
p->next = s;
s->prior = p;
s->next->prior = s;
s->prior =
p->prior;
p->prior = s;
s->next = p;
s->prior->next = s;
s = p->next;
p->next = s->next;
p->next->prior = p;
p->prior->next =
p->next;
p->next->prior =
p->prior;
6. 顺序表与单链表的比较
表 2.3 顺序表和单链表的比较
顺序表
单链表
以地址相邻表示关系
用指针表示关系
随机访问,取元素 O(1)
顺序访问,取元素 O(n)
插入、删除需要移动元素 O(n)
插入、删除不用移动元素 O(n)(用于查找
a
1
a
2
a
n
L
L
... ...
data
prior
next
剩余101页未读,继续阅读
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/cc659a59504a425c991cc8199a82dd8d_jake443403168.jpg!1)
Jake443403168
- 粉丝: 47
- 资源: 394
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 解决本地连接丢失无法上网的问题
- BIOS报警声音解析:故障原因与解决方法
- 广义均值移动跟踪算法在视频目标跟踪中的应用研究
- C++Builder快捷键大全:高效编程的秘密武器
- 网页制作入门:常用代码详解
- TX2440A开发板网络远程监控系统移植教程:易搭建与通用解决方案
- WebLogic10虚拟内存配置详解与优化技巧
- C#网络编程深度解析:Socket基础与应用
- 掌握Struts1:Java MVC轻量级框架详解
- 20个必备CSS代码段提升Web开发效率
- CSS样式大全:字体、文本、列表样式详解
- Proteus元件库大全:从基础到高级组件
- 74HC08芯片:高速CMOS四输入与门详细资料
- C#获取当前路径的多种方法详解
- 修复MySQL乱码问题:设置字符集为GB2312
- C语言的诞生与演进:从汇编到系统编程的革命
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)