程序设计与算法基础(1).ppt

1、程序设计与算法基础(1),潘爱民 2006/9/18,Contact info,潘爱民 Pan.A 孙方成 F,提纲,程序设计概述 语言基础：C 基本数据结构list,程序设计(programming)概述,什么是程序(program) 软件的执行流，可以理解为指令流，也涉及到环境的信息：输入、输出、存储介质 软件(software) 代码和数据，融入了各种知识，算法，经验，等许多无形的东西 由人来设计程序，是程序设计之艺术,计算机是如何工作的,机器代码,程序在哪里,脑子里的程序 纸带上的程序 磁带中的程序 软盘上的程序 光盘上的程序 硬盘上的程序,内存中的程序,哪一条指令，哪一个数据单元？,

2、刚开始那个？上一个？下一个？还是最后那个？ 第0个？第1个？编号 索引一维，还是二维？ 地址(address)，可寻址的(addressable) 每条指令，每个数据单元都有地址 在有些语言中，称为“指针(pointer)”，或者“引用(reference)”,内存，外存,机器有内存，要执行的代码，以及在执行过程中要用到的数据都在内存中 机器也有外存，很多种，像硬盘、U盘、CD-ROM，等等 一般而言，外存比内存大得多，对于计算机的运行，内存是必不可少的 CPU直接操作内存中的数据，而外存中的数据被换到内存中以后，才能被CPU使用,计算机会做什么,计算，加减乘除，位操作，浮点运算 挪内存中的数

3、据单元,简单智力题：两个空桶，一个能盛5升水，一个能盛3升水， 请问如何准确地量出4升水？,从机器代码开始工作,现在，这种能力接近于特异功能了，虽然实际上，正常人都能学得会,在汇编语言上工作,能够精准地控制计算机做最微小的事情，控制力很强，但工作效率低下 时钟频率的提高，人已经无法手工处理如此巨量的指令,进入高级语言,用高级语言来告诉计算机该做什么 通过编译器，把高级语言的语句翻译成计算机的指令 高级语言更加接近于人们的思考方式，和人们对问题的数学描述 主流的语言：Basic，Fortran，Pascal，C/C+，Java，C#，Python，等等,语言和算法,把想法变成用程序语言来描述的程

4、序代码 进入程序设计(programming)，俗称编程序 算法是一种知识的积累，用于完成一些常见的任务 熟练掌握常用的算法是大学期间的学习任务之一 对于某些算法，清楚其细节，包括其在各种情形下的性能表现,程序设计是一门艺术,在程序设计过程中，除了程序和代码本身，还有许多相关的东西 程序设计中的思想 结构化的思想 面向对象的思想 类型泛化的思想 虚拟机的思想 你的程序是一件艺术品：如何迎接同行审视的目光？,写代码的层次,按照任务指示，写一个没有下家的程序 只要正确地完成功能 写一个给大量用户使用的程序 考虑到用户的各种意外行为，要健壮 写一个可复用的程序组件 对接口的理解和实现，包括错误处理

5、写一个代码库，供自己及同伴使用 预知客户的行为，库的扩展性 写一个开源软件 你的面子全在程序上了,代码的好与坏一段低质量代码,void HandleStuff (CORP_DATA ,参考Code Complete(2nd Edition)，列举了10多个问题,代码的好与坏好的代码,取自于Windows Kernel中的一段代码,课程内容,第一周 概述 语言基础C 基本数据结构-list 第二周 基本数据结构-stack/queue 摸底 第三周 Sort 算法复杂度 第四周 Tree (1),第五周 Tree (2) 第六周 hash 第七周 其他算法：recurrence strcpy(

6、string, Hello world from ),strcat( string, strcpy ); strcat( string, and ); strcat( string, strcat! ); printf( String = %sn, string ); ,C语言特点,结构化 用简单的方法可以构造复杂的结构，强调数据的流动 表达式灵活、简练 提高代码质量、程序的可读性 提供了一些接近于汇编语言的功能及指针 适合于编写系统软件和工具软件；指针非常灵活 调试方便 移植性好 目标代码小、运行效率高,C程序开发过程,进入开发,编辑(edit),编译(compile),出错？,链接(lin

7、k),执行(run),结果正确？,结束,源程序 file.c,目标程序 file.obj,库函数和 其它OBJ,可执行程 序file.exe,Yes,Yes,No,No,演示写一个最简单的C程序,Hello World! 程序 顺序输出命令行参数,C语言基本元素,变量，内存单元的别名：名称+类型 命名规则：字母、下划线和数字的组合(第一个字符不能为数字)，注意大小写有区别 基本数据类型和常数 基本数据类型：char int float double 字符型变量和常数，转义序列、整型、浮点型 算术运算符、赋值运算符 + - * / % + - 赋值运算符(针对左值)：+= -= *= /= %=

8、 控制语句 函数,基本运算,表达式 + - * / % + - 关系运算符 = = != 逻辑运算符 语句b; . 简化条件表达式 表达式1 ? 表达式2 : 表达式3,开关语句(switch) switch (表达式) case 表达式1: 语句1; break; case 表达式2: 语句2; break; . default: 语句 break; ,控制语句例子(续),while语句 while (表达式) 语句 for语句 for(表达式1; 表达式2; 表达式3) 语句 赋初值 结束条件 控制变量行为 do-while语句 do 语句; while (表达式); break, con

9、tinue语句 空操作语句,函数(代替子程序，子模块),完成原程序中一部分基本的功能 提取出来，成为单独的子模块 可以被其他部分的代码反复调用(call/ret指令支持) Call之前保存现场，ret之后恢复现场，在函数中只能看到局部的视图。函数的状态包括：局部变量、参数、返回地址栈帧(stack frame) 典型的模块化设计, Mov Mov Add Sub Inc Mov Mov ,程序,子程序函数,函数(代替子程序、子模块),函数声明和函数定义 函数名、函数参数、函数返回值 BOOL Func(int x, int y); 函数定义(函数体) 调用参数处理：_stdcall _cdec

10、l inline、导入导出函数(MS) extern static 参数、返回值、函数调用 函数库stdio，stdlib.h，math等,函数例子,void main() /* Function prototypes */ long lift( int ), step( int ), drop( int ); void work( int number, long (*function)(int i); int select, count; . . . select = 1; switch( select ) case 1: work( count, lift ); break; case

11、2: work( count, step ); break; case 3: work( count, drop ); /* Fall through to next case */ default: break; ,/* Function definition */ void work( int number, long (*function)(int i) ) int i; long j; for ( i = j = 0; i number; i+ ) j += ( *function )( i ); ,C语言数据类型,基本类型 void、char 、 short 、 int 、 long

12、 、float 、double 、signed 、unsigned 结构struct 联合union 枚举enum typedef 指针,数组,一维数组 int number100; extern int number; 多维数组 int number10010; extern int number10; 结构数组 struct float x, y; complex100;,结构struct,简单结构 struct date int year, month, day; char mon3; ;,匿名结构和嵌套结构 struct phone int areacode; long number;

13、 ; struct person char name30; char sex; int age; int weight; struct phone; /匿名结构 Jim; Jim.number = 1234567;,结构续,结构中的位域 struct mybitfields unsigned a : 4; unsigned b : 5; unsigned c : 7; test; 访问结构中的成员 .操作符 Jim.number = 1234567;,联合union,联合类型 union u_tag int ival; float fval; char *pval; ; 联合与结构的区别 内存

14、分配、引用方式 Union和struct中的成员对齐,枚举类型,枚举类型 enum Days / 声明Days为枚举类型 saturday, / 缺省saturday = 0 sunday = 0, / 指定sunday = 0 monday, / monday = 1 tuesday, / tuesday = 2 wednesday, / 等 thursday, friday today; / 定义变量today为类型Days 使用例子 enum Days yesterday; / C和C+中都合法 Days tomorrow; / C+合法，C非法 yesterday = monday;

15、int i = tuesday; / 合法; i = 2 yesterday = 0; / 非法，不允许 yesterday = (Days)0; / 合法，但结果不确定,typedef,例子 typedef char FlagType; const FlagType x; typedef int (FAR WINAPI *FARPROC)(); typedef int (WINAPI *PROC)(); PROC proc . int retVal = (*proc)();,指针,指针是一个变量，它包含另一个变量的地址，因此，通过指针可以间接地访问另一个变量 int x, *px； / 声明

16、指针 px = 运算符 pa = ,C语言说明,说明 1. 变量说明 extern int global; extern int global = 10; / 定义！ 2. 函数说明 void Func(int x, int y); *隐含说明 *通常#include文件中包含的是函数的说明 3. 结构、联合、枚举类型说明(类class) struct POINT int x; int y; ;,C语言定义,定义 1. 变量定义 int global; 2. 函数定义 void Func(int x, int y) . return; 3. 结构、联合、枚举类型定义(类class) struc

17、t POINT point; struct POINT int x; int y; ;,变量类型,自动变量和外部变量 自动变量：函数中说明的变量 例如，在某个函数内部：auto int i; 特点：定义在函数中，位于栈中，有效期在函数中 外部变量：所有函数外部定义的变量 例如，在函数中说明：extern int i; 特点：定义在函数外，不在栈中，全程有效 静态变量和寄存器变量 静态变量：内部静态变量和外部静态变量 例如：static int i; 特点：变量的连续性，有效期在函数中 分析：有效期和生存期 寄存器变量： 例如：register int i; register char x; 特

18、点： 只能用于自动变量、个数限制、类型限制(int、char,指针),变量类型例子,#include static int i; /* 外部静态变量 */ extern int Total; /* 外部变量，定义在其它文件中*/ int Add(int x, int y) int z; /* 自动变量 */ extern int Total; /* 可以省略 */ z = x + y; Total +; return z; int Sub(int x, int y) int z; /* 自动变量 */ static int SubTime = 0; z = x - y; SubTime +;

19、return z; ,#include int Total = 0; /* 外部变量，定义 */ int main() register int i1, i2; /* 自动变量 */ int Result1, Result2; i1 = 10; i2 = 20; Result1 = Add(i1, i2); Result2 = Sub(i1, i2); printf(“i1 = %d , i2 = %dn”, i1, i2); printf(“Result1 = %d , Result2 = %dn”, Result1, Result2); printf(“Total = %dn”,Total

20、); return 0; ,预处理及其它,格式 换行起分隔符的作用， 续行用“” 注释 用/*开始，用*/结束 在C+中，用/做 宏定义 符号常数定义 格式：#define 符号名 常数/字符串 例如：#define TRUE 1 带参数的宏 #define IS_LEAP_YEAR(y) y%4=0 p-next = head; head = p;,Insert to Tail,head,tail,List_Node *p = CreateNode(); tail-next = p; tail = tail-next;,Remove a node from head,head,tail,As

21、sert(head); List_Node *pOldHead = head; head = head-next; Remove(pOldHead);,Remove a node,在单链表中删除任何位置上的一个节点 要求扫描到该节点的前一个节点,head,tail,List_Node *pPrevNode; pPrevNode = FindPreviousNode(head, pNode) pPrevNode-next = pNode-next; Remove(pNode);,加入、删除节点的注意事项,考虑list是否为空 考虑删除以后，list是否为空 除了-next域，还要正确地维护hea

22、d和tail,从list中获得满足条件的entry,Add和remove是维护list 我们需要GetEntry() 遍历整个list，直到找到满足条件的entry,List_Node *pTmp = head; for(;pTmp != null;) if (pTmp-value = specifiedXX) return pTmp; else pTmp = pTmp-next; return null;,双链表,tail,head,循环链表,循环单链表 循环双链表,head,SkipList,5,7,8,10,12,17,19,22,28,31,33,查找过程 构造和维护过程,List的广泛应用,从系统底层，到应用层的数据管理 系统层： 内核对象的管理 动态对象的管理 应用层： 稀疏表格(矩阵) 各种纪