數(shù)據(jù)結(jié)構(gòu)-第四章課件

數(shù)

據(jù)

結(jié)

構(gòu)第四章串4.1串的抽象數(shù)據(jù)類型的定義4.2串的表示和實(shí)現(xiàn)4.1串的抽象數(shù)據(jù)類型的定義串：是由零個(gè)或多個(gè)字符組成的有限序列。

s=′a1a2···

an′空串：零個(gè)字符的串。長(zhǎng)度：串中字符的數(shù)目。子串：串中任意個(gè)連續(xù)的字符組成的子序列。主串：包含子串的串。位置：通常稱字符在序列中的序號(hào)為該字符在串中的位置。4.1串的抽象數(shù)據(jù)類型的定義如下：ADTString{

數(shù)據(jù)對(duì)象：D＝{ai|ai∈CharacterSet,i=1,2,...,n,n≥0}數(shù)據(jù)關(guān)系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}串是有限長(zhǎng)的字符序列，由一對(duì)單引號(hào)相括，如:′astring′

基本操作：

StrAssign(&T,chars)

StrCopy

(&T,S)

DestroyString(&S)

StrEmpty

(S)

StrCompare

(S,T)

StrLength(S)

Concat

(&T,S1,S2)SubString

(&Sub,S,pos,len)

Index(S,T,pos)

Replace(&S,T,V)StrInsert

(&S,pos,T)

StrDelete

(&S,pos,len)

ClearString

(&S)}ADTString

StrEmpty

(S)

初始條件：串S存在。

操作結(jié)果：若S為空串，則返回true，

否則返回false。表示空串，空串的長(zhǎng)度為零。

StrCompare(S,T)

初始條件：串S和T存在。

操作結(jié)果：若ST，則返回值

0；

若ST，則返回值

0；

若ST，則返回值

0。例如：StrCompare(data,state)<0

StrCompare(cat,case)>0

Concat

(&T,S1,S2)

初始條件：串S1和S2存在。

操作結(jié)果：用T返回由S1和S2

聯(lián)接而成的新串。例如：

Concat(T,

man,

kind)

求得T=

mankind

SubString

(&Sub,S,pos,len)初始條件：操作結(jié)果：

用Sub返回串S的第pos個(gè)字符起長(zhǎng)度為len

的子串。串S存在，1≤pos≤StrLength(S)

且0≤len≤StrLength(S)-pos+1。例如：

SubString(sub,

commander,4,3)子串為“串”中的一個(gè)字符子序列求得sub=

man;

SubString(sub,

commander,1,9)SubString(sub,

commander,9,1)求得sub=

r求得sub=

commanderSubString(sub,

commander,4,7)sub=?SubString(sub,

beijing

,7,2)=?sub=?SubString(

student,5,0)=起始位置和子串長(zhǎng)度之間存在約束關(guān)系長(zhǎng)度為0的子串為“合法”串

Index(S,T,pos)

初始條件：串S和T存在，T是非空串，

1≤pos≤StrLength(S)。

操作結(jié)果：

若主串S中存在和串T值相同

的子串,則返回它在主串S中第pos

個(gè)字符之后第一次出現(xiàn)的位置;否則

函數(shù)值為0。

假設(shè)S=

abcaabcaaabc

,T=

bca

Index(S,T,1)=2;Index(S,T,3)=6;Index(S,T,8)=0;

“子串在主串中的位置”意指子串中的第一個(gè)字符在主串中的位序。

Replace(&S,T,V)

初始條件：串S,T和V均已存在，

且T是非空串。

操作結(jié)果：用V替換主串S中出

現(xiàn)的所有與（模式串）T

相等的不重疊的子串。例如：假設(shè)S=

abcaabcaaabca

,T=

bca若V=

x,則經(jīng)置換后得到

S=

axaxaax

若V=

bc

,則經(jīng)置換后得到

S=

abcabcaabc

bcabcabca

StrInsert

(&S,pos,T)

初始條件：串S和T存在，

1≤pos≤StrLength(S)＋1。

操作結(jié)果：在串S的第pos個(gè)字符之前插入串T。例如：S=

chater

，T=

rac

，則執(zhí)行StrInsert(S,4,T)之后得到

S=

character

StrDelete

(&S,pos,len)

初始條件：串S存在

1≤pos≤StrLength(S)-len+1。

操作結(jié)果：從串S中刪除第pos個(gè)字符

起長(zhǎng)度為len的子串。

對(duì)于串的基本操作集可以有不同的定義方法，在使用高級(jí)程序設(shè)計(jì)語言中的串類型時(shí)，應(yīng)以該語言的參考手冊(cè)為準(zhǔn)。

gets(str)輸入一個(gè)串；

puts(str)

輸出一個(gè)串；

strcat(str1,str2)串聯(lián)接函數(shù)；

strcpy(str1,str2)串復(fù)制函數(shù)；

strcmp(str1,str2)串比較函數(shù)；

strlen(str)求串長(zhǎng)函數(shù)；例如：C語言函數(shù)庫(kù)中提供下列串處理函數(shù)：串賦值StrAssign、串復(fù)制Strcopy、

串比較StrCompare、求串長(zhǎng)StrLength、

串聯(lián)接Concat以及求子串SubString

等六種操作構(gòu)成串類型的最小操作子集。在上述抽象數(shù)據(jù)類型定義的13種操作中，即：這些操作不可能利用其他串操作來實(shí)現(xiàn)，反之，其他串操作（除串清除ClearString和串銷毀DestroyString外）可在這個(gè)最小操作子集上實(shí)現(xiàn)。串的邏輯結(jié)構(gòu)和線性表極為相似，區(qū)別僅在于串的數(shù)據(jù)對(duì)象約束為字符集。

串的基本操作和線性表有很大差別。在線性表的基本操作中，大多以“單個(gè)元素”作為操作對(duì)象；在串的基本操作中，通常以“串的整體”作為操作對(duì)象。

在程序設(shè)計(jì)語言中，串只是作為輸入或輸出的常量出現(xiàn)，則只需存儲(chǔ)此串的串值，即字符序列即可。但在多數(shù)非數(shù)值處理的程序中，串也以變量的形式出現(xiàn)。4.2串的表示和實(shí)現(xiàn)一、串的定長(zhǎng)順序存儲(chǔ)表示二、串的堆分配存儲(chǔ)表示三、串的塊鏈存儲(chǔ)表示

#defineMAXSTRLEN255//用戶可在255以內(nèi)定義最大串長(zhǎng)

typedef

unsignedchar

Sstring[MAXSTRLEN+1];//0號(hào)單元存放串的長(zhǎng)度一、串的定長(zhǎng)順序存儲(chǔ)表示按這種串的表示方法實(shí)現(xiàn)的串的運(yùn)算時(shí)，其基本操作為

“字符序列的復(fù)制”串的實(shí)際長(zhǎng)度可在這個(gè)預(yù)定義長(zhǎng)度的范圍內(nèi)隨意設(shè)定，超過予定義長(zhǎng)度的串值則被舍去，稱之為“截?cái)唷?/p>

特點(diǎn):

StatusConcat(SStringS1,SStringS2,SString

&T){

//用T返回由S1和S2聯(lián)接而成的新串。若未截?cái)?則返回TRUE，否則FALSE。

returnuncut;}//Concat例如：串的聯(lián)接算法中需分三種情況處理：

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;

}

if

(S1[0]+S2[0]<=MAXSTRLEN)

{//未截?cái)?/p>

elseif

(S1[0]<MAXSTRSIZE){//截?cái)?/p>

else{//截?cái)?僅取S1)T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN－S1[0]];T[0]=MAXSTRLEN;uncut=FALSE;

}

T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];//T[0]==S1[0]==MAXSTRLENuncut=FALSE;

}

typedef

struct{char*ch;

//若是非空串，則按串長(zhǎng)分配

//存儲(chǔ)區(qū)，否則ch

為NULL

intlength;//串長(zhǎng)度

}

HString;二、串的堆分配存儲(chǔ)表示

通常，C語言中提供的串類型就是以這種存儲(chǔ)方式實(shí)現(xiàn)的。系統(tǒng)利用函數(shù)malloc()和free()進(jìn)行串值空間的動(dòng)態(tài)管理，為每一個(gè)新產(chǎn)生的串分配一個(gè)存儲(chǔ)區(qū)，稱串值共享的存儲(chǔ)空間為“堆”。

C語言中的串以一個(gè)空字符為結(jié)束符，串長(zhǎng)是一個(gè)隱含值。這類串操作實(shí)現(xiàn)的算法為:

先為新生成的串分配一個(gè)存儲(chǔ)空間，然后進(jìn)行串值的復(fù)制。三、串的塊鏈存儲(chǔ)表示也可用鏈表來存儲(chǔ)串值，由于串的數(shù)據(jù)元素是一個(gè)字符，因此用鏈表存儲(chǔ)時(shí)，通常一個(gè)結(jié)點(diǎn)中存放的不是一個(gè)字符，而是一個(gè)子串。存儲(chǔ)密度

=數(shù)據(jù)元素所占存儲(chǔ)位實(shí)際分配的存儲(chǔ)位

#defineCHUNKSIZE80

//可由用戶定義的塊大小

typedef

structChunk{

//

結(jié)點(diǎn)結(jié)構(gòu)

char

ch[CHUNKSIZE];

struct

Chunk*next;

}Chunk;

typedef

struct{//串的鏈表結(jié)構(gòu)

Chunk*head,*tail;//串的頭和尾指針

int

curlen;//串的當(dāng)前長(zhǎng)度

}

LString;

例如:

在編輯系統(tǒng)中，整個(gè)文本編輯區(qū)可以看成是一個(gè)串，每一行是一個(gè)子串，構(gòu)成一個(gè)結(jié)點(diǎn)。即:同一行的串用定長(zhǎng)結(jié)構(gòu)(80個(gè)字符),行和行之間用指針相聯(lián)接。實(shí)際應(yīng)用時(shí)，可以根據(jù)問題所需來設(shè)置結(jié)點(diǎn)的大小。本章作業(yè)1.兩個(gè)串相等的充分必要條件是什么？2.空串與空格串是相同的嗎？為什么？

習(xí)題一1.for(i=1;i<=n;++i)for(j=1;j<=n;++j){

c[i][j]=0;for(k=1;k<=n;++k)

c[i][j]+=a[i][k]*b[k][j];}O（n3）2.for(i=1;i<=n;i=2*i) ++x;O（log2n）3.s=0;for(i=0;i<=n;i++)for(j=0;j<=n;j++)for(k=0;k<i+j;k++)s++;O（n3）習(xí)題一4.向一個(gè)長(zhǎng)度為n的順序表中的第i個(gè)元素（0≤i≤n-1）之前插入一個(gè)元素時(shí)，需向后移動(dòng)

n-i

個(gè)元素。5.在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素（0≤i≤n-1）時(shí)，需向前移動(dòng)

n-i-1個(gè)元素。6.需要分配較大空間，插入和刪除不需要移動(dòng)元素的線性表，其存儲(chǔ)結(jié)構(gòu)是：靜態(tài)鏈表。7.如果最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用順序表存儲(chǔ)方式最節(jié)省時(shí)間。習(xí)題一8.在一個(gè)單鏈表中的p所指結(jié)點(diǎn)之前插入一個(gè)s所指結(jié)點(diǎn)時(shí)，可執(zhí)行如下操作：（1）s->next=p->next;（2）p->next=s;（3）t=p->data;（4）p->data=s->data;（5）s->data=t;9.在一個(gè)單鏈表中刪除p所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行以下操作：q=p->next;p->data=p->next->data;p->next=p->next->next;

free(q);習(xí)題一10.從順序表中刪除所有值為x的元素。

voiddelall(Sqlist&L){

inti=0,j;

while(i<L.len&&L.data[i]!=x)i++;

for(j=i+1;j<L.len;j++)

if(L.data[j]!=x){

L.data[i]=L.data[j];i++;}

L.len=i;}習(xí)題一11.某百貨公司倉(cāng)庫(kù)中有一批電視機(jī)，按其價(jià)格從低到高的次序構(gòu)成了一個(gè)單鏈表存于計(jì)算機(jī)中，鏈表的每個(gè)結(jié)點(diǎn)指出同樣價(jià)格的若干臺(tái)，現(xiàn)在又新到m臺(tái)價(jià)格為h元的電視機(jī)入庫(kù)，試完成該算法。

typedef

struct

LNode{floatcost;

intnum;

Struct

LNode*next;}LNode,*LinkList;VoidTvsets(LinkList&L,intm,floath){q=L;p=q->next;While(p->cost<h&&p!=null){q=p;p=p->next;}If(p->cost==h&&p!=null){p->num=p->num+m;}Else{t=(LNode*)malloc(sizeof(LNode));t->cost=h;t->num=m;q->next=t;t->next=p;