数据结构与算法第四章数组、串与广义表

一维数组与多维数组

多维数组每一个数据元素可有多个直接前驱和多个直接后继（边界会有相应减少）。

数组元素下标一般具有固定下界和上界。

用一维内存表示多维数组，必须按某种次序将数组元素排列到一个序列中：行优先/列优先

行优先存放：设数组开始存放位置 $LOC(0, 0) = a$, 每个元素占用l个存储单元,$LOC ( j, k ) = a + ( j * m + k ) * l$（注意：要考虑第零行与第零列）；列优先存放：$LOC ( j, k ) = a + ( k * n + j ) * l$

三维数组：各维（页/行/列）元素个数为$m_1,m_2,m_3$，下标为的数组元素存储地址：（按页／行／列存放）

$LOC ( i1, i2, i3 ) = a + ( i1 m2 * m3 + i2 m3 + i3 ) * l $

$n$维数组同理。

对称矩阵与三对角矩阵

对称矩阵

只存对角线及对角线以上/下元素，称为上/下三角矩阵。

对$a[i][j],i>j$，为下三角矩阵，要计算其在一维数组中的存放位置只需罗列计算即可。$(i + 1)* i / 2 + j$

若$ i < j$，可以找对称元素$A[j][i] = j *(j +1) / 2 + i $

三对角矩阵

$B=\left { a_{00}, a_{01},a_{10},a_{11},a_{12},a_{21},a_{22},a_{23},a_{32}, … a_{n-1,n-2},a_{n-1,n-1} \right } $

共$3n-2$个元素。

在三条对角线上的元素$a_{ij}$ 满足$ 0\le i\le n-1,i-1\le j\le i+1$,在一维数组B中$A[i][j] $在第 $i$ 行，它前面有 $3*i-1 $个非零元素, 在本行中第 $j $列前面有 $j-i+1$ 个，所以元素$A[i][j] $在B中位置为 $k = 2*i + j$。

若已知三对角矩阵中某元素$A[i][j] $在数组 B[]存放于第$k$个位置，则有$i = floor((k + 1) / 3) , j = k - 2 * i$

稀疏矩阵：一般稀疏因子小于$0.05$称为稀疏矩阵。

用三元组$(i,j,a_{ij})$存储矩阵元素

稀疏矩阵三元组表中，非零矩阵元素按行存放。行号相同时按列号递增顺序存放。

稀疏矩阵快速转置算法

对原矩阵$A$扫描一遍，按$A$中每一元素的列号，立即确定在转置矩阵$B$三元组表中的位置，并装入它。

建立辅助数组$rowSize$和$rowStart$：$rowSize$记录矩阵转置前（矩阵$A$）各列，即转置矩阵$B$各行非零元素个数；$rowStart$记录转置矩阵$B$各行非零元素在转置三元组表中开始存放位置。（只要根据前面累加即可$Rowstart_i = Rowstart_{i-1}+Rowsize_{i-1}$）

template <class E> 
void SparseMatrix<E>::FastTranspos (SparseMatrix<E>& B) {
    int *rowSize = new int[Cols];//列元素数数组
    int *rowStart = new int[Cols];//转置位置数组
    B.Rows = Cols;
    B.Cols = Rows;
    B.Terms = Terms;
    if (Terms > 0) 
    {
        int i, j;
        for (i = 0; i < Cols; i++) rowSize[i] = 0;     
        for (i = 0; i < Terms; i++)
                 rowSize[smArray[i].col]++;
        rowStart[0] = 0;
        for (i = 1; i < Cols; i++)          
            rowStart[i] = rowStart[i-1]+rowSize[i-1];
        for (i = 0; i < Terms; i++) 
        {           
            j = rowStart [smArray[i].col];
            //因为矩阵A中的元素是按照行递增，行相同则列递增排列的，故第一个出现的列元素应当排在rowstart位置，而后逐渐递增。
            B.smArray[j].row = smArray[i].col;
            B.smArray[j].col = smArray[i].row;
            B.smArray[j].value = smArray[i].value;
            rowStart [smArray[i].col]++;        
        }        
    }    
    delete [ ] rowSize;   
    delete [ ] rowStart;
}

字符串

空串和空白串不同

起始位置为0

字符串重载操作

//串连接
AString& AString::operator += (const AString& ob)
{
     char *temp = ch;//暂存原串数组
     int n = curLength + ob.curLength;//串长度累加
     int m = (maxSize >= n) ? maxSize : n;//新空间大小
     ch = new char[m];
     if (ch == NULL) 
     { 
         cerr << “存储分配错!\n ”; 
         exit(1); 
     }
     maxSize = m;  curLength = n;
     strcpy(ch, temp);//拷贝原串数组
     strcat(ch, ob.ch);//连接ob串数组  
     delete []temp;  
     return this;
};
//串赋值，取第i个字符，判串相等/不等/空否/取子串

串的模式匹配

int AString::fastFind(AString& pat, int k, 
          int next[]) const {
//从k开始寻找 pat 在 this 串中匹配的位置。若找到，函数返回 pat 在 this 串中开始位置，否则函数返回-1。数组next[ ] 存放 pat 的next[j] 值。
     int posP = 0,  posT = k;//两个串的扫描指针
     int lengthP = pat.curLength;//模式串长度
     int lengthT = curLength;//目标串长度
     while (posP < lengthP && posT < lengthT)
     {
         if (posP == -1 || pat.ch[posP] == ch[posT]) 
            { 
                posP++;
                posT++;
            }//对应字符匹配
         else posP = next[posP];   //求pat下趟比较位置
         //为什么说next[0]=-1，当第一位没有匹配上时，必须P归零且T往后挪一位。
     }
     if (posP < lengthP) return -1; //匹配失败
     else return posT-lengthP;      //匹配成功
};
void AString::getNext(int next[]) 
{
     int j = 0, k = -1,lengthP = curLength;
     next[0] = -1;
     while (j < lengthP)//计算next[j]
     {
         if ( k == -1 || ch[j] == ch[k]) 
         {
             j++;
             k++;
             next[j] = k;
         }
         else k = next[k];
     }
}; 

//此算法的时间复杂度取决于 while 循环。由于是无回溯的算法，执行循环时，目标串字符比较有进无退，要么执行 posT 和 posP 进 1，要么查找next[ ] 数组进行模式位置的右移，然后继续向后比较。字符的比较次数最多为 O(lengthT)，不超过目标的长度。 

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
int m,n,Next[N],ans;
char pat[N],t[N];
void kmp()
{
    int j=0;
    for(int i=1;i<=n;i++)
    {
        while(j&&pat[j+1]!=t[i]) j=Next[j];
        if(pat[j+1]==t[i]) j++;
        if(j==m) ans++,j=Next[j];
    }
}
void getnext()
{
    int j=0;
    for(int i=2;i<=m;i++)
    {
        while(j&&pat[j+1]!=pat[i]) j=Next[j];
        if(pat[j+1]==pat[i]) j++;
        Next[i]=j;
    }
}
int main()
{
    cin>>t+1;
    cin>>pat+1;
    m=strlen(pat+1),n=strlen(t+1);
    getnext();kmp();
    cout<<ans;
    return 0;
}

广义表

为递归定义：允许有原子与子表

表头：第一个表元素表尾：除表头外其他元素组成的表

（重点）通过head与tail操作取出原子

在描述表头，表尾时如果出现嵌套询问，需按递归原则给出表及其子表的表头或表尾，并且要注意表尾定义，打上括号。 在书写取元素时也要注意表尾定义的额外影响

只包含原子的表退化为线性表 长度：原子/子表总个数 深度：以==表==为树结点，仿照树的深度，其中记线性表深度为1，例：((a,b),(),((((),c),d,e))的深度为4。对于递归表，深度记为无穷大。 特点：有次序性，有长度，有深度，可递归，可共享。（空表，线性表，纯表==无共享无递归==，再入表，递归表）

广义表的表示：链表

画广义表简图（重点）

uytpe(0/½,表头，原子数据，子表)	info（utype为0，存放引用计数，utype为1，存放数据值，utype为2，存放指向子表标头的指针）	tlink（utype为0，指向该表的第一个结点，否则指向同一层下一个节点）

数据结构与算法第四章 数组、串与广义表

画广义表简图（重点）

数据结构与算法第四章数组、串与广义表