串的抽象数据类型ADT

定义串的一些操作
服务器君一共花费了213.754 ms进行了6次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

串的逻辑结构和线性表很相似,不同之处在于串针对的是字符集,也就是串中的元素都是字符,哪怕串中的字符是“123”这样的数字组成,或者“2010-10-1CT这 样的日期组成,它们都只能理解为长度为3和长度为10的字符串,每个元素都是字符而已。

因此,对于的基本操作与线性表是有很大差别的。线性表更关注的是单个元素的操作,比如査找一个元素,插入或删除一个元素,但串中更多的是査找子串位置、得到指定位置子串、替换子串等操作。

为了更加深入地了解串这个数据结构,我们需要定义串的ADT,然后再实现串的一些常见操作。串的ADT定义如下:

ADT 串 (String)

Data
	串中的元素仅由一个字符组成,相邻元素具有前驱和后继关系.
	
Operation
StrAssign (&T, chars)
	初始条件:chars是字符串常量。
	操作结果:生成一个其值等于chars的串T。
StrCopy (&T, S)
	初始条件:串S存在。
	操作结果:由串S复制得串T。
StrEmpty(S)
	初始条件:串S存在。
	操作结果:若S为空串,则返回TRUE,否则返回FALSE。 
StrCompare(S, T)
	初始条件:串S和T存在。
	操作结果:若S>T,则返回值>0;若S=T,则返回值=0;若S < T,则返回值 < 0。
StrLength(S)
	初始条件:串S存在。
	操作结果:返回S的元素个数,称为串的长度。
ClearString (&S)
	初始条件:串S存在。
	操作结果:将S清为空串。
Concat (&T, S1, S2)
	初始条件:串S1和S2存在。
	操作结果:用T返回由S1和S2联接而成的新串。
SubString(&Sub, S, pos, len)
	初始条件:串S存在,1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1
	操作结果:用Sub返回串S的第pos个字符长度为len的子串。
Index(S, T, pos)
	初始条件:串S和T存在,T是非空串,1≤pos≤StrLength(S)。
	操作结果:若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置;否则函数值为0。
Replace (&S, T, V)
	初始条件:串S, T和V存在,T是非空串。
	操作结果:用V替换主串S中出现的所有与T相等的不重叠的子串。
StrInsert (&S, pos, T)
	初始条件:串S和T存在, 1≤pos≤StrLength(S)+1。
	操作结果:在串S的第pos个字符之前插入串T。
StrDelete (&S, pos, len)
	初始条件:串S存在, 1≤pos≤StrLength(S)-len+1。
	操作结果:从串S中删除第pos个字符起长度为len的子串。
DestroyString (&S)
	初始条件:串S存在。
	操作结果:串S被销毁。

endADT

以下5个操作称为最小操作子集:

  • 串赋值StrAssign
  • 串比较StrCompare
  • 求串长StrLength
  • 串联接Concat
  • 求子串SubString
  • 在上述抽象数据类型定义的13种操作中,这5种操作不可能利用其他串操作来实现,但其他串操作均可在这个最小操作子集上实现。

延伸阅读

此文章所在专题列表如下:

  1. 数据结构里的串是什么东西?
  2. 如何比较串的大小
  3. 串的抽象数据类型ADT
  4. 串的顺序存储结构
  5. 串最基本的5个操作的C实现
  6. 寻找子串在主串中的位置
  7. 如何在串中插入串
  8. 如何在串中删除特定长度的子串
  9. 字符串中的子串替换
  10. 题外话:谈谈malloc()和free()

本文地址:http://www.nowamagic.net/librarys/veda/detail/2403,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/2403

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《计算机程序的构造和解释(原书第2版)》 艾伯森 (译者), 裘宗燕 (译者), 等 (译者)

《计算机程序的构造和解释》(原书第2版)1984年出版,成型于美国麻省理工学院(MIT)多年使用的一本教材,1996年修订为第2版。在过去的二十多年里,《计算机程序的构造和解释》(原书第2版)对于计算机科学的教育计划产生了深刻的影响。第2版中大部分重要程序设计系统都重新修改并做过测试,包括各种解释器和编译器。作者根据其后十余年的教学实践,还对其他许多细节做了相应的修改。《计算机程序的构造和解释》(原书第2版)自出版以来,世界各地已有100多所院校采用《计算机程序的构造和解释》(原书第2版)做教材,其中包括美国斯坦福大学、美国普林斯顿大学、英国牛津大学、日本东京大学等。

更多计算机宝库...