数据结构、算法及线性表总结

一、思维导图

数据结构、算法及线性表总结

 二、重要概念

1.算法分析:

  1.时间复杂度分析:T(n)与函数规模大小相关。

  2.空间复杂度分析:与临时变量所占空间有关。

  3.递归算法时间与空间复杂度:都应该写出递推式,通过求解递推式来获得时间复杂度和空间复杂度。

2.线性表:

   1.顺序表:有随机存取特性,但其算法时间主要花费在删除和插入元素时元素移动上。

   2.链表:不需要移动元素,没有随机存取特性,算法时间主要花费在遍历元素上。

3.队列:

  1.一种操作受限的线性表,仅允许在表一端进行插入,在表另一端进行删除。删除一端为队头或队首,插入一端为队尾。因而队列又称为先进先出表。

  2.顺序队

     初始化队列时:front与rear指针为-1。

     1.判断队空条件:q->front==q->rear;

     2.判断队满条件:q->rear=MaxSize-1(数组最大下标)。

     3.进队:rear加一,将元素放入data数组rear位置;

     4.出队:将front加一,取出data数组front位置元素。

   3.环形队:

     初始化时front与rear指针为0。

     1.进队:rear=(rear+1)%MaxSize

     2.出队:front=(front+1)%MaxSize

     3.判断队空条件:q->rear==q->front

     4.判断队满条件:(q->rear+1)%MaxSize=q->front

     作用:解决了队列的假溢出问题,但队里最多只有MaxSize-1个元素。

   4.链队:

     1.链队不存在队满溢出问题。

可使用c++的头文件<queue>使用。

 3.栈:

   1.特点:后进先出表。

   2.顺序栈:

      进栈:top++;

      出栈:top--;

    3. 链栈同样没有链满问题

参考:可用c++头文件<stack>。

  4.串:

    串是由字符数据组成的有限序列

    1.顺序串与链串

    2.难点:

   串的模式匹配:

   BF算法:目标串的第一个字符开始和模式串第一个字符匹配,匹配成功,比较目标串和模式串的后续元素(即i++,j++),匹配失败,目标串回溯到刚开始元素的后续元素。

   暴力匹配,需要主串指针回溯。

   KMP算法:

   消除了主串指针回溯。用next数组表示,(next数组,nextval数组)

三、疑难问题:

 next数组 与nextval求值问题:数组开始的下标书上跟老师讲的或许不同,很容易混乱。

网上人们用的next

解决方案:

自己选定一种下标,列如

next数组:第一个next[1]=0,next[2]=1,再通过网上视频,或者老师讲解视频学习。

按个人喜好寻找方法吧。

    

相关推荐