[TOC]

数据结构:串与数组

一、串类型的定义

  1. 含义:串(或字符串)是由零个或多个字符组成的有限序列。一般记作: s=‘c0c1c2…cn-1’(n≥0),字符串一般简称为串,可以将它看作是一种特殊的线性表;

  2. 特点:在线性表的基本操作中,大多以“单个元素”作为操作对象,而在串中,则是以“串的整体”或一部分作为操作对象

  3. 常用基本运算:

    StrAssign (&T, chars)
    StrCopy (&T, S)
    StrCompare (S, T)
    StrLength (S)
    Concat (&T, S1, S2)
    SubString (&Sub, S, pos, len)
    Index(S, T, pos)

二、串的表示

串是一种特殊的线性表,其存储结构与线性表的存储结构类似,只不过组成串的结点是单个字符。串的存储结构表示有两种方法:静态存储和动态存储

  1. 顺序存储结构 (静态)串的顺序存储结构是采用与其逻辑结构相对应的存储结构,将串中的各个字符按顺序依次存放在一组地址连续的存储单元里,逻辑上相邻的字符在内存中也相邻。 串值的存储分配是在编译时完成的。因此,需要预先定义串的存储空间大小。如果定义的空间过大,则会造成空间浪费;如果定义的空间过小,则会限制串的某些运算,如联接、置换运算等。

  2. 堆分配存储结构(动态)
    堆存储结构的特点是,仍以一组空间足够大的、地址连续的存储单元存放串值字符序列,但它们的存储空间是在程序执行过程中动态分配的。所以也称为动态存储分配的顺序表。每当产生一个新串时,系统就从剩余空间的起始处为串值分配一个长度和串值长度相等的存储空间。(利用malloc和free两个函数实现动态存储分配)
    由于堆分配存储结构的串既有顺序存储结构的特点,处理方便,操作中对串长也没有任何限制,更显得灵活,因此使用极为广泛。

  3. 块链存储结构(动态)
    顺序串上的插入和删除操作不方便,需要移动大量的字符。因此,我们可用单链表方式来存储串值,串的这种链式存储结构简称为链串。用单链表存放串,每个结点仅存储一个字符,因此,每个结点的指针域所占空间比字符域所占空间要大得多。为了提高空间的利用率,我们可以使每个结点存放多个字符,称为块链结构

    结点大小为1的链式存储结构:
    一个链串由头指针唯一确定。这种结构便于进行插入和删除运算,但存储空间利用率太低。

三、数组的定义

  • 定义

数组(Array)是由n(n>1)个相同类型数据元素a0,a1,…ai…,an-1构成的有限序列

  • 数组的性质:
  1. 数组中的数据元素数目固定。一旦定义了一个数组,其数据元素数目不再有增减变化。它属于静态分配存储空间的数据结构。

  2. 数组中的数据元素必须具有相同的数据类型。

  3. 数组中的每个数据元素都有一组唯一的下标值。

  4. 数组是一种随机存储结构,可随机存取数组中的任意数据元素。

注明:有时也把一维数组称为向量,二维数组称为矩阵

四、数组的顺序表示和实现

五、矩阵的压缩存储

数值分析中常出现矩阵,如何处理较为重要:

  • 特殊矩阵的压缩存储方法
    对称矩阵、三角矩阵、带状矩阵和稀疏矩阵等。为了节省存储空间并且加快处理速度,需要对它们进行压缩存储,压缩存储的原则是:不重复存储相同元素;不存储零值元素。
  1. 对称矩阵的压缩存储

    对称矩阵是一个n阶方阵。若一个n阶矩阵A中的元素满足:ai,j=aj,I (0≤i,j≤n-1),则称A为n阶对称矩阵。

​ 处理:由于对称矩阵中的元素关于主对角线对称,因此可以为每一对对称的矩阵元素分配 1 个存储空间,n阶矩阵中的n×n个元素就可以被压缩到 n(n+1)/2 个元素的存储空间中去。 称一维数组sa[0..n(n+1)/2] 为n 阶对称矩阵A的压缩存储

  1. 三角矩阵的压缩存储
    三角矩阵也是一个n阶方阵,有上三角和下三角矩阵。下(上)三角矩阵是主对角线以上(下)元素均为零的n阶矩阵。设以一维数组sb[0..n(n+1)/2]作为n阶三角矩阵B的存储结构,仍采用按行存储方案,则B中任一元素bi,j和sb[k]之间存在着如下对应关系
  1. 对角矩阵的压缩存储
    对角方阵(或称带状矩阵)是指所有的非零元素(简称非零元)都集中在以主对角线为中心的带状区域中,即除了主对角线上和紧靠着主对角线上下方若干条对角线上的元素外,所有其它元素皆为零的矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。下图是一个具有3(1≤m<n)条非零元素带的n阶对角矩阵。

    具有3条非零对角线的对角矩阵 :

对于n阶有m (m必为奇数,因为副对角线关于主对角线对称) 条非零元素带的对角矩阵,只需存放对角区域内的所有非零元素即可。

总结:对特殊矩阵的压缩存储实质上就是将二维矩阵中的部分元素按照某种方案排列到一维数组中,不同的排列方案也就对应不同的存储方案。

wechat