博文
05_更多数据结构的课程请用以下网址登录(2006-08-15 21:14:00)
摘要：http://www.cstudyhome.com/datastruct1/index.htm
数据结构......
04_算法效率与存储空间需求(2006-08-15 21:11:00)
摘要：第四课
本课主题： 算法效率的度量和存储空间需求
教学目的： 掌握算法的渐近时间复杂度和空间复杂度的意义与作用
教学重点： 渐近时间复杂度的意义与作用及计算方法
教学难点： 渐近时间复杂度的意义
授课内容：
一、算法效率的度量
算法执行的时间是算法优劣和问题规模的函数。评价一个算法的优劣，可以在相同的规模下，考察算法执行时间的长短来进行判断。而一个程序的执行时间通常有两种方法：
1、事后统计的方法。
缺点：不利于较大范围内的算法比较。（异地，异时，异境）
2、事前分析估算的方法。
程序在计算机上运行所需时间的影响因素
算法本身选用的策略
问题的规模
规模越大，消耗时间越多
书写程序的语言
语言越高级，消耗时间越多
编译产生的机器代码质量
机器执行指令的速度
综上所述，为便于比较算法本身的优劣，应排除其它影响算法效率的因素。
从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。 （原操作在所有该问题的算法中都相同）
T(n)=O(f(n))
上示表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。
求4*4矩阵元素和，T(4)=O(f(4))
f=n*n;
sum(int num[4][4])
{ int i,j,r=0;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
r+=num[i][j]; /*原操作*/
return r;
}
最好情况：
T（4）=O（0）
最坏情况：
T（4）=O（n*n）
ispass(int num[4][4])
{ int i,j;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
if(num[i][j]!=i*4+j+1)
return 0;
return 1;
}
原操作执行次数和包含它的语句的频度相同。语句的频度指的是该语句重复执行的次......
03_算法(2006-08-15 21:09:00)
摘要：转自（http://www.cstudyhome.com/datastruct1/class03/class03.htm）
第三课
本课主题： 算法及算法设计要求
教学目的： 掌握算法的定义及特性，算法设计的要求
教学重点： 算法的特性，算法设计要求
教学难点： 算法设计的要求
授课内容：
一、算法的定义及特性
1、定义：
ispass(int num[4][4])
{ int i,j;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
if(num[i][j]!=i*4+j+1)/*一条指令，多个操作*/
return 0;
return 1;
}/*上面是一个类似华容道游戏中判断游戏是否结束的算法*/
算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作；此外，一个算法还具有下列五个重要特性：
2、算法的五个特性：
有穷性
一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成；
确定性
算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。有任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
可行性
一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
输入
一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。
输出
一个算法有一个或多个的输出。这些输出是同输入有着某些特定关系的量。
例：
有穷性
haha()
{/*only a joke,do nothing.*/
}
main()
{printf("请稍等...您将知道世界的未日...");
while(1)
haha();
}
确定性
float average(int *a,int num)
{int i;long sum=0;
for(i=0;i<num;i++)
sum+=*(a++);
return sum/num;
}
main(......
02_抽象数据类型的表示和实现(2006-08-15 21:07:00)
摘要：第二课
本课主题： 抽象数据类型的表示与实现
教学目的： 了解抽象数据类型的定义、表示和实现方法
教学重点： 抽象数据类型表示法、类C语言语法
教学难点： 抽象数据类型表示法
授课内容：
一、抽象数据类型定义（ADT）
作用：抽象数据类型可以使我们更容易描述现实世界。例：用线性表描述学生成绩表，用树或图描述遗传关系。
定义：一个数学模型以及定义在该模型上的一组操作。
关键：使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。
例：线性表这样的抽象数据类型，其数学模型是：数据元素的集合，该集合内的元素有这样的关系：除第一个和最后一个外，每个元素有唯一的前趋和唯一的后继。可以有这样一些操作：插入一个元素、删除一个元素等。
抽象数据类型分类
原子类型
值不可分解，如int
固定聚合类型
值由确定数目的成分按某种结构组成，如复数
可变聚合类型
值的成分数目不确定如学生基本情况
抽象数据类型表示法：
一、
三元组表示：（D，S，P）
其中D是数据对象，S是D上的关系集，P是对D的基本操作集。
二、书中的定义格式：
ADT 抽象数据类型名{
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<基本操作的定义>
}ADT 抽象数据类型名
例：线性表的表示
名称
线性表
数据对象
D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}
任意数据元素的集合
数据关系
R1={<ai-1,ai>| ai-1,ai(- D,i=2,...,n}
除第一个和最后一个外，每个元素有唯一的直接前趋和唯一的直接后继
基本操作
ListInsert(&L,i,e)
L为线性表，i为位置，e为数据元素。
ListDelete(&L,i,e)
...
二、类C语言语法
类C语言语法示例
1、预定义常量和类型
#define TRUE 1
#define FAL......
01_数据结构及基本概念(2006-08-15 21:05:00)
摘要：转自（http://www.cstudyhome.com/datastruct1/class01/class01.htm）
第一课
本课主题：数据结构的基本概念和术语
教学目的：了解数据结构的基本概念，理解常用术语
教学重点：基本概念：数据与数据元素
教学难点：数据元素间的四种结构关系。
授课内容：
一、数据、数据元素、数据对象、数据结构的定义
1、数据的定义
定义一：数据是客观事物的符号表示。
学号
姓名
语文
数学
C语言
6201001
张三
85
54
92
6201002
李四
92
84
64
6201003
王五
87
74
73
6201004
...
例：张三的C语言考试成绩为92分，92就是该同学的成绩数据。
定义二：能输入到计算机中并被计算机程序处理的符号的总称。
例：图像、声音等。
总结：现实世界信息的分析、复制、传播首先要符号化，这样才便于处理，尤其是便于计算机的处理。家长、社会要了解一个学生的学习成绩和能力，要看他的学习档案，而学习档案即是说明该学生学习情况的数据。
2、数据元素、数据项
数据元素是数据的基本单位，它也可以再由不可分割的数据项组成。如图示：
3、数据对象
是性质相同的数据元素的集合。如上例：一个班级的成绩表可以看作一个数据对象。
4、数据结构
定义一、数据元素集合（也可称数据对象）中各元素的关系。
定义二、相互之间存在特定关系的数据元素集合。
数据结构的种类：
特征
示例
集合
元素间为松散的关系
线性结构
元素间为严格的一对一关系
如上面的成绩表中各元素
树形结构
元素间为严格的一对多关系
图状结构（或网状结构）
元素间为多对多关系
数据结构的形式定义：
数据结构名称=（D，S）
其中D为数据元素的有限集，S是D上关系的......