电子课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,高等教育出版社,信息学奥赛课课通（,C+,）,第,7,单元 基本数据结构,作者：林厚从,信息学奥赛课课通（,C+,）,第,1,课 结构体的引入和应用,学习目标,1.,理解结构体的概念和应用背景。,2.,学会使用结构体解决一些实际问题。,结构体,在存储和处理大批量数据时，一般会使用数组来实现，但是每一个数据的类型及含义必须一样。如果需要把不同类型、不同含义的数据当作一个整体来处理，如,1000,个学生的姓名、性别、年龄、体重、成绩等，怎么处理呢？,C+,提供了结构体（,struct,）来解决这类问题。,1.,结构体的定义,C+,中的结构体是由一系列具有相同类型或不同类型的数据构成的数据集合，也叫结构。,使用结构体，必须要先声明一个结构体类型，再定义和使用结构体变量。结构体类型的声明格式如下：,struct,类型名,数据类型,1,成员名,1;,数据类型,2,成员名,2;,;,定义结构体变量,定义结构体变量格式如下：,struct,结构体类型名 变量名列表,;,也可以把结构体类型声明和变量定义合在一起，格式如下：,struct,类型名,数据类型,1,成员名,1;,数据类型,2,成员名,2;,变量名,;,2.,结构体的使用,结构体变量具有以下特点：,（,1,）可以对结构体变量的整体进行操作。,例如：,swap(ai,aj),（,2,）可以对结构体变量的成员进行操作。,引用结构体变量中成员的格式为：,结构体变量名,.,成员名,（,3,）结构体变量的初始化方法与数组类似。,例,1,、学生信,息,【,问题描述,】,输入一个学生的信息，包括姓名、性别、年龄、体重，再输出这些信息。,【,输入格式,】,一行，依次是学生的姓名、性别、年龄、体重。,【,输出格式,】,一行，依次是姓名、性别、年龄、体重（体重保留一位小数）。,【,输入样例,】,zhangsan,m 20 90.5,【,输出样例,】,zhangsan,m 20 90.5,/p7-1-1,#include,using namespace std;struct student,string name;,char sex;,int age;,double weight;,;,int main(),student stu;,cin stu.name stu.sex stu.age stu.weight;,cout stu.name “stu.sex “stu.age “;,cout fixed setprecision(1)stu.weight n;,for(int i=1;i ai.name ai.sex ai.year ai.month;,for(int i=1;i=n;i+),for(int j=i+1;j=n;j+),if(ai.year aj.year|ai.year=aj.year&ai.month aj.month),swap(ai,aj);,for(int i=1;i=n;i+),cout ai.name ”ai.sex ”;,cout ai.year ”ai.month n;,sum.hr=sum.minut=sum.sec=0;,for(int i=1;i stu.hr stu.minut stu.sec;,sum=sum+stu;/,两个结构体,sum,和,stu,通过重载,+,运算符进行加法运算,cout sum.hr ”hour”sum.minut ”minute”sum.sec name heigh num;,void output(),cout name “heigh “num n;,for(int i=1;i maxn.heigh)maxn=ai;,else if(ai.heigh=maxn.heigh,maxn.output();,return 0;,实践巩固,第,3,课 共用体的引入和应用,学习目标,1.,理解共用体的概念和应用背景。,2.,学会使用共用体解决一些实际问题。,共用体,在,C+,中，共用体也称联合（,union,），是一种数据格式，能存储不同类型数据，但同一时间只能存储其中的一种类型数据。例如，存放一个人的信息，如果是成年人，存放他的身份证号码；否则，存放他的学籍号这里面就有两个成员，但是任何一个人只能使用其中的一个。,使用共用体前必须先声明一个共用体类型，才可以定义和使用共用体变量。例如，要声明一个记录个人信息的共用体，可以这样：,union person /,声明一个共用体类型,person,char id18;/,声明一个字符数组，存储身份证号码,int num;/,声明一个整数，存放学籍号,;,例,1,、成绩统计,【,问题描述,】,兴趣小组收集学员成绩信息，每个学员的成绩有两种表示方法，一种用,best,、,good,、,poor,三种等级来表示，还有一种就是直接用分数来表示（百分制）。请保存学员成绩信息，并且统计有多少人是用等级来表示成绩的，用分数来表示成绩的人的平均分是多少（取整就行）。,【,输入格式,】,第,1,行一个正整数,n,，表示学员人数，,n1000,。,第,2n+1,行，每行一个字符和一个字符串，中间用一个空格隔开。第一个字符表示这个学生成绩类型，有,C,、,N,两种分别代表等级表示和分数表示，第二个字符串表示成绩信息。,【,输出格式,】,一行两个整数，分别表示用等级表示成绩的人数和用分数表示成绩人的平均分（取整），中间用一个空格隔开。,【,输入样例,】,5,C best,C good,N 90,C poor,N 98,【,输出样例,】,3 94,/p7-3-1,#include,using namespace std;,int main(),union res/,声明一个共用体,res,char rank5;/,用等级表示成绩,int x;/,用分数表示成绩,;,struct stu,char f;/,代表学生用哪种方式记录成绩,res score;/,定义,score,为共用体,;,stu a1001;,int n,count=0,num=0;,cin n;,for(int i=1;i ai.f;,switch(ai.f),case C :for(int j=0;j ai.score.rankj;,count+;,break;,case N :cin ai.score.x;,num+=ai.scorex;,cout count ”num/(n-count),变量名,;/,或,fout n;,for(int i=1;i x;,if(x%2=1)s1+=x;,else s2+=x;,fout s1 endl s2 endl;,fin.close();,fout.close();,return 0;,2.,文件的重定向,在,C+,中，,cin,使用的输入设备是键盘，称之为“标准输入（,stdin,）”。,cout,使用的输出设备是显示器，称之为“标准输出（,stdout,）”。,C+,可以使用,freopen,函数把,stdin,和,stdout,重新定向到某一个指定的文件，使原来的标准输入、输出变成指定文件的输入、输出。具体语句格式为：,freopen(“,输入流文件名”,”r”,stdin);,freopen(“,输出流文件名”,”w”,stdout);,经过重定向后，任何对,stdin,、,stdout,的操作都变成了对输入流文件、输出流文件的操作。,例,2,、替换型密码,【,问题描述,】,简单的替换型密码是很弱的，它通过将每个字母替换成另外一个字母来加密一个字母组成的信息。考虑下面的替换型密码描述：,ABCDEFGHIJKLMNOPQRSTUVWXYZ,NOPQRSTUVWXYZABCDEFGHIJKLM,这样的描述表示当输入中出现“,A”,的时候，输出中应该出现的是“,N同理，每个“,B”,都变成“,O”,，以此类推，一直到“,Z”,都变成“,M”,。这个特殊的替换型密码的例子被称为“,rot13”,（旋转,13rotate-13,的简称），有一个有趣的特性：它是自解密的。将信息再加密一次就会得到原始的信息。这样的密码中，单词“,CAT”,就会成为“,PNG”,。而句子“,NOW IS THE TIMEFOR ALL GOOD PEOPLE TO PROGRAM WELL.”,就成了“,ABJ VF GUR GVZR SBE NYY TBBQCRBCYR GB CEBTENZ JRYY.”,。注意，所有的空格、标点符号以至于任何不在字符集,AZ,中的字符都不变。,请写一个程序来实现替换型密码。,【,输入格式,】,第,1,行：没有空格隔开的乱序的,26,个字母,AZ,，这些字母被用于描述替换型密码。,第,2,行：一段长度在,180,之间的内容，这段内容将被加密。不会有小写字母出现。标点符号、空格和数字都可能出现。没有奇怪的字符（像退格、响铃字符之类）出现。,【,输出格式,】,一行输入内容加密后的一行文本。,【,输入样例,】,NOPQRSTUVWXYZABCDEFGHIJKLM,NOW IS THE TIME FOR ALL GOOD PEOPLE TO PROGRAM WELL.,【,输出样例,】,ABJ VF GUR GVZR SBE NYY TBBQ CRBCYR GB CEBTENZ JRYY.,/p7-4-2,#include,using namespace std;,int main(),freopen(“subcip.in”,”r”,stdin);,freopen(“subcip.out”,”w”,stdout);,string s,pass;,getline(cin,pass);,getline(cin,s);,for(int i=0;i s.size();i+),if(isupper(si)si=passsi-65;,cout s x,）来不断读入数据，直到文件里所有数据都读完为止。,/p7-4-3,#includeusing namespace std;,int main(),int x,s=0;,freopen(“odd.in”,”r”,stdin);,freopen(“odd.out”,”w”,stdout);,while(cin x),if(x%2=1)s+;,cout s endl;,return 0;,实践巩固,第,5,课 队列,学习目标,1.,理解队列的概念及其基本操作。,2.,学会使用队列解决一些实际问题。,队列,队列是一种操作（或者说运算）受到限制的特殊线性表。其插入操作限定在表的一端进行，称为“入队”；其删除操作则限定在表的另一端进行，称为“出队”。插入一端称为队尾（,rear,）；删除一端称为队头（,front,）。,队列,队列也被称作“先进先出”线性表（,FIFO,，,First In First Out,）。类似于生活中排队购票，先来先买，后来后买。,在不断入队、出队的过程中，队列将会呈现出以下几种状态：,队空：队列中没有任何元素。,队满：队列空间已全被占用。,溢出：当队列已满，却还有元素要入队，就会出现“上溢（,overflow,）”；当队列已空，却还要做“出队”操作，就会出现“下溢（,underflow,）”。两种情况合在一起称为队列的“溢出”。,1.,队列的基本操作（具体参见教材,245,页,-,246,页）,（,1,）初始化,（,2,）判空,（,3,）求队列中实际元素的个数,（,4,）入队，入队操作前，需要判断队列是否已满,（,5,）出队，出队操作前，需要判断队列是否为空,（,6,）取队首元素,2.,循环队列,随着入队与出队操作的不断进行，队头指针在数组中不断向队尾方向移动，而在队头前面产生了一片不能利用的“空闲区”，当队尾指针指向数组最后一个位置，即,rear=maxn,时，如果再有元素入队就会出现“溢出”，这种溢出称作“假溢出”。,如何解决这种情况呢？一种方法是每次出队操作时，都向“空闲区”整体移动一位，带来的后果是时间复杂度高了；另一种方法是让数组首尾相连，形成“环”状，即所谓的“循环队列”。,2.,循环队列,循环队列初始时，,front=rear=0,，如果,maxn,个元素一个个依次入队，则,rear=maxn,，此时再有元素入队，则它会被存放在,q0,这个单元，也会出现,front=rear=0,，与队空时的状态一样。解决方法是少用一个元素空间，约定数据入队前，测试“队尾指针在循环意义下加,1,后是否等于头指针”作为判断“队满”的条件。循环队列的实际长度为,(rear-front+maxn),%maxn,。,循环队列的重要操作修改如下,(,使用,q0,这个单元,),：,（,1,）判断队满：如果,(rear+1),%maxn=front,，则队列已满。,（,2,）入队：如果队列未满，则执行：,rear=(rear+1),%maxn,；,qrear,=x,；,（,3,）出队：如果队列不为空，则执行：,front=(front+1),%maxn,；,3.,队列的应用举例,例,1,、周末舞会,【,问题描述,】,假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲只能有一对跳舞者。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。,【,输入格式,】,第,1,行两个正整数，表示男士人数,m,和女士人数,n,，,1m,，,n1000,；,第,2,行一个正整数，表示舞曲的数目,k,，,k1000,。,【,输出格式,】,共,k,行，每行两个数，之间用一个空格隔开，表示配对舞伴的序号，男士在前，女士在后。,【,输入样例,】,2 4,6,【,输出样例,】,1 1,2 2,1 3,2 4,1 1,2 2,【,问题分析,】,显然，舞伴配对的顺序符合“先进先出”，所以用两个队列分别存放男士队伍和女士队伍。然后，模拟,k,次配对：每次取各队队头元素“配对”输出，并进行“出队”和重新“入队”操作。,参考程序参见教材,247,页,-248,页。,例,2,、取牌游戏,【,问题描述,】,小明正在使用一堆共,K,张纸牌与,N-1,个朋友玩取牌游戏。其中，,NK100000,，,2N100,，,K,是,N,的倍数。纸牌中包含,M=K/N,张“,good”,牌和,K-M,张“,bad”,牌。小明负责发牌，他当然想自己获得所有“,good”,牌。,他的朋友怀疑他会欺骗，所以他们给出以下一些限制，以防小明耍诈：,1,）游戏开始时，将最上面的牌发给小明右手边的人。,2,）每发完一张牌，他必须将接下来的,P,张牌（,1P10,）一张一张地依次移到最后，放在牌堆的底部。,3,）以逆时针方向，连续给每位玩家发牌。,小明迫切想赢，请你帮助他算出所有“,good”,牌放置的位置，以便他得到所有“,good”,牌。牌从上往下依次标注为,#1,，,#2,，,#3,，,【,输入格式,】,第,1,行，,3,个用一个空格间隔的正整数,N,、,K,和,P,。,【,输出格式,】,M,行，从顶部按升序依次输出“,good”,牌的位置。,【,输入样例,】,3 9 2,【,输出样例,】,3,7,8,【,问题分析,】,方法,1,、利用普通队列模拟。,结合题目中的条件,1,和,3,，可以推出“小明是第,n,个拿到牌的”，根据数据范围大致推出队列存储容量上界为,K+10 N (100000/N),=1100000,。,参考程序参见教材,248,页,-249,页。,方法,2,、利用循环队列模拟实现。,参考程序参见教材,249,页,-250,页。,实践巩固,第,6,课 队列的应用,学习目标,1.,使用队列解决一些实际应用问题。,2.,学会用队列实现简单的宽度优先搜索。,例,1,、,Blah,数集,【,问题描述,】,数学家高斯小时候偶然间发现一种有趣的自然数集合,Blah,。对于以,a,为基的集合,Blah,定义如下：,1,）,a,是集合,Blah,的基，且,a,是,Blah,的第一个元素；,2,）如果,x,在集合,Blah,中，则,2x+1,和,3x+1,也都在集合,Blah,中；,3,）没有其他元素在集合,Blah,中了。,现在小高斯想知道如果将集合,Blah,中元素按照升序排列，第,n,个元素会是多少？注意：集合中没有重复的元素。,【,输入格式,】,一行两个正整数，分别表示集合的基,a,以及所求元素序号,n,，,1a50,，,1n1000000,。,【,输出格式,】,一行一个正整数，表示集合,Blah,的第,n,个元素值。,【,输入样例,1】,1 100,【,输出样例,1】,418,【,输入样例,2】,28 5437,【,输出样例,2】,900585,【,问题分析,】,根据条件，除了第一个数,a,以外，可以把数集,q,的所有数分成两个子集，一个是用,2x+1,来表示的数的集合,1,，另一个是用,3x+1,来表示的数的集合,2,，两个集合要保持有序非常容易，只需用两个指针,two,和,three,来记录。其中,two,表示集合,1,下一个要产生的数是由,qtwo,*,2+1,得到，,three,表示集合,2,下一个要产生的数是由,q,three,*,3+1,得到。接下来比较,qtwo,*,2+1,和,qthree,*,3+1,的大小关系：,1,）如果,qtwo,*,2+1 qthree,*,3+1,，则把,qthree,*,3+1,加入数集中。,3,）如果,qtwo,*,2+1=qthree,*,3+1,，则取任意其一加入数集中即可。,所以，本题就是利用队列先进先出的特点，模拟,n,个数依次产生的过程。,/p7-6-1,#include,using namespace std;,int q1000011;,int main(),int a,n,x,two,three,rear;,cin a n;,two=three=rear=1;,q1=a;,while(rear!=n),if(2*qtwo+1 3*qthree+1),rear+;,qrear=3*qthree+1;,three+;,else if(2*qtwo+1 3*qthree+1),rear+;,qrear=2*qtwo+1;,two+;,else,rear+;,qrear=3*qthree+1;,two+;three+;,cout qn n x y;,for(i=1;i=n;i+),for(j=1;j aij;,f=r=1;,qf0=x;qf1=0;,px=false;,while(f=r),tmp=qf0;,if(tmp=y),cout qf1-1 endl;,return 0;,for(,i,=1;,i,n;,for(int i=1;i=n;i+),for(int j=1;j aij;,cout 1;,q1=1;h1=1;,for(int l=1,r=1;l=r;l+),int u=ql;,for(int i=1;i=n;i+),if(aui&!hi),cout -i;,q+r=i;,hi=1;,return 0;,实践巩固,第,7,课 栈,学习目标,1.,理解栈的概念及其基本操作。,2.,学会使用栈解决一些实际问题。,栈也是一种操作（或者说运算）受到限制的特殊线性表。其插入和删除操作都限制在表的一端进行，这一端被称为“栈顶（,top,）”，相对的另一端称为“栈底（,bottom,）”。插入操作称为“进栈（,PUSH,）”或者“压栈”，删除操作称为“出栈（,POP,）”。栈的特点是“先进后出（,FILO,，,First In Last Out,）”,1.,栈的基本操作（具体参见教材,260,页,-,261,页）,（,1,）初始化,（,2,）判空,（,3,）求栈中实际元素的个数,（,4,）进栈（压栈）,（,5,）出栈,（,6,）取栈顶元素,2.,栈的应用举例,例,1,、程序员输入问题,【,问题描述,】,程序员输入程序出现差错时，可以采取以下的补救措施：按错了一个键时，可以补按一个退格符“,#”,，以表示前一个字符无效；发现当前一行有错，可以按一个退行符“,”,，以表示“,”,与前一个换行符之间的字符全部无效。,【,输入格式,】,输入一行字符，个数不超过,100,。,【,输出格式,】,输出一行字符，表示实际有效字符。,【,输入样例,】,sdfosiffor,（,ii#=1,，,#,；,i,.#=8,；,i,+#,）；,【,输出样例,】,for,（,i,=1,；,i,=8,；,i,+,）；,【,问题分析,】,通过栈的操作，模拟这一过程：,1,、逐行处理，处理完一行后输出结果、栈重新置空。,2,、对于每行，逐个字符处理：,既不是退格符“”，也不是退行符“”，则将该字符压栈；,是退格符“”，则出栈；是退行符“”，就把栈置空。,/p7-7-1,#include,using namespace std;,int main(),freopen(“editor.in“,“r“,stdin);,freopen(“editor.out“,“w“,stdout);,char s110;,int top=0;,string str;,while(getline(cin,str),for(int i=0;i str.size();+i),switch(stri),case#,：,top-;break;,case ,：,top=0;break;,default,：,top+;stop=stri;,for(int i=1;i=top;i+)cout si;,cout endl;,return 0;,例,2,、溶液模拟器,【,问题描述,】,小谢虽然有很多溶液，但是还是没有办法配成想要的溶液，因为万一倒错了就没有办法挽回了。因此，小谢到网上下载了一个溶液配置模拟器。模拟器在计算机中构造一种虚拟溶液，然后可以虚拟地向当前虚拟溶液中加入一定浓度、一定体积的这种溶液，模拟器会快速地算出倒入后虚拟溶液的浓度和体积。当然，如果倒错了可以撤销。,模拟器的使用步骤如下：,1,）为模拟器设置一个初始体积和浓度,V0,、,C0%,。,2,）进行一系列操作，模拟器支持两种操作：,P(,v,c,),操作：表示向当前的虚拟溶液中加入体积为,v,浓度为,c,的溶液；,Z,操作：撤销上一步的,P,操作。,【,输入格式,】,第一行两个整数，表示,V0,和,C0,，,0C0100,；,第二行一个整数,n,，表示操作数，,n10000,；,接下来,n,行，每行一条操作，格式为：,P_v_c,或,Z,。,其中,_,代表一个空格，当只剩初始溶液的时候，再撤销就没有用了。,任意时刻质量不会超过,231-1,。,【,输出格式,】,n,行，每行两个数,Vi,，,Ci,，其中,Vi,为整数，,Ci,为实数（保留,5,位小数）。,其中，第,i,行表示第,i,次操作以后的溶液体积和浓度。,【,输入样例,】,100 100,2,P 100 0,Z,【,输出样例,】,200 50.00000,100 100.00000,【,问题分析,】,使用栈来模拟实现：,1,）读入撤销时，栈顶元素出栈。,2,）读入溶液时，把新的溶液的体积和浓度压栈。,3,）每次操作完，输出栈顶的体积和浓度。,/p7-7-2,#include,using namespace,std,;,const,int,N=10010;,struct,node,int,w;,double c;,aN;,int,main(),freopen,(“,simulator.in,”,”r”,stdin,);,freopen,(“,simulator.out,”,”w”,stdout,);int,v,n,c,top,=1;,cin,v c n;,atop.w=,v,a,top.c=c;/,将初始溶液入栈,while(n-),char,ch,;,cin,ch,;,if(,ch,=Z /,出栈,if(,ch,=P ),cin,v c;,top+;,atop.w=atop-1.w+v;/,将新溶液的质量入栈,atop.c=(atop-1.w*atop-1.c+v*c)/(double)atop.w;,/,将新溶液的浓度入栈,cout,atop.w “;,cout,fixed,setprecision,(5)atop.c,endl,;,return 0;,实践巩固,第,8,课 栈的应用,学习目标,1.,使用栈解决一些实际应用问题。,2.,学会用栈实现简单的深度优先搜索。,例,1,、,括号匹配,【,问题描述,】,假设表达式中允许包含圆括号和方括号两种括号，其嵌套的顺序随意，如（）或（）等为正确的匹配，（）或（）或（）均为错误的匹配。,本题的任务是检验一个给定表达式中的括号是否正确匹配。,输入一个只包含圆括号和方括号的字符串，判断字符串中的括号是否匹配，匹配就输出“,OK”,，不匹配就输出“,Wrong”,。,【,输入格式,】,一行字符，只含有圆括号和方括号，个数小于,255,。,【输出格式】,匹配就输出一行文本“,OK,”，不匹配就输出一行文本“,Wrong,”。,【输入样例】,(),【,输出样例,】,Wrong,【,问题分析,】,一个匹配的括号序列，必定是左、右圆括号、方括号的数量一样多。但是反过来，一样多不一定是匹配的。,定义一个字符型的栈来维护左括号，按顺序处理括号序列：,1,）遇到左括号：将它压栈。,2,）遇到右括号：检查栈顶元素与右括号是否匹配：如果匹配，将栈顶左括号出栈；否则，判断出序列不匹配，结束。,如果读到了右括号，而栈为空，也不匹配。如果序列处理完毕，栈非空，也不匹配。,具体程序参考教材,267,页。,例,2,、表达式求值,【,问题描述,】,给定一个只包含加法和乘法的算术表达式，请编程计算表达式的值。,【,输入格式,】,输入仅有一行，为需要计算的表达式。表达式中只包含数字、加法运算符“,+”,和乘法运算符“*”，且没有括号，所有参与运算的数字均为,0231-1,之间的整数。输入数据保证这一行只有,09,、,+,、*这,12,种字符。,【,输出格式,】,输出只有一行，包含一个整数，表示这个表达式的值。注意：当答案长度多于,4,位时，请只输出最后,4,位，前导,0,不输出。,【,输入样例,1】,1+1*3+4,【,输出样例,1】,8,【,输入样例,2】,1+1234567890*1,【,输出样例,2】,7891,【,输入样例,3】,1+1000000003*1,【,输出样例,3】,4,【,输入输出样例说明,】,样例,1,计算的结果为,8直接输出,8,。,样例,2,计算的结果为,1234567891,，输出后,4,位，即,7891,。,样例,3,计算的结果为,1000000004,，输出后,4,位，即,4,。,【,数据范围,】,对于,30%,的数据，,0,表达式中加法运算符和乘法运算符的总数,100,。,对于,80%,的数据，,0,表达式中加法运算符和乘法运算符的总数,1000,。,对于,100%,的数据，,0,表达式中加法运算符和乘法运算符的总数,100000,。,【,问题分析,】,由于只有加号和乘号，只要从左往右扫一遍，如果遇到乘号直接计算（做乘法）；如果遇到加号，若后面没有符号或者后面一个符号也是加号，则直接计算（做加法）；否则，先把后面紧接着的连续的乘号算完，最后再加。,算法实现中，只要设置一个栈保存没有立即进行的加法，扫描结束后再一起处理栈中的加法运算；同时，因为把一个数字串转换成数也需要单独编写一个子程序；最后，还要注意实现过程中及时对,10000,取模。,具体程序参考教材,269,页。,例,3,、图的深度优先遍历,【,问题描述,】,读入一个用邻接矩阵存储的无向图，输出它的深度优先遍历序列。,【,输入格式,】,第,1,行,1,个正整数,n,，表示图中的顶点数，,2n100,。,接下来的,n,行是一个,nn,的邻接矩阵，,a,i,j=1,表示顶点,i,和顶点,j,之间有直接边相连，,a,i,j=0,表示没有直接边相连。保证,i,=j,时，,a,i,j=0,，并且,a,i,j=aj,i,。,【,输出格式,】,输出,1n,的某一种排列，表示从顶点,1,开始，对该图进行深度优先遍历得到的顶点序列，每两个数之间用一个“,-”,分隔。,【,输入样例,】,8,0 1 1 0 0 0 0 0,1 0 0 1 1 0 0 0,1 0 0 0 0 0 1 1,0 1 0 0 0 1 0 0,0 1 0 0 0 1 0 0,0 0 0 1 1 0 0 0,0 0 1 0 0 0 0 1,0 0 1 0 0 0 1 0,【,输出样例,】,1-2-4-6-5-3-7-8,【,问题分析,】,图的深度优先遍历如图,78-1,所示。用手工栈来实现图的深度优先遍历：先任意找一个顶点入栈，即为栈顶元素，然后找到跟栈顶元素相连的一个顶点入栈，接着继续把跟栈顶元素相连的一个顶点入栈，若栈顶元素没有相连的顶点或者相连的顶点都已经入过栈那么栈顶元素就出栈，循环操作直到栈为空，那么元素的入栈顺序就是图的深度优先遍历。,具体程序参考教材,270,页。,实践巩固,第,9,课 哈希表,学习目标,初步掌握哈希表的基本思想和简单应用。,哈希表,哈希表，也称散列表，是一种高效的数据结构。它的最大优点就是把数据存储和查找所消耗的时间大大降低，几乎可以看成是,O,（,1,）的，而代价是消耗比较多的内存。在当前竞赛可利用内存空间越来越多程序运行时间控制的越来越紧的情况下，“以空间换时间”的做法还是值得的。另外，哈希表的编程复杂度比较低也是它的优点之一。,1.,哈希表的基本概念,哈希表的基本原理是使用一个下标范围比较大的数组,A,来存储元素，设计一个函数,h,，对于要存储的线性表的每个元素,node,，取一个关键字,key,，算出一个函数值,h(key),，把,h(key),作为数组下标，用,Ah(key),这个数组单元来存储,node,。也可以简单的理解为，按照关键字为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方,(,这一过程称为“直接定址”,),。,1.,哈希表的基本概念,但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突”，换句话说，就是把不同的元素分在了相同的“类”之中了。假设一个结点的关键字值为,key,，把它存入哈希表的过程是根据确定的函数,h,计算出,h(key),的值，如果以该值为地址的存储空间还没有被占用，那么就把结点存入该单元；如果此值所指单元里已存储了别的结点,(,即发生了冲突,),，那么就再用另一个函数,I,进行映射，计算出,I(h(key),再看用这个值作为地址的单元是否已被占用了，若已被占用，则再用,I,映射，,直至找到一个空位置将结点存入为止。当然，这只是解决“冲突”问题的一种简单方法，如何避免、减少和处理“冲突”是使用哈希表的一个难题。,1.,哈希表的基本概念,在哈希表中查找元素的过程与建立哈希表的过程相似，首先计算,h(key),的值，以该值为地址到基本区域中去查找。如果该地址对应的空间未被占用，则说明查找失败；否则用该结点的关键字值与要找的,key,比较，如果相等则查找成功；否则要继续用函数,I,计算,I(h(key),的，,如此重复，或者求出的某地址空间未被占用,(,查找失败,),或者比较相等,(,查找成功,),为止。,例,1,、用哈希表存储以下线性表（,18,，,75,，,60,，,43,，,54,，,90,，,46,）。,【,问题分析,】,假设选取的哈希函数为,h(K),=K mod m,，,K,为元素的关键字，,m,为哈希表的长度，用余数作为存储该元素的哈希地址。,K,和,m,均为正整数，并且,m,要大于或等于线性表的长度,n,。此例,n=7,，故取,m=13,就已经足够，得到的每个元素的哈希地址为：,h(18)=18 mod 13=5 h(75)=75 mod 13=10,h(60)=60 mod 13=8 h(43)=43 mod 13=4,h(54)=54 mod 13=2 h(90)=90 mod 13=12,h(46)=46 mod 13=7,根据哈希地址，依次把元素存储到哈希表,H(0 m-1),中的效果如下：,这是一个比较理想的情况，假如要再往表中插入第,8,个元素,30,，,h(30)=30 mod 13=4,，会发现,H4,已经存放了,43,，此时就发生了冲突，那么就可以从,H4,往后按顺序找一个空位置存放,30,，即可以把它插入到,H6,中。,2.,哈希表的应用举例,例,2,、分身数对,【,问题描述,】,给出,n,个不同的正整数,a1 an,，它们的值在,11000000,之间。再给定一个整数,x,，编程计算这样的数对个数,(a,i,aj),，,1i,jn,并且,a,i,+aj=x,。,【,输入格式,】,第,1,行,1,个正整数,n,，,1n100000,。,第,2,行,n,个正整数，表示元素,a1 an,，每两个数之间用一个空格分隔。,第,3,行,1,个正整数,x,，,1x2000000,。,【,输出格式,】,一行一个整数，表示这样的数对个数。,【,输入样例,】,9,5 12 7 10 9 1 2 3 11,13,【,输出样例,】,3,【,样例说明,】,不同的和为,13,的数对是,(12,1),(10,3),和,(2,11),，共,3,对。,【,问题分析,】,如果使用双重循环来查找，本题是要超时的。用哈希表来处理，定义,ax,代表,x,这个数在数列中是否存在，,1,代表存在，,0,代表不存在，那么只需要扫描,1 x/2,，若数字存在，那么只需要查看,x,减去这个数的结果在数列里是否存在，若存在就增加一对数对具体程序参考教材,274,页。,例,3,、明明的随,机数,【,问题描述,】,明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了,N,个,11000,之间的随机整数，,N100,，对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请协助明明完成“去重”与“排序”的工作。,【,输入格式,】,第,1,行为,1,个正整数，表示所生成的随机数的个数,N,。,第,2,行有,N,个用一个空格隔开的正整数，为所产生的随机数。,【,输出格式,】,输出两行。,第,1,行为,1,个正整数,M表示不相同的随机数的个数。,第,2,行为,M,个从小到大排好序的不相同的随机数，每两个数之间用一个空格隔开。,【,输入样例,】,10,20 40 32 67 40 20 89 300 400 15,【,输出样例,】,8,15 20 32 40 67 89 300 400,【,问题分析,】,因为,N100,，可以使用冒泡排序、插入排序、选择排序等时间复杂度为,O(n2),的算法实现，这样做不会超时。实际上，对于产生的随机数,a,i,，由于,0a,i,1001,，且,a,i,为整数。所以，可以使用哈希表,a,i,=0,表示没有,i,这个数，,a,i,=1,表示有,i,这个数。那么，每次读一个,i,，把,a,i,赋值为,1,，读完所有数据后，只要再扫描一下这个数组就可完成统计和排序输出任务。这种方法类似“桶排序”原理。,具体程序参考教材,276,页,-,277,页。,实践巩固,