20220524数据结构绿皮书读书笔记

20220524数据结构绿皮书读书笔记
# 6 List and String
list实现和string
太简单了,不罗嗦了直接跳过 附两种实现的代码如下
数组实现
https://github.com/956237586/DataStructure-C/blob/master/DataStructure-C/1.1.linearlist.h
https://github.com/956237586/DataStructure-C/blob/master/DataStructure-C/1.1.linearlist.c
链表实现
https://github.com/956237586/DataStructure-C/blob/master/DataStructure-C/1.2.linearlist.c
https://github.com/956237586/DataStructure-C/blob/master/DataStructure-C/1.2.linearlist.h
字符串算法上有意思的就比较多了
KMP算法
https://blog.hylstudio.cn/archives/192
Levenshtein距离
https://blog.hylstudio.cn/archives/795
特殊玩法
一些比较老的语言,例如FORTRAN, COBOL,
BASIC 没有提供动态内存申请或者指针的能力,在这些语言里,可以使用基于数组实现的链表。
核心思想是:只要能记录元素的相对位置就可以实现这个线性表
实现方法也非常简单,通过一个next数组记录下一个元素的角标即可
如顺序表”a”->”b”->”c”->”d”->”e”
index =       0   1   2   3   4
arr_value = [“c”,”a”,”b”,”d”,”e”]
begin = 1
arr_next  = [ 3,  2,  0,  4,  -1]
这种存储方式借助数组的index来实现相对位置的记录,也有人叫做跳表
明天第7章,搜索
mark 目前是237页 ,pdf是285页
0 Comments
Leave a Reply