发布时间 : 星期一 文章数据结构-朱二周更新完毕开始阅读12798ad2c9d376eeaeaad1f34693daef5ef7132a
串的数据结构定义和实现。 （2）串的表示和实现
在程序设计语言中，如何在内存中表示。表示类型有： (a) 定长顺序存储表示，结构定义：
#define MAXSTRLEN 255
Typedef unsigned char SString[MAXSTRLEN + 1];
定长顺序存储表示的串的操作： 串连接Concat(&T, S1, S2)
求子串 SubString(&Sub, S, pos ,len) (b) 堆分配存储表示,结构定义：
Typedef struct { Char * ch; Int length; } HString;
堆分配存储表示的串的操作：
插入：Status StrInsert(HString &S, int pos, HString T) 赋值：Status StrAssign(HString &T, char * chars) 返回字符长度：int StrLength(HString S) 清空：int Status ClearString(HString &S)
连接：Status Concat(HString &T, HString S1, HString S2) 子串：Status SubString( HString &Sub, HString S ,int pos, int len) (c) 串的块链存储表示, 结构定义：
#define CHUNKSIZE 80 Typedef struct Chunk {
Char ch[CHUNKSIZE]; Struct Chunk * next; }Chunk;
Typedef struct {
Chunk * head, *tail; Int curlen; }LString; （3）串的模式匹配算法
(a) 求子串位置的定位函数 Index(S, T, pos)。基本思想是: 从主串S的第pos
个字符起和模式的第一个字符比较之，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式的字符比较之。 (b) 最快情况下时间复杂度是O（n *m）。
(c) 模式匹配的一种改进算法：KMP算法。算法复杂度是O（m）。 （4）串操作应用举例。 （二）基本要求
(1) 了解串的结构，定义，表示、实现，还有一些基本的匹配算法。 (2) 熟悉掌握串的内存分配表示和实现。
（三）重点、难点
重点：
(1) 了解串的特点。
(2) 了解串的几种实现方式。 (3) 了解几种方法的操作。 (4) 串的模式匹配算法。 难点：
(1) 几种串的实现方法。 (2) KMP算法的思想。 （四）作业及课外学习要求：
(1) 实现一个完整的字符串的类，要求：
实现完成的操作，包括插入，赋值，清空，定位子串等操作； 考虑效率；
考虑内存使用。 (2) 深入考虑KMP算法，看有没有进一步优化的可能性。
本知识点的讲授和学习，可以支撑“毕业要求1工程知识”中的“指标点1.1和1.3：能够运用数学与自然科学基础知识，理解软件工程中涉及的相关科学原理；掌握软件工程专业基本理论，以及基本分析与设计方法，用于解决复杂软件工程问题”，使学生掌握将工程基础知识和本专业的基本理论知识向结合，锻炼学生的工程实践能力，并为后续课程的学习奠定理论基础。 第5章 数组与广义表 ( 6学时) （一）基本内容：
（1） 数组的定义与基本操作
数组的定义：
数组的特点是每个数据元素可以又是一个线性表结构。若线性表中的数据元素为非结构的简单元素，则称为一维数组，即为向量；若一维数组中的数据元素又是一维数组结构，则称为二维数组；依次类推，若二维数组中的元素又是一个一维数组结构，则称作三维数组
二维数组可以看成是这样一个定长线性表：它的每个数据元素也是一个定长的线性表。
数组的基本操作：
数组结构一般在创建时就确定了组成该结构的行向量数目和列向量数目，因此，在数组结构中不存在插入、删除元素的操作。 二维数组结构的基本操作：
给定一组下标，修改该位置元素的内容 Assign(A,item,index1,index2)； 给定一组下标，返回该位置的元素内容 Value(A,item,index1,index2)。
（2）数组的存储结构
数组一般采用顺序存储结构，从理论上讲，数组结构也可以使用两种存储结构，即顺序存储结构和链式存储结构。然而，由于数组结构没有插入、删除元素的操作，所以使用顺序存储结构更为适宜。换句话说，一般的数组结构不使用链式存储结构。
数组的存储表示：
组成数组结构的元素可以是多维的，但存储数据元素的内存单元地址是一维的，因此，在存储数组结构之前，需要解决将多维关系映射到一维关系的问题。
对于数组，一旦规定了它的维数和各维的长度，便可为它分配存储空间。反之，只要给出一组下标便可求得相应数组元素的存储位置。在C语言中数组的存储采用以行序为主序的存储结构。假设每个数据元素占L个存储单元，则上述二维数组A中任一元素aij的存储位置可由下式确定：
LOC(i,j)=LOC(0,0)+(n*i+j)*L 数组结构的定义：
#define MAX_ROW_INDEX 10 #define MAX_COL_INDEX 10 typedef struct {
ElemType elem[MAX_ROW_INDEX][MAX_COL_INDEX] ;
} Array;
基本操作算法举例： （a）给数组元素赋值：
void Assign(Array*A,ElemType item,int index1,int index2){
if (index1<0||index1>=MAX_ROW_INDEX||
index2<0||index2>=MAX_COL_INDEX) exit(ERROR); else A->item[index1][index2]=item; }
（b）返回给定位置的元素内容
int Value(Array A,ElemType *item,int index1,int index2){
if
(index1<0||index1>=MAX_ROW_INDEX||index2<0||index2>=MAX_COL_INDEX)
return FALSE;
else { *item= A.item[index1][index2];
return OK;} } （3）矩阵的压缩存储
矩阵是在很多科学与工程计算中遇到的数学模型。在数学上，矩阵是这样定义的：它是一个由m×n个元素排成的m行（横向）n列（纵向）的表。 (a)特殊矩阵
所谓特殊矩阵就是元素值的排列具有一定规律的矩阵。常见的这类矩阵有：对称矩阵、下（上）三角矩阵、对角线矩阵等等。 (b)对称矩阵
对称矩阵的特点是aij=aji
(c)下（上）三角矩阵
其特点是以主对角线为界的上（下）半部分是一个固定的值，下（上）半部分的元素值没有任何规律。 (d)对角矩阵
其特点是所有的非零元素都集中在以主对角线为中心的带状区域中。 对于这些特殊矩阵，应该充分利用元素值的分布规律，将其进行压缩存储。选择压缩存储的方法应遵循两条原则：一是尽可能地压缩数据量，二是压缩后仍然可以比较容易地进行各项基本操作。 三种特殊矩阵的压缩方法： （a）对称矩阵
对称矩阵的特点是aij=aji。一个n×n的方阵，共有n2个元素，而实际上在对称矩阵中有n(n-1)/2个元素可以通过其他元素获得。压缩的方法是首先将二维关系映射成一维关系，并只存储其中必要的n(n+1)/2个（主对角线和下三角）元素内容，这些元素的存储顺序以行为主序。 （b）下（上）三角矩阵
下三角矩阵的压缩存储与上面讲述的对称矩阵的压缩存储一样，只是将上三角部分的常量值存储在0单元，下三角和主对角上的元素从1号单元开始存放。 （c）对角矩阵
我们以三阶对角矩阵为例讨论一下它的压缩存储方法。对于对角矩阵，压缩存储的主要思路是只存储非零元素。这些非零元素按以行为主序的顺序，从下标为1 的位置开始依次存放在一维数组中，而0位置存放数值0。 (4 )稀疏矩阵的压缩存储
若一个m×n的矩阵含有t个非零元素，且t远远小于m*n，则我们将这个矩阵称为稀疏矩阵。
(a)稀疏矩阵的压缩存储方法——三元组表示法。
矩阵中的每个元素都是由行序号和列序号唯一确定的。因此，我们需要用三项内容表示稀疏矩阵中的每个非零元素，即形式为：
(i,j,value)
其中，i表示行序号，j表示列序号，value表示非零元素的值，通常将它称为三元。我们将稀疏矩阵中的所有非零元素用这种三元的形式表示，并将它们按以行为主的顺序存放在一个一维数组中，就形成了我们所说的三元组表示法。类型定义：
#define MAX_SIZE 100 最大的非零元素个数 typedef struct{
int i,j; //行序号、列序号
EntryType value; //非零元素值 }Three_Item; typedef struct {
Three_Item Item[MAXSIZE];//存储非零元素的一维数组
int rows,cols,tu; //稀疏矩阵的总行数、列数及非零元素个数 }Matrix;
(b)矩阵的转置