数据结构串的定义

数据结构教案

第四章 串

数据结构教案 第4章 串

目 录

4.1 串类型定义 ............................................................................................................................. 2 4.2 串的表示与实现 ..................................................................................................................... 3

4.2.1 定长顺序存储表示 ...................................................................................................... 3 4.2.2 堆分配存储表示 .............................................................................

实验报告四 串操作

班级： 姓名： 学号： 专业：

一、 实验目的：

（1） 掌握串的定义、术语。 （2） 掌握串的基本操作算法。 （3） 掌握串的匹配算法。 二、 实验内容：

1. 在常量串MyString类中，增加以下方法，并求各算法的时间复杂度。 public MyString trim() //删除串中所有空格 public char[] toCharArray() //返回字符数组

public MyString toLowerCase() //返回将大写字母转换成小写字母的字符串 public MyString toUpperCase() //返回将小写字母转换成大写字母的字符串

public MyString replace(char old, char newc) //用字符newc替换串中的字符old public Boolean equals(Object obj) //判断两个串是否相等

public Boolean equalsIgnoreCase(String1 str) //判断两个串是否相等,忽略大小写 public int compareTo

#include #include #define MAXSIZE 100 typedef struct{ char data[MAXSIZE];

int length; }SqString;

int index_bf(SqString *s,SqString *t,int start); void getNext(SqString *t,int next[]);

int index_kmp(SqString *s,SqString *t,int start,int next[]); void show_index();

int index_bf(SqString *s,SqString *t,int start){ int i=start; int j=1; while(i<=s->length &&j<=t->length ){

if(s->data[i]==t->data[j]) {++i;++j;} else{i=i-j+2; j=1;} }

if(j>t->data[0]) return i-t->data[0]; else return 0;

}

void getNext

第四章 串

一、选择题

1．下面关于串的的叙述中，哪一个是不正确的？（ ）【北方交通大学 2001 一、5（2分）】

A．串是字符的有限序列 B．空串是由空格构成的串

C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 2 若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行 concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2)))

其结果为（ ）【北方交通大学 1999 一、5 （25/7分）】 A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345 E．ABC###G1234 F．ABCD###1234 G．ABC###01234

3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ） A．求子串 B．联接 C．匹配 D．求串长

【北京邮电大学

第四章 串

一、选择题 1.B 2.E 3.C 4.A 5.C 6.A 7.1D 7.2F 8.B注 9.D 10.B 注：子串的定义是：串中任意个连续的字符组成的子序列，并规定空串是任意串的子串，任意串是其自身的子串。若字符串长度为n（n>0），长为n的子串有1个，长为n-1的子串有2个，长为n-2的子串有3个，??，长为1的子串有n个。由于空串是任何串的子串，所以本题的答案为：8*（8+1）/2+1=37。故选B。但某些教科书上认为“空串是任意串的子串”无意义，所以认为选C。为避免考试中的二意性，编者认为第9题出得好。 二、判断题

1.√ 2.√ 3.√

三．填空题

1．(1) 由空格字符（ASCII值32）所组成的字符串 (2)空格个数 2．字符 3．任意个连续的字符组成的子序列 4．5 5.O(m+n) 6．01122312 7．01010421 8．(1)模式匹配 (2)模式串

9．(1)其数据元素都是字符(2)顺序存储(3)和链式存储(4)串的长度相等且两串中对应位置的字符也相等

10．两串的长度相

福建农林大学计算机与信息学院实验报告

数据结构的程序实现

一、 实验目的和要求

1) 进一步了解数据结构的实现策略。 2) 掌握动态结构的静态实现方法。 3) 了解大批量数据的组织策略。 4) 掌握数据结构在问题建模中的应用。 二、 实验内容和原理 实验内容：

编程实现Josephus问题。 实验原理：

【问题描述】设有n个人围坐一圈并由1~n编号。从某个人（例如编号为k的人）开始报数，数到m的人出列；接着从出列的下一个人开始重新1~m报数，数到m的人又出列；如此反复地报数和出列，知道最后一个人出列为止。试设计确定这n个人出列序列的程序。

【解题思路】有问题描述可以很自然地联想到循环列表，用循环列表对Josephus问题建模，可以做到程序世界和问题世界的完全一致性，符合面向对象的设计思想。考虑到反复报数的过程，可选用不带头结点的单循环链表，以避免报数过程中识别头结点的麻烦。由此，程序中可以先构建一个具有n个结点的单循环链表，然后从约定的结点开始1到m计数，计到m时从链表中删除对应结点；接着从被删除结点的下一个结点起计数，知道最后一个结点从链表中删除后结

束。

三、 实验环境 Windows XP系统 visual c++6.0 四、 实验习

数据结构

1

1.为解决计算机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。（全国统考2009） A．栈 B．队列 C．树 D．图

2.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后入队Q，若出队序列为e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是（ ）。（全国统考2009）

A．1 B．2 C．3 D．4

3.若元素abcdef依次进栈，允许进栈、出栈交替进行，不允许连续三次进行出栈操作，则不可能得到的出栈序列是（ ）。（全国统考2010）

A．dcebfa B．cbdaef C．dbcaef D．afedcb 4.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是（ ）。（全国统考2010） A．bacde B．dbace C．dbcae D．ecbad

5.元素abcde依次进入初

第四章 字符串的应用

【实验目的】

1. 熟练掌握字符串的数据类型定义以及字符串的五种基本操作的定义，并能利用这些基本操作实现字符串的其他基本操作的方法。

2. 熟练掌握字符串串的定长顺序存储结构上实现字符串的各种操作的方法。 3. 理解字符串的堆分配存储表示以及在其上实现字符串操作的基本方法。

4. 熟练掌握串的基本操作类型的实现方法，其中文本模式匹配方法是一个难点，在掌握了BF算法的基础上理解改进的KMP算法。

5. 了解一般文字处理软件的设计方法。

第一节 知识准备

一、 有关串几个重要概念

1. 串（字符串）：零个或多个字符组成的有限序列。一般记作s=\?an\ 2. 长度：串中字符的数目

3. 空串：零个字符的串，其长度为零

4. 子串和主串：串中任意个连续的字符组成的子序列称为该串的子串；包含子串的串相应地称为主串，字符在序列中的序号为该字符在串中的位置。

5. 当两个串的长度相等，并且各个对应位置的字符都相等时称为两串相等。 6. 空格串：由一个或多个空格组成的串‘ ’，同空串是完全不同的。

二、 串的抽象数据类型定义 ADT String{

数据对象：D={ | ∈CharacterSet, i=1,2,...,n, n

数据结构

为了编写一个“好”的程序，必须分析待处理的对象特性以及各处理对象之间存在的关系.这就需要学习“数据结构”。因此，简单地说来，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。在信息学奥赛中需要学习线性表、树、图三种数据结构，在后面我们将一一介绍.

4.1 栈

线性表是最常用且比较简单的一种数据结构，它是由有限个数据元素组成的有序集合，每个数据元素有一个数据项或者含多个数据项.例如我们前面所学过的数组是线性的数据结构.

下面介绍的栈是一种线性表，但是对它的插人和删除等操作都限制在表的同一端进行，即栈顶，而另一端则称为是栈底.打个形象地比喻，用桶堆积物品，先堆进来的压在底下，随后一件一件往上堆.取走时，只能从上面一件一件取.堆和取都在顶部进行，底部一般是不动的.所以，栈也称为后进先出表(LIFO表).

通常栈可以用顺序的方式存储，分配一块连续的存储区域来存放栈中的数据项，即用定长为N的数组S来表示，并用一个变量TOP指向当前栈顶(如图4-1-1).若TOP=0，表示栈空，T0P=N时栈满.我们一般把插人操作称为进栈(PUSH)，此时TOP加1，删除操作则称为出栈

《数据结构》第4章、串存储与基本操作的实现

第四章 串存储与基本操作的实现

本章学习要点

◆熟悉串的相关概念以及串与线性表的关系

◆重点掌握串的定长存储、堆分配存储的表示方法与基本操作的实现

◆了解串的各种存储结构，能根据需要合理选用串的存储结构解决实际问题

“串”(string)，是字符串的简称，它是一种特殊的线性表，其特殊性在于组成线性表的数据元素是单个字符。字符串在计算机处理实际问题中使用非常广泛，比如人名、地名、商品名、设备名等均为字符串。同样在文字编辑、自然语言理解和翻译、源程序的编辑和修改等方面，都离不开对字符串的处理。

4.1串的基本概念

4.1.1串的概念

1．串的定义

串（string）是由n个字符组成的有限序列，记为：S=”a0a1a2…an-1” (n≥0)。

其中，S是串的名字，字符序列a0a1a2…an-1是串的值，ai(0≤i≤n-1)可以是字母、数字或其他字符元素；由于在C语言系统中数组元素的下标是从0开始的，所以串中所含元素的序号等于该元素的下标值加1；串中所含字符的个数n称为该串的长度，长度为0的字符串称为空串（null string）。

从串的定义可以看出，串实际上是数据元素为字符的特殊的线性表。 例如