Java教程

数据结构-串,数组,广义表

本文主要是介绍数据结构-串,数组,广义表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

数据结构-串,数组,广义表

王卓老师课程的听课笔记

串,数组,和广义表

  • 对于串而言,数据元素只能是字符
  • 可以看作是线性表(内容受限的线性表)
  • 是线性结构的推广(某种意义上讲,已经不再属于线性结构)

  • 串(String)是由零个或多个任意字符组成的有限序列

  • 串的内容称之为串值,串的名称称为串名

  • 当元素大小等于0时,被称为空串,用空集的符号表示,空串连空格都没有。

  • 子串:一个串中任意个连续字符组成的子序列(含空串),称为该串的子串。

  • 真子串是指不包含自身的所有子串

  • 主串:包含子串的串相应地称为主串

  • 字符位置:字符在序列中的序号为该字符在串中的位置

  • 字串位置:子串第一个字符在主串中的位置

  • 空格串:由一个或多个空格组成的串,与空串不同

  • 串相等:当且仅当两个串长度相等并且各个对应位置上的字符都相同时,这两个串才相等,空串全部都相等

串的类型定义以及存储结构

  • 串中元素逻辑关系与线性表相同,串可以采用与线性表相同的存储结构。
  • 串的顺序存储结构

    #define MAXLEN 255
    typedef struct{
    	char ch[MAXLEN+1];//存储串的一维数组
    	int length;//串的当前长度
    }SString;
    
    • 串的顺序存储,通常将数组的第一个元素空开。这样有利于后续的一些字符串算法的实现。
  • 串的链式存储结构

    • 优点:操作方便
    • 缺点:存储密度较低
    • 存储密度=串值所占的存储/实际分配的存储

如果将多个字符存放在一个结点中,就可以克服存储密度低的缺点。

#define CHUNKSIZE 80//块的大小可由用户定义
typedef struct Chunk
{
	char ch[CHUNKSIZE];
	struct Chunk *next;
}Chunk;

typedef struct{
    Chunk *head,*tail;//串的头指针和尾指针
    int curlen;//串的当前长度
}LString;//字符串的块链结构

串的模式匹配算法

  • 确定主串中所含子串(模式串)第一次出现的位置(定位)

  • 算法应用:

    • 搜索引擎、拼写检查、语言翻译、数据压缩
  • 算法种类:

    • BF算法(穷举法)
    • KMP算法
  • BF算法

    主串S(正文串),子串T(模式串)

    • 从S的每一个字符开始一次与T的字符进行匹配。
    • 匹配的内容时每一个字符,一一比较看是否相同。
    • 匹配失败:i = i-j+2 = 2(回溯,回溯岛上一个匹配的位置);j = 1(从头开始);
    • 核心思想:
      • 将主串的第pos个字符和模式串的第一个字符比较
      • 若相等,继续逐个比较后续字符
      • 若不等,从主串的下一个字符起,重新与模式串的第一个字符比较。
      • 直到主串的一个连续子串字符序列与模式串相等。返回值为S中与T匹配的子序列第一个字符的序号,即匹配成功。
      • 否则,匹配失败,返回值0;
  • BF算法代码:

    int Index_BF(SString S,SString T)
    {
        int i = 1,j = 1;
        while(i<=S.length&&j<=T.length)
        {
            if(s.ch[i]==t.ch[j])//主串和子串一次匹配下一个字符
            {
                ++i;
                ++j;
            }
            else
            {
                i = i - j + 2;
                j = 1;//主串、子串指针回溯重新开始下一次匹配
            }
        }
        if(j>=T.length) return i-T.length;//返回匹配的第一个字符的下标
        else return 0;//模式匹配不成功
    }
    
    • 课本算法源码

      int Index_BF(SString S,SString T,int pos)
      {
          int i = pos,j = 1;
          while(i<=S.length&&j<=T.length)
          {
              if(s.ch[i]==t.ch[j])//主串和子串一次匹配下一个字符
              {
                  ++i;
                  ++j;
              }
              else
              {
                  i = i - j + 2;
                  j = 1;//主串、子串指针回溯重新开始下一次匹配
              }
          }
          if(j>=T.length) return i-T.length;//返回匹配的第一个字符的下标
          else return 0;//模式匹配不成功
      }
      
      • 这个pos是开始的位置。第一个算法是默认从第一位开始匹配的,第二个算法默认是从pos位置开始。
  • KMP算法
    • 相较于BF算法,主串i的指针不再回溯了,假如在子串中有和子串首元素相同的字符,而且在之前的匹配过程中已经匹配完毕了,那么J也没有必要回溯至0。
    • 为此,定义next[j]数组 ,表明当模式串中第j个字符与主串中相应字符“失配”时,在模式串中需重新和主串中该字符进行比较的字符的位置。
    • next[j]存储三种数据:
      • 当j = 1时,next[j]=0
      • 其他情况,next[j]=1
      • 当主串从头开始的k-1个元素(前缀)和j前面的k-1个元素(后缀)相同时。next[j]=max(1,j)
int Index KMP(SString S,SString T,int pos)
{
	i = pos,j = i;
    while(i<S.length && j<T.length)
    {
        if(j==0||S.ch[i]==T.ch[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];/*i不变,j后退*/
        }
    }
    if(j>T.length)
    {
        return i-T.length;/*匹配成功*/
    }
    else return 0;
}

求next[j]的算法

void get_next(SString T,int &next[])
{
	i = 1;next[1] = 0;j = 0;
	while(i<T.length)
	{
		if(j == 0||T.ch == T.ch[j])
		{
			++i;
			++j;
			next[i] = j;
		}
		else
		{
			j = next[j];
		}
	}
}
  • 针对next函数的改进

    • 如果前面出现了很多相同的字符,字符本身没有匹配上,那么后面也不需要重复的对已经失配的字符城府匹配了。

      void get_nextval(SString T,int &nextval[])
      {
      	i = 1;nextval[1] = 0;j = 0;
      	while(i<T.length)
      	{
      		if(j==0||T.ch[i] == T.ch[j])
      		{
      			++i;
      			++j;
      			if(T.ch[i] != T.ch[j])
      			{
      				nextval[i] = j;
      			}
      			else
      			{
      				nextval[i] = nextval[j];
      			}
      		}
      		else j = nextval[j];
      	}
      }
      

数组(就是那个你熟悉的)

  • 按照一定的格式排列起来的,具有相同类型的数据元素的集合。

  • 若线性表中的数据元素为非结构的简单元素,则称为一维数组。

  • 一维数组的逻辑结构:线性结构。定长的线性表。

  • 声明格式:数据类型 变量名称[长度];

  • 可以单个赋值,也可以统一初始化赋初值。

  • 二维数组:若一维数组中的数据元素又是一维数组结构,则称为二维数组

  • 二维数组的逻辑结构

    • 非线性结构:每一个数据元素既在一个行表中,又在一个列表中。(不只有一个前驱,一个后继,有多个前驱,多个后继)
    • 线性结构,定长的线性表:该线性表的每个数据元素也是一个定长的线性表。
  • 声明格式:数据类型 变量名称[行数] [列数];

  • 在C语言中,一个二维数组类型也可以定义为一维数组类型(其分量类型为一维数组类型),即:

    typedef elemtype array2[m][n];
    
    //等价于:
    typedef elemtpye array1[n];
    typedef array1 array2[m];
    
  • 三维数组:若二维数组中的元素又是一个一维数组,则称作三维数组。

  • n维数组:若n-1维数组中的元素又是一个一维数组结构,则称作n维数组。

  • 线性表结构是数组结构的一个特例,而数组结构又是线性表结构的扩展。

  • 数组特点:结构固定——定义后,维数和维界不再改变。

  • 数组基本操作:除了结构的初始化和销毁之外,只有取元素和修改元素值的操作。

  • 数组的结构固定,维数和维界不变,所以,一般采用顺序存储结构来表示数组。
  • 注意:数组可以是多维的,但存储数据元素的内存单元地址是一维的,因此,在存储数组结构之前,需要解决将多维关系映射到一维关系的问题
  • 二维数组在内存中如何存储呢?

    C,PASCAL,Java,Basic,是以行序为主序(一行一行来存储)

    个别语言以列序为主序

  • 设数组开始存储位置LOC(0,0),存储每个元素需要L个存储单元,数组元素a[i] [j]的存储位置是:LOC(i,j) = LOC(0,0) + (n*i+j) *L

  • 三维数组,按页/行/列存放,计算地址位置同理二维数组。

特殊矩阵的压缩存储

  • 矩阵的常规存储:

    将矩阵描述为一个二维数组

  • 矩阵的常规存储的特点:

    • 可以对其元素进行随机存取;
    • 矩阵运算非常简单;存储的密度为1.
  • 不适宜常规存储的矩阵:值相同的元素很多,且呈某种规律分布;零元素多。

  • 矩阵的压缩存储:为多个相同的非零元素只分配一个存储空间;对零元素不分配空间。

  • 什么是压缩存储?

    若多个数据元素的值都相同,则只分配一个元素值的存储空间,且零元素不占存储空间。

  • 什么样的矩阵能够压缩?

    一些特殊矩阵,如:对称矩阵,对角矩阵,三角矩阵,稀疏矩阵等。

  • 什么叫稀疏矩阵?

    矩阵中非零元素的个数较少(一般小于5%)

  • 对称矩阵

    • 特点:在n*n的矩阵中,沿主对角线对称的元素相同。
    • 存储方法:只存储下(或者上)三角(包括主对角线)的数据元素。共占用n(n+1)/2个元素空间。

存储时可以以行序为主序储存下三角

按顺序存储到一维数组当中

三角矩阵的压缩存储

  • 特点:对角线一以下(或者以上)的数据元素(不包括对角线)全部为常数C。
  • 存储方法:重复元素c共享一个元素存储空间,共占用n(n+1)/2+1个元素

对角矩阵(带状矩阵)

  • 在n*n的方阵中,所有非0 元素都集中在以主对角线为中心的带状区域中,区域外的值全为0,则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。(有几条,就叫做几对角矩阵)
  • 用二维数组去存,从上往下,一条对角线存一行。

稀疏矩阵

  • 三元组法确定稀疏矩阵的内容
  • 由于稀疏矩阵里面的元素特别的少,所以三元组里面包含三个元素(行,列,数据本身),这样就知道了该矩阵的所有情况。
  • 三元组用顺序表存储,通常还得再加一个“总体”信息:即总行数、总列数、非零元素总个数。这样可以按照这个顺序表复现稀疏矩阵。
  • 三元组顺序表又称有序的双下标法。
  • 三元组顺序表的优点:非零元在表中按行序有序存储,因此便于进行依行顺序处理的矩阵运算。
  • 三元组顺序表的缺点:不能随机存取,若按行号存取某一行中的非零元,则需从头开始进行查找。
  • 十字链表:
    • 优点:能够灵活地插入因运算而产生的新的非0元素,删除因运算而产生的新的零元素,实现矩阵的各种运算。
    • 在十字链表中,矩阵的每一个非零元素用一个结点表示,该结点除了三元组(row,col,value)以外,还要有两个域:
      • right:用于链接同一行中的下一个非零元素。
      • down:用于链接同一列中的下一个非零元素。
      • 还需要行的头指针数组和列的头指针数组

广义表

  • 又称List,是n>=0个元素的有限序列,其中每一个元素,可以是任何形式的数据。

  • 广义表通常记作LS = (a1,a2,a3…,an)

    其中:LS为表名,n为表的长度,每一个ai为表的元素。

  • 习惯上,一般用大写字母表示广义表,小写字母表示原子。

  • 表头:若LS非空,则第一个元素a1就是表头。记作head(LS) = a1.表头可以是原子,也可以是子表。

  • 表尾:除表头之外的其他元素组成的表。

    记作 tail(LS) = (a2,…,an)

    注:表尾不是最后一个元素,而是一个子表。

  • 广义表中的数据元素有相对次序:一个直接前驱和一个直接后继

  • 广义表的长度定义为最外层所包含元素的个数;

  • 广义表的深度定义为该广义表展开后所含括号的重数;

  • 广义表可以为其他广义表共享。

  • 广义表可以是一个递归的表,长度有限,深度无限。

  • 广义表是多层次结构,广义表的元素可以是单元素,也可以是子表,而子表的元素还可以是子表…

广义表可以看成是线性表的推广,线性表是广义表的特例

常见算法

  • 求表头GetHead(L):表头可以是元素也可以是子表
  • 求表尾GetTail(L):表尾一定是一个表

存储方式

  • 链表(共用体链表?)
这篇关于数据结构-串,数组,广义表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!