没有合适的资源？快使用搜索试试~ 我知道了~

首页《数据结构》辅导讲义——严蔚敏版配套

《数据结构》辅导讲义——严蔚敏版配套

数据结构

需积分: 10 1 下载量 48 浏览量更新于2024-07-25 收藏 1.53MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

试读

102页

"数据结构讲义（严蔚敏版）" 这本数据结构讲义是针对计算机专业基础课程《数据结构》编写的，作者庄波基于多年教学经验，旨在辅助学生理解和掌握严蔚敏版教材的核心内容。讲义共102页，特别适合准备专升本考试的学生使用。书中采用较为口语化和直观的语言描述数据结构的思想，以便于学习和记忆，但同时也提醒读者，这种表达方式并不适合正式引用。讲义涵盖的内容包括：前言部分，作者阐述了编写此书的初衷和风格特点；复习提示章节，对教材的主要内容进行了概括，如经典算法、线性表、栈和队列、串、树和二叉树、图、查找表和内部排序等；接着，详细讲解了各个主题，如绪论介绍了基础知识和算法的概念；线性表讨论了顺序表和各种链表结构的特性；栈和队列阐述了栈和队列的基本操作、不同实现方式以及它们的应用；串部分则涉及串的定义、基本操作和存储结构。每章后面均配备有习题，习题量适中，难度各异，不仅限于专升本考试要求，并且提供了参考答案，方便学生自我检测和巩固学习。此外，作者在编写过程中得到了多位老师的帮助和支持，他们的贡献使得这本讲义能够顺利完成并出版。此讲义作为严蔚敏版《数据结构》教材的补充，对于深入理解和实践数据结构概念具有很高的价值。学生可以结合讲义与教材一同学习，通过实例和习题更好地掌握数据结构的核心知识。

资源详情

资源推荐

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;

www.juanjuantx.com 3. 单链表——线性表的链式存储结构之一

- 14 -

(6) 插入算法 ListInsert(&L,i,x)

技巧：画图辅助分析。

思路：

先查找第 i-1 个元素

若找到，在其后插入新结点

bool

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 返回数据，并删除之

这里返回 true 表示正确插入，返回 false 表示插入失败。

i-1

插入前

执行①之后

执行②之后

i-1

①

②

①

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

,…,a

)，每次插入表头得(a

,…,a

)）。

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 );

i-1

删除前

i-1

执行①之后

①

i-1

执行②之后

①

②

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。

其余操作相同。

(

)

...

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)(用于查找

... ...

data

prior

剩余101页未读，继续阅读

粉丝: 0
资源: 5

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

《数据结构》辅导讲义——严蔚敏版配套

严蔚敏版数据结构讲义

数据结构讲义(严蔚敏版)

数据结构讲义严蔚敏（word版本）

期末复习数据结构讲义pdf

数据结构 算法 讲义 PPT

数据结构与算法python讲义

生成一个基于python的数据结构栈的讲义和教案一级配到代码

传智播客2018c++全套讲义,c基础,c提高,c++基础,linux,c++提高,数据结构等等.

数据结构教程python

csdn北京邮电大学数据结构期末试卷

山东大学 数据结构复习资料 csdn

数据结构与算法黑马程序员\

408数据结构笔记pdf整理

38000词汇讲义word版本

数据结构教学计划编制问题

费曼物理学讲义中文版.doc

浙江大学数据结构878

黑马程序员通讯录管理系统讲义pdf版

02331数据结构讲解视频

c基础讲义2018修订版

最新资源

数据结构算法讲义 PPT

山东大学数据结构复习资料 csdn