第1章 绪论 北京师范大学 教育技术学院 杨开城

一、C语言关键库函数(1) int getch(void)； char * gets(char *s); int sscanf (const char *buffer, const char *format [, address, ...]); int sprintf (char *buffer, const char *format [, argument, ...]); void clrscr(void)； void gotoxy(int x，int y)； void textcolor(int newcolor)； int cprintf (const char *format [ , argument, ...]);

一、C语言关键库函数(2) void * malloc(unsigned int size); void free(void * block); FILE *fopen(char *filename, char *mode); int fclose(FILE *stream); char *fgets(char *s, int n, FILE *stream);

二、C语言关键句法(1) typedef语句 typedef int INT; /*INT是别名*/ struct student_info { char name[20]; unsigned int age,gender,class; int grade; }; typedef struct student_info STUDENT; //STUDENT是别名 typedef char STR80[81]; /*STR80是别名*/

二、C语言关键句法(2) 用typedef语句连续定义多个别名 typedef unsigned int INT , WORD; typedef struct student_info { char name[20]; unsigned int age,gender,class; int grade; }STUDENT, *STUDENTPTR;

二、C语言关键句法(3) 指针作为函数参数 void f(int a) { a=3; } void main() int b=0; f(b); printf("%d",b); void f(int *ptr) { *ptr=3; } void main() int b=0; f(&b); printf("%d",b);

二、C语言关键句法(4) 指针作为函数参数 void main() { int a=1,b=2; swap1(a,b); printf("a=%d,b=%d",a,b); /*输出a=1,b=2 */ swap2(&a,&b); printf("a=%d,b=%d",a,b); /*输出a=2,b=1 */ } void swap1(int a ,int b) { int t; t=a; a=b; b=t; } void swap2(int *a, int *b) t=*a; *a=*b; *b=t;

二、C语言关键句法(5) 指针作为函数参数 void geta(int *ptr) { int b; void geta(int x) 假设我们的main函数中，定义了一个int型变量a，并试图通过函数geta来改变这个变量的值，象下面这样定义geta函数是做不到的。 void geta(int x) { int b; scanf("%d",&b); x=b; } void main() { int a; geta(a); . . . } 而应该这样定义geta函数： void geta(int *ptr) { int b; scanf("%d",&b); *ptr=b; } 而在main函数中应该这样调用它： geta(&a);

二、C语言关键句法(6) 指针作为函数参数 typedef struct { void geta(NODE *ptr) int x,y; void geta(NODE n) { int x,y; scanf("%d%d",&x,&y); n.x=x; n.y=y; } void main() NODE a; geta(a);. . . } 应该这样定义geta函数： void geta(NODE *ptr) { int x,y; scanf("%d%d",&x,&y); ptr->x=x; ptr->y=y; } 在main函数中，应该这样调用geta函数： geta(&a);

二、C语言关键句法(7) 指针作为函数参数 void getp(int *ptr) { ptr=(int *)malloc(5*sizeof(int)); } void main() int *p; getp(p); . . . 应该这样定义getp函数： void getp(int **ptr) { *ptr=(int *)malloc(5*sizeof(int)); } 而在main函数中应该这样调用getp函数： getp(&p);

二、C语言关键句法(8) 指针作为函数参数 typedef struct { int x,y; }NODE; void getnode(NODE**ptr) { int x,y; NODE *p; p=(NODE*)malloc(sizeof(NODE)); scanf("%d%d",&p->x,&p->y); *ptr=p; } void main() NODE *p; getnode(&p); . . . }

三、数据结构基本概念和术语(1) 编程任务：已知某高校有N条课程信息需要保存在计算机中供查询之用。课程信息包括“课程编号”、“课程名称”、“主讲教师”、“学分”、“有无实验”等内容。用户可以输入课程名称、学分或者主讲教师等信息进行检索，系统将符合查找要求的课程信息全部显示出来。 需要思考的3个问题： ⑴这个程序需要处理的数据是什么样子的，这些数据之间是一种什么关系？ ⑵这些数据及其关系如何在计算机中表示，即如何存储在内存中？ ⑶根据软件的功能要求，具体如何处理这些存储在内存中的数据？

三、数据结构基本概念和术语(2) 数据对象 数据元素 数据项 需要思考的3个问题： ⑴这个程序需要处理的数据是什么样子的，这些数据之间是一种什么关系？ ⑵这些数据及其关系如何在计算机中表示，即如何存储在内存中？ ⑶根据软件的功能要求，具体如何处理这些存储在内存中的数据？ typedef struct CurriInfo { int ID;/*课程编号*/ char name[40]; /*课程名称*/ char teacher[20]; /*主讲教师*/ int credit; /*学分*/ int exp;/*有无实验，0表示无，1表示有*/ }CURRIINFO; 数据对象 数据元素 数据项

三、数据结构基本概念和术语(3) 需要思考的3个问题： ⑴这个程序需要处理的数据是什么样子的，这些数据之间是一种什么关系？ ⑵这些数据及其关系如何在计算机中表示，即如何存储在内存中？ ⑶根据软件的功能要求，具体如何处理这些存储在内存中的数据？ 做法1 #define N 500 CURRIINFO cf[N]; ID name teacher credit exp 233 计算机基础 陈保国 2 1 245 数据结构 王小小 4 246 离散数学 张名民 3 250 操作系统 李小华 …

三、数据结构基本概念和术语(4) 逻辑结构 存储结构 顺序存储 链式存储 需要思考的3个问题： ⑴这个程序需要处理的数据是什么样子的，这些数据之间是一种什么关系？ ⑵这些数据及其关系如何在计算机中表示，即如何存储在内存中？ ⑶根据软件的功能要求，具体如何处理这些存储在内存中的数据？ 做法2 typedef struct cf_node { CURRIINFO cf; struct cf_node *next; }CFNODE; 逻辑结构 存储结构 顺序存储 链式存储

三、数据结构基本概念和术语(5) 数据（Data） 数据对象（Data Object） 数据元素（Data Element） 数据结构（Data Structure） 逻辑结构 Data_Structure=(D,R) 存储结构 顺序存储结构 链式存储结构

三、数据结构基本概念和术语(6) 逻辑结构 集合 线性结构 树形结构 图形结构

四、数据类型和抽象数据类型 数据类型明确地或者隐含地规定了数据的取值范围以及在这些值上的操作。 抽象数据类型(Abstract Data Type)是指一个数据结构以及定义在这个数据结构上的一组操作。 任何高级语言中的基本数据类型都是抽象数据类型。抽象数据类型是一种逻辑上的数据类型定义，与在计算机处理器内部的实现细节无关。 抽象数据类型的形式化描述通常采用三元组的方式： ADT=(D,R,P)

五、算法与算法分析(1) 算法(Algorithm)是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令代表一个或多个功能相对独立和完整的操作。 算法具有下面五个重要特性： ⑴有零个或多个输入 ⑵有一个或多个输出 ⑶确定性 ⑷有穷性 ⑸可行性

五、算法与算法分析(2) 算法设计的要求 ⑴正确性（Correctness） ⑵可读性（Readability） ⑶健壮性（Robustness） ⑷高效性（efficiency） 时间复杂度 空间复杂度

五、算法与算法分析(3) 时间复杂度 算法的执行时间是问题规模n的函数。 一个算法是由控制结构（顺序、分支和循环三种）和原操作构成的。 为了比较针对同一问题的不同算法，我们从算法中选取一种对于所处理的问题来说是基本操作的原操作，用它的重复执行的次数作为算法的执行时间量度。

五、算法与算法分析(4) 时间复杂度 原操作是比较操作 算法总的比较次数： 设存在这样一个函数f(n)，使得存在两个常数c和n0，对于所有n≥n0时, T(n) ≤cf(n) ，这时将T(n)记作 f(n)通常是T(n)中变化最快的一项。我们将其称为算法的时间复杂度 ，选择排序的时间复杂度是O(n2) 常见的时间复杂度： 时间复杂度 计算下面算法的时间复杂度 void SelectSort(int r[],int n) { int i,j,k; int tmp; for(i=0;i<n-1;i++) { k=i; for(j=i+1;j<n;j++) if(r[j]<r[k]) k=j; if(k!=i) { tmp=r[i]; r[i]=r[k]; r[k]=tmp; }

导 航 图(1)

导 航 图(2)

导 航 图(3)

导 航 图(4)

导 航 图(5)