本文仅作备忘。。。

数组和字符串都是线性表。

一、数组

一维数组即为采用顺序存储映像的线性表，其大小固定。

二维数组可以看做：它的每个数据元素也是一个定长线性表的定长线性表。

N维数组一次类推。

约定N维数组array[n1][n2]…[nN]中，n1指第一维，n2指第二维，…nn为第N维。

 

由于数组各个维度的长度都固定，因而N维数组中任意一个元素的存储位置可以表示为：

Location（j1,j2,…jn）= Location（0,0,…0）+ （b2 * … * bn * j1 + b3 * … * bn * j2+ … + jn） * L（其中j1, j2, jn为要求的数组元素在每一维上的下标，b2,b3,…bn为第2,3,N维的长度，L为每个数据元素占据的空间大小。）

因而数组元素的存储位置都是其下标的线性函数，称具有这样的特点的存储结构为随机存储结构。

 

矩阵多采用二维数组（矩阵运算在一些图形图像计算，音频视频编解码时是比较常见的，而且现在有专门的芯片为此类运算提供支持）。

 

如果矩阵是稀疏矩阵，则采用数组就会浪费空间，此时可以采用十字链表法。

其c结构如下：

typedef struct node_s{

       introw,col;  //该非零元素的行、列下标

       Elementele; //该非零元素

       structnode_s *rignt, *down;//right用于将本行上的非零元素串起来，down用于将本列上的非零元素串起来

}node_t; 

二、字符串

字符串是由零个或多个字符组成的有限序列。

1、其涉及的一些概念：

字符串的长度：字符串中字符的数目

空串：零个字符的字符串

子串：字符串中任意个连续字符组成的子序列

字符串相等：字符串的长度相同并且各个位置对应的字符相同

2、字符串的表示和实现：

如果字符串的长度固定，就可以为字符串分配一个固定大小的存储区。

如果字符串的长度不固定，可以在使用时动态申请一块连续的存储区，C中通过malloc来实现。

本质上，字符串也可以使用链式存储结构，但是采用链式存储结构会大量消耗内存而且操作复杂，因而基本上字符串不采用链式存储结构。

文本编辑器中的基本操作一般都包括串的查找、修改、插入和删除。