2019考研计算机：数据结构知识点整理（4）

考研网

下面是新东方在线整理的2019考研计算机专业课资料：数据结构的知识点整理，请参考：
    计算机专业考研复习教材推荐：
    数据结构：清华大学出版社《数据结构》严蔚敏主编
    计算机组成原理：高等教育出版社《计算机组成原理(第2版)》唐朔飞主编
    操作系统：西安电子科技大学出版社《计算机操作系统(第3办版)》汤小丹等主编
    计算机网络：《计算机网络(第5版》谢希仁主编
    　　第三章 串知识点整理
    串是零个或多个字符组成的有限序列。
    ·空串：是指长度为零的串，也就是串中不包含任何字符(结点)。
    ·空白串：指串中包含一个或多个空格字符的串。
    ·在一个串中任意个连续字符组成的子序列称为该串的子串，包含子串的串就称为主串。
    ·子串在主串中的序号就是指子串在主串中首次出现的位置。
    ·空串是任意串的子串，任意串是自身的子串。
    串分为两种：
    ·串常量在程序中只能引用不能改变;
    ·串变量的值可以改变。
    串的基本运算有：
    ·求串长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)。链串上的子串定位运算位移是结点地址而不是整数