下载文档原格式
数据结构串、数组和广义表知识点总结
数据结构是计算机科学中研究数据如何组织、存储、管理和操作的学科。
三个常见的数据结构串、数组和广义表都是用于存储和操作数据的。
1. 串：
- 串是由0个或多个字符组成的有限序列。
它是一维数组的特例。
- 串的操作包括插入、删除、修改和查找等常见操作。
- 串可以通过数组、链表或动态分配的内存来实现。
2. 数组：
- 数组是一种线性数据结构，它由一组连续的内存空间组成，
存储相同类型的数据。
- 数组的操作包括插入、删除、修改和查找等常见操作。
- 数组的访问时间复杂度为O(1)，但插入和删除的时间复杂度
较高。
3. 广义表：
- 广义表是由若干元素组成的有序集合，每个元素可以是原子
或者是一个广义表。
- 广义表可以通过链表来实现，每个节点包含两个指针，一个
指向元素，一个指向下一个节点。
- 广义表的操作包括插入、删除、修改和查找等常见操作。
- 广义表可以表示任意层次的嵌套结构，具有灵活性和扩展性。
总结：
- 串、数组和广义表都是常见的数据结构，用于存储和操作数据。
- 串是字符的有限序列，可以通过数组或链表来实现。
- 数组是一维线性数据结构，存储相同类型的数据，具有常数时间复杂度的访问操作。
- 广义表是由元素组成的有序集合，可以通过链表来实现，能够表示任意层次的嵌套结构。
本章概览当前讲授一、知识结构二、本章重难点本要求考生熟悉数组在按行优先顺序的存储结构中元素地址的计算方法；熟悉特殊矩阵在压缩存储时的下标变换方法；理解稀疏矩阵的三元组表存储表示方法及有关算法；熟悉广义表的有关概念，理解广义表的括号表示和图形表示；掌握广义表的求表头和表尾的运算。
本章重点是多维数组的存储方式、矩阵的压缩存储、广义表的表头和表尾的求解；难点是压缩存储特殊矩阵和稀疏矩阵的各种运算及应用。
第一节多维数组和运算当前讲授一、多维数组的定义1、一维数组是一种元素个数固定的线性表。
2、多维数组是一种复杂的数据结构，可以看成是线性表的推广，一个n维数组可视为其数据元素为n-1维数组的线性表。
二、数组的顺序存储通常采用顺序存储结构来存放数组。
对二维数组可有两种存储方法：一种是以行序为主序的存储方式，另一种是以列序为主序的存储方式。
在C语言中，采用以行为主序存储。
（1）对于C语言的二维数组A[m][n]，下标从0开始，假设一个数组元素占d个存储单元，则二维数组中任一元素a[i][j]的存储位置可由下式确定：loc(A[i][j])=loc(A[0][0])+(i *n + j) * d【真题选解】（例题·单选题）二维数组A[4][5]按行优先顺序存储，若每个元素占2个存储单元，且第一个元素A[0][0]的存储地址为1000，则数组元素A[3][2]的存储地址为( )A．1012B．1017C．1034D．1036隐藏答案【答案】C【解析】loc(A[3][2])=loc(A[0][0])+(3 *5 + 2) *2=1000+34=1034（2）对于C语言的三维数组A[m][n][p]，下标从0开始，假设一个数组元素占d个存储单元，则三维数组中任一元素a[i][j][k]的存储位置可由下式确定：loc(A[i][j][k])=loc(A[0][0][0]+(i *n *p+ j*p+k) * d（例题·单选题）三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A[3][[4][5]的存储地址为（）。
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为每个元素所占的存储单元数③ 根据地址计算公式，可以通过地址公式同时在内存中访问数组中的任何元素。
数据结构数组与广义表知识点总结数组是一种线性数据结构，可以存储多个相同类型的元素。
它的特点是元素的大小固定，并且在内存中是连续存储的。
数组的访问方式是通过下标来访问，下标从0开始。
数组可以在编程中应用于各种情况，比如存储一组数字、一组字符串等。
广义表是一种扩展的线性数据结构，可以存储不同类型的元素。
它由元素和表构成，其中表可以是空表、原子或子表。
广义表可以递归定义，即子表可以包含更多的子表。
广义表的访问方式是通过递归来访问，可以对表的元素进行遍历和操作。
在数据结构中，数组和广义表都有自己的特点和用途，下面对它们的知识点进行总结：
1.数组的特点及应用：
-数组是一种线性数据结构，可以存储多个相同类型的元素。
-数组的内存分配是连续的，可以通过下标来访问元素。
-数组的大小固定，一旦定义后不能改变。
-数组的访问速度快，可以通过下标直接访问元素。
-数组适合用于存储一组相同类型的数据，比如一组数字、一组字
符串等。
-数组的应用场景包括但不限于：排序算法、查找算法、图像处理、矩阵运算等。
2.数组的操作和常用算法：
-初始化：可以直接赋值或使用循环初始化数组。
-访问元素：通过下标访问元素，下标从0开始。
-修改元素：直接通过下标修改元素的值。
-插入元素：需要移动插入位置之后的元素。
-删除元素：需要移动删除位置之后的元素。
-查找元素：可以使用线性查找或二分查找等算法。
-排序算法：比如冒泡排序、选择排序、插入排序等。
-数组还有一些常用的属性和方法，比如长度、最大值、最小值等。
3.广义表的特点及应用：
-广义表是一种扩展的线性数据结构，可以存储不同类型的元素。
-广义表由元素和表构成，表可以是空表、原子或子表。
-广义表可以递归定义，即子表可以包含更多的子表。
-广义表的访问方式是通过递归遍历和操作。
-广义表适合存储一组不同类型的数据，比如存储学生信息、函数调用栈等。
-广义表的应用场景包括但不限于：函数式编程、树的表示、图的表示等。
4.广义表的操作和常用算法：
-初始化：可以通过递归构造广义表。
-遍历元素：可以使用递归遍历所有的元素。
-插入元素：需要遍历找到插入位置，并将元素插入。
-删除元素：需要遍历找到删除位置，并将元素删除。
-修改元素：需要遍历找到修改位置，并修改元素的值。
-查找元素：可以使用递归查找指定元素。
-广义表还可以进行一些其他的操作，比如计算表的长度、判断表是否为空等。
5.数组与广义表的对比：
-数组适合存储相同类型的一组数据，广义表适合存储不同类型的一组数据。
-数组的访问速度快，广义表的访问速度较慢。
-数组的大小固定，广义表的大小可以动态调整。
-数组的操作相对简单，广义表的操作相对复杂。
-数组在内存中是连续存储的，广义表可以是非连续存储的。
总结：数组和广义表是数据结构中常用的线性数据结构，它们分别适用于存储相同类型的一组数据和不同类型的一组数据。
数组可以高效地访问元素，适合处理一组相同类型的数据；而广义表可以灵活地存储不同类型的数据，适合处理复杂的数据结构。
熟练掌握数组和广义表的知识点，对于编程和数据处理都具有重要意义。
