《数据结构与算法(C语言版)》教学参考（合集）

模块1数据结构概述

教学要求:

(1)了解数据结构的概念，熟悉数据结构的研究内容。

(2)会用逻辑结构描述数据，能够熟练地说出数据的存储结构。

(3)掌握算法的特性和效率，能够对算法进行分析。

(4)熟练掌握数据结构与算法的关系。

教学重点：

数据结构中的一些基本术语、逻辑结构的描述、数据的存储结构、数据类型、算法的描述及

复杂度分析。

教学难点：

数据的存储结构、算法描述和复杂度分析。

课时安排：

本模块安排4课时。其中，理论讲授2课时，上机实验2课时。

教学大纲：

模块1数据结构概述

案例导入

案例分析

相关知识

1.1什么是数据结构

1.1.1从数据结构实例认识数据结构

1.1.2数据结构的研究内容

1.2逻辑结构的描述

1.3数据的存储结构

1.4算法和算法分析

1.4.1算法特性

1.4.2算法的效率

1.4.3算法效率的评价

1.5数据结构与算法的关系

案例实施

案例总结

思考与练习

主要概念：

1.数据

2.数据元素

3.数据项

4.数据对象

5.数据结构

6.数据的逻辑结构

7.集合

8.线性结构

9.树状结构

10.图状结构

11.数据的存储结构

12.非线性结构

13.位

14.字节

15.字

16.位串

17.结点

18.数据域

19.顺序存储

20.链式存储

21.数据类型

22.原子类型

23.结构类型

24.抽象数据类型

25.算法

26.算法的5个特性

27.算法描述

28.类C语言

29.算法的时间复杂度

30.事前分析估算法

31.事后统计法

32.算法的空间复杂度

33.算法设计的要求

实验：

实验编写程序实现算法，熟悉数据结构的有关概念(2学时)

1.试编写算法，完成从大至小依次输出顺序读入的三个整数x,y,z的值，并将此算法用

程序设计语言实现。

2.试编写算法，完成复数的加、减操作，并用程序设计语言实现。有关抽象数据类型的描

述如下：

【复数抽象数据类型ADT的描述】

ADTcomplex{

数据对象：D={cl,c2cl,c2eFloatSet}

数据关系：R={clc2}

基本操作：

创建一个复数Create(a);

输出一个复数Outputc(a);

求两个复数相加之和Add(a,b);

求两个复数相减之差Sub(a,b);

等等；

}ADTcomplex;

【部分实现的源码】

〃存储表示,结构体类型的定义

typedefstruct{

floatx;〃实部子域

floaty;//虚部的实系数子域

}comp;

//全局变量的说明

compa,b,al,bl;

intz;

〃子函数的原型声明

voidCreate(comp*c);

voidOutputc(compa);

compAdd(compk,comph);

compSub(compk,comph);

〃主函数

main(){

Create(&a);

Outputc(a);

Create(&b);

Outputc(b);

al=Add(a,b);

Outputc(al);

al=Sub(a,b);

Outputc(al);

}//main

〃创建一个复数

voidCreate(comp*c){

floatcl,c2;

printf(〃输入实部realx=");

scanf&cl);

printf(〃输入虚部xvpuy=〃)；

scanf&c2);

(*c).x=cl;

c->y=c2;

}//Create

〃输出一个复数

voidOutputc(compa){

printf("\n%f+%fi\n\n〃，a.x,a.y);

}//Outputc

〃求两个复数相加之和

compAdd(compk,comph){

〃程序需要实现的内容

}//Add

compSub(compk,comph){

〃程序需要实现的内容

}//Sub

模块2线性表

教学要求：

(1)了解线性表的定义，熟练掌握线性表的操作。

(2)掌握线性表的顺序存储。

(3)掌握线性表的链式存储。

教学重点：

线性表的顺序存储及其基本操作；线性表的链式存储及其基本操作。

教学难点：

线性表的链式存储结构。

课时安排：

本模块安排8课时。其中，理论讲授4课时，上机实验4课时。

教学大纲：

模块2线性表

案例导入

案例分析

相关知识

2.1线性表的定义与操作

2.1.1线性表的定义

2.1.2线性表的操作

2.2线性表的顺序存储

2.2.1顺序表

2.2.2顺序表上基本运算的实现

2.2.3顺序表基本运算的算法

2.3线性表的链式存储

2.3.1线性单链表

2.3.2线性表上基本运算的实现

2.3.3其他形式的链表

案例实施

案例总结

思考与练习

主要概念：

1.第一元素

2.最后元素

3.线性表

4.记录（结点）

5.文件

6.线性表的特性

7.线性表的抽象数据类型

8.顺序表

9.顺序表的初始化操作

10.顺序表的插入操作

11.顺序表的删除操作

12.链表

13.头结点

14.单链表

15.单链表的建立操作

16.单链表的查找操作

17.单链表的插入操作

18.单链表的删除操作

19.循环链表

20.循环链表的基本操作

21.双向链表

22.双循环链表

23.双向链表的插入操作

24.双向链表的删除操作

实验：

实验编写程序求解问题，掌握线性表的存储结构（4课时）

狐狸逮兔子问题：围绕着山顶有10个圆形排列的洞，狐狸耍吃兔子，兔子说：“可以，但必

须找到我，我就藏身于这十个洞中，你先至U1号洞找，第二次隔1个洞（即3号•洞）找，第

三次隔2个洞（即6号洞）找，以后如此类推，次数不限。”但狐狸从早到晚进进出出了1000

次，仍没有找到兔子。编写算法找出兔子究竟藏在哪个洞里，并用程序语言实现算法？（提

示：这实际上是一个反复查找线性表的过程。）

【数据描述】

定义一个顺序表，用具有10个元素顺序表来表示这10个洞。每个元素分别表示围着山顶的

一个洞，下标为洞的编号。

ttdefineLIST_INITSIZE10〃线性表存储空间的初始分配量

typedefstruct{

ElemType*elem;〃存储空间基址

intlength;〃当前长度

intlistsize;〃当前分配的存储容量（以sizeof（ElemType）为单位）

}SqList;

【算法描述】

statusInitList_Sq(SqList&L)(〃构造一个线性表L

L.elem=(ElemType)malloc(LIST_INIT_SIZE*sizeof(ElemType));

If(!L.elem)returnOVERFLOW;//存储分配失败

L.length=0;〃空表长度为0

L.listsize=LIST_INIT_SIZE;〃初始存储容量

returnOK;

}//InitList_Sq

statusRabbit(SqList&L){〃构造狐狸逮兔子函数

intcurrent=0;〃定义一个当前洞口号的记数器，初始位置为第一个洞口

for(i=0;i<LIST_INIT_SIZE;i++)

L.elem[i]=l;〃给每个洞作标记为1,表示狐狸未进之洞

L.elem[LISTINITSIZET]=L.elem[0]=0;〃首先进入第一个洞，标记进过的洞为0。

for(i=2;i<=1000;i++){

current=(current+i)%LIST_INIT_SIZE;〃实现顺序表的循环引用

L.elem[i]=0;〃标记进过的洞为0

}〃第二次隔1个洞找，第三次隔2个洞找，以后如此类推，经过一千次

printf（"兔子可能藏在如下的洞中：”）

for(i=0;i<LISTINITSIZE;i++)

if(L.elem[i]==l)

printf(a第%d个洞\n”，i+1);〃输出未进过的洞号

returnOK;

}//end

【源代码】

#include<stdio.h>

#include<stdlib.h>

MefineOK1

#defineOVERFLOW-2

typedefintstatus;

typedefintElemType;

#defineLIST_INIT_SIZE10〃线性表存储空间的初始分配量

typedefstruct{

ElemType*elem;〃存储空间基址

intlength;〃当前长度

intlistsize;〃当前分配的存储容量(以sizeof(ElemType)为

单位)

}SqList;

statusInitList_Sq(SqList*L){〃构造一个线性表L

(*L).elem=(ElemType*)malloc(LISTINITSIZE*sizeof(ElemType));

if(!((*L).elem))returnOVERFLOW;〃存储分配失败

(*L).lengths;〃空表长度为0

(*L).listsize=LIST_INIT_SIZE;〃初始存储容量

returnOK;

}//InitList_Sq

statusRabbit(SqList礼){〃构造狐狸逮兔子函数

inti,currents;〃定义一个当前洞口号的记数器，初始位置为第一个洞口

for(i=0;i<LIST_INITSIZE;i++)

(*L).elem[i]=l;〃给每个洞作标记为1,表示狐狸未进之洞

(*L).elem[LISTINITSIZE-1]=O;

(*L).elem[O]=O;〃第一次进入第一个洞，标记进过的洞为0

for(i=2;i<=1000;i++){

current=(current+i)%LIST_INITSIZE;//实现顺序表的循环引用

(*L).elem[current]=O;〃标记进过的洞为0

}〃第二次隔1个洞找，第三次隔2个洞找，以后如此类推，经过一千次

printf("\n兔子可能藏在如下的洞中：“);

for(i=0;i<LIST_INIT_SIZE;i++)

if((*L).elem[i]=l)

printfC\n此洞是第%d号洞”，i+1)；〃输出未进过的洞号

returnOK;

)

voidmain()

(

SqList*L;

InitList_Sq(L);

Rabbit(L);

getchO;

)

【运行结果】

最后的输出结果为：2479

【实验总结】

本算法思路比较简单，采用了顺序表表示围着山顶的10个洞，首先对所有洞设置标志为1,

然后通过1000次循环，对每次所进之洞修改标志为0,最后输出标志为1的洞。

模块3栈

教学要求：

（1）了解栈的定义，掌握栈的运算。

（2）掌握栈的存储和实现。

（3）能够利用栈进行数制转换、表达式求值、递归调用等。

教学重点：

顺序栈的操作；链栈的操作；栈的递归。

教学难点：

链栈的操作；栈的递归。

课时安排：

本章安排8课时。其中，理论讲授4课时，上机实验4课时。

教学大纲：

模块3栈

案例导入

案例分析

相关知识

3.1栈的定义和运算

3.1.1栈的定义

3.1.2栈的运算

3.2栈的存储和实现

3.2.1顺序栈的实现

3.2.2链栈

3.3栈的应用举例

3.3.1数制转换

3.3.2表达式求值

3.3.3递归调用

案例实施

案例总结

思考与练习

主要概念：

1.栈

2.栈顶

3.栈底

4.进栈

5.出栈

6.LIFO(lastinfirstout)

7.顺序栈

8.顺序栈的初始化操作

9.顺序栈的判空操作

10.顺序栈求栈长操作

11.顺序栈取栈顶元素操作

12.顺序栈的进栈操作

13.上溢

14.顺序栈出栈操作

15.链栈

16.链栈的初始化操作

17.链栈的判空操作

18.链栈取栈顶元素操作

19.进栈操作

20.出栈操作

21.栈的递归

实验：

实验栈的算法实现(4学时)

编程实现本模块案例导入中的算法。

模块4队列

教学要求：

(1)了解队列的概念，掌握队列的基本运算。

(2)掌握队列的存储实现及运算实现。

(3)熟悉队列的应用。

教学重点：

顺序队列的基本操作；链队列的基本操作。

教学难点：

链队列的基本操作。

课时安排：

本章安排8课时。其中，理论讲授4课时，上机实验4课时。

教学大纲：

模块4队列

案例导入

案例分析

相关知识

4.1队列的概念和基本运算

4.1.1队列的概念

4.1.2队列的基本运算

4.2队列的存储实现及运算实现

4.2.1顺序队列

4.2.2链队列

4.3队列应用举例

案例实施

案例总结

思考与练习

主要概念：

1.队列

2.FIFO(firstinfirstout)

3.队头

4.队尾

5.顺序队列

6.溢出

7.真溢出

8.假溢出

9.链队列

10.链队列的初始化操作

11.链队列的判空操作

12.链队列的入队操作

13.链队列的出队操作

14.链队列的销毁操作

实验：

实验队列的算法实现（4学时）

编程实现本模块中案例导入的算法;

模块6图

教学要求:

(1)了解图的定义，熟悉图的相关术语，掌握图的基本操作。

(2)掌握图的存储表示。

(3)掌握图的深度优先遍历和广度优先遍历。

(4)掌握图的连通性。

(5)熟悉最短路径确定方法。

教学重点：

图的基本术语；有关图的定理；图的存储结构；图常用的两种遍历方法；最小生成树；最短

路径问题求解。

教学难点：

图常用的两种遍历方法；最小生成树的构造；最短路径问题的求解。

课时安排：

本章安排10课时。其中，理论讲授7课时，上机实验3课时。

教学大纲：

模块6图

案例导入

案例分析

相关知识

6.1图的定义、术语及基本操作

6.1.1图的定义

6.1.2图的相关术语

6.1.3图的基本操作

6.2图的存储表示

6.2.1邻接矩阵

6.2.2邻接表

6.3图的遍历

6.3.1深度优先遍历

6.3.2广度优先遍历

6.4图的连通性

6.4.1无向图的连通分量和生成树

6.4.2最小生成树

6.5最短路径

案例实施

案例总结

思考与练习

主要概念：

1.图

2.有向图

3.无向图

4.混合图

5.无向完全图

6.有向完全图

7.稀疏图

8.稠密图

9.主子图

10.n阶完全图

11.补图

12.入度

13.出度

14.度

15.路径长度

16.自回路

17.回路（环）

18.简单路径

19.简单回路（简单环）

20.连通图

21.强连通图

22.强连通分量

23.权

24.赋权图

25.欧拉回路

26.欧拉图

27.欧拉通路

28.半欧拉图

29.图的邻接矩阵法

30.图的邻接表法

31.图的遍历

32.深度优先搜索

33.广度优先搜索

34.最小生成树（MST）

35.最短路径问题

36.拓扑排序

37.偏序关系

38.全序关系

实验：

实验一八皇后问题（1学时）

本书附录中上机实验3；

实验二旅行商问题（2学时）

本书附录中上机实验5。

模块7查找

教学要求:

(1)了解查找的基本概念。

(2)掌握静态查找表的使用方法，包括顺序查找、二分查找和分块查找。

(3)掌握动态查找表的使用方法啊，包括二叉排序树和平衡二叉树。

(4)掌握哈希表的使用方法。

教学重点：

几种典型静态查找方法；二叉排序树的定义及有关操作；哈希查找技术。

教学难点：

哈希查找。

课时安排：

本章安排6课时。其中，理论讲授4课时，上机实验2课时。

教学大纲：

模块7查找

案例导入

案例分析

相关知识

7.1查找的基本概念

7.2静态查找表

7.2.1顺序查找

7.2.2二分查找

7.2.3分块查找

7.3动态查找表

7.3.1二叉排序树

7.3.2平衡二叉树

7.4哈希表

7.4.1哈希表与哈希方法

7.4.2哈希函数的构造方法

7.4.3处理冲突的方法

案例实施

案例总结

思考与练习

主要概念：

1.关键字

2.主关键字

3.次关键字

4.查找

5.静态查找

6.动态查找

7.顺序查找

8.折半查找（二分查找）

9.斐波那契查找

10.分块查找

11.平均查找长度（ASL）

12.二叉排序树

13.二叉排序树的查找

14.哈希表

15.哈希查找

16.哈希函数

17.冲突

18.除留余数法

19.直接定址法

20.数字分析法

21.开放定址法

22.链地址法

23.哈希表的装填因子

实验：

实验折半查找算法的实现