计算机软件基础（MOOC版）课件汇总 第1--7章 预备知识---排序.pptx

计算机软件基础;课

程

内

容;;目;;if-else语句的一般形式为：;例：将a和b按从小到大排列;例：将a、b、c按从小到大排列（只写完成该功能的程序段）;例：判断一个数字是奇数还是偶数。;多分支结构和else-if语句;sign(x)符号函数;sign(x)符号函数;三种循环结构;猴子吃桃问题;猴子吃桃问题;猴子吃桃问题;小球落地问题;小球落地问题;水仙花数问题;水仙花数问题（单循环）;水仙花数问题（多重循环）;编写一个求1到100和的程序段，结果放在sum变量中;用循环语句的方式，编写一个求1到100和的程序;编写一个程序，实现输入100个数据求和;编写一个程序，实现输入以0作为结束的任意个数据求和;编写一个程序，实现输入一个班（设40人）的成绩，打印出高于平均分的成绩和人数;输出如下图形;输入行数n，输出如下图形;输入行数n，输出如下图形;输入行数n，输出如下图形;函数（过程和函数）;函数举例;指针的概念;定义如下：;P=x；在这是取地址运算符，把x变量的地址赋给指针变量p

在双目运算中是位运算的按位与运算

;例如：;例如：;例如：;例如：;例如：用指针实现交换;指针和数组;指针和数组;指针和结构体;指针和结构体;指向结构体的指针;链表;每个元素由结点(Node)构成，它包括两个域:数据域（Data）和指针域（next）;单链表的类型定义;;单链表的插入操作（三种情况）

第一种情况：在第一个结点前插入;第二种情况：在链表中间插入;第三种情况：在链表尾部插入;Newnode-next=p-next;

p-next=newnode;

;单链表的删除操作

;编程：实现输出以head为头节点的单链表中所有结点的程序段;;算法设计基本方法—常用算法;算法设计基本方法—枚举法;百元买百鸡——枚举法;百元买百鸡——枚举法;百元买百鸡——枚举法;二、归纳法;三、递推法;例1：阶乘函数

IntFact(n)

{intt=1,i;

for(i=1;i=n;i++)

t=t*i;

returnt;

}

;四、递归法;四、递归法;四、递归法;四、递归法;voidHanoi(intn,a,b,c)

{if(n==1)

move(n,a,c);//一张盘片

else

{Hanoi(n-1,a,c,b);//多张盘片

move(n,a,c);//一张盘片

Hanoi(n-1,b,a,c);//多张盘片

}

}

voidmove(intn,a,c)

{printf(“将%d???盘从%d搬到%d\n”,n,a,c);};五、分治法;六、迭代法;七、回溯法（高级算法）—八皇后问题;七、回溯法（高级算法）—八皇后问题;七、回溯法（高级算法）—八皇后问题;1.1.6算法的复杂度分析

一.算法的后期

在算法中的某些部位插装时间函数time(),

测定算法完成某一功能所花费时间

doublestart,stop;

time(start);

intk=seqsearch(a,n,x);

time(stop);

doublerunTime=stop-start;

printf(“%d%d\n”,n,runTime);;二.算法的事前估计

1.空间复杂度度量

（1）存储空间的固定部分

程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占空间

（2）可变部分

尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用空间、通过new和delete命令动态使用空间;2.时间复杂度度量

运行时间=算法中每条语句执行时间之和。

每条语句执行时间=该语句的执行次数（频度）*语句执行一次所需时间。

语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量，很难确定。

设每条语句执行一次所需时间为单位时间，则一个算法的运行时间就是该算法中所有语句的频度之和。

;;1.1.1算法的四个基本特征：

1.有穷性：

一个算法必须在执行有穷步之后结束

2.确定性：

算法的每一步必须是确切定义的。对于相同输入必须得到相同结果。;1.1.2评价算法：

正确性：对于一切合法输入都能产生满足规格要求的结果

易读性：算法要便于阅读，有助于人们对算法的理解

健壮性：当输入非法数据时，也能正常作出反应和处理

效率和低存储量需求：对相同规模的问题，运行时间短、占用空间少;1.1算法的基本概