C数据结构-串和数组

一，串及其运算

串（即字符串）是一种特殊的线性表，它的数据元素仅由字符组成。

串是由零个或多个字符组成的有限序列。串中任意连续个字符组成的子序列称为子串。子串的第一个字符在主串中的序号，定义为子串在主串中的位置，该位置索引从0开始。

特别的，空串是任意串的子串，任意串是自身的子串。

串的逻辑结构与线性表极为相似，区别仅在于串的数据对象约束为字符集，但操作有很大差别。

求子串，从第i位置的字符开始抽出j个字符构成一个新的串。j<=strlen(s)+1-i;

二，串的存储结构

存储串的方法也是存储线性表的一般方法。

1，顺序存储

typedef struct{
char ch[maxsize];
int len;
}string;

用一个不会出现在串中的字符作为串的终结符，放在串的尾部，表示串的结束。（C中为\0）

2，链式存储

typedef struct linknode{
char data;
struct linknode *next;
}linkstring;
linkstring *s;

链串由头指针唯一确定。但存储效率极低。

3，索引存储

在索引存储中，除了存放串值外，还要建立一个串名和串值之间对应关系的索引表。

（1）带长度的索引表

typedef struct{
char name[maxsize];  //串长
int length;
char *stadr;   //串值存入的起始地址
}lennode;

记录每个串的名字，长度和起始地址。可以由起始地址加长度来确定串名表示的串。

（2）带末指针的索引表

用一个指向串值存放的末地址的指针enadr来代替长度。

typedef struct{
char name[maxsize];
char *stadr,*enadr;
}enode;

（3）带特征位的索引表

当串值只需要一个指针域的空间就能存放时，可将串值放在stadr域中。这时需要增加一个特征位tag来指出stadr域中是指串还是指针。

typedef struct{
char name[maxsize];
int tag;
union{
  char *stadr;
  char value[4];
}uval;
}tagnode;

在串的索引存储下实现串值空间的动态分配：假设有一个大的向量表示可供分配用的连续的存储空间，用一个指针指示尚未分配存储空间的起始位置。当程序运行过程中，每产生一个新串，就从起始位置进行存储分配，同时在索引表中建立一个相应的结点，在结点中填入名字，分配到的起始地址，串长等，然后修改起始指针。

三，串运算的实现

大多数情况下串采用顺序存储，这是关于串的运算往往是通过元素的移动来实现的。

1，基本运算实现

typedef struct{
char ch[maxsize];
int len;
}string;

（1）串的连接运算（strcat）

for(i=0;i<s->len;i++)
     r->ch[i]=s->ch[i];
for(i=0;i<t->len;i++)
     r->ch[s->len+i]=t->ch[i];
r->ch[s->len+i]='\0';
r->len=s->len+t->len;

（2）求子串运算

将S中第i个字符起，抽取j个字符构成一个子串，结果存放在t中。

if(i+j-1>s->len)
     printf("超界");
else
{
    for(k=0;k<j;k++)
          t->ch[k]=s->ch[i+k-1];
    t->len=j;
    t->ch[t->len]='\0'; 

（3）子串定位

子串定位又称为串的模式匹配，是串处理中最重要的运算之一。

从目标S中查找模式为T的子串的过程称为模式匹配。

<1>朴素的模式匹配思想是：从目标S中的第一个字符开始和模式T中的第一个字符比较（用i和j分别表示S串和T串中正在比较的字符位置），若相等，则继续比较，否则从目标S的第二个字符开始重新与模式串的第一个字符比较。又称布鲁特-福斯算法。

在一趟失败的匹配中必定存在一个j使得S(i)!=T(j),T(j-1)!=S(i-1),,,,,,T(1)!=S(i-j+1)，即T(1)和S的第i-j+1个字符对应。因此，新的一趟匹配开始时，i应该回溯到i-j+2的位置。

int Index(string *s,string *t){
int i=0,j=0;
while(i<s->len&&j<t->len)
{
   if(s->ch[i]==t->ch[j]
   {
      i++;
      j++;
   }
   else
   {
      i=i-j+1;   //此时回溯位置尚有疑问
      j=0;
   }
}
if(j==t->len)
    return i-t->len;
else
    return -1;
}//Index

匹配成功时j==t->len，i的值相对应于t->len的后一个位置，故返回值是i-t->len,而不是i-t->len+1;

上述算法可做改进，当某一趟匹配已失败，i值回溯时，可加入另一个判断，若i>s->len-t->len，则串中剩余子串的长度已小于模式T的长度，此时匹配不可能成功，故可直接返回-1.

也可以在i值回溯前加入判断i>s->len-t->len+j-1.    （此处尚有疑问）

采用链式存储结构写出模式匹配算法：

//只要用一个指针first，记住每一趟匹配开始时目标串起始比较结点的地址。若某一趟匹配成功，则返回first的值；若整个匹配失败，返回空指针。
linkstring *iNDEX(linkstring *s,linkstring *t){
linkstring *first,*sptr,*tptr;   //s,t是不带头结点的链串
first=s;     //first指向s起始比较地址
sptr=first;   tptr=t;
while(sptr&&tptr)
{
   if(sptr->data==tptr->data)    //继续比较后续结点的字符
   {
       sptr=sptr->next;
       tptr=tptr->next;
   }
   else      //本趟匹配失败，回溯
   {
       first=first->next;
       sptr=first;
       tptr=t;
   }
}
if(tptr==NULL)           //匹配成功
     return first;
else                   //匹配失败
     return NULL;
}

<2>改进的模式匹配算法（KMP算法）

改进之处：每当一趟匹配过程中出现字符比较不相等时，不需回溯i值，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。

设计一个无回溯的匹配算法，关键在于匹配过程中，一旦Si与Tj比较不相等，存在有下列条件时

substr(s,i-j+1,j-1)=substr(t,1,j-1)    ;      si!=tj;

注：substr(s,i,j)求子串：从S的第i个字符开始抽取j个字符组成新串。

要立即确定右移的位数和继续比较的字符，也就是说，能确定T中哪一个字符应该和S中的Si进行比较。将这个字符记为Tk，k<j，且对于不同的j值，k值也不同。（之前回溯到i-j+1，现在不必回溯，还是和Si比较）

这个K值仅仅依赖于模式串T本身的前j个字符的组成，而与目标S无关。

一般使用next[j]表示与j对应 的k值，即若next[j]>0,表示一旦匹配过程中出现不相等Si!=Tj，可用T中的以next[j]为下标的字符与Si进行比较；若next[j]=0,则表示T中任何字符都不与Si进行比较，将T1与Si+1进行比较。

可见，对模式T而言，只要能确定next[j]的值，就可以加速匹配过程。

对next[j]性质进行分析的步骤如下：

（1）next[j]是一个整数，并且满足0<next[j]<j;

（2）匹配过程中，一旦Si!=Tj,根据next[j]的意义，用Tk（k=next[j]!=0）与Si继续比较。也可以看做将T右移j-next[j]位。

为了保证下一步比较是有效的，这时应有t1=si-k+1,t2=si-k+2,.........tk-1=si-1.

由于在si!=tj之前已有t1=si-j+1,t2=si-j+2,........,tj-1=si-1,因此上述条件等价于t1=tj-k+1,t2=tj-k+2,,,,,,,,,tk-1=tj-1,即表示k的取值范围应使得t1t2.....tj-1的首尾k-1个字符组成的子串相等，也就是说SubStr(T,1,k-1)=SubStr(T,j-k+1,k-1).

（3）为使T的右移不丢失任何匹配成功的可能，对于同时存在多个满足（2）的K值应取其中最大的值，这样移动的位数j-k最小。

（4）如果在t1t2......tj-1的首尾不存在相同的子串，即子串的长度为0，则K=1，表示一旦有tj!=si,则用t1与sj进行比较。

特殊情况，当J=1时，不能右移，可将t1与si+1进行比较，next[j]=0;若tj与si比较不相等，则可用（K=NEXT[J]）tk与si比较；如果已知tj=tk,则相比较必有tk!=si；此时可根据next[j]意义再取k'=next[k]!=0,用tk'与si继续比较。所以当tj=tk时，next[j]=next[k].

下面给出next函数的定义：

next[j]=0,j=i;      max(k|0<k<j且使得t1t2.......tk-1=tj-k+1.......tj-1成立   当此集合不为空时        1 ，其他情况

模式串的next值
int index(string *s,string *t)
{
 int i=0,j=0;
while(i<s->len&&j<t->len)
{
   if((j==-1)||(s->ch[i]==t->ch[i]))
   {
         i++;     j++;
   }
   else
   { 
        j=next[j];       //模式串向右移动
    }
  }
if(j==t->len)
    return i-t->len;     //匹配成功
else
    return -1;          //匹配失败
} 

下面给出求next数组的算法：

void getnext(string *t,int *next){
int i=0,j=-1;
next[0]=-1;
while(i<t->len)
{
   if((j==-1)||t->ch[i]==t->ch[j])
   {
       ++i;
       ++j;
       next[i]=j;
    }
    else
        j=next[j];
  }
} 

快速模式匹配算法仅在模式与主串之间存在许多“部分匹配”的情况下，才显得更有效果。快速匹配的优点是指示目标串的指针不需要回溯，在整个匹配过程中，对目标串仅需从头到尾扫描一遍，这对处理从外设输入的庞大文件很有效，可以边读入边匹配，无需回头重读。

四，数组的定义和运算

三维数组可以看做其元素用二维数组定义的特殊线性表。以此类推，n维数组是由n-1维数组定义的，每个元素受到n个下标约束。

数组是由值与下标构成的有序对，结构中的数据元素都与其下标有关。

数组性质：数据元素数目确定；数据元素有相同类型；下标有上下界的约束，并且下标有序；

五，数组的顺序存储结构

一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动。

二维数组的顺序存储：以行为主序的优先存储和以列为主序的优先存储。以下标顺序为主序的优先存储和以逆下标顺序为主序的优先存储。

多维数组中，以下标顺序为主序表示先排最右的下标，从右向左直到排到最左的下标；而以逆下标顺序为主序，则表示从最左开始向右排列。

六，矩阵的压缩存储

用二维数组来描述矩阵。

压缩存储，是指对多个相同的元素只分配一个空间，对零元素不分配空间。

1，特殊矩阵

（1）对角矩阵

所有非零元都集中在以主对角线为中心的带状区域中，即除了主对角线上和主对角线相邻近的上下方以外，其余元素均为0.

最简单的情况为只在主对角线上含有非零元。

A[0]=A[0][0],A[1]=A[1][1],即A[k]与aii对应关系是k=i.

（2）三角矩阵

上三角矩阵是指矩阵的下三角（不包含对角线）中的元素均为0，上三角矩阵与之相反。

在三角矩阵中，值相同的元素可共享一个存储空间，若重复元素为0则可不分配存储空间；其余的元素共有n*(n+1)/2个。

在下三角矩阵中，对于aij元素，前面已经存放了i行，元素的总数为i*(i+1)/2,aii处在第i+1行的第j+1个元素，则其前面已存放的元素数目为i*(i+1)/2+j,也就是说，aij应是数组A的第k+1个元素，k=i*(i+1)/2+j.

A[k]与aij的对应关系为   k=i*(i+1)/2+j,i>=j;     k=n*(n+1)/2,i<j

（3）对称矩阵

在n阶方阵中，若A中元素满足aij=aji,则A是对阵矩阵。

元素关于对角线对称，因此在存储时只需存储上三角或下三角中的元素，使得对称的元素共享一个存储空间。

假设存储下三角中的元素，k=i*(i+1)/2+j,i>=j;

当i>j时，在上三角矩阵，k=j*(j+1)/2+i,i<j；

统一起来就是：k=i*(i+1)/2+j,   i=max(i,j),     j=min(i,j).

2,稀疏矩阵

含有非零元素及较多的零元素，但非零元素的分布没有任何规律。

下面仅讨论用三元组表来表示两种稀疏矩阵的压缩存储方法。

若将表示稀疏矩阵的非零元素的三元组按行优先（或列优先）的顺序排列（跳过零元素），则得到一个其结点都是三元组的线性表。我们将该线性表的顺序存储结构称为三元组表。因此，三元组表是稀疏矩阵的一种顺序存储结构。

要唯一的存储一个稀疏矩阵，还必须存储该矩阵的行数和列数。还要将非零元素的个数与三元组表存储在一起。

typedef strucct{
   int i,j;   //行号，列号
   datatype v;    //元素值
}node;    
typedef struct{ 
  int m,n,t;           //行数，列数，非零元素个数
  node data[maxsize];      //三元组表
}spmatrix;           //稀疏矩阵类型

通过行号，列号以及元素值来存储矩阵。

压缩存储中实现矩阵的运算：

将矩阵转置，将A转置成B，就是将A的三元组表中的a->data置换成b->data，再重新排列三元组 的顺序使之成为按行优先排列。

由于A的列是B的行，因此，按a->data的列序转置，所得到的转置矩阵B的三元组表必定是按行优先存放的。为了找到A的每一列中所有的非零元素，需要对三元组表从第一行起整个扫描一遍。

spmatrix *transmat(spmatrix *a){
int i,j,bno=0;
apmatrix *b;
b=(spmatrix *)malloc(sizeof(apmatrix));
b->m=a->n;
b->n=a->m;
b->t=0;
if(a->t==0)     return b;
for(i=0;i<a->n;i++)    //遍历列
{
    for(j=0;j<a->t;j++)
    {
        if(a->data[j].j==i)
        {
            b->data[bno].i=a->data[j].j;           
            b->data[bno].j=a->data[j].i;           
            b->data[bno].v=a->data[j].v;
            bno++;
        }
     }
}
b->t=bno;
return b;
}