教學(xué)目的： 掌握串的幾種實(shí)現(xiàn)方法
教學(xué)重點(diǎn)： 定長順序存儲(chǔ)表示法 堆分配存儲(chǔ)表示法
教學(xué)難點(diǎn)： 堆分配存儲(chǔ)表示法
授課內(nèi)容：
一、復(fù)習(xí)串的定義
串的定義
二、定長順序存儲(chǔ)表示
類似于線性表的順序存儲(chǔ)結(jié)構(gòu),用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列.
#define MAXSTRLEN 255
typedef unsigned char SString[MAXSTRLEN+1] //0號單元存放串長
串的實(shí)際長度可在這予定義長度的范圍內(nèi)隨意,超過予定義長度的串值則被舍去
串長可用下標(biāo)為0的數(shù)組元素存儲(chǔ),也可在串值后設(shè)特殊標(biāo)記
a[0]a[1]a[2]a[3]a[4]a[5]...a[n]
3abcpascal
abc\0c
1串聯(lián)接的實(shí)現(xiàn)Concat(&T,S1,S2)
假設(shè)S1,S2和T都是SString型的串變量,且串T是由串S1聯(lián)結(jié)串S2得到的,即串T的值的前一段和串S1的值相等,串T的值的后一段和串S2的值相等,則只要進(jìn)行相應(yīng)的"串值復(fù)制"操作即可,對超長部分實(shí)施"截?cái)?操作
以下是串聯(lián)接可能出現(xiàn)的三種情況:
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] 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;
}
三、堆分配存儲(chǔ)表示
這種存儲(chǔ)表示的特點(diǎn)是,仍以一組地址連續(xù)的存儲(chǔ)單元存放串值字符序列,但它們的存儲(chǔ)空間是在程序執(zhí)行過程中動(dòng)態(tài)分配而得
在C語言中,存在一個(gè)稱之為堆的自由存儲(chǔ)區(qū),并由C語言的動(dòng)態(tài)分配函數(shù)malloc()和free()來管理.利用函數(shù)malloc()為每個(gè)新產(chǎn)生的串分配一塊實(shí)際串長所需存儲(chǔ)空間,為處理方便,約定串長也作為存儲(chǔ)結(jié)構(gòu)的一部分
typedef struct{
char *ch;//若是非空串,則按串長分配存儲(chǔ)區(qū),否則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;
}
四、總結(jié)
思考兩種存儲(chǔ)表示方法的優(yōu)缺點(diǎn)
教學(xué)重點(diǎn)： 定長順序存儲(chǔ)表示法 堆分配存儲(chǔ)表示法
教學(xué)難點(diǎn)： 堆分配存儲(chǔ)表示法
授課內(nèi)容：
一、復(fù)習(xí)串的定義
串的定義
二、定長順序存儲(chǔ)表示
類似于線性表的順序存儲(chǔ)結(jié)構(gòu),用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列.
#define MAXSTRLEN 255
typedef unsigned char SString[MAXSTRLEN+1] //0號單元存放串長
串的實(shí)際長度可在這予定義長度的范圍內(nèi)隨意,超過予定義長度的串值則被舍去
串長可用下標(biāo)為0的數(shù)組元素存儲(chǔ),也可在串值后設(shè)特殊標(biāo)記
a[0]a[1]a[2]a[3]a[4]a[5]...a[n]
3abcpascal
abc\0c
1串聯(lián)接的實(shí)現(xiàn)Concat(&T,S1,S2)
假設(shè)S1,S2和T都是SString型的串變量,且串T是由串S1聯(lián)結(jié)串S2得到的,即串T的值的前一段和串S1的值相等,串T的值的后一段和串S2的值相等,則只要進(jìn)行相應(yīng)的"串值復(fù)制"操作即可,對超長部分實(shí)施"截?cái)?操作
以下是串聯(lián)接可能出現(xiàn)的三種情況:
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]
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;
}
三、堆分配存儲(chǔ)表示
這種存儲(chǔ)表示的特點(diǎn)是,仍以一組地址連續(xù)的存儲(chǔ)單元存放串值字符序列,但它們的存儲(chǔ)空間是在程序執(zhí)行過程中動(dòng)態(tài)分配而得
在C語言中,存在一個(gè)稱之為堆的自由存儲(chǔ)區(qū),并由C語言的動(dòng)態(tài)分配函數(shù)malloc()和free()來管理.利用函數(shù)malloc()為每個(gè)新產(chǎn)生的串分配一塊實(shí)際串長所需存儲(chǔ)空間,為處理方便,約定串長也作為存儲(chǔ)結(jié)構(gòu)的一部分
typedef struct{
char *ch;//若是非空串,則按串長分配存儲(chǔ)區(qū),否則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;
}
四、總結(jié)
思考兩種存儲(chǔ)表示方法的優(yōu)缺點(diǎn)