下载文档原格式
数据结构串、数组和广义表知识点总结
数据结构是计算机科学中研究数据如何组织、存储、管理和操作的学科。
三个常见的数据结构串、数组和广义表都是用于存储和操作数据的。
1. 串：
- 串是由0个或多个字符组成的有限序列。
它是一维数组的特例。
- 串的操作包括插入、删除、修改和查找等常见操作。
- 串可以通过数组、链表或动态分配的内存来实现。
2. 数组：
- 数组是一种线性数据结构，它由一组连续的内存空间组成，
存储相同类型的数据。
- 数组的操作包括插入、删除、修改和查找等常见操作。
- 数组的访问时间复杂度为O(1)，但插入和删除的时间复杂度
较高。
3. 广义表：
- 广义表是由若干元素组成的有序集合，每个元素可以是原子
或者是一个广义表。
- 广义表可以通过链表来实现，每个节点包含两个指针，一个
指向元素，一个指向下一个节点。
- 广义表的操作包括插入、删除、修改和查找等常见操作。
- 广义表可以表示任意层次的嵌套结构，具有灵活性和扩展性。
总结：
- 串、数组和广义表都是常见的数据结构，用于存储和操作数据。
- 串是字符的有限序列，可以通过数组或链表来实现。
- 数组是一维线性数据结构，存储相同类型的数据，具有常数时间复杂度的访问操作。
- 广义表是由元素组成的有序集合，可以通过链表来实现，能够表示任意层次的嵌套结构。
四、串、数组和⼴义表(内容待完善)知识点串的模式匹配⼜称⼦串定位运算或串匹配。
在匹配中，将主串称为⽬标（串），⼦串称为模式（串）。
BF法(Brute Force):KMP法:串的模式匹配的两种⽅法。
BF法,朴素的串匹配法。
KMP法，尽可能的滑动得更远，利⽤部分的匹配结果。
朴素的模式匹配算法（BF算法）图⽰说明第⼀轮⽐较：第⼆轮⽐较：...... 原理⼀致，省略中间步骤第五轮：第六轮：第⼀轮：⼦串中的第⼀个字符与主串中的第⼀个字符进⾏⽐较若相等，则继续⽐较主串与⼦串的第⼆个字符若不相等，进⾏第⼆轮⽐较第⼆轮：⼦串中的第⼀个字符与主串中第⼆个字符进⾏⽐较......第N轮：依次⽐较下去，直到全部匹配代码实现:(略)BF算法优点：思想简单，直接，缺点：每次字符不匹配时，都要回溯到开始位置，时间开销⼤。
时间复杂度 O((n-m+1)*m) 。
KMP模式匹配算法图⽰说明:从图中，我们可以很容易的发现，因为前⾯的字符,S和T中存在同的元素,所以S不必回溯到S[1]的位置，T也不必回溯到T[0]的位置。
我们就可直接跳过对相同元素的回溯⽐较，直接⽐较S[8]与T[3]。
因此我们构建⼀个next数组储存回溯位置。
KMP算法的思想：假设在模式匹配的进程中，执⾏T[i]和W[j]的匹配检查。
若T[i]=W[j]，则继续检查T[i+1]和W[j+1]是否匹配。
next数组两种求法（1）第⼀种求法：根据前⼀个字符的next值求初始化:代码实现：1 char t[]={"ababaabab"};2 int Len=strlen(t);34 int i = 0, j = -1;5 int next[len];6 next[0]=-1;7 while (i < len - 1) {8 if ((j == -1) || t[i] == t[j]) {9 ++i, ++j;10 next[i] = j;11 }else{12 j = next[j];13 }14 }1516 for(i=0;i<len;i++)17 {printf("next[%d]->%d\n",i,next[i])}（2）第⼆种求法：根据最⼤公共元素长度求的求法））next数组优化（nextval的求法当⼦串中有多个连续重复的元素，例如主串 S=“aaabcde” ⼦串T=“aaaaax” 在主串指针不动，移动⼦串指针⽐较这些值，其实有很多⽆⽤功，因为⼦串中5个元素都是相同的a，所以我们可以省略掉这些重复的步骤。
串数组广义表题目
我不确定你想要什么类型的题目，但我可以给你一些与串、数组和广义表相关的题目作为参考：
1. 串：编写一个程序，从用户输入的字符串中查找给定的子串，并返回它在原始字符串中的位置。
2. 数组：编写一个程序，找到给定数组中的最大值和最小值，并计算它们的差值。
3. 广义表：实现一个广义表的数据结构，并编写相关的操作函数，如插入、删除、获取子表等操作。
4. 串：编写一个程序，判断给定的两个字符串是否是Anagram，即它们包含的字符相同，但顺序不同。
5. 数组：编写一个程序，对给定的数组进行排序，可以选择不同的排序算法实现。
6. 广义表：编写一个程序，将一个广义表展开为一个一维的数组。
7. 串：编写一个程序，计算给定字符串中各个字母出现的频率。
8. 数组：编写一个程序，查找给定数组中第K个最大/最小的
元素。
9. 广义表：编写一个程序，将一个普通的表达式字符串解析为一个广义表，并计算其值。
这些题目可以帮助你更深入地理解和应用串、数组和广义表的相关知识。
你可以根据自己的兴趣和能力选择其中一个或多个来实现。
02331数据结构-04数组和广义表1.多维数组和广义表是一种复杂的非线性结构，它们的逻辑特征是：一个数据元素可能有多个直接前驱和多个直接后继。
2.一维数组（向量）是存储于计算机的连续存储空间中的多个具有统一类型的数据元素。
同一数组的不同元素通过不同的下标标识。
（a1,a2,…,an)3.二维数组Amn可视为由m个行向量组成的向量，或由n个列向量组成的向量。
二维数组中的每个元素aij既属于第i行的行向量，又属于第j列的列向量。
4.多维数组:三维数组Amnp可视为以二维数组为数据元素的向量。
四维数组可视为以三维数组为数据元素的向量……三维数组中的每个元素aijk都属于三个向量。
四维数组中的每个元素都属于四个向量……5.数组的顺序存储方式:由于计算机内存是一维的，多维数组的元素应排成线性序列后存人存储器。
数组一般不做插入和删除操作，即结构中元素个数和元素间关系不变化。
一般采用顺序存储方法表示数组。
（1）行优先顺序：将数组元素按行向量排列，第i+1个行向量紧接在第i个行向量后面。
【例】二维数组Amn的按行优先存储的线性序列为：a11,a12,…,a1n,a21,a22,…,a2n,……，am1,am2,…，amn（2）列优先顺序将数组元素按列向量排列，第i+1个列向量紧接在第i个列向量后面。
【例】二维数组Amn的按列优先存储的线性序列为：a11,a21,…,am1,a12,a22,…,am2,……，a1n,a2n,…，amn6.数组元素的地址计算公式:（1）按行优先顺序存储的二维数组Amn地址计算公式LOC(aij)=LOC(a11)+[(i-1)某n+j-1]某d(注：此公式下界为1，如下界为0，则公式变为[i某n+j])①LOC(a11)是开始结点的存放地址（即基地址）②d为每个元素所占的存储单元数③由地址计算公式可得，数组中任一元素可通过地址公式在相同时间内存取。
即顺序存储的数组是随机存取结构。
