抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

二分查找算法

只能对有序排列数据进行高效查找。

方法

定义下标：头l，尾r，中位数mid。

集合

集合(set)作为存储数据容器时：

  • 它不允许存储相同元素，只能保留一份。
  • 能快速帮助我们进行去重操作，过滤掉重复元素。

典型应用

词汇量统计

统计一篇英文文章的总单词数，使用集合进行去重，判断英文文章难度。

队列(Queue)

数组实现队列

队列相关操作

void Enqueue(T t);//入队

T Dequeue();//出队

T Peek();//查看队首元素

int Count { get; }//查看元素个数

bool IsEmpty { get; }//查看队列是否为空

数组栈、链表栈以及c#系统提供的Stack性能比对

代码如下

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace AlgorithmTest09_实现栈Stack
{
    class Program
    {
        public static long TextStack(IStack<int> stack, int N)
        {
            Stopwatch t = new Stopwatch();
            t.Start();
            for (int i = 0; i < N; i++)
            {
                stack.Push(i);
            }
            for (int i = 0; i < N; i++)
            {
                stack.Pop();
            }
            t.Stop();
            return t.ElapsedMilliseconds;
        }
        static void Main(string[] args)
        {
            #region 测试性能
            //数组栈
            int N = 10000000;
            Array1Stack<int> array1Stack = new Array1Stack<int>(N);
            long t1 = TextStack(array1Stack, N);
            Console.WriteLine("array1Stack'Time:{0}ms", t1);

            //链表栈
            LinkedList1Stack<int> linked = new LinkedList1Stack<int>();
            long t2 = TextStack(linked, N);
            Console.WriteLine("linked'Time:{0}ms", t2);

            //c#自带的stack
            Stack<int> stack = new Stack<int>();
            Stopwatch t3 = new Stopwatch();
            t3.Start();
            for (int i = 0; i < N; i++)
            {
                stack.Push(i);
            }
            for (int i = 0; i < N; i++)
            {
                stack.Pop();
            }
            t3.Stop();
            Console.WriteLine("stack'Time:{0}ms", t3.ElapsedMilliseconds);
            #endregion
            Console.ReadKey();
        }
    }
}

打印结果

影响程序运行的总时间主要和两点有关

  • 执行每条语句的耗时

  • 执行每条语句的频率

前者主要取决于计算机性能、编译器、操作系统；

后者主要取决于程序本身和输入。

什么是链表

链表由若干节点构成,节点之间有链接,链接末尾没有节点,指向空null.

image-20221025134229495

链表的实现需要定义:

顺序表

image-20221025134433697

定义接口

namespace AlgorithmTest06_List
{
    interface IListDS<T>
    {
        int GetLength();//求长度

        void Chear();//清空

        bool IsEmpty();//判断线性表是否为空

        T Add(T item);//添加

        void Insert(int index, T item);//插入

        T Delete(int i);//删除

        T this[int i] { get; }//定义索引器 获取元素

        T GetElem(int i);//取表元

        T Set(int i, T item);//修改

        int IndexOf(T value);//按值查找

        void Remove(T value);//根据值删除
    }
}

栈(Stack)

栈中元素是从上到下加入的，即“后进先出”

栈的应用

十进制转二进制

枚举算法

image-20221025135058941

打印结果:

image-20221025135114001

递推算法

有一只大兔子，一个月生一只小兔子，过一个月小兔子变大兔子。以此求第几个月，有几个大兔子。

namespace AlgorithmTest
{
    class Program
    {
        static void Main(string[] args)
        {
            //费波拉契数列，一个数等于前两个数之和。
            //根据输入数，展示到这个数之前的所有数。
            Console.WriteLine("请输入一个0~21之间的数");
            int i = int.Parse(Console.ReadLine());
            int[] array = new int[20];//定义有20个空的数组
            array[0] = 1;
            array[1] = 1;
            if (i == 1)
            {
                Console.WriteLine(array[0]);
            }
            else if (i == 2)
            {
                Console.WriteLine(array[0]);
                Console.WriteLine(array[1]);
            }
            else if (i >= 3 && i < 21)
            {
                Console.WriteLine(array[0]);
                Console.WriteLine(array[1]);
                for (int j = 3; j <= i; j++)
                {
                    array[j - 1] = array[j - 2] + array[j - 3];
                    Console.WriteLine(array[j - 1]);
                }
            }
            else
            {
                Console.WriteLine("数字超过范围");
            }
            Console.ReadKey();
        }
    }
}

打印结果：


1 / 2