当前位置：文档之家 › 数据结构-4 串

数据结构-4 串

  • 格式：docx
  • 大小：25.29 KB
  • 文档页数：3

数据结构-4 串

数据结构 4 串

在计算机科学中，数据结构是组织和存储数据的方式，以便能够有效地进行操作和访问。今天，咱们来聊聊数据结构中的“串”。

什么是串呢？简单来说，串就是由零个或多个字符组成的有限序列。这就好比我们日常说的一句话、一篇文章中的一段文字，都是串的具体表现形式。

串在计算机中的应用非常广泛。比如说，在文本编辑中，我们输入的每一行文字都可以看作是一个串；在网络通信中，传输的各种信息也常常以串的形式存在；在数据库中，存储的字符数据也可以理解为串。

为了更好地处理串，计算机科学家们设计了各种各样的操作和算法。首先是串的存储结构。常见的有两种：顺序存储和链式存储。

顺序存储就像是把一串字符一个挨着一个地放在连续的内存空间里。这样的好处是可以快速地随机访问串中的任意字符，但缺点是在插入或删除字符时可能需要大量的移动操作。

链式存储则是通过节点把字符连接起来，每个节点存储一个字符以及指向下一个节点的指针。这种方式在插入和删除操作时比较方便，但随机访问的效率相对较低。 接下来，咱们聊聊串的比较操作。比较两个串是否相等是很常见的需求。这可不是简单地看看两个串长得一不一样，还得考虑字符的顺序和数量。常见的比较方法有逐个字符比较，从串的开头一个一个比下去，直到发现不同或者其中一个串结束。

再说说串的模式匹配。这是一个很重要的操作，比如说要在一篇长文章中找到某个特定的关键词或者短语，这就用到了模式匹配算法。其中，著名的有朴素模式匹配算法和 KMP 算法。

朴素模式匹配算法的思路很直接，就是从主串的开头开始，逐个与模式串进行匹配，如果匹配不成功就将模式串往后移动一位继续匹配。这个算法简单易懂，但效率不是很高，特别是在主串和模式串长度较长时。

KMP 算法则通过对模式串的预处理，计算出一个 next 数组，利用这个数组可以在匹配不成功时更有效地移动模式串，从而提高匹配的效率。

除了上面说的这些，串还有很多其他的操作，比如串的连接、子串提取、串的替换等等。

在实际应用中，选择合适的串操作和算法取决于具体的问题和需求。比如，如果需要频繁地进行插入和删除操作，可能链式存储结构更合适；如果对随机访问要求较高，顺序存储就更好。而在进行模式匹配时，如果对效率要求高，KMP 算法就是不错的选择。 总之，串作为一种重要的数据结构，在计算机科学的众多领域都发挥着关键作用。理解和掌握串的相关知识和操作，对于我们编写高效、准确的程序至关重要。无论是处理文本数据、进行信息检索，还是实现各种与字符相关的功能，串都为我们提供了有力的工具和方法。

希望通过今天的介绍，您对数据结构中的串有了更清晰的认识和理解。在未来的学习和工作中，能够灵活运用串的相关知识，解决更多复杂的问题。

合集下载

数据结构求子串

数据结构求子串

实验三

一、实验目的及要求

理解、掌握串的有关概念，串的存储形式及常见基本的实现。

二、实验环境

硬件：计算机 软件：Microsoft Visual C++

三、实验内容

用定长顺序存储表示串，实现求子串的操作。

四、调试过程及实验结果

在输入字符串时出现错误，由于scanf("%c",&S[i]);中&S[i]错误写成S[i]。

五、总结

通过本次实验，加深了我对串的理解，了解了串的一些基本操作，看似很简单的操作，很少写程序的人，在编译过程中还是会遇到许多错误，所以只有不断写程序，编译才能发现问题，提高自己的编程能力。

六、附录（源程序清单）

#include

#define T 22

#define MAXSTRLEN 255

typedef unsigned char SString[MAXSTRLEN+1];

int InitString(SString &S);

int SubString(SString &Sub,SString S,int pos,int len);

int main()

{

SString S,Sub;

int pos,len;

S[0]=T;

InitString(S);

SubString(Sub,S,pos,len); 课程名称：数据结构 班级：嵌入式1班 完成日期：2011、10、27

姓名郝祥海 学号：1010431079 指导教师：

实验名称：串的基本操作 实验序号： 实验成绩： return 0;

}

int InitString(SString &S)

{

printf("请输入字符串:");

for(int i=1;i<=S[0];i++)

scanf("%c",&S[i]);

return 0;

}

int SubString(SString &Sub,SString S,int pos,int len)

数据结构4,5串、数组练习题

数据结构4,5串、数组练习题

串、数组和稀疏矩阵 1、串是一种特殊的线性表，请从存储和运算两方面分析它的特殊之处。

2、设字符串S= 'aabaabaabaac'，P= 'aabaac'

(1) 给出S和P的next值

012123456789 012123

(2) 若S作主串，P作模式串，试给出KMP算法的匹配过程。

利用KMP算法的匹配过程：

第一趟匹配：aabaabaabaac

aabaac(i=6,j=6)

第二趟匹配：aabaabaabaac

(aa)baac

第三趟匹配：aabaabaabaac

(成功) (aa)baac

3、假设有二维数组 A6×8，每个元素用相邻的 6 个字节存储，存储器按字节编址。已知 A 的起始存储位置(基地址)

为 1000，计算：

(1) 数组 A 的体积（即存储量）;

(2) 数组 A 的最后一个元素 a57 的第一个字节的地址;

(3) 按行存储时，元素 a14 的第一个字节的地址;

(4) 按列存储时，元素 a47 的第一个字节的地址。 (1）6×8×6 = 288Byte (2）1000+288-6=1282； (3）1000+(1×8+4)×6=1072 (4）1000+(7×6+4)×6=1276 4、一个稀疏矩阵A如图所示 (1) 给出三元组存储示意图； (2) 给出带行指针向量的链式存储示意图； (3) 给出十字链表存储示意图。 （1） （2） （3）

030000020500000000900001A = 4×6

数据结构-数据结构题库

数据结构-数据结构题库

1 第一章 绪论

一．单项选择题

1．数据对象是指______。

A. 描述客观事物且由计算机处理的数值、字符等符号的总称

B. 数据的基本单位

C. 性质相同的数据元素的集合

D. 相互之间存在一种或多种特定关系的数据元素的集合

2．在数据结构中，数据的基本单位是_________。

A. 数据项 B. 数据类型 C. 数据元素 D. 数据变量

3．数据结构中数据元素之间的逻辑关系被称为______。

A. 数据的存储结构 B. 数据的基本操作 C. 程序的算法 D. 数据的逻辑结构

4．在数据结构中，与所使用计算机无关的是数据的_______。

A. 存储结构 B. 逻辑和物理结构 C. 逻辑结构 D. 物理结构

5．在链式存储结构中，数据之间的关系是通过________体现的。

A. 数据在内存的相对位置 B. 指示数据元素的指针

C. 数据的存储地址 D. 指针

6．在定义ADT时，除数据对象和数据关系外，还需说明_______。

A. 数据元素 B. 算法 C. 基本操作 D. 数据项

7．计算算法的时间复杂度是属于一种_______。

A. 事前统计的方法 B. 事前分析估算的方法

C. 事后统计的方法 D. 事后分析估算的方法

8．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是_______。

A. n2 B. nlogn C. n D. logn

9．设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为_______。

A. O(1) B. O(n) C. O(200n) D. O(nlog2n)

10．有如下递归函数fact(a)，其时间复杂度为_________。

int fact(int a)

{

if(n==0)

retrun 1;

else

return(n*fact(n-1));

数据结构——串实践报告

数据结构——串实践报告

实 验 报 告

课程名称： 数据结构实践课

实验项目： 定长串存储方法

姓 名：

专 业：

班 级：

学 号：

计算机科学与技术学院

实验教学中心

2017 年 9 月 23 日 成绩：

哈尔滨理工大学计算机科学与技术学院实验教学中心 实验报告

实验项目名称： 串的定长存储表示方法

一、实践目的：

1. 熟练掌握串的定长顺序存储表示方法。

2. 利用串的基本操作实现相关算法。

二、实践内容：

1. 实现串的定长顺序存储表示的基本操作。并用主程序进行多次验证。

2. 设s='abcdefghijk'、t='cde'为两个字符串，利用定长顺序存储结构的串操作，判断t是否为s的子串。如果是，输出子串所在位置（第一个字符）。编程实现。

3. 已知三个字符串分别为s=’ababababcaabcbcaaaaaa’，s1=’caab’, s2=’bcb’。利用所学字符串基本运算的函数得到结果串为：s3=’caabcbcaaaaaacaaaaaa’。编程实现。

三、实验用设备仪器及材料

计算机

四、实验原理及接线

五、实验操作步骤

// main4-1.cpp 检验bo4-1.cpp的主程序

// c1.h (程序名)

#include

#include

#include // malloc()等

#include // INT_MAX等

#include // EOF(=^Z或F6),NULL

#include // atoi()

#include // eof()

哈尔滨理工大学计算机科学与技术学院实验教学中心 实验报告

#include // floor(),ceil(),abs()