Q.front->next=NULL;
return
OK;}
Status
Destroyqueue(LinkQueue &Q) {
//队列Q存在则销毁Q
while(Q.front){
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return
OK;}
Status
EnQueue(LinkQueue &Q,QElemType e) {
//队列Q存在,插入元素e为Q的队
尾元素
p=(QueuePtr)malloc(sizeof(QNode));
if(!p)
exit(OVERFLOW);
p->data=e;p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return
OK;}
Status
DeQueue(LinkQueue &Q,QElemType &e) {
//Q为非空队列,删除Q的队头元
素,并用e返回其值
if(Q.front==Q.rear)return
ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)Q.rear=Q.front;
free(p);
return
OK;}
三、总结
链队列的存储表示
链队列的操作及实现
回目录上一课下一课
第十四课
本课主题:串的定义
教学目的:掌握串的定义及作用
教学重点:串的类型定义
教学难点:串的类型定义
授课内容:
一、串定义
串(或
字符串),是由零个或多个字符组成的有限序列。一般记为:
s='a1a2...an'(n>=0)
其中s是串的名,用单引号括起来的字符序列是串的
值;串中字符的数目n称为串的长度。零个字
符的串称为空串,它的长度为零。
串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。通常称字符在序列中的称为该字符在串中的位置。子
串在主串中的位置则以子串的第一个字符在主串中的位置来表示。
例:a='BEI',b='JING',c='BEIJING',d='BEI JING'
串长分别为3,4,7,8,且a,b都是c,d的
子串。
称两个串是相等的,当且仅当这两个串的值相等。
二、串的抽象数据类型的定义:
ADT String{
数据对象:D={ai|ai(-CharacterSet,i=1,2,...,n,n>=0}
数据关系:R1={<ai-1,ai>|ai-1,ai(-D,i=2,...,n}
基本操作:
StrAssign(&T,chars)
chars是字符常量。生成一个其值等于
chars的串T。
StrCopy(&T,S)
串S存在则由串S复制得串T
StrEmpty(S)
串S存在则若S为空串,返回真否则返回假
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&
lt;=StrLength(S)且0<=len<=StrLength(S)-pos+1
Index(S,T,pos)
串S和T存在,T是非空,1<=pos&
lt;=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&
lt;=StrLength(S)+1,在串S的第pos个字符之前插入串T
StrDelete(&S,pos,len)
串S存在,1<=pos&
lt;=StrLength(S)-len+1从串中删除第pos个字符起长度为len的子串
DestroyString(&S)
串S存在,则串S被销毁
}ADT String
三、串操作应用举例:
1文字处理中常用的:串的查找(比较,定位)与替
换
在TC集成环境中可用^QF快速查找变量
在WORD中可用搜索与替换批量改变文本
2串的截断与连接
可用求子串及串连接的方法进行文字处理
四、总结
找出几个自己亲自做过的串操作例子。
回目录上一课下一课
第十五课
本课主题:串的表示和实现
教学目的:掌握串的几种实现方法
教学重点:定长顺序存储表示法
堆分配存储表示法
教学难点:堆分配存储表示法
授课内容:
一、复习串的定义
串的
定义
二、定长顺序存储表示
类似于线性表的顺序存储结构,用一组地址连续的存储单元存储串值的字符序列.
#define
MAXSTRLEN 255
typedef
unsigned char SString[MAXSTRLEN+1] //0号单元存放串长
串的实际长度可在这予定义长度的范围内随意,超过予定义长度的串值则被舍去
串长可用下标为0的数组
元素存储,也可在串值后设特殊标记
a[0] | a[1] | a[2] | a[3] | a[4] | a[5] | ... | a[n] |
1串联接的实现
Concat(&T,S1,S2)
假设S1,S2和T都是
SString型的串变量,且串T是由串S1联结串S2得到的,即串T的值的前一段和串S1的值相等,串T的值的后一段和串S2的值相等,则只要进行相应
的"串值复制"操作即可,对超长部分实施"截断"操作
以下是串联接可能出现的三种情况:
S1,S2串长和小于最大值 | S1 | S2 | T | 6 | 6 | 8 | a | g | a | b | h | b | c | i | c | d | j | d | e | k | e | f | l | f | | | g | | | h |
S1,S2串长和超过最大串长 | S1 | S2 | T | 8 | 2 | 8 | a | i | a | b | j | b | c | | c | d | | d | e | | e | f | | f | g | | g | h | | h |
S1串长已等于最大串长 |
算法描述如下:
Status
Concat(SString &T,SString S1,SString S2){
if(S1[0]+S2[0]<=MAXSTRLEN){
T[1..S1[0]]=S1[1..S1[0]];
T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]];
T[0]=S1[0]+S2[0]uncut=TRUE;
}
else
if(S1[0]<MAXSTRSIZE){
T[1..S1[0]]=S1[1..S1[0]];
T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]];
T[0]=MAXSTRLEN;uncut=FALSE;
}
else{
T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];
uncut=FALSE;
}
return
uncut;
}
三、堆分配存储表示
这种存储表示的特点是,
仍以一组地址连续的存储单元存放串值字符序列,但它们的存储空间是在程序执行过程中动态分配而得
在C语言中,存在一个称
之为堆的自由存储区,并由C语言的动态分配函数malloc()和free()来管理.利用函数malloc()为每个新产生的串分配一块实际串长所需存
储空间,为处理方便,约定串长也作为存储结构的一部分
typedef
struct{
char
*ch;//若是非空串,则按串长分配存储区,否则ch为NULL
int
length; //串长度
}HString
Status
StrInsert(HString &S,int pos,HString T){
if(pox<1||pos>S.length+1)
return
ERROR;
if(T.length){
if(!(S.ch=(char
*)realloc(S.ch,(S.length+T.length)*sizeof(char))))
exit(OVERFLOW);
for(i=S.length-1;i>=pos-1;--i)
S.ch[i+T.length]=S.ch[i];
S.ch[pos-1..pos+T.lenght-2]=T.ch[0..T.length-1];
S.length+=T.length;
}
return
OK;
}
四、总结
思考两种存储表示方法的优缺点
回目录上一课下一课