計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)本科-

數(shù)據(jù)結(jié)構(gòu)第二講順序表計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)（本科）目

錄順序表概述一般順序表字符串§2.1

順序表概述一、定義1、表——線性表的簡(jiǎn)稱2、順序表——一種順序存儲(chǔ)的線性表3、順序存儲(chǔ)——以連續(xù)空間順序存貯表中各元素的存貯結(jié)構(gòu)。例如，C++中用數(shù)組來(lái)實(shí)現(xiàn)。4、表長(zhǎng)（n）——順序表中表項(xiàng)（元素）的數(shù)目，n＝0的表叫做空表。二、數(shù)組1、類型相同的有限個(gè)元素的序列，叫數(shù)組。2、數(shù)組是采用順序存貯的線性表設(shè)第0號(hào)元組的地址為a，元素的長(zhǎng)度為L(zhǎng)L·

·

· ·

·

·0

1

2 ·

·

·

i ·

·

·(表長(zhǎng)度為n)n-2

n-1一維數(shù)組任一元素的地址LOC(i)＝

a＋i﹡L行號(hào)：0n-1列號(hào)：1 ·

·

·L

j ·

·

··

·

·

·

····

·0

1

2

···

k

···m-1二維數(shù)組任一元素的地址LOC(j,k)＝

a＋(j﹡m＋k)L三、順序表分類1、一般順序表

2、順序棧 3、順序隊(duì)列§2.2一般順序表一、順序表的類定義1、類聲明template

<class

Type>

class

SeqList

{Private:Type

*data;int

MaxSize;int

last;//last是當(dāng)前最后public:所在位置SeqList

(int

MaxSize=defaultSize);//構(gòu)造函數(shù)~SeqList(){delete[]data;}

//析構(gòu)函數(shù)int

Length(

)

const

{return

last

+1;}int

Find(Type

&

x)

const;int

IsIn(Type

&

x);int

Insert(Type

&

x

,

int

i

);int

Remove(Type

&

x);int

IsEmpty(

)

{return

last

=

=

-1;}int

IsFull(){return

last==Maxsize-1;}Type

Get(int

i)}//取第i個(gè)元素的值一、順序表的類定義

2、部分操作的實(shí)現(xiàn)構(gòu)造函數(shù)template

<class

Type>SeqList

<Type>::Seqlist(int

sz){if

(sz>0){

//::是作用域區(qū)分符，表明其后的函數(shù)所屬的類MaxSize=sz;last=-1;//置表最大規(guī)模，初始化為空data=new

Type

[MaxSize];}//創(chuàng)建順序表數(shù)組定位函數(shù)（找x在表中的位置）template

<class

Type>

int

SeqList

<Type>::Find(Type

&

x){int

i

=

0;while

(i<=last

&&

data[i]

!=

x)

i++;if

i>last

return

-1;else

return

i;

}一、順序表的類定義2、部分操作的實(shí)現(xiàn)判斷x是否在表中template

<class

Type>

int

SeqList

<Type>::

IsIn(Type

&

x){int

i=0;

found=0;while

(

i<=last

&&

!found)if

(data[i]

!=

x)

i++else

found=1;return

found;}插入x到表中第i位置處template

<class

Type>

int

SeqList

<Type>::

Insert(Type

&{if

(i<0||i>last+1||last==MaxSize-1)return

0//不能插e(cuò)lse

{last++;//表長(zhǎng)加1for

(int

j=last;j>i;j--)data[j]=data[j-1];//依次data[i]=x;return

1;}}

//插入一、順序表的類定義2、部分操作的實(shí)現(xiàn)刪除xtemplate

<class

Type>

int

SeqList

<Type>::

Remove(Type

&{int

i=Find(x);if

(i>=0)

{

last--;for

(int

j=i;

j<=last;

j++)

data[j]=data[j+1];return

1;}return

0;}取第i個(gè)元素的值template

<class

Type>

Type

SeqList

<Type>::

Get(int

i){if

i<0

||

i

>

last

return

NULLelse

return

data[i]

;}456lastn=8二、順序表的查找、插入和刪除的算法分析1、查找（int

Find(Type

&

x))（1）方法（示例）（a）成功1

2

3

4

5

6

734

08

16

57

48

09

63i

i

i

i

i0data

25x=48

i（b）失敗0data

25x=20

i1

2

334

08

16i

i

i7

last57

48

09

63

n=8i

i

i

i

i=8二、順序表的查找、插入和刪除的算法分析1、查找（int

Find(Type

&

x))（2）時(shí)間代價(jià)——以數(shù)據(jù)比較次數(shù)來(lái)衡量◎最好情況只比較1次，最壞情況比較n次◎設(shè)各表項(xiàng)的查找概率相等，即Pi=1/n◎設(shè)各表項(xiàng)被查找成功的比較次數(shù)為Ci=i+1◎平均比較次數(shù)ACN（Average

Comparing

Number）為n-1 n-1i=0i=0ACN=∑Pi

·

Ci

=n－∑(i+1)

=n－(1+2+

···

+n)=

—1

1

n+12二、順序表的查找，插入和刪除的算法分析2、插入和刪除（1）插入◎要將i至n-1的所有表項(xiàng)后移一個(gè)位置，然后last+1◎被移動(dòng)的表項(xiàng)數(shù)Ci=(n-1)-i+1=n-i◎數(shù)據(jù)平均移動(dòng)次AMN（Average

Moving

Number）為n-1

ni=0n+1

i=01

1n+1nAMN=∑Pi

·

Ci

=

——∑(n-i)

=

——(n+

···

+21+0)=last

=

n-1456n=8◎示例0

1

2

3data

25

34

08

16ix

=

507

857

48

09

63·

·

·二、順序表的查找，插入和刪除的算法分析2、插入和刪除（2）刪除n=8◎示例last

=

n-10

1

2

3

4

5

6

7data

25

34

08

16

57

48

09

63 ·

·

·i◎第i+1至n-1的所有表項(xiàng)逐個(gè)前移一個(gè)位置,后last-1◎被移動(dòng)的表項(xiàng)數(shù)為(n-1)–i=n-i-1◎AMN=

—∑(n-i-1)

=

—((n-1)+

···

+1+0)=

——n

i=0n-11

1nn-12三、作為抽象數(shù)據(jù)類型，使用順序表的事例1、求表LA和LB的并集template

<class

Type>void

Union(SeqList

<Type>

&LA

,

SeqList

<Type>

&LB){//&

為引用符int

n=LA.Length();int

m=LB.Length();

for

(int

i

=0;i<m;i++){Type

x

=

LB

.

Get(

i

);int

k

=

LA

.

Find(

x

);if

(

k

=

=

-1

)

{LA

.

Insert(

x,

n);

n++;}}}三、作為抽象數(shù)據(jù)類型，使用順序表的事例2、求表LA和LB的交集eqList類，不能引用§2.3

字符串（String）一、字符串的定義1、字符串（簡(jiǎn)稱串）的概念◎串是n(n≥0)個(gè)字符的有限序列◎串的一般表示： S

=

"

a0a1a2…an-1"◎串中字符的數(shù)目n叫做串的長(zhǎng)度，串長(zhǎng)不包括分界符‘"’和結(jié)束符‘\0’，n=0的串叫做空串◎只包含空格字符的串叫做空白串◎從串中取出連續(xù)的若干字符所構(gòu)成的串叫做原串的子串，子串第0號(hào)字符在串中的位置為子串在原串的位置，空串是所有串的子串◎串是屬于值為字符類型的順序表2、串作為抽象數(shù)據(jù)類型的類定義const

int

maxLen=128

//串的最大長(zhǎng)度class

String{public: String

(const

String

&

ob);String

(const

char

*

init);//復(fù)制構(gòu)造函數(shù)//構(gòu)造函數(shù)，由init初始化String

(

);~String

(

)

{delete[

]

ch};//構(gòu)造函數(shù)，實(shí)際長(zhǎng)度為0//析構(gòu)函數(shù)//取子串int

Length(

)

const

{return

curLen;}

String

&operator

(

)

(int

pos,

int

len);int

operator

=

=

(const

String

&

ob)

const

{return

strcmp(ch,ob.ch)==0;} //判斷兩串是否等int

operator!=(const

String

&ob)const{return

strcmp(ch,ob.ch)!=0;} //判斷兩串是否不等int

operator

!(

)

const

{return

curLen

=

=

0;}String

&

operator

=

(const

String

&

ob);String

&

operator

+

=

(const

String

&

ob);//判斷串是否空//賦值//串連接char

&

operator[

]

(int

i);int

Find(String

&

pat)

const;//取*this的第i個(gè)字符//求與pat第一次匹配的位置private: int

curLen; char

*ch;

}二、串操作的實(shí)現(xiàn)1、串復(fù)制構(gòu)造函數(shù)，由已知串ob，構(gòu)造一個(gè)新串String::String(const

String

&ob)

{ch

=

new

char[maxLen

+1];if

!ch

{cout<<

"

Allocation

Error\n";

exit(

1

);

}curLen

=

ob

.

curLen;strcpy(ch,

ob

.

ch);

}2、串構(gòu)造函數(shù)，由init初始化新串String::String(const

char

*

init){ch

=

new

char[maxLen

+1];if

!ch

{cout<<

"

Allocation

Error\n";

exit(

1

);

}curLen

=

strLen(init);strcpy(ch,

init);

}二、串操作的實(shí)現(xiàn)3、串構(gòu)造函數(shù)，實(shí)際長(zhǎng)度為0String::String(){ch

=

new

char[maxLen

+1];if

!ch

{cout<<

"

Allocation

Error\n";

exit(

1

);

}curLen

=

0;ch[0]

=

"

\0

";

}4、串重載操作——串連接String

&

String::operator

+

=

(const

String

&ob)

{char

*temp

=

ch;curLen

+

=

ob

.

curLen;//保存將要復(fù)蓋串的地址//連接后的串長(zhǎng)ch=new

char[maxLen

+1]; //為結(jié)果串分配空間if

!ch

{cout<<"Allocation

Error\n";exit(1);}strcpy(ch,

temp);strcat(ch,

ob

.

ch);//復(fù)制結(jié)果串的前部//連在結(jié)果串的后部delete[

]

temp; return

*this;

}二、串操作的實(shí)現(xiàn)5、串重載操作——求子串String

&

String::operator(

)(int

pos,

int

len)

{String

*temp=new

String; //創(chuàng)建空串if

(pos+len–1>=curLen)len=curLen–pos;//調(diào)整len的temp->curLen=len;for

(int

i

=

0,

j

=

pos;

i<len;

i++,

j++)

temp

->

ch[i]

=

ch[temp

->

ch[len]

=

"

\0

";return

temp;}三、字符串的模式匹配第四趟 T：a

b

d

a

b

cP：