2020考研计算机《数据结构(C语言版)》复习笔记(4)
2019.05.23 14:25

  2020年计算机考研复习已经开始,新东方在线在此整理了2020考研计算机《数据结构(C语言版)》复习笔记(4),希望能帮助大家!

  第三章 串知识点整理

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

  ·空串:是指长度为零的串,也就是串中不包含任何字符(结点)。

  ·空白串:指串中包含一个或多个空格字符的串。

  ·在一个串中任意个连续字符组成的子序列称为该串的子串,包含子串的串就称为主串。

  ·子串在主串中的序号就是指子串在主串中首次出现的位置。

  ·空串是任意串的子串,任意串是自身的子串。

  串分为两种:

  ·串常量在程序中只能引用不能改变;

  ·串变量的值可以改变。

  串的基本运算有:

  ·求串长strlen(char*s)

  ·串复制strcpy(char*to,char*from)

  ·串联接strcat(char*to,char*from)

  ·串比较charcmp(char*s1,char*s2)

  ·字符定位strchr(char*s,charc)

  串是特殊的线性表(结点是字符),所以串的存储结构与线性表的存储结构类似。串的顺序存储结构简称为顺序串。

  顺序串又可按存储分配的不同分为:

  ·静态存储分配:直接用定长的字符数组来定义。优点是涉及串长的操作速度 快,但不适合插入、链接操作。

  ·动态存储分配:是在定义串时不分配存储空间,需要使用时按所需串的长度分配存储单元。

  串的链式存储就是用单链表的方式存储串值,串的这种链式存储结构简称为链串。链串与单链表的差异只是它的结点数据域为单个字符。

  为了解决“存储密度”低的状况,可以让一个结点存储多个字符,即结点的大小。

  顺序串上子串定位的运算:又称串的“模式匹配”或“串匹配”,是在主串中查找出子串出现的位置。在串匹配中,将主串称为目标(串),子串称为模式(串)。这是比较容易理解的,串匹配问题就是找出给定模式串P在给定目标串T中首次出现的有效位移或者是全部有效位移。最坏的情况下时间复杂度是O((n-m+1)m),假如m与n同阶的话则它是O(n^2)。链串上的子串定位运算位移是结点地址而不是整数


MORE+

    相关阅读 MORE+

    版权及免责声明
    1.凡本网注明"稿件来源:新东方在线"的所有文字、图片和音视频稿件,版权均属北京新东方迅程网络科技有限公司所有,任何媒体、网站或个人未经本网协议授权不得转载、链接、转贴或以其他方式复制发表。已经本网协议授权的媒体、网站,在下载使用时必须注明"稿件来源:新东方在线",违者本网将依法追究责任。
    2.本网末注明"稿件来源:新东方在线"的文/图等稿件均为转载稿,本网转载出于传递更多信息之目的,并不意味着赞同其观点或证实其内容的真实性。如其他媒体、网站或个人从本网下载使用,必须保留本网注明的"稿件来源",并自负版权等法律责任。如擅自篡改为"稿件来源:新东方在线”,本网将依法追究责任。
    3.如本网转载稿涉及版权等问题,请作者致信weisen@xdfzx.com,我们将及时外理

    Copyright © 2011-202

    All Rights Reserved