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

4
串的基本操作示例：
5
C 语言字符串函数库中提供下列串处理函数： 语言字符串函数库中提供下列串处理函数： 头文件： 头文件：# include <string.h> gets(str) puts(str) strcat(str1, str2) strcpy(str1, str2, k) strcmp(str1, str2) strlen(str) // 输入一个串； 输入一个串； // 输出一个串； 输出一个串； // 串联接函数； 串联接函数； // 串复制函数； 串复制函数； // 串比较函数； 串比较函数； // 求串长函数； 求串长函数；
记为： =‘a 记为：s = a1a2…an’ a 串名 串值
(用‘ ’ 括 起来) 起来)
(n≥0 )
C++中隐含结 C++中隐含结 束符‘ 束符‘\0’ , ASCII码 即ASCII码 NUL
2
串与线性表
串的逻辑结构和线性表极为相似，区别仅在于串 逻辑结构和线性表极为相似，区别仅在于串 极为相似 仅在于 数据对象约束为字符集。 约束为字符集 的数据对象约束为字符集。 串的基本操作和线性表有很大差别。 串的基本操作和线性表有很大差别。 基本操作和线性表有很大差别 线性表的基本操作中 大多以“单个元素” 的基本操作中， 在线性表的基本操作中，大多以“单个元素” 作为操作对象； 作为操作对象； 操作对象 的基本操作中，通常以“串的整体” 在串的基本操作中，通常以“串的整体”作为 操作对象。 操作对象。
20
二维数组的定义: 二维数组的定义: 数据对象: 数据对象 D = {aij | 0≤i≤b1-1, 0 ≤j≤b2-1} 数据关系: 数据关系 R = { ROW, COL } ROW={<ai,j,ai,j+1>|0≤i≤b1-1, 0≤j≤b2-2} COL={<ai,j,ai+1,j>|0≤i≤b1-2, 0≤j≤b2-1}

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

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

数组的访问方式是通过下标来访问，下标从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为每个元素所占的存储单元数③ 根据地址计算公式，可以通过地址公式同时在内存中访问数组中的任何元素。

Data structures
串的存储与操作
❖ 串的顺序存储与操作 ❖ 1.串的基本操作
(3) 求串长StrLength(s) 返回串s中字符的个数。 算法4.3 求串长度 int StrLength(char s[]) { int len=0;
while(s[len++]!='\0'); return --len; }
4.2(b)所示。当节点大小大于1时，由于串长不一定
是节点大小的整倍数，因此链表中的最后一个节点不
一定全被串值占满，此时通常要补上“#”或其他的
非串值字符(通常，“#”不属于串的字符集，是一个
特殊的符号)。 头指针
S
D
A
E
头指针
S
DATA
STR
UCTU
RE# #
空格符
Data structures
串的存储与操作
charch[CHUNKSIZE];
structChunk *next;
}Chunk;
typedef struct { /*串的链表结构*/
Chunk *head, *tail;/*串的头和尾指针*/
int curlen; /*串的当前长度*/
}LString;
Data structures
串的存储与操作
串（或字符串），是由零个或多个字符组成的有限序列。一般 记为：
s=‘a0a1...an-1’ (n>=0)
其中s是串的名，用单引号括起来的字符序列是串的值；串中字 符的数目n称为串的长度。
❖ 2.空串和空格串
零个字符的串称为空串，它的长度为零。
由一个或多个空格组成的串，称为空格串。它的长度是串中空格字符 的个数。

(13) DestroyString(&S)
//串销毁
}ADT String 北京林业大学信息学院
2021年1月9日
6
串的存储结构
顺序存储 链式存储
2021年1月9日
7
顺序存储表示
typedef struct{ char *ch;
int length; }HString;
//若串非空,则按串长分配存储区, //否则ch为NULL //串长度
S :ababcabcacbab
•
T :abc j
i指针回溯
S :ababcabcacbab
T : abc
S :ababcabcacbab
T : abc
2021年1月9日
13
BF算法设计思想
Index(S,T,pos)
• 将主串的第pos个字符和模式的第一个字符比较, 若相等，继续逐个比较后续字符; 若不等，从主串的下一字符起，重新与模式的第 一个字符比较。
//串的当前长度
}LString;
2021年1月9日
11
串的模式匹配算法
算法目的:
确定主串中所含子串第一次出现的位置（定位） 即如何实现教材P72 Index(S,T,pos)函数
算法种类：
•BF算法（又称古典的、经典的、朴素的、穷举的） •KMP算法（特点：速度快）
2021年1月9日
12
i
BF算法设计思想
(6) StrCopy(&T,S)
//串拷贝
(7) StrEmpty(S)
//串判空
(8) ClearString (&S)
//清空串
(9) Index(S,T,pos)

3.建立广义表的存储结构 假定广义表中的元素类型ElemType为chai类型，每个原子的值被限 定为英文字母。并假定广义表是一个表达式，其格式为：元素之间用一 个逗号分隔，表元素的起止符号分别为左、右圆括号，空表在其圆括号 内不包含任何字符。例如“(a，(b, c, d))”就是一个符合上述规定的广 义表格式。 建立广义表存储结构的算法同样是一个递归算法。该算法使用一个 具有广义表格式的字符串参数s,返回由它生成的广义表存储结构的头结 点指针h。在算法的执行过程中，需要从头到尾扫描s的每一个字符。当 碰到左括号时，表明它是一个表元素的开始，则应建立一个由h指向的表 结点，并用它的sublist域作为子表的表头指针进行递归调用，来建立子 表的存储结构；当碰到一个英文字母时，表明它是一个原子，则应建立 一个由h指向的原子结点；当碰到一个“）”字符时，表明它是一个空表， 则应置h为空。当建立了一个由h指向的结点后，接着碰到逗号字符时， 表明存在后继结点，需要建立当前结点(即由h指向的结点）的后继表； 当碰到右括号或分号字符时，表明当前所处理的表已结束，应该置当前 结点的link域为空。 4.输出广义表 5.广义表的复制
广义表的转换过程
为了使子表和原子两类结点既能在形式上保持一致，又能进
行区别，可采用如下结构形式：
其中，tag域为标志字段，用于区分两类结点。sublist或data
域由tag决定。若tag=0，表示该结点为原子结点，则第二个 域为data，存放相应原子元素的信息；若tag=l，表示该结点 为表结点，则第二个域为sublist，存放相应子表第一个元素 对应结点的地址。link域存放与本元素同一层的下一个元素所 在结点的地址，当本元素是所在层的最后一个元素时，link域 为NULL。 例：前面的广义表C的存储结构如下图所示(很多《数据结构 公教科书上称之为带表头结点的广义表的链表存储结构

数据结构复习 (数组和广义表)
a
第5章 数组和广义表
一、数组 1、数组的顺序存储方式和地址计算方法
数组的存储方式有：
（1）行优先存储方式 （2） 列优先存储方式 例5-1 二维数组 int a[10][10], 以行优先存储, 第1 个元素 的首址是100, 每个元素的长度为2,求A[4][5]的存储首址。
原子结点 tag=0 atom
例5-2：A=(( ),(e),2）对角矩阵
例：以三对角矩阵为例，按行主序方式存储，
仅存储非零部分。
将一个a[100][100]的三对角矩阵以行主序存入一
维数组B[298]中，元素a[65][64]在B数组中的位置k等
于。
a
3、稀疏矩阵的存储方式
——三元组法
矩阵A中有非零元个数s远远小于矩阵元素的
总数，则称A为稀疏矩阵。
ijv
1 2 12
0 12 9 0 0 0
M=
0 0 0 000
-3 0 0 0 0 14
0 0 24 0 0 0
13 9 3 1 -3 3 6 14 4 3 24
a
二、广义表 1、广义表的定义
广义表 ls=（d1,d2,……,dn）。其中每个元素可以是原子， 也可以是子表。 称d1为表头，d2,……,dn为表尾。 n: 表示广义表的长度，括号层数表示广义表的深度。
2、广义表与线性表的区别
线性表（a1,a2,……,an）中每个元素都具有相同的类型， 有两种存储结构：顺序表和链表。
广义表（d1,d2,……,dn）中每个元素可以是原子，也可以 是子表。可以将广义表看作是线性表的推广。由于原子和子 表的类型不同，所以只能用链式存储结构。
a
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，所以我们可以省略掉这些重复的步骤。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1.1 串的定义
串(string)(或字符串)是由零个或多个字符组成 的有限序列，一般记为： S="a1 a2 …… an" (n≥0) 串名：串的名字S。 串值：用双引号括起来的字符串序列，ai(1≤i≤n) 可以是字母、数字或其他字符。 串的长度：串中字符的个数n称为串的长度。 串相等：只有当两个串的长度相等，并且各个对 应位置上的字符都相等时，才能称为串相等。
4.1.1 串的定义
判断空串StrEmpty(S)：若S为空串，则返回TRUE，否则返回FALSE； 串复制StrCopy(&T,S)：将串S复制到串T； 串清空ClearString(S)：将S置空串； 串定位StrIndex(S,T,pos)：串S和T存在，T是非空串， 1≤pos≤StrLength(S)，若T是S的子串，返回T在S中第一次出现的位 置，否则返回0； 串置换Replace(&S,T,V)：串S，T和V存在，T是非空串，用V替换主串 S中出现的所有与T相等的不重叠的子串。例如：设S＝ "bbabbabba"，T＝"ab"，V＝"a"，则Replace(&S,T,V)的结果是S ＝"bbababa"； 串插入StrInsert(&S,pos,T)：1≤pos≤StrLength(S)+1，在串S的第pos 个字符之前插入串T； 串删除StrDelete(&S,pos,len)： 1≤pos≤StrLength(S)-len+1，从串S中 删去第pos字符起长度为len的子串； 串销毁DestroyString(&S) ：串S被销毁，并回收串空间； }ADT String
4.1.3 串的模式匹配算法

5.1 数组的定义
数组：按一定格式排列起来的 具有相同类型的数据元素的集合。
一维数组：若线性表中的数据元素为非结构的简单元素，
则称为一维数组。 一维数组的逻辑结构：线性结构。定长的线性表。 声明格式： 数据类型 变量名称[长度]；
例：int num[5] = {0，1，2，3，4};
数据结构
第五周 串、数组和广义表
数据结构
第五周 串、数组和广义表
数据结构
第五周 串、数组和广义表
内容回顾1 1、 串的概念； 2、 串的存储结构； 3、 串的运算。
数据结构 4.1 串类型的定义 基本概念
第五周 串、数组和广义表
串（也称字符串）：是由 0 个或多个字符组成的有限序列。 通常记为：s =― a1 a2 a3 … ai …an ‖ ( n≥0 )。 串的名 串的值 串的长度 字母、数字或其他字符
a00 a10 ……. am-1, 0 a01 a11 …….. am-1, 1 ………. a0, n-1 a1, n-1 …….. am-1, n-1
串的逻辑结构：和线性表极为相似。
区别：串的数据对象约定是字符集。 串的基本操作：和线性表有很大差别。 在线性表的基本操作中，大多以“单个元素” 作为操作对象； 在串的基本操作中，通常以“串的整体”作为 操作对象。例如：在串中查找某个子串、求 取一个子串、在串的某个位置上插入一个子 串以及删除一个子串等。
数据结构 以行序为主序存放：
第五周 串、数组和广义表 0 1
a00 a01 a00 a01 …….. a0, n-1 ……. a10 a11 …….. a1, n-1 a0, n-1 n -1 …………………. a10 n am-1, 0 am-1, 1 …….. am-1, n-1 a11 …….. 二维数组中任一元素 aij 的存储位置 a1, n-1 LOC(i, j) = LOC(0, 0) + (b2×i＋j )×L ………. 基地址或基址 二维数组的映象函数 am-1, 0 am-1, 1 某个元素的地址就是它前面所有行 所占的单元加上它所在行前面所有列元 …….. m*n -1 素所占的单元数之和。 am-1, n-1

5.1.2 串的操作
下面讨论串的操作，为了方便讨论，我们先定义如下几个串：
s1 = "It is a car"
s2 = "jeep" s3 = "car" 串的操作主要有： (1) 求串的长度。例如，s1的长度为11，s2的长度为4。
(2) 把一个串的值赋值给另一个串。若有s4＝s3，则s4 的值为 "car"。
String operator + (String & ob);
(3) 把两个串连接形成一个长度为两个串长度之和的新 串。设s5为s2和s3连接形成的新串，则s5="jeepcar"，即将 后面的串连接在前面串的尾部。
(4) 比较两个串的ASCII码值的大小。设str1和str2为两个串， 按下述规则得到两个串的比较结果。 若str1小于str2，比较结果为－1； 若str1等于str2，比较结果为0；
(8) 在一个串中插入另一个串。设把串str2插入到串str1 中，pos为要插入的起始位臵，则操作结果形成的新串长 度为str1和str2之和。
例如，把串s7=" not"，插入到串s1的位臵5处，则操作结 果形成的新串s8="It is not a car"。 (9) 从一个串中删除一个子串。设在串str中要删除长度 为length的子串，pos为要删除的子串在str中的起始位臵， 则删除后的新串长度为原长度减去length。 例如，要在s8中删除长度为4的子串，起始位臵为5，则 删除后的新串为s1。 (10) 从键盘输入一个字符序列。 (11) 在屏幕上显示一个字符序列。
C++的流库（iostream.h）为字符输入流cin（键盘）和字符 输出流cout（屏幕）提供I/O操作，使用方法如下： (1) 读串 Stream Variable >>str cin>>s4； //若输入"Hello!"，则s4 = "Hello!" (2) 写串 Stream Variable <<str cout << s4； //输出"Hello!" C++的串库提供的实现字符串操作的函数功能较强，但由于 函数定位通常用字符指针，所以使用的难度较大。

0 0 3 0 1 0 1 2 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 2 0
一个稀疏矩阵里存在大量的零元素，若 以常规方法，即以二维数组来存储稀疏矩 阵时产生如下问题: 1) 零值元素占了很多空间; 2) 如果进行计算，则会进行很多和零值 的运算，如是除法，还需判别除数是否为 零。
2 三角矩阵 以主对角线划分，三角矩阵有上三角 和下三角两种。如图所示。其中(a)图为下 三角矩阵：主对角线以上均为同一个常 数；(b)图为上三角矩阵，主对角线以下均 为同一个常数。
(1) 下三角矩阵 三角矩阵中的重复元素c可共享一个 存储空间，其余的元素正好有n(n+1)/2 个，因此，三角矩阵可压缩存储到向量 SA[0…n(n+1)/2]中，其中c存放在向量的 最后1个分量SA[n(n+1)/2]中。 该存储方式可节约n*(n-1)/2-1个存储 单元。
传统矩阵的转置算法为： for(col=1; col<=n ;++col) for(row=0 ; row<=m ;++row) b[col][row]=a[row][col] ;
时间复杂度为O(n×m) 当非零元素的个数tn和m×n同数量级时，算法 TransMatrix的时间复杂度为O(m×n2)。
以“行优先顺序”存储: (1) 第1行中的每个元素对应的(首)地址是： LOC[a1j]=LOC[a11]+(j-1) ×L (2) 第2行中的每个元素对应的(首)地址是： LOC[a2j]=LOC[a11]+n×L +(j-1) ×L (3) 第m行中的每个元素对应的(首)地址是： LOC[amj]=LOC[a11]+(m-1) n×L +(j-1) ×L

一、数据结构的章节结构及重点构成数据结构学科的章节划分基本上为:概论，线性表，栈和队列，串，多维数组和广义表，树和二叉树，图，查找，内排，外排，文件，动态存储分配。

对于绝大多数的学校而言，“外排，文件，动态存储分配”三章基本上是不考的，在大多数高校的计算机本科教学过程中，这三章也是基本上不作讲授的。

数据结构的章节比重大致为：1.概论:概念，时间复杂度。

2.线性表:基础章节，必考内容之一。

概念，算法设计题。

3.栈和队列:基本概念。

4.串:基本概念。

5.多维数组及广义表: 基本概念。

6.树和二叉树:重点难点章节，各校必考章节。

概念，问答，算法设计题。

7.图:重点难点章节，各校必考章节。

概念，问答，算法设计题。

8.查找:重点难点章节，概念，问答。

9.排序:重点难点章节，问答各种排序算法的排序过程二、各章节的主要内容：第一章概述主要内容：本章主要起到总领作用，为读者进行数据结构的学习进行了一些先期铺垫。

大家主要注意以下几点: （1）数据结构的基本概念。

（数据；数据元素；数据项；数据结构；数据的逻辑结构：线性和非线性，具体分为集合、线性结构、树形结构和图状结构；数据的存储结构：顺序存储和链式存储；运算）（2）算法的度量：时间效率和空间效率，分别用时间复杂度和空间复杂度度量，掌握时间复杂度的度量方法量方法。

（大O表示法）参考题目：填空题：1、数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容，分别是数据的逻辑结构、（）和（）。

2、数据结构按逻辑结构可分为两大类，它们分别是（）和（）3. 数据的物理结构主要包括（）和（）两种情况。

4．线性表，栈，队列和二叉树四种数据结构中（）是非线性结构，（）是线性结构。

5、线性结构中元素之间存在（）关系，树形结构中元素之间存在（）关系，图形结构中元素之间存在（）关系。

6、程序段的时间复杂度是_______。

for(i=1;i<=n;i++){ k++;for(j=1;j<=n;j++)x=x+k;}7．下列算法的时间复杂度是_____。

0603
2090
B5×4 = 0 8 0 0
0000
row col val
4000
0 12
0 44
1 06
1 28
2 19
3 03
现在，要通过A的 三元组表求其转置 矩阵B的三元组表。
row col val
0 16 0 33 1 02 1 29 2 18 4 04
16
三元组表的转置
方法1：设矩阵A是m行、n列、t个非0元素 从头到尾扫描A，将第0列的元素依次放入B（行号列号互换）; 从头到尾扫描A，将第1列的元素依次放入B（行号列号互换）; ．．．．．． 从头到尾扫描A，将第n-1列的元素依次放入B（行号列号互换）; 扫描A几趟？ 矩阵A的列数n
}tritype;
typedef struct { //三元组表
tritype data[MAXSIZE]; //三元组表存储空间
int mu, nu, tu;
//原矩阵的行数、列数、非0元素个数
}Tsmtype, *Tsmlink;
//三元组表说明符
14
三元组表
例 5.3 矩阵的转置。 求矩阵A的转置矩阵B，算法很简单：
ArrayInit(&A, n, d1, d2, ..., dn) ArrayDestroy(&A)
ArrayGet(A, i1, ..., in, &e)
ArrayAssign(&A, i1, ..., in, e) }ADT Array；
数组的基本操作一般不包括插入和删除
4
5.2 数组的存储结构
存储空间是在程序执行时动态分配的
n维数组A[u1][u2]…[un]

第一章：绪论1.1：数据结构课程的任务是：讨论数据的各种逻辑结构、在计算机中的存储结构以及各种操作的算法设计。

1。

2:数据：是客观描述事物的数字、字符以及所有的能输入到计算机中并能被计算机接收的各种集合的统称。

数据元素：表示一个事物的一组数据称作是一个数据元素,是数据的基本单位。

数据项：是数据元素中有独立含义的、不可分割的最小标识单位。

数据结构概念包含三个方面：数据的逻辑结构、数据的存储结构的数据的操作。

1.3数据的逻辑结构指数据元素之间的逻辑关系，用一个数据元素的集合定义在此集合上的若干关系来表示，数据结构可以分为三种：线性结构、树结构和图。

1.4:数据元素及其关系在计算机中的存储表示称为数据的存储结构,也称为物理结构。

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

2.1：算法：一个算法是一个有穷规则的集合，其规则确定一个解决某一特定类型问题的操作序列。

算法规则需满足以下五个特性：输入——算法有零个或多个输入数据。

输出-—算法有一个或多个输出数据,与输入数据有某种特定关系。

有穷性——算法必须在执行又穷步之后结束。

确定性—-算法的每个步骤必须含义明确，无二义性。

可行性—-算法的每步操作必须是基本的，它们的原则上都能够精确地进行，用笔和纸做有穷次就可以完成。

有穷性和可行性是算法最重要的两个特征。

2.2：算法与数据结构：算法建立数据结构之上,对数据结构的操作需用算法来描述。

算法设计依赖数据的逻辑结构，算法实现依赖数据结构的存储结构。

2。

3:算法的设计应满足五个目标:正确性：算法应确切的满足应用问题的需求，这是算法设计的基本目标.健壮性：即使输入数据不合适,算法也能做出适当的处理，不会导致不可控结高时间效率：算法的执行时间越短,时间效率越高。

果。

高空间效率：算法执行时占用的存储空间越少，空间效率越高。

可读性:算法的可读性有利于人们对算法的理解.2.4:度量算法的时间效率，时间复杂度，（课本39页）。

列优先，寻址函数： Loc(i,j) = Loc(r,c) + ((j-c) ×m + (i-r)) ×s
r≤i≤r+m-1，c≤j≤c+n-1 行优先，寻址函数： Loc(i,j) = Loc(r,c) + ((i-r) ×n + (j-c)) ×s
r≤i≤r+m-1，c≤j≤c+n-1 当r、c为0，寻址函数：
(4)求子串StrSub(S，i，piecelen)
操作条件 串S存在
操作结果 返回S的第i个字符开始的长 度为piecelen的子串。
(5)串比较StrCmp(S1，S2) 操作条件 串S1,S2存在。 操作结果 比较串的大小。
(6)子串定位StrIndex(S，T)
操作条件 串S，T存在。
操作结果 查找子串T在主串S中首次出 现的位置。如果S中不包含T，则返回 值为-1。
S1->len=piecelen ;
return OK;}
（3）串插入
StrInsert(Seqstring *S, Seqstring *T) {if(i>=S->len|| S->len+T->Ien>MAXSIZE)
printf(“不能插入”); else if(i==0) {for(k=S->len+T->len-
i (i – 1) +j-1 当 i≥j
2 k=
j (j – 1) +i-1 当 i＜j
2
a12
a13
= =
a11 a21 a22 a31 k= 0 1 2 3
ann n(n+1)
2 -1
2) 三角矩阵