资源简介

(共30张PPT)
第10课 遍历列表
——一维列表——
问题：
输入50个学生的某门课程的成绩，打印出低于平均分的学生序号与成绩。
导入新课
一维列表的定义
当列表中每个元素只带有一个下标时，我们称这样的列表为一维列表。
列表的定义格式如下：
类型标识符 列表名[常量表达式]
说明：
　　①列表名的命名规则与变量名的命名规则一致。
　　②常量表达式表示列表元素的个数。可以是常量和符号常量，但不能是变量。
　　例如：
　　int a[10]; //列表a定义是合法的
int b[n]; //列表b定义是非法的
一维列表的定义
int a[10]
其中，a是一维列表的列表名，该列表有10个元素，依次表示为：a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]。需要注意的是：a[10]不属于该列表的空间范围。当在说明部分定义了一个列表变量之后,C++编译程序为所定义的列表在内存空间开辟一串连续的存储单元，每个列表第一个元素的下标都是0，因此第一个元素为第0个列表元素。例如：上例中的a列表在内存的存储如表所示：
一维列表的引用
通过给出的列表名称和这个元素在列表中的位置编号(即下标)，程序可以引用这个列表中的任何一个元素。
一维列表元素的引用格式：
列表名[下标]
例如：若i、j都是int型变量，则
a[5]
a[i+j]
a[i++]
都是合法的元素。
一维列表的引用
说明：
(1)下标可以是任意值为整型的表达式，该表达式里可以包含变量和函数调用。引用时，下标值应在列表定义的下标值范围内。
(2)列表的精妙在于下标可以是变量，通过对下标变量值的灵活控制，达到灵活处理列表元素的目的。
(3)C++语言只能逐个引用列表元素，而不能一次引用整个列表。
　　(4)列表元素可以像同类型的普通变量那样使用，对其进行赋值和运算的操作，和普通变量完全相同。
例如： c[10]=34;实现了给c[10]赋值为34。
一维列表的初始化
列表的初始化可以在定义时一并完成。
格式：类型标识符 列表名[常量表达式]={值1，值2，…}
例如：
　　int a[5]={1,2,3,4,5}
说明：
　　(1)在初值列表中可以写出全部列表元素的值，也可以写出部分。
　　例如：int x[10]={0,1,2,3,4};
　　该方法仅对列表的前5个元素依次进行初始化，其余值为0。
　　(2)对列表元素全部初始化为0，可以简写为：{}。
　　例如：int a[5]={}; 将列表a的5个元素都初始化为0。
一维列表的初始化
一维列表的初始化
【说明】
程序1、程序2和程序3的区别在于列表定义在int main()之外与之内，程序1中列表定义放在int main()之外，其初始值是0值。程序2中列表定义放在int main()之内，其初始值是随机的。程序2中列表定义放在int main()之内，只给a[0]、a[1]赋初值，但后面的a[2]～a[4]元素自动赋0值。
列表的越界
C++语言规定，使用列表时，要注意：
(1)、列表元素的下标值为正整数。
(2)、在定义元素个数的下标范围内使用。
然而，当在程序中把下标写成负数、大于列表元素的个数时，程序编译的时候是不会出错的。例如：
int a[10];
a[-3]=5;
a[20]=15;
a[10]=20;
int k=a[30]
这些语句的语法是正确的，能够通过程序的编译。然而，它们要访问的列表元素并不在列表的存储空间的，这种现象叫列表越界。例如下面程序
列表的越界
#include
using namespace std;
int main()
{
int a[5];
for (int i=0;i<=10;i++)
{
a[i]=i;
cout<}
return 0;
}
一维列表的应用
例5.1 输入n个数,要求程序按输入时的逆序把这n个数打印出来，已知整数不超过100个。也就是说，按输入相反顺序打印这n个数。
一维列表的应用
例5.2 将a列表中第一个元素移到列表末尾,其余数据依次往前平移一个位置。
【分析】为完成题目所要求的操作，其算法应该包括以下几个主要步骤：
　　①把第一个元素的值取出放在一个临时单元 temp中；
　　②通过 a[2]→a[1], a[3]→a[2], a[4]→a[3]，……， a[n]→a[n-1],实现其余元素前移
　 ③将 temp值送入a[n]。
一维列表的应用
参考程序：
一维列表的应用
例5.3 宾馆里有一百个房间，从1-100编了号。第一个服务员把所有的房间门都打开了，第二个服务员把所有编号是2的倍数的房间“相反处理”，第三个服务员把所有编号是3的倍数的房间作“相反处理”…，以后每个服务员都是如此。当第100个服务员来过后，哪几扇门是打开的。（所谓“相反处理”是：原来开着的门关上，原来关上的门打开。）
一维列表的应用
参考程序：
一维列表的应用
例5.4 约瑟夫问题：N个人围成一圈，从第一个人开始报数，数到M的人出圈；再由下一个人开始报数，数到M的人出圈；…输出依次出圈的人的编号。N，M由键盘输入。
一维列表的应用
参考程序：
一维列表的应用
例5.5 输入n个整数,存放在列表a[1]至a[n]中，输出最大数所在位置(n<=10000)。
输入样例：
5
67 43 90 78 32
输出样例：
3
一维列表的应用
参考程序：
一维列表的应用
例5.6 编程输入十个正整数，然后自动按从大到小的顺序输出。（冒泡排序）
【问题分析】
①用循环把十个数输入到A列表中；
②从a[1]到a[10]，相邻的两个数两两相比较，即：
a[1]与a[2]比，a[2]与a[3]比，……a[9]与a[10]比。
只需知道两个数中的前面那元素的标号，就能进行与后一个序号元素（相邻数）比较，可写成通用形式a[i]与a[i+1]比较，那么，比较的次数又可用1～( n-i )循环进行控制(即循环次数与两两相比较时前面那个元素序号有关) ；
③在每次的比较中，若较大的数在后面，就把前后两个对换，把较大的数调到前面，否则不需调换位置。
一维列表的应用
下面例举5个数来说明两两相比较和交换位置的具体情形：
5 6 4 3 7 5和6比较，交换位置，排成下行的顺序；
6 5 4 3 7 5和4比较，不交换，维持同样的顺序；
6 5 4 3 7 4和3比较，不交换，顺序不变
6 5 4 3 7 3和7比较，交换位置，排成下行的顺序；
6 5 4 7 3 经过（1～（n-1））次比较后，将3调到了末尾。
经过第一轮的1～ (N-1)次比较，就能把十个数中的最小数调到最末尾位置，第二轮比较1～ (N-2)次进行同样处理，又把这一轮所比较的“最小数”调到所比较范围的“最末尾”位置；……；每进行一轮两两比较后，其下一轮的比较范围就减少一个。最后一轮仅有一次比较。在比较过程中，每次都有一个“最小数”往下“掉”，用这种方法排列顺序，常被称之为“冒泡法”排序。
一维列表的应用
参考程序：
（冒泡排序）
一维列表的应用
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n ) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
1. 算法步骤
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
一维列表的应用
参考程序：
（选择排序）
一维列表的应用
冒泡排序
一维列表的应用
选择排序
一维列表的应用
例5.6 输入N 个正整数，保证每个数在10000以内，输出一共有多少个不同的数。
一维列表的应用
例5.6 输入N 个正整数，保证每个数在10000以内，将这N个数按从小到大的顺序输出。
一维列表的应用
计数排序

展开更多......

收起↑