精华内容
下载资源
问答
  • 下列不属于算法结构的是
    2021-03-18 12:06:24
    一、选择题
    1. 在计算机中,算法是指______。
      A. 查询方法 B. 加工方法 C. 解题方案的准确而完整的描述 D. 排序方法

    2.下列叙述中正确的是
    A)算法的效率只与问题的规模有关,而与数据的存储结构无关
    B)算法的时间复杂度是指执行算法所需要的计算工作量
    C)数据的逻辑结构与存储结构是一一对应的
    D)算法的时间复杂度与空间复杂度一定相关

    3.算法的有穷性是指
    A)算法程序的运行时间是有限的 B)算法程序所处理的数据量是有限的
    C)算法程序的长度是有限的 D)算法只能被有限的用户使用

    4.算法的时问复杂度是指
      A)算法的执行时间   B)算法所处理的数据量
      C)算法程序中的语句或指令条数 D)算法在执行过程中所需要的基本运算次数

    5.算法的空间复杂度是指
    A)算法在执行过程中所需要的计算机存储空间 B)算法所处理的数据量
    C)算法程序中的语句或指令条数 D)算法在执行过程中所需要的临时工作单元数

    1. 下列叙述中正确的是
        A)一个算法的空间复杂度大,则其时间复杂度也必定大
        B)一个算法的空间复杂度大,则其时间复杂度必定小
        C)一个算法的时间复杂度大,则其空间复杂度必定小
      D)上述三种说法都不对

    7.:数据的存储结构是指
     A) 存储在外存中的数据 B) 数据所占的存储空间量
     C) 数据在计算机中的顺序存储方式 D) 数据的逻辑结构在计算机中的表示

    1. 下列数据结构中,属于非线性结构的是
      A)循环队列 B) 带链队列
      C) 二叉树 D)带链栈

    9.下列叙述中正确的是( )。
    A)顺序存储结构的存储一定是连续的,链式存储结构的存储空间不一定是连续的
    B)顺序存储结构只针对线性结构,链式存储结构只针对非线性结构
    C)顺序存储结构能存储有序表,链式存储结构不能存储有序表
    D)链式存储结构比顺序存储结构节省存储空间

    10算法执行过程中所需要的存储空间称为算法的
    A)时间复杂度B)计算工作量C)空间复杂度D)工作空间

    11.下列叙述中正确的是
    A)一个逻辑数据结构只能有一种存储结构
    B)数据的逻辑结构属于线性结构,存储结构属于非线性结构
    C)一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理的效率
    D)一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理的效率

    12.下列关于算法的时间复杂度陈述正确的是
    A)算法的时间复杂度是指执行算法程序所需要的时间
    B)算法的时间复杂度是指算法程序的长度
    C)算法的时间复杂度是指算法执行过程中所需要的基本运算次数
    D)算法的时间复杂度是指算法程序中的指令条数

    13.下列叙述中正确的是( )
      A)算法的效率只与问题的规模有关,而与数据的存储结构无关
      B)算法的时间复杂度是指执行算法所需要的计算工作量
      C)数据的逻辑结构与存储结构是一一对应的
    D)算法的时间复杂度与空间复杂度一定相关

    1. 下列叙述中正确的是
      A)一个算法的空间复杂度大,则其时间复杂度也必定大
      B)一个算法的空间复杂度大,则期时间复杂度必定小
      C)一个算法的时间复杂度大,则其空间复杂度必定小
      D)上述三种说法都不对

    2. 数据的存储结构是指______。
      A)存储在外存中的数据 B)数据所占的存储空间量
      C)数据在计算机中的顺序存储方式 D)数据的逻辑结构在计算机中的表示

    3. 下列叙述中,错误的是
      A)数据的存储结构与数据处理的效率密切相关
      B)数据的存储结构与数据处理的效率无关
      C)数据的存储结构在计算机中所占的空间不一定是连续的
      D)一种数据的逻辑结构可以有多种存储结构

    4. 算法的空间复杂度是指
      A)算法程序的长度 B)算法程序中的指令条数
      C)执行算法程序所占的存储空间 D)算法执行过程中所需要的存储空间

    18.数据结构中,与所使用的计算机无关的是数据的
    A)存储结构 B)物理结构 C)逻辑结构 D)物理和存储结构

    19.算法分析的目的是______。
    A)找出数据结构的合理性 B)找出算法中输入和输出之间的关系
    C)分析算法的易懂性和可靠性 D)分析算法的效率以求改进

    1. 在下列选项中,哪个不是一个算法一般应该具有的基本特征______。
      A、确定性 B、可行性 C、无穷性 D、拥有足够的情报

    2. 在计算机中,算法是指______。
      A、查询方法 B、加工方法 C、解题方案的准确而完整的描述 D、排序方法

    3. 在单链表中,增加头结点的目的是______。
      A、方便运算的实现 B、使单链表至少有一个结点
      C、标识表结点中首结点的位置 D、说明单链表是线性表的链式存储实现

    23.线性表若采用链式存储结构时,要求内存中可用存储单元的地址
    A)必须是连续的 B)部分地址必须是连续的
    C)一定是不连续的 D)连续不连续都可以

    24.链表不具有的特点是
    A)不必事先估计存储空间 B)可随机访问任一元素
    C)插入删除不需要移动元素 D)所需空间与线性表长度成正比

    25.循环链表的主要优点是
    A)不再需要头指针了 B)从表中任一结点出发都能访问到整个链表
    C)在进行插入、删除运算时,能更好的保证链表不断开
    D)已知某个结点的位置后,能够容易的找到它的直接前件

    26.下列叙述中正确的是
    A)线性表是线性结构 B)栈与队列是非线性结构
    C)线性链表是非线性结构 D)二叉树是线性结构

    27.在单链表中,增加头结点的目的是
    A)方便运算的实现 B)使单链表至少有一个结点
    C)标识表结点中首结点的位置 D)说明单链表是线性表的链式存储实现

    28.用链表表示线性表的优点是
    A)便于随机存取 B)花费的存储空间较顺序存储少
    C)便于插入和删除操作 D)数据元素的物理顺序与逻辑顺序相同

    29.用链表表示线性表的优点是______。
    A)便于插入和删除操作 B)数据元素的物理顺序与逻辑顺序相同
    C)花费的存储空间较顺序存储少 D)便于随机存取

    答案:
    C B A D A
    D D C A C
    D C B D D
    B C C D C
    C A D B B
    A A C A

    更多相关内容
  • 第5章_算法与数据结构.ppt
  • 从今天开始,我将正式开启一个新的打卡专题——【数据结构·水滴计划】,没错!这是今年上半年的一整个系列计划!本专题目的是通过百天刷题计划,通过题目和知识点串联的方式,刷够1000道题!完成对数据结构相关知识...

    🌕写在前面


    Hello🤗大家好啊,我是kikokingzz,名字太长不好记,大家可以叫我kiko哦~

    从今天开始,我将正式开启一个新的打卡专题——【数据结构·水滴计划】,没错!这是今年上半年的一整个系列计划!本专题目的是通过百天刷题计划,通过题目和知识点串联的方式刷够1000道题完成对数据结构相关知识的全方位复习和巩固;同时还配有专门的笔记总结和文档教程哦!想要搞定,搞透数据结构的同学

    🎉🎉欢迎订阅本专栏🎉🎉

    🍊博客主页:kikoking的江湖背景🍊


    🌟🌟往期必看🌟🌟

    🔥【水滴计划】第一话·数据结构入门竟如此简单?🔥

    目录

    🌕写在前面

    🍺知识点2:算法及其评价

    🥝2.1 算法的基本概念

    🍊1.什么是算法?

    🍊2.数据结构与算法有什么关系?

    🍊3.算法具有什么特性呢?

    🍊4.怎样算一个好的算法?

    🍊5.什么是算法的效率?

    🥝2.2 算法的时间复杂度

    🍊1.什么是时间复杂度?

    🍊2.大O的渐进表示法

    🍊3.时间复杂度有哪3种情况?

    🍊4.计算复杂度的两条规则

    📜实战案例

    🥝2.3 算法的空间复杂度

    🍊1.什么是空间复杂度?

    📝LeetCode之消失的数字

    📝LeetCode之旋转数组

    📜水滴石穿

    🌕写在最后

    热爱所热爱的, 学习伴随终生,kikokingzz与你同在!❥(^_-)

    🍺知识点2:算法及其评价

    🥝2.1 算法的基本概念


    🍊1.什么是算法?

    算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每条指令表示一个或多个操作。


    🍊2.数据结构与算法有什么关系?

    程序 = 数据结构 + 算法

    • 数据结构:如何用数据正确地描述现实世界的问题(逻辑结构),并存入计算机(存储结构)。
    • 算法:如何高效地处理上述这些数据,以解决实际问题。

    可见数据结构是将现实问题转化为电脑可以处理的数据,而算法则是求解问题的步骤;因此针对同一数据结构,求解问题的步骤方法可以不同,因此使用的算法也可以不同。


    🍊3.算法具有什么特性呢?

    (1)有穷性:一个算法必须总在执行有穷步后结束,且每一步都可在有穷时间内完成。

    • 注:算法必须是有穷的,而程序可以是无穷的,如手机上的CSDN是程序,而不是算法。

    (2)确定性:算法中每条指令必须有确切的含义,对于相同的输入只能得到相同的输出。

    (3)可行性:算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。

    (4)输入:一个算法有零个或多个输入,这些输入取自于某个特定的对象的集合。

    (5)输出:一个算法有一个或多个输出,这些输出是与输入有着某种特定关系的量。


    🍊4.怎样算一个好的算法?

    (1)正确性:算法能够正确地解决求解问题。

    (2)可读性:算法应具有良好的可读性,以帮助人们理解。

    (3)健壮性:输入非法数据时,算法能适当地做出反应或进行处理,而不会产生莫名其名的输出结果。

    (4)高效率与低存储需求:时间复杂度低,空间复杂度低。


    🍊5.什么是算法的效率?

    江湖中,传闻,算法效率有时空之分,具体来说便是时间效率与空间效率之分:

    • 时间效率被称为时间复杂度——衡量一个算法的运行速度
    • 空间效率被称为空间复杂度——衡量一个算法所需的额外空间

    在计算机发展早期,计算机存储容量很小,所以很在意空间复杂度;但是时光流逝,如今计算机的江湖之中,存储容量已到达极之巅峰,我们已无需特别关注算法复杂度了。


    📜007.题目难度 ⭐️

    007.一个算法应该是( )。
    A.程序
    B.问题求解步骤的描述
    C.要满足五个基本特性
    D.A和C

    🍊详细题解:

    A. 程序是一组计算机能识别和执行的指令,运行于电子计算机上,其不一定满足有穷性,如死循环、操作系统等。

    C. 是算法的特性而不是它的基本定义。

    算法:对特定问题求解步骤的一种描述,它是指令的有限序列,其中每条指令表示一个或多个操作;算法代表对问题求解步骤的描述,而程序则是算法在计算机上的实现。

    ✅正确答案:B 

     ✨✨✨我是分割线✨✨✨

    🥝2.2 算法的时间复杂度


    🍊1.什么是时间复杂度?

    算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。一个算法所花费的时间与其中语句的执行次数成正比,算法中的基本操作的执行次数,为算法的时间复杂度。

    Q1:可以使用“算法先运行,事后统计运行时间”的方法来估算时间开销吗?

    A1:使用如此方法是不客观的,主要有以下几个原因:

    • 机器性能越强,开销越少;如:超级计算机 vs 单片机。
    • 编程语言越高级,执行效率越低;如:Java写的程序要比用C写的效率低一些。
    • 和编译程序产生的机器指令质量有关。
    • 有些算法是不能事后统计的,如:导弹精准控制算法

    🍊2.大O的渐进表示法

    实际中我们计算时间复杂度只需要计算大概执行次数,那么我们使用大O的渐进表示法。

    大O符号:用于描述函数渐进式行为的数学符号

    通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项,简洁明了的表示出了执行次数。


    🍊3.时间复杂度有哪3种情况?

    最坏情况:任意输入规模的最大运行次数(上界)。

    平均情况:任意输入规模的期望运行次数。

    最好情况:任意输入规模的最小运行次数(下界) 。


    🍊4.计算复杂度的两条规则

    (1)加法规则:多项相加,只保留最高阶的项,且系数变为1。

    • T(n,m) = T1(n) + T2(n) = O [ max ( f(n), g(m) ) ]

    (2)乘法规则:多项相乘,都保留。

    • T(n,m) = T1(n) * T2(m) = O [ f(n) * g(m) ]

     记忆方式:常 < 对 < 幂< 指 < 阶


    📜008.题目难度 ⭐️⭐️

    008.某算法的时间复杂度为O(n^2)表明该算法的( )。
    A.问题规模是(n^2)
    B.执行时间等于(n^2)
    C.执行时间与(n^2)成正比
    D.问题规模与(n^2)成正比

    🍊详细题解:

    算法时间复杂度:O[ F(N) 意味着算法在任何情况下,规模为n的前提下,所花费的时间小于等于K*F(N),其中K是与N无关的常数。

    A/D. 在评价一个算法的复杂度时,已经默认问题规模为n。

    B. 执行时间不是等于(n^2),时间复杂度是该算法的一个上界(即时该算法的最坏情况),应当是小于等于。

    C. 算法时间复杂度本身就是一个数量级问题,表示该算法的执行时间小于等于K*(n^2),即与(n^2)成正比。

    ✅正确答案:C

     ✨✨✨我是分割线✨✨✨ 

    📜实战案例


    📜案例1——复杂度相加运算

    该例中有两个for循环,循环的上限分别为M+1次和N+1次(+1是因为跳出循环时还计算了一次),由大O的渐进表示法可以计算为:O(M+N+2) 近似为O(M+N),本题没有其他条件,不知道M和N的数量级大小,因此O(M+N)可以作为最终答案。

    • 当 M>>N时:时间复杂度为O(M)
    • 当 N>>M时:时间复杂度为O(N)


    📜案例2——用1代替所有常数次

    该案例中有一个for循环,循环的上限取决于条件判断的常数大小,此处是100,说明最多进行101次循环;如果这里的100改为100000000,也同样是进行常数次循环。因此依照大O的渐进表示法,用1替代所有常数,则其时间复杂度为O(1)

    相对的O(1)并不是代表只执行1次,而是代表执行常数次,可以是100次、1000次,也可以是1000万次,不管次数多大,都是常数次!


    📜案例3——strchr采用最坏时间复杂度

    strchr函数功能为在一个串中查找给定字符的第一个匹配之处。函数原型为:

    char *strchr(const char *str, int c);
    

    即在参数 str 所指向的字符串中搜索第一次出现字符 c(一个无符号字符)的位置。


    📜案例4——冒泡排序的时间复杂度

    最好情况:所有数字已经按序排列,自身有序排列,只需要冒泡排序一遍,由于没有发生交换,因此exchange值不发生改变,仍然为0,最后跳出循环,因此一共就执行了(N-1)次交换,所以其时间复杂度为O(N)。

    最坏情况:所有数字倒序排列,每一轮都需要冒泡排序,第一遍冒泡排序(N-1)次,将最大的数字安排到最后一位,然后继续从头开始进行冒泡排序,此时只需要交换(N-2)次,将次大的数安排在倒数第二位,按此顺序一直计算到最后交换1次,此时所有数字排序完成,总共排序了 [(N-1)+(N-2)+·····+ 2 + 1 ] 次,最终计算的时间复杂度为O(N^{2})


    📜案例5——二分查找的时间复杂度

    二分查找法这里假设数组元素呈升序排列,将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止;如 果x<a[n/2],则我们只要在数组a的左半部继续搜索x;如果x>a[n/2],则我们只要在数组a的右 半部继续搜索x。

    最好情况:直接1次就找到了,常数次找到,因此时间复杂度为O(1)。

    最坏情况:当找不到该数时,需要不断进行折半,一直折半到最后 begin==end 时,退出循环,此时一共执行了 \ logN次(具体计算步骤见下图)。

    注:时间复杂度中,习惯将log2(N) 简写为 logN


    📜案例6——递归阶乘的时间复杂度

    (1)单次递归函数调用为O(1)时,就看它递归的次数:

    本题在疯狂进行递归,每一次递归中包含了常数次的运算:1次逻辑判断运算和乘法运算,但从时间复杂度角度来看可以近似忽略为O(1)次;而真正占据时间复杂度的应当是其向下递归的次数,其递归次数取决于N,是幂函数,因此其时间复杂度为O(N)。

    (2)单次递归函数调用不为O(1)时,就看他递归调用中次数的累加:

    long long Fac(size_t N)
    {
    	if (0 == N)
    		return 1;
    	for (size_t i = 0; i < N; ++i)
    	{
    		printf("%d", i);
    	}
    	printf("\n");
    	return Fac(N - 1) * N;
    }

    对于上面这种变式情况,每次递归调用不是O(1),每次递归调用中的运算次数是变化的,第一次递归时,函数内部进行N次循环;递归到第二次时,函数内部进行N-1次循环;···;递归到第N-1次时,函数内部循环2次;通过计算我们可以得出:


    📜009.题目难度 ⭐️

    009.【2012统考真题】求整数n (n≥0)的阶乘的算法如下,其时间复杂度是( )。
        int fact(int n) {
            if(n<=1) return 1;
            return n*fact (n-1) ;
        }
    
    A.O(logn)        B.O(n)       C.O(nlogn)        D.O(n^2)
    

    🍊详细题解:

    本题就属于上面第(1)种情况,单次递归函数调用为O(1),其只包含了一次乘法运算,因此其时间复杂度就看它向下递归调用的次数,该例有n次递归,因此其时间复杂度为O(n)。

    ✅正确答案:B


    📜案例7——斐波那契数列的时间复杂度

    斐波那契数列的递归其实像是一个N-1层金字塔(当然是有残缺的金字塔),但我们计算复杂度时候真正关心的是数量级问题,残缺的那部分根本不会改变数量级,因此可以将其近似看成一个满元素的金字塔,因此从顶向下挨个计算,也就是计算一个等比数列求和,公比为2;最终计算出其时间复杂度为 :O(2^{n})


    📜案例8——三层循环的时间复杂度

    我希望通过这题,可以让大家明白复杂度的核心是数量级的问题,在计算步骤上,只要不改变其最终数量级,可以通过省略和近似的方式来估算其复杂度:

    for (i=1 ;i<=n ;i++)
        for(j=1 ;j<=i; j++)
            for(k=1; k<=j; k++)
                x++;

    对于上题我们可以从内层向外层来看,首先最内层循环的次数为 j 次,次外层循环为 i 次,此时计算内部两层循环的次数为(1+2+3+4+·····+i)次,即 (1+i)*i/2,这时我们再计算最外层循环,由于最外层循环n次,i的取值范围为(1~n),因此其执行总次数为:

    由上述计算过程可得其最后的时间复杂度为O(n^3)。

    注意:通过这题我希望大家明白的一个道理是,时间复杂度并不是准确计算出来的一种度量,而是一种算法的最坏情况,或者是算法的一种数量级情况,对于上题,在计算过程中我都采取了局部的省略和近似,这是因为,这些省略和近似并不会改变复杂度的最终数量级,也就是n^3,通过这种省略和近似可以节约复杂度的计算时间。

     ✨✨✨我是分割线✨✨✨

    🥝2.3 算法的空间复杂度


    🍊1.什么是空间复杂度?

    空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少 bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似,也使用大O渐进表示法。


    📜案例1——冒泡排序的空间复杂度

    空间复杂度计算的是在程序运行过程中,为了满足程序需求,临时创建的空间个数。在下例冒泡排序中,总共开了三个空间,分别是变量end、exchange、i;尽管在这个循环中,exchange这个变量被循环使用,但是用的始终都是exchange这1个空间,只是使用次数在增加,使用的空间个数始终为1,没有发生改变,因此其时间复杂度为O(N),而空间复杂度为O(1)。

    注意:使用了常数个空间==空间复杂度为O(1)


    📜案例2——斐波那契数列的空间复杂度

    下例中,我们单单计算fibArray动态开辟的空间就已经有(n+1)个了,其他剩下的变量开设的都是常数个,因此时间复杂度为O(N);我们这里只需要算一个大概的即可,计算开辟空间数最多的那个即可。

    注意:空间复杂度的计算比时间复杂度的简单,一般来说不是O(1)就是O(N)。

    // 计算Fibonacci的空间复杂度?
    // 返回斐波那契数列的前n项
    long long* Fibonacci(size_t n)
     {
         if(n==0)
         return NULL;
     
         long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));
         fibArray[0] = 0;
         fibArray[1] = 1;
         for (int i = 2; i <= n ; ++i)
             {
                 fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
             }
         return fibArray;
     }

    📜案例3——计算阶乘递归Fac的空间复杂度

    long long Fac(size_t N)
     {
         if(N == 0)
             return 1;
         return Fac(N-1)*N; 
    }

    对于本题,递归出N个栈帧,栈帧开辟的空间是常数个,可以认为是O(1),因此决定其开辟空间个数的主要取决于其递归的次数,本题递归次数为N次,因此空间复杂度为O(N)。


    📜案例4——计算斐波那契数列的空间复杂度

    long long Fib(size_t N) 
    {
         if(N < 3)
             return 1;
     
         return Fib(N-1) + Fib(N-2);
    }

    上例中我们不断调用,当我们一直递归调用到Fib(2)时,将Fib(2)的值返回给Fib(3),这时Fib(2)栈帧就销毁了,Fib(3)将接着调用Fib(1),这时Fib(1)使用了之前Fib(2)使用的空间,使用了同一块空间;同理在向上返回的时候将不断重复使用销毁过的空间,从Fib(2)到Fib(N)总共建立了N-1个栈帧;而后该开始递归调用Fib(N-2),而这块空间正是之前Fib(N-1)使用过的空间,即空间是可以回收复用的。因此本题的空间复杂度为O(N)。

    注意:时间是累计的不可复用,而空间回收之后是可以重复利用的。

    程序证明:

    当调用完f1( )函数后,将f1中的空间释放;调用f2( )函数,由a和b的地址相同可见,f2( )使用的空间正是刚刚f1释放的空间,证明空间被重复利用了。

    void f1()
    {
    	int a = 0;
    	printf("%p\n", & a);
    }
    
    void f2()
    {
    	int b = 0;
    	printf("%p\n", & b);
    }
    
    int main()
    {
    	f1(); //调用函数开始会创建栈帧;结束会销毁栈帧
    	f2();
    	return 0;
    }


    📜010.题目难度 ⭐️⭐️

    010.下面的说法中,错误的是( )。
    I.算法原地工作的含义是指不需要任何额外的辅助空间
    II.在相同规模n下,复杂度为O(n)的算法在时间上总是优于复杂度为O(2")的算法
    III.所谓时间复杂度,是指最坏情况下估算算法执行时间的一个上界
    IV.同一个算法,实现语言的级别越高,执行效率越低
    A.I                B.I、II            C.I、IV            D.III

    🍊详细题解:

    I. 算法原地工作是指算法所需的辅助空间是常量,即O(1)个空间。

    II. 算法的负责度是一个宏观上的理解,O(n)的算法一定是优于O(2")的算法。

    III. 时间复杂度总是考虑最坏情况下的时间复杂度,以保证算法的运行时间不会比它更长。

    IV. 越高级的语言,需要层层转换为低级语言给计算机读取,因此执行效率会降低。

    ✅正确答案:A

     ✨✨✨我是分割线✨✨✨

    📝LeetCode之消失的数字



    思路1-排序

    思路:将这些数字进行挨个排序,如果后一个数字不是前一个数字+1,那么缺的数就是这两个数共同相邻的那个数。例如我们将数字排序后得到{1,2,4},我们从前向后挨个比较相邻两个数,我们发现2后面的数字不等于2+1,因此我们得出缺少的数字是3。

    优点:简单易想

    缺点:时间复杂度太大,以下算法时间复杂度均未满足题目要求。

    • 采用冒泡排序—— 时间复杂度:O(N^{2})
    • 采用快排qsort——时间复杂度:O(N*logN)

    思路2-映射方式

    思路:建立一个可以完整包含0~n的所有整数的数组并将其初始化为全-1;然后将输入的数字x放到对应下标为[x]的数组空间中(如数字6就放到下标为[6]的空间里);全部放完后,数组中元素值为-1对应的下标,就是缺失的数字。

    缺点:这种方式有O(N)的空间复杂度。


    思路3-异或^

    前情提要:

    1.异或运算中顺序发生改变,并不会影响最终结果:

     a^b^c = b^a^c = b^c^a = c^b^a =···

    2.两个相同数字异或的最终结果为0;

    a^a = b^b = 0

    3.0和任意非零数x相异或,其结果等于非零数x;

    0 ^ x = x

    思路:对于本题,可先对0-n的连续数字异或一遍,接着对含有欠缺数字的数组中的每个数字异或,那么该数组中未欠缺的数字和0-n连续数字会异或2次,结果为0;而因为数组中缺少1位数字,原先0-n的连续数字中必有1位只参与异或1次,因此最后异或计算出的值即为缺失的数字。

    代码实现:

    int missingNumber(int* nums, int numsSize){
        int sum=0;
        for(int i=0;i<numsSize;++i)
        {
            sum^=nums[i];//计算数列中的异或
        }//时间复杂度为O(N)
        
        for(int j=0;j<numsSize+1;++j)
        {
            sum^=j;//求0-n的异或
        }//时间复杂度为O(N)
     
        return sum;
    }

    思路4-数列和相减

    (0-n计算等差数列的和)-(数组中的值相加)
           O(1)               O(N) 

    优点:算法时间复杂度满足√

    代码实现:

    int missingNumber(int* nums, int numsSize){
        int sum1=0 , sum2=0 ,ret=0;
        for(int i=0;i<numsSize;++i)
        {
            sum2+=nums[i];//计算数列中的和
        }//时间复杂度为O(N)
        sum1=numsSize*(numsSize+1)/2;//计算0-n的等差数列之和
        ret=sum1-sum2;
        return ret;
    }

     ✨✨✨我是分割线✨✨✨

    📝LeetCode之旋转数组


    进阶:

    • 尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
    • 你可以使用空间复杂度为 O(1) 的原地算法解决这个问题吗?

    思路1-依次右移动

    思路:右旋K次,依次移动一个;当K=N时,等于数组没有发生旋转,当K=N+1时,等于数组旋转1次,即旋转的次数=(K%N);当(K%N=N-1)时,旋转的次数最多。

    时间复杂度:旋转1次需要移动N次,旋转K次就需要移动N*K次,因此为O(K*N);当K的值为N-1时,复杂度为O(N^2),但是由于K也是未知数,因此该算法的时间复杂度为O(N*K)。

    空间复杂度:没有额外开数组,用的是原数组,因此为O(1)。


    思路2-额外开数组

    思路:用空间来换时间,额外建立一个数组,将后K个数拷贝到新建数组的前端,将(n-K)个剩下的数,拷贝到新数组的后端。

    时间复杂度:将从前向后挨个计算,将前(n-k)个数拷贝到新数组后(n-k)个位置,再将后k个数拷贝到新数组的前k个位置,计算量即为n,因此时间复杂度为O(N)。

    空间复杂度:这时额外开了一个数组,因此空间复杂度为O(N)。


    思路3-三轮逆置

    思路:用空间来换时间,额外建立一个数组,将后K个数拷贝到新建数组的前端,将(n-K)个剩下的数,拷贝到新数组的后端。

    时间复杂度:进行三轮逆置,因此时间复杂度的量级依然取决于元素个数n,时间复杂度为O(N)。

    空间复杂度:没有额外开数组,用的是原数组,因此为O(1)。

    代码实现:

    void reverse(int*a, int left , int right)//创建一个逆置函数
    {
        while(left<right)
        {
            int tmp=a[left];
            a[left]=a[right];
            a[right]=tmp;
            ++left;
            --right;
        }
    }
    
    void rotate(int* nums, int numsSize, int k){
        k=k%numsSize;
        reverse(nums,0,numsSize-k-1);//step1.逆置前n-k个
        reverse(nums,numsSize-k,numsSize-1);//step2.逆置后k个
        reverse(nums,0,numsSize-1);//step3.逆置整体n个
    }

     ✨✨✨我是分割线✨✨✨

    📜水滴石穿


    📜011.题目难度 ⭐️

    011.以下算法的时间复杂度为( )。
    void fun(int n) {
    	int i = 1;
    	while (i <= n)
    		i = i * 2;
    }
    A.O(n)        B.O(n^2)        C.O(nlogn)        D.O(logn)
    

    🍊详细题解:

    ✅正确答案:D


    📜012.题目难度 ⭐️

    012.以下算法的时间复杂度为( )。
    void fun(int n) {
    	int i = 0;
    	while (i * i * i <= n)
    		i++;
    }
    A.O(n)        B.O(nlogn)        C.O(³√n)        D.O(√n)

    🍊详细题解:

    ✅正确答案:C


    📜013.题目难度 ⭐️

    013.以下算法中最后一行语句的执行次数为( )。
    	int m = 0, i, j;
    	for (i = 1; i <= n; i++)
    		for (j = 1; j <= 2 * i; j++)
    			m++;
    A.n(n+1)        B.n        C.n+1        D.n^2

    🍊详细题解:

    ✅正确答案:A


    📜014.题目难度 ⭐️⭐️

    014.程序段如下:
    	for (i=n-1;i>1;i--)
    		for (j=1;j<i;j++)
    			if (A[j]> A[j+1])
    				A[j]与A[j+1]对换;
    
    其中n为正整数,则最后一行语句的频度在最坏情况下是( )。
    A.O(n)        B.O(nlogn)        C.O(n³)        D.O(n²)

    🍊详细题解:

    ✅正确答案:D


    📜015.题目难度 ⭐️⭐️

    015.【2014统考真题】下列程序段的时间复杂度是( )。
    count=0;
    for (k=1 ; k<=n ; k*=2)
        for(j=1;j<=n;j++)
            count++;
    A.O(logn)        B.O(n)        C.O(nlogn)        D.O(n^2)

    🍊详细题解:

    ✅正确答案:C


    📜016.题目难度 ⭐️⭐️⭐️

    016.【2017统考真题】下列函数的时间复杂度是( )。
        int func(int n){
            int i=0,sum=0;
            while (sum<n) sum +=++i;
            return i;
        }
    A.O(logn)        B.O(√n)        C.O(n)        D.O(nlogn)
    

    🍊详细题解:

    ✅正确答案:B


     📜017.题目难度 ⭐️⭐️⭐️

    🍊详细题解:

    🌕写在最后


    数据结构的世界是相当丰富的,内容方向繁多,但只要一步一个脚印,跟随【水滴计划】水滴石穿吃透、搞懂、拿捏住数据结构是完全没有问题的!后期该系列还会有视频教程和经验分享,关于更多这方面的内容,请关注本专栏哦!

    热爱所热爱的, 学习伴随终生,kikokingzz与你同在!❥(^_-)

    展开全文
  • 大学生 数据结构期末复习——知识点+题库 四川轻化工

    第一章绪论

    1.1 数据结构的基本概念

    (1)数据:所有能被计算机识别、存储和处理的符号的集合(包括数字、字符、声音、图像等信息 )。
    (2)数据元素:是数据的基本单位,具有完整确定的实际意义。在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。
    (3)数据项:构成数据元素的项目。它是数据不可分割的最小单位。
    (4)数据类型:指一个类型和定义在这个类型上的操作集合。例:C语言(基本类型:整型、浮点型、字符型等构造类型:数组、结构、联合、指针、枚举等)
    (5)抽象数据元素:抽象定义的、没有实际含义的数据元素。
    (6)抽象数据类型:用户自己定义的数据类型。
    (7)数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。或按照一定逻辑关系组织,并按一定存储方法存储的数据的集合,且需要定义一系列运算。逻辑结构、存储结构和运算合称为三要素。表示为:
    Data_Structure=(D, S)
    其中:D—元素有限集,S—关系有限集

    1.2 数据结构涵盖的内容

    ![在这里插入图片描述](https://img-blog.csdnimg.cn/a52cea60d3f9447fb28d05a5fb7d3567.png

    • 解释1: 什么叫数据的逻辑结构?
      答:指数据元素之间的逻辑关系。即从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。
      逻辑结构可细分为4类:
      集合结构: 仅同属一个集合
      线性结构: 一对一(1:1)
      树 结 构: 一对多(1:n) 非线性
      图 结 构: 多对多 (m:n) 非线性
    • 解释2:什么叫数据的物理结构?
      答:物理结构亦称存储结构,是数据的逻辑结构在计算机存储器内的表示(或映像)。它依赖于计算机。
      存储结构可分为4大类:顺序、链式、索引、散列
    • 解释3:什么是数据的运算?
      答:在数据的逻辑结构上定义的操作算法。
      它在数据的存储结构上实现。
      最常用的数据运算有 5 种:插入、删除、修改、查找、排序

    1.3 什么是抽象数据类型

    1 数据类型与抽象数据类型的区别

    数据类型:是一个值的集合和定义在该值上的一组操作的总称。
    抽象数据类型(ADT):由用户定义,用以表示应用问题的数据模型。它由基本的数据类型构成,并包括一组相关的服务(或称操作)

    2 抽象数据类型如何定义

    抽象数据类型可以用以下的三元组来表示:
    ADT = (D,S,P)
    D:数据对象
    S:D上的关系集
    P:D上的操作集

    3 抽象数据类型如何表示和实现

    抽象数据类型可以通过固有的数据类型(如整型、实型、字符型等)来表示和实现。即利用处理器中已存在的数据类型来说明新的结构,用已经实现的操作来组合新的操作。

    1.4 算法和算法分析

    算法的基本特性:有穷性、确定性、可行性、必有输出
    算法评价指标:正确性、可读性、健壮性、高效率与低存储量需求

    本章小结

    数据结构课程—— 数据结构+算法=程序,涉及数学、计算机硬件和软件。
    数据结构定义——指互相有关联的数据元素的集合,可用data_Structure=(D,S)表示。
    数据结构内容——数据的逻辑结构、存储结构和基本运算 。
    数据结构描述工具——抽象数据类型和类C语言。
    算法效率——时间效率和空间效率 。

    这是我们学校的机考题库,仅作参考

    【知识点】基本概念

    1. 数据结构中,与所使用的计算机无关的是数据的( A )结 构。A.逻辑 B.物理 C.存储 D.物理和存储
    2. 以下属于逻辑结构的是( C ) A.哈希表 B.单链表 C.有序表 D.顺序表
    3. 以下属于逻辑结构的是( B ) A.双链表 B.有序表 C.哈希表 D.顺序表
    4. 以下与数据的存储结构有关的术语是( D )。 A.网 B.队列 C.二叉树 D.链表
    5. 以下与数据的存储结构无关的术语是( B )。 A.单链表 B.栈 C.哈希表 D.循环队列
    6. 数据结构中,与所使用的计算机无关的是数据的( B)结 构。A.存储 B.逻辑 C.物理和存储 D.物理
    7. 可以用( C )定义一个完整的数据结构。 A.数据元素 B.数据对象 C.抽象数据类型 D.数据关系
    8. 下列数据中,( D )是非线性数据结构 A.链栈 B.堆C.循环队列 D.哈夫曼树
    9. 以下与数据的存储结构无关的术语是( A ) A.栈B.单链表 C.哈希表 D.循环队列

    【知识点】1.3本章练习题库

    选择题

    1. 一种抽象数据类型包括数据和( B )两个部分。 A.类型说明 B.操作 C.数据抽象 D.数据类型
    2. 数据结构是研究数据的( D )以及它们之间的相互关系。 A.理想结构,物理结构 B.理想结构,抽象结构 C.抽象结构,逻辑结构 D.物理结构,逻辑结构
    3. 以下说法正确的是(D)。 A.数据元素是数据的最小单位 B.数据项是数据的基本单位 C.数据结构是带有结构的各数据项的集合 D.一些表面上很不相同的数据可以有相同的逻辑结构
    4. 通常要求同一逻辑结构中的所有数据元素具有相同的特性, 这意味着( C )。 A.每个数据元素都一样 B.数据具有同一特点 C.不仅数据元素所包含的数据项的个数要相同,而且对应数据项的类型要一致 D.数据元素所包含的数据项的个数要相等

    判断题

    1. 健壮的算法不会因非法的输入数据而出现莫名其妙的状态。A
    2. 数据元素是数据的最小单位。B
    3. 只要是算法,肯定可以在有限的时间内完成。A
    4. 数据的物理结构是指数据在计算机内的实际存储形式。A
    5. 作为解决一类特定问题的算法,不能没有输入运算项。B
    6. 因为算法和程序没有区别,所以在数据结构中二者是通用的。B
    7. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算 机的储存结构。 B
    8. 同一数据逻辑结构中的所有数据元素都具有相同的特性是指 数据元素所包含的数据项的个数都相等。B
    9. 数据结构是指相互之间存在一种或多种关系的数据元素的全体。A

    填空题

    1. [填空1]是数据的基本单位。数据元素
    2. [填空1]是数据的最小单位。数据项
    3. 抽象数据类型的特点是 [填空1] 、信息隐蔽、使用与实现分离。数据封装
    4. 数据结构有线性结构、树结构、图结构、 [填空1] 等几种逻 辑结构。集合结构
    5. 一个算法具有 5个特性:有穷性、可行性、 [填空1] ,有零 个或多个输入、有一个或多个输出。确定性

    【知识点】1.5算法的概念和特性

    1. 下面关于算法说法错误的是( B ) A.算法不一定要用高级语言描述 B.算法最终必须由计算机程序实现 C.算法的确定性是指指令不能有二义性 D.一个算法可以没有输入
    2. 下面关于算法说法错误的是( B ) A.复杂度O(n)的算法在时间上不一定总是优于复杂度O(n2) 的算法 B.算法原地工作的含义是指不需要任何额外的辅助空间 C.同一个算法,不同的程序员实现,用低级语言实现的效率 不一定比高级语言实现效率高 D.算法的时间复杂度不是唯一的评判算法的标准

    2022.5.12 修改,明天更新下一章节

    展开全文
  • C#数据结构算法

    千次阅读 2022-03-14 08:42:40
    对于许多常见的问题,工具箱里的数据结构是理想的选择。就像.NET Framework 中 Windows 应用程序开发中的工具箱,程序员可以直接拿来或经过少许的修改就可以使用,非常方便。 2.讲授常用的算法 它和

    一、数据结构介绍

    运用计算机处理数据时,必须解决四个方面的问题:

    1.如何在计算机中方便、高效地表示和组织数据?

    2.如何在计算机存储器(内存和外存)中存储数据?

    3.如何对存储在计算机中的数据进行操作?可以有哪些操作?如何实现这些操作以及如何对同一问题的不同操作方法进行评价?

    4.必须理解每种数据结构的性能特征,以便选择一个适合于某个特定问题的数据机构。

    为什么学习数据结构?

    对于同样的问题,有的人写出来的程序效率高,而有的人却用很复杂的方法解决。
    学习数据结构的目的是:能用最有效的方法解决绝大多数的问题。

    学习数据结构的三个目的:

    1.讲授常用的数据结构

    这些数据结构形成了程序员基本数据结构工具箱(toolkit)。对于许多常见的问题,工具箱里的数据结构是理想的选择。就像.NET Framework 中 Windows 应用程序开发中的工具箱,程序员可以直接拿来或经过少许的修改就可以使用,非常方便。

    2.讲授常用的算法

    它和数据结构一样,是人们在长期实践过程中的总结,程序员可以直接拿来或经过少许的修改就可以使用。可以通过算法训练来提高程序设计水平。

    3.通过程序设计的技能训练促进程序员综合能力的提高。

    总结:数据结构是程序员的内功修炼的一部分。

    基本概念和术语:

    1.数据(Data)

    计算机程序处理各种各样的数据,可以是数值数据,如整数、实数或复数;也可以是非数值数据,如字符、文字、图形、图像、声音等。

    2.数据元素(Data Element)和数据项(Data Item)

    数据元素是数据的基本单位,在计算机程序中通常被作为一个整体进行考虑和处理。一个数据元素可由若干个数据项(Data Item)组成。数据项是不可分割的、含有独立意义的最小数据单位,数据项有时也称为字段(Field)或域(Domain)。例如,一条学生记录就是一个数据元素。这条记录中的学生学号、姓名、性别、籍贯、出生年月、成绩等字段就是数据项。数据项分为两种,一种叫做初等项,如学生的性别、籍贯等,在处理时不能再进行分割;另一种叫做组合项,如学生的成绩,它可以再分为数学、物理、化学等更小的项。

    3.数据对象(Data Object)

    数据对象是性质相同的数据元素的集合, 是数据的一个子集。例如,整数数据对象是{0,±1,±2,±3,…},字符数据对象是{a,b,c,…}。

    4.数据类型(Data Type)

    数据类型是高级程序设计语言中的概念,是数据的取值范围和对数据进行操作的总和。数据类型规定了程序中对象的特性。程序中的每个变量、常量或表达式的结果都应该属于某种确定的数据类型。例如,C#语言中的字符串类型( String,经常写为 string)。一个 String 表示一个恒定不变的字符序列集合,所有的字符序列集合构成 String 的取值范围。我们可以对 String 进行求长度、复制、连接两个字符串等操作。

    数据结构分类(Data Structure):

    数据结构是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中,数据元素之间都不是孤立的,而是存在着一定的关系,这种关系称为结构(Structure)。根据数据元素之间关系的不同特性,通常有 4 类基本数据结构:

    (1)集合(Set):如图(a)所示,该结构中的数据元素除了存在“同属于一个集合”的关系外,不存在任何其它关系。
    (2)线性结构(Linear Structure):如图(b)所示,该结构中的数据元素存在着一对一的关系。
    (3)树形结构(Tree Structure):如图(c)所示,该结构中的数据元素存在着一对多的关系。   (4)图状结构(Graphic Structure):如图(d)所示,该结构中的数据元素存在着多对多的关系。

    数据结构(Data Structure)简记为DS,是一个二元组,DS=(D,R),其中:D是数据元素的有限集合,R是数据元素之间关系的有限集合。

    什么是算法?

    算法(Algorithm)是对某一特定类型的问题的求解步骤的一种描述,是指令的有限序列。其中的每条指令表示一个或多个操作。

    一个算法应该具备以下5个特性:

    1.有穷性:一个算法总是在执行有穷步之后结束,即算法的执行时间是有限的;

    2.确定性:算法的每一个步骤都必须有确切的含义,即无二义,并且对于相同的输入只能有相同的输出;

    3.输入:一个算法具有零个或多个输入。它即是在算法开始之前给出的量。这些输入是某数据结构中的数据对象;

    4.输出:一个算法具有一个或多个输出,并且这些输出与输入之间存在着某种特定的关系;

    5.能行性:算法中的每一步都可以通过已经实现的基本运算的有限次运行来实现。

    算法和数据结构的关系

    数据结构可以认为是数据在程序中的存储结构,和基本数据操作。
    算法可以是认为解决问题的,算法是基于数据结构的。

    数据结构是问题的核心,是算法的基础。

    算法的评价标准

    1.运行时间(Running Time)。
    2.占用空间(Storage Space)。
    有时需要牺牲空间来换取时间,有时需要牺牲时间来换取空间。
    其他方面:3.正确性(Correctness)、4.可读性(Readability)、5.健壮性(Robustness)

    空间复杂度(Space Complexity):通常把算法在运行过程中临时占用的存储空间的大小叫算法的空间复杂度。它主要包括局部变量所占用的存储空间和系统为实现递归所使用的堆栈占用的存储空间。

    计算机的性能由以下因素决定:

    1、硬件条件。包括所使用的处理器的类型和速度(比如,使用双核处理器还是单核处理器)、可使用的内存(缓存和 RAM)以及可使用的外存等;

    2、实现算法所使用的计算机语言。实现算法的语言级别越高,其执行效率相对越低;

    3、所使用的语言的编译器/解释器。一般而言,编译的执行效率高于解释,但解释具有更大的灵活性;

    4、所使用的操作系统软件。操作系统的功能主要是管理计算机系统的软件和硬件资源,为计算机用户方便使用计算机提供一个接口。各种语言处理程序如编译程序、解释程序等和应用程序都在操作系统的控制下运行。

    时间复杂度:一个算法的时间复杂度(Time Complexity)是指该算法的运行时间与问题规模的对应关系。通常把算法中基本操作重复执行的次数(频度)作为算法的时间复杂度。

    算法中基本操作语句的频度是问题规模n的某个函数f(n),记作:T(n)=O(f(n))。其中O表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同。例如:T(n)=1/2n(n-1),则1/2n(n-1)的数量级与n²相同,所以T(n)=O(n²)。

    如果一个算法没有循环语句,则算法中基本操作的执行频度与问题规模n无关,记作O(1),也称为常数阶;

    如果一个算法只有一个一重循环,则算法的基本操作的执行频度与问题规模n呈线性增大关系,记作O(n),也叫线性阶。

    常用的还有平方阶O(n²),立方阶O(n³),对数阶O()等。

     

     

    数学预备知识:

    对数:一般地,如果a(a>0,a≠1)的b次幂等于N,就是ab=N,那么数b叫做以a为底N的对数(Logarithm),记作logaN=b,其中a叫做对数的底数,N叫做真数。

     从定义可知,负数和零没有对数。事实上,因为 a>0,所以不论 b 是什么实数,都有 ab>0,这就是说不论 b 是什么数,N 永远是正数,因此负数和零没有对数。

    递归(Recursive):一个算法调用自己来完成它的部分工作,在解决某些问题时,一个算法需要调用自身。如果一个算法直接调用自己或间接调用自己,就称这个算法是递归的。根据递归方式的不同,它分为直接递归(Direct Recursion)和间接递归(Indirect Recursion)。

    如阶乘函数就是一种递归,我们可以对n!作如下定义:

     阶乘函数的C#语言实现如下:

    //阶乘
        public static long fact(int n)
        {
            if(n<=1)
            {
                return 1;
            }
            else
            {
                return n * fact(n - 1);
            }
        }

    C#预备知识:

    接口(Interface):接口定义为一个约定,实现接口的类或结构必须遵守该约定。简单地说,接口是类之间交互时遵守的一个协议。接口是独立于类的一个定义,定义了类之间交互的标准。

    接口只包含成员定义,不包含成员的实现。接口不会继承自任何的System.Object派生类型。接口仅仅是一个包含着一组虚方法的抽象类型。成员的实现需要在继承的类或者结构中实现。接口的成员包括静态方法、索引器、常数、事件以及静态构造器等,不包含任何实例字段或实例构造器,所以,不能实例化一个接口。

    抽象类(Abstract Class)和接口在定义与功能上有很多相似的地方,在程序中选择使用抽象类还是接口需要比较抽象类和接口之间的具体差别。

    抽象类是一种不能实例化而必须从中继承的类,抽象类可以提供实现,也可以不提供实现。子类只能从一个抽象类继承。抽象类应主要用于关系密切的对象。如果要设计大的功能单元或创建组件的多个版本,则使用抽象类。

    接口是完全抽象的成员集合,不提供实现。类或者结构可以继承多个接口。接口最适合为不相关的类提供通用功能。如果要设计小而简练的功能块,则使用接口。接口一旦创建就不能更改,如果需要接口的新版本,必须创建一个全新的接口。

    接口的实现分为隐式实现和显式实现。如果类或者结构要实现的是单个接口,可以使用隐式实现;如果类或者结构继承了多个接口,那么接口中相同名称成员就要显式实现。显式实现是通过使用接口的完全限定名来实现接口成员的。

    接口及该接口的C#实现如下:

    class Progaram
    {
        static void Main(string[] args)
        {
            NewBook MyNovel = new NewBook("中国梦", "罗伯特", 500);
            MyNovel.ShowBook();
        }
    
        public interface IBook
        {
            void ShowBook();
            string GetTitle();
            int GetPages();
            void SetPages(int pages);
        }
    
        public class NewBook:IBook
        {
            public string title;
            public int pages;
            public string author;
            public NewBook(string title,string author,int pages)
            {
                this.title = title;
                this.author = author;
                this.pages = pages;
            }
    
            public int GetPages()
            {
                return pages;
            }
    
            public string GetTitle()
            {
                return title;
            }
    
            public void SetPages(int pages)
            {
                this.pages = pages;
            }
    
            public void ShowBook()
            {
                Console.WriteLine("书名为:{0}", title);
                Console.WriteLine("作者为:{0}", author);
                Console.WriteLine("页数为:{0}", pages);
            }
        }
    }

    泛型(Generic Type)是.NetFramework2.0最强大的功能。泛型的主要思想就是将算法与数据结构完全分离开来,使得一次定义的算法能够作用于多种数据结构,从而实现高度可重用的开发。通过泛型可以定义类型安全的数据结构,而没有必要使用实际的数据类型。这将显著提高性能并得到更高质量的代码,因为可以重用数据处理算法,而没有必要复制类型特定的代码。

    public class Container<T>
        {
            readonly int m_Size;//容器的容量
            int m_ContainerPointer;//容器指针,指示最后一个元素的位置
            T[] m_Items;//容器数组,存放数据
    
            //无参构造器
            public Container():this(100)
            {
                m_ContainerPointer = -1;
                m_Size = 100;
            }
    
            //有参构造器
            public Container(int size)
            {
                m_Size = size;
                m_Items = new T[m_Size];
                m_ContainerPointer = -1;
            }
    
            //获取容器元素个数属性
            public int Count
            {
                get
                {
                    return m_ContainerPointer;
                }
            }
    
            //判断容器是否为空
            public bool IsEmpty
            {
                get 
                { 
                    return (m_ContainerPointer == -1); 
                }
            }
    
            //容器是否已满
            public bool IsFull
            {
                get 
                {
                    return (m_ContainerPointer == m_Size - 1);
                }
            }
    
            //在容器的尾部插入一个元素
            public void Insert(T item)
            {
                if(IsFull)
                {
                    Console.WriteLine("容器为空");
                    return;
                }
                else if(IsEmpty)
                {
                    m_Items[++m_ContainerPointer] = item;
                }
                else
                {
                    m_Items[++m_ContainerPointer] = item;
                }
            }
    
            //从容器的尾部删除一个元素
            public object Delete()
            {
                if (m_ContainerPointer >= 0)
                {
                    return m_Items[m_ContainerPointer--];
                }
                return null;
            }
        }

    二、线性表

    线性表是最简单、最基本、最常用的数据结构。线性表是线性结构的抽象(Abstract),线性结构的特点是结构中的数据元素之间存在一对一的线性关系。这种一对一的关系指的是数据元素之间的位置关系,即:

    (1)除第一个位置的数据元素外,其它数据元素位置的前面都只有一个数据元素;

    (2)除最后一个位置的数据元素外,其它数据元素位置的后面都只有一个元素。也就是说,数据元素是一个接一个的排列。因此,可以把线性表想象为一种数据元素序列的数据结构。

    线性表就是位置有先后关系,一个接着一个排列的数据结构。

    什么是线性表?

    线性表(List)是由n(n>=0)个相同类型的数据元素构成的有限序列。对于这个定义应该注意两个概念:一是“有限”,指的是线性表中的数据元素的个数是有限的,线性表中的每一个数据元素都有自己的位置。二是“相同类型”,指的是线性表中的数据元素都属于同一种类型。虽然有的线性表具有不同类型的数据元素,但本书中所讨论的线性表中的数据元素都属于同一类型。

    CLR中的线性表

    c# 1.1 提供了一个非泛型接口IList接口,接口中的项是object,实现了IList解扣子的类有ArrayList,ListDictionary,StringCollection,StringDictionary;

    c# 2.0 提供了泛型的IList<T>接口,实现了List<T>接口的类有List<T>;

    线性表的接口定义

    public interface IListDS<T>
    {
        int GetLength(); //求长度 
        void Clear(); //清空操作 
        bool IsEmpty(); //判断线性表是否为空 
        void Append(T item); //附加操作 
        void Insert(T item, int i); //插入操作 
        T Delete(int i); //删除操作 
        T GetElem(int i); //取表元 
        int Locate(T value); //按值查找 
    }

    线性表的实现方式

    线性表的实现方式有下面几种:

    1.顺序表;

    2.单链表;

    3.双向链表;

    4.循环链表;

    顺序表

    在计算机内,保存线性表最简单、最自然的方式,就是把表中的元素一个接一个地放进顺序的存储单元,这就是线性表的顺序存储(Sequence Storage)。线性表的顺序存储是指在内存中用一块地址连续的空间依次存放线性表的数据元素,用这种方式存储的线性表叫顺序表(Sequence List),如图所示。顺序表的特点是表中相邻的数据元素在内存中存储位置也相邻。

    顺序表的存储

    假设顺序表中的每个数据元素占w个存储单元,设第i个数据元素的存储地址为Loc(ai),则有:
    Loc(ai)= Loc(a1)+(i-1)*w  1≤i≤n 式中的Loc(a1)表示第一个数据元素a1的存储地址,也是顺序表的起始存储地址,称为顺序表的基地址(Base Address)。也就是说,只要知道顺序表的基地址和每个数据元素所占的存储单元的个数就可以求出顺序表中任何一个数据元素的存储地址。并且,由于计算顺序表中每个数据元素存储地址的时间相同,所以顺序表具有随机存取的特点。(可以在任意位置存取东西)
    C#语言中的数组在内存中占用的存储空间就是一组连续的存储区域,因此,数组具有任意存取的特点。所以,数组天生具有表示顺序表的数据存储区域的特性。

    顺序表的实现

    public class SeqList<T>:IListDS<T>
    {
        private int maxsize;//顺序表的容量
        private T[] data;//数组,用于存储顺序表中的数据元素
        private int last;//指示顺序表最后一个元素的位置
    
        //索引器
        public T this[int index]
        {
            get 
            {
                return data[index];
            }
            set
            {
                data[index] = value;
            }
        }
    
        //最后一个数据元素位置属性
        public int Last
        {
            get 
            {
                return last;
            }
        }
    
        //容量属性
        public int Maxsize
        {
            get 
            {
                return maxsize;
            }
            set
            {
                maxsize = value;
            }
        }
    
        //构造器
        public SeqList(int size)
        {
            data = new T[size];
            maxsize = size;
            last = -1;
        }
    
        //求顺序表的长度
        public int GetLength()
        {
            return last + 1;
        }
    
        //清空顺序表
        public void Clear()
        {
            last = -1;
        }
    
        //判断顺序表是否为空
        public bool IsEmpty()
        {
            if(last==-1)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    
        //判断顺序表是否为满
        public bool IsFull()
        {
            if(last==maxsize-1)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    
        //在顺序表的末尾添加新元素
        public void Append(T item)
        {
            if(IsFull())
            {
                Console.WriteLine("List is full");
                return;
            }
            data[++last] = item;
        }
    
        //在顺序表的第i个数据元素的位置插入一个数据元素
        public void Insert(T item,int i)
        {
            if(IsFull())
            {
                Console.WriteLine("List is full");
                return;
            }
            if(i<1||i>last+2)
            {
                Console.WriteLine("Position is error!");
                return;
            }
            if(i==last+2)
            {
                data[last + 1] = item;
            }
            else
            {
                for(int j=last;j>=i-1;--j)
                {
                    data[j + 1] = data[j];
                }
                data[i - 1] = item;
            }
            ++last;
        }
    
        //删除顺序表的第i个数据元素
        public T Delete(int i)
        {
            T tmp = default(T);
            if(IsEmpty())
            {
                Console.WriteLine("List is empty");
                return tmp;
            }
            if(i<1||i>last+1)
            {
                Console.WriteLine("Position is error!");
                return tmp;
            }
            if(i==last+1)
            {
                tmp = data[last--];
            }
            else
            {
                tmp = data[i - 1];
                for(int j=i;j<=last;++j)
                {
                    data[j] = data[j + 1];
                }
            }
            --last;
            return tmp;
        }
    
        //获得顺序表的第i个数据元素
        public T GetElem(int i)
        {
            if(IsEmpty()||(i<1)||(i>last+1))
            {
                Console.WriteLine("List is empty or Position is error");
                return default(T);
            }
            return data[i - 1];
        }
    
        //在顺序表中查找值为value的数据元素
        public int Locate(T value)
        {
            if(IsEmpty())
            {
                Console.WriteLine("Last is Empty!");
                return -1;
            }
    
            int i = 0;
            for(i=0;i<=last;++i)
            {
                if(value.Equals(data[i]))
                {
                    break;
                }
            }
            if(i>last)
            {
                return -1;
            }
            return i;
        }
    
        //顺序表倒置
        public void Reverse()
        {
            T tmp = default(T);
            int len = GetLength();
            for(int i=0;i<=len/2;++i)
            {
                tmp = data[i];
                data[i] = data[len - i];
                data[len - i] = tmp;
            }
        }
    }

    答:算法思路:把第一个元素与最后一个元素交换,把第二个元素与倒数第二个元素交换。一般地,把第i个元素与第n-i个元素交换,i的取值范围是0到n/2 (n为顺序表的长度)。

    存储整数的顺序表的倒置的算法实现如下:

    //顺序表倒置(存储的整数)
        public void ReverseSeqList(SeqList<int> L)
        {
            int tmp = 0;
            int len = L.GetLength();
            for(int i=0;i<=len/2;++i)
            {
                tmp = L[i];
                L[i] = L[len - i];
                L[len - i] = tmp;
            }
        }

    【例2-2】有数据类型为整型的顺序表La和Lb,其数据元素均按从小到大的升序排列,编写一个算法将它们合并成一个表Lc,要求Lc中数据元素也按升序排列。

    算法思路:依次扫描La和Lb的数据元素,比较La和Lb当前数据元素的值,将较小值的数据元素赋给Lc,如此直到一个顺序表被扫描完,然后将未完的那个顺序表中余下的数据元素赋给Lc即可。Lc的容量要能够容纳La和Lb两个表相加的长度。

    按升序合并两个表的算法C#实现如下:

    public SeqList<int> Merge(SeqList<int> La,SeqList<int> Lb)
        {
            SeqList<int> Lc = new SeqList<int>(La.Maxsize + Lb.Maxsize);
            int i = 0;
            int j = 0;
            int k = 0;
            //两个表中都有数据元素
            while(i<=(La.GetLength()-1)&&(j<=(Lb.GetLength()-1)))
            {
                if(La[i]<Lb[j])
                {
                    Lc.Append(La[i++]);
                }
                else
                {
                    Lc.Append(Lb[j++]);
                }
            }
    
            //a表中还有数据元素
            while(i<=(La.GetLength()-1))
            {
                Lc.Append(La[i++]);
            }
    
            //b表中还有数据元素
            while(j<=(Lb.GetLength()-1))
            {
                Lc.Append(Lb[j++]);
            }
            return Lc;
        }

    该算法的时间复杂度是O(m+n),m是La的表长,n是Lb的表长。

    【例2-3】已知一个存储整数的顺序表La,试构造顺序表Lb,要求顺序表Lb中只包含顺序表La中所有值不相同的数据元素。

    算法思路:先把顺序表La的第一个元素赋给顺序表Lb,然后从顺序表La的第二个元素起,每一个元素与顺序表Lb中每一个元素进行比较,如果不相同,则把该元素附加到顺序表Lb的末尾。

    从表中删除相同数据元素的算法的C#实现如下:

    public SeqList<int> Purge(SeqList<int> La)
        {
            SeqList<int> Lb = new SeqList<int>(La.Maxsize);
            //将a表中的第一个数据元素赋给b表
            Lb.Append(La[0]);
            //依次处理a表中的数据元素
            for(int i=1;i<=La.GetLength()-1;++i)
            {
                int j = 0;
                //查看b表中有无与a表中相同的数据元素
                for(j=0;j<=Lb.GetLength()-1;++j)
                {
                    //有相同的数据元素
                    if(La[i].CompareTo(Lb[j])==0)
                    {
                        break;
                    }
                }
                //没有相同的数据元素,将a表中数据元素附加到b表的末尾
                if(j>Lb.GetLength()-1)
                {
                    Lb.Append(La[i]);
                }
            }
            return Lb;
        }

    该算法的时间复杂度是O(m+n),m是La的表长,n是Lb的表长。

    单链表

    顺序表是用地址连续的存储单元顺序存储线性表中的各个数据元素,逻辑上相邻的数据元素在物理位置上也相邻。因此,在顺序表中查找任何一个位置上的数据元素非常方便,这是顺序存储的优点。但是,在对顺序表进行插入和删除时,需要通过移动数据元素来实现,影响了运行效率。线性表的另外一种存储结构——链式存储(Linked Storage),这样的线性表叫链表(Linked List)。链表不要求逻辑上相邻的数据元素在物理存储位置上也相邻,因此,在对链表进行插入和删除时不需要移动数据元素,但同时也失去了顺序表可随机存储的优点。

    单链表的存储

    链表是用一组任意的存储单元来存储线性表中的数据元素(这组存储单元可以是连续的,也可以是不连续的)。那么,怎么表示两个数据元素逻辑上的相邻关系呢?即如何表示数据元素之间的线性关系呢?为此,在存储数据元素时,除了存储数据元素本身的信息外,还要存储与它相邻的数据元素的存储地址信息。这两部分信息组成该数据元素的存储映像(Image),称为结点(Node)。把存储据元素本身信息的域叫结点的数据域(Data Domain),把存储与它相邻的数据元素的存储地址信息的域叫结点的引用域(Reference Domain)。因此,线性表通过每个结点的引用域形成了一根“链条”,这就是“链表”名称的由来。
    如果结点的引用域只存储该结点直接后继结点的存储地址,则该链表叫单链表(Singly Linked List)。把该引用域叫 next。单链表结点的结构如图所示,图中 data 表示结点的数据域。

     链式存储结构

    下图是线性表(a1,a2,a3,a4,a5,a6)对应的链式存储结构示意图。

     另外一种表示形式:

     单链表结点定义:

    public class Node<T>
    {
        private T data;//数据域
        private Node<T> next;//引用域
    
        //构造器
        public Node(T val,Node<T> p)
        {
            data = val;
            next = p;
        }
    
        //构造器
        public Node(Node<T> p)
        {
            next = p;
        }
    
        //构造器
        public Node(T val)
        {
            data = val;
            next = null;
        }
    
        //构造器
        public Node()
        {
            data = default(T);
            next = null;
        }
    
        //数据域属性
        public T Data
        {
            get 
            {
                return data;
            }
            set
            {
                data = value;
            }
        }
    
        //引用域属性
        public Node<T> Next
        {
            get 
            {
                return next;
            }
            set
            {
                next = value;
            }
        }
    }

    单链表的实现:

    public class LinkList<T> : IListDS<T>
    {
        private Node<T> head;//单链表的头引用
    
        //头引用属性
        public Node<T> Head
        {
            get
            {
                return head;
            }
            set
            {
                head = value;
            }
        }
    
        //构造器
        public LinkList()
        {
            head = null;
        }
    
        //求单链表的长度
        public int GetLength()
        {
            Node<T> p = head;
            int len = 0;
            while (p != null)
            {
                ++len;
                p = p.Next;
            }
            return len;
        }
    
        //清空单链表
        public void Clear()
        {
            head = null;
        }
    
        //判断单链表是否为空
        public bool IsEmpty()
        {
            if (head == null)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    
        //在单链表的末尾添加新元素
        public void Append(T item)
        {
            Node<T> q = new Node<T>(item);
            Node<T> p = new Node<T>();
            if (head == null)
            {
                head = q;
                return;
            }
            p = head;
            while (p.Next != null)
            {
                p = p.Next;
            }
            p.Next = q;
        }
    
        //在单链表的第i个结点的位置前插入一个值为item的结点
        public void Insert(T item, int i)
        {
            if (IsEmpty() || i < 1)
            {
                Console.WriteLine("List is empty or Position is error!");
                return;
            }
            if (i == 1)
            {
                Node<T> q = new Node<T>(item);
                q.Next = head;
                head = q;
                return;
            }
            Node<T> p = head;
            Node<T> r = new Node<T>();
            int j = 1;
    
            while (p.Next != null && j < i)
            {
                r = p;
                p = p.Next;
                ++j;
            }
            if (j == i)
            {
                Node<T> q = new Node<T>(item);
                q.Next = p;
                r.Next = q;
            }
        }
    
        //在单链表的第i个结点的位置后插入一个值为item的结点
        public void InsertPost(T item, int i)
        {
            if (IsEmpty() || i < 1)
            {
                Console.WriteLine("List is empty or Position is error!");
                return;
            }
            if (i == 1)
            {
                Node<T> q = new Node<T>(item);
                q.Next = head.Next;
                head.Next = q;
                return;
            }
    
            Node<T> p = head;
            int j = 1;
            while (p != null && j < i)
            {
                p = p.Next;
                ++j;
            }
            if (j == i)
            {
                Node<T> q = new Node<T>(item);
                q.Next = p.Next;
                p.Next = q;
            }
        }
    
        //删除单链表的第i个结点
        public T Delete(int i)
        {
            if (IsEmpty()||i<0)
            {
                Console.WriteLine("Link is empty or Position is error!");
                return default(T);
            }
            Node<T> q = new Node<T>();
            if(i==1)
            {
                q = head;
                head = head.Next;
                return q.Data;
            }
            Node<T> p = head;
            int j = 1;
            while(p.Next!=null&&j<i)
            {
                ++j;
                q = p;
                p = p.Next;
            }
            if(j==i)
            {
                q.Next = p.Next;
                return p.Data;
            }
            else
            {
                Console.WriteLine("The ith node is not exist!");
                return default(T);
            }
        }
    
        //获得单链表的第i个数据元素
        public T GetElem(int i)
        {
            if(IsEmpty())
            {
                Console.WriteLine("List is empty!");
                return default(T);
            }
            Node<T> p = new Node<T>();
            p = head;
            int j = 1;
            while(p.Next!=null&&j<i)
            {
                ++j;
                p = p.Next;
            }
            if(j==i)
            {
                return p.Data;
            }
            else
            {
                Console.WriteLine("The ith node is not exist!");
                return default(T);
            }
        }
    
        //在单链表中查找值为value的结点
        public int Locate(T value)
        {
            if(IsEmpty())
            {
                Console.WriteLine("List is Empty!");
                return -1;
            }
            Node<T> p = new Node<T>();
            p = head;
            int i = 1;
            while(!p.Data.Equals(value)&&p.Next!=null)
            {
                p = p.Next;
                ++i;
            }
            return i;
        }
    }

    双向链表

    前面介绍的单链表允许从一个结点直接访问它的后继结点,所以, 找直接后继结点的时间复杂度是 O(1)。但是,要找某个结点的直接前驱结点,只能从表的头引用开始遍历各结点。如果某个结点的 Next 等于该结点,那么,这个结点就是该结点的直接前驱结点。也就是说,找直接前驱结点的时间复杂度是 O(n), n是单链表的长度。当然,我们也可以在结点的引用域中保存直接前驱结点的地址而不是直接后继结点的地址。这样,找直接前驱结点的时间复杂度只有 O(1),但找直接后继结点的时间复杂度是 O(n)。如果希望找直接前驱结点和直接后继结点的时间复杂度都是 O(1),那么,需要在结点中设两个引用域,一个保存直接前驱结点的地址,叫 prev,一个直接后继结点的地址,叫 next,这样的链表就是双向链表(Doubly Linked List)。双向链表的结点结构示意图如图所示。

    双向链表结点实现

    public class DbNode<T>
    {
        private T data; //数据域
        private DbNode<T> prev; //前驱引用域
        private DbNode<T> next; //后继引用域
    //构造器
        public DbNode(T val, DbNode<T> p)
        {
            data = val;
            next = p;
        }
    
    //构造器
    
        public DbNode(DbNode<T> p)
        {
            next = p;
        }
    
    //构造器
        public DbNode(T val)
        {
            data = val;
            next = null;
        }
    
    //构造器
        public DbNode()
        {
            data = default(T);
            next = null;
        }
    
    //数据域属性
        public T Data
        {
            get { return data; }
            set { data = value; }
        }
    
    //前驱引用域属性
        public DbNode<T> Prev
        {
            get { return prev; }
            set { prev = value; }
        }
    
    //后继引用域属性
        public DbNode<T> Next
        {
            get { return next; }
            set { next = value; }
        }
    }
    

    双向链表插入示意图

     循环链表

    有些应用不需要链表中有明显的头尾结点。在这种情况下,可能需要方便地从最后一个结点访问到第一个结点。此时,最后一个结点的引用域不是空引用,而是保存的第一个结点的地址(如果该链表带结点,则保存的是头结点的地址),也就是头引用的值。带头结点的循环链表(Circular Linked List)如图所示。

     三、栈和队列

    栈和队列是非常重要的两种数据结构,在软件设计中应用很多。栈和队列也是线性结构,线性表、栈和队列这三种数据结构的数据元素以及数据元素间的逻辑关系完全相同,差别是线性表的操作不受限制,而栈和队列的操作受到限制。栈的操作只能在表的一端进行,队列的插入操作在表的一端进行而其它操作在表的另一端进行,所以,把栈和队列称为操作受限的线性表。

    栈(Stack)是操作限定在表的尾端进行的线性表。表尾由于要进行插入、删除等操作,所以,它具有特殊的含义,把表尾称为栈顶( Top),另一端是固定的,叫栈底( Bottom)。当栈中没有数据元素时叫空栈(Empty Stack)。
    栈通常记为: S= (a1,a2,…,an),S是英文单词stack的第 1 个字母。a1为栈底元素,an为栈顶元素。这n个数据元素按照a1,a2,…,an的顺序依次入栈,而出栈的次序相反,an第一个出栈,a1最后一个出栈。所以,栈的操作是按照后进先出(Last In First Out,简称LIFO)或先进后出(First In Last Out,简称FILO)的原则进行的,因此,栈又称为LIFO表或FILO表。栈的操作示意图如图所示。

     BCL中的栈

    C#2.0 以下版本只提供了非泛型的Stack类(存储object类型)

    C#2.0 提供了泛型的Stack<T>类

    重要的方法如下:
    1,Push()入栈(添加数据)
    2,Pop()出栈(删除数据,返回被删除的数据)
    3,Peek()取得栈顶的数据,不删除
    4,Clear()清空所有数                                                                                                               5,Count取得栈中数据的个数

    栈的接口定义

    public interface IStackDS<T>
        {
            int Count { get; }
            int GetLength();//求栈的长度
            bool IsEmpty();//判断栈是否为空
            void Clear();//清空操作
            void Push(T item);//入栈操作
            T Pop();//出栈操作
            T Peek();//取栈顶元素
        }

    顺序栈

    用一片连续的存储空间来存储栈中的数据元素(使用数组),这样的栈称为顺序栈(Sequence Stack)。类似于顺序表,用一维数组来存放顺序栈中的数据元素。栈顶指示器 top 设在数组下标为 0 的端, top 随着插入和删除而变化,当栈为空时,top=-1。下图是顺序栈的栈顶指示器 top 与栈中数据元素的关系图。

    class SeqStack<T> : IStackDS<T>
        {
            private T[] data;
            private int top;
    
            public SeqStack(int size)
            {
                data = new T[size];
                top = -1;
            }
    
            public SeqStack():this(10)
            {
    
            }
    
            public int Count
            {
                get { return top + 1; }
            }
    
            public void Clear()
            {
                top = -1;
            }
    
            public int GetLength()
            {
                return Count;
            }
    
            public bool IsEmpty()
            {
                return Count == 0;
            }
    
            public T Peek()
            {
                return data[top];
            }
    
            public T Pop()
            {
                T temp = data[top];
                top--;
                return temp;
            }
    
            public void Push(T item)
            {
                data[top + 1] = item;
                top++;
            }
        }

    链栈

    栈的另外一种存储方式是链式存储,这样的栈称为链栈(Linked Stack)。链栈通常用单链表来表示,它的实现是单链表的简化。所以,链栈结点的结构与单链表结点的结构一样,如图 3.3 所示。由于链栈的操作只是在一端进行,为了操作方便,把栈顶设在链表的头部,并且不需要头结点。

    链栈的结点

    class Node<T>
        {
            private T data;
            private Node<T> next;
    
            public Node()
            {
                data = default(T);
                next = null;
            }
    
            public Node(T data)
            {
                this.data = data;
                next = null;
            }
    
            public Node(Node<T> next)
            {
                this.next = next;
                data = default(T);
            }
    
            public Node(T data,Node<T> next)
            {
                this.data = data;
                this.next = next;
            }
    
            public T Data 
            { 
                get { return data; }
                set { data = value; }
            }
    
            public Node<T> Next
            {
                get { return next; }
                set { next = value; }
            }
        }

     链栈的类

    class LinkStack<T> : IStackDS<T>
        {
            private Node<T> top;//栈顶元素结点
    
            public int count = 0;//栈中元素个数
    
            public int Count
            {
                get { return count; }
            }
    
            public int GetLength()
            {
                return count;
            }
    
            public void Clear()
            {
                count = 0;
                top = null;
            }
    
            
    
            public bool IsEmpty()
            {
                return count == 0;
            }
    
            /// <summary>
            /// 取得栈顶中的数据,不删除栈顶
            /// </summary>
            /// <returns></returns>
            public T Peek()
            {
                return top.Data;
            }
    
            /// <summary>
            /// 出栈  取得栈顶元素,然后删除
            /// </summary>
            /// <returns></returns>
            public T Pop()
            {
                T data = top.Data;
                top = top.Next;
                count--;
                return data;
            }
    
            /// <summary>
            /// 入栈
            /// </summary>
            /// <param name="item"></param>
            public void Push(T item)
            {
                //把新添加的元素作为头结点(栈顶)
                Node<T> newNode = new Node<T>(item);
                newNode.Next = top;
                top = newNode;
                count++;
            }
        }

    队列

    队列(Queue)是插入操作限定在表的尾部而其它操作限定在表的头部进行的线性表。把进行插入操作的表尾称为队尾(Rear),把进行其它操作的头部称为队头(Front)。当队列中没有数据元素时称为空队列(Empty Queue)。
    队列通常记为: Q= (a1,a2,…,an),Q是英文单词queue的第 1 个字母。a1为队头元素,an为队尾元素。这n个元素是按照a1,a2,…,an的次序依次入队的,出对的次序与入队相同,a1第一个出队,an最后一个出队。所以,对列的操作是按照先进先出(First In First Out)或后进后出( Last In Last Out)的原则进行的,因此,队列又称为FIFO表或LILO表。队列Q的操作示意图如图所示。
    在实际生活中有许多类似于队列的例子。比如,排队取钱,先来的先取,后来的排在队尾。
    队列的操作是线性表操作的一个子集。队列的操作主要包括在队尾插入元素、在队头删除元素、取队头元素和判断队列是否为空等。与栈一样,队列的运算是定义在逻辑结构层次上的,而运算的具体实现是建立在物理存储结构层次上的。因此,把队列的操作作为逻辑结构的一部分,每个操作的具体实现只有在确定了队列的存储结构之后才能完成。队列的基本运算不是它的全部运算,而是一些常用的基本运算。

    BCL中的队列

    C#2.0 以下版本提供了非泛型的Queue类

    C#2.0 提供了泛型Queue<T>类
    方法
    1,Enqueue()入队(放在队尾)
    2,Dequeue()出队(移除队首元素,并返回被移除的元素)
    3,Peek()取得队首的元素,不移除
    4,Clear()清空元素
    属性
    5,Count获取队列中元素的个数

    队列接口定义

    public interface IQueue<T>
        {
            int Count { get; }//取得队列长度的属性
            int GetLength();//求队列的长度
            bool IsEmpty();//判断队列是否为空
            void Clear();//清空队列
            void Enqueue(T item);//入队
            T Dequque();//出队
            T Peek();//取队头元素
        }

    顺序队列

    用一片连续的存储空间来存储队列中的数据元素,这样的队列称为顺序队列(Sequence Queue)。类似于顺序栈,用一维数组来存放顺序队列中的数据元素。队头位置设在数组下标为 0 的端,用 front 表示;队尾位置设在数组的另一端,用 rear 表示。 front 和 rear 随着插入和删除而变化。当队列为空时, front=rear=-1。
    图是顺序队列的两个指示器与队列中数据元素的关系图。

     顺序队列(循环顺序队列)

    如果再有一个数据元素入队就会出现溢出。但事实上队列中并未满,还有空闲空间,把这种现象称为“假溢出”。这是由于队列“队尾入队头出”的操作原则造成的。解决假溢出的方法是将顺序队列看成是首尾相接的循环结构,头尾指示器的关系不变,这种队列叫循环顺序队列(Circular sequence Queue)。循环队列如图所示。

    把循环顺序队列看作是一个泛型类,类名叫 CSeqStack<T>,“ C”是英文单词 circular 的第 1 个字母。 CSeqStack<T>类实现了接口 IQueue<T>。用数组来存储循环顺序队列中的元素,在 CSeqStack<T>类中用字段 data 来表示。用字段maxsize 表示循环顺序队列的容量, maxsize 的值可以根据实际需要修改,这通过CSeqStack<T>类的构造器中的参数 size 来实现,循环顺序队列中的元素由 data[0]开始依次顺序存放。字段 front 表示队头, front 的范围是 0 到 maxsize-1。字段 rear表示队尾,rear 的范围也是 0 到 maxsize-1。如果循环顺序队列为空,front=rear=-1。当执行入队列操作时需要判断循环顺序队列是否已满,如果循环顺序队列已满,(rear + 1) % maxsize==front , 循 环 顺 序 队 列 已 满 不 能 插 入 元 素 。 所 以 ,CSeqStack<T>类除了要实现接口 IQueue<T>中的方法外,还需要实现判断循环顺序队列是否已满的成员方法。

    链队列

    队列的另外一种存储方式是链式存储,这样的队列称为链队列(Linked Queue)。同链栈一样,链队列通常用单链表来表示,它的实现是单链表的简化。所以,链队列的结点的结构与单链表一样,如图所示。由于链队列的操作只是在一端进行,为了操作方便,把队头设在链表的头部,并且不需要头结点。

    链队列结点类

    public class Node<T>
        {
            private T data;//数据域
            private Node<T> next;//引用域
            //构造器
            public Node(T val,Node<T> p)
            {
                data = val;
                next = p;
            }
    
            //构造器
            public Node(Node<T> p)
            {
                next = p;
            }
    
            //构造器
            public Node(T val)
            {
                data = val;
                next = null;
            }
    
            //构造器
            public Node()
            {
                data = default(T);
                next = null;
            }
    
            //数据域属性
            public T Data
            {
                get { return data; }
                set { data = value; }
            }
    
            //引用域属性
            public Node<T> Next
            {
                get { return next; }
                set { next = value; }
            }
        }

    把链队列看作一个泛型类,类名为 LinkQueue<T>。 LinkQueue<T>类中有两个字段 front 和 rear,表示队头指示器和队尾指示器。由于队列只能访问队头的数据元素,而链队列的队头指示器和队尾指示器又不能指示队列的元素个数,所以,与链栈一样,在 LinkQueue<T>类增设一个字段 num 表示链队列中结点的个数。

    栈和队列的应用举例:

    编程判断一个字符串是否是回文。回文是指一个字符序列以中间字符为基准两边字符完全相同,如字符序列“ ACBDEDBCA”是回文。

    算法思想:判断一个字符序列是否是回文,就是把第一个字符与最后一个字符相比较,第二个字符与倒数第二个字符比较,依次类推,第 i 个字符与第 n-i个字符比较。如果每次比较都相等,则为回文,如果某次比较不相等,就不是回文。因此,可以把字符序列分别入队列和栈,然后逐个出队列和出栈并比较出队列的字符和出栈的字符是否相等,若全部相等则该字符序列就是回文,否则就不是回文。

    class Program
        {
            static void Main(string[] args)
            {
                string str = Console.ReadLine();
                Stack<char> stack = new Stack<char>();
                Queue<char> queue = new Queue<char>();
                for(int i=0;i<str.Length;i++)
                {
                    stack.Push(str[i]);
                    queue.Enqueue(str[i]);
                }
                bool isHui = true;
                while(stack.Count>0)
                {
                    if(stack.Pop()!=queue.Dequeue())
                    {
                        isHui = false;
                        break;
                    }
                }
                Console.WriteLine("是否是回文字符串:" + isHui);
                Console.ReadKey();
            }
        }

    四、串

    在应用程序中使用最频繁的类型是字符串。字符串简称串,是一种特殊的线性表,其特殊性在于串中的数据元素是一个个的字符。字符串在计算机的许多方面应用很广。如在汇编和高级语言的编译程序中,源程序和目标程序都是字符串数据。在事务处理程序中,顾客的信息如姓名、地址等及货物的名称、产地和规格等,都被作为字符串来处理。另外,字符串还具有自身的一些特性。因此,把字符串作为一种数据结构来研究。

    串的基本概念

    串(String)由 n(n≥0)字符组成的有限序列。一般记为:
    S=”c1c2…cn” (n≥0)
    其中, S是串名,双引号作为串的定界符,用双引号引起来的字符序列是串值。 ci( 1≤i≤n)可以是字母、数字或其它字符, n为串的长度,当n=0 时,称为空串(Empty String)。
    串中任意个连续的字符组成的子序列称为该串的子串(Substring)。包含子串的串相应地称为主串。子串的第一个字符在主串中的位置叫子串的位置。如串s1”abcdefg”,它的长度是 7,串s2”cdef”的长度是 4, s2是s1的子串, s2的位置是 3。
    如果两个串的长度相等并且对应位置的字符都相等,则称这两个串相等。而在 C#中,比较两个串是否相等还要看串的语言文化等信息。

    串的存储和代码实现

    由于串中的字符都是连续存储的,而在 C#中串具有恒定不变的特性,即字符串一经创建,就不能将其变长、变短或者改变其中任何的字符。所以,这里不讨论串的链式存储,也不用接口来表示串的操作。同样,把串看作是一个类,类名为 StringDS。取名为 StringDS 是为了和 C#自身的字符串类 String 相区别。类StringDS 只有一个字段,即存放串中字符序列的数组 data。由于串的运算有很多,类 StringDS 中只包含部分基本的运算。串类 StringDS中的方法和属性:

    class StringDS
        {
            public char[] data;//用来存放字符串中的字符
    
            public StringDS(char[] array)
            {
                data = new char[array.Length];
                for(int i=0;i<data.Length;i++)
                {
                    data[i] = array[i];
                }
            }
    
            public StringDS(string str)
            {
                data = new char[str.Length];
                for(int i=0;i<data.Length;i++)
                {
                    data[i] = str[i];
                }
            }
    
            //根据索引访问字符的索引器
            public char this[int index]
            {
                get { return data[index]; }
            }
    
            public int GetLength()
            {
                return data.Length;
            }
    
            /// <summary>
            /// 如果两个字符串一样,那么返回0
            /// 如果两个字符串小于s,那么返回-1
            /// 如果两个字符串大于s,那么返回1
            /// </summary>
            /// <param name="s"></param>
            /// <returns></returns>
            public int Compare(StringDS s)
            {
                int len = this.GetLength() < s.GetLength() ? this.GetLength() : s.GetLength();//取得两个字符串中,长度更小的字符串的长度
                int index = -1;
                for(int i=0;i<len;i++)
                {
                    if(this[i]!=s[i])
                    {
                        index = i;
                        break;
                    }
                }
                if(index!=-1)
                {
                    if(this[index]>s[index])
                    {
                        return 1;
                    }
                    else
                    {
                        return -1;
                    }
                }
                else
                {
                    if(this.GetLength()==s.GetLength())
                    {
                        return 0;
                    }
                    else
                    {
                        if(this.GetLength()>s.GetLength())
                        {
                            return 1;
                        }
                        else
                        {
                            return -1;
                        }
                    }
                }
            }
    
            /// <summary>
            /// 截取字符串(从index开始,长度为length的字符串)
            /// </summary>
            /// <param name="index"></param>
            /// <param name="length"></param>
            /// <returns></returns>
            public StringDS SubString(int index,int length)
            {
                char[] newData = new char[length];
                for(int i=index; i<index+length;i++)
                {
                    newData[i - index] = data[i];
                }
                return new StringDS(newData);
            }
    
            /// <summary>
            /// 连接两个字符串
            /// </summary>
            /// <param name="s1"></param>
            /// <param name="s2"></param>
            /// <returns></returns>
            public static StringDS Concat(StringDS s1,StringDS s2)
            {
                char[] newData = new char[s1.GetLength() + s2.GetLength()];
                for(int i=0;i<s1.GetLength();i++)
                {
                    newData[i] = s1[i];
                }
                for(int i=s1.GetLength();i<newData.Length;i++)
                {
                    newData[i] = s2[i - s1.GetLength()];
                }
                return new StringDS(newData);
            }
    
            /// <summary>
            /// 用于返回某个指定字符串值在字符串中首次出现的位置
            /// </summary>
            /// <param name="s"></param>
            /// <returns></returns>
            public int IndexOf(StringDS s)
            {
                for(int i=0;i<=this.GetLength()-s.GetLength();i++)
                {
                    bool isEqual = true;
                    for(int j=i;j<i+s.GetLength();j++)
                    {
                        if(this[j]!=s[j-i])
                        {
                            isEqual = false;
                        }
                    }
                    if(isEqual)
                    {
                        return i;
                    }
                    else
                    {
                        continue;
                    }
                }
                return -1;
            }
        }

    C#中的串

    在 C#中,一个 String 表示一个恒定不变的字符序列集合。 String 类型是封闭类型,所以,它不能被其它类继承,而它直接继承自 object。因此, String 是引用类型,不是值类型,在托管堆上而不是在线程的堆栈上分配空间。 String 类型还继承了 IComparable 、 ICloneable 、 IConvertible 、 IComparable<string> 、IEnumerable<char>、 IEnumerable 和 IEquatable<string>等接口。 String 的恒定性指的是一个串一旦被创建,就不能将其变长、变短或者改变其中任何的字符。所以,当我们对一个串进行操作时,不能改变字符串,如在本书定义的 StringDS 类中,串连接、串插入和串删除等操作的结果都是生成了新串而没有改变原串。 C#也提供了 StringBuilder 类型来支持高效地动态创建字符串。
    在 C#中,创建串不能用 new 操作符,而是使用一种称为字符串驻留的机制。

    这是因为 C#语言将 String 看作是基元类型。基元类型是被编译器直接支持的类型,可以在源代码中用文本常量(Literal)来直接表达字符串。当 C#编译器对源代码进行编译时,将文本常量字符串存放在托管模块的元数据中。而当 CLR 初始化时, CLR 创建一个空的散列表,其中的键是字符串,值为指向托管堆中字符串对象的引用。散列表就是哈希表。当 JIT编译器编译方法时,它会在散列表中查找每一个文本常量字符串。如果找不到,就会在托管堆中构造一个新的 String 对象(指向字符串),然后将该字符串和指向该字符串对象的引用添加到散列表中;如果找到了,不会执行任何操作。

    C#中的数组

    数组是一种常用的数据结构,可以看作是线性表的推广。数组作为一种数据结构,其特点是结构中的数据元素可以是具有某种结构的数据,甚至可以是数组,但属于同一数据类型。数组在许多高级语言里面都被作为固定类型来使用。
    数组是 n(n≥1)个相同数据类型的数据元素的有限序列。一维数组可以看作是一个线性表,二维数组可以看作是“数据元素是一维数组”的一维数组,三维数组可以看作是“数据元素是二维数组”的一维数组,依次类推。
    C#支持一维数组、多维数组及交错数组(数组的数组)。所有的数组类型都隐含继承自 System.Array。Array 是一个抽象类,本身又继承自 System.Object。所以,数组总是在托管堆上分配空间,是引用类型。任何数组变量包含的是一个指向数组的引用,而非数组本身。当数组中的元素的值类型时,该类型所需的内存空间也作为数组的一部分而分配;当数组的元素是引用类型时,数组包含是只是引用。

    Array类中的常用方法

    public abstract class Array : ICloneable, IList, ICollection, IEnumerable
        {
            //判断Array是否具有固定大小
            public bool IsFixedSize { get; }
            //获取Array元素的个数
            public int Length { get;}
            //获取Array的秩(维数)
            public int Rank { get; }
            //实现IComparable接口,在Array中搜索特定元素
            public static int BinarySearch(Array array, object value);
            //实现IComparable<T> 泛型接口,在Array中搜索特定元素
            public static int BinarySearch<T>(T[] array, T value);
            //实现IComparable接口,在Array某个范围中搜索值
            public static int BinarySearch(Array array, int index, int length, Object value);
            //实现IComparable<T>泛型接口,在Array中搜索值
            public static int BinarySearch<T>(T[] array, int index, int length, T value);
            //Array设置为零、false或null,具体取决于元素类型
            public static void Clear(Array array, int index, int length);
            //System.Array的浅表副本
            public object Clone();
            //从第一个元素开始复制Array中的一系列元素 到另一个Array中(从第一个元素开始)
            public static void Copy(Array sourceArray, Array destinationArray, int length);
            //将一维Array的所有元素复制到指定的一维Array中
            public void CopyTo(Array array, int index);
            //创建使用从零开始的索引、具有指定Type和维长的多维Array
            public static Array CreateInstance(Type elementType, params int[] lengths);
            //返回ArrayIEnumerator
            public IEnumerator GetEnumerator();
            //获取Array指定维中的元素数
            public int GetLength(int dimension);
            //获取一维Array中指定位置的值
            public object GetValue(int index);
            //返回整个一维Array中的第一个匹配项的索引
            public static int IndexOf(Array array, object value);
            //返回整个Array中第一个匹配项的索引
            public static int LastIndexOf(Array array, object value);
            //反转整个一维Array中最后一个匹配项的索引
            public static void Reverse(Array array);
            //设置给一维Array中指定位置的元素
            public void SetValue(object value, int index);
            //对整个一维Array中的元素进行排序
            public static void Sort(Array array);
        }

    练习题:

    1. 设 s=”I am a teacher”,i=”excellent”,r=”student”。用 StringDS类中的方法求:
    ( 1) 串 s、i、r 的长度;
    ( 2) s.SubString(8, 4)、i.SubString(2, 1);
    ( 3) s.IndexOf(“tea”)、i.IndexOf(“cell”)、r.IndexOf(“den”)。

    class Program
        {
            static void Main(string[] args)
            {
                StringDS s = new StringDS("I am a teacher");
                StringDS i = new StringDS("excellent");
                StringDS r = new StringDS("student");
                Console.WriteLine(s.GetLength());
                Console.WriteLine(i.GetLength());
                Console.WriteLine(r.GetLength());
    
                StringDS s2 = s.SubString(8, 4);
                StringDS i2 = i.SubString(2, 1);
                Console.WriteLine(s2.ToString());
                Console.WriteLine(i2.ToString());
    
                Console.WriteLine(s.IndexOf(new StringDS("tea")));
                Console.WriteLine(i.IndexOf(new StringDS("cell")));
                Console.WriteLine(r.IndexOf(new StringDS("den")));
                Console.ReadKey();
            }
        }

    2. 串的替换操作是指:已知串 s、t、r,用 r 替换 s 中出现的所有与 t 相等的子串。写出算法,方法名为 Replace。

    /// <summary>
            /// 串的替换操作
            /// </summary>
            /// <param name="s"></param>
            /// <param name="t"></param>
            /// <param name="r"></param>
            /// <returns></returns>
            public StringDS Replace(StringDS s,StringDS t,StringDS r)
            {
                int temp = s.IndexOf(t);//查找t字符串在s中的位置
                if(temp!=-1)//如果 s中有与t相同的子串
                {
                    StringDS s1 = s.SubString(0, temp);//字符串s前半部分(t之前)
                    StringDS s2 = s.SubString(temp + t.GetLength(), s.GetLength() - (temp + t.GetLength())); //字符串s后半部分(t之后)
                    s1 = s1.Concat(s1, r);
                    s1 = s1.Concat(s1, s2);
                    return s1.Replace(s1, t, r);
                }
                return s;
            }

    验证结果:

    StringDS s = new StringDS("I am a teacher");
                StringDS t = new StringDS("a1");
                StringDS r = new StringDS("*");
                StringDS temp = new StringDS("");
                temp = temp.Replace(s, t, r);
                Console.WriteLine(temp.ToString());
                Console.ReadKey();

    3. 已知下列字符串:
    a=”THIS”,f=”A SMPLE” c=”GOOD”,d=”NE”,b=”︼”,g=”IS”,
    s=a.Concat(b.Concat(a.SubString(3,2)).(f.SubString(2,7))),
    t=f.Replace(f.SubString(3,6),c),
    u=c.SubString(3,1).Concat(d),
    v=s.Concat(b.Concat(t.ConCat(b.Concat(u))))。
    问 s,t,v,GetLength(s),v.IndexOf(g),u.IndexOf(g)各是什么。

    4. 设已知两个串为:
    S1=”bc cad cabcadf”,S2=”abc”。试求两个串的长度,并判断 S2 串是否是 S1 串的子串,如果 S2 是 S1 的子串,指出 S2 在 S1 中的起始位置。

    5. 已知:s=”(XYZ)+*”,t=”(X+Z)*Y”,试利用连接、求子串和替换等基本运算,将 s 转化为 t。

    五、简单排序方法

    排序

    排序(Sort)是计算机程序设计中的一种重要操作,也是日常生活中经常遇到的问题。例如,字典中的单词是以字母的顺序排列,否则,使用起来非常困难。同样,存储在计算机中的数据的次序,对于处理这些数据的算法的速度和简便性而言,也具有非常深远的意义。

    基本概念

    排序是把一个记录(在排序中把数据元素称为记录)集合或序列重新排列成按记录的某个数据项值递增(或递减)的序列。
    下表是一个学生成绩表,其中某个学生记录包括学号、姓名及计算机文化基础、C 语言、数据结构等课程的成绩和总成绩等数据项。在排序时,如果用总成绩来排序,则会得到一个有序序列;如果以数据结构成绩进行排序,则会得到另一个有序序列。

    作为排序依据的数据项称为“排序项”,也称为记录的关键码(Keyword)。关键码分为主关键码(Primary Keyword)和次关键码(Secondary Keyword)。一般地,若关键码是主关键码,则对于任意待排序的序列,经排序后得到的结果是唯一的;若关键码是次关键码,排序的结果不一定唯一,这是因为待排序的序列中可能存在具有相同关键码值的记录。此时,这些记录在排序结果中,它们之间的位置关系与排序前不一定保持一致。如果使用某个排序方法对任意的记录序列按关键码进行排序,相同关键码值的记录之间的位置关系与排序前一致,则称此排序方法是稳定的;如果不一致,则称此排序方法是不稳定的。
    由于待排序的记录的数量不同,使得排序过程中涉及的存储器不同,可将排序方法分为内部排序(Internal Sorting)和外部排序(External Sorting)两大类。
    内部排序指的是在排序的整个过程中,记录全部存放在计算机的内存中,并且在内存中调整记录之间的相对位置,在此期间没有进行内、外存的数据交换。外部排序指的是在排序过程中,记录的主要部分存放在外存中,借助于内存逐步调整记录之间的相对位置。在这个过程中,需要不断地在内、外存之间交换数据。

    直接插入排序

    插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中。
    插入排序的基本思想是:每步将一个待排序的纪录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。

     冒泡排序

    冒泡排序(Bubble Sort)的基本思想是:将相邻的记录的关键码进行比较,若前面记录的关键码大于后面记录的关键码,则将它们交换,否则不交换。

     简单选择排序

    简单选择排序(Simple Select Sort)算法的基本思想是:从待排序的记录序列中选择关键码最小(或最大)的记录并将它与序列中的第一个记录交换位置;然后从不包括第一个位置上的记录序列中选择关键码最小(或最大)的记录并将它与序列中的第二个记录交换位置;如此重复,直到序列中只剩下一个记录为止。

    class Program
        {
            static void Main(string[] args)
            {
                int[] data = new int[] { 42, 20, 17, 27, 13, 8, 17, 48 };
                SelectSort(data);
                foreach(var temp in data)
                {
                    Console.Write(temp + " ");
                }    
                Console.ReadKey();
            }
    
            static void SelectSort(int[] dataArray)
            {
                for (int i = 0; i < dataArray.Length - 1; i++)
                {
                    int min = dataArray[i];
                    int minIndex = i;//最小值所在索引
                    for (int j = i + 1; j < dataArray.Length; j++)
                    {
                        if (dataArray[j] < min)
                        {
                            min = dataArray[j];
                            minIndex = j;
                        }
                    }
                    if (minIndex != i)
                    {
                        int temp = dataArray[i];
                        dataArray[i] = dataArray[minIndex];
                        dataArray[minIndex] = temp;
                    }
                }
            }
        }

     六、快速排序

    快速排序由于排序效率综合来说在这几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试,包括像腾讯,微软等知名IT公司都喜欢考这个,还有大大小小的程序方面的考试如软考,考研中也常常出现快速排序的身影。
    快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。

    该方法的基本思想是:
    1.先从数列中取出一个数作为基准数。
    2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
    3.再对左右区间重复第二步,直到各区间只有一个数。

    详细步骤

    以一个数组作为示例,取区间第一个数为基准数。

    初始时,i = 0;  j = 9;   X = a[i] = 72
    由于已经将a[0]中的数保存到X中,可以理解成在数组a[0]上挖了个坑,可以将其它数据填充到这来。
    从j开始向前找一个比X小或等于X的数。当j=8,符合条件,将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++;  这样一个坑a[0]就被搞定了,但又形成了一个新坑a[8],这怎么办了?简单,再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数,当i=3,符合条件,将a[3]挖出再填到上一个坑中a[8]=a[3]; j--;
    数组变为:

     

    i = 3;   j = 7;   X=72
    再重复上面的步骤,先从后向前找,再从前向后找。
    从j开始向前找,当j=5,符合条件,将a[5]挖出填到上一个坑中,a[3] = a[5]; i++
    从i开始向后找,当i=5时,由于i==j退出。
    此时,i = j = 5,而a[5]刚好又是上次挖的坑,因此将X填入a[5]。
    数组变为:

    可以看出a[5]前面的数字都小于它,a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。

    快速排序代码实现

    class Program
        {
            static void Main(string[] args)
            {
                int[] data = new int[] { 42, 20, 17, 27, 13, 8, 17, 48 };
                QuickSort(data,0,data.Length-1);
                foreach(var temp in data)
                {
                    Console.Write(temp + " ");
                }    
                Console.ReadKey();
            }
    
            static void QuickSort(int[] dataArray,int left,int right)
            {
                if(left<right)
                {
                    int x = dataArray[left];//基准数,把比它小或者等于它的 放在它的左边,然后把比它大的放在它的右边
                    int i = left;
                    int j = right;//用来做循环的标志位
    
                    //当i==j的时候,说明我们找到了一个中间位置,这个中间位置就是基准数应该所在的位置
                    while(true&&i<j)
                    {
                        //从后往前比较(从右向左比较)找一个比x小(或者=)的数字,放在我们的坑里 坑位于i的位置
                        while (true && i < j)
                        {
                            //找到一个比基准数 小于或者等于的数字,应该把它放在x的左边
                            if (dataArray[j] <= x)
                            {
                                dataArray[i] = dataArray[j];
                                break;
                            }
                            else
                            {
                                j--;//向左移动 到下一个数字,然后做比较
                            }
                        }
    
                        //从前往后(从左向右)找一个比x大的数字,放在我们的坑里面,现在的坑位于j的位置
                        while(true&&i<j)
                        {
                            if(dataArray[i]>x)
                            {
                                dataArray[j] = dataArray[i];
                                break;
                            }
                            else
                            {
                                i++;
                            }
                        }
                    }
                    //跳出循环 现在i=j i是中间位置
                    dataArray[i] = x;
                    QuickSort(dataArray, left, i - 1);
                    QuickSort(dataArray, i + 1, right);
                }
            }
        }

    快排总结

    1.  i =L; j = R; 将基准数挖出形成第一个坑a[i];

    2.j--由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中;

    3.  i++由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中;

    4.再重复执行2,3二步,直到i==j,将基准数填入a[i]中。

    七、算法简介

    算法的作用

    算法解决了哪些问题?
    互联网信息的访问检测,海量数据的管理;
    在一个交通图中,寻找最近的路;
    人类基因工程,dna有10万个基因,处理这些基因序列需要复杂的算法支持......

    上面的算法是我们没有接触到,或者是封装到底层的东西,那么作为程序员,在日常编码过程中会在什么地方使用算法呢?
    在你利用代码去编写程序,去解决问题的时候,其实这些编码过程都可以总结成一个算法,只是有些算法看起来比较普遍比较一般,偶尔我们也会涉及一些复杂的算法比如一些AI。
    大多数我们都会利用已有的思路(算法)去开发游戏!

    学习算法的好处

    学习算法就像是去理解编程

    可以让我们平时的编码过程变得更加通畅

    并且会提高我们解决程序问题的能力

    所以称之为内功修炼。

    八、分治算法

    分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

    可使用分治法求解的一些经典问题:
    (1)二分搜索
    (2)大整数乘法
    (3)Strassen矩阵乘法
    (4)棋盘覆盖
    (5)合并排序
    (6)快速排序
    (7)线性时间选择
    (8)最接近点对问题
    (9)循环赛日程表
    (10)汉诺塔

    eg:股票问题

    天数

    0

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    价格

    100

    113

    110

    85

    105

    102

    86

    63

    81

    101

    94

    106

    101

    79

    94

    90

    97

    变化

    13

    -3

    -25

    20

    -3

    -16

    -23

    18

    20

    -7

    12

    -5

    -22

    15

    -4

    7

     方法一:暴力求解法

    class Program
        {
            static void Main(string[] args)
            {
                //暴力求解法
                int[] priceArray = { 100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97 };//股价数组
                int[] priceFluctuationArray = new int[priceArray.Length - 1];//股价波动数组
                for(int i=1;i<priceArray.Length;i++)
                {
                    priceFluctuationArray[i - 1] = priceArray[i] - priceArray[i - 1];
                }
                int total = priceFluctuationArray[0];//默认数组的第一个元素是最大子数组
                int startIndex = 0;
                int endIndex = 0;
                for(int i=0;i<priceFluctuationArray.Length;i++)
                {
                    //取得以i为 子数组起点 的 所有子数组
                    for(int j=i;j<priceFluctuationArray.Length;j++)
                    {
                        //由i j 就确定了一个子数组
                        int totalTemp = 0;//临时 最大子数组的和
                        for(int index=i;index<j+1;index++)
                        {
                            totalTemp += priceFluctuationArray[index];
                        }
                        if(totalTemp>total)
                        {
                            total = totalTemp;
                            startIndex = i;
                            endIndex = j;
                        }
                    }
                }
                Console.WriteLine("股票最佳购买日是第" + startIndex + "天,最佳出售日是第" + (endIndex + 1)+"天");
                Console.ReadKey();
            }
        }

    方法二:分治法

    class Program
        {
            //最大子数组的结构体
            struct SubArray
            {
                public int startIndex;
                public int endIndex;
                public int total;
            }
    
            /// <summary>
            /// 用来取得从low到high之间的最大子数组
            /// </summary>
            /// <param name="low"></param>
            /// <param name="high"></param>
            /// <param name="array"></param>
            /// <returns></returns>
            static SubArray GetMaxSubArray(int low, int high, int[] array)
            {
                if(low==high)
                {
                    SubArray subarray;
                    subarray.startIndex = low;
                    subarray.endIndex = high;
                    subarray.total = array[low];
                    return subarray;
                }
                int mid = (low + high) / 2;//低区间[low,mid]  高区间[mid=1,high]
                SubArray subArray1 = GetMaxSubArray(low, mid, array);
                SubArray subArray2 = GetMaxSubArray(mid + 1, high, array);
    
                //从[low,mid]中找到最大子数组[i,mid]
                int total1 = array[mid];
                int startIndex = mid;
                int totalTemp = 0;
                for(int i=mid;i>=low;i--)
                {
                    totalTemp += array[i];
                    if(totalTemp>total1)
                    {
                        total1 = totalTemp;
                        startIndex = i;
                    }
                }
    
                //从[mid+1,high]中找到最大子数组[mid+1,j]
                int total2 = array[mid + 1];
                int endIndex = mid + 1;
                totalTemp = 0;
                for(int j=mid+1;j<=high;j++)
                {
                    totalTemp += array[j];
                    if(totalTemp>total2)
                    {
                        total2 = totalTemp;
                        endIndex = j;
                    }
                }
    
                SubArray subArray3;
                subArray3.startIndex = startIndex;
                subArray3.endIndex = endIndex;
                subArray3.total = total1 + total2;
                if(subArray1.total>=subArray2.total&&subArray1.total>=subArray3.total)
                {
                    return subArray1;
                }
                else if(subArray2.total>=subArray1.total&&subArray2.total>=subArray3.total)
                {
                    return subArray2;
                }
                else
                {
                    return subArray3;
                }
            }
    
            static void Main(string[] args)
            {
                //分治法
                int[] priceArray = { 100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97 };//股价数组
                int[] priceFluctuationArray = new int[priceArray.Length - 1];//股价波动数组
                for(int i=1;i<priceArray.Length;i++)
                {
                    priceFluctuationArray[i - 1] = priceArray[i] - priceArray[i - 1];
                }
    
                SubArray subArray = GetMaxSubArray(0, priceFluctuationArray.Length - 1, priceFluctuationArray);
                Console.WriteLine("股票最佳购买日是第" + subArray.startIndex + "天,最佳出售日是第" + (subArray.endIndex + 1)+"天");
                Console.ReadKey();
            }
        }

    九、树

    1.空树;

    2.只有一个根节点的树;

    3.

     什么是子树?什么是父子结点?什么是根节点?什么是度?(拥有子树的个数称为结点的度)

    结点关系:孩子,兄弟。

    什么是树的层次?

    最大层是树的深度

    什么是有序树和无序树?

    树的错误案例:

    1.树只有一个根节点;

    2.子树之间是不相交的;

    3.一个结点不能有两个父结点。

    树的存储结构

    存储结构一般是 顺序存储和链式存储。

    树的关系复杂 使用链式存储
    1.双亲表示法

     2.孩子表示法

    3.孩子兄弟表示法

     

     二叉树

    什么是二叉树?

     

    1.空二叉树

    2.只有根结点

    3.大于一个结点

    什么是左右子树?

    特殊二叉树

    1.斜树(左斜树,右斜树)

    2.满二叉树

    3.完全二叉树

     

    4.非完全二叉树

     二叉树的性质

     二叉树的存储结构

    一般的树,是一对多的关系,使用顺序结构存储起来比较困难,但是二叉树是一种特殊的树,每个结点最多有两个子节点,并且子节点有左右之分,并且兄弟,父亲,孩子可以很方便的通过编号得到,所以我们使用顺序存储结构使用二叉树的存储。

    二叉树存储 类型1:

     二叉树存储 类型2:

     

    二叉树存储 类型3:

     注意:顺序存储一般只用于完全二叉树。

     二叉树 二叉链表存储

    二叉树每个结点最多有两个孩子,所以为它设计一个数据域和两个指针域,我们称这样的链表为二叉链表。

     

     二叉树的遍历

    二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中的所有结点,使得每个结点被访问一次且仅被访问一次。

    1.前序遍历

    先输出当前结点的数据,再依次遍历输出左结点和右结点。

    2.中序遍历

    先遍历输出左结点,再输出当前结点的数据,再遍历输出右结点。

    3.后序遍历

    先遍历输出左结点,再遍历输出右结点,最后输出当前结点的数据。

    4.层序遍历

    从树的第一层开始,从上到下逐层遍历,在同一层中,从左到右对结点 逐个访问输出

     

    class BiTree<T>
        {
            private T[] data;
            private int count = 0; //数量count代表当前保存了多少个数据
    
            public BiTree(int capacity)//这个参数是当前二叉树的容量,容量就是最多可以存储的数据个数
            {
                data = new T[capacity];
            }
    
            public bool Add(T item)
            {
                if (count >= data.Length)
                    return false;
                data[count] = item;
                count++;
                return true;
            }
    
            public void Traversal()
            {
                FirstTraversal(0);
                Console.WriteLine("\n");
                MiddleTraversal(0);
                Console.WriteLine("\n");
                LastTraversal(0); 
                Console.WriteLine("\n");
                LayerTraversal();
            }
    
            /// <summary>
            /// 1.前序遍历
            /// </summary>
            /// <param name="index"></param>
            private void FirstTraversal(int index)
            {
                if (index >= count) return;
                //得到要遍历的这个结点的编号
                int number = index + 1;
                if (data[index].Equals(-1)) return;
                Console.Write(data[index] + " ");
                //得到左子结点的编号
                int leftNumber = number * 2;
                int rightNumber = number * 2 + 1;
                FirstTraversal(leftNumber - 1);
                FirstTraversal(rightNumber - 1);
            }
    
            /// <summary>
            /// 2.中序遍历
            /// </summary>
            /// <param name="index"></param>
            private void MiddleTraversal(int index)
            {
                if (index >= count) return;
                //得到要遍历的这个结点的编号
                int number = index + 1;
                if (data[index].Equals(-1)) return;
                //得到左子结点的编号
                int leftNumber = number * 2;
                int rightNumber = number * 2 + 1;
                MiddleTraversal(leftNumber - 1);
                Console.Write(data[index] + " ");
                MiddleTraversal(rightNumber - 1);
            }
    
            /// <summary>
            /// 3.后序遍历
            /// </summary>
            /// <param name="index"></param>
            private void LastTraversal(int index)
            {
                if (index >= count) return;
                //得到要遍历的这个结点的编号
                int number = index + 1;
                if (data[index].Equals(-1)) return;
                //得到左子结点的编号
                int leftNumber = number * 2;
                int rightNumber = number * 2 + 1;
                LastTraversal(leftNumber - 1);
                LastTraversal(rightNumber - 1);
                Console.Write(data[index] + " ");
            }
    
            /// <summary>
            /// 4.层序遍历
            /// </summary>
            private void LayerTraversal()
            {
                for(int i=0;i<count;i++)
                {
                    if (data[i].Equals(-1)) continue;
                    Console.Write(data[i] + " ");
                }
                Console.WriteLine();
            }
        }
    
        class Program
        {
            static void Main(string[] args)
            {
                char[] data = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J' };//这个是我们要存储的数据
                BiTree<char> tree = new BiTree<char>(10);
                for (int i = 0; i < data.Length; i++)
                {
                    tree.Add(data[i]);
                }
                tree.Traversal();
                Console.ReadKey();
            }
        }

    展开全文
  • 目录1 基本概念2 算法分析2.1 算法设计的要求2.2 算法效率的度量——大O记法3 Python结构的性能3.1 列表3.2 字典 1 基本概念 数据结构 相互之间存在一种或多种特定关系的数据元素的集合。通常有四类基本结构:集合、...
  • 第 PAGE 1 页 共 NUMPAGES 10 页 选择题每小题2分共30分 1以下函数的时间复杂度为 int Rsum ( int a[], int n ) { if... } AO(1) BO(n2)CO(n) DO(nlog2n) 2下列不属于顺序存储结构特点的是 A可对元素进行随机访问 B非表
  • 数据结构算法选择题宣贯.pdf
  • 数据结构算法的描述和分析

    千次阅读 2018-08-17 19:25:49
    数据结构概论 高级语言程序设计在解决某一实际问题的一般步骤是:分析实际问题、确定数学模型、设计或选择一个求解此数学模型的算法、编写程序进行调试和测试解决问题等几个步骤。 例1:已知:游泳池的长length和...
  • 数据结构算法知识总结(一)

    千次阅读 2020-04-24 17:15:07
    下面是对学习数据结构与算法一些基础知识总结,主要讲解...数据结构是指相互之间存在一种或者多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效果。数据结构往往同高效的...
  • 数据结构算法课后题整理(一)

    千次阅读 2021-04-05 21:17:25
    数据结构与算法1课后题整理第一章什么是数据结构、算法结构与设计功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容...
  • 最小生成树(Prim算法、Kruskal算法) 生成树的定义: 生成树是一个连通图G的一个极小连通子图。 包含G的所有n个顶点,但只有n-1条边,并且是连通的。 生成树可由遍历过程中所经过的边组成(有多个)。 最小生成树的...
  • Python数据结构&...简单来说,数据结构是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间的关系和操作的学科。 1.1.1 基本概念及术语 【数据】是对客观事物的符号表示,在计算机科学
  • 数据结构算法习题库

    万次阅读 多人点赞 2018-12-26 21:24:55
    第一章 绪论 一.选择题 1.数据结构被形式地定义为(K,R),其中K是①_B_的有限集合,R是K上的②_D_的有限集合。...2.算法分析的目的是①C,算法分析的两个主要方面是②A。  ①A.找出数据结构的合理性 ...
  • 数据结构算法常见笔试题

    万次阅读 多人点赞 2017-09-10 11:03:57
    1.数据结构算法常见笔试题   第一章 数据结构算法 一.算法的基本概念 计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。 1.算法的基本特征:可行性,确定性,有穷性,拥有足够的情报。 2....
  • 算法导论03】贪心算法-prim算法

    千次阅读 2020-07-27 21:18:59
    接下来来了解一下最小生成树的最优子结构性质:假设一个无向图包含两部分A,B,其中A为最小生成树部分,B为剩余部分,则存在以下性质:该无向图中一个顶点在A部分,另一个顶点在B部分的边中,权值最小的边一定属于...
  • 稳定排序算法有哪些

    万次阅读 2020-10-03 09:09:56
    我们知道堆的结构是节点i的孩子为 2*i 和 2*i+1 节点,大顶堆要求父节点大于等于其 2 个子节点,小顶堆要求父节点小于等于其 2 个子节点。 在一个长为 n 的序列,堆排序的过程是从第 n/2 开始和其子节点共 3 个值...
  • 数据结构–七大查找算法总结

    万次阅读 多人点赞 2018-08-06 17:13:43
    转 数据结构–七大查找算法总结 2017年08月15日 21:06:17 阅读数:10610 ...
  • 数据结构中各种排序算法的稳定性比较

    万次阅读 多人点赞 2018-07-05 16:27:46
    1.简单选择排序 2.堆排序&nbsp;&nbsp;&nbsp;&nbsp;&... (1和2是属于选择排序) 3.直接插入排序 4.... (3和4属于插入排序,有时把改进后的直接插入排序叫做二分插入) 5.冒泡排序&nbs...
  • 高中信息技术《Python语言》模块试卷本试卷分为五大题,37小题,共100分,考试用时60分钟。一、单选题(本题共15小题,每小题2分,共30分)是一门( )(A)自然语言(B)汇编语言(C)高级语言(D)机器语言中...下列不可以作...
  • 数据结构算法基础(软件设计师备考笔记)

    千次阅读 多人点赞 2021-02-27 22:00:01
    数据结构算法基础(重点) 第一节.数组及稀疏矩阵 第二节.数据结构的定义及线性表的概念 第三节.顺序存储与链式存储的比较 第四节.线性表——队列与栈 第五节.广义表 第六节.非线性结构——树与二叉树(import)...
  • 第一类:小于60分,及格,学生概率为5%; 第二类:大于等于60分,但小于70分,及格,学生概率为15%; 第三类:大于等于70分,但小于80分,中等,学生概率为40%; 第四类:大于等于80分,但小于90分,良好,学生...
  • “循环链表”中的“链表”是存储结构的概念, 是指 要求逻辑上相邻的结点在物理上也相邻,结点间的逻辑关系是由附加的指针字段表示的。 综上 ,循环链表也是链表的一种,链表满足线性表的条件,所以循环链表自然...
  • 1算法及其描述(2-3) 一、 选择题1 下面关于算法的描述,正确的是A1 算法及其描述(2‐3)一、 选择题1. 下面关于算法的描述, 正确的是A.一个算法只能有一个输入B.算法只能用框图来表示C.一个算法的执行步骤可以是无限...
  • RSA算法:p=23,q=29,加密指数e=13,对明文 M=123456,计算用RSA加密得到的密文为( )。 A. 151 B. 264 C. 396 D. 418 【答案】C 【解析】n = p × q = 23 × 29 = 667,公钥 (n,e) = (667,13),得到密文 C = Me ...
  • 五大常用算法(二) - 动态规划算法

    千次阅读 2018-10-16 16:49:12
    动态规划算法 基本思想 动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。 动态规划算法与分治法类似,其基本思想也是...
  • 国密算法

    千次阅读 2018-11-14 16:24:33
    国际算法由美国的安全局发布,是现今最通用的商用算法。今天就以分组密码算法(SM4)、公钥密码算法(SM2)、摘要算法(SM3)为例,和大家谈谈国米算法。 #分组密码算法——国产SM4 分组密码就是将明文数据按固定长度进行...
  • C++ 数据结构算法

    千次阅读 2018-02-05 06:47:43
    集合结构,集合结构中的数据元素除了同属于一个集合外,他们之间没有其他不三不四的关系。 线性结构,线性结构中的数据元素之间是一对一的关系。 树形结构,树形结构中,数据元素之间存在一种一对多的层次关系。 ...
  • 数据结构算法(较全)

    千次阅读 2019-08-11 20:14:32
    数据结构是以某种形式将数据组织在一起的集合,它不仅存储数据,还支持访问和处理数据的操作。 算法是为求解一个问题需要遵循的、被清楚指定的简单指令的集合 线性表 线性表是最常用且最简单的一种数据结构,它是n...
  • 程序设计 = 数据结构 + 算法。 1.2 概念 数据 = 符号 (1). 其可以输入到计算机中。 (2). 能够被计算机识别和处理。 1.3 分类 数据分为: (1).数据元素:数据的基本单位,也称为结点或者记录。 (2).数据对象: 相同...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 43,667
精华内容 17,466
关键字:

下列不属于算法结构的是