|
几乎所有的程序设计语言都定义数组为一种固有的数据类型，事实上，数组本身就具有线性表的性质。例如：一维数组，它的每个数组元素对应于一个下标，二维数组，它的每个数组元素对应于一对下标，对于 n 维数组，它的每个元素对应一组 n 个下标。而数组元素的数据类型都是相同的，元素的有序性可由下标的顺序关系来确定。但是数组与一般的线性表不同，数组一般不作插入和删除操作，而通常只定义两种操作，即对于给定的下标读取和修改相应的数组元素的值。 | ||||||||||||||||||||
|
1.1 定义及基本运算 一.定义：长度为几的线性表是一种数据结构 B=(K,R) 其中:k由几个结点{k1,k2....kn}组成 R只有一个关系N,且N确定了一个结点序列 N={(ki-1,ki)/2<=i<=n} n={(k1,k2),(k2,k1)....(kn-1,kn)} n--长度 n=0空表 k1--开始结点 kn-- 端点 ki-1--ki的直接前件 ki+1--ki的直接后件 二、基本运算 1.取(第i个结点)ki 2.删(第i个结点)ki 3.插入(在ki-1与ki之间)一新结点 4.把k1放到它应有的位置上 三、对线必表的基本操作有以下几种:
| ||||||||||||||||||||
|
1.2 线性表的顺序存储结构 一、存储方式 l───占单元数 loc(k1)──地址 loc(ki)───ki地址 基地址
二、特点 逻辑关系相邻的结点物理位置上也相邻 类型描述: const max=<线性表可能的最大长度> var r=arrraY[1..MAX] OF 数据类型 n=integer; type sqlist=record 顺序表 r=array[1..max] of elementype; n=integer end; 三、基本运算 1.取ki 开始
↓ 是
i<1 ─────↑───→出错,结束 ↓ i>A.n│ ----------------------------- ─────┘
↓
打 印 A.r[n]
↓
结束
A────线性表 I─────要取结点的序号
Begin if (i<1) or (i>A.n) then call error ("出错') else write (A.r[i]) END;
pas.w
开 始
↓
i<1 ↓ i>A.n
↓
┌→ for j=i+1 to A.n───┐
│ ↓ │
│ A.r[j-1]←A.r[j] │
│ │ │
└──────┘ │
┌──────┤
↓
A.n←A.n-1
↓
结束
A───线性表 i───要删结点的序号 j───指示移动时的"指针"辅变
Begin if (i<10 or (i>A.n) then callerror ("出错") else [for j:=i+1 to a.n do A.n:=A.n-1] end;
开始
↓
A.n>=max───→出错,结束
↓
i<1──────→出错,结束 ↓ i>A.n
↓
┌─→ for j←a.n don't to i──┐
│ ↓ │
│ A.r[j+1]←A.r[j] │
└──────┤ │
│
│
┌────────┘
↓
A.r[i]←x
A.n←A.n+1
↓
结束
Begin if A.n>=max then call error ('出错') else if j(i<1) or (i>A.n) then call error ('不合理') else [for j:=A.n don't i do A.r[j+1]:=A.r[j]; A.r[i]:=x;A.n:=A.n+1] END;
设:在表的任何位置插,删的概率相同 1 1
P(in)= ── q(del)= ──
n+1 n
插入 删除
开始
↓
T←A.r[1] f3
↓
┌──for i←2 to A.n →结束
│ ↓
│ r←A.r[i]
│ ↓
│ A.r[i] f3>=T→x←A.r[i]───┐
│ ↓ ←───────────┘
│ for j←1 own to 1
│ ↓
│ A.r[j]←A.r[j-1]
│ ↓
│ A.r[j]←x
│
└───────↑
|
|
队列 |
2.4.1 抽象数据类型队列的定义和栈相反，队列(Queue)是一种先进先出(First In First Out,缩写为FIFO)的线性表。它只允许在表的一端进行插入，而在另一端删除元素。这和我们日常生活中的排队是一致的，最早进入队列的元素 最早离开。在队列中，允许插入的一端叫做队尾(rear)，允许删除的一端则称为队头(front)。 假设队列为q=(a1,a2,...an),那么，a1是队头元素，an则是队尾元素。队列中的元素是按照a1,a2,...an的顺序进入 的，推出队列也只能按照这个次序依次推出，也就是说，只有在a1,a2,...an-1都离开队列之后，an才能 推出队列。 如图所示： 队列在程序设计中也经常出现。一个最典型的例子就是操作系统中的作业排对。在允许多道程序运行的计算机系统中，同时有几个作业运行。如果运行的结果都需要通过通道输出，那就要按请求输出的先后次序排队。每当通道传输完毕可以接受新的输出任务时，队头的作业先从队列中推出，作输出操作。凡是申请输出的作业都从队尾进入队列。 队列的操作与栈的操作类似，也有七个。不同的是删除运算是在表的头部(即队头)进行。 下面给出队列的抽象数据类型定义： 规格说明3.2 ADT Queue 数据元素可以是各种类型的，只要同属一个数据对象即可。 结构数据元素之间呈线性关系。假设队列中有n个数据元素(a1,a2,...an)，则对每一个元素 ai(i=1,2,...,n-1)都存在关系(ai,ai+1),并且a1无前趋，an无后继。 操作
|
|
串 |
|
3.1 串的基本概念 串是零个或多个字符组成的有限序列。一般记S=‘a1a2....an ’其中，S是串名，单引号括起的字符序列是串值；ai（1〈=i〈=n）可以是字母，数字或其它字符；串中所包含的字符个数为该串的长度。长度为零的串称为空串，它不包含任何字符。 串中任意个连续的字符组成的子序列称为该串的子串。包含子串的相应地称为主串。通常，把子串在主串中第一次出现时，子串的第一次字符在主串中的序号，定义为子串在主串中的序号。 称两个串是相等的，当且仅当这两个串的值相等。也就是说，只有当两个串的长度相等，并且各个对应位置的字符都相等时才相等。 值得一提的是，串值必须用一对单引号括起来，但单引号本身不属于。 |
|
3.2 基本操作 1）ASSIGN（s，t）和CREAT（s，ss） 赋值操作。其中t为串名，ss 为字符序列。 2）EQUAL（s，t） 判等函数。若s和t相等，则返回函数值“true”，否则返回函数值“false”。 3）LENGTH（s） 求长函数。其函数值为串s中字符的个数。 4）CONCAT（s，t） 联接函数。其函数值为一个新的串。 5）SUBSTR（s，start，len） 求子串函数。返回函数值为从串s中第start个字符起，长度为len的字符序列。 6）INDEX（s，t） 定位函数。若在主串s中存在和t相等的子串，则函数值为s中第一个这样的子串在主串s中的位置，否则函数值为零。注意：在此t不能为空串。 7）REPLACE（s，t，v） 置换操作。操作结果是以串v替换所有在串s中出现的和非空串t相等的重叠的子串。 8）INSERT（s，pos，t） 插入操作。在串s中第pos个字符之前插入串t。 9）DELETE（s，pos，len） 删除操作。从串s中删去第pos个字符起长度为len的子串。 |
|
3.3 存储结构 1. 静态存储结构 是用一组地址连续的存储单元存储串的字符序列。可分为两种格式：非紧缩格式：数组的一个分量至少占一个字符单元（如下图一）；紧缩格式：在一个字存储单元中存放多个字符（如下图二）。 2. 动态存储结构 可采用链表方式存储串值，每个结点可以存放一个字符，也可以存放多个字符（如下图三）。 |
|
3.4 基本操作实现 这里介绍一下在串处理系统中比较重要的几个操作： 1.串的链结 CONCAT(l,s,t) CONST maxlen=串被确认的最大长度； TYPE strtp=RECORD ch：ARRAY [1..maxlen] OF char； curlen：0..maxlen END； 假设l,s,t都是strtp型的串变量,且l为s联结t之后得到的串,则联结运算是将s和t的值分别传送到l的相应位置上,超过maxlen的部分截断之。其运算结果可能有三种情况（如下图a，b，c）。 |
