字符串集合由称为什么的规则来描述（字符是什么）

本文目录

• 字符是什么
• 程序设计语言|正规式
• 什么是字符串请举例说明
• 表示集合的方法
• 求数据结构题

字符是什么

字符是电子计算机或无线电通信中字母、数字、符号的统称，是数据结构中最小的数据存取单位，通常由8个二进制位（一个字节）来表示一个字符。

为了方便理解，可以将字符简单地理解为用输入法单独打出的任何单个的内容（空格也算是字符）。对于中文和英文而言，以下内容分别都是1个字符。

（1）1个中文字，例如“是”。

（2）1个英文字母，例如“T”。

（3）1个中文标点符号，例如“。”。

（4）1个英文标点符号，例如“．”。

字符的作用

针对微软公共语言运行库的应用程序使用编码将字符表示形式从本机字符方案映射至其他方案。应用程序使用解码将字符从非本机方案映射至本机方案。

电脑和通讯设备会使用字符编码的方式来表达字符。意思是会将一个字符指定给某个东西。传统上，是代表整数量的位元序列，如此，则可透过网络来传输，同时亦便于储存。

两个常用的例子是ASCII和用于统一码的UTF-8。根据谷歌的统计，UTF-8是最常用于网页的编码方式。相较于大部分的字符编码把字符对应到数字或位元串，摩斯密码则是使用不定长度的电子脉冲的序列来表现字符。

程序设计语言|正规式

词法分析是把构成源程序的字符串转换成单词符号序列。词法规则可用 3型文法 （正规文法）或正规表达式描述，他产生的集合是语言基本字符集Σ（字母表）上的字符串的一个子集，称为正规集。

正规式是一种表示正规集的工具，正规式是描述程序语言单词的表达式，对于字母表Σ。

正规式（正规表达式）的运算符有3个，优化级从高到低顺序排列为：*（闭包）、·（连接，可省略）、|（或）。

正规式  →  正规集

ab  →  字符串ab构成的集合

a|b  →  字符串a、b构成的集合

a*  →  由0个或多个a构成的字符串集合

(a|b)*  →  所有字符a和b构成的串的集合

a(a|b)*  →  以a为首字符的a、b字符串的集合

(a|b)*abb  →  以abb结尾的a、b字符串的集合

有限自动机可以转换为正规式，正规式也可以转换为有限自动机。
词法分析器的构造步骤：

1）用正规式描述语言中的单词构成规则。

2）为每个正规式构造一个NFA，它识别正规式所表示的正规集。

3）将构造出的NFA转换成等价的DFA。

4）对DFA进行最小化处理，使其最简。

5）从DFA构造词法分析器。

什么是字符串请举例说明

由数字、字母、下划线组成的一串字符叫做字符串。

字符串的长度是在字符串中字符的数目（序列的长度），它可以是任何非负整数。“空串”是在Σ上的唯一的长度为0的字符串，并被指示为ε或λ。在Σ上的所有长度为n的字符串的集合指示为Σn。

例如：如果Σ={0,1}则Σ2={00,01,10,11}。注意Σ0={ε}对于任何字母表Σ。在Σ上的所有任何长度的字符串的集合是Σ的Kleene闭包并被指示为Σ*。

扩展资料：

字符串的转换：

用 (string) 标记或者strval()函数将一个值转换为字符串。当某表达式需要字符串时，字符串的转换会在表达式范围内自动完成。布尔值TRUE将被转换为字符串 "1"，而值FALSE将被表示为 ""（即空字符串）。这样就可以随意地在布尔值和字符串之间进行比较。

整数或浮点数数值在转换成字符串时，字符串由表示这些数值的数字字符组成（浮点数还包含有指数部分）。对象将被转换成字符串 "Object"。如果因为调试需要，需要将对象的成员变量打印出来。如果希望得到该对象所依附的类的名称，需要使用函数get_class()。

表示集合的方法

表示集合的方法有两种，一种是枚举法，另一种是描述法。

一、枚举法

1、枚举法也称为列举法，顾名思义，就是把集合中的元素一个一个地列出来。例如，集合A={1,2,3,4,5}，就是用枚举法表示这个集合的。

2、枚举法的优点是简单明了，容易理解和掌握，适合初学者使用。但是当集合中的元素比较多时，枚举法就不太实用了，因为会浪费大量时间和精力，而且不便于计算和处理。

二、描述法

1、描述法也称为规则法，使用描述性语言来定义集合中元素的特征、性质或规则。例如，集合B={x|x是大于等于0小于10的偶数}，这就是用描述法表示这个集合的方法。

2、描述法的优点是可以快速确定集合中的元素，并且适合处理复杂的问题。但是需要注意的是，在描述集合时必须确保描述的条件清晰明了、无歧义，否则会导致结果错误。

集合的基本概念

一、集合的定义

集合是由一些确定的、互不相同的对象所组成的整体，这些对象称为集合的元素。例如，{1,2,3,4,5}就是一个集合，其中1、2、3、4、5是这个集合的元素。

二、子集和超集

如果一个集合中的所有元素都属于另一个集合，那么前者就是后者的子集。例如，集合A={1,2,3}，集合B={1,2,3,4}，那么A是B的子集。

反之，如果一个集合包含另一个集合的所有元素，那么前者就是后者的超集。例如，集合A={1,2,3}，集合B={1,2,3,4}，那么B就是A的超集。

三、交集和并集

两个集合的交集是指两个集合中都包含的元素组成的新集合。例如，集合A={1,2,3}，集合B={2,3,4}，那么它们的交集就是{2,3}。

两个集合的并集是指两个集合中所有元素组成的新集合。例如，集合A={1,2,3}，集合B={2,3,4}，那么它们的并集就是{1,2,3,4}。

四、补集和集合的运算法则

集合的补集是指与这个集合互不相交的全集中去掉这个集合中所有元素所剩下的部分组成的集合。

求数据结构题

就行了，准过！
第一章：绪论
1.1：数据结构课程的任务是：讨论数据的各种逻辑结构、在计算机中的存储结构以及各种操作的算法设计。
1.2：数据：是客观描述事物的数字、字符以及所有的能输入到计算机中并能被计算机接收的各种集合的统称。
数据元素：表示一个事物的一组数据称作是一个数据元素，是数据的基本单位。
数据项：是数据元素中有独立含义的、不可分割的最小标识单位。
数据结构概念包含三个方面：数据的逻辑结构、数据的存储结构的数据的操作。
1.3数据的逻辑结构指数据元素之间的逻辑关系，用一个数据元素的集合定义在此集合上的若干关系来表示，数据结构可以分为三种：线性结构、树结构和图。
1.4：数据元素及其关系在计算机中的存储表示称为数据的存储结构，也称为物理结构。
数据的存储结构基本形式有两种：顺序存储结构和链式存储结构。
2.1：算法：一个算法是一个有穷规则的集合，其规则确定一个解决某一特定类型问题的操作序列。算法规则需满足以下五个特性：
输入——算法有零个或多个输入数据。
输出——算法有一个或多个输出数据，与输入数据有某种特定关系。
有穷性——算法必须在执行又穷步之后结束。
确定性——算法的每个步骤必须含义明确，无二义性。
可行性——算法的每步操作必须是基本的，它们的原则上都能够精确地进行，用笔和纸做有穷次就可以完成。
有穷性和可行性是算法最重要的两个特征。
2.2：算法与数据结构：算法建立数据结构之上，对数据结构的操作需用算法来描述。
算法设计依赖数据的逻辑结构，算法实现依赖数据结构的存储结构。
2.3：算法的设计应满足五个目标：
正确性：算法应确切的满足应用问题的需求，这是算法设计的基本目标。
健壮性：即使输入数据不合适，算法也能做出适当的处理，不会导致不可控结
高时间效率：算法的执行时间越短，时间效率越高。 果。
高空间效率：算法执行时占用的存储空间越少，空间效率越高。
可读性：算法的可读性有利于人们对算法的理解。
2.4：度量算法的时间效率，时间复杂度，（课本39页）。
2.5：递归定义：即用一个概念本身直接或间接地定义它自己。递归定义有两个条件：
至少有一条初始定义是非递归的，如1！=1.
由已知函数值逐步递推计算出未知函数值，如用（n-1）！定义n！。
第二章：线性表
1.1线性表：线性表是由n(n》=0)个类型相同的数据元素a0,a1,a2,…an-1,组成的有限序列,记作： LinearList = (a0,a1,a2,…an-1)
其中，元素ai可以是整数、浮点数、字符、也可以是对象。n是线性表的元素个数，成为线性表长度。若n=0，则LinearList为空表。若n》0，则a0没有前驱元素，an-1没有后继元素，ai（0《i《n-1）有且仅有一个直接前驱元素ai-1和一个直接后继元素ai+1。
1.2线性表的顺序存储是用一组连续的内存单元依次存放线性表的数据元素，元素在内存的物理存储次序与它们在线性表中的逻辑次序相同。
线性表的数据元素数据同一种数据类型，设每个元素占用c字节，a0的存储地址为
Loc（a0），则ai的存储地址Loc（ai）为：Loc（ai） = Loc（a0）+ i*c
数组是顺序存储的随机存储结构，它占用一组连续的存储单元，通过下标识别元素，元素地址是下标的线性函数。
1.3：顺序表的插入和删除操作要移动数据元素。平均移动次数是 属数据表长度的一半。（课本第50页）
1.4：线性表的链式存储是用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻，必须采用附加信息表示数据元素之间的顺序关系。
它有两个域组成：数据域和地址域。通常成为节点。（课本第55页及56页）
1.5单链表（课本56页）
单链表的遍历：Node《E》 p = head; while(p!=null)
单链表的插入和删除操作非常简便，只要改变节点间的链接关系，不需移动数据元素。
单链表的插入操作：1）：空表插入/头插入 2)中间插入/尾插入
if(head == null) Node《E》 q = new Node《E》(x);
{ head = new Node《E》(x); q.next = p.next;
}else{ p.next = q;
Node《E》 q=new Node《E》(x); 中间插入或尾插入都不会改变单表
q.next = head; 的头指针head。
head = q;
}
单链表的删除操作：
头删除：head = head.next;
中间/尾删除：if(p.next!=null)
循环单链表：如果单链表最后一个节点的next链保存单链表的头指针head值，则该单链表成为环形结构，称为循环单链表。（课本67）
若rear是单链表的尾指针，则执行（rear.next=head;）语句，使单链表成为一条循环单链表。当head.next==head时，循环单链表为空。
1.6：双链表结构：双链表的每个结点有两个链域，分别指向它的前驱和后继结点，
当head.next==null时，双链表为空。
设p指向双链表中非两端的某个结点，则成立下列关系：p=p.next.prev=p.prev.next。
双链表的插入和删除：1）插入 2)删除
q=new DLinkNode（x）； p.prev.next = p.next;
q.prev=p.prev;q.next =p; if(p.next=null){
p.prev.next = q;p.prev=q; (p.next).prev = p.prev;}
循环双链表：当head.next==head且head.prev==head时，循环双链表为空。
第三章：栈和队列
1.1栈：栈是一种特殊的线性表，其中插入和删除操作只允许在线性表的一端进行。允许操作的一端称为栈顶，不允许操作的一端称为栈底。栈有顺序栈和链式栈。
栈中插入元素的操作称为入栈，删除元素的操作称为出栈。没有元素的中称为空栈。
栈的进出栈顺序：后进先出，先进后出。（及75页的思考题）。
1.2：队列：队列是一种特殊的线性表，其中插入和删除操作分别在线性表的两端进行。
向队列中插入元素的过程称为入队，删除元素的过程称为出对，允许入队的一端称为队尾，允许出队的一端称为对头。没有元素的队列称为空队列。队列是先进先出。
第四章：串
1.1：串是一种特殊的线性表，其特殊性在于线性表中的每个元素是一个字符。一个串记为： s=“s0s1s2…sn-1” 其中n》=0,s是串名，一对双引号括起来的字符序列s0s1s2…sn-1是串值，si（i=0，1，2，…n-1）为特定字符集合中的一个字符。一个串中包含的字符个数称为串的长度。
长度为0的串称为空串，记作“”，而由一个或多个空格字符构成的字符串称为空格串。
子串：由串s中任意连续字符组成的一个子序列sub称为s的子串，s称为sub的主串。子串的序号是指该子串的第一个字符在主串中的序号。
串比较：两个串可比较是否相等，也可比较大小。两个串（子串）相等的充要条件是两个串（子串）的长度相同，并且各对应位置上的字符也相同。
两个串的大小由对应位置的第一个不同字符的大小决定，字符比较次序是从头开始依次向后。当两个串长度不等而对应位置的字符都相同时，较长的串定义为较“大”。
第五章：数组和广义表
1.1：数组是一种数据结构，数据元素具有相同的数据类型。一维数组的逻辑结构是线性表，多维数组是线性表的扩展。
1.2：一维数组：一维数组采用顺序存储结构。一个一维数组占用一组连续的存储单元。
设数组第一个元素a0的存储地址为Loc（a0），每个元素占用c字节，则数组其他元素ai的存储地址Loc（ai）为： Loc（ai）= Loc（a0）+i*c
数组通过下标识别元素，元素地址是下标的线性函数。一个下标能够唯一确定一个元素，所划给的时间是O（1）。因此数组是随机存取结构，这是数组最大的优点。
1.3：多维数组的遍历：有两种次序：行主序和列主序。
行主序：以行为主序，按行递增访问数组元素，访问完第i行的所有元素之后再访问第i+1行的元素，同一行上按列递增访问数组元素。
a00,a01,…a0(n-1), a10,a11,…a1(n-1),…a(m-1)0,a(m-1)1,…,a(m-1)(n-1)
2)列主序：以列为主序，按列递增访问数组元素，访问完第j列的所有元素之后再访问第j+1列的元素，同一列上按列递增访问数组元素。
多维数组的存储结构：多维数组也是由多个一维数组组合而成，组合方式有一下两种。
静态多维数组的顺序存储结构：可按行主序和列主序进行顺序存储。
按行主序存储时，元素aij的地址为：Loc（aij）= Loc（a00）+（i*n+j）*c
按列主序存储时，Loc（aij）= Loc（a00）+（j*m+i）*c
动态多维数组的存储结构。
二维数组元素地址就是两个下标的线性函数。无论采用哪种存储结构，多维数组都是基于一维数组的，因此也只能进行赋值、取值两种存取操作，不能进行插入，删除操作。
第六章：
树是数据元素（结点）之间具有层次关系的非线性结构。在树结构中，除根以外的结点只有一个直接前驱结点，可以有零至多个直接后继结点。根没有前驱结点。
树是由n（n》=0）个结点组成的有限集合（树中元素通常称为结点）。N=0的树称为空树；n》0大的树T；
@有一个特殊的结点称为根结点，它只有后继结点，没有前驱结点。
@除根结点之外的其他结点分为m（m》=0）个互不相交的集合T0,T1,T3……..,Tm-1，其中每个集合Ti（0《=i《m）本身又是一棵树，称为根的子树。
树是递归定义的。结点是树大的基本单位，若干个结点组成一棵子树，若干棵互不相交的子树组成一棵树。树的每个结点都是该树中某一棵子树的根。因此，树是由结点组成的、结点之间具有层次关系大的非线性结构。
结点的前驱结点称为其父母结点，反之，结点大的后继结点称为其孩子结点。一棵树中，只有根结点没有父母结点，其他结点有且仅有一个父母结点。
拥有同一个父母结点的多个结点之间称为兄弟结点。结点的祖先是指从根结点到其父母结点所经过大的所有结点。结点的后代是指该结点的所有孩子结点，以及孩子的孩子等。
结点的度是结点所拥有子树的棵数。度为0的结点称为叶子结点，又叫终端结点；树中除叶子结点之外的其他结点称为分支结点，又叫非叶子结点或非终端结点。树的度是指树中各结点度的最大值。
结点的层次属性反应结点处于树中的层次位置。约定根结点的层次为1，其他结点的层次是其父母结点的层次加1。显然，兄弟结点的层次相同。
树的高度或深度是树中结点的最大层次树。
设树中x结点是y结点的父母结点，有序对（x，y）称为连接这两个结点的分支，也称为边。
设（X0,X1,….,Xk-1）是由树中结点组成的一个序列，且（Xi，Xi+1）（0《=i《k-1）都是树中的边，则该序列称为从X0到Xk-1的一条路径。路径长度为路径上的边数。
在树的定义中，结点的子树T0，T1…..,Tm-1之间没有次序，可以交换位置，称为无序树，简称树。如果结点的子树T0,T1……,Tm-1从左到右是有次序的，不能交换位置，则 称该树为有序树。
森林是m（m》=0）棵互不相干的树的集合。给森林加上一个根结点就变成一棵树，将树的根节点删除就变成森林。
二叉树的性质1：若根结点的层次为1，则二叉树第i层最多有2 的i-1次方（i》=1）个结点。
二叉树的性质2：在高度为k的二叉树中，最多有2的k次方减一个结点。
二叉树的性质3：设一棵二叉树的叶子结点数为n0,2度结点数为n2，则n0=n2+1。
一棵高度为k的满二叉树是具有2的k次方减一个结点的二叉树。满二叉树中每一层的结点数目都达到最大值。对满二叉树的结点进行连续编号，约定根节点的序号为0，从根节点开始，自上而下，每层自左至右编号。
一棵具有n个结点高度为k的二叉树，如果他的每个节点都与高度为k的满二叉树中序号为0~n-1
的结点一一对应，则这棵二叉树为为完全二叉树。
满二叉树是完全二叉树，而完全二叉树不一定是满二叉树。完全二叉树的第1~k-1层是满二叉树第k层不满，并且该层所有结点必须集中在该层左边的若干位置上。
二叉树的性质4：一棵具有n个结点的完全二叉树，其高度k=log2n的绝对值+1
二叉树的性质5：一棵具有n个结点的完全二叉树，对序号为i的结点，有
@若i=0，则i为根节点，无父母结点；若i》0，则i的父母结点的序号为。
@若2i+1《n，则i的左孩子结点序号为2i+1；否则i无左孩子。
@若2i+2《n，则i的右孩子结点的序号为2i+2，否则i无右孩子。
二叉树的遍历
二叉树的遍历是按照一定规则和次序访问二叉树中的所有结点，并且每个结点仅被访问一次。
二叉树的三种次序遍历
1：先根次序；访问根节点，遍历左子树，遍历右子树。
2：中根次序；遍历左子树，访问右子树，遍历右子树。
3：后根次序；遍历左子树，遍历右子树，访问根节点。
先根次序遍历时，最先访问根节点；后根次序遍历时，最后访问根节点；中根次序遍历时，左子树上的结点在根节点之前访问，右子树上的结点在根节点之后访问。
二叉树的插入和删除操作P147
二叉树的层次遍历P149
习题P167 6—10，6—19
第七章
图是由定点集合及顶点间的关系集合组成的一种数据关边系。顶点之间的关系成为边。一个图G记为G=（V,E），V是顶点A的有限集合，E是边的有限集合。即 V=
E=或E=其中Path（A,B）表示从顶点A到B的一条单向通路，即Path（A,B）是有方向的。
无向图中的边事没有方向，每条边用两个顶点的无序对表示。
有向图中的边是有方向，每条边用两个顶点的有序对表示。
完全图指图的边数达到最大值。n个顶点的完全图记为Kn。无向完全图Kn的边数为n*（n-1）/2,有向完全图Kn的边数为n*（n-1）。
子图：设图G==(V,E),G’=(V’,E’)，若V’包含于V且E’包含于E,则称图G’是G的子图。若G’是G的真子图。
连通图：在无向图G中，若从顶点VI到Vj有路径，则称Vi和Vj是联通的。若图G中任意一对顶点Vi和Vj（Vi不等于Vj）都是联通的，则称G为连通图。非连通图的极大联通子图称为该图的联通分量。
强连通图：在有向图中，若在每一对顶点Vi和Vj（Vi不等于Vj）之间都存在一条从Vi到Vj的路径，也存在一条从Vi到Vj的路径，也存在一条从Vi到Vj的路径，则称该图的强连通图。非强连通图的极大强连通子图称为该图的强连通图分量。
图的遍历
遍历图是指从图G中任意一个顶点V出发，沿着图中的边前行，到达并访问图中的所有顶点，且每个顶点仅被访问一次。遍历图要考虑一下三个问题：
@指定遍历的第一个访问顶点
@由于一个顶点可能与多个顶点相邻，因此要在多个邻接顶点之间约定一种访问次序。
@由于图中可能存在回路，在访问某个顶点之后，可能沿着某条路径又回到该顶点。
深度优先搜索
图的深度优先搜索策略是，访问某个顶点v，接着寻找v的另一个未被访问的邻接顶点w访问，如此反复执行，走过一条较长路径到达最远顶点；若顶点v没有未被访问的其他邻接顶点，则回到前一个被访问顶点，再寻找其他访问路径。
图的深度优先搜索遍历算法P188
联通的无回路的无向图，简称树。树中的悬挂点又成为树叶，其他顶点称为分支点。各连通分量均为树的图称为森林，树是森林。
由于树中无回路，因此树中必定无自身环也无重边（否则他有回路）若去掉树中的任意一条边，则变成森林，成为非联通图；若给树加上一条边，形成图中的一条回路，则不是树。P191
生成树和生成森林：
一个连通无向图的生成树是该图的一个极小联通生成子图，它包含原图中所有顶点（n个）以及足以构成一棵树的n-1条边。
一个非联通的无向图，其各连通图分量的生成图组成该图的生成森林。
图的生成图或生成森林不是唯一的，从不同顶点开始、采用不同遍历可以得到不同的生成树或森林。
在生成树中，任何树中，任何两个顶点之间只有唯一的一条路径。
第八章
折半查找算法描述 P206,P207
二叉排序树及其查找：
二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：
@每个结点都有一个作为查找依据的关键字，所有结点的关键字互不相同。
@若一个结点的左子树不空，则左子树上所有结点的关键字均小于这个节点的关键字；
@每个结点的左右子树也分别为二叉排序树。
在一棵二叉排序树中，查找值为value的结点，算法描述如下：
@从根结点开始，设p指向根结点
@将value与p结点的关键字进行比较，若两者相等，则查找成功；若value值较小，则在p的左子树中继续查找；若value值较大，则在p的右子树中继续查找。
@重复执行上一步，直到查找成功或p为空，若p为空，则查找不成功。
习题 8-6
第九章
直接插入排序算法描述：p228
冒泡排序算法的描述：p232
快速排序算法描述p233
直接选择排序算法描述p236
直接选择排序算法实现如下：
Public static void selectSort(inttable){
for(int i=0;i《table.length-1;i++){
int min=I;
for(int j=i+1;j《table.length;j++){
if(table)
min=j;
if(min!=i){
int temp=table;
table;
table=temp;
}
}
}
}
堆排序是完全二叉树的应用，是充分利用完全二叉树特性的一种选择排序。
堆定义：设n个元素的数据序列，当且仅当满足下列关系
k1《=k2i+1且ki《=k2i+2 i=0,1,2,3,….,
或ki》==k2i+1且ki》=2i+2i=0,1,2,3,…..时，序列称为最小堆或最大堆。将最小（大）堆看成是一颗完全二叉树的层次遍历序列，则任意一个结点的关键字都小于等于（大于等于）它的孩子节点的关键字值，由此可知，根结点值最小（大）。根据二叉树的性质5，完全二叉树中的第i（0《=i《n）个结点，如果有孩子，则左孩子为第2i+1个结点，右孩子为第2i+2个结点。
希望对你会有所帮助。