精华内容
下载资源
问答
  • 本文主要介绍数据结构与算法的知识点,包括线性表、数组和广义表、栈和队列、树和二叉树、图、查找、排序等,如有不当之处,敬请指正,感谢各位大佬!有些问题不免解释不全面或者暂时未回答(先留坑),欢迎各位读者...

    整理不易,手有余香请点个赞吧!

    本文主要介绍数据结构与算法的知识点,包括线性表、数组和广义表、栈和队列、树和二叉树、图、查找、排序等,如有不当之处,敬请指正,感谢各位大佬!有些问题不免解释不全面或者暂时未回答(先留坑),欢迎各位读者踊跃解答哈!

    数据结构

    线性表

    栈和队列

    字符串

    1. 写最大串匹配算法

    数组和广义表

    树存储结构

    1. 二叉树深度优先遍历的递归和循环实现

    2. 二叉树层次(广度)遍历

    3. 求完全二叉树节点数方法1:当做普通二叉树,递归求解;

    方法2:根据完全二叉树左右深度是否相等进行,若相等则用公式计算节点数,若不相等则继续递归。

    图存储结构

    查找表结构

    1. 写二分查找

    2. Hash冲突解决方法开放定址法:线性探测法:d=1,2,3,…,m-1

    二次探测法:d=12,-12,22,-22,32,…

    伪随机数探测法:d=伪随机数

    再哈希法

    链地址法

    建立一个公共溢出区

    排序算法

    1. 写快速排序

    2. 写堆排序算法C++中,set和multiset都是基于红黑树实现,查找、删除、插入操作都只需O(logk)时间。

    基础理论

    1. 理解递归

    基础算法

    1. 找链表倒数第k个节点

    2. 从尾到头打印链表

    3. n阶台阶每次只能跨一步或两步,求路径总数。动态规划,从上到下分析问题,从下到上编码实现。

    4. 已知两矩形的x1,y1,x2,y2,求交集面积。

    x11, y11, x12, y12 = []

    x21, y21, x22, y22 = []

    def calc_intersection(bbox1, bbox2):

    """calc_intersection"""

    xmingt, ymingt, xmaxgt, ymaxgt = bbox1

    xminpre, yminpre, xmaxpre, ymaxpre = bbox2

    xmin = max(xmingt, xminpre)

    ymin = max(ymingt, yminpre)

    xmax = min(xmaxgt, xmaxpre)

    ymax = min(ymaxgt, ymaxpre)

    w = xmax - xmin

    h = ymax - ymin

    if w <= 0 or h <= 0:

    return 0

    return w * h

    5. n+1长的无序数组,数分布为1~n,只有1个数重复,找出重复数;要求:不能改原数组,空间复杂度<=o(1),时间复杂度<=o(n)方法1:求数组中重复元素 位操作。所有元素逐个求异或操作,再与range(1,n)的数字逐个求异或操作;所得结果为重复数字与n+1的异或结果,可反推出唯一重复数字。

    方法2:数值二分法。统计数值区间中,数的个数;如数值区间[1,n/2](不是数组下标值的二分)中,数的个数是否大于n/2个,大于则此区间内必有重复数;继续数值二分,直到找到该数。

    def search_duplication(array):

    """search_duplication"""

    n = len(array)

    if n > 1:

    xor_res = None

    for a in array + list(range(1, n+1)):

    xor_res ^= a

    return xor_res ^ n

    return None

    6. n*n矩阵,逆时针旋转90度。

    # coding: utf-8

    def rotation90_anticw(arr, n, res):

    """rotation90_anticw"""

    if n == 0 or not arr:

    return

    if not len(res) == n or not len(res[0]) == n:

    return

    r, c = 0, 0

    for jj in range(n-1, -1, -1):

    c = 0

    for ii in range(0, n):

    res[r][c] = arr[ii][jj]

    c += 1

    r += 1

    return res

    if __name__ == '__main__':

    n = 5

    arr = [[1,2,3,4,5],

    [6,7,8,9,10],

    [11,12,13,14,15],

    [16,17,18,19,20],

    [21,22,23,24,25]]

    res = [[-1,-1,-1,-1,-1],

    [-1,-1,-1,-1,-1],

    [-1,-1,-1,-1,-1],

    [-1,-1,-1,-1,-1],

    [-1,-1,-1,-1,-1]]

    print(rotation90_anticw(arr, n, res))

    7. a, b两数组里面都存放不重复的int数,但a和b有重复数,找出。

    8. 判断两个字符串是否模式一致两个字符串中包含多个单词,单词与单词用空格隔开,判断两个字符串是否模式一致。模式一致定义为重复和不重复单词出现的位置一致。

    模式一致样例:A = 'hey hey I am your brother, hey'

    B = 'oh oh you are here ? oh'

    模式不一致样例:A = 'X Y X Y Z'

    B = 'P Q P Q R'

    def is_same_pattern(A, B):

    a_parts = A.split(' ')

    b_parts = B.split(' ')

    if len(a_parts) != len(b_parts):

    return False

    words_dict_a = {}

    words_dict_b = {}

    idx_a = 0

    idx_b = 0

    for ii in range(len(a_parts)):

    # a

    if a_parts[ii] not in words_dict_a.keys():

    words_dict_a[a_parts[ii]] = idx_a

    idx_a += 1

    # b

    if b_parts[ii] not in words_dict_b.keys():

    words_dict_b[b_parts[ii]] = idx_b

    idx_b += 1

    # judge

    if words_dict_a[a_parts[ii]] != words_dict_b[b_parts[ii]]:

    return False

    return True

    9. 数组按个位数排序

    10. 计算1到n每个数的阶乘求和

    11. 手环有十项运动,根据用户点击次数进行智能排序;需要什么数据;排序用的数学模型是什么

    编程语言

    C++

    1. C++11新特性,5个

    2. STL中vector和map区别vector是连续地址存储,三个指针指向first,last,end;

    map是键值对序列,可以用平衡二叉树存储;

    3. set/multiset, map/multimap使用set或multiset之前,必须加入头文件;

    set、multiset都是集合类,差别在与set中不允许有重复元素,multiset中允许有重复元素;

    sets和multiset内部以平衡二叉树(红黑树)实现。

    sets和multiset可以看成一个序列,查找、插入、删除一个数都能够在O(logn)的时间内完成,而且他能时刻保证序列中的数是有序的。

    set c; // 创建空集合,不包含任何元素set c(op); // 以op为排序准则,产生一个空的setset c1(c2); // 复制c2中的元素到c1中set c(const value_type *first, const value_type* last); // 复制[first, last)之间元素构成新集合set c(const value_type *first, const value_type* last,op); // 以op为排序准则,复制[first, last)之间元素构成新集合。c.~set(); // 销毁所有元素,释放内存

    multiset mc; // 创建空集合,不包含任何元素multiset mc(op); // 以op为排序准则,产生一个空的setmultiset c1(c2); // 复制c2中的元素到c1中multiset c(const value_type *first, const value_type* last); // 复制[first, last)之间元素构成新集合multiset c(const value_type *first, const value_type* last,op); // 以op为排序准则,复制[first, last)之间元素构成新集合。c.~set(); // 销毁所有元素,释放内存

    4. 各个常用数据容器的特点,优缺点及适用场景数组、链表、二叉搜索树、平衡二叉树(AVL树)

    最大堆最小堆数据结构插入的时间复杂度得到中位数的时间复杂度

    没有排序的数组O(1)O(n)

    排序的数组O(n)O(1)

    排序的链表O(n)O(1)

    二叉搜索树平均O(logn),最差O(n)平均O(logn),最差O(n)

    AVL树O(logn)O(1)

    最大堆最小堆O(logn)O(1)

    5. make_heap(), pop_heap(), push_heap()make_heap()是生成一个堆,大顶堆或小顶堆make_heap(_RAIter,_RAIter) # 默认生成大顶堆

    make_heap(_RAIter,_RAIter,_Compare) # _Compare有两种参数,一种是greater(生成小顶堆),一种是less(生成大顶堆)

    push_heap()是向堆中插入一个元素,并且使堆的规则依然成立push_heap(_RAIter,_RAIter) # 默认为大顶堆

    push_heap(_RAIter,_RAIter,_Compare) # _Compare有两种参数,一种是greater(小顶堆),一种是less(大顶堆)

    调用push_heap之前必须调用make_heap创建一个堆

    首先数组push_back插入元素,然后再调用push_heap,它会使最后一个元素插到合适位置

    注意,push_heap中的_Compare和make_heap中的_Compare参数必须是一致的,不然会插入堆失败,最后一个元素还是在最后位置,导致插入失败

    pop_heap()是在堆的基础上,弹出堆顶元素pop_heap(_RAIter,_RAIter) # 默认为大顶堆

    pop_heap(_RAIter,_RAIter,_Compare) # _Compare有两种参数,一种是greater(小顶堆),一种是less(大顶堆)

    比如pop_heap(nums.begin(), nums.end(),greater()),它会将堆顶元素(即为数组第一个位置)和数组最后一个位置对调,然后你可以调用数组pop_back,删除这个元素

    注意,pop_heap中的_Compare和make_heap中的_Compare参数必须是一致的,不然会失败

    6. 比较仿函数less和greater

    sort(vec.begin(), vec.end(), less());

    push_heap(nums.begin(), nums.end(), greater());

    pop_heap(nums.begin(), nums.end(), greater());

    7. C++常见问题

    Python

    1. python函数的值传递、引用传递什么时候发生值传递就发生在实参为不可变对象时,而引用传递发生在实参为可变对象时。不可变对象:如 数字,元组,字符串;

    可变对象:如 列表,字典。

    在值传递中,不改变形式参数的值,而在引用传递中,形式参数的值是被改变的。

    2. python的type和objecttype可以实例化所有类,包括object;

    object是所有类的父类,包括type;

    type.__new__:type.__new__()调用的是type类的类方法__new__或者静态方法__new__

    type()是使用type的__init__()方法新建一个type实例或者调用type类的静态__call__()方法或者类方法__call__()

    (典型的就是求一个对象的类型type("Hello"))type(object) -> the object's type

    type(name, bases, dict) -> a new type

    3. python的虚函数、抽象方法、metaclass元类;

    4. 目录下所有文件如何遍历?

    os.walk()默认以topdown方式递归遍历根文件夹及其子文件夹。

    5. str.split(sep),sep是空格, \t, 还是正则

    6. 读取大文件,求最大值,最小值,均值,方差

    # data.txt

    # cat_id num

    # ......

    # cat_id min, max, mean, sample_variance

    form collections import defaultdict

    def read_file(file_path):

    assert os.path.exist(file_path)

    with open(file_path) as f:

    for line in f.readline():

    # split(sep) sep .strip()

    cat_id, num = line.split().strip()

    yield (int(cat_id), float(num))

    def statistics(file_path):

    table = defaultdict(list)

    for cat_id, num in read_file(file_path):

    if table.get(cat_id, None):

    min_val, max_val, mean_val, var_val, N = table[cat_id] # N is samples number of cat_id

    new_min_val = min_val if min_val < num else num

    new_max_val = max_val if max_val > num else num

    # >> 1

    new_mean_val = (mean_val + num) >> 1

    new_var_val = ((var_val * (N - 1)) + (num - new_mean_val) ** 2)) / N

    table[cat_id]= [new_min_val, new_max_val, new_mean_val, new_var_val, N + 1]

    else:

    table[cat_id] = [num, num, num, 0, 1]

    return table

    操作系统

    1. linux删除后空间未释放

    2. 查找端口号为8080的进程

    3. sed字符串替换

    展开全文
  • 基本概念

    串:由零个或多个任意字符组成的有限序列。
    串长度:串中所包含的字符个数。
    空串:长度为0的串,记为:“”。
    非空串:S = “a1, a2…, an”
    其中,双引号是定界符
    两个串相等:如果两个串的长度相等且对应字符都相等。
    子串:串中任意连续的字符组成的子序列称为子串。
    主串:包含子串的串。
    子串的第一个字符在主串中的序号称为子串的位置。

    顺序串

    如何表示串的长度?

    1. 用一个变量来表示串的长度。
      在这里插入图片描述

    2. 在串尾存储一个不会在串中出现的特殊字符作为串的终结符。
      在这里插入图片描述

    3. 用数组的0号单元存放串的长度,串值从1号单元开始存放。
      在这里插入图片描述

    链串

    1. 非压缩形式
      在这里插入图片描述

    2. 压缩形式
      在这里插入图片描述

    串的基本操作算法

    1. 串的复制 strcpy(字符数组名1,字符数组名2)
    2. 串的连接 strcat(字符数组名1,字符数组名2)
    3. 串的比较 strcmp(字符数组名1,字符数组名2)

    BF算法

    从主串s中下标为0的字符开始,与模式串t中下标为0的字符比较,若相同,则继续逐个比较s和t中的后续字符;若不同,从主串s中下标为1的字符开始,与模式串t中下标为0的字符比较。以此类推,重复上述过程,若t中字符全部比完,则说明匹配成功;否则匹配失败。

    写法1

    int BFMatch(char *s, char *t)
    {
    	int i = 0; 
    	int j = 0;
    	while(i<strlen(s) && j<strlen(t))
    	{
    		if(s[i] == t[j])
    		{i++;
    		j++;}
    		else 
    		{i = i-j+1; 
    		j = 0;}
    	}
    	if(j>=length(t)) return i;
    	else return -1;
    }
    

    写法2

    int BF(char *s, char *t)
    {
    	for(i = 0; i < strlen(s); i++)
    	{
    		for(j = 0; j < strlen(t); j++)
    		{
    			int tmp = i;
    			if(s[tmp] == t[j])
    				tmp++;
    			else break;
    		}
    		if(j>=strlen(t)) return i-j;
    	}
    	return -1;
    }
    
    展开全文
  • 3. 串的抽象数据类型 4. 串的存储结构 4.1 串的顺序存储结构 4.2 串的链式存储结构 5. 朴素的模式匹配算法 6. KMP模式匹配算法 1. KMP模式匹配算法原理 2. next数组值推荐 3. KMP模式匹配算法实现 4. KMP...

    目录

    1. 串的定义

    2. 串的比较

    3. 串的抽象数据类型

    4. 串的存储结构

    4.1 串的顺序存储结构

    4.2 串的链式存储结构

    5. 朴素的模式匹配算法

    6. KMP模式匹配算法

    1. KMP模式匹配算法原理

    2. next数组值推荐

    3. KMP模式匹配算法实现

    4. KMP模式匹配算法改进

    5. nextval数组值推导

    7. 总结


    串:串(string)是由零个或多个字符组成的有限序列,又叫字符串。

    在介绍串的基本知识点之前,先举个小例子,是关于诗句中的回文诗。

    我们古人没有电影电视,没有游戏网络,所以文人们就会想出一些文字游戏来娱乐。比如宋代的李禺写了这样一首诗:“枯眼望遥山隔水,往来曾见几心知?壶空怕酌一杯酒,笔下难成和韵诗。途路阻人离别久,讯音无雁寄回迟。孤灯夜守长寥寂,夫忆妻兮父忆儿。”显然这是老公想念老婆和儿子的诗句。曾经和妻儿在一起,尽享天伦之乐,现在一个人长久没有回家,也不见书信返回,望着油灯想念亲人,能不伤感吗?

    可再仔细一读发现,这首诗竟然可以倒过来读:“儿忆父兮妻忆夫,寂寥长守夜灯孤。迟回寄雁无音讯,久别离人阻路途。诗韵和成难下笔,酒杯一酌怕空壶。知心几见曾来往,水隔山遥望眼枯。”这表达了什么意思呢?哈哈,表达了妻子对丈夫的思念。老公离开好久,路途遥远,难以相见。写信不知道写什么,独自喝酒也没什么兴致。只能和儿子夜夜守在家里一盏孤灯下,苦等老公的归来。

    这种诗体叫做回文诗。它是一种可以倒读或反复回旋阅读的诗体。刚才这首就是正读是丈夫思念妻子,倒读是妻子思念丈夫的古诗。是不是感觉很奇妙呢?

    在英语单词中,同样有神奇的地方。“即使是lover也有个over,即使是friend也有个end,即使是believe也有个lie。”你会发现,本来不相干,甚至对立的两个词,却有某种神奇的联系。这可能是创造这几个单词的那些智者们也没有想到的问题。

    接下来谈谈这些单词或句子组成字符串的相关问题。

    1. 串的定义

    早先的计算机在被发明时,主要作用是做一些科学和工程的计算工作,也就是现在我们理解的计算器,只不过它比小小计算器功能更强大、速度更快一些。后来发现,在计算机上作非数值处理的工作越来越多,使得我们不得不需要引入对字符的处理。于是就有了字符串的概念。

    生活中有哪些比较常见关于串的应用呢?比如我们现在常用的搜索引擎,当我们在文本框中输入“数据”时,它已经把我们想要的“数据结构”列在下面了。显然这里网站作了一个字符串查找匹配的工作:

    我们先看看串的定义:

    串:串(string)是由零个或多个字符组成的有限序列,又叫字符串。

    一般记为s=“aia2……an”(n>0),其中,s是串的名称,用双引号括起来的字符序列是串的值,注意双引号不属于串的内容。a_{i}(1< i <n)可以是字母、数字或其他字符,i 就是该字符在串中的位置。串中的字符数目n称为串的长度,定义中谈到“有限”是指长度 n 是一个有限的数值。零个字符的串称为空串(null string),它的长度为零,可以直接用两双引号“ ”” ”表示,也可以用希腊 \Phi字母来表示。所谓的序列,说明串的相邻字符之间具有前驱和后继的关系。

    下面这些概念我们也清楚:

    1. 空格串,是只包含空格的串。注意它与空串的区别,空格串是有内容有长度的,而且可以不止一个空格。

    2. 子串与主串,串中任意个数的连续字符组成的子序列称为该串的子串,相应地,包含子串的串称为主串。

    3. 子串在主串中的位置就是子串的第一个字符在主串中的序号。

    前面提到的“over”“end”“lie”其实可以认为是“lover”“friend”“believe”这些单词字符串的子串。

    2. 串的比较

    两个数字,很容易比较大小。2比1大,这完全正确,可是两个字符串如何比较?

    比如“silly”、“stupid”这样的同样表达“愚蠢的”的单词字符串,它们在计算机中的大小其实取决于它们挨个字母的前后顺序。它们的第一个字母都是“s”,我们 认为不存在大小差异,而第二个字母,由于“ i ”字母比“ t ”字母要靠前,所以“ i ” < “ t ”,于是我们说 “silly” < “stupid”。

    事实上,串的比较是通过组成串的字符之间的编码来进行的,而字符的编码指的是字符在对应字符集中的序号

    计算机中的常用字符是使用标准的ASCII 编码,更准确一点,由7位二进制数表示一个字符,总共可以表示128个字符

    后来发现一些特殊符号的出现,128个不够用,于是扩展ASCII 码由8位二进制数表示一个字符,总共可以表示256个字符,这已经足够满足以英语为主的语言和特殊符号进行输入、存储、输出等操作的字符需要了。

    可是,单我们国家就有除汉族外的满、回、藏、蒙古、维吾尔等多个少数民族文字,换作全世界估计要有成百上千种语言与文字,显然这256个字符是不够的,因此后来就有了 Unicode 编码,比较常用的是由16位的二进制数表示一个字符,这样总共就可以表示2^{16}个字符,约是65万多个字符,足够表示世界上所有语言的所有字符了。当然,为了和ASCII码兼容,Unicode的前256个字符与ASCII码完全相同。

    所以如果我们要在C语言中比较两个串是否相等,必须是它们串的长度以及它们各个对应位置的字符都相等时,才算是相等

    即给定两个串:s = “a_{1}a_{2}......a_{n}t = “b_{1}b_{2}......b{m},当且仅当 n = m,且 a_{1}=b_{1}a_{2}=b_{2},......,a_{n}=b_{m}时,我们认为s = t

    那么对于两个串不相等时,如何判定它们的大小呢。我们这样定义:

    给定两个串:s = “a_{1}a_{2}......a_{n}t = “b_{1}b_{2}......b{m}当满足以下条件之一时,s < t

    1. n < m,且a_{i}=b_{i}  (i = 1, 2, ...... , n)。s < t 成立。

    例如当s = “hap”,t = “happy”,就有s < t。因为 ts 多出了两个字母。

    2. 存在某个 k ≤ min (m, n),使得a_{i}=b_{i} (i=1, 2, ...... , k-1), a_{k}<b_{k} 。s < t 成立。

    例如当 s = “happen”,t = “happy”,因为两串的前4个字母均相同,而两串第5个字母(k 值),字母 eASCII 码是101,而字母yASCII 码是121,显然e < y, 所以s < t

    英语字典就是一个字符串比较的应用。我们的英语词典,通常都是上万个单词的有序排列。就大小而言,前面的单词比后面的要小。你在查找单词的过程,其实就是在比较字符串大小的过程。

    3. 串的抽象数据类型

    串的逻辑结构和线性表很相似,不同之处在于串针对的是字符集,也就是串中的元素都是字符,哪怕串中的字符是“123”这样的数字组成,或者“2010-10-10”这样的日期组成,它们都只能理解为长度为3和长度为10的字符串,每个元素都是字符而已。

    因此,对于串的基本操作与线性表是有很大差别的。线性表更关注的是单个元素的操作比如查找一个元素,插入或删除一个元素,但串中更多的是查找子串位置、得到指定位置子串、替换子串等操作

    ADT 串(string)
    Data
        串中元素仅由一个字符组成,相邻元素具有前驱和后继关系。
    Opration
        StrAssign(T, *chars):生成一个其值等于字符串常量chars的串T。
    
        StrCopy(T, S):串S存在,由串S复制得串T。
    
        ClearString(S):若串S存在,将串清空。
    
        StringEmpty(S):若串S为空,返回true,否则返回false。
    
        StrLength(S):返回串的元素个数,即串的长度。
    
        StrCompare(S, T):若S > T,返回值 > 0,若S = T,返回0,若S < T,返回值 < 0。
    
        Concat(T, S1, S2):用T返回由S1和S2联接而成的新串。
    
        SubString(Sub, S, pos, len):串S存在,1≤pos≤StrLength(S), 
                且0≤len≤StrLength(S) - pos + 1,
                用Sub返回串S的第pos个字符,用Sub返回串S的第pos个字符起长度为len的字串。
    
        Index(S, T, pos):串S和T存在,T是非空串,1≤pos≤StrLength(S)。
                若主串S中存在和串T相同的子串,则返回它在主串S中第pos个字符之后第一个出现的位置,则返回0。
        Replace(S, T, V):串S、T和V存在,T是非空串。用V替换主串S中出现的所有与T相等的不重叠的子串。
    
        StrInsert(S, pos, T):串S和T存在,1≤pos≤StrLength(S) + 1。在串S的第pos个字符之前插入串T。
    
        StrDelete(S, pos, len):串S存在,1≤pos≤StrLength(S) - len + 1。从串S中删除第pos个字符起长度为len的子串。
    
    endADT

    先看看一个操作 Index 的实现算法:

    /*
    T为非空串。若主串S中第pos个字符串之后存在与T相等的子串,
    则返回第一个这样的子串在S中的位置,否则返回0
    */
    int Index(string  S, string  T, int pos)
    {
    	int n, m, i;
    	string sub;
    	if (pos > 0)
    	{
    		n = StrLength(S); //得到主串S的长度
    		m = StrLenhth(T); //得到子串T的长度
    		i = pos;
    		while (i <= n - m + 1)
    		{
    			SubString(sub, S, i, m); //取主串第i个位置,长度与T相等子串给sub
    			if (StrCompare(sub, T) != 0) //如果两串不相等
    			{
    				++i;
    			}
    			else //如果两串相等
    			{
    				return i; //返回i值
    			}
    		}
    	}
    	return 0; //若无子串与T相等,返回0
    }

    当中用到了StrLength、SubString、StrCompare等基本操作来实现。

    4. 串的存储结构

    串的存储结构与线性表相同,分为两种。

    4.1 串的顺序存储结构

    串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小,为每个定义的串变量分配一个固定长度的存储区。一般是用定长数组来定义。

    既然是定长数组,就存在一个预定义的最大串长度,一般可以将实际的串长度值保存在数组的 0 下标位置,有的也会定义存储在数组的最后一个下标位置。但也有些编程语言不想这么干,觉得存个数字占个空间麻烦。它规定在串值后面加一个不 计入串长度的结束标记字符,比如“ \0 ”来表示串值的终结,这个时候,你要想知道此时的串长度,就需要遍历计算一下才知道了,其实这还是需要占用一个空间。比如C语言中,给字符串赋值时,编译系统就会自动为数组最后一个元素后面加一个“\0”。

    由于定长数组的数组长度是固定的,存放的元素个数是有上限的,于是对于串的顺序存储,有一些变化,串值的存储空间可在程序执行过程中动态分配而得。比如在计算机中存在一个自由存储区,叫做“ 堆 ”。这个堆可由C语言的动态分配函数malloc ()和free ()来管理。

    4.2 串的链式存储结构

    对于串的链式存储结构,与线性表是相似的,但由于串结构的特殊性,结构中的每个元素数据是一个字符,如果也简单的应用链表存储串值,一个结点对应一个字符,就会存在很大的空间浪费。因此,一个结点可以存放一个字符,也可以考虑存放多个字符,最后一个结点若是未被占满时,可以用“ # ”或其他非串值字符补全,如图下所示:

    当然,这里一个结点存多少个字符才合适就变得很重要,这会直接影响着串处理的效率,需要根据实际情况做出选择。

    串的链式存储结构除了在连接串与串操作时有一定方便之外,总的来说不如顺序存储灵活,性能也不如顺序存储结构好

    5. 朴素的模式匹配算法

    当统计一本书中什么字、什么词语或什么单词出现频率最高时,这里里面最重要的其实就是去找一个单词在一篇文章(相当于一个大字符串)中的定位问题。这种子串的定位操作通常称做串的模式匹配,应该算是串中最重要的操作之一。

    假设我们要从下面的主串 S="goodgoogie”中,找到 T=“google”这个子串的位置。我们通常需要下面的步骤。

    1. 主串S第一位开始,S T 前三个字母都匹配成功,但 S 第四个字母是 dT 的是 g。第一位匹配失败。如下图所示,其中竖直连线表示相等,闪电状弯折连线表示不等。

    2. 主串 S 第二位开始,主串S首字母是 o ,要匹配的 T 首字母是 g ,匹配失败, 如下图所示。

    3. 主串 S 第三位开始,主串 S 首字母是 o ,要匹配的 T 首字母是 g ,匹配失败, 如下图所示。

    4. 主串 S 第四位开始,主串 S 首字母是 d ,要匹配的T首字母是 g ,匹配失败, 如下图所示。

    5. 主串 S 第五位开始,ST,6个字母全匹配,匹配成功,如下图所示。

    简单的说,就是对主串的每一个字符作为子串开头,与要匹配的字符串进行匹配。对主串做大循环,每个字符开头做 T 的长度的小循环,直到匹配成功或全部遍历完成为止。

    前面我们已经用串的其他操作实现了模式匹配的算法 Index。现在考虑不用串的其他操作,而是只用基本的数组来实现同样的算法。注意我们假设主串 S 和要匹配的子串 T 的长度存在 S[0]T[0] 中。实现代码如下:

    /*
    返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数返回值为0。
    T 非空,1≤pos≤StrLength(S)。
    */
    int Index(string S, string T, int pos)
    {
    	int i = pos; //i用于主串S中当前位置下标,若pos不为1,则从pos位置开始匹配
    	int j = 1; //j用于子串T中当前位置下标值
    	while (i <= S[0] && j <= T[0]) //若i小于S长度且j小于T的长度时循环
    	{
    		if (S[i] == T[j]) //两字母相等则继续
    		{
    			++i;
    			++j;
    		}
    		else //指针后退重新开始匹配
    		{
    			i = i - j + 2; //i退回到上次匹配首位的下一位
    			j = 0; //j退回到子串T的首位
    		}
    	}
    	if (j > T[0])
    	{
    		return i - T[0];
    	}
    	else
    	{
    		return 0;
    	}
    }

    分析一下,最好的情况是什么?那就是一开始就区配成功,比如 “googlegood”  中去找 “google” ,时间复杂度为O(1) 。稍差一些,如果像刚才例子中第二、三、四位一样,每次都是首字母就不匹配,那么对 T 串的循环就不必进行了,比如 “abcdefgoogle” 中去找 “google” 。那么时间复杂度为O(n+m) ,其中 n 为主串长度,m 为要匹配的子串长度。根据等概率原则,平均是 (n+m) /2 次查找,时间复杂度为O(n+m)

    那么最坏的情况又是什么?就是每次不成功的匹配都发生在串 T 的最后一个字符。举一个很极端的例子。主串为 S = “00000000000000000000000000000000000000000000000001”,而要匹配的子串为 T = “0000000001”,前者是有49个 “0” 和1个 “1” 的主串,后者是 9个 “0” 和 1 个 “1” 的子串。在匹配时,每次都得将 T 中字符循环到最后一位才发现:哦,原来它们是不匹配的。这样等于 T 串需要在 S 串的前 40 个位置都需要判断 10 次,并得出不匹配的结论,如下图所示:

    直到最后第 41 个位置,因为全部匹配相等,所以不需要再继续进行下去,如下图所示:

    如果最终没有可匹配的子串,比如是 T= “0000000002”,到了第 41 位置判断不匹配后同样不需要继续比对下去。因此最坏情况的时间复杂度为 O((n-m+1)*m)

    不要以为我这只是危言耸听,在实际运用中,对于计算机来说,处理的都是二进位的 0 1 的串,一个字符的 ASCII 码也可以看成是 8 位的二进位 01 串,当然,汉字等所有的字符也都可以看成是多个 01 串。再比如像计算机图形也可以理解为是 由许许多多个 01 的串组成。所以在计算机的运算当中,模式匹配操作可说是随处可见,而刚才的这个算法,就显得太低效了。

    6. KMP模式匹配算法

    由于朴素匹配算法太过于低效,前辈们觉得像这种有多个 0 1 的重复字符的字符串,却需要挨个遍历的算法是非常糟糕的事情。于是有三位前辈,D.E.KnuthJ.H.Morris V.R.Pratt (其中 Knuth Pratt 共同研究,Morris 独立研究)发表一个模式匹配算法,可以大大避免重复遍历的情况,我们把它称之为克努特一莫里斯一普拉特算法,简称KMP算法。

    1. KMP模式匹配算法原理

    为了能讲清楚 KMP 算法,我们不直接讲代码,那样很容易造成理解困难,还是从这个算法的研究角度来理解为什么它比朴素算法要好。

    如果主串 S= “abcdefgab”,其实还可以更长一些,我们就省略掉只保留前 9 位,我们要匹配的 T= “abcdex”,那么如果用前面的朴素算法的话,前 S 个字母,两个串完全相等,直到第 6 个字母,“ f ”“ x ”不等,如下图的①所示。接下来,按照朴素模式匹配算法,应该是如上图的流程②③④⑤⑥。即主串 S 中当 i =2、3、4、5、6 时,首字符与子串 T 的首字符均不等。

    似乎这也是理所当然,原来的算法就是这样设计的。可仔细观察发现。对于要匹配的子串 T 来说,“abcdex” 首字母“ a ”与后面的串 “bcdex” 中任意一个字符都不相等。也就是说,既然“ a ”不与自己后面的子串中任何一字符相等,那么对于上图的来说,前五位字符分别相等,意味着子串 T 的首字符“ a ”不可能与 S 串的第 2 位到第 5 位的字符相等。在上图中,②③④⑤的判断都是多余。

    注意这里是理解 KMP 算法的关键。如果我们知道 T 串中首字符“ a ”T 中后面的字符均不相等(注意这是前提,如何判断后面再讲)。而 T 串的第一位的“ b ”S 串中第二位的“ b ”在上图中的①中已经判断是相等的,那么也就意味着,T 串中首 字符“ a ”S 串中的第二位“ b ”是不需要判断也知道它们是不可能相等了,这样上图中的②这一步判断是可以省略的,如下图所示:

    同样道理,在我们知道 T 串中首字符“ a ” T 中后面的字符均不相等的前提下,T 串的“ a ”S 串后面的“ b ”“ c ”“ d ”“ e ”也都可以在①之后就可以确定是不相等的,所以这个算法当中②③④⑤没有必要,只保留①⑥即可,如下图所示:

    之所以保留⑥中的判断是因为在①中 T[6] ≠ S[6] ,尽管我们已经知道T[1] ≠ T[6],但也不能断定 T[1] —定不等于 S[6],因此需要保留⑥这一步。

    对于另外一种情况,就是如果 T 串后面也含有首字符“ a ”的字符怎么办呢?

    我们来看下面一个例子,假设 S= “abcabcabc”T= “abcabx”。对于开始的判断,前 S 个字符完全相等,第6个字符不等,如下图的 ①。此时,根据刚才的经验,T 的首字符“ a ”T 的第二位字符“ b ”、第三位字符“ c ”均不等,所以不需要做判断,下图的朴素算法步骤②③都是多余。

    因为 T 的首位“ a ” T 第四位的“ a ”相等,第二位的“ b ”与第五位的“ b ”相等。而在①时,第四位的“ a ”与第五位的“ b ”已经与主串 S 中的相应位置比较过了,是相等的,因此可以断定,T 的首字符“ a ”、第二位的字符“ b ”S 的第四位字符和第五位字符也不需要比较了,肯定也是相等的——之前比较过了,还判断什么,所以④⑤这两个比较得出字符相等的步骤也可以省略

    也就是说,对于在子串中有与首字符相等的字符,也是可以省略一部分不必要的判断步骤。如下图所示,省略掉右图的 T 串前两位“ a ”“ b ”S 串中的4、5 位置字符匹配操作。

    对比这两个例子,我们会发现在①时,我们的 i 值,也就是主串当前位置的下标是 6,②③④⑤,i 值是2、3、4、5,到了⑥,i 值才又回到了 6即我们在朴素的模式匹配算法中,主串的 i 值是不断地回溯来完成的。而我们的分析发现,这种回溯其 实是可以不需要的——正所谓好马不吃回头草,我们的KMP模式匹配算法就是为了让这没必要的回溯不发生

    既然 i 值不回溯,也就是不可以变小,那么要考虑的变化就是 j 值了。通过观察也可发现,我们屡屡提到了 T 串的首字符与自身后面字符的比较,发现如果有相等字符,j 值的变化就会不相同。也就是说,这个 j 值的变化与主串其实没什么关系,关键就取决于 T 串的结构中是否有重复的问题。

    比如上图中,由于 T="abcdex”,当中没有任何重复的字符,所以 j 就由 6 变成了 1。而下图中,由于 T="abcabx”,前缀的“ ab ”与最后“ x ”之前串的后缀“ ab ”是相等的。因此 j 就由 6 变成了 3。因此,我们可以得出规律,j 值的多少取决于当前字符之前的串的前后缀的相似度

    我们把 T 串各个位置的 j 值的变化定义为一个数组 next,那么 next 的长度就是 T 串的长度。于是我们可以得到下面的函数定义:

    2. next数组值推荐

    具体如何推导出一个串的 next 数组值呢,我们来看一些例子。

    1. T =“ abcdex ”(如下表所示)

    1)  当 j=1 时,next[1] = 0

    2)  当 j=2 时,j1 j-1 就只有字符“ a ”,属于其他情况 next[2]=1

    3)  当 j=3 时,j 1 j-1 串是“ ab ”,显然“ a ”“ b ”不相等,属其他情况,next[3]=1

    4)  以后同理,所以最终此 T 串的 next[ j ]011111

    2. T=“ abcabx ”(如下表所示)

    1)  当 j=1 时,next[1]=0

    2)  当 j=2 时,同上例说明,next[2]=1

    3)  当 j=3 时,同上,next[3]=1

    4)  当 j=4 时,同上,next[4]=1

    5)  当 j=5 时,此时 j 1j-1 的串是abca ”,前缀字符“ a ”与后缀字符“ a ”相等(前缀用下划线表示,后缀用斜体表示),因此可推算出 k 值为 2  (由' p_{1}......p_{k-1}' = ' p_{j-k+1}......p_{j-1} ',得到p_{1}=p_{4})因此 next[5]=2

    6)  当 j=6 时,j1 j-1 的串是abcab ”,由于前缀字符“ ab ”与后缀“ ab ”相等,所以 next[6]=3

    我们可以根据经验得到如果前后缀一个字符相等,k 值是 2,两个字符 k 值是 3, n 个相等 k 值就是 n+1

    3. T=“ababaaaba”(如下表所示)

    1)  当 j=1 时,next[1]=0

    2)  当 j=2 时,同上 next[2]=1

    3)  当 j=3 时,同上 next[3]=1

    4)  当 j=4 时,j1 j-1 的串是aba ”,前缀字符“ a ”与后缀字符“ a ”相等,next[4]=2

    5)  当 j=5 时,j1j-1 的串是abab ”由于前缀字符“ ab ”与后缀“ ab ”相等,所以 next[5]=3

    6)  当 j=6 时,j由 1j-1 的串是ababa ”,由于前缀字符“ aba ”与后缀 “ aba ” 相等,所以 next[6]=4

    7)  当 j=7 时,j由 1j-1 的串是ababaa ”,由于前缀字符“ ab ”与后缀 “ aa ”并不相等,只有“ a ”相等,所以 next[7]=2

    8)  当 j=8 时,j由 1j-1 的串是ababaaa ”,只有“ a ”相等,所以 next[8]=2

    9)  当 j=9 时,j由 1j-1 的串是 ababaaab ”,由于前缀字符 “ ab ” 与后缀“ ab ”相等,所以 next[9]=3

    4.  T=”aaaaaaaaab”(如下表所示)

    1)  当 j=1 时,next[1]=0

    2)  当 j=2 时,同上 next[2]=1

    3)  当 j=3 时,j1j-1 的串是aa ”,前缀字符“ a ”与后缀字符“ a ”相等,next[3]=2

    4)  当 j=4 时,j 1j-1 的串是“ aaa ”,由于前缀字符“ aa ”与后缀“ aa ”相等,所以 next[4]=3

    5)    .........

    6)    当 j=9 时,j 1j-1 的串是aaaaaaaa ”,由于前缀字符“ aaaaaaa ”与后缀“ aaaaaaa ”相等,所以 next[9]=8

    3. KMP模式匹配算法实现

    了解了思路之后,我们可以看看代码了:

    //通过计算返回子串T的next数组
    void get_next(String T, int *next)
    {
    	int i, j;
    	i = 1;
    	j = 0;
    	next[1] = 0;
    	while (i < T[0]) //此处T[0]表示串T的长度
    	{
    		if (j == 0 || T[i] == T[j]) //T[i]表示后缀的单个字符 T[j]表示前缀的单个字符
    		{
    			++i;
    			++j;
    			next[i] = j;
    		}
    		else
    		{
    			j = next[j]; //若字符不相同,则j值回溯
    		}
    	}
    }

    这段代码的目的就是为了计算出当前要匹配的串T的next数组。

    /*
    返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数返回为0
    T非空,1≤pos≤StrLength(S)
    */
    int Index_KMP(String S, String T, int pos)
    {
    	//i用于主串S当前位置下标值,若pos不为1,则从pos位置开始匹配
    	int i = pos;
    	//j用于子串T中当前位置下标值
    	int j = 1;
    	int next[255]; //定义一个next数组
    	get_next(T, next); //对串T作分析,得到next数组
    	while (i <= S[0] && j <= T[0]) //若i小于S的长度且j小于T的长度时,继续循环
    	{
    		if (j == 0 || S[i] == T[j])//两字母相等则继续,比朴素算法增加了j=0判断
    		{
    			++i;
    			++j;
    		}
    		else //指针后退重新开始匹配
    		{
    			j = next[j]; //j退回合适的位置,i值不变
    		}
    	}
    	if (j > T[0])
    	{
    		return i - T[0];
    	}
    	else
    	{
    		return 0;
    	}
    }

    相对于朴素匹配算法增加的代码不多就一点点,改动不算大,关键就是去掉了 i 值回溯的部分。对于 get_next 函数来说,若 T 的长度为 m,因只涉及到简单的单循环,其时间复杂度为 O(m) ,而由于 i 值的不回溯,使得 index_KMP 算法效率得到了提高,while 循环的时间复杂度为 O(n) 。因此,整个算法的时间复杂度为 O(n+m) 。相较于朴素模式匹配算法的 O((n-m+1)*m)来说,是要好一些。

    这里也需要强调,KMP 算法仅当模式与主串之间存在许多“ 部分匹配 ”的情况下才体现出它的优势,否则两者差异并不明显。

    4. KMP模式匹配算法改进

    KMP 还是有缺陷的。比如,如果我们的主串 S="aaaabcde”,子串 T=“aaaaax next数组值分别为 012345,在开始时,当 i=5、j=5 时,我们发现b a 不相等,如下图的①,因此 j=next[5]=4如图中的②,此时b4 位置的“ a 依然不等,j=next[4]=3如图中的③,后依次是④⑤,直到 j=next[1]=0 时,根据算法,此时i++j++,得到 i=6j=1如图中的⑥。

    我们发现,当中的②③④⑤步骤,其实是多余的判断。由于 T 串的第二、三、 四、五位置的字符都与首位的“ a ”相等,那么可以用首位 next[1] 的值去取代与它相等的字符后续 next[j] 的值,这是个很好的办法。因此我们对求 next 函数进行了改良。

    假设取代的数组为nextval,代码如下:

    //求模式串T的next函数修正值并存入数组nextval
    void get_nextval(String T, int *nextval)
    {
    	int i, j;
    	i = 1;
    	j = 0;
    	nextval[1] = 0;
    	while (i < T[0]) //此处T[0]表示串T的长度
    	{
    		if (j == 0 || T[i] == T[j]) //T[i]表示后缀的单个字符 T[j]表示前缀的单个字符
    		{
    			++i;
    			++j;
    			if (T[i] != T[j]) //若当前字符与前缀字符不同
    			{
    				nextval[i] = j; //则当前的j为nextval在i位置的值
    			}
    			else
    			{
    				//如果与前缀字符相同,则将前缀字符的nextval值赋值给nextval在i位置的值
    				nextval[i] = nextval[j]; 
    			}
    		}
    		else
    		{
    			j = nextval[j]; //若字符不相同,则j值回溯
    		}
    	}
    }

    实际匹配算法,只需要将“ get_next (T,  next); "改为“ get_nextval (T,next); "即可,这里不再重复。

    5. nextval数组值推导

    改良后,nextval 值就与 next 值不完全相同了。比如:

    1. T="ababaaaba”(如下表所示)

    先算出 next 数组的值分别为 001234223,然后再分别判断。

    1)  当 j=1 时,nextval[1]=0

    2)  当 j=2 时,因第二位字符“ b ”next 值是 1,而第一位就是“ a ”,它们不相等,所以 nextval[2]=next[2]=1,维持原值。

    3)  当 j=3 时,因为第三位字符“ a ”next 值为 1,所以与第一位的“ a ”比较得知它们相等,所以 nextval[3]=nextval[1]=0;如下图所示:

    4)  当 j=4 时,第四位的字符“ b ” next 值为2,所以与第二位的“ b ”相比较得到结果是相等,因此 nextval[4]=nextval[2]=1;如下图所示:

    5)  当 j=5 时,next 值为 3,第五个字符“ a ”与第三个字符“ a ”相等,因此 nextval[5]=nextval[3]=0

    6)  当 j=6 时,next 值为 4,第六个字符“ a ”与第四个字符“ b ”不相等,因此 nextval [6]=4

    7)  当 j=7 时,next 值为 2,第七个字符 “a ”与第二个字符“ b ”不相等,因此 nextval [7]=2

    8)  当 j=8 时,next 值为 2,第八个字符“ b ”与第二个字符“ b ”相等,因此 nextval[8]=nextval[2]=1

    9)  当 j=9 时,next 值为 3,第九个字符“ a ”与第三个字符“ a ”相等,因此 nextval [9]=nextval [3]=1

    2. T=“aaaaaaaab”(如下表所示)

    先算出 next 数组的值分别为 012345678,然后再分别判断。

    1)  当 j=1 时,nextval[1]=0

    2)  当 j=2 时,next 值为1,第二个字符与第一个字符相等,所以 nextval[2]= nextval[1]=0

    3)  同样的道理,其后都为 0 ……

    4)  当 j=9 时,next 值为 8,第九个字符“ b ”与第八个字符“ a ”不相等,所以 nextval[9]=8

    总结改进过的 KMP 算法,它是在计算出 next 值的同时,如果 a 位字符与它 next 值指向的 b 位字符相等,则该 a 位的 nextval 就指向 b 位的 nextval 值,如果不等,则该 a 位的 nextval 值就是它自己 a 位的 next 的值。

    7. 总结

    本篇博客重点讲了“ 串 ”这样的数据结构,串(string)是由零个或多个字符组成的有限序列,又名叫字符串

    本质上,它是一种线性表的扩展,但相对于线性表关注一个个元素来说,我们对串这种结构更多的是关注它子串的应用问题,如查找、 替换等操作。

    现在的高级语言都有针对串的函数可以调用。我们在使用这些函数的时候,同时也应该要理解它当中的原理,以便于在碰到复杂的问题时,可以更加灵活的使用,比如 KMP 模式匹配算法的学习,就是更有效地去理解 index 函数当中的实现细节。多用心一点,说不定有一天,可以有以你的名字命名的算法流传于后世。

     

    注:本博客是本人在学习《大话数据结构》后整理的笔记,用于自己以后的复习与回顾,博客中的照片是本人从《大话数据结构》中截取的。

    展开全文
  • 串的定义与基本操作 串的存储结构 朴素模式匹配算法 KMP算法(一) KMP算法(二) KMP算法优化(nextval数组)
    展开全文
  • (string)是由零个或多个字符组成有限序列,又叫字符中字符个数可以是0个也可以是多个,他们之间存在先后关系,是一个有限序列。 空串 “” 空格“ ” 子串“lie”, 主”believe”普遍来说...
  • 回顾知识点字符类型概念回顾 ;字符型数据可以是字母符号数;ord(1=1)=1 ;将数字8转换为一个字符8;例题一将任一大写字母,转换成小;题二 按字母表顺序和逆序每隔;题三输入一字符字符个数不;字符处理即字符...
  • 此为数据结构串的一些操作,其中包括定位子串位置的普通算法,与KMP模式匹配算法等。
  • 一,核心知识点 1.定义 :由零个或多个字符组成有限序列。记为: s=’a1a2a3……an’ (n&gt;=0) **名:**s 值: a1a2a3……an 长:n 子串:中任意个连续字符组成子序列 任意是其自身子串 主...
  • 在本文中我们系统给大家整理了关于python字符和常用数据结构的相关知识点以及实例代码,需要朋友们学习下。
  • 数据结构知识点

    2017-09-23 23:31:01
    数据结构知识点串聊,也是当时校招自己做一点笔记
  • 数据结构知识点

    2019-03-31 16:12:26
    数据的逻辑结构分为线性结构和非线性结构。 常用线性结构有:线性表,栈,队列,双队列,数组,。 常见非线性结构有:二维数组,多维数组,广义表,树(二叉树等),图,堆。 ...
  • 下列数据结构不是多型数据类型的是() A 堆 B 栈 C 字符串 D 有向图 【解析】 "多型" 是指数据元素的类型不确定。 字符串的每个元素始终都是字符类型,栈、堆和有向图的数据元素的元素类型不确定。 选C。
  • 数据结构知识点复习

    2015-08-05 23:28:00
    因此写篇文章,梳理一下数据结构这个知识点的基本框架与结构。   二、基本数据结构: 1.数组: c语言数组 vector 2.链表: 单链表 双向链表 环形链表 3.栈: 程序栈 4.队列: 双端队列 有限队列   5.字符 5.队列...
  • 本帖用于记录在学习数据结构的过程中做错的题目所涉及到的知识点,以及还未弄明白但是重要的知识点,常更新  cin>> 该操作符是根据后面变量的类型读取数据。 输入结束条件 :遇到Enter、Space、Tab键。 对结束...
  • 数据结构——

    2019-12-09 20:24:11
    数据结构——串(知识点整理) 1.串类型的定义 1.串(或字符串)是由零个或多个字符组成的有限序列 2.C语言中处理串的两种方法:字符数组和字符指针 3. 空串是长度为零的串,而空格串是一个或多个空格组成的串 ...
  • 线性表 线性结构的定义 若结构是非空有限集,则有且仅有一个开始结点和一个终端结点,并且所有结点都最多...定义:用数据元素有限序列表示 n=0时称为空表 线性表类型定义 顺序存储 线性表顺序表示又称为
  • 关联数组不是,关联数组是一种映射、字典(dictionary),是一种抽象的数据结构,里面包含着类似<K,V>键值对 char str[] = “Hello”,sizeof(str)计算:存储str时实际要上是‘H’‘e’‘l’‘l’‘o’...
  • 2. 数据的逻辑结构与物理结构 3. 算法复杂度 4. 线性表之顺序表 5. 线性表之单链表 6. 线性表之循环链表 7. 线性表之双向链表 8. 线性表之静态链表 9. 线性表应用 10. 栈之顺序栈 11. 栈之链栈 12. 栈应用 13. ...
  • 1在一棵具有 5 层的满二叉树中结点总数为 A 6对下图 V4 的度为 C A) 31 B 32 A1 B 2 C 3 D 4 C33 D 16 (2^n) - 1, k N = 2 -1...D 集合 串的逻辑结构和线性表极为相似 区别仅在于串的数据对象 v4 约束为字符集 P71 7在
  • 一、数据结构知识点总结整理 3 2.数据结构的定义: 4 3.数据结构的知识: 9 二、数据结构的实现 16 1、二叉树三种遍历的非递归算法 16 1.先序遍非递归算法 16 2.中序遍历非递归算法 17 3.后序遍历非递归算法 18 4....
  • 408知识点-数据结构

    2021-01-16 15:43:43
    数据结构 408系列参考王道2021系列书籍 文章目录数据结构前言一、绪论二、线性表1.顺序表2.链式表3.小结栈和队列1.栈—先进后出2.队列—先进先出3.特殊矩阵压缩存储树和二叉树1.基本概念2.应用图查找排序总结 ...
  • 数据结构知识点总结整理

    千次阅读 2013-12-06 17:33:47
    数据结构知识点总结整理 0、常考基础必知必会 A. 排序:排序有几种,各种排序比较,哪些排序是稳定,快排算法; B. 查找:哈希查找、二叉树查找、折半查找对比,哈希映射和哈希表区别? C. 链表和...
  • 数据结构之字符

    2020-05-05 23:12:47
    在计算机上做非数值处理的计算越来越多,而在计算机上非数值处理大部分是对字符串的处理,处理这些字符串数据比起处理整型、浮点型数据都要复杂很多,所以把串作为一种独立的数据结构进行研究。 串(数据结构)前言...
  • 1.字符常量是用单引号括起来的一个字符。例如: 'a'、'='、'+'等。转义字符是一种特殊的字符常量...串值也可用链表来存储,由于串的数据元素是一个字符,它只有8位二进制数,因此用链表存储时,通常一个结 点中存放的...
  • 字符操作。 Hash表hash函数,冲突解决方法有哪些。 各种排序:冒泡、选择、插入、希尔、归并、快排、堆排、桶排、基数原理、平均时间复杂度、最坏时间复杂度、空间复杂度、是否稳定。 快排partition函数与...
  • 数据结构—字符

    2018-07-28 09:12:25
    总第118篇前言本篇开始写数据结构的第三部分——字符串,主要内容如下:概念串的存储结构串的基本操作关于字符串还有一个重要的知识点是KMP模式匹配算法,关于这个算法会单独拿一篇来写。概念串...

空空如也

空空如也

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

数据结构串的知识点

数据结构 订阅