精华内容
下载资源
问答
  • 信息系统项目管理师具体成绩查询方法如下: ①进入中国计算机技术职业资格网(http://www.ruankao.org.cn),选择页面下方右侧的“考试分数查询”;②选择按准证号或证件号进行查询;③选择考试时间,填入准证...

    首先,信息系统项目管理师属于高级软考,每年有两次考试。考试成绩查询的开放时间一般在考试后两个月内。比如上半年5月份软考成绩通常在7月初的时候公布,下半年11月份软考成绩通常在12月底的时候公布。信息系统项目管理师具体成绩查询方法如下:

    ①进入中国计算机技术职业资格网(http://www.ruankao.org.cn),选择页面下方右侧的“考试分数查询”;②选择按准考证号或证件号进行查询;③选择考试时间,填入准考证号(证件号)、姓名及验证码。

    0

     

     

     

    1

    2

    昨天小编为大家整理了高级信息系统项目管理师考前准备的一些科普,如算考试后需要在哪儿报名、如何报名以及考试的题型和分数想必大家对这门考试已经有了初步的了解,不像之前的一头雾水了吧?那么今天我继续为大家科普一下信息系统项目管理师考试的相关事项,让大家备考更安心。

    1、考试地点

    在计算机技术与软件专业技术资格(水平)考试(软考)中,信息系统项目管理师、系统集成项目管理工程师等考试在各省(区、市)都有考点,一般在各地(区、市)考试报名地点进行,有些地区(区、市)如果没有设立考点,可能需要考生到省会城市参加考试,具体考点设置在哪里需要在考试前一周左右先打印准考证,具体考试地点在准考证上会详细标明

    2、历年考点题型分析

    由于每年的考试题目都在变,选择题是基础知识我们就不多介绍了。但每年像案例分析、论文考点都汇总好的,为便于各位考友有针对性的对重点知识进行复习备考,科科过对历年以来的各年信息系统项目管理师考试真题题型做了一个分析,下面是我整理的历年考题汇总希望对大家的复习备考有帮助。

     

    4

    3、备考资料

    其实高项不算难,是知识点太多,需要记忆,包括论文,如果有项目经验的话案例分析和论文都会上手快一点。通过一个考试在短时间内去了解一个项目管理过程是很有效的方式,感觉有能力过了高项的人对项目管理过程应该有非常清晰的认知了

     

    4、考试分数查询

    信息系统项目管理师考试成绩一般在考后的一个半月左右公布,成绩查询入口一般为中国计算机技术职业资格网(http://www.ruankao.org.cn)。考试每一门的总分为75分,考生需要每一科考的成绩大于45分才算成绩合格,如果三门中任意一门成绩低于45分那么三门科目都要重新再考

    5、证书的领取

    一般在公布成绩后的4个月由考生本人持本人身份证件、准考证到指定地点领取资格证书 

    6、证书的用途

    5

    ①、评职称:此证书在国企和事业单位可以评职称。对事业单位和国有企业的工作人员来说,职称在很大程度上代表了地位和收入,而软考不设报考条件,可以提前一到几年进行准备和考试,一到升职时间就拿出来,绝对是前占先机的好办法。

    ②升职加薪:对于私企、私企、求职者来说,证书至少可以代表你的学习能力。学习能力是IT行业中发展速度最快、最宝贵的素质之一。也许证书不能在短时间内给你带来收入,但绝对是找工作的敲门砖,晋升的阶梯。

    ③、能力的体现:对于要考的朋友来说,学习的过程就是自我享受的过程,证书就是自己能力的证明书,绝对的炫耀资本,自己能力的一种体现。

    考试的试题注重岗位知识和技能,综合性和灵活性强,创意多。但只要考生掌握了相应岗位所需的基本知识和技能,就会认为考试并不难。只要大家认真备考相信一定都会取得一个好的成绩!

    展开全文
  • 上传目的:希望所有对计算方法考试没信心的同学都能正确面对自己的不足,及时复习,按照考试题型有针对性的复习,效果会非常....最后希望大家都能考出优异的成绩
  • 超硬核!数据结构学霸笔记,考试面试吹牛就靠它

    万次阅读 多人点赞 2021-03-26 11:11:21
    操作系统学霸笔记,考试复习面试全靠它 第一次笔记(复习c,课程概述) 第一节课复习了c语言的一些知识,并简单介绍了数据结构这门课程。 1、引用和函数调用: 1.1引用:对一个数据建立一个“引用”,他的作用是为一...

    上次发操作系统笔记,很快浏览上万,这次数据结构比上次硬核的多哦,同样的会发超硬核代码,关注吧。

    超硬核!操作系统学霸笔记,考试复习面试全靠它

     


     


     

    第一次笔记(复习c,课程概述)

    第一节课复习了c语言的一些知识,并简单介绍了数据结构这门课程。

     

    1、引用和函数调用:

    1.1引用:对一个数据建立一个“引用”,他的作用是为一个变量起一个别名。这是C++对C语言的一个重要补充。

    用法很简单:

    int a = 5;

    int &b = a;

    b是a别名,b与a代表的是同一个变量,占内存中同一个存储单元,具有同一地址。

    注意事项:

    1. 声明一个引用,同时必须初始化,及声明它代表哪一个变量。(作为函数参数时不需要初始化)
       
    2. 在声明一个引用后,不能再作为另一变量的引用。

         3。不能建立引用数组。

    1.2函数调用:

    其实还是通过函数来理解了一下引用

    void Myswap1(int a,int b)
    {
    	int c = a;
    	a = b;
    	b = c;
    }
    
    void Myswap2(int &a,int &b)
    {
    	int c = a;
    	a = b;
    	b = c;
    }
    
    void Myswap3(int *pa,int *pb)
    {
    	int c = *pa;
    	*pa = *pb;
    	*pb = c;
    }

    这三个函数很简单,第一个只传了值进来,不改变全局变量;而第三个也很熟悉,就是传递了地址,方便操作。依旧是“值传递”的方式,只不过传递的是变量的地址而已;那二就彻底改变了这些东西,引用作为函数参数,传入的实参就是变量,而不是数值,真正意义上的“变量传递”。

     

    2、数组和指针:

    这一块讲得比较简单,就是基本知识。

    主要内容:

    1、函数传数组就是传了个指针,这个大家都知道,所以传的时候你写arr[],里面写多少,或者不写,都是没关系的,那你后面一定要放一个变量来把数组长度传进来。

    2、还有就是,定义:int arr[5],你访问越界是不会报错的,但是逻辑上肯定就没有道理了。那用typedef int INTARR[3];访问越界,在vs上会报错,要注意。

    3、再说一下指针和数组名字到底有什么区别?这本来就是两个东西,可能大家没注意罢了。

    第一:指针可以自增,数组名不行,因为是常量啊。

    第二:地址不同,虽然名字[n],都可以这样用,但是数组名地址就是第一个元素地址。指针地址就是那个指针的地址,指针里存的才是第一个元素地址。

    第三:sizeof(),空间不一样,数组是占数组那么大空间。指针是四个字节。

    本来就是俩东西,这么多不同都是本质不同的体现。

    3、结构体:

    也是讲的基本操作,基本就是这个东西:

    typedef struct Date
    {
    	int Year;
    	int Month;
    	int Day;
    	struct Date *pDate;
    }Date, *pDate;

    1、内部无指向自己的指针才可以第一行先不起名字。

    2、内部不能定义自己的,如果能的话那空间不就无限了么。很简单的逻辑

     

    指针我不习惯,还是写Date *比较顺眼

    3、有同学没注意:访问结构体里的东西怎么访问?

    Date.这种形式,或者有指向这个节点的指针p可以p->这种形式,别写错了。

     

    4、还有就是结构体能直接这么赋值:

       Date d1 = {2018,9,11};

    我竟然不知道,以前还傻乎乎的一个一个赋值呢。

     

    5、还有,想写一下结构体有什么优点。。

    这一块可能写的就不好了,因为不是老师讲的。。

    比如学生成绩,如果不用结构体,我们一个学生可能有十几个信息,那定义变量和操作就很烦琐了,数据结构有一种松散的感觉。用一个结构体来表示更好,无论是程序的可读性还是可移植性还是可维护性,都得到提升。还有就是函数调用的时候,传入相当多的参数,又想操作或者返回,那是很麻烦的事。现在只传入一个结构体就好了,操作极其简单。总结一下就是好操作,中看中用,有机地组织了对象的属性。以修改结构体成员变量的方法代替了函数(入口参数)的重新定义。

    基本就这样吧。

    6、还有就是它了:typedef int INTARR[3];这样直接定义了一个数据类型,长度为3的数组,然后直接这样用就可以了:

    INTARR arr1;

     

    回忆完C语言储备知识,然后讲了数据结构的基本概念

     

    数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作等的学科。

    数据:是对客观事物的符号表示,在计算机中指能输入到计算机中并被处理的符号总称。

    数据元素:数据的基本单位

    数据项:数据的不可分割的最小单位

    数据对象:性质相同的数据元素的集合。

    举例:动物是数据,某只动物是数据元素,猫狗是数据对象,颜色可以是数据项。

     

    数据元素之间存在某种关系,这种关系成为结构。

    四种基本结构:

    集合:除了同属一个集合无其他关系。

    线性结构:一对一的关系

    树形结构:一对多的关系

    图状结构:多对多的关系

     

    第二次笔记(基本概念,时间空间复杂度)

    今天继续说明了一些基本概念,讲解了时间空间复杂度。

    (对于概念的掌握也很重要)

     

    元素之间的关系在计算机中有两种表示方法:顺序映像和非顺序映像,由此得到两种不同的储存结构:

    顺序存储结构和链式存储结构。

     

    顺序:根据元素在存储器中的相对位置表示关系

    链式:借助指针表示关系

     

    数据类型:是一个值的集合和定义在这个值集上的一组操作的总称。

    抽象数据类型:是指一个数学模型以及定义在该模型上的一组操作。(仅仅取决于逻辑特性,与其在计算机内部如何表示和实现无关)

     

    定义抽象数据类型的一种格式:

    ADT name{

    数据对象:<>

    数据关系:<>

    基本操作:<>

    }ADT name

     

    算法:是对特定问题求解步骤的一种描述。

    算法五个特性:

    1. 有穷性:有穷的时间内完成,或者可以说是可接受的时间完成
    2. 确定性:对于相同的输入只能得到相同的输出
    3. 可行性:描述的操作都可以执行基本操作有限次来实现
    4. 输入:零个或多个输入。取自于某个特定对象的集合
    5. 输出:一个或多个输出

     

    设计要求:正确性、可读性、健壮性、效率与低存储量需求。

    执行频度概念:是指通过统计算法的每一条指令的执行次数得到的。

    执行频度=算法中每一条语句执行次数的和

    一般认定每条语句执行一次所需时间为单位时间(常数时间)O(1)

     

    几个小知识和小问题:

    1)循环执行次数n+1次,不是n次。第一次执行i=1和判断i<=n以后执行n次判断和i++。所以该语句执行了n+1次。在他的控制下,循环体执行了n次。

    2)四个并列程序段:分别为O(N),O(N^2),O(N^3),O(N*logN),整个程序时间复杂度为O(N^3),因为随着N的增长,其它项都会忽略

    3)算法分析的目的是分析算法的效率以求改进

    4)对算法分析的前提是算法必须正确

    5)原地工作指的不是不需要空间,而是空间复杂度O(1),可能会需要有限几个变量。

    实现统一功能两种算法:时间O(2^N),O(N^10),假设计算机可以运行10^7秒,每秒可执行基本操作10^5次,问可解问题规模各为多少?选哪个更为合适?

    计算机一共可执行10^7*10^5=10^12次

    第一种:n=log2,(10^12)=12log(2,10)

    第二种:n=(10^12)^0.1

    显然1更适用。

    虽然一般情况多项式算法比指数阶更优

     

    时间空间复杂度概述

     

    找个时间写一写时间复杂度和一些问题分类,也普及一下这方面知识。

    如何衡量一个算法好坏

    很显然,最重要的两个指标:需要多久可以解决问题、解决问题耗费了多少资源

    那我们首先说第一个问题,要多长时间来解决某个问题。那我们可以在电脑上真实的测试一下嘛,多种方法比一比,用时最少的就是最优的啦。

    但是没必要,我们可以通过分析计算来确定一个方法的好坏,用O()表示,括号内填入N、1,等式子。

    这到底是什么意思呢?

    简单来说,就是这个方法,时间随着数据规模变化而增加的快慢。时间可以当成Y,数据规模是X,y=f(x),就这样而已。但是f(x)不是准确的,只是一个大致关系,y=10x,我们也视作x,因为他的增长速度还是n级别的。现在就可以理解了:一般O(N)就是对每个对象访问优先次数而已。请注意:O(1)它不是每个元素访问一次,而是Y=1的感觉,y不随x变化而变化,数据多大它的时间是不变的,有限的常数操作即可完成。

    那我们就引入正规概念:

    时间复杂度是同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。

    计算机科学中,算法的时间复杂度是一个函数,它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,它考察当输入值大小趋近无穷时的情况。

    注意:文中提到:不包括这个函数的低阶项和首项系数。什么意思呢?就是说10n,100n,哪怕1000000000n,还是算做O(N),而低阶项是什么意思?不知大家有没有学高等数学1,里面有最高阶无穷大,就是这个意思。举个例子。比如y=n*n*n+n*n+n+1000

    就算做o(n*n*n),因为增长速率最大,N*N及其它项增长速率慢,是低阶无穷大,n无限大时,忽略不计。

     

    那接着写:o(n*n*n)的算法一定不如o(n)的算法吗?也不一定,因为之前说了,时间复杂度忽略了系数,什么意思?o(n)可以是10000000n,当n很小的时候,前者明显占优。

    所以算法要视实际情况而定。

    算法的时间 复杂度常见的有:
    常数阶 O(1),对数阶 O(log n),线性阶 O(n),
    线性对数阶 O(nlog n),平方阶 O(n^2),立方阶 O(n^3),…,
    k 次方阶O(n^k),指数阶 O(2^n),阶乘阶 O(n!)。

    常见的算法的时间 复杂度之间的关系为:
           O(1)<O(log n)<O(n)<O(nlog n)<O(n^2)<O(2^n)<O(n!)<O(n^n) 

     

    我们在竞赛当中,看见一道题,第一件事就应该是根据数据量估计时间复杂度。

    计算机计算速度可以视作10^9,如果数据量是10000,你的算法是O(N*N),那就很玄,10000*10000=10000 0000,别忘了还有常数项,这种算法只有操作比较简单才可能通过。你可以想一想O(nlog n)的算法一般就比较稳了。那数据量1000,一般O(N*N)就差不多了,数据量更小就可以用复杂度更高的算法。大概就这样估算。

     

    当 n 很大时,指数阶算法和多项式阶算法在所需时间上非常
    悬殊。因此,只要有人能将现有指数阶算法中的任何一个算法化
    简为多项式阶算法,那就取得了一个伟大的成就。

    体会一下:

     

    空间复杂度也是一样,用来描述占空间的多少。

    注意时间空间都不能炸。

    所以才发明了那么多算法。

    符上排序算法的时间空间表,体会一下:

     


    排序博客:加深对时间空间复杂度理解

    https://blog.csdn.net/hebtu666/article/details/81434236

     

     

     

    引入:算法优化

     

    想写一系列文章,总结一些题目,看看解决问题、优化方法的过程到底是什么样子的。

     

    系列问题一:斐波那契数列问题

    在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=0,F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)根据定义,前十项为1, 1, 2, 3, 5, 8, 13, 21, 34, 55

    问题一:

    给定一个正整数n,求出斐波那契数列第n项(这时n较小)

    解法一:最笨,效率最低,暴力递归,完全是抄定义。请看代码

    def f0(n):
        if n==1 or n==2:
            return 1
        return f(n-1)+f(n-2)

     

    分析一下,为什么说递归效率很低呢?咱们来试着运行一下就知道了

     

    比如想求f(10),计算机里怎么运行的?

     

    每次要计算的函数量都是指数型增长,时间复杂度O(2^(N/2))<=T(N)<=O(2^N),效率很低。效率低的原因是,进行了大量重复计算,比如图中的f(8),f(7).....等等,你会发现f(8)其实早就算过了,但是你后来又要算一遍。

    如果我们把计算的结果全都保存下来,按照一定的顺序推出n项,就可以提升效率, 斐波那契(所有的一维)的顺序已经很明显了,就是依次往下求。。

    优化1

    def f1(n):
        if n==1 or n==2:
            return 1
        l=[0]*n
        l[0],l[1]=1,1
        for i in range(2,n):
            l[i]=l[i-1]+l[i-2]
        return l[-1]

     

    时间复杂度o(n),依次往下打表就行,空间o(n).

    继续优化:既然只求第n项,而斐波那契又严格依赖前两项,那我们何必记录那么多值呢?记录前两项就行了

     

    优化2

    def f2(n):
        a,b=1,1
        for i in range(n-1):
            a,b=b,a+b
        return a

    此次优化做到了时间o(n),空间o(1)

    附:这道题掌握到这里就可以了,但是其实有时间o(log2n)的方法

     

    优化三:

    学习过线性代数的同学们能够理解:

     

    结合快速幂算法,我们可以在o(log2n)内求出某个对象的n次幂。(在其它专题详细讲解)

    注意:只有递归式不变,才可以用矩阵+快速幂的方法。

    注:优化三可能只有在面试上或竞赛中用,当然,快速幂还是要掌握的。

     

    经过这个最简单的斐波那契,大家有没有一点感觉了?

    好,我们继续往下走

    (补充:pat、蓝桥杯原题,让求到一万多位,结果模一个数。

    可以每个结果都对这个数取模,否则爆内存,另:对于有多组输入并且所求结果类似的题,可以先求出所有结果存起来,然后直接接受每一个元素,在表中查找相应答案)

     

    问题二:

    一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

    依旧是找递推关系,分析:跳一阶,就一种方法,跳两阶,它可以一次跳两个,也可以一个一个跳,所以有两种,三个及三个以上,假设为n阶,青蛙可以是跳一阶来到这里,或者跳两阶来到这里,只有这两种方法。它跳一阶来到这里,说明它上一次跳到n-1阶,同理,它也可以从n-2跳过来,f(n)为跳到n的方法数,所以,f(n)=f(n-1)+f(n-2)

    和上题的优化二类似。

    因为递推式没变过,所以可以用优化三

     

    问题三:

    我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?提示,大矩形看做是长度吧

    请读者自己先思考一下吧。。。仔细看题。。仔细思考

    如果n是1,只有一种,竖着放呗;n是2,两种:

    n等于3,三种:

     

    题意应该理解了吧?

    读到这里,你们应该能很快想到,依旧是斐波那契式递归啊。

    对于n>=3:怎么能覆盖到三?只有两种办法,从n-1的地方竖着放了一块,或者从n-2的位置横着放了两块呗。

    和问题二的代码都不用变。

     

    问题四:

    给定一个由0-9组成的字符串,1可以转化成A,2可以转化成B。依此类推。。25可以转化成Y,26可以转化成z,给一个字符串,返回能转化的字母串的有几种?

    比如:123,可以转化成

    1 2 3变成ABC,

    12 3变成LC,

    1 23变成AW,三种,返回三,

    99999,就一种:iiiii,返回一。

    分析:求i位置及之前字符能转化多少种。

    两种转化方法,一,字符i自己转换成自己对应的字母,二,和前面那个数组成两位数,然后转换成对应的字母

    假设遍历到i位置,判断i-1位置和i位置组成的两位数是否大于26,大于就没有第二种方法,f(i)=f(i-1),想反,等于f(i-1)+f(i-2)

    注意:递归式不确定,不能用矩阵快速幂

     

    (这几个题放到这里就是为了锻炼找递归关系的能力,不要只会那个烂大街的斐波那契)

     

    '''
    斐波那契问题:
    斐波纳契数列以如下被以递归的方法定义:
    F(1)=1
    F(2)=1
    F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)
    '''
    #暴力抄定义,过多重复计算
    def f0(n):
        if n==1 or n==2:
            return 1
        return f(n-1)+f(n-2)
    #记录结果后依次递推的优化,时间O(N)
    def f1(n):
        if n==1 or n==2:
            return 1
        l=[0]*n
        l[0],l[1]=1,1
        for i in range(2,n):
            l[i]=l[i-1]+l[i-2]
        return l[-1]
    #既然严格依赖前两项,不必记录每一个结果,优化空间到O(1)
    def f2(n):
        a,b=1,1
        for i in range(n-1):
            a,b=b,a+b
        return a

    第三次笔记(线性表结构和顺序表示)

     

    这节课介绍了线性表结构和顺序表示的一部分内容。

    操作太多,而且书上有,就不一一介绍分析了。

    线性表定义:n个数据元素的有限序列。

    特点:

    1. 存在唯一一个称作“第一个”的元素。
    2. 存在唯一一个称作“最后一个”的元素
    3. 除最后一个元素外,集合中每一个元素都只有一个直接前趋
    4. 除最后一个元素外,集合中每一个元素都只有一个直接后继

    注意1、2条:证明循环的序列不是线性表

     

    注意:

    1)线性表从1开始,线性表第一个元素对应到数组中下标是0.

    2)函数通过引用对线性表的元素进行修改即可

    3)数组比较特别,它即可视为逻辑结构,又可视为存储结构。

    4)每一个表元素都是不可再分的原子数据。一维数组可以视为线性表,二维数组不可以,在逻辑上它最多可以有两个直接前趋和直接后继。

    5)线性表具有逻辑上的顺序性,在序列中各元素有其先后次序,各个数据元素在线性表中的逻辑位置只取决于序号。

     

    顺序表:是线性表的循序储存结构,以物理位置表示逻辑关系,任意元素可以随机存取。用一组地址连续的存储单元依次存储线性表中的元素。逻辑顺序和物理顺序是一致的。可以顺序访问,也可随机访问。

    顺序表存储:

    这些定式还是很重要的,比如define typedef等,真正实现时最好就这样写,不要自己规定个长度和数据类型,这样以后好维护、修改。

    静态存储分配:

    #define maxSize 100//显式定义表长

    Typedef int DataType;//定义数据类型

    Typedef struct{

    DataType data[maxSize];//静态分配存储表元素向量

    Int n;//实际表中个数

    }SeqList;

     

    动态存储分配:

    #define maxSize 100//长度初始定义

    Typedef int DataType;//定义数据类型

    Typedef struct{

    DataType *data;//动态分配数组指针

    Int maxSize,n;//最大容量和当前个数

    }SeqList;

     

    初始动态分配:

    Data=(DataType *)malloc(sizeof(DataType)* initSize);

    C++:data=new DataType[initSize];

    maxSize=initSize;n=0;

    动态分配存储,向量的存储空间是在程序执行过程中通过动态存储分配来获取的。空间满了就另外分配一块新的更大的空间,用来代替原来的存储空间,从而达到扩充的目的。

     

    插入:需要查找,移动元素,概率上1,2,3....n,平均O(N)

    删除:同样需要移动元素。填充被空出来的存储单元。

    在等概率下平均移动次数分别为n/2,(n-1)/2

     插入注意事项:

    1. 需要判断是否已满
    2. 要从后向前移动,否则会冲掉元素

    删除注意事项:

    1. 需要先判断是否已空
    2. 需要把后方元素前移,要从前向后。

     

    注意:线性表的顺序存储借用了一维数组,但是二者不同:

    1. 一维数组各非空结点可以不相继存放,但顺序表是相继存放的
    2. 顺序表长度是可变的,一维数组长度是确定的,一旦分配就不可变
    3. 一维数组只能按下标存取元素,顺序表可以有线性表的所有操作。

     

     

    第四次笔记(链表概述)

     

    介绍了链表和基本操作

    用一组物理位置任意的存储单元来存放线性表的数据元素。 这组存储单元既可以是连续的,也可以是不连续的,甚至是零散分布在内存中的任意位置上的。因此,链表中元素的逻辑次序和 物理次序不一定相同。

     

    定义:

    typedef  struct  Lnode{  
            //声明结点的类型和指向结点的指针类型  
            ElemType         data;    //数据元素的类型 
            struct   Lnode  *next;   //指示结点地址的指针  
    }Lnode, *LinkList;  
    struct Student
    { char num[8];   //数据域
      char name[8];  //数据域
      int score;          //数据域
      struct Student *next;  // next 既是 struct Student 
                                           // 类型中的一个成员,又指 
                                           // 向 struct Student 类型的数据。 
    }Stu_1, Stu_2, Stu_3, *LL;  
    

    头结点:在单链表的第一个结点之前人为地附设的一个结点。

    带头结点操作会方便很多。

    带和不带的我都写过了

    下面列出我见过的一些好题

    1、

    线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。

    • 正确
    • 错误

     

    错,线性表是逻辑结构概念,可以顺序存储或链式储,与元素数据类型无关。链表就是线性表的一种  前后矛盾

     

    2、

    若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用(    )存储方式最节省运算时间。

    • 单链表
    • 仅有头指针的单循环链表
    • 双链表
    • 仅有尾指针的单循环链表

      对于A,B,C要想在尾端插入结点,需要遍历整个链表。

      对于D,要插入结点,只要改变一下指针即可,要删除头结点,只要删除指针.next的元素即可。

     

    3、注意:线性表是具有n个数据元素的有限序列,而不是数据项

     

    4、

    以下关于单向链表说法正确的是

    • 如果两个单向链表相交,那他们的尾结点一定相同
    • 快慢指针是判断一个单向链表有没有环的一种方法
    • 有环的单向链表跟无环的单向链表不可能相交
    • 如果两个单向链表相交,那这两个链表都一定不存在环

    自己多画画想想就明白了,关于快慢指针我以后会写总结。

     

    5、

    链接线性表是顺序存取的线性表 。 ( )

    • 正确
    • 错误

    链接线性表可以理解为链表
    线性表分为顺序表和链表
    顺序表是顺序存储结构、随机存取结构
    链表是随机存储结构、顺序存取结构

     

    6、

    typedef struct node_s{
        int item;
        struct node_s* next;
    }node_t;
    node_t* reverse_list(node_t* head)
    {
        node_t* n=head;
        head=NULL;
        while(n){
        _________               
        }
        return head;
     }

    空白处填入以下哪项能实现该函数的功能?

    • node_t* m=head; head=n; head->next=m; n=n->next;
    • node_t* m=n; n=n->next; m->next=head; head=m;
    • node_t* m=n->next; n->next=head; n=m; head=n;
    • head=n->next; head->next=n; n=n->next;


     

    代码的功能是要实现链表的反转。为了方便阐述,每个结点用①②③④⑤⑥等来标示。

    在执行while(n)循环之前,有两句代码:

    node_t* n=head;

    head=NULL;

    这两行代码的中:第一句的作用是用一个临时变量n来保存结点①,第二句是把head修改为NULL。

    然后就开始遍历了,我们看到while循环里的那四句代码:

    node_t* m=n; 
    n=n->next; 
    m->next=head; 
    head=m;
    

    先看前两句,用m来保存n,然后让n指向n的下一个结点,之所以复制 n 给 m ,是因为 n 的作用其实是  控制while循环次数  的作用,每循环一次它就要被修改为指向下一个结点。

    再看后两句,变量head在这里像是一个临时变量,后两句让 m 指向了 head,然后 head 等于 m。

     

    7、

    若某表最常用的操作是在最后一个结点之后插入一个节点或删除最后一二个结点,则采用()省运算时间。

    • 单链表
    • 双链表
    • 单循环链表
    • 带头结点的双循环链表

    D

    带头结点的双向循环链表,头结点的前驱即可找到最后一个结点,可以快速插入,再向前可以找到最后一二个结点快速删除

    单链表找到链表尾部需要扫描整个链表

    双链表找到链表尾部也需要扫描整个链表

    单循环链表只有单向指针,找到链表尾部也需要扫描整个链表

     

    8、

    单链表的存储密度(  )

    • 大于1
    • 等于1
    • 小于1
    • 不能确定

    全麦白

    存储密度 = 数据项所占空间 / 结点所占空间

     

    9、完成在双循环链表结点p之后插入s的操作是

    • s->prior=p; s->next=p->next; p->next->prior=s ; p->next=s;

     

    10、用不带头结点的单链表存储队列,其队头指针指向队头结点,队尾指针指向队尾结点,则在进行出队操作时()

    • 仅修改队头指针
    • 仅修改队尾指针
    • 队头、队尾指针都可能要修改
    • 队头、队尾指针都要修改

     

    当只有一个元素,出队列时,要将队头和队尾,指向-1.所以说队头和队尾都需要修改

     

     

    链表刷了几百道吧,好题还有很多,以后接着更新

     

     

    第六次笔记(链表选讲/静态链表)

     

    本节课介绍了单链表的操作实现细节,介绍了静态链表。

     

    链表带头的作用:对链表进行操作时,可以对空表、非空表的情况以及 对首元结点进行统一处理,编程更方便。

    下面给出带头的单链表实现思路:

     

    按下标查找:

    判断非法输入,当 1 < =i <= n 时,i 的值是合法的。

    p = L -> next; j = 1;

    while ( p && j < i ) {  p = p ->next; ++j; }

    return 

     

    按值查找:

     p = L1 -> next;

     while ( p && p ->data!=key)          p = p -> next;

    return;

     

    插入:

    判断

    查找

    创建

    插入

     

    删除:

    查找

    删除

    释放内存

     

    静态链表

    对于线性链表,也可用一维数组来进行描述。这种描述方法便于在没有指针类型的高级程序设计语言中使用链表结构。

    这种存储结构,仍需要预先分配一个较大的空间,但在作为线性表的插入和删除操作时不需移动元素,仅需修改指针,故仍具有链式存储结构的主要优点。

     

    表示:

    #define MAXSIZE 1000      / /链表的最大长度

    typedef  struct{      

        ElemType data;        

        int cur;

    }component,  SLinkList[MAXSIZE];

     

    过程:

     

     

    顺序存储线性表实现

     

    在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构。

     

    顺序存储结构的主要优点是节省存储空间,因为分配给数据的存储单元全用存放结点的数据(不考虑c/c++语言中数组需指定大小的情况),结点之间的逻辑关系没有占用额外的存储空间。采用这种方法时,可实现对结点的随机存取,即每一个结点对应一个序号,由该序号可以直接计算出来结点的存储地址。但顺序存储方法的主要缺点是不便于修改,对结点的插入、删除运算时,可能要移动一系列的结点。

    优点:随机存取表中元素。缺点:插入和删除操作需要移动元素。

     

    线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的(注意,这句话只适用大部分线性表,而不是全部。比如,循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储),但是把最后一个数据元素的尾指针指向了首位结点)。

    给出两种基本实现:

    /*
    静态顺序存储线性表的基本实现
    */
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define LIST_INITSIZE 100
    #define ElemType int
    #define Status int
    #define OK     1
    #define ERROR  0
    
    typedef struct
    {
    	ElemType elem[LIST_INITSIZE];
    	int length;
    }SqList;
    
    //函数介绍
    Status InitList(SqList *L); //初始化
    Status ListInsert(SqList *L, int i,ElemType e);//插入
    Status ListDelete(SqList *L,int i,ElemType *e);//删除
    void ListPrint(SqList L);//输出打印
    void DisCreat(SqList A,SqList *B,SqList *C);//拆分(按正负),也可以根据需求改
    //虽然思想略简单,但是要写的没有错误,还是需要锻炼coding能力的
    
    Status InitList(SqList *L)
    {
        L->length = 0;//长度为0
        return OK;
    }
    
    Status ListInsert(SqList *L, int i,ElemType e)
    {
        int j;
        if(i<1 || i>L->length+1)
            return ERROR;//判断非法输入
        if(L->length == LIST_INITSIZE)//判满
        {
            printf("表已满");//提示
            return ERROR;//返回失败
        }
        for(j = L->length;j > i-1;j--)//从后往前覆盖,注意i是从1开始
            L->elem[j] = L->elem[j-1];
        L->elem[i-1] = e;//在留出的位置赋值
        (L->length)++;//表长加1
        return OK;//反回成功
    }
    
    Status ListDelete(SqList *L,int i,ElemType *e)
    {
        int j;
        if(i<1 || i>L->length)//非法输入/表空
            return ERROR;
        *e = L->elem[i-1];//为了返回值
        for(j = i-1;j <= L->length;j++)//从前往后覆盖
            L->elem[j] = L->elem[j+1];
        (L->length)--;//长度减1
        return OK;//返回删除值
    }
    
    void ListPrint(SqList L)
    {
        int i;
        for(i = 0;i < L.length;i++)
            printf("%d ",L.elem[i]);
        printf("\n");//为了美观
    }
    
    void DisCreat(SqList A,SqList *B,SqList *C)
    {
        int i;
        for(i = 0;i < A.length;i++)//依次遍历A中元素
        {
            if(A.elem[i]<0)//判断
                ListInsert(B,B->length+1,A.elem[i]);//直接调用插入函数实现尾插
            else
                ListInsert(C,C->length+1,A.elem[i]);
        }
    }
    
    int main(void)
    {
        //复制的
    	SqList L;
    	SqList B, C;
    	int i;
    	ElemType e;
    	ElemType data[9] = {11,-22,33,-3,-88,21,77,0,-9};
    	InitList(&L);
    	InitList(&B);
    	InitList(&C);
    	for (i = 1; i <= 9; i++)
    		ListInsert(&L,i,data[i-1]);
        printf("插入完成后L = : ");
    	ListPrint(L);
        ListDelete(&L,1,&e);
    	printf("删除第1个后L = : ");
    	ListPrint(L);
        DisCreat(L , &B, &C);
    	printf("拆分L后B = : ");
    	ListPrint(B);
    	printf("拆分L后C = : ");
    	ListPrint(C);
    	printf("拆分L后L = : ");
    	ListPrint(L);
    }

    静态:长度固定

    动态:不够存放可以加空间(搬家)

     

    /*
    子任务名任务:1_2 动态顺序存储线性表的基本实现
    */
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define LIST_INIT_SIZE 100
    #define LISTINCREMENT 10
    #define Status int
    #define OVERFLOW -1
    #define OK 1
    #define ERROR 0
    #define ElemType int
    
    typedef struct
    {
    	ElemType * elem;
    	int length;
    	int listsize;
    }SqList;
    //函数介绍
    Status InitList(SqList *L); //初始化
    Status ListInsert(SqList *L, int i,ElemType e);//插入
    Status ListDelete(SqList *L,int i,ElemType *e);//删除
    void ListPrint(SqList L);//输出打印
    void DeleteMin(SqList *L);//删除最小
    
    Status InitList(SqList *L)
    {
        L->elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));//申请100空间
    	if(!L->elem)//申请失败
    		return ERROR;
    	L->length = 0;//长度0
    	L->listsize = LIST_INIT_SIZE;//容量100
    	return OK;//申请成功
    }
    
    Status ListInsert(SqList *L,int i,ElemType e)
    {
        int j;
        ElemType *newbase;
        if(i<1 || i>L->length+1)
            return ERROR;//非法输入
            
        if(L->length >= L->listsize)//存满了,需要更大空间
        {
            newbase = (ElemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType));//大10的空间
            if(!newbase)//申请失败
                return ERROR;
            L->elem = newbase;//调指针
            L->listsize+= LISTINCREMENT;//新容量
        }
        
        for(j=L->length;j>i-1;j--)//从后往前覆盖
            L->elem[j] = L->elem[j-1];
        L->elem[i-1] = e;//在留出的位置赋值
        L->length++;//长度+1
        return OK;
    }
    
    Status ListDelete(SqList *L,int i,ElemType *e)
    {
        int j;
        if(i<1 || i>L->length)//非法输入/表空
            return ERROR;
        *e = L->elem[i-1];//为了返回值
        for(j = i-1;j <= L->length;j++)//从前往后覆盖
            L->elem[j] = L->elem[j+1];
        (L->length)--;//长度减1
        return OK;//返回删除值
    }
    
    void ListPrint(SqList L)
    {
        int i;
        for(i=0;i<L.length;i++)
            printf("%d ",L.elem[i]);
        printf("\n");//为了美观
    }
    
    void DeleteMin(SqList *L)
    {
        //表空在Listdelete函数里判断
        int i;
        int j=0;//最小值下标
        ElemType *e;
        for(i=0;i<L->length;i++)//寻找最小
        {
            if(L->elem[i] < L->elem[j])
                j=i;
        }
        ListDelete(L,j+1,&e);//调用删除,注意j要+1
    }
    
    int main(void)
    {
    	SqList L;
    	int i;
    	ElemType e;
    	ElemType data[9] = {11,-22,-33,3,-88,21,77,0,-9};
    	InitList(&L);
    	for (i = 1; i <= 9; i++)
    	{
    		ListInsert(&L,i,data[i-1]);
    	}
    	printf("插入完成后 L = : ");
    	ListPrint(L);
        ListDelete(&L, 2, &e);
    	printf("删除第 2 个后L = : ");
    	ListPrint(L);
        DeleteMin(&L);
    	printf("删除L中最小值后L = : ");
    	ListPrint(L);
    	DeleteMin(&L);
    	printf("删除L中最小值后L = : ");
    	ListPrint(L);
    	DeleteMin(&L);
    	printf("删除L中最小值后L = : ");
    	ListPrint(L);
    }

    单链表,不带头实现

    链表是一种物理存储单元上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

    使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。链表最明显的好处就是,常规数组排列关联项目的方式可能不同于这些数据项目在记忆体磁盘上顺序,数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点,但是不允许随机存取。链表有很多种不同的类型:单向链表双向链表以及循环链表

     

    下面给出不带头的单链表标准实现:

    定义节点:

    typedef struct node 
    { 
        int data;
        struct node * next;
    }Node;

    尾插:

    void pushBackList(Node ** list, int data) 
    { 
        Node * head = *list;
        Node * newNode = (Node *)malloc(sizeof(Node));//申请空间
        newNode->data = data; newNode->next = NULL;
        if(*list == NULL)//为空
            *list = newNode;
        else//非空
        {
            while(head ->next != NULL)
                head = head->next;
            head->next = newNode;
        }
    }
    
    

    插入:

    int insertList(Node ** list, int index, int data) 
    {
        int n;
        int size = sizeList(*list); 
        Node * head = *list; 
        Node * newNode, * temp;
        if(index<0 || index>size) return 0;//非法
        newNode = (Node *)malloc(sizeof(Node)); //创建新节点
        newNode->data = data; 
        newNode->next = NULL;
        if(index == 0) //头插
        {
            newNode->next = head; 
            *list = newNode; 
            return 1; 
        }
        for(n=1; n<index; n++) //非头插
            head = head->next;
        if(index != size) 
            newNode->next = head->next; 
        //链表尾部next不需指定
        head->next = newNode; 
        return 1;
    }
    

    按值删除:

    void deleteList(Node ** list, int data) 
    { 
        Node * head = *list; Node * temp; 
        while(head->next!=NULL) 
        { 
            if(head->next->data != data) 
            { 
                head=head->next; 
                continue; 
            } 
            temp = head->next;
            if(head->next->next == NULL) //尾节点删除
                head->next = NULL; 
            else 
                head->next = temp->next; 
            free(temp);
        }    
        head = *list; 
        if(head->data == data) //头结点删除
        { 
            temp = head; 
            *list = head->next; 
            head = head->next; 
            free(temp); 
        }
    }
    

    打印:

    void printList(Node * head) 
    { 
        Node * temp = head; 
        for(; temp != NULL; temp=temp->next) 
            printf("%d ", temp->data); 
        printf("\n"); 
    }

    清空:

    void freeList(Node ** list) 
    { 
        Node * head = *list; 
        Node * temp = NULL; 
        while(head != NULL) //依次释放
        { 
            temp = head; 
            head = head->next; 
            free(temp); 
        } 
        *list = NULL; //置空
    }

    别的也没啥了,都是基本操作

    有些代码要分情况,很麻烦,可读性较强吧

    看我压缩代码:https://blog.csdn.net/hebtu666/article/details/81261043

     

    双链表带头实现

    以前写的不带头的单链表实现,当时也啥也没学,好多东西不知道,加上一心想压缩代码,减少情况,所以写得不太好。

    请教了老师,首先是命名问题和代码紧凑性等的改进。还有可读性方面的改进,多写了一些注释。并且因为带头的比较好写,好操作,所以标准写法也不是很长,繁琐。

     

     

    下面贴代码

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef struct node{
        int key;//数据
        struct node * prev;//前驱
        struct node * next;//后继
    }Node;

    初始化(带头) 

    Node * list;
    //初始化,这里·我们list不再是NULL,而是指向了一个节点
    //这个改进方便了很多操作,也不用借助二重指针把list和next统一表示了
    
    void init(Node * list)//初始化
    {
        list = (Node *)malloc(sizeof(Node));
        list->next = NULL;
        list->prev = NULL;
    }

    查找(不用再判断一下空不空)

    Node * find(int key,Node * list)
    {
        Node * head = list->next;//从头节点后面开始找
        while(head != NULL && head->key != key)//找到或空跳出
            head = head->next;
        return head;
    }

    打印

    void printList(Node * list)//打印
    {
        Node * temp = list->next;头节点下一个开始
        while(temp != NULL)
        {
            printf("%d ",temp->key);
            temp = temp->next;
        }
        printf("\n");
    }

    删除指定结点

    void delete(Node * list)//删除指定结点
    {
        list->prev->next = list->next;前面后面指针改了,再free自己即可
        list->next->prev = list->prev;
        free(list);
    }

    配合一下删除:

    void deleteKey(int key,Node * list)
    {
        delete(find(key,list));
    }

    头插:

    void insertHead(int key,Node * list)//头插
    {
        Node * newNode = (Node *)malloc(sizeof(Node));//初始化
        newNode->key = key;
        newNode->next = list->next;//赋值后继
        if(list->next != NULL)//如果有后继,赋值后继的前指针为新结点
            list->next->prev = newNode;
        list->next = newNode;//改头
        newNode->prev = list;//赋值新结点前指针
    }

    按下标插入

    单链表都写了,我就不写长度函数和判断非法了,用的时候注意吧。

    void insert(int key,Node * list,int index)
    {
        Node * head=list;//最后指到要插位置的前一个即可
        Node * newNode = (Node *)malloc(sizeof(Node));//初始化
        newNode->key = key;
        while(index--)
            head = head->next;
        newNode->next = head->next;//修改指针
        newNode->prev = head;
        head->next = newNode;
    }

    指定某值后插入不写了,和这个修改指针逻辑一样,再传一个find配合一下就行了。

     

    然后简单测试

    int main()
    {
        Node * list = NULL;
        init(list);
        insertHead(1,list);
        insertHead(2,list);
        insertHead(3,list);
        printList(list);
        deleteKey(2,list);
        printList(list);
        insert(10,list,0);
        printList(list);
    }

     

    第七次笔记(栈/队列)

     

    介绍栈和队列基本概念和用法。

     

    设输入序列1、2、3、4,则下述序列中( )不可能是出栈序列。【中科院中国科技大学2005】

    A. 1、2、3、4                      B. 4、 3、2、1

    C. 1、3、4、2                      D.4、1、2、3

    选D

    我是一个个模拟来做的。

     

    描述栈的基本型性质:

    1、集合性:栈是由若干个元素集合而成,没有元素(空集)成为空栈。

    2、线性:除栈顶和栈底之外,任意元素均有唯一前趋和后继。

    3、运算受限:只在一端插入删除的线性表即为栈

     

    顺序存储和顺序存取:顺序存取是只能逐个存或取结构中的元素,例如栈。顺序存储是利用一个连续的空间相继存放,例如栈可基于一维数组存放元素。

     

    一个较早入栈的元素能否在后面元素之前出栈?如果后面元素压在它上面,就不可以了。如果后面元素未压入,它可以弹出。在其他元素前面。

     

     

    栈与递归:

      当在一个函数的运行期间调用另一个函数时,在运行 该被调用函数之前,需先完成三件事:  将实参等传递给被调用函数,保存返回地址(入栈);  为被调用函数的局部变量分配存储区;    将控制转移到被调用函数的入口。  

    从被调用函数返回调用函数之前,应该完成:  保存被调函数的计算结果;  释放被调函数的数据区;  按被调函数保存的返回地址(出栈)将控制转移到调        用函数。

    多个函数嵌套调用的规则是:后调用先返回。

     此时的内存管理实行“栈式管理”

     

    队列:

            在多用户计算机系统中,各个用户需要使用 CPU 运行自己的程序,它们分别向操作系统提出使用 CPU 的请求,操作系统按照每个请求在时间上的先后顺序, 将其排成一个队列,每次把CPU分配给队头用户使用, 当相应的程序运行结束,则令其出队,再把CPU分配 给新的队头用户,直到所有用户任务处理完毕。

     

    以主机和打印机为例来说明,主机输出数据给打印 机打印,主机输出数据的速度比打印机打印的速度要快 得多,若直接把输出的数据送给打印机打印,由于速度 不匹配,显然不行。解决的方法是设置一个打印数据缓 冲区,主机把要打印的数据依此写到这个缓冲区中,写 满后就暂停输出,继而去做其它的事情,打印机就从缓 冲区中按照先进先出的原则依次取出数据并打印,打印 完后再向主机发出请求,主机接到请求后再向缓冲区写 入打印数据,这样利用队列既保证了打印数据的正确, 又使主机提高了效率。

     

    双端队列:

    某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作,若元素a,b,c,d,e依次入队列后,再进行出队操作,则不可能得到的顺序是( )。 

    A. bacde                B. dbace              C. dbcae                D. ecbad

    解析:出队只能一端,所以abcde一定是这个顺序。

    反模拟入队,每次只能在两边出元素。

     

    栈/队列 互相模拟实现

     

    用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。

    思路:大概这么想:用一个辅助栈把进第一个栈的元素倒一下就好了。

    比如进栈1,2,3,4,5

    第一个栈:

    5

    4

    3

    2

    1

    然后倒到第二个栈里

    1

    2

    3

    4

    5

    再倒出来,顺序为1,2,3,4,5

    实现队列

    然后要注意的事情:

    1)栈2非空不能往里面倒数,顺序就错了。栈2没数再从栈1倒。

    2)栈1要倒就一次倒完,不倒完的话,进新数也会循序不对。

    import java.util.Stack;
     
    public class Solution {
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();
         
        public void push(int node) {
            stack1.push(node);
        }
         
        public int pop() {
            if(stack1.empty()&&stack2.empty()){
                throw new RuntimeException("Queue is empty!");
            }
            if(stack2.empty()){
                while(!stack1.empty()){
                    stack2.push(stack1.pop());
                }
            }
            return stack2.pop();
        }
    }

     

    用两个队列实现栈,要求同上:

    这其实意义不是很大,有些数据结构书上甚至说两个队列不能实现栈。

    其实是可以的,只是时间复杂度较高,一个弹出操作时间为O(N)。

    思路:两个队列,编号为1和2.

    进栈操作:进1号队列

    出栈操作:把1号队列全弄到2号队列里,剩最后一个别压入,而是返回。

    最后还得把1和2号换一下,因为现在是2号有数,1号空。

     

    仅仅有思考价值,不实用。

    比如压入1,2,3

    队列1:1,2,3

    队列2:空

    依次弹出1,2,3:

    队列1里的23进入2号,3弹出

    队列1:空

    队列2:2,3

     

    队列2中3压入1号,2弹出

    队列1:3

    队列2:空

     

    队列1中只有一个元素,弹出。

     

    上代码:

    public class TwoQueueImplStack {
    	Queue<Integer> queue1 = new ArrayDeque<Integer>();
    	Queue<Integer> queue2 = new ArrayDeque<Integer>();
    //压入
    	public void push(Integer element){
    		//都为空,优先1
    		if(queue1.isEmpty() && queue2.isEmpty()){
    			queue1.add(element);
    			return;
    		}
    		//1为空,2有数据,放入2
    		if(queue1.isEmpty()){
    			queue2.add(element);
    			return;
    		}
    		//2为空,1有数据,放入1
    		if(queue2.isEmpty()){
    			queue1.add(element);
    			return;
    		}
    	}
    //弹出
    	public Integer pop(){
    		//两个都空,异常
    		if(queue1.isEmpty() && queue2.isEmpty()){
    			try{
    				throw new Exception("satck is empty!");
    			}catch(Exception e){
    				e.printStackTrace();
    			}
    		}	
    		//1空,2有数据,将2中的数据依次放入1,最后一个元素弹出
    		if(queue1.isEmpty()){
    			while(queue2.size() > 1){
    				queue1.add(queue2.poll());
    			}
    			return queue2.poll();
    		}
    		
    		//2空,1有数据,将1中的数据依次放入2,最后一个元素弹出
    		if(queue2.isEmpty()){
    			while(queue1.size() > 1){
    				queue2.add(queue1.poll());
    			}
    			return queue1.poll();
    		}
    		
    		return (Integer)null;
    	}
    //测试
    	public static void main(String[] args) {
    		TwoQueueImplStack qs = new TwoQueueImplStack();
    		qs.push(2);
    		qs.push(4);
    		qs.push(7);
    		qs.push(5);
    		System.out.println(qs.pop());
    		System.out.println(qs.pop());
    		
    		qs.push(1);
    		System.out.println(qs.pop());
    	}
    }
    

     

    第八次笔记 (串)

    串的概念:串(字符串):是由 0 个或多个字符组成的有限序列。 通常记为:s =‘ a1 a2 a3 … ai …an  ’ ( n≥0 )。

    串的逻辑结构和线性表极为相似。

     

    一些串的类型:

     

    空串:不含任何字符的串,长度 = 0。

    空格串:仅由一个或多个空格组成的串。

    子串:由串中任意个连续的字符组成的子序列。

    主串:包含子串的串。

    位置:字符在序列中的序号。

    子串在主串中的位置:子串的首字符在主串中的位置。

     

    空串是任意串的子串,任意串是其自身的子串。

    串相等的条件:当两个串的长度相等且各个对应位置的字符都相等时才相等。

     

    实现:

     

    因为串是特殊的线性表,故其存储结构与线性表的 存储结构类似,只不过组成串的结点是单个字符。

     

    定长顺序存储表示

    也称为静态存储分配的顺序串。 即用一组地址连续的存储单元依次存放串中的字符序列。

     

    串长:可能首字符记录(显式)或\0结尾(隐式)

     

    定长顺序存储表示时串操作的缺点 :串的某些操作受限(截尾),如串的联接、插入、置换

     

    堆分配存储表示  

     

    存储空间在程序执行过程中动态分配,malloc() 分配一块实际串长所需要的存储空间(“堆”)

    堆存储结构的优点:堆存储结构既有顺序存储 结构的特点,处理(随机取子串)方便,操作中对 串长又没有任何限制,更显灵活,因此在串处理的 应用程序中常被采用。

     

    串的块链存储表示

    为了提高空间利用率,可使每个结点存放多个字符 (这是顺序串和链串的综合 (折衷) ),称为块链结构。

     优点:便于插入和删除    缺点:空间利用率低 

     

    串的定长表示

    思想和代码都不难,和线性表也差不多,串本来就是数据受限的线性表。

    串连接:

     

    #include <stdio.h>
    #include <string.h>
    //串的定长顺序存储表示
    #define MAXSTRLEN 255							//用户可在255以内定义最大串长
    typedef unsigned char SString[MAXSTRLEN + 1];	//0号单元存放串的长度
    
    int Concat(SString *T,SString S1,SString S2)
    	//用T返回S1和S2联接而成的新串。若未截断返回1,若截断返回0
    {
    	int i = 1,j,uncut = 0;
    	if(S1[0] + S2[0] <= MAXSTRLEN)	//未截断
    	{
    		for (i = 1; i <= S1[0]; i++)//赋值时等号不可丢
    			(*T)[i] = S1[i];
    		for (j = 1; j <= S2[0]; j++)
    			(*T)[S1[0]+j] = S2[j];	//(*T)[i+j] = S2[j]
    		(*T)[0] = S1[0] + S2[0];
    		uncut = 1;
    	}
    	else if(S1[0] < MAXSTRLEN)		//截断
    	{
    		for (i = 1; i <= S1[0]; i++)//赋值时等号不可丢
    			(*T)[i] = S1[i];
    
    		for (j = S1[0] + 1; j <= MAXSTRLEN; j++)
    		{
    			(*T)[j] = S2[j - S1[0] ];
    			(*T)[0] = MAXSTRLEN;
    			uncut = 0;
    		}
    	}
    	else
    	{
    		for (i = 0; i <= MAXSTRLEN; i++)
    			(*T)[i] = S1[i];
    		/*或者分开赋值,先赋值内容,再赋值长度
    		for (i = 1; i <= MAXSTRLEN; i++)
    			(*T)[i] = S1[i];
    		(*T)[0] = MAXSTRLEN;
    		*/
    		uncut = 0;
    	}
    
    	return uncut;
    }
    
    int SubString(SString *Sub,SString S,int pos,int len)
    	//用Sub返回串S的第pos个字符起长度为len的子串
    	//其中,1 ≤ pos ≤ StrLength(S)且0 ≤ len ≤ StrLength(S) - pos + 1(从pos开始到最后有多少字符)
    	//第1个字符的下标为1,因为第0个字符存放字符长度
    {
    	int i;
    	if(pos < 1 || pos > S[0] || len < 0 || len > S[0] - pos + 1)
    		return 0;
    	for (i = 1; i <= len; i++)
    	{
    		//S中的[pos,len]的元素 -> *Sub中的[1,len]
    		(*Sub)[i] = S[pos + i - 1];//下标运算符 > 寻址运算符的优先级
    	}
    	(*Sub)[0] = len;
    	return 1;
    }
    void PrintStr(SString S)
    {
    	int i;
    	for (i = 1; i <= S[0]; i++)
    		printf("%c",S[i]);
    	printf("\n");
    }
    
    
    int main(void)
    {
    	/*定长顺序存储初始化和打印的方法
    	SString s = {4,'a','b','c','d'};
    	int i;
    	//s = "abc";	//不可直接赋值
    	for (i = 1; i <= s[0]; i++)
    		printf("%c",s[i]);
    	*/
    	SString s1 = {4,'a','b','c','d'};
    	SString s2 = {4,'e','f','g','h'},s3;
    	SString T,Sub;
    	int i;
    	
    	for (i = 1; i <= 255; i++)
    	{
    		s3[i] = 'a';
    		if(i >= 248)
    			s3[i] = 'K';
    	}
    	s3[0] = 255;
    	SubString(&Sub,s3,247,8);
    	PrintStr(Sub);
    	
    
    
    
    	return 0;
    }

    第九次笔记(数组,广义表)

    数组:按一定格式排列起来的具有相同类型的数据元素的集合。

     

    二维数组:若一维数组中的数据元素又是一维数组结构,则称为二维数组。 

    同理,推广到多维数组。若 n -1 维数组中的元素又是一个一维数组结构,则称作 n 维数组。 

    声明格式:数据类型   变量名称[行数] [列数] ;

     

    实现:一般都是采用顺序存储结构来表示数组。

     

    二维数组两种顺序存储方式:以行序为主序 (低下标优先) 、以列序为主序 (高下标优先)

    一个二维数组 A,行下标的范围是 1 到 6,列下标的范围是 0 到 7,每个数组元素用相邻的6 个字节存储,存储器按字节编址。那么,这个数组的体积是288个字节。

     

     广义表(又称列表 Lists)是n≥0个元素 a1, a2, …, an 的有限序列,其中每一个ai 或者是原子,或者是一个子表。

     

    表头:若 LS 非空 (n≥1 ),则其第一个元素 a1 就是表头。

     表尾:除表头之外的其它元素组成的表。记作  tail(LS) = (a2, ..., an)。 

     

    (( )) 长度为 1,表头、表尾均为 ( )

    (a, (b, c))长度为 2,由原子 a 和子表 (b, c) 构成。表头为 a ;表尾为 ((b, c))。

     

    广义表的长度定义为最外层所包含元素的个数

    广义表的深度定义为该广义表展开后所含括号的重数。

    “原子”的深度为 0 ;  “空表”的深度为 1 。

     

    取表头运算 GetHead  和取表尾运算 GetTail

    GetHead(LS) = a1        GetTail(LS) = (a2, …, an)。

     

    广义表可看成是线性表的推广,线性表是广义表的特例。

     

    广义表的结构相当灵活,在某种前提下,它可以兼容线 性表、数组、树和有向图等各种常用的数据结构。

    由于广义表不仅集中了线性表、数组、树和有向图等常 见数据结构的特点,而且可有效地利用存储空间,因此在计算机的许多应用领域都有成功使用广义表的实例。 

     

     

    第十次笔记(树和二叉树)

     

    树的定义:树(Tree)是 n(n≥0)个结点的有限集。若 n=0,称为空树;若 n > 0,则它满足如下两个条件:  

    (1)  有且仅有一个特定的称为根 (Root) 的结点;  

    (2)  其余结点可分为 m (m≥0) 个互不相交的有限集 T1, T2, T3, …, Tm, 其中每一个集合本身又是一棵树,并称为根的子树 (SubTree)。

    显然,树的定义是一个递归的定义。

    树的一些术语:

    • 结点的度(Degree):结点的子树个数;
    • 树的度:树的所有结点中最大的度数;
    • 叶结点(Leaf):度为0的结点;
    • 父结点(Parent):有子树的结点是其子树的根节点的父结点;
    • 子结点/孩子结点(Child):若A结点是B结点的父结点,则称B结点是A结点的子结点;
    • 兄弟结点(Sibling):具有同一个父结点的各结点彼此是兄弟结点;
    • 路径和路径长度:从结点n1到nk的路径为一个结点序列n1,n2,...,nk。ni是ni+1的父结点。路径所包含边的个数为路径的长度;
    • 祖先结点(Ancestor):沿树根到某一结点路径上的所有结点都是这个结点的祖先结点;
    • 子孙结点(Descendant):某一结点的子树中的所有结点是这个结点的子孙;
    • 结点的层次(Level):规定根结点在1层,其他任一结点的层数是其父结点的层数加1;
    • 树的深度(Depth):树中所有结点中的最大层次是这棵树的深度;

    将树中节点的各子树看成从左至右是有次序的(即不能互换),则称为该树是有序树,否则称为无序树

    森林(forest)是 m (m≥0) 棵互不相交的树的集合。

     

    二叉树

     

    在计算机科学中,二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。

     

    虽然二叉树与树概念不同,但有关树的基本术语对二叉树都适用。

     

    二叉树结点的子树要区分左子树和右子树,即使只有一 棵子树也要进行区分,说明它是左子树,还是右子树。树当 结点只有一个孩子时,就无须区分它是左还是右。

     

    注意:尽管二叉树与树有许多相似之处,但二叉树不是树的特殊情形。

    一些性质:

    在二叉树的第 i 层上至多有  个结点 (i ≥1)。

    证明:每个节点至多两个孩子,每一层至多比上一层多一倍的结点,根为1.

     

    深度为 k 的二叉树至多有 个结点(k ≥1)。

    证明:把每一层最大节点加起来即可

     

    对任何一棵二叉树 T,如果其叶子数为 n0,度为 2的结点数为 n2,则 n0 = n2 + 1。

    证明:对于一个只有根的树,n0 = n2 + 1成立。1=0+1

    我们把一个叶子节点换成度为2的结点:

    黑色节点原来为叶子节点

    我们发现,度为2的结点数加1(黑色节点);叶子节点数加1(原来的去掉,新增两个);对于式子n0 = n2 + 1没影响,还是成立。

     

    我们把叶子节点换成度为1的结点,比如没有右孩子。

    我们发现,度为2的结点数没变。叶子节点数没变(减了一个加了一个)

    所以,不管你怎么换,公式都成立。(佛系证明)

     

     

    二叉树概述

     

    各种实现和应用以后放链接

    一、二叉树的基本概念

    二叉树:二叉树是每个节点最多有两个子树的树结构。

    根节点:一棵树最上面的节点称为根节点。

    父节点子节点:如果一个节点下面连接多个节点,那么该节点称为父节点,它下面的节点称为子 节点。

    叶子节点:没有任何子节点的节点称为叶子节点。

    兄弟节点:具有相同父节点的节点互称为兄弟节点。

    节点度:节点拥有的子树数。上图中,13的度为2,46的度为1,28的度为0。

    树的深度:从根节点开始(其深度为0)自顶向下逐层累加的。上图中,13的深度是1,30的深度是2,28的深度是3。

    树的高度:从叶子节点开始(其高度为0)自底向上逐层累加的。54的高度是2,根节点23的高度是3。

    对于树中相同深度的每个节点来说,它们的高度不一定相同,这取决于每个节点下面的叶子节点的深度。上图中,13和54的深度都是1,但是13的高度是1,54的高度是2。

    二、二叉树的类型

    类型定义图示

    满二叉树

    Full Binary Tree

    除最后一层无任何子节点外,每一层上的所有节点都有两个子节点,最后一层都是叶子节点。满足下列性质:

    1)一颗树深度为h,最大层数为k,深度与最大层数相同,k=h;

    2)叶子节点数(最后一层)为2k−1;

    3)第 i 层的节点数是:2i−1;

    4)总节点数是:2k−1,且总节点数一定是奇数。

    完全二叉树

    Complete Binary Tree

    若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。满足下列性质:

    1)只允许最后一层有空缺结点且空缺在右边,即叶子节点只能在层次最大的两层上出现;

    2)对任一节点,如果其右子树的深度为j,则其左子树的深度必为j或j+1。 即度为1的点只有1个或0个;

    3)除最后一层,第 i 层的节点数是:2i−1;

    4)有n个节点的完全二叉树,其深度为:log2n+1或为log2n+1;

    5)满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树。

    平衡二叉树

    Balanced Binary Tree

    又被称为AVL树,它是一颗空树或左右两个子树的高度差的绝对值不超过 1,并且左右两个子树都是一棵平衡二叉树。

    二叉搜索树

    Binary Search Tree

    又称二叉查找树、二叉排序树(Binary Sort Tree)。它是一颗空树或是满足下列性质的二叉树:

    1)若左子树不空,则左子树上所有节点的值均小于或等于它的根节点的值;

    2)若右子树不空,则右子树上所有节点的值均大于或等于它的根节点的值;

    3)左、右子树也分别为二叉排序树。

    红黑树

    Red Black Tree

    是每个节点都带有颜色属性(颜色为红色或黑色)的自平衡二叉查找树,满足下列性质:

    1)节点是红色或黑色;

    2)根节点是黑色;

    3)所有叶子节点都是黑色;

    4)每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)

    5)从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

     

     

     

     

     

     

     

     

     

    啦啦啦

     

     

    第十一次笔记(满二叉树,完全二叉树)

    因为图片丢失,内容不全,我尽量找一下图

    满二叉树 (Full binary tree)

    除最后一层无任何子节点外,每一层上的所有结点都有两个子结点二叉树。

    国内教程定义:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是(2^k) -1 ,则它就是满二叉树。

    国外(国际)定义:a binary tree T is full if each node is either a leaf or possesses exactly two childnodes.

    大意为:如果一棵二叉树的结点要么是叶子结点,要么它有两个子结点,这样的树就是满二叉树。(一棵满二叉树的每一个结点要么是叶子结点,要么它有两个子结点,但是反过来不成立,因为完全二叉树也满足这个要求,但不是满二叉树)

    从图形形态上看,满二叉树外观上是一个三角形。

    这里缺失公式

    完全二叉树

     

    完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

    可以根据公式进行推导,假设n0是度为0的结点总数(即叶子结点数),n1是度为1的结点总数,n2是度为2的结点总数,则 :

    ①n= n0+n1+n2 (其中n为完全二叉树的结点总数);又因为一个度为2的结点会有2个子结点,一个度为1的结点会有1个子结点,除根结点外其他结点都有父结点,

    ②n= 1+n1+2*n2 ;由①、②两式把n2消去得:n= 2*n0+n1-1,由于完全二叉树中度为1的结点数只有两种可能0或1,由此得到n0=n/2 或 n0=(n+1)/2。

    简便来算,就是 n0=n/2,其中n为奇数时(n1=0)向上取整;n为偶数时(n1=1)。可根据完全二叉树的结点总数计算出叶子结点数。

     

    重点:出于简便起见,完全二叉树通常采用数组而不是链表存储

     

    对于tree[i]有如下特点:

    (1)若i为奇数且i>1,那么tree的左兄弟为tree[i-1];

    (2)若i为偶数且i<n,那么tree的右兄弟为tree[i+1];

    (3)若i>1,tree的父亲节点为tree[i div 2];

    (4)若2*i<=n,那么tree的左孩子为tree[2*i];若2*i+1<=n,那么tree的右孩子为tree[2*i+1];

    (5)若i>n div 2,那么tree[i]为叶子结点(对应于(3));

    (6)若i<(n-1) div 2.那么tree[i]必有两个孩子(对应于(4))。

    (7)满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树。

    完全二叉树第i层至多有2^(i-1)个节点,共i层的完全二叉树最多有2^i-1个节点。

    特点:

    1)只允许最后一层有空缺结点且空缺在右边,即叶子结点只能在层次最大的两层上出现;

    2)对任一结点,如果其右子树的深度为j,则其左子树的深度必为j或j+1。 即度为1的点只有1个或0个

     

    第十二次笔记(二叉树的存储和遍历)

     

    顺序存储结构

     

    完全二叉树:用一组地址连续的 存储单元依次自上而下、自左至右存 储结点元素,即将编号为 i  的结点元 素存储在一维数组中下标为 i –1 的分量中。

    一般二叉树:将其每个结点与完 全二叉树上的结点相对照,存储在一 维数组的相应分量中。

     

    最坏情况:树退化为线性后:

    我们要把它“变”成这个大家伙来存了:

    深度为 k 的且只 有 k 个结点的右单支树需要 长度为2^k-1 的一维数组。 

     

    链式存储结构

    lchild和rchild都是指向相同结构的指针

    在 n 个结点的二叉链表中有 n + 1 个空指针域。

    typedef struct BiTNode { // 结点结构
        TElemType data;
        struct BiTNode *lchild,*rchild;// 左右孩子指针
    } BiTNode, *BiTree;
    

    可以多一条指向父的指针。

     

    遍历二叉树

     

    顺着某一条搜索路径巡访二叉树中的结点,使   得每个结点均被访问一次,而且仅被访问一次

     “访问”的含义很广,可以是对结点作各种处理, 如:输出结点的信息、修改结点的数据值等,但要求这种访问不破坏原来的数据结构。

    (所以有些题目比如morris遍历、链表后半段反转判断回文等等必须进行完,解题时就算已经得出答案也要遍历完,因为我们不能改变原来的数据结构。)

     

    具体遍历的介绍

    https://blog.csdn.net/hebtu666/article/details/82853988

     

    深入理解二叉树遍历

    二叉树:二叉树是每个节点最多有两个子树的树结构。

     

    本文介绍二叉树的遍历相关知识。

    我们学过的基本遍历方法,无非那么几个:前序,中序,后序,还有按层遍历等等。

    设L、D、R分别表示遍历左子树、访问根结点和遍历右子树, 则对一棵二叉树的遍历有三种情况:DLR(称为先根次序遍历),LDR(称为中根次序遍历),LRD (称为后根次序遍历)。

    首先我们定义一颗二叉树

    typedef char ElementType;
    typedef struct TNode *Position;
    typedef Position BinTree;
    struct TNode{
        ElementType Data;
        BinTree Left;
        BinTree Right;
    };
    

    前序

    首先访问根,再先序遍历左(右)子树,最后先序遍历右(左)子树

    思路:

    就是利用函数,先打印本个节点,然后对左右子树重复此过程即可。

    void PreorderTraversal( BinTree BT )
    {
        if(BT==NULL)return ;
        printf(" %c", BT->Data);
        PreorderTraversal(BT->Left);
        PreorderTraversal(BT->Right);
    }

     

    中序

    首先中序遍历左(右)子树,再访问根,最后中序遍历右(左)子树

    思路:

    还是利用函数,先对左边重复此过程,然后打印根,然后对右子树重复。

    void InorderTraversal( BinTree BT )
    {
        if(BT==NULL)return ;
        InorderTraversal(BT->Left);
        printf(" %c", BT->Data);
        InorderTraversal(BT->Right);
    }

    后序

    首先后序遍历左(右)子树,再后序遍历右(左)子树,最后访问根

    思路:

    先分别对左右子树重复此过程,然后打印根

    void PostorderTraversal(BinTree BT)
    {
        if(BT==NULL)return ;
        PostorderTraversal(BT->Left);
        PostorderTraversal(BT->Right);
        printf(" %c", BT->Data);
    }

    进一步思考

    看似好像很容易地写出了三种遍历。。。。。

     

    但是你真的理解为什么这么写吗?

    比如前序遍历,我们真的是按照定义里所讲的,首先访问根,再先序遍历左(右)子树,最后先序遍历右(左)子树。这种过程来遍历了一遍二叉树吗?

    仔细想想,其实有一丝不对劲的。。。

    再看代码:

    void Traversal(BinTree BT)//遍历
    {
    //1111111111111
        Traversal(BT->Left);
    //22222222222222
        Traversal(BT->Right);
    //33333333333333
    }

    为了叙述清楚,我给三个位置编了号 1,2,3

    我们凭什么能前序遍历,或者中序遍历,后序遍历?

    我们看,前序中序后序遍历,实现的代码其实是类似的,都是上面这种格式,只是我们分别在位置1,2,3打印出了当前节点而已啊。我们凭什么认为,在1打印,就是前序,在2打印,就是中序,在3打印,就是后序呢?不管在位置1,2,3哪里操作,做什么操作,我们利用函数遍历树的顺序变过吗?当然没有啊。。。

    都是三次返回到当前节点的过程:先到本个节点,也就是位置1,然后调用了其他函数,最后调用完了,我们开到了位置2。然后又调用别的函数,调用完了,我们来到了位置3.。然后,最后操作完了,这个函数才结束。代码里的三个位置,每个节点都被访问了三次。

    而且不管位置1,2,3打印了没有,操作了没有,这个顺序是永远存在的,不会因为你在位置1打印了,顺序就改为前序,你在位置2打印了,顺序就成了中序。

     

    为了有更直观的印象,我们做个试验:在位置1,2,3全都放入打印操作;

    我们会发现,每个节点都被打印了三次。而把每个数第一次出现拿出来,就组成了前序遍历的序列;所有数字第二次出现拿出来,就组成了中序遍历的序列。。。。

     

    其实,遍历是利用了一种数据结构:栈

    而我们这种写法,只是通过函数,来让系统帮我们压了栈而已。为什么能实现遍历?为什么我们访问完了左子树,能返回到当前节点?这都是栈的功劳啊。我们把当前节点(对于函数就是当时的现场信息)存到了栈里,记录下来,后来才能把它拿了出来,能回到以前的节点。

     

    想到这里,可能就有更深刻的理解了。

    我们能否不用函数,不用系统帮我们压栈,而是自己做一个栈,来实现遍历呢?

    先序实现思路:拿到一个节点的指针,先判断是否为空,不为空就先访问(打印)该结点,然后直接进栈,接着遍历左子树;为空则要从栈中弹出一个节点来,这个时候弹出的结点就是其父亲,然后访问其父亲的右子树,直到当前节点为空且栈为空时,结束。

    核心思路代码实现:

    *p=root;
    while(p || !st.empty())
    {
        if(p)//非空
        {
            //visit(p);进行操作
            st.push(p);//入栈
            p = p->lchild;左
        } 
        else//空
        {
            p = st.top();//取出
            st.pop();
            p = p->rchild;//右
        }
    }

    中序实现思路:和前序遍历一样,只不过在访问节点的时候顺序不一样,访问节点的时机是从栈中弹出元素时访问,如果从栈中弹出元素,就意味着当前节点父亲的左子树已经遍历完成,这时候访问父亲,就是中序遍历.

    (对应递归是第二次遇到)

    核心代码实现:

    *p=root;
    while(p || !st.empty())
    {
        if(p)//非空
        {
            st.push(p);//压入
            p = p->lchild;
        }
        else//空
        {
            p = st.top();//取出
            //visit(p);操作
            st.pop();
            p = p->rchild;
        }
    }

    后序遍历是最难的。因为要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点,这就为流程的控制带来了难点。

    因为我们原来说了,后序是第三次遇到才进行操作的,所以我们很容易有这种和递归函数类似的思路:对于任一结点,将其入栈,然后沿其左子树一直往下走,一直走到没有左孩子的结点,此时该结点在栈顶,但是不能出栈访问, 因此右孩子还没访问。所以接下来按照相同的规则对其右子树进行相同的处理。访问完右孩子,该结点又出现在栈顶,此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出,在这个过程中,每个结点都两次出现在栈顶,只有在第二次出现在栈顶时,才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。

    第二种思路:对于任一结点P,先将其入栈。如果P不存在左孩子和右孩子,或者左孩子和右孩子都已被访问过了,就可以直接访问该结点。如果有孩子未访问,将P的右孩子和左孩子依次入栈。

    网上的思路大多是第一种,所以我在这里给出第二种的大概实现吧

    首先初始化cur,pre两个指针,代表访问的当前节点和之前访问的节点。把根放入,开始执行。

    s.push(root);
    while(!s.empty())
    {
        cur=s.top();
        if((cur->lchild==NULL && cur->rchild==NULL)||(pre!=NULL && (pre==cur->lchild||pre==cur->rchild)))
        {
            //visit(cur);  如果当前结点没有孩子结点或者孩子节点都已被访问过 
            s.pop();//弹出
            pre=cur; //记录
        }
        else//分别放入右左孩子
        {
            if(cur->rchild!=NULL)
                s.push(cur->rchild);
            if(cur->lchild!=NULL)    
                s.push(cur->lchild);
        }
    }

    这两种方法,都是利用栈结构来实现的遍历,需要一定的栈空间,而其实存在一种时间O(N),空间O(1)的遍历方式,下次写了我再放链接。

     

    斗个小机灵:后序是LRD,我们其实已经知道先序是DLR,那其实我们可以用先序来实现后序啊,我们只要先序的时候把左右子树换一下:DRL(这一步很好做到),然后倒过来不就是DRL了嘛。。。。。就把先序代码改的左右反过来,然后放栈里倒过来就好了,不需要上面介绍的那些复杂的方法。。。。

    第十四次笔记(树的存储)

     

     

    父节点表示法

     

    数据域:存放结点本身信息。

    双亲域:指示本结点的双亲结点在数组中的位置。

    对应的树:

    /* 树节点的定义 */
    #define MAX_TREE_SIZE 100
     
    typedef struct{
        TElemType data;
        int parent; /* 父节点位置域 */
    } PTNode;
     
    typedef struct{
        PTNode nodes[MAX_TREE_SIZE];
        int n; /* 节点数 */
    } PTree;

    特点:找双亲容易,找孩子难。

    孩子表示法(树的链式存储结构)

     

    childi指向一个结点

    可以加上parent。

    在有 n 个结点、度为  d 的树的 d 叉链表中,有  n×(d-1)+1 个空链域

     

    我们可以用degree记录有几个孩子,省掉空间,但是结点的指针个数不相等,为该结点的度 degree。

     

    孩子链表:

     

    把每个结点的孩子结点排列起来,看成是一个线性表,用单链表存储,则 n 个结点有 n 个孩子链表(叶子的孩子链表为空表)。而 n 个头指针又组成一个线性表,用顺序表(含 n 个元素的结构数组)存储。

    孩子兄弟表示法(二叉树表示法)

    用二叉链表作树的存储结构,链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点

    typedef struct CSNode{
         ElemType data;
         struct CSNode *firstchild, *nextsibling;  
    } CSNode, *CSTree;
    

    第十五次笔记(图基础)

     

    图是一种:   数据元素间存在多对多关系的数据结构   加上一组基本操作构成的抽象数据类型。

    图 (Graph) 是一种复杂的非线性数据结构,由顶点集合及顶点间的关系(也称弧或边)集合组成。可以表示为: G=(V, VR)  

    其中 V 是顶点的有穷非空集合;

    VR 是顶点之间   关系的有穷集合,也叫做弧或边集合。

    弧是顶点的有序对,边是顶点的无序对。

     

    特点:(相对于线性结构)

    顶点之间的关系是任意的 

    图中任意两个顶点之间都可能相关

    顶点的前驱和后继个数无限制

     

    相关概念:

     

    顶点(Vertex):图中的数据元素。线性表中我们把数据元素叫元素,树中将数据元素叫结点。

    边:顶点之间的逻辑关系用边来表示,边集可以是空的。

     

    无向边(Edge):若顶点V1到V2之间的边没有方向,则称这条边为无向边。

    无向图(Undirected graphs):图中任意两个顶点之间的边都是无向边。(A,D)=(D,A)

    无向图中边的取值范围:0≤e≤n(n-1)/2

    有向边:若从顶点V1到V2的边有方向,则称这条边为有向边,也称弧(Arc)。用<V1,V2>表示,V1为狐尾(Tail),V2为弧头(Head)。(V1,V2)≠(V2,V1)。

    有向图(Directed graphs):图中任意两个顶点之间的边都是有向边。

    有向图中弧的取值范围:0≤e≤n(n-1)

       注意:无向边用“()”,而有向边用“< >”表示。

     

    简单图:图中不存在顶点到其自身的边,且同一条边不重复出现。

    无向完全图:无向图中,任意两个顶点之间都存在边。

    有向完全图:有向图中,任意两个顶点之间都存在方向互为相反的两条弧。

    稀疏图:有很少条边。

    稠密图:有很多条边。

     

    邻接点:若 (v, v´) 是一条边,则称顶点 v 和 v´互为 邻接点,或称 v 和 v´相邻接;称边 (v, v´) 依附于顶点 v 和 v´,或称 (v, v´) 与顶点 v 和 v´ 相关联。

     

    权(Weight):与图的边或弧相关的数。

    网(Network):带权的图。

    子图(Subgraph):假设G=(V,{E})和G‘=(V',{E'}),如果V'包含于V且E'包含于E,则称G'为G的子图。

     

     入度:有向图中以顶点 v 为头的弧的数目称为 v 的入度,记为:ID(v)。  

    出度:有向图中以顶点 v 为尾的弧的数目称为 v 的出度,记为:OD(v)。

    度(Degree):无向图中,与顶点V相关联的边的数目。有向图中,入度表示指向自己的边的数目,出度表示指向其他边的数目,该顶点的度等于入度与出度的和。

     

    回路(环):第一个顶点和最后一个顶点相同的路径。

    简单路径:序列中顶点(两端点除外)不重复出现的路径。 

    简单回路(简单环):前后两端点相同的简单路径。

    路径的长度:一条路径上边或弧的数量。

     

    连通:从顶点 v 到 v´ 有路径,则说 v  和 v´ 是连通的。

    连通图:图中任意两个顶点都是连通的。

    连通分量:无向图的极大连通子图(不存在包含它的 更大的连通子图);

    任何连通图的连通分量只有一个,即其本身;非连通图有多个连通分量(非连通图的每一个连通部分)。

    强连通图: 任意两个顶点都连通的有向图。 

    强连通分量:有向图的极大强连通子图;任何强连通 图的强连通分量只有一个,即其本身;非强连通图有多个 强连通分量。

     

    生成树:所有顶点均由边连接在一起但不存在回路的图。(n个顶点n-1条边)

     

     

     

     

    图的存储

     

    多重链表:完全模拟图的样子,每个节点内的指针都指向该指向的节点。

    节点结构内指针数为度

    缺点:浪费空间、不容易操作

     

    数组表示法(邻接矩阵表示法)

    可用两个数组存储。其中一个 一维数组存储数据元素(顶点)的信息,另一个二维数组 (邻接矩阵)存储数据元素之间的关系(边或弧)的信息

    有向图:

    有向网:

    缺点:用于稀疏图时空间浪费严重

    优点:操作较容易

     

    邻接表

    指针数组存放每个结点,每个结点后接所有能到达的节点。

     

    图的遍历

     

    从图的任意指定顶点出发,依照某种规则去访问图中所有顶 点,且每个顶点仅被访问一次,这一过程叫做图的遍历。

    图的遍历按照深度优先和广度优先规则去实施,通常有深度 优先遍历法(Depth_First Search——DFS )和  广度优先遍历法 ( Breadth_Frist Search——BFS)两种。

    简单棋盘搜索https://blog.csdn.net/hebtu666/article/details/81483407

    别的实现以后再贴

    如何判别V的邻接点是否被访问?

    为每个顶点设立一个“访问标志”。

     

    最小生成树

    问题提出:
        要在n个城市间建立通信联络网。顶点:表示城市,权:城市间通信线路的花费代价。希望此通信网花费代价最小。
    问题分析:
        答案只能从生成树中找,因为要做到任何两个城市之间有线路可达,通信网必须是连通的;但对长度最小的要求可以知道网中显然不能有圈,如果有圈,去掉一条边后,并不破坏连通性,但总代价显然减少了,这与总代价最小的假设是矛盾的。
    结论:
        希望找到一棵生成树,它的每条边上的权值之和(即建立该通信网所需花费的总代价)最小 —— 最小代价生成树。
        构造最小生成树的算法很多,其中多数算法都利用了一种称之为 MST 的性质。
        MST 性质:设 N = (V, E)  是一个连通网,U是顶点集 V的一个非空子集。若边 (u, v) 是一条具有最小权值的边,其中u∈U,v∈V-U,则必存在一棵包含边 (u, v) 的最小生成树。


    (1)普里姆 (Prim) 算法

    算法思想: 
        ①设 N=(V, E)是连通网,TE是N上最小生成树中边的集合。
        ②初始令 U={u_0}, (u_0∈V), TE={ }。
        ③在所有u∈U,u∈U-V的边(u,v)∈E中,找一条代价最小的边(u_0,v_0 )。
        ④将(u_0,v_0 )并入集合TE,同时v_0并入U。
        ⑤重复上述操作直至U = V为止,则 T=(V,TE)为N的最小生成树。

     
    代码实现:

    void MiniSpanTree_PRIM(MGraph G,VertexType u)
        //用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边。
        //记录从顶点集U到V-U的代价最小的边的辅助数组定义;
        //closedge[j].lowcost表示在集合U中顶点与第j个顶点对应最小权值
    {
        int k, j, i;
        k = LocateVex(G,u);
        for (j = 0; j < G.vexnum; ++j)    //辅助数组的初始化
            if(j != k)
            {
                closedge[j].adjvex = u;
                closedge[j].lowcost = G.arcs[k][j].adj;    
    //获取邻接矩阵第k行所有元素赋给closedge[j!= k].lowcost
            }
        closedge[k].lowcost = 0;        
    //初始,U = {u};  
        PrintClosedge(closedge,G.vexnum);
        for (i = 1; i < G.vexnum; ++i)    \
    //选择其余G.vexnum-1个顶点,因此i从1开始循环
        {
            k = minimum(G.vexnum,closedge);        
    //求出最小生成树的下一个结点:第k顶点
            PrintMiniTree_PRIM(G, closedge, k);     //输出生成树的边
            closedge[k].lowcost = 0;                //第k顶点并入U集
            PrintClosedge(closedge,G.vexnum);
            for(j = 0;j < G.vexnum; ++j)
            {                                           
                if(G.arcs[k][j].adj < closedge[j].lowcost)    
    //比较第k个顶点和第j个顶点权值是否小于closedge[j].lowcost
                {
                    closedge[j].adjvex = G.vexs[k];//替换closedge[j]
                    closedge[j].lowcost = G.arcs[k][j].adj;
                    PrintClosedge(closedge,G.vexnum);
                }
            }
        }
    }


    (2)克鲁斯卡尔 (Kruskal) 算法

    算法思想: 
        ①设连通网  N = (V, E ),令最小生成树初始状态为只有n个顶点而无边的非连通图,T=(V, { }),每个顶点自成一个连通分量。
        ②在 E 中选取代价最小的边,若该边依附的顶点落在T中不同的连通分量上(即:不能形成环),则将此边加入到T中;否则,舍去此边,选取下一条代价最小的边。
    ③依此类推,直至 T 中所有顶点都在同一连通分量上为止。
          
        最小生成树可能不惟一!

     

    拓扑排序

    (1)有向无环图

        无环的有向图,简称 DAG (Directed Acycline Graph) 图。
     
    有向无环图在工程计划和管理方面的应用:除最简单的情况之外,几乎所有的工程都可分为若干个称作“活动”的子工程,并且这些子工程之间通常受着一定条件的约束,例如:其中某些子工程必须在另一些子工程完成之后才能开始。
    对整个工程和系统,人们关心的是两方面的问题: 
    ①工程能否顺利进行; 
    ②完成整个工程所必须的最短时间。

    对应到有向图即为进行拓扑排序和求关键路径。 
    AOV网: 
        用一个有向图表示一个工程的各子工程及其相互制约的关系,其中以顶点表示活动,弧表示活动之间的优先制约关系,称这种有向图为顶点表示活动的网,简称AOV网(Activity On Vertex network)。
    例如:排课表
          
    AOV网的特点:
    ①若从i到j有一条有向路径,则i是j的前驱;j是i的后继。
    ②若< i , j >是网中有向边,则i是j的直接前驱;j是i的直接后继。
    ③AOV网中不允许有回路,因为如果有回路存在,则表明某项活动以自己为先决条件,显然这是荒谬的。


    问题:    
        问题:如何判别 AOV 网中是否存在回路?
        检测 AOV 网中是否存在环方法:对有向图构造其顶点的拓扑有序序列,若网中所有顶点都在它的拓扑有序序列中,则该AOV网必定不存在环。


    拓扑排序的方法:
        ①在有向图中选一个没有前驱的顶点且输出之。
        ②从图中删除该顶点和所有以它为尾的弧。
        ③重复上述两步,直至全部顶点均已输出;或者当图中不存在无前驱的顶点为止。
            
        一个AOV网的拓扑序列不是唯一的!
    代码实现:

    Status TopologicalSort(ALGraph G)
        //有向图G采用邻接表存储结构。
        //若G无回路,则输出G的顶点的一个拓扑序列并返回OK,否则返回ERROR.
        //输出次序按照栈的后进先出原则,删除顶点,输出遍历
    {
        SqStack S;
        int i, count;
        int *indegree1 = (int *)malloc(sizeof(int) * G.vexnum);
        int indegree[12] = {0};
        FindInDegree(G, indegree);    //求个顶点的入度下标从0开始
        InitStack(&S);
        PrintStack(S);
        for(i = 0; i < G.vexnum; ++i)
            if(!indegree[i])        //建0入度顶点栈S
                push(&S,i);        //入度为0者进栈
        count = 0;                //对输出顶点计数
        while (S.base != S.top)
        {
            ArcNode* p;
            pop(&S,&i);
            VisitFunc(G,i);//第i个输出栈顶元素对应的顶点,也就是最后进来的顶点    
            ++count;          //输出i号顶点并计数
            for(p = G.vertices[i].firstarc; p; p = p->nextarc)
            {    //通过循环遍历第i个顶点的表结点,将表结点中入度都减1
                int k = p->adjvex;    //对i号顶点的每个邻接点的入度减1
                if(!(--indegree[k]))
                    push(&S,k);        //若入度减为0,则入栈
            }//for
        }//while
        if(count < G.vexnum)
        {
            printf("\n该有向图有回路!\n");
            return ERROR;    //该有向图有回路
        }
        else
        {
            printf("\n该有向图没有回路!\n");
            return OK;
        }
    }


    关键路径

        把工程计划表示为有向图,用顶点表示事件,弧表示活动,弧的权表示活动持续时间。每个事件表示在它之前的活动已经完成,在它之后的活动可以开始。称这种有向图为边表示活动的网,简称为 AOE网 (Activity On Edge)。
    例如:
    设一个工程有11项活动,9个事件。
    事件v_1——表示整个工程开始(源点) 
    事件v_9——表示整个工程结束(汇点)

     
    对AOE网,我们关心两个问题:  
    ①完成整项工程至少需要多少时间? 
    ②哪些活动是影响工程进度的关键?
    关键路径——路径长度最长的路径。
    路径长度——路径上各活动持续时间之和。
    v_i——表示事件v_i的最早发生时间。假设开始点是v_1,从v_1到〖v�i〗的最长路径长度。ⅇ(ⅈ)——表示活动a_i的最早发生时间。
    l(ⅈ)——表示活动a_i最迟发生时间。在不推迟整个工程完成的前提下,活动a_i最迟必须开始进行的时间。
    l(ⅈ)-ⅇ(ⅈ)意味着完成活动a_i的时间余量。
    我们把l(ⅈ)=ⅇ(ⅈ)的活动叫做关键活动。显然,关键路径上的所有活动都是关键活动,因此提前完成非关键活动并不能加快工程进度。
        例如上图中网,从从v_1到v_9的最长路径是(v_1,v_2,v_5,v_8,ν_9 ),路径长度是18,即ν_9的最迟发生时间是18。而活动a_6的最早开始时间是5,最迟开始时间是8,这意味着:如果a_6推迟3天或者延迟3天完成,都不会影响整个工程的完成。因此,分析关键路径的目的是辨别哪些是关键活动,以便争取提高关键活动的工效,缩短整个工期。
        由上面介绍可知:辨别关键活动是要找l(ⅈ)=ⅇ(ⅈ)的活动。为了求ⅇ(ⅈ)和l(ⅈ),首先应求得事件的最早发生时间vⅇ(j)和最迟发生时间vl(j)。如果活动a_i由弧〈j,k〉表示,其持续时间记为dut(〈j,k〉),则有如下关系:
    ⅇ(ⅈ)= vⅇ(j)
    l(ⅈ)=vl(k)-dut(〈j,k〉)
        求vⅇ(j)和vl(j)需分两步进行:
    第一步:从vⅇ(0)=0开始向前递推
    vⅇ(j)=Max{vⅇ(i)+dut(〈j,k〉)}   〈i,j〉∈T,j=1,2,…,n-1
    其中,T是所有以第j个顶点为头的弧的集合。
    第二步:从vl(n-1)=vⅇ(n-1)起向后递推
    vl(i)=Min{vl(j)-dut(〈i,j〉)}  〈i,j〉∈S,i=n-2,…,0
    其中,S是所有以第i个顶点为尾的弧的集合。
    下面我们以上图AOE网为例,先求每个事件v_i的最早发生时间,再逆向求每个事件对应的最晚发生时间。再求每个活动的最早发生时间和最晚发生时间,如下面表格:
              
    在活动的统计表中,活动的最早发生时间和最晚发生时间相等的,就是关键活动


    关键路径的讨论:

    ①若网中有几条关键路径,则需加快同时在几条关键路径上的关键活动。      如:a11、a10、a8、a7。 
    ②如果一个活动处于所有的关键路径上,则提高这个活动的速度,就能缩短整个工程的完成时间。如:a1、a4。
    ③处于所有关键路径上的活动完成时间不能缩短太多,否则会使原关键路径变成非关键路径。这时必须重新寻找关键路径。如:a1由6天变成3天,就会改变关键路径。

    关键路径算法实现:

    int CriticalPath(ALGraph G)
    {    //因为G是有向网,输出G的各项关键活动
        SqStack T;
        int i, j;    ArcNode* p;
        int k , dut;
        if(!TopologicalOrder(G,T))
            return 0;
        int vl[VexNum];
        for (i = 0; i < VexNum; i++)
            vl[i] = ve[VexNum - 1];        //初始化顶点事件的最迟发生时间
        while (T.base != T.top)            //按拓扑逆序求各顶点的vl值
        {
     
            for(pop(&T, &j), p = G.vertices[j].firstarc; p; p = p->nextarc)
            {
                k = p->adjvex;    dut = *(p->info);    //dut<j, k>
                if(vl[k] - dut < vl[j])
                    vl[j] = vl[k] - dut;
            }//for
        }//while
        for(j = 0; j < G.vexnum; ++j)    //求ee,el和关键活动
        {
            for (p = G.vertices[j].firstarc; p; p = p->nextarc)
            {
                int ee, el;        char tag;
                k = p->adjvex;    dut = *(p->info);
                ee = ve[j];    el = vl[k] - dut;
                tag = (ee == el) ? '*' : ' ';
                PrintCriticalActivity(G,j,k,dut,ee,el,tag);
            }
        }
        return 1;
    }

     

    最短路 

    最短路

        典型用途:交通网络的问题——从甲地到乙地之间是否有公路连通?在有多条通路的情况下,哪一条路最短?
     
        交通网络用有向网来表示:顶点——表示城市,弧——表示两个城市有路连通,弧上的权值——表示两城市之间的距离、交通费或途中所花费的时间等。
        如何能够使一个城市到另一个城市的运输时间最短或运费最省?这就是一个求两座城市间的最短路径问题。
        问题抽象:在有向网中A点(源点)到达B点(终点)的多条路径中,寻找一条各边权值之和最小的路径,即最短路径。最短路径与最小生成树不同,路径上不一定包含n个顶点,也不一定包含n - 1条边。
       常见最短路径问题:单源点最短路径、所有顶点间的最短路径
    (1)如何求得单源点最短路径?
        穷举法:将源点到终点的所有路径都列出来,然后在其中选最短的一条。但是,当路径特别多时,特别麻烦;没有规律可循。
        迪杰斯特拉(Dijkstra)算法:按路径长度递增次序产生各顶点的最短路径。
    路径长度最短的最短路径的特点:
        在此路径上,必定只含一条弧 <v_0, v_1>,且其权值最小。由此,只要在所有从源点出发的弧中查找权值最小者。
    下一条路径长度次短的最短路径的特点:
    ①、直接从源点到v_2<v_0, v_2>(只含一条弧);
    ②、从源点经过顶点v_1,再到达v_2<v_0, v_1>,<v_1, v_2>(由两条弧组成)
    再下一条路径长度次短的最短路径的特点:
        有以下四种情况:
        ①、直接从源点到v_3<v_0, v_3>(由一条弧组成);
        ②、从源点经过顶点v_1,再到达v_3<v_0, v_1>,<v_1, v_3>(由两条弧组成);
        ③、从源点经过顶点v_2,再到达v_3<v_0, v_2>,<v_2, v_3>(由两条弧组成);
        ④、从源点经过顶点v_1  ,v_2,再到达v_3<v_0, v_1>,<v_1, v_2>,<v_2, v_3>(由三条弧组成);
    其余最短路径的特点:    
        ①、直接从源点到v_i<v_0, v_i>(只含一条弧);
        ②、从源点经过已求得的最短路径上的顶点,再到达v_i(含有多条弧)。
    Dijkstra算法步骤:
        初始时令S={v_0},  T={其余顶点}。T中顶点对应的距离值用辅助数组D存放。
        D[i]初值:若<v_0, v_i>存在,则为其权值;否则为∞。 
        从T中选取一个其距离值最小的顶点v_j,加入S。对T中顶点的距离值进行修改:若加进v_j作中间顶点,从v_0到v_i的距离值比不加 vj 的路径要短,则修改此距离值。
        重复上述步骤,直到 S = V 为止。

    算法实现:

    void ShortestPath_DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D)
    { // 用Dijkstra算法求有向网 G 的 v0 顶点到其余顶点v的最短路径P[v]及带权长度D[v]。
        // 若P[v][w]为TRUE,则 w 是从 v0 到 v 当前求得最短路径上的顶点。  P是存放最短路径的矩阵,经过顶点变成TRUE
        // final[v]为TRUE当且仅当 v∈S,即已经求得从v0到v的最短路径。
        int v,w,i,j,min;
        Status final[MAX_VERTEX_NUM];
        for(v = 0 ;v < G.vexnum ;++v)
        {
            final[v] = FALSE;
            D[v] = G.arcs[v0][v].adj;        //将顶点数组中下标对应是 v0 和 v的距离给了D[v]
            for(w = 0;w < G.vexnum; ++w)
                P[v][w] = FALSE;            //设空路径
            if(D[v] < INFINITY)
            {
                P[v][v0] = TRUE;
                P[v][v] = TRUE;
            }
        }
        D[v0]=0;
        final[v0]= TRUE; /* 初始化,v0顶点属于S集 */
        for(i = 1;i < G.vexnum; ++i) /* 其余G.vexnum-1个顶点 */
        { /* 开始主循环,每次求得v0到某个v顶点的最短路径,并加v到S集 */
            min = INFINITY; /* 当前所知离v0顶点的最近距离 */
            for(w = 0;w < G.vexnum; ++w)
                if(!final[w]) /* w顶点在V-S中 */
                    if(D[w] < min)
                    {
                        v = w;
                        min = D[w];
                    } /* w顶点离v0顶点更近 */
                    final[v] = TRUE; /* 离v0顶点最近的v加入S集 */
                    for(w = 0;w < G.vexnum; ++w) /* 更新当前最短路径及距离 */
                    {
                        if(!final[w] && min < INFINITY && G.arcs[v][w].adj < INFINITY && (min + G.arcs[v][w].adj < D[w]))
                        { /* 修改D[w]和P[w],w∈V-S */
                            D[w] = min + G.arcs[v][w].adj;
                            for(j = 0;j < G.vexnum;++j)
                                P[w][j] = P[v][j];
                            P[w][w] = TRUE;
                        }
                    }
        }
    }

     

    经典二分问题

    经典二分问题:给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target  。

    写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
    示例 1:

    输入: nums = [-1,0,3,5,9,12], target = 9。输出: 4
    解释: 9 出现在 nums 中并且下标为 4
    示例 2:

    输入: nums = [-1,0,3,5,9,12], target = 2。输出: -1
    解释: 2 不存在 nums 中因此返回 -1

    思路1:我们当然可以一个数一个数的遍历,但是毫无疑问要被大妈鄙视,这可怎么办呢?

    思路2:二分查找
    二分查找是一种基于比较目标值和数组中间元素的教科书式算法。

    如果目标值等于中间元素,则找到目标值。
    如果目标值较小,证明目标值小于中间元素及右边的元素,继续在左侧搜索。
    如果目标值较大,证明目标值大于中间元素及左边的元素,继续在右侧搜索。

    算法代码描述:

    初始化指针 left = 0, right = n - 1。
    当 left <= right:
    比较中间元素 nums[pivot] 和目标值 target 。
    如果 target = nums[pivot],返回 pivot。
    如果 target < nums[pivot],则在左侧继续搜索 right = pivot - 1。
    如果 target > nums[pivot],则在右侧继续搜索 left = pivot + 1。

    算法实现:照例贴出三种语言的实现,在Java实现中给出了详细注释

    class Solution {
      public int search(int[] nums, int target) {
    	//分别准备好左右端点
        int left = 0, right = nums.length - 1;
    	//循环二分
        while (left <= right) {
    	//取中点
          int pivot = left + (right - left) / 2;
    	  //找到答案并返回
          if (nums[pivot] == target) return pivot;
    	  //向左继续找
          if (target < nums[pivot]) right = pivot - 1;
    	  //向右继续找
          else left = pivot + 1;
        }
    	//未找到,返回-1
        return -1;
      }
    }
    class Solution:
        def search(self, nums: List[int], target: int) -> int:
            left, right = 0, len(nums) - 1
            while left <= right:
                pivot = left + (right - left) // 2
                if nums[pivot] == target:
                    return pivot
                if target < nums[pivot]:
                    right = pivot - 1
                else:
                    left = pivot + 1
            return -1
    class Solution {
      public:
      int search(vector<int>& nums, int target) {
        int pivot, left = 0, right = nums.size() - 1;
        while (left <= right) {
          pivot = left + (right - left) / 2;
          if (nums[pivot] == target) return pivot;
          if (target < nums[pivot]) right = pivot - 1;
          else left = pivot + 1;
        }
        return -1;
      }
    };

     

     

     

    二叉搜索树实现

    本文给出二叉搜索树介绍和实现

     

    首先说它的性质:所有的节点都满足,左子树上所有的节点都比自己小,右边的都比自己大。

     

    那这个结构有什么有用呢?

    首先可以快速二分查找。还可以中序遍历得到升序序列,等等。。。

    基本操作:

    1、插入某个数值

    2、查询是否包含某个数值

    3、删除某个数值

     

    根据实现不同,还可以实现其他很多种操作。

     

    实现思路思路:

    前两个操作很好想,就是不断比较,大了往左走,小了往右走。到空了插入,或者到空都没找到。

    而删除稍微复杂一些,有下面这几种情况:

    1、需要删除的节点没有左儿子,那就把右儿子提上去就好了。

    2、需要删除的节点有左儿子,这个左儿子没有右儿子,那么就把左儿子提上去

    3、以上都不满足,就把左儿子子孙中最大节点提上来。

     

    当然,反过来也是成立的,比如右儿子子孙中最小的节点。

     

    下面来叙述为什么可以这么做。

    下图中A为待删除节点。

    第一种情况:

     

    1、去掉A,把c提上来,c也是小于x的没问题。

    2、根据定义可知,x左边的所有点都小于它,把c提上来不影响规则。

     

    第二种情况

     

    3、B<A<C,所以B<C,根据刚才的叙述,B可以提上去,c可以放在b右边,不影响规则

    4、同理

     

    第三种情况

     

    5、注意:是把黑色的提升上来,不是所谓的最右边的那个,因为当初向左拐了,他一定小。

    因为黑色是最大,比B以及B所有的孩子都大,所以让B当左孩子没问题

    而黑点小于A,也就小于c,所以可以让c当右孩子

    大概证明就这样。。

    下面我们用代码实现并通过注释理解

    上次链表之类的用的c,循环来写的。这次就c++函数递归吧,不同方式练习。

    定义

    struct node
    {
        int val;//数据
        node *lch,*rch;//左右孩子
    };

    插入

     node *insert(node *p,int x)
     {
         if(p==NULL)//直到空就创建节点
         {
             node *q=new node;
             q->val=x;
             q->lch=q->rch=NULL;
             return p;
         }
         if(x<p->val)p->lch=insert(p->lch,x);
         else p->lch=insert(p->rch,x);
         return p;//依次返回自己,让上一个函数执行。
     }

    查找

     bool find(node *p,int x)
     {
         if(p==NULL)return false;
         else if(x==p->val)return true;
         else if(x<p->val)return find(p->lch,x);
         else return find(p->rch,x);
     }

    删除

     node *remove(node *p,int x)
     {
          if(p==NULL)return NULL;
          else if(x<p->val)p->lch=remove(p->lch,x);
          else if(x>p->val)p->lch=remove(p->rch,x);
          //以下为找到了之后
          else if(p->lch==NULL)//情况1
          {
              node *q=p->rch;
              delete p;
              return q;
          }
          else if(p->lch->rch)//情况2
          {
              node *q=p->lch;
              q->rch=p->rch;
              delete p;
              return q;
          }
          else
          {
              node *q;
              for(q=p->lch;q->rch->rch!=NULL;q=q->rch);//找到最大节点的前一个
              node *r=q->rch;//最大节点
              q->rch=r->lch;//最大节点左孩子提到最大节点位置
              r->lch=p->lch;//调整黑点左孩子为B
              r->rch=p->rch;//调整黑点右孩子为c
              delete p;//删除
              return r;//返回给父
          }
          return p;
     }

     

    对数组排序可以说是编程基础中的基础,本文对八种排序方法做简要介绍并用python实现。

    代码中注释很全,适合复习和萌新学习。这是刚入学自己写的,可能难免比不上标准的写法,但是懒得改了。

    文末会放和排序相关的基本拓展总结链接。

    看不明白可以看群里视频

    注意排序实现的具体方式,不要用局部变量,否则占空间太多,和空间复杂度不符。

    好,我们开始。

    • 选择排序

    选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在待排序序列的起始位置,直到全部待排序的数据元素排完。时间复杂度O(N^2)

    for i in range(len(l)):#意义是第i个位置开始挑第i大(小)的元素
        for j in range(i,len(l)):#和其他待排序的元素比较
    	if l[j]<l[i]:#更大就交换
    	    l[j],l[i]=l[i],l[j]
    • 冒泡排序

    冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法

    它重复地走访过要排序的元素列,一次比较两个相邻的元素,如果他们的顺序(如从大到小、首字母从A到Z)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换(一般进行n次即可,第n次一定会把第n小的元素放到正确位置)。

    这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。时间复杂度O(N^2)

    for i in range(len(l)-1):#下标和i无关,代表的只是第i次排序,最多需要len(l)-1次排序即可
        for j in range(len(l)-1):#遍历每一个元素
    	if l[j]<l[j+1]:#本元素比下一个元素小,就交换
    		l[j],l[j+1]=l[j+1],l[j]

     分析一下其实每次排序都会多一个元素已经确定了位置,不需要再次遍历。

    所以j循环可以改成len(l)-i-1

    时间复杂度没变。

     

    • 插入排序

    有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。

    for i in range(1,len(l)):#意义是第i个元素开始插入i之前的序列(已经有序)
        for j in range(i,0,-1):#只要比它之前的元素小就交换
    	if l[j]<l[j-1]:
    	    l[j],l[j-1]=l[j-1],l[j]
    	else:
                break#直到比前一个元素大

     

    • 归并排序

    速度仅次于快速排序,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的数列

    试想:假设已经有两个有序数列,分别存放在两个数组s,r中,我们如何把他们有序的合并在一起?

    归并排序就是在重复这样的过程,首先单个元素合并为含有两个元素的数组(有序),然后这种数组再和同类数组合并为四元素数组,以此类推,直到整个数组合并完毕。

    def gg(l,ll):#合并函数
        a,b=0,0
        k=[]#用来合并的列表
        while a<len(l) and b<len(ll):#两边都非空
            if l[a]<ll[b]:
                k.append(l[a])
                a=a+1
            elif l[a]==ll[b]:a=a+1#实现去重
            else:
                k.append(ll[b])
                b=b+1
        k=k+l[a:]+ll[b:]#加上剩下的
        return k
    
    def kk(p):#分到只剩一个元素就开始合并
        if len(p)<=1:
            return p
        a=kk(p[0:len(p)//2])#不止一个元素就切片
        b=kk(p[len(p)//2:])
        return gg(a,b)#返回排好序的一部分
    l=list(map(int,input().split(" ")))
    print(kk(l))
    • 快速排序

    快速排序(Quicksort)是对冒泡排序的一种改进。

    快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列

    • 随机化快排

    快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下,每次划分将得到最坏的结果。比如1 2 3 4 5,每次取第一个元素,就退化为了O(N^2)。一种比较常见的优化方法是随机化算法,即随机选取一个元素作为主元。

    这种情况下虽然最坏情况仍然是O(n^2),但最坏情况不再依赖于输入数据,而是由于随机函数取值不佳。实际上,随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度

    进一步提升可以分割为三部分,即小于区,等于区,大于区,减小了递归规模,并克服了多元素相同的退化。

    def gg(a,b):
        global l
        if a>=b:#注意停止条件,我以前没加>卡了半小时
            return
        x,y=a,b
        import random#为了避免遇到基本有序序列退化,随机选点
        g=random.randint(a,b)
        l[g],l[y]=l[y],l[g]#交换选中元素和末尾元素
        while a<b:
            if l[a]>l[y]:#比目标元素大
                l[a],l[b-1]=l[b-1],l[a]#交换
                b=b-1#大于区扩大
                #注意:换过以后a不要加,因为新换过来的元素并没有判断过
            else:a=a+1#小于区扩大
        l[y],l[a]=l[a],l[y]#这时a=b
        #现在解释a和b:a的意义是小于区下一个元素
        #b是大于区的第一个元素
        gg(x,a-1)#左右分别递归
        gg(a+1,y)
    
    l=list(map(int,input().split(" ")))
    gg(0,len(l)-1)
    print(l)
    
    • 堆排序

    堆排序(HeapSort)是一树形选择排序。堆排序的特点是:在排序过程中,将R[l..n]看成是一棵完全二叉树顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系,在当前无序区中选择关键字最大(或最小)的记录。

    由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。

    堆排序是就地排序,辅助空间为O(1).

    它是不稳定的排序方法。

    主要思想:维持一个大根堆(根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大根堆,又称最大堆。注意:①堆中任一子树亦是堆。②以上讨论的堆实际上是二叉堆(Binary Heap),类似地可定义k叉堆。)

    第一步:通过调整原地建立大根堆

    第二步:每次交换堆顶和边界元素,并减枝,然后调整堆顶下沉到正确位置。

    def down(i,k):#在表l里的第i元素调整,k为边界
    
    #优先队列也是通过这种方式实现的
        global l
        while 2*i+2<k:#右孩子不越界
            lift,right=2*i+1,2*i+2
            m=max(l[i],l[lift],l[right])
            if m==l[i]:#不需要调
                break
            if m==l[lift]:#把最大的换上来
                l[i],l[lift]=l[lift],l[i]
                i=lift#目的节点下标更新
            else:#把最大的换上来
                l[i],l[right]=l[right],l[i]
                i=right#目的节点下标更新
        if 2*i+1<k:#判断左孩子
            if l[2*i+1]>l[i]:
                l[i],l[2*i+1]=l[2*i+1],l[i]
    
    def main():
        global l
        for j in range(1,len(l)+1):#调大根堆
            i=len(l)-j
            down(i,len(l))
        for i in range(len(l)-1,-1,-1):#排序
            l[i],l[0]=l[0],l[i]#最大和边界交换,剪枝
            down(0,i)
        print(l)
        
    l=list(map(int,input().split(" ")))
    main()
    
            
        
    
            
    
    • 桶排序

    桶排序不是基于比较的排序方法,只需对号入座。将相应的数字放进相应编号的桶即可。

    当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间o(n)

    对于海量有范围数据十分适合,比如全国高考成绩排序,公司年龄排序等等。

    l=list(map(int,input().split(" ")))
    n=max(l)-min(l)
    p=[0]*(n+1)#为了省空间
    for i in l:
        p[i-min(l)]=1#去重排序,做标记即可
    for i in range(n):
        if p[i]==1:#判断是否出现过
            print(i+min(l),end=" ")
    • 希尔排序

    希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

    通过缩小有序步长来实现。

     

    def shell(arr):
     n=len(arr)#初始化步长
     h=1
     while h<n/3:
      h=3*h+1
     while h>=1:#判断,退出后就有序了。
      for i in range(h,n):
       j=i
       while j>=h and arr[j]<arr[j-h]:#判断是否交换
        arr[j], arr[j-h] = arr[j-h], arr[j]
        j-=h
      h=h//3#逐渐缩小步长
     print arr

    稳定性及时间复杂度

    排序稳定性概念:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。

    时间复杂度:时间复杂度是同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。可以理解为和常数操作所成的一种关系(常数操作为O(1))

    空间复杂度类似。

    下面给出各类排序的对比图:

     

     

     

    • 基数排序

    因为桶排序是稳定的,基数排序就是很多次桶排序而已,按位进行桶排序即可。

    (个人认为桶排序名字不恰当,因为桶是先进后出,和稳定的算法正好反了,)

     

     

     

     

    总:

    比较排序和非比较排序

          常见的排序算法都是比较排序,非比较排序包括计数排序、桶排序和基数排序,非比较排序对数据有要求,因为数据本身包含了定位特征,所有才能不通过比较来确定元素的位置。

          比较排序的时间复杂度通常为O(n2)或者O(nlogn),比较排序的时间复杂度下界就是O(nlogn),而非比较排序的时间复杂度可以达到O(n),但是都需要额外的空间开销。

    • 若n较小(数据规模较小),插入排序或选择排序较好
    • 若数据初始状态基本有序(正序),插入、冒泡或随机快速排序为宜
    • 若n较大,则采用时间复杂度为O(nlogn)的排序方法:快速排序或堆排序
    • 快速排序是目前基于比较的排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;
    • 堆排序所需的辅助空间少于快速排序,并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。

     

     

     

     

     

     

     

     

     

    展开全文
  • 考试系统--成绩分析功能感想

    千次阅读 热门讨论 2014-03-23 17:48:01
    成绩分析功能最近分给我的一项功能,要求对于对于试卷上每道题的学生的正确率进行分析,从而得出那些题比较简单(学生得分率高),那些题比较难(学生得分率低了),这样老师下次卷子就可以参考这次的数据.   这个功能,...

             成绩分析功能最近分给我的一项功能,要求对于对于试卷上每道题的学生的正确率进行分析,从而得出那些题比较简单(学生得分率高),那些题比较难(学生得分率低了),这样老师下次出卷子就可以参考这次的数据.

             这个功能,我从18号开始,弄了5天左右,弄了一个能用,但是不算好的效果.运行起来的效果,是这个样子的.


             分到这个功能的时候,说是要用报表,我就想着用水晶报表.总听他们说,报表是非常有用,而且常用的功能,所以我就想试试.可是由于没有用过水晶报表,所以就想着先用简单的方法,把功能全部都实现了,再用水晶报表去替换.最后,用了别的东西实现了功能,却再也不想用水晶报表去替换,至少这两天不想干这个.

             开始的时候,想仿着禅道的报表弄成这个效果.看了图形,查了FusionCharts Trial,最后用了VS2012自带的Chart工具.

     

             Chart的使用就是先从工具箱从拖控件,然后在后台绑定数据源,写法和其他控件绑定datable基本一样.只不过你要为你的ChartX轴和Y轴赋值,他们具体代表什么.这和dropdownlist类似,你要设置TextValue分别是什么.Series1,你拖了Chart控件就知道是什么了,也可以写成Chart1.Series[0]这种样式.如果你添加了Series2的话,那么就会两种颜色的线在Chart表中.设置ChartType就可以选择用条形图还是线形图,还是其他什么.如这个就是饼形图了Chart1.Series["Series1"].ChartType= SeriesChartType.Pie;而且还可以设置3d样式,如这样Chart1.ChartAreas["ChartArea1"].Area3DStyle.Enable3D =true;

    Chart1.DataSource = Datatable1;
    Chart1.Series["Series1"].XValueMember = "题号";
    Chart1.Series["Series1"].YValueMembers = "得分率";
    Chart1.DataBind();

             本来打算左边和禅道一样用复选框的.但是这样有个问题,因为不同的考试,题型(就是听短文,多选题,选择题,填空题这种东西)是不一样的,我要根据不同的考试来查出他们的题型,然后显示一系列的复选框,或者复选框列表.

             这里有两种思路,一种就是,我根据所有的题型,在前台界面写死,每个题型都弄一个 复选框,只是VisibleFalse,只有选择的考试中存在的题型才会VisibleTrue,这样的话东西就未免太多(因为题型有20多中种).

             而且当我勾选不同的题型进行题型分析的时候,就要为每种题型都写一条判断,是否选中,选中如何如何.而且我的数据是在gridview(开始的时候想着用它的排序功能,后来用了图表之后发现这个功能可以不要了)中显示的.如果我一次性勾选所有的复选框,那么就要为所有题型都用一个GridView,那么你就会看到NGridView.(而且用的时候我忘了开启GridViewAllowPaging,所以设置PageSize完全不管用,可想而知数据多的时候的效果了)

               所以,上一种思路被我淘汰了.

              第二种是,我在后台动态生成复选框,有多少题型,就生成多少复选框.但是我好死不死的.在前台界面上,添加了一个按钮,就是上上图中的分析按钮.运行的效果是,界面加载的时候,确实根据不同的题型生成了不同的复选框.但是当我点击分析按钮的时候,我发现他们被刷没了.我就想这个还不如上面那么呢,所以放弃了.后来想想,其实button按钮我也可以试着在后台添加, 这样说不定就不会被刷新掉了. 但是用复选框还是存在,生成多个GridView(还有Chart)的问题,而且还得给这些个GridView都添加属性,添加事件,工作量不一定小.

            最后,果断放弃了复选框,使用了单选框,这样我就只要一个GridView和一个Chart.              

            由于不同的题型在数据库中的表都是不一样的,根据界面获取到的数据,拼凑SQL查询语句,并且还要统计得分率,就是从答题记录中获取该题的每个小题的所有学生的分数,以及从题库表中获取该题每小题的分值,和考该小题的人数的乘积,他们相除的结果.SQL语句中用这样一句实现,cast(SUM(学生该小题的总成绩)*100/SUM(该小题的总成绩)as numeric(9,2)) as 得分率.如果真要加上"%"的话,在最后加上"%"就可以了,cast(SUM(学生该小题的总成绩)*100/SUM(该小题的总成绩) as numeric(9,2)) +"%",但是类型就是varchar,就别想变成数值了.

            最后数据都显示在GridView中了,但是有的数据特别的长,如果都显示出来,GridView hold不住,就想着截取一部分(在数据库中查询的时候也可以直接用substring截取,但是这样就没法tooTip显示所有的内容了),然后鼠标移上去的时候显示全部内容.所以在gridview_DataBound事件中添加这样的代码.凡是长度超过43的都在40上截取,后面的用...代替.Cells[1]代表的是题干列.

      for (int i = 0; i < GridView1.Rows.Count; i++)
      {
         if (GridView1.Rows[i].Cells[1].Text.Length > 43)
         {
            GridView1.Rows[i].Cells[1].ToolTip = GridView1.Rows[i].Cells[1].Text;
            GridView1.Rows[i].Cells[1].Text = GridView1.Rows[i].Cells[1].Text.Substring(0, 40) + "...";
          }
     
      }

             最后就这样,花了5天的时间修修改改,弄出来这样的效果,没有用水晶报表,没有弄下载导出的功能,没有设置页面跳转的功能,页面样式也基本没有调,还需要进一步完善.前两天写完了所有的SQL语句,第三天周四,休息了,第四天用了GridViewChart,最终决定不用复选框用单选框.把三层补完,把所有的SQL语句进行修改后写到各个类中,以及设置GridViewDatabound.第五天,忘了还有一个统计及格人数和及格率这种东西,所以添加了一个页面加上这个功能.并且设置好了样式,只是还是不大好看.

             感觉自己的效率不是很高,一段代码本来自己慢慢看就能发现错误,或者多想想就能不出问题,但是我非要不停的运行,然后运行一次,发现一个错误,然后改一次,然后再运行,发现还有错误,再继续改,这样很浪费时间.经常一个下午过去了,只是解决了一点点问题,大部分时间都是不停地运行,改错,运行,改错.

              以后一定多想,多看,少直接运行.

             

    展开全文
  • 关于考试类型和成绩分析的几个问题一、关于考试类型及其命题原则对事物更深入的认识所必经的一个过程就是分类,只有对事物进行全方位多层次地进行分类,才能较全面地把握其特征,这是我学习生物学所领悟的一个道理。...
      

    关于考试类型和成绩分析的几个问题

    一、关于考试类型及其命题原则

    对事物更深入的认识所必经的一个过程就是分类,只有对事物进行全方位多层次地进行分类,才能较全面地把握其特征,这是我学习生物学所领悟的一个道理。通过对考试类型的学习,我认识到考试成绩的用途不同,必然要求命题具有不同的、甚至有些是相反的试题特点或命题原则、评价标准:

    1、选拔考试:如升学考试。力求试题的难度有一定的梯度,以保证略高于选拔数额的考生成绩能最大程度地“等距离散”,即这部分学生的成绩宜呈水平线分布而不是正态分布,至于其余考生的成绩则不必考虑。

    2、水平考试:如毕业考试。力求试题能严格表达课程标准的要求(如,对课标要求“掌握”内容的考核,拟题必须具有分析、综合、创新等“灵活运用”的因素),该类考试不注重试题有怎样的难度也不注重成绩分布(正态、非正态等)的类型情况。

    3、诊断考试:如开学初新生考试。……。若期望对学生的习得情况进行程度甄别,则应力求试题的难度有梯度性,以使全体考生的成绩呈正态分布。

    我们现行的考试很少是典型类型的考试,如小学六年级和初中三年级学年末考试就兼有毕业考试和升学考试两种性质,甚至还有很多同志期望其成绩能够呈正态分布。这是可以理解也是非常自然和普遍的,但正是由此便促成了命题人命题和考试后试题质量评价的尴尬,如:某学科若有20%的学生满分,这在水平考试中是英雄辈出、校校都有好学生令人欣喜若狂,而在选拔考试中则是群龙无首、前三名的奖状都发不出去让人一筹莫展。

    对于典型类型的考试,我们的命题也很难尽如人意,甚至画虎类犬,那么,对于上述复合的考试类型,又将期望我们的命题会有怎样的满意度呢?对于命题质量的评价,各有自论难缄其口、未有公论任尔评说,绕开命题的成败仅就试题的考查点来讨论成绩和答卷所反映的问题便是我们时下所做的“分析报告”。

    二、为什么引入标准分的概念和方法

    卷面得分及平均分、及格率、优秀率等统计指标(我们称之为原始分)只能反映学生对试卷的完成情况(即学生对考试期望值的达成情况),却不能表达该成绩在团体中的排位。“名次”虽然可以反映具体排位,却不能反映不同名次间差异的程度,例如成绩第一和第二之间、第二与第三之间虽都是高一个名次,但其分数的差异却是不同的。总之,仅仅根据某学校的原始分及其在全县各校中的名次,仍然不足以对成绩的优劣高下做出判定,更不能对不同的成绩统计指标、不同的考试科目、不同时期的考试进行合乎情理的成绩比较。

    标准分可以将各种原始分转换为平均值都是500,标准差都是100的正整数,做到了“统一度量”,从而使基于同一个总体的诸样本的各种成绩之间都具有了可比性。虽然标准分反映的成绩排位与原始分的名次是一致的,但不同排位之间的量值差是不同的(与成绩的离散程度关系甚大),也正因其量值的大小有所不同,标准分所反映的排序能够反映不同排位之间的差异程度。

    综上所述,引入标准分的概念和方法是必须的,而无论我们是否习惯和熟悉。

    三、关于考生习得程度档次的划分

    划分考生习得程度档次的依据可以是“成绩分数值”也可以是“考生数量比”,以下是对两者孰优的讨论。

    依据“成绩分数值”:凡大于卷面60%的分数为及格、大于卷面90%的分数为优秀,这是我们一直使用的。

    依据“考生数量比”:以全县所有的考生为整体,设定成绩排名位列“全县××%”的学生为某类,某学生究竟属于哪一类档次,必须考查他在“全县所有考生”中的排位情况,校内排名第一、卷面得分91都不足以表明该学生一定就是“优等生”。

    由于试题的较难(或较易),不同学校的“及格、优秀”人数会有不同程度的改观,其程度取决于该学校中接近“及格、优秀”成绩的学生数的大小。类似地,试题难度也影响着学校“前中后末”类的学生数量,但其影响程度却有很大的消减,例如:由于试题难度不同,某校和全县的优秀率可能是0%或100%及两者之间的某个值,而无论试题难度如何,全县“前中后末”类学生的比率都一定始终是某个既定值。总之,无论采用上述怎样的方法对成绩进行分析,在依据分析结果认定其教学质量优劣时,都无法消除试题难度所产生的干扰,只是我们“有否”在意、“是否有必要”注重这样的影响而已。

    在水平性考试中,试题难度不悖于课程标准,“及格、优秀”与否直接反映了学生对教学要求(教学期望)的达成情况,这是极有意义而必须坚持的;但在选拔考试中,试题难度并不严格遵循课程标准,如此,“及格、优秀”就不再具有“反映教学期望达成度”的意义;而另一方面,引入“及格率、优秀率”的概念来说明问题往往不够明晰(并非不足以说明问题,而是可能性过多、确定性不强),相比较而言,在非水平考试中,依据“考生数量比”来划分考生习得程度的档次似乎更简捷。我们认为,在小学六年级、初中三年级学年末考试中应使用“成绩分数值”划分考生习得程度的档次,就“优等生率、非差等生率”等指标考量各学校的教学质量。

    四、学额对“率”计算的影响

    从理论上说,各校间学额差异过大并不是“率”计算产生明显差异的原因,但学额过小必将导致“率”的计算不合理,火箭发射一向都说第某次又获成功或从无失败,却绝不言成功率百分之百,就是缘于这个道理。优秀率为0%或及格率为100%的情况,在200名学生的学校是“不可能”的而在2名学生的学校却是“有可能”的,我们不否认“大”学校与“小”学校在“率”的比较上是不适宜的,但我们需要知道有什么办法可以实现较为合理的比较。不比较是不可以的,但时下比较的结果是“大”学校能“真实再现”就“休想便宜”,“小”学校虽然“祸福参半”却常常“只赚不赔”,那么,“多大学额”的学校应该算作是“小”学校呢?这些问题一直困扰着我们,百思不得其解。

     

    我们对于标准分问题的研究目前还很不够,我们的工作就犹如一个未足月的早产儿,虽然还有着诸多的不如意和麻烦事,但好歹也是历经长期的辛苦孕育才形成的,也算是个宝贝,我们期望着她的成长,只是不知道她能否长成

     
    展开全文
  • CKA考试经验:报考和考纲

    万次阅读 2019-11-08 08:57:40
    所有命令都验证过,有更的方式,欢迎留言~~~ CKA习题和真题汇总 CKA考试经验:报考和考纲 CKA :2019年12月英文原题和分值 CKA考试习题:K8S基础概念--API 对象 CKA考试习题:调度管理-nodeAffinity...
  • 电子技术专业基础与实务(中级)考试介绍与复习方法 (2012-04-16 13:37:13) 标签: 职称 电子 考试 复习 教育 分类: 学习与考试 昨天下午在天坛东门的北京第五十中学参加了2012年...
  • 之前女票忘记了六级的准证号,成绩出来的时候特别着急。。。毕竟了那么多次 我也特别着急,刚好在支付宝和微信小程序里都有查询六级成绩的程序,但是特别坑爹的是支付宝的四六级查询要不抽风,还需要根据准证...
  • 考试,一种严格的水平鉴定方法

    千次阅读 2017-06-14 23:49:05
    那是一个寒冷的冬天下午,我来到提前一个月就在师范大学门口的城中村里订的一个干净单人间,又另加10块钱从房东那租了一个很大的小太阳,就准备找邓局去学校食堂吃饭,那时邓菊已经先我一年上成了学长。...
  • emmmmmmm 总算是了个满分,不用以后再交PAT考场一日游入场费了T ^T 第一次在去年秋天,被第一题...注意,考试的运行时的黑框,是不能使用Crtl+V进行粘贴的,但这不代表考试不能进行复制粘贴,PAT考试系统里的代码...
  • 虽然是在第二次ISPM,才通过。但是,本文,主要面向希望通过较少复习时间,就通过考试的考生。因此,**本文不强调获取完整、扎实的ISPM知识点,而是强调考试技巧。**这是一种投机取巧的方法,不值得广泛推广。参加...
  • 本人参加的是2017年上半年信息系统项目管理师考试,今天看到2017上半年考试成绩合格分数为45,也算是侥幸通过,在这里写一写自己是如何备考的,供各位友参考一下。 这里说的50天是指白天上班以业余时间备考所需...
  • 在线考试系统文献综述

    热门讨论 2010-05-28 14:57:16
    所以现在较考试方法为网络考试,试题内容放在服务器上,考生通过姓名、准证号码和口令进行登录,考试答案也存放在服务器中,这样考试的公平性、答案的安全性可以得到有效的保证。因此,采用网络考试方式将是...
  • CKA考试经验总结

    万次阅读 多人点赞 2019-01-11 14:44:58
    购买了CKA考试,完成后CNFC会给Exam Preparation Checklist 1、有效期一年。在一年内需要定好考试的时间。 2、提前15分钟进入考试系统, 提前进入考试系统后并不是立马开始考试,而是预留给考官时间考察你的考试...
  • Django框架实现在线考试系统

    万次阅读 多人点赞 2019-06-21 19:30:00
    遇见Django框架之简单版在线考试系统1.Django的简介2.项目的设计思路3.搭建你的开发环境4.分模块设计5.总结 1.Django的简介 Django是一个基于MVC构造的框架。但是在Django中,控制器接受用户输入的部分由框架自行...
  • PAT 计算机程序设计能力考试

    千次阅读 2016-08-06 08:43:36
     计算机程序设计能力考试(Programming Ability Test,简称PAT)旨在通过统一组织的在线考试及自动评测方法客观地评判考生的算法设计与程序设计实现能力,科学的评价计算机程序设计人才,为企业选拔人才提供参考...
  • 剑指Offer——银行考试

    万次阅读 2016-08-31 09:09:09
    剑指Offer——银行考试网申简历一、 银行网申简历主要看哪些方面?1、职业形象(30%),基本体现为证件照;2、学校+成绩+校内表现(40%),体现为证书,成绩排名以及任职经历等;3、校外实践(20%),主要体现在工作...
  • NPDP考试相关事宜

    千次阅读 2018-07-31 10:19:54
    NPDP(产品经理国际资格认证)是国际公认的唯一的新产品开发专业认证,NPDP认证的核心价值在于整合产品开发管理的...NPDP考试报名一般在考前的2个月进行,维持一个月左右的时间,也就是2018年5月26日的考试报名会在...
  • OCP认证考试心得

    万次阅读 多人点赞 2015-07-03 15:11:40
    本人OCP认证考试亲身经历,分享给大家,仅供参考。 祝好运
  • RHCE考试心得

    千次阅读 多人点赞 2019-03-21 23:32:42
    在博主还是混吃等死的大学狗的时候天真的以为只要了个CE就算是行业里中等水平。等完了再回来看觉得这真只是一个入门,就好比是数学里的九九乘法表一样全是基础的...不管过没过,成绩一般第二天就会发邮件告诉你...
  • oscp认证考试指南

    万次阅读 多人点赞 2019-02-18 22:11:44
    目录简介第一节: 考试要求文档要求Exploit 代码考试证据控制面板提交截图要求考试限制Metasploit 限制第二节:考试信息考试网络连接考试控制板靶机快照恢复考试中proof文件分值分配取消得分建议使用的报告模板奖励...
  • Python全国二级等级考试(2019)

    万次阅读 多人点赞 2019-03-19 08:40:24
    最后送给报名了3月份python计算机二级同学一份福利:**2019年3月二级Python考试模拟软件**,同时也预祝大家都能顺利通过,快快转发分享给你的同学们一起刷一波题吧~
  • RHCE考试经验

    千次阅读 2016-03-30 09:48:54
    http://blog.csdn.net/chinalinuxzend/archive/2008/10/16/3086761.aspx特别推荐:...RHCE在每科考试之前都必须签署不得于后泄题的同意书,违者会被取消 RHCE资格,这造成了RHCE的考古题取得不易,及RHCE的重率高
  • 基于Web的在线考试系统

    万次阅读 热门讨论 2015-07-27 15:02:39
    基于Web的在线考试系统 二十一世纪的今天,随着社会的迅猛发展,科技也越来越发达,互联网已经遍布于家家户户,深入到人们的日常生活中。网络技术给我们当今的教育方式的带来了一次历史性的变革,在线考试就是...
  • JSP在线考试系统

    千次阅读 2019-11-28 12:10:20
    JSP在线考试系统 第一章 绪论 1.1.课题的背景及研究意义 在我们教育快速发展的今天,比较传统的纸质考试已经过时了,因为这不仅需要大量的人力物力去打印试卷、还要去批改试卷,要花费大量的时间。更关键的是,在...
  • 所以现在较考试方法为网络考试,试题内容放在服务器上,考生通过姓名、准证号码和口令进行登录,考试答案也存放在服务器中,这样考试的公平性、答案的安全性可以得到有效的保证。因此,采用网络考试方式将是...
  • 和我徒弟一样发文纪念下,信息系统项目管理师考试45分,我报名,开始复习,具体时间,自己去某网站看,上面写着倒计时70天,也不知道对不对。把我 一次通过信息系统项目管理师考试过程进行一个简单回顾, 供各位...
  • 基于ASP.NET在线考试系统设计

    热门讨论 2011-03-14 16:07:15
    在线考试系统的主要特点是一方面可以动态地管理各种考试系统信息,只要准备足够大的题库,就可以按照要求自动生成各种试卷;另一方面,考试时间灵活,用户可以在规定时间段内的任意时间参加考试;另外计算机化的考试的...
  • Oracle认证考试介绍

    万次阅读 2016-04-12 11:41:53
    Oracle认证考试介绍 top↑  Oracle认证考试由Oracle公司授权国际考试认证中心对考生进行资格认证的。考生按考试标准要求参加几门课程的考试(一般为三至五门),在通过全部考试后,将获得OCP的专家认证。Oracle认证...
  • 基于J2EE的在线考试系统构建探讨

    热门讨论 2009-07-17 23:34:19
    由于涉及到需要调用word程序进行word试题的考试,因此需要用到调用java外部程序的功能,java.lang.Runtime类提供了exce()方法来完成对外部可执行程序的调用。具体代码见下: String path="C:/word.doc"; try ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 29,520
精华内容 11,808
关键字:

如何考试考出好成绩方法