精华内容
下载资源
问答
  • 串濮阳市第一高级中学 ;字符变量定义Var x:ch;Ord(x)对于字符来说是求字;廓屉贱锥样港呈棕少篷慑疏鼻贺甭;回顾知识点字符类型的概念回顾 ;字符型数据可以是字母符号数;ord(1=1)=1 ;...字符串的操作一字符串
  • 串的存储结构 串的模式匹配算法 1.串的存储结构 串的定长顺序存储表示 //定长顺序存储表示结构体定义如下: typedef struct { char str[maxsize+1]; int length; }str; //maxsize为已经定义的常量,表示...

    本节学习脉络

    • 串的存储结构
    • 串的模式匹配算法

    1.串的存储结构

    在这里插入图片描述

    • 串的定长顺序存储表示

    在这里插入图片描述

    //定长顺序存储表示结构体定义如下:
    typedef struct
    {
       char str[maxsize+1];
       int length;
     }str;
     //maxsize为已经定义的常量,表示串的最大长度,str数组长度定义为maxsize+1是因为多出一个‘\0’作为结束标记
    
    • 串的变长分配存储表示

      即动态分配存储表示,特点是在程序执行过程中根据需要动态分配。这种存储方式在使用时需要用函数malloc()来分配一个长度为length,类型为char型的连续存储空间,分配的空间可以用函数free()释放掉。用函数malloc()分配存储空间如果成功,则返回一个指向起始地址的指针,作为串的基地址,这个地址由ch指针指向,如果分配失败,则返回NULL。

    //其结构体定义如下:
    typedef struct
    {
      char *ch;  //指向动态分配存储区首地址的字符指针
      int length;//串长度
    }str;
    
    • 串的链式存储表示

    在这里插入图片描述

    • 基于顺序存储的一些常用基本操作

    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述

    2.串的模式匹配算法

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    附上代码

    //第一种方法
    #include <stdio.h> 
     
    //pos是从1开始的一个下标
    int index_force(char * s, char * t)
    {
     
       int i=0;
        int j=0;
        while(s[i]!='\0' && t[j]!='\0') {	//主串或者模式串遍历完成
            if(s[i]==t[j]) {				//如果主串和模式串对应位置的值相等,则比较后面的字符
                ++i;
                ++j;
            }
            else {							//如果不相等,则模式串需要回朔到第一个字符,而主串则从下一个字符开始
                i=i-j+1;
                j=0;
            }
        }
        if(t[j]=='\0') {					//如果循环是由于模式串遍历完了而结束的,说明找到了对应子串的位置
            return i-j+1;
        }
        else  {								//否则,主串不包含模式串
            return 0;
        }
    }
    int main (void){						//用于测试的主函数 
    	char *p="abcdefgh";					//主串 
    	char *q="fg";						//模式串 
    	int index;
    	index=index_force(p,q);
    	printf("%d\n",index);				//输出结果 
    }
    
    
    //第二种方法
    #include <stdio.h>
    #include <string.h>
    
    int  index (char S[],char T[]){
         int  i=1,j=1;//下标从1开始
         int  lenS,lenT; 
         lenS=strlen(S)-1;//主串S实际长度
         lenT=strlen(T)-1;//子串T实际长度
    
         while ( i<=lenS && j<=lenT ){//i<S且j<T时循环
            if ( S[i] == T [j] ){//若两字符相等,则匹配下一位
                    ++i;
                    ++j;
            }
            else //S[i] != T[j] 两字符不相等
            {
                    i=i-(j-1)+1; //主串回到上次匹配的下一位
                    j=1; //子串从头开始匹配
                    //注: j-1 是这次循环中 主串较起始位置移动的字符数量 i-(j-1) 即这次循环的主串字符初始的位置 i-(j-1)+1 即下一次循环开始i的位置
            }
         }
        if ( j>lenT )  return i-lenT; //若j超出子串的下标 匹配成功
        else return 0; //否则 匹配失败
    }
    int main()
    {
        char S[]=" Mynameisbruceforce";//主串
        char T[]=" bruce";//子串
        int pos; //位置
        pos = index(S,T);
        printf("%d",pos);
        return 0;
    
    }
    
    

    这节的内容就整理完毕,之后会更新KMP算法(串的最后一讲哦!)2020.9.21.

    展开全文
  • 数据结构.ppt

    2020-07-19 18:29:21
    第回拿 数据类型特殊的线性表 4.1串类型的定义 4.2串的表示和实现 4.3串的模式匹配 4.4串的应用 4.1串类型的定义 串的特点:数据元素为字符或字符串的线性表叫做串 是由零个或多个字符组成的有限序列 本术语:长度空串...
  • 数据结构04

    2017-02-23 14:59:50
    第四章 串 ...计算机上非数值处理的对象基本上是...在不同类型的应用中,字符串具有不同的特点,要有效的实现字符串的处理,必须选用合适的存储结构。 4.1 串类型的定义 串 String由零个或多个字符组成的有限序列。 s

    第四章 串

    STL:string  http://blog.csdn.net/weixin_37289816/article/details/54716009

    计算机上非数值处理的对象基本上是字符串数据。

    在不同类型的应用中,字符串具有不同的特点,要有效的实现字符串的处理,必须选用合适的存储结构。

     

    4.1 串类型的定义

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

    s = 'a1a2a3...an'   n >= 0

    s 串名

    用单引号扩起来的字符序列是串的值

    n 串的长度

    空串:零个字符的串

    子串:串中任意个连续字符组成的子序列称为该串的字串

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

    相等:当且仅当两个串的值相等

     

    串的逻辑结构与线性表极为相似,区别仅在于串的数据对象约束为字符集。

    最小操作子集: 串赋值求串长 求子串 串比较 串连接

     

    4.2 串的表示和实现

    串的三种表示方法:

    1、定长顺序存储表示

       用一组连续的存储单元存储串值的字符序列,此时串的最大长度被限定。

       两种表示方法:

            1以下标为0的数组分量存放串的实际长度  PASCAL

            2在串值后面加一个不计入串长的结束标记字符,此时串长为隐含值  C语言中的'\0'

     

    2、堆分配存储表示

       在C语言中,存在一个称之为“堆”的自由存储区,由动态分配函数malloc()和free()管理。

       仍以一组连续的存储单元存储串值的字符序列,此时串的长度无限制。

       存储空间在程序执行过程中动态分配。

     

    3、块链存储表示

       块大小的选择

       头指针 尾指针串长度

       设置尾指针的目的:联结操作

     

    4.3 串的模式匹配算法

    串的模式匹配:字串的定位操作。

    KMP算法: O(n+m)

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

     

    匹配仅需从模式中第k个字符与主串中第i个字符继续进行比较:此时模式中头k-1个字符和主串中最后k-1个字符相同。

    亦即 next[1, j-1] 这个串中,前后缀相同串的字符为 next[1, next[j] - 1],所以下一次比较的是next[j]个字符的不同。

    next数组里存放的,相同前后缀子串,前子串位置的下一个位置坐标。

     

    next[j] = k : 当模式中第j个字符失配时,重新进行比较的位置。

    算法:

    假设主串指针i = pos,模式串指针j = 1;

    若si = pj,则i++, j++;

    否则j = next[j], 继续进行si 和pj 的比较。

    如果 j = 0, 则 i++, j++, 继续进行si和 pj的比较。

     

    KMP算法的基础是next函数值,仅和模式串本身有关。

    求next[j + 1] 的方法:

    next[1] = 0;

    next[j] = k;

    若 pk = pj,next[j + 1] = k +1;

    若 pk!=pj,k = next[k],继续进行pk和 pj的比较。若k = next[k] = 0,则next[j + 1] = 1。

     

     

    i = 1;
    next[1] = 0;
    j = 0;
    while (i < length)
    {
        if (j == 0 || T[i] == T[j])
            i++; j++; next[i] = j;
        else
            j = next[j];
    }

     

     

     

    两点说明:

    1、简单算法的时间复杂度虽然是O(n*m),但在一般情况下,其实际执行时间近似于O(n+m),因此至今仍被采用。

    KMP算法仅当模式与主串之间存在许多“部分匹配”的情况下才显得比简单算法快得多。

    KMP算法的最大特点:无需回溯,整个匹配过程,对主串仅需从头至尾扫描一遍,这对处理从外设输入的庞大文件很有效,可以边读入边匹配,而无需回头重读。

    2、next函数的修正算法 针对连续字符的改进

     

    i = 1;
    next[1] = 0;
    j = 0;
    while (i < length)
    {
        if (j == 0 || T[i] == T[j])
            i++; j++;
            if (T[i] != T[j])  next[i] = j;
            else next[i ] = next[j];
        else
            j = next[j];
    }

     

     

     

     

     

    4.4 串操作应用举例:

    文本编辑

    文本编辑程序是一个面向用户的系统服务程序,文本编辑的实质是修改字符数据的形式或格式。

    虽然各文本编辑程序的功能强弱不同,但基本操作是一致的,一般包括串的查找、插入、删除等。

    可以利用换页符和换行符把文本划分为若干页,每页有若干行。

    把文本看成是一个字符串,称为文本串。页是文本串的子串,行是页的子串。

     

    为了管理文本的页和行,在进入文本编辑的时候,编辑程序先为文本串建立相应的页表和行表,即建立各子串的存储映像。

    页表的每一项给出页号和该页的起始行号。

    行表的每一项指示行号、起始地址和该字串的长度。

    设立页指针、行指针、字符指针,分别指向当前操作的页、行、字符。

    页表和行表是递增顺序存储的,对行表进行的插入或删除运算需移动操作位置以后的全部表项。

    Tip:由于访问是以页表和行表作为索引的,所以在作行和页的删除操作时,可以只对行表和页表作相应的修改,不必删除所涉及的字符,这样可以节省时间。

     

     

    建立词索引表

    信息检索。

    可设定此索引表为按字典有序的线性表。

     

    重复下列操作直至文件末尾:

    1、从书目文件中读取一个书目串

    2、从书目串中提取所有关键词插入词表

    3、对词表中的每一个关键词,在索引表中进行查找并作相应的插入操作。

     

    需要一张常用词表,不在常用词表中的字符串为关键字。

    索引表虽是动态生成,在生成过程中需频繁进行插入操作,但考虑索引表主要为查找用,为了提高查找效率,宜采用顺序存储结构

    索引表内容:关键词 + 书号索引。

    书号索引采用链式存储结构。

     

    展开全文
  • Redis 提供了5种数据类型:String(字符)、Hash(哈希)、List(列表)、Set(集合)、Zset(有序集合),理解每种数据类型的特点对于redis的开发和运维非常重要。 二、疑问与解析  结构图上显示,...

    数据结构

    Redis通过sdsnewlen函数创建SDS。在函数中会根据字符串长度选择合适的类型,初始化完相应的统计值后,返回指向字符串内容的指针,根据字符串长度选择不同的类型
    在这里插入图片描述

    参考链接

    Redis极致设计-五大数据结构的底层结构原理
    jstarseven | String数据类型之底层解析

    展开全文
  • 本文主要讲解 数据结构的串,内容包括其特点、结构等,希望你们会喜欢。

    前言

    本文主要讲解 数据结构中的串,内容包括其特点、结构等,希望你们会喜欢。


    目录

    示意图


    1. 简介

    示意图


    2. 存储结构介绍

    包括:顺序存储结构 & 链式存储结构

    示意图


    3. 串的比较

    示意图


    4. 子串的定位

    • 子串定位 的主要任务是:确定主串是否存在子串 & 子串在主串中的位置

    子串的定位操作 也称 串的模式匹配

    • 下面主要讲解串模式匹配的重要方法:KMP模式匹配算法

    4.1 KMP模式匹配算法 简介

    示意图

    4.2 具体算法

    • 概念:字符串的前缀 & 后缀

    示意图

    • 具体使用
      步骤1:计算出子串(T串)各个位置的 j 值的变化
      步骤2:根据步骤1计算出的next数组,将子串与主串进行模式匹配

    示意图

    下面将重点讲解步骤1:计算出子串(T串)各个位置的 j 值的变化

    • 定义1数组:next [ j ] = 子串(T串)各个位置的 j 值的变化

    j 值仅取决于:T串 当前字符 前后缀字符的相似度

    • next [ j ]值的函数定义如下
      示意图

    • 举例说明

    示意图

    4.3 算法改进

    示意图


    5. 总结

    • 本文主要讲解了 数据结构中 串的知识,含 其特点、结构等

    • 下面我将继续对 数据结构进行讲解,有兴趣可以继续关注Carson_Ho的安卓开发笔记


    请帮顶 / 评论点赞!因为你的鼓励是我写作的最大动力!

    展开全文
  • 数据结构:字符ADT

    2020-05-03 20:13:04
    这片文章给大家讲解一下字符串。 1.字符串的逻辑结构 ...字符串的特点数据元素都是字符,使得它的操作的对象一般不再是点那个数据元素,而是一组数据元素(字符子串)。 2.字符串结构上定义的操作 ①字符...
  • 数据结构数组与

    2018-09-25 14:47:30
    串的基本概念、串的存储结构和相关的操作算法; 数组的存储结构,在顺序存储的情况下,数组元素与存储单元的对应关系; 稀疏矩阵的存储结构特点以及基本操作。 字符串匹配算法(例如KMP算法)。 串的定义:由一...
  • 数据结构- & KMP

    2018-04-02 13:22:19
    字符串的简称, 字符串本身就是一种数据结构, 由零个或者多个字符组成的有限序列(顺序存储结构) 串的定义及子串 定义 :在C语言中, 串可以用字符数组来定义: char str[] = "adrui"; 这里str 是...
  • [数据结构] -

    2019-06-16 21:39:00
    字符串(String)是由字符组成有限序列,是常用的一种非数值数据串的逻辑结构是线性表,串是一种特殊的线性表,限制其元素类型是字符,串的操作特点与线性表不同,主要对子串进行操作,通常采用顺序存储结构存储。...
  • 数据结构--字符

    2018-10-26 16:10:42
    今天要跟大家介绍数据结构当中字符,字符是由若干个字符组成序列,由于现今使用计算机硬件结构是面向数值计算需要而设计,在处理字符数据时比处理整数和浮点数要复杂得多,而且字符在编程时...
  • 数据结构》KMP 串的模式匹配

    千次阅读 2018-11-27 19:31:00
    题目 给定两个由英文字母组成字符 String 和 Pattern,要求找到 Pattern 在 String 中第一次...各组测试数据特点如下: 数据0:小规模字符,测试基本正确性; 数据1:随机数据,String 长度为 105^55​​​ ...
  • 串的堆分配存储表示的特点是,仍以一组地址连续的存储单元存放串值字符序列,但它们的存储空间是在程序执行过程中动态分配的。使用动态分配函数malloc()和函数free()来管理存储空间的大小。 串的堆分配存储方法具有...
  • 掌握这种抽象数据类型的特点;熟练掌握串的顺序存储结构表示和基本操作,并能利用这些基本操作实现串的其他各种操作。 实验要求: 定义串的定长顺序存储结构; 实现串赋值,求串长,求子串,串连接,串比较等...
  • 以一组地址连续的存储单元存放值字符...优点:堆分配存储结构既有顺序存储结构的特点,处理方便,操作中对长又没有任何限制,更加的灵活。 存储结构为:typedef struct { char *ch; int length; }HString
  • 数据结构之字符

    2019-10-20 21:37:19
    字符这一章的大体框架为: 1、模式匹配算法(BF,KMP) 2、多维数组的寻址,存储表示法 ...利用最长公共前后缀的特点,每次匹配失败后不需要从头开始。需要预先处理出前缀表,根据前缀表来判...
  • 那么它是怎么样一种结构呢?? 特点:字母个数不会很多,why? 来看代码实现吧 题目 AcWing835 Trie字符 维护一个字符集合,支持两种操作: “I x”向集合中插入一个字符x; “Q x”询问一个字符在...
  • 数据结构】字符

    2020-01-04 16:47:07
    字符String创建方式字符留驻特点字符操作函数StringBufferStringBuilderString 、StringBuffer与StringBuilder区别效率可变性JVM对String优化String s = new String ("字符")创建了几个字符对象被 ...
  • 数据结构第四章:

    2019-08-16 11:39:52
    不同的应用所处理的串的特点亦不相同。 在线性表的基本操作中,大多以“单个元素”作为操作对象,而在串中则是以“串的整体”或一部分作为操作对象。 串的定义: 串(String)是零个或多个字符组成的有限序列。 ...
  • redis 没有直接使用C语言传统的字符串,而是自己构建了一种名为简单动态字符串(simple ...先了解一下,C语言传统字符串的特点 1、以空字符串结尾的字符数组  2、SDS的数据结构  .free属性的值为0,表示这个SD...
  • 前言Redis用了这么久,一直没有认真去了解其内部的数据结构和实现原理。从今天开始正式系统性学习Redis。首先,还是从工作中经常打交道数据类型开始说起,然后,在说到其内部使用的数据结构。Redis简介Redis...
  • 的特点为后进先出(Last In First Out,LIFO)。下图为一个栈的示意图,通常用指针top指示栈顶的位置,用指针bottom指向栈底。栈顶指针top动态反映栈的当前位置。 栈的基本操作 栈的基本操作主要有以下六种。 ...
  • 思路:根据回文字符串的特点,如果以字符a为中心,各向两边扩散一个字符,这两个字符一样的话这个子串一定是回文子串,并且可以继续扩散;若扩散的两个字符不一样,那么这个子串一定不是回文子串,并且无法继续扩散...
  • 数据结构简介与特点

    千次阅读 2017-05-18 17:38:46
    数据结构简介与特点线性表 顺序表 单链表 循环链表 双向循环链表 静态链表 栈 顺序栈 链栈 队列 顺序队列 链队列 循环队列 串 串的定长存储 串的堆分配存储 串的块链存储 树 树的双亲表示法 树的孩子兄弟表示法 ...
  • KMP 串的模式匹配 (25 分) 给定两个由英文字母组成的字符串 String 和 Pattern,要求找到 Pattern 在 String 中第一次出现的位置,并将此位置后的 String 的子串输出。如果找不到,则输出“Not Found”。 本题旨在...
  • 专栏原创出处:github-源笔记文件 ,github-源码 ,欢迎 Star,转载请附上原文出处链接和本声明。...数组是一种基本的数据结构,用于按顺序存储元素集合。但是元素可以随机存取,因为数组中每...
  • 数组、字符是两种最基本的数据结构,使用连续内存分别存数字和字符,并按照顺序存储。 特点 数组在创建时需要指定大小,按大小分配内存,因此空间效率较低,常有空闲区域未利用。由于数组内存连续,可根据下标...
  • 1、字符串定义和特点定义:一个个字符组成的...2、不可变的,有序,连续空间,可迭代3、Python3起,字符串就是Unicode类型2、字符串的定义,初始化:举例:s = 'strint's= "string"s= '''string'''s= 'hello \nwor...
  • 书上说的:“在处理字符串数据时,会比处理整数或浮点数要复杂的多,且在不同类型的应用中,所用的字符有不同的特点。所以要想有效的实现字符处理,就必须根据具体的情况使用合适的储存结构。”我想,这因该是这...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,501
精华内容 1,000
关键字:

串的特点数据结构

数据结构 订阅