数据结构串、数组和广义表知识点总结

数据结构数组与广义表知识点总结数组是一种线性数据结构，可以存储多个相同类型的元素。

它的特点是元素的大小固定，并且在内存中是连续存储的。

数组的访问方式是通过下标来访问，下标从0开始。

数组可以在编程中应用于各种情况，比如存储一组数字、一组字符串等。

广义表是一种扩展的线性数据结构，可以存储不同类型的元素。

它由元素和表构成，其中表可以是空表、原子或子表。

广义表可以递归定义，即子表可以包含更多的子表。

广义表的访问方式是通过递归来访问，可以对表的元素进行遍历和操作。

在数据结构中，数组和广义表都有自己的特点和用途，下面对它们的知识点进行总结：1.数组的特点及应用：-数组是一种线性数据结构，可以存储多个相同类型的元素。

-数组的内存分配是连续的，可以通过下标来访问元素。

-数组的大小固定，一旦定义后不能改变。

-数组的访问速度快，可以通过下标直接访问元素。

-数组适合用于存储一组相同类型的数据，比如一组数字、一组字符串等。

-数组的应用场景包括但不限于：排序算法、查找算法、图像处理、矩阵运算等。

2.数组的操作和常用算法：-初始化：可以直接赋值或使用循环初始化数组。

-访问元素：通过下标访问元素，下标从0开始。

-修改元素：直接通过下标修改元素的值。

-插入元素：需要移动插入位置之后的元素。

-删除元素：需要移动删除位置之后的元素。

-查找元素：可以使用线性查找或二分查找等算法。

-排序算法：比如冒泡排序、选择排序、插入排序等。

-数组还有一些常用的属性和方法，比如长度、最大值、最小值等。

3.广义表的特点及应用：-广义表是一种扩展的线性数据结构，可以存储不同类型的元素。

-广义表由元素和表构成，表可以是空表、原子或子表。

-广义表可以递归定义，即子表可以包含更多的子表。

-广义表的访问方式是通过递归遍历和操作。

-广义表适合存储一组不同类型的数据，比如存储学生信息、函数调用栈等。

-广义表的应用场景包括但不限于：函数式编程、树的表示、图的表示等。

02331数据结构 04数组和广义表02331数据结构-04数组和广义表第四章多维数组和广义表1.多维数组和广义表是一种复杂的非线性结构，它们的逻辑特征是：一个数据元素可能有多个直接前驱和多个直接后继。

2.一维数组（矢量）是存储在计算机连续存储空间中的若干具有统一类型的数据元素。

同一数组的不同元素通过不同的下标标识。

（a1,a2,…,an)3.二维数组amn可视为由m个行向量组成的向量，或由n个列向量组成的向量。

二维数组中的每个元素aij既属于第i行的行向量，又属于第j列的列向量。

4.多维数组：3D数组AMNP可以看作是一个以2D数组为数据元素的向量。

将三维阵列的四维向量作为视觉数据三维数组中的每个元素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为每个元素所占的存储单元数③ 根据地址计算公式，可以通过地址公式同时在内存中访问数组中的任何元素。

四、串、数组和⼴义表(内容待完善)知识点串的模式匹配⼜称⼦串定位运算或串匹配。

在匹配中，将主串称为⽬标（串），⼦串称为模式（串）。

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，所以我们可以省略掉这些重复的步骤。

数据结构串的知识点归纳数据结构串是一种线性表结构，它是由零个或多个数据元素组成的有限序列。

数据结构串的存储结构有两种：顺序存储结构和链式存储结构。

下面将从串的定义、顺序存储结构、链式存储结构、串的基本操作等几个方面进行详细介绍。

一、串的定义串是由零个或多个字符组成的有限序列。

在串中，字符的个数称为串的长度。

如果串的长度为0，则称为空串。

串中的字符可以是字母、数字、标点符号和其他特殊符号等。

二、顺序存储结构顺序存储结构是将串中的字符按照其在串中的顺序依次存放在一块连续的存储空间中。

在顺序存储结构中，我们可以使用一维数组来表示串。

数组的下标表示字符在串中的位置，数组的元素存储字符的ASCII码值或字符本身。

通过这种方式，我们可以方便地对串进行插入、删除、查找等操作。

三、链式存储结构链式存储结构是将串中的字符按照其在串中的顺序分别存放在一系列结点中，并通过指针将这些结点链接起来。

在链式存储结构中，我们可以使用单链表、双链表或循环链表等数据结构来表示串。

每个结点包含一个字符和一个指向下一个结点的指针。

通过这种方式，我们可以方便地对串进行插入、删除、查找等操作。

四、串的基本操作1. 串的赋值：将一个串赋值给另一个串，即将被赋值串的字符复制给另一个串。

2. 串的连接：将两个串连接成一个新串，即将一个串的字符依次复制到另一个串的后面。

3. 串的比较：比较两个串是否相等或大小关系。

4. 串的求子串：从一个串中截取一段连续的子串。

5. 串的插入：将一个串插入到另一个串的指定位置。

6. 串的删除：从一个串中删除指定位置的字符或一段连续的子串。

7. 串的替换：将一个串中的子串替换为另一个串。

8. 串的查找：在一个串中查找指定字符或子串的位置。

9. 串的长度：获取一个串的长度。

10. 串的清空：将一个串清空，使其变成空串。

五、应用场景串作为一种基本的数据结构，在实际应用中有着广泛的应用场景。

例如，字符串匹配算法中常用的KMP算法和Boyer-Moore算法，都是基于串的操作实现的。