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

一.思维导图

二 . 重要概念的笔记

1.循环队列

删除一个元素
front=(front+1)%maxsize

添加一个元素
rear=(rear+1)%maxsize;

队列元素个数=(front-rear+maxsize)%maxsize;

2.随机存储取元素地址

position=a[0]+(i-1)*sizeof(Elementype);

3.KMP算法

next[j]代码

    i=1,next[1]=0;j=0
    while(i<T[0]){
        if(j==0||T[i]==T[j])
        {++i,++j,next[i]=j;}
        else j=next[j];
    }

nextval[j]代码

    i=1,nextval[1]=0;j=0
    while(i<T[0]){
        if(j==0||T[i]==T[j])
        {++i,++j;
        if(T[i]!=T[j])nextval[i]=j;
        else nextval[i]=nextval[j];
        }
        else j=nextval[j];
    }

4.递归算法时间复杂度

思路：列出T（k）的函数

例1

int fact(int n)
{     if(n<=1) return 1;   
     else     return n*fact(n-1); 
} 

T(k)=1               当k=1 
T(k)=1+T(k-1)        当 k≠1 
则： T(n)=1+T(n-1)        
              =1+1+T(n-2)
              =1+1+....+T(1)
               =n        
               =O(n)

例2

void mergesort(int a[],int i,int j){
    int m;
        m=(i+j)/2;
    if(i!=j){
       mergesort(a,i,m);
       mergesort(a,m+1,j);
       merge(a,i,j,m);
    }
}

o(nlg2n)
T(k)=O(1)              当k=1 
T(k)=2T(k/2)+O(k)        当 k≠1 
T(N)=2T(N/2)+N=2(2T((n/4)+N/2)+N=......=2^k(T(n/2^K))+kn
当N=2^k 即k=log2 n
T（N）=n+nlog2n=O（nlog2n）

三. 疑难问题及解决方案

问题：多维数组计算

按底下标优先存储的A[9] [3] [5] [8],第一个元素地址为100.每个整数占4个字节，求loc（a[1] [1]

[1] [1])。

解决方案：

当第一次思考时毫无头绪，但老师提到多维数组在计算机中其实还是一维排列。如a[2] [2],顺序为a[0] [0],

a[0][1] ,a[1][0],a[1][1].列满了再进行，如同将一个整体分割为两部分a[0]、a[1]，再将这两部分分别再分割为两部分，即a[0]变为a[0][0],a[0][1],a[1]变为a[1] [0],a[1] [1]两部分。所以A[9] [3] [5] [8]即先分9部分，每一部分再分3部分，3部分里每一部分继续分为5部分这样下去。仿照二维数组公式loc(i,j)=loc(0,0)+(n*i+j) *L,得loc（a[1] [1][1][1])=100+(1 * (3 * 5 * 8)+1 * (5 * 8)+1 * 8+ 1) *4=776。个人认为这不需要用立体想象的方法也能快速解决，更多维的数组也可方便地计算。