数据结构题集c语言版严蔚敏_数据结构c语言版严蔚敏pdf第四版

数据结构题集c语言版严蔚敏_数据结构c语言版严蔚敏pdf第四版《数据结构C语言版严蔚敏第2版》:串、数组、广义表_严蔚敏数据结构c语言版第二版主要内容

一、串

1、串的定义 

计算机上的非数值处理的对象大部分是字符串数据,字符串一般简称为串

串是一种特殊的线性表,其特殊性体现在数据元素是一个字符,也就是说,串是一种内容
受限的线性表

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

串中字符的数目 n 称为串的长度。零个字符的串称为空串(null string) , 其长度为零

只有当两个串的长度相等, 并且各个对应位置的字符都相等时才相等

由一个或多个空格组成的串 ” ” 称为空格串 (blank string, 请注意:此处不是空串),
其长度为串中空格字符的个数

2、串的存储结构及其运算 

2.1、串的存储结构 

1)串的顺序存储 

用一组地址连续的存储单元存储串值的字符序列。 

按照预定义的大小,为每个定义的串变量分配一个固定长度的存储区,则可用定长数
组如下描述: 

#define MAXLEN 255 // 串的最大长度
typedef struct{
    char ch[MAXLEN + 1]; // 存储串的一位数组
    int length; // 串的当前长度
} SString;

在C语言中,存在一个称之为“堆”(Heap) 的自由存储区,可以 为每个新产生的串动态分配一块实际串长所需的存储空间,若分配成功,则返回一个指向起始地址的指针,作为串的基址,同时为了以后处理方便,约定串长也作为存储结构的一部分。这种字符串的存储方式也称为串的堆式顺序存储结构。 

串的堆式顺序存储结构 

typedef struct{
    char *ch; // 若是非空串,则按串长分配存储区,否则 ch 为NULL
    int length; // 串的当前长度
} HString;

2)串的链式存储 

 用链表存储串值时,存在一个“结点大小”的问题,即每个结点可以存放一个字符,也可以存放多个字符

 数据结构题集c语言版严蔚敏_数据结构c语言版严蔚敏pdf第四版

(a)所示为 结点大小为 4 (即每个结点存放 4 个字符)的链表,图 4.3 (b)所示为结点大小为 1 的链表 

当结点大小大于 1 时,由于串长不一定是结点大小的整倍数,则链表中的最后一个结点不一定全被串值占满,此时通常补上”#”或其他的非串值字符(通常”#”不属于串的字符集,是一个特殊的符号) 

为了便于进行串的操作,当以链表存储串值时,除头指针外,还可附设一个尾指针指示链
表中的最后一个结点,并给出当前串的长度。称如此定义的串存储结构为块链结构。 

串的链式存储结构 

#define CHUNKSIZE 80 // 可由用户定义的块大小

typedef struct CHUNK{
    char ch[CHUNKSIZE];
    struct Chunk *next;
} Chunk;

typedef struct{
    Chunk *head,*tail; // 串的头尾指针
    int length; // 串的当前长度
} LString;

在链式存储方式中,结点大小的选择直接影响着串处理的效率。

 一般来说,字符集小,则字符的机内编码就短,这也影响串值存储方式的选取。

串值的链式存储结构对某些串操作,如联接操作等,有一定方便之处,但总地说来,不如顺序存储结构灵活,它占用存储量大且操作复杂。

2.2、串的模式匹配算法 

子串的定位运算通常称为串的模式匹配或串匹配。

串的模式匹配设有两个字符串S和T, 设S为主串,也称正文串;设T为子串,也称为模式。 

1)BF 算法 

最简单直观的模式匹配算法是 BF (Brute-Force) 算法

最好情况下的平均时间复杂度是 O(n + m)

最坏情况下的平均时间复杂度是 O(n * m) 

步骤: 

  1. 分别利用计数指针 i 和 j 指示主串 S 和模式 T 中当前正待比较的字符位置,i 初值为 pos,j 初值为 1
  2. 如果两个串均未比较到串尾,即 i 和 j 均分别小于等于 S 和 T 的长度时,则循环执行以下操作:
    1. S[i].ch 和 T[j].ch 比较,若相等,则 i 和 j 分别指示串中下个位置,继续比较后续字符
    2. 若不等,指针后退重新开始匹配,从上一次匹配主串的起始位置的下一个字符(i = i – j + 2)起再重新和模式的第一个字符(j = 1)比较
  3. 如果 j > T.length ,说明模式 T 中的每个字符依次和主串 S 中的一个连续的字符序列相等,则匹配成功,返回和模式 T 中第一个字符相等的字符在主串 S 中的序号(i – T.length);否则称匹配不成功,返回 0 
int Index_BF(SString S,SString T,int pos){
    // 返回模式 T 在主串 S 中的第 pos 个字符开始第一次出现的位置,若不存在,则返回值为 0
    // 其中,T 非空,1 ≤ pos ≤ S.length
    i = pos;
    j = 1; // 初始化
    while(i <= S.length && j <= T.length){ // 两个串均未比较到串尾
        if(S[i].ch == T[j].ch){ // 继续比较后继字符
            ++i;
            ++j;
        }else{ // 指针后退重新开始匹配
            i = i - j + 2; // 上一次匹配主串的起始位置的下一个字符
            j = 1;
        }
    }
    if(j > T.length)
        return i - T.length; // 匹配成功
    else
        return 0; // 匹配失败
}

数据结构题集c语言版严蔚敏_数据结构c语言版严蔚敏pdf第四版

 BF 算法的匹配过程

2)KMP 算法 

这种改进算法是由 Knuth 、 Morris 和 Pratt 同时设计实现的, 因此简称 KMP 算法。

此算法可以在 O(n + m) 的时间数量级上完成串的模式匹配操作。 

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

当匹配过程中产生 “失配” 时,指针 i 不变,指针 j 退回到 next[j] 所指示的位置上重新进行比较,并且当 指针 j 退至零时,指针 i 和指针 j 需同时增 1。即若主串的第 i 个字符和模式的第 1 个字符不等,应从主串的第 i + 1个字符起重新进行匹配。 

int Index_KMP(SString S,SString T,int pos){
    // 利用模式串 T 的 next 函数求 T 在主串 S 中第 pos 个字符之后的位置
    // 其中,T 非空,1 ≤ pos ≤ S.length
    i = pos;
    j = 1; // 初始化
    while(i <= S.length && j <= T.length){ // 两个串均未比较到串尾
        if(j == 0 || S[i] == T[j]){ // 继续比较后继字符
            ++i;
            ++j;
        }else{ // 模式串向后移动
            j = next[j];
        }
    }
    if(j > T[0])
        return i - T[0]; // 匹配成功
    else
        return 0; // 匹配失败
}

计算 next 函数值 

// 时间复杂度为O(m)。
// 通常,模式串的长度m比主串的长度n要小得多,对整个匹配算法来说,所增加的
这点时间是值得的。
void get_next(SString T,int next[]){
    // 求模式串 T 的 next 函数值并存入数组 next
    i = 1;
    next[1] = 0;
    j = 0;
    while(i < T[0]){
        if(j == 0 || T[i] == T[j]){
            ++i;
            ++j;
            next[i] = j;
        }else{
            j = next[j];
        }
    }
}

计算 next 函数修正值 

void get_nextVal(SSTring T,int nextVal[]){
    // 求模式串 T 的 next 函数修正值并存入数组 nextVal
    i = 1;
    nextVal[1] = 0;
    j = 0;
    while(i < T[0]){
        if(j == 0 || T[i] == T[j]){
            ++i;
            ++j;
            if(T[i] != T[j]){
                nextVal[i] = j;
            }else{
                nextVal[i] = nextVal[j];
            }
        }else{
            j = nextVal[j];
        }
    }
}

 

二、数组

 1、数组的定义

数组是由类型相同的数据元素构成的有序集合。

数组中每个元素处于 n(n ≥ 1) 个关系中,故称该数组为 n 维数组。

特点是结构中的元素本身可以是具有某种结构的数据, 但属于同一数据类型。 

 

2、特殊矩阵的压缩存储 

所谓压缩存储,是指为多个值相同的元只分配一个存储空间, 对零元不分配空间。

假若值相同的元素或者零元素在矩阵中的分布有一定规律,则称此类矩阵为特殊矩阵。 

1)对称矩阵 

若 n 阶矩阵A中的元满足下述性质 a_{ij} = a_{ji} 1 ≤ i,j ≤ n 则称为 n 阶对称矩阵。
对于对称矩阵,可以为每一对对称元分配一个存储空间,则可将 n^{2} 个元压缩存储到 \frac{n(n +1)}{2} 个元的空间中。 

2)三角矩阵 

上三角矩阵是指矩阵下三角(不包括对角线)中的元均为常数 c 或零的 n 阶矩阵, 下三角矩阵与之相反。 

3)对角矩阵 

对角矩阵所有的非零元都集中在以主对角线为中心的带状区域中,即除了主对角线上和直接在对角线上、下方若干条对角线上的元之外,所有其他的元皆为零。 

4)稀疏矩阵 

非零元较零元少,且分布没有一定规律, 称之为稀疏矩阵。 

 

三、广义表 

3.1、广义表的定义 

广义表是线性表的推广,也称为列表。 

在线性表的定义中,a_{i}(1 ≤ i ≤ n)只限于是单个元素。

而在广义表的定义中,ai可以是单个元素,也可以是广义表,分别称为广义表 LS 的原子和子表。

习惯上,用大写字母表示广义表的名称,用小写字母表示原子。

广义表的定义是一个递归的定义。 

例子:

(1) A = () —— A 是一个空表, 其长度为零

(2) B=(e) —— B 只有一个原子 e, 其长度为 1

(3) C= (a, (b, c, d)) —— C的长度为2, 两个元素分别为原子 a 和子表(b,c, d)。

(4) D = (A, B, C) —— D 的长度为3,3个元素都是广义表。显然,将子表的值代入后,则有 D = ((), (e), (a, (b, c, d)))。

(5) E = (a, E) —— 这是一个递归的表, 其长度为2。E 相当于一个无限的广义表 E=(a, (a,(a, ···)))。 

结论:

  • 广义表的元素可以是子表,而子表的元素还可以是子表。
  • 广义表可为其他广义表所共享。
  • 广义表可以是一个递归的表,即广义表也可以是其本身的一个子表。 

广义表最重要的两个运算:

  • 取表头 GetHead(LS):取出的表头为非空广义表的第一个元素,它可以是一个单原子,也可以是一个子表。
  • 取表尾 GetTail(LS):取出的表尾为除去表头之外,由其余元素构成的表。即表尾一定是一个广义表。 

 

3.2、广义表的存储结构 

由于广义表中的数据元素可以有不同的结构(或是原子,或是列表),因此难以用顺序存储结构表示,通常采用链式存储结构。

常用的链式存储结构有两种, 头尾链表的存储结构 和 扩展线性链表的存储结构 。 

1)头尾链表的存储结构 

一对确定的表头和表尾可唯一确定广义表。

一个表结点可由3个域组成:标志域、 指示表头的指针域和指示表尾的指针域。

原子结点只需两个域 :标志域和值域。 

数据结构题集c语言版严蔚敏_数据结构c语言版严蔚敏pdf第四版

广义表的头尾链式存储结构 

typedef enum{
    ATOM, // ATOM == 0:原子
    LIST // LIST == 1:子表
} ElemTag;

typedef struct GLN ode{
    ElemTag tag; // 公共部分,用于区分原子结点和表结点
    union{
        AtomType atom; // atom是原子结点的值域,AtomType有用户定义
        struct{
            struct GLN ode *hp,*tp;
        }ptr; // ptr是表结点的指针域,ptr.hp和ptr.tp分别指向表头和表尾
    };
}*GList; // 广义表类型

数据结构题集c语言版严蔚敏_数据结构c语言版严蔚敏pdf第四版 

  • 除空表的表头指针为空外,对任何非空广义表,其表头指针均指向一个表结点, 且该结点中的 hp 域指示广义表表头(或为原子结点,或为表结点),tp 域指向广义表表尾(除非表尾为空,则指针为空,否则必为表结点)
  • 容易分清列表中原子和子表所在层次
  • 最高层的表结点个数即为广义表的长度

 

2)扩展线性链表的存储结构 

在这种结构中, 无论是原子结点还是表结点均由三个域组成。 

数据结构题集c语言版严蔚敏_数据结构c语言版严蔚敏pdf第四版

数据结构题集c语言版严蔚敏_数据结构c语言版严蔚敏pdf第四版

扩展线性链表表示的存储结构示例 

一  叶  知  秋,奥  妙  玄  心 

今天的文章数据结构题集c语言版严蔚敏_数据结构c语言版严蔚敏pdf第四版分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/84006.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注