數(shù)據(jù)結(jié)構(gòu)和算法課件

數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法1作為抽象數(shù)據(jù)類型的數(shù)組一維數(shù)組一維數(shù)組的示例作為抽象數(shù)據(jù)類型的數(shù)組一維數(shù)組2一維數(shù)組的特點(diǎn)連續(xù)存儲(chǔ)的線性聚集（別名向量）除第一個(gè)元素外，其他每一個(gè)元素有一個(gè)且僅有一個(gè)直接前驅(qū)。除最后一個(gè)元素外，其他每一個(gè)元素有一個(gè)且僅有一個(gè)直接后繼。一維數(shù)組的特點(diǎn)連續(xù)存儲(chǔ)的線性聚集（別名向量）3數(shù)組的定義和初始化#include<iostream.h>classszcl{inte; public:

szcl(){e=0;}

szcl(intvalue){e=value;} intget_value(){returne;} }數(shù)組的定義和初始化#include<iostream.h>4main

(){

szcla1[3]={3,5,7},*elem;

for(int

i=0,i<3,i++)

cout<<a1[i].get_value()<<“\n”; //打印靜態(tài)數(shù)組

elem=&a1;

for(int

i=0,i<3,i++){

cout<<elem→get_value()<<“\n”; //打印動(dòng)態(tài)數(shù)組

elem++;

}

return0;}

main(){5一維數(shù)組(Array)類的定義#include<iostream.h>#include<stdlib.h>template<classType>classArray{Type

*elements;//數(shù)組存放空間

intArraySize;//當(dāng)前長(zhǎng)度

voidgetArray();//建立數(shù)組空間

public:Array(intSize=DefaultSize);

Array(const

Array<Type>&x);一維數(shù)組(Array)類的定義#include<iost6~Array(){delete[]elements;} Array<Type>

&

operator

=

(const

Array<Type>

&A);Type&operato[](inti); operatorType*

()

const

{return

elements;}int

Length()const{returnArraySize;} voidReSize(intsz); }~Array(){delete[]e7template<classType>void

Array<Type>::getArray(){

//私有函數(shù)：創(chuàng)建數(shù)組存儲(chǔ)空間

elements=newType[ArraySize];if(elements==0)

cerr<<"MemoryAllocationError"<<endl;}一維數(shù)組公共操作的實(shí)現(xiàn)template<classType>一維數(shù)組公共操8template<classType>void

Array<Type>::Array(intsz){

//構(gòu)造函數(shù)

if(sz<=0){cerr<<"InvalidArraySize"<<

endl;return;}

ArraySize=sz;getArray();

}template<classType>9template<classType> Array<Type>::

Array(const

Array<Type>

&x){

//復(fù)制構(gòu)造函數(shù)

int;

elements=newType[n]; if(elements==0)

cerr

<<"MemoryAllocationError"<<endl;

Type;

Type

*destptr=elements;

while

(n--

)*destptr++=*srcptr++;}template<classType> Array<T10template<classType>Type&Array<Type>::operator[](inti){

//按數(shù)組名及下標(biāo)i，取數(shù)組元素的值

if(i<0

||i>ArraySize-1)

cerr<<"IndexoutofRange"<<

endl;

returnelement[i]; }

使用該函數(shù)于賦值語(yǔ)句

Position[i]=Position[i-1]+Number[i

-1]template<classType>11template<classType>void

Array<Type>::Resize(int

sz){if(sz>=0&&

sz!=ArraySize){Type*newarray=

newType[sz]; if(newarray==0)

cerr

<<"MemoryAllocationError"<<

endl;intn=(sz<=ArraySize)?sz:ArraySize; Type

*srcptr=elements; Type*destptr=newarray; while(n--)*destptr++=*srcptr++;

delete[]elements; elements=newarray; ArraySize=sz; }}

template<classType>12

二維數(shù)組三維數(shù)組行向量下標(biāo)

i頁(yè)向量下標(biāo)i列向量下標(biāo)

j行向量下標(biāo)j

列向量下標(biāo)k二維數(shù)組三維數(shù)組行向量下標(biāo)13數(shù)組的連續(xù)存儲(chǔ)方式一維數(shù)組LOC(i)=LOC(i-1)+l=α+i*l數(shù)組的連續(xù)存儲(chǔ)方式一維數(shù)組LOC(i)=LOC(14

二維數(shù)組行優(yōu)先LOC(j,k)=j*m+k

二維數(shù)組行優(yōu)先LOC(j,k)=j*m15n維數(shù)組各維元素個(gè)數(shù)為

m1,m2,m3,…,mn下標(biāo)為i1,i2,i3,…,in

的數(shù)組元素的存儲(chǔ)地址：n維數(shù)組各維元素個(gè)數(shù)為m1,m2,m3,…,m16順序表(SequentialList)順序表的定義和特點(diǎn)定義n（0）個(gè)表項(xiàng)的有限序列

（a1,a2,…,an）

ai是表項(xiàng)，n是表長(zhǎng)度。 特點(diǎn)順序存取遍歷逐項(xiàng)訪問從前向后從后向前從兩端向中間順序表(SequentialList)順序表的定義和特點(diǎn)17順序表(SeqList)類的定義template<classType> class

SeqList{Type*data;//順序表存儲(chǔ)數(shù)組

intMaxSize; //最大允許長(zhǎng)度

int

last; //當(dāng)前最后元素下標(biāo)public:

SeqList(intMaxSize=defaultSize);

~SeqList()

{delete[]data;}

intLength()

const

{return

last+1;

}

intFind(Type

&x)const;順序表(SeqList)類的定義template<clas18

intIsIn(Type

&x);

int

Insert(Type&x,int

i);

int

Remove(Type

&x);

intNext(Type

&x);

intPrior(Type

&x);intIsEmpty()

{return

last==-1;

} int

IsFull()

{returnlast==MaxSize-1;

} Type

&Get(

inti){return

i<0

||i>last？NULL

:

data[i];}}

intIsIn(Type&x); 19順序表部分公共操作的實(shí)現(xiàn)template<classType>

SeqList<Type>::SeqList(intsz){//構(gòu)造函數(shù)

if(sz>0)

{

MaxSize=sz;last=-1;

data=newType[MaxSize];

} }順序表部分公共操作的實(shí)現(xiàn)template<classT20template<classType> int

SeqList<Type>::Find(Type

&x)const{//搜索函數(shù)：在表中從前向后順序查找x

inti=0;

while

(i<=last&&data[i]

!=x)

i++;

if(i>last)return

-1;

elsereturni; }template<classType> 21順序搜索圖示x=48x=50順序搜索圖示x=4822搜索成功

若搜索概率相等，則

搜索不成功數(shù)據(jù)比較n

次搜索成功

若搜索概率相等，則

23表項(xiàng)的插入表項(xiàng)的插入24template<classType>int

SeqList<Type>::Insert(

Type

&x,

int

i){//在表中第i

個(gè)位置插入新元素x

if(i<0

||

i>last+1

||

last==MaxSize-1)

return0;//插入不成功

else{

last++;

for(

intj=last;j>i;j--

)

data[j]=data[j-1];

data[i]=x;return1;//插入成功

}}template<classType>25表項(xiàng)的刪除表項(xiàng)的刪除26template<classType>int

SeqList<Type>::Remove(

Type

&x){//在表中刪除已有元素x

int

i=Find(x); //在表中搜索x

if(i>=0

){

last--;

for(intj=i;j<=last;j++)

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

return1; //成功刪除

} return0;//表中沒有

x}template<classType>27順序表的應(yīng)用：集合的“并”運(yùn)算

template<classType>void

Union(SeqList<Type>

&LA,SeqList<Type>

&LB){

intn=LA.Length();

intm=LB.Length();

for(inti=1;i<=m;i++){ Type(i);//在LB中取一元素

int(x);//在LA中搜索它

if(k==

-1)//若未找到插入它

{LA.Insert(n+1,x);n++;}}}順序表的應(yīng)用：集合的“并”運(yùn)算template<clas28template<classType> voidIntersection(SeqList<Type>

&LA,SeqList<Type>

&LB){

intn=LA.Length();

intm=LB.Length();inti=1;

while(i<n){Type(i);//在LA中取一元素

int(x);//在LB中搜索它

if(k==

-1){LA.Remove(i);n--;} elsei++;//未找到在LA中刪除它

}}順序表的應(yīng)用：集合的“交”運(yùn)算template<classType> 順序表的應(yīng)用：29多項(xiàng)式(Polynomial)n階多項(xiàng)式Pn(x)有n+1項(xiàng)。系數(shù)a0,a1,a2,…,an

指數(shù)0,1,2,…,n。按升冪排列多項(xiàng)式(Polynomial)n階多項(xiàng)式Pn(x)有n+130classPolynomial

{public:

Polynomial();//構(gòu)造函數(shù)

intoperator!

();//判是否零多項(xiàng)式

CoefficientCoef(Exponente);

Exponent

LeadExp();//返回最大指數(shù)

Polynomial

Add(Polynomial

poly);

Polynomial

Mult(Polynomialpoly);

floatEval(float

x); //求值}多項(xiàng)式(Polynomial)的抽象數(shù)據(jù)類型classPolynomial{多項(xiàng)式(Polynomi31#include<iostream.h>class

power{

double

x;

int

e;

double

mul;

public:

power(double

val,intexp);

double

get_power(){returnmul;}

};創(chuàng)建power類，計(jì)算x的冪#include<iostream.h>創(chuàng)建power類32power::power(double

val,int

exp){

//按val值計(jì)算乘冪

x=val;

e=exp;mul;

if(exp==0)return;

for(;

exp>0;

exp--)mul=mul*x;

}main(){

powerpwr(1.5,2);

cout<<pwr.get_power()<<“\n”;

}power::power(doubleval,int33

多項(xiàng)式的存儲(chǔ)表示第一種：

private:(靜態(tài)數(shù)

intdegree; 組表示)floatcoef[maxDegree+1];

Pn(x)可以表示為：

=n [i]=ai,0

i

n多項(xiàng)式的存儲(chǔ)表示第一種：private:34第二種：private:

(動(dòng)態(tài)數(shù)

int

degree;組表示)

float*coef;

Polynomial::Polynomial(int

sz){

degree=sz;

coef=newfloat[degree+1];

}以上兩種存儲(chǔ)表示適用于指數(shù)連續(xù)排列的多項(xiàng)式。但對(duì)于指數(shù)不全的多項(xiàng)式如P101(x)=3+5x50-14x101,不經(jīng)濟(jì)。第二種：private: 35第三種：

class

Polynomial;

classterm{

//多項(xiàng)式的項(xiàng)定義

friendPolynomial;

private:

floatcoef;//系數(shù)

intexp; //指數(shù)

};第三種：36classPolynomial{//多項(xiàng)式定義public:……private:

statictermtermArray[MaxTerms];//項(xiàng)數(shù)組

staticintfree;//當(dāng)前空閑位置指針

//term

Polynomial::termArray[MaxTerms];//intPolynomial::free=0;

intstart,finish; //多項(xiàng)式始末位置 }classPolynomial{//37A(xx1000B(xx50x101

兩個(gè)多項(xiàng)式存放在termArray中A(xx1000兩個(gè)多項(xiàng)式存放在termArray中38兩個(gè)多項(xiàng)式的相加結(jié)果多項(xiàng)式另存掃描兩個(gè)相加多項(xiàng)式，若都未檢測(cè)完：若當(dāng)前被檢測(cè)項(xiàng)指數(shù)相等，系數(shù)相加。若未變成0，則將結(jié)果加到結(jié)果多項(xiàng)式。若當(dāng)前被檢測(cè)項(xiàng)指數(shù)不等，將指數(shù)小者加到結(jié)果多項(xiàng)式。若有一個(gè)多項(xiàng)式已檢測(cè)完，將另一個(gè)多項(xiàng)式剩余部分復(fù)制到結(jié)果多項(xiàng)式。兩個(gè)多項(xiàng)式的相加結(jié)果多項(xiàng)式另存39PolynomialPolynomial::Add(PolynomialB){

PolynomialC;

int

a=start;

int

;

C.start=free;

floatc;

while(a<=finish&&)

Switch

(compare(termArray[a].exp,termArray[b].exp)){

//比較對(duì)應(yīng)項(xiàng)指數(shù)

case‘=’://指數(shù)相等

c=termArray[a].coef+termArray[b].coef;if(c)NewTerm(c,termArray[a].exp);

a++;b++;

break;

PolynomialPolynomial::Add(P40case'>':

NewTerm(termArray[b].coef,

termArray[b].exp);

b++;

break;

case'<':

NewTerm(termArray[a].coef,

termArray[a].exp);

a++;

}for(;a<=finish;a++)//a未檢測(cè)完時(shí)

NewTerm(termArray[a].coef,

termArray[a].exp);

case'>':41for(

;;b++)//b未檢測(cè)完時(shí)

NewTerm(termArray[b].coef,

termArray[b].exp);

C.finish=free-1;

return

C;}for(;;b++)//b未檢測(cè)完時(shí)42在多項(xiàng)式中加入新的項(xiàng)

void

Polynomial::NewTerm(floatc,

inte){

//把一個(gè)新的項(xiàng)加到多項(xiàng)式C(x)中

if(free>=maxTerms){cout<<"Toomanytermsinpolynomials”<<

endl;return;

}

termArray[free].coef=c;

termArray[free].exp=e;

free++;}

在多項(xiàng)式中加入新的項(xiàng)43稀疏矩陣

(SparseMatrix)行數(shù)m=6,列數(shù)n=7,非零元素個(gè)數(shù)t=6

稀疏矩陣(SparseMatrix)行數(shù)m=6,44稀疏矩陣(SparseMatrix)的抽象數(shù)據(jù)類型

template<classType>class

SparseMatrix

{

int

Rows,Cols,Terms;//行/列/非零元素?cái)?shù)

Trituple<Type>smArray[MaxTerms];

public://三元組表

SparseMatrix(int

MaxRow,intMaxcol);

SparseMatrix<Type>Transpose();//轉(zhuǎn)置

SparseMatrix<Type>//相加

Add(SparseMatrix<Type>b);SparseMatrix<Type>//相乘

Multiply(SparseMatrix<Type>b);}

稀疏矩陣(SparseMatrix)的抽象數(shù)據(jù)類型45

三元組(Trituple)類的定義

template<classType>class

SparseMatrix;template<classType>classTrituple

{ friendclass

SparseMatrixprivate:

int

row,col; //非零元素所在行號(hào)/列號(hào)

Typevalue;//非零元素的值

}

三元組(Trituple)類的定義46稀疏矩陣轉(zhuǎn)置矩陣稀疏矩陣轉(zhuǎn)置矩陣47用三元組表表示的稀疏矩陣及其轉(zhuǎn)置用三元組表表示的稀疏矩陣及其轉(zhuǎn)置48稀疏矩陣轉(zhuǎn)置算法思想設(shè)矩陣列數(shù)為Cols，對(duì)矩陣三元組表掃描Cols次。第k次檢測(cè)列號(hào)為k的項(xiàng)。第k次掃描找尋所有列號(hào)為k的項(xiàng)，將其行號(hào)變列號(hào)、列號(hào)變行號(hào)，順次存于轉(zhuǎn)置矩陣三元組表。設(shè)矩陣三元組表總共有Terms項(xiàng)，其時(shí)間代價(jià)為O(Cols*Terms)。若矩陣有200行，200列，10,000個(gè)非零元素，總共有2,000,000次處理。稀疏矩陣轉(zhuǎn)置算法思想設(shè)矩陣列數(shù)為Cols，對(duì)矩陣三元組表掃描49稀疏矩陣的轉(zhuǎn)置

template<classType>SparseMatrix<Type>SparseMatrix<Type>::

Transpose(){

SparseMatrix<Type>b;

b.Rows=Cols;

b.Cols=Rows;

b.Terms=Terms;//轉(zhuǎn)置矩陣的列數(shù),行數(shù)和非零元素個(gè)數(shù)

if(Terms>0){

int

CurrentB=0; //轉(zhuǎn)置三元組表存放指針稀疏矩陣的轉(zhuǎn)置50for(intk=0;k<Cols;k++)

for(inti=0;i<Terms;i++)

if(smArray[i].col==k){ [CurrentB].row=k;

[CurrentB].col=smArray[i].row; [CurrentB].value=smArray[i].value;

CurrentB++;

}}

returnb;}for(intk=0;k<Cols51快速轉(zhuǎn)置算法建立輔助數(shù)組rowSize和rowStart，記錄矩陣轉(zhuǎn)置后各行非零元素個(gè)數(shù)和各行元素在轉(zhuǎn)置三元組表中開始存放位置。掃描矩陣三元組表，根據(jù)某項(xiàng)的列號(hào)，確定它轉(zhuǎn)置后的行號(hào)，查rowStart表，按查到的位置直接將該項(xiàng)存入轉(zhuǎn)置三元組表中。轉(zhuǎn)置時(shí)間代價(jià)為O(max(Terms,Cols))。若矩陣有200列，10000個(gè)非零元素，總共需10000次處理?？焖俎D(zhuǎn)置算法建立輔助數(shù)組rowSize和rowStart，記52for(inti=0;i<Cols;i++)rowSize[i]=0; for(i=0;i<Terms;i++)rowSize[smArray[i].col]++;

rowStart[0]=0; for(i=1;i<Cols;i++) rowStart[i]=rowStart[i-1]+rowSize[i-1];for(inti=0;i<Cols;i++)53稀疏矩陣的快速轉(zhuǎn)置template<classType> SparseMatrix<Type>SparseMatrix<Type>::FastTranspos(){

int

*rowSize=newint[Cols];

int*rowStart=

newint[Cols];

SparseMatrix<Type>b;

b.Rows=Cols;b.Cols=Rows;

b.Terms=Terms;if(Terms>0){for(inti=0;i<Cols;i++)rowSize[i]=0;for(i=0;i<Terms;i++)

rowSize[smArray[i].col]++;稀疏矩陣的快速轉(zhuǎn)置54

rowStart[0]=0;

for(i=1;i<Cols;i++) rowStart[i]=rowStart[i-1]+rowSize[i-1]; for(i=0;i<Terms;i++){ intj=rowStart[smArray[i].col]; [j].row=smArray[i].col;[j].col=smArray[i].row;[j].value=smArray[i].value; rowStart[smArray[i].col]++;

}}

delete

[]rowSize;

delete[]rowStart;

returnb;} rowStart[0]=0; 55字符串(String)字符串是n(0)個(gè)字符的有限序列，記作S:“c1c2c3…cn”

其中，S是串名字“c1c2c3…cn”是串值

ci是串中字符

n是串的長(zhǎng)度。字符串(String)字符串是n(0)個(gè)字符的56constintmaxLen=128;

classString{intcurLen;//串的當(dāng)前長(zhǎng)度

char

*ch;//串的存儲(chǔ)數(shù)組

public:

String(constString&ob);

String(constchar*init);

String(

);~String(){delete[]ch;}

intLength()const{

return

curLen;}字符串抽象數(shù)據(jù)類型和類定義constintmaxLen=128; 字符串抽57

String

&operator()

(int

pos,

intlen);

intoperator

==(const

String&ob)const{returnstrcmp(ch,)==0;}

intoperator!=(const

String&ob)const{returnstrcmp(ch,)!=0;}

intoperator!()

const

{returncurLen==0;}

String

&operator=(const

String

&ob);

String&operator+=(const

String&ob);char&operator[](inti);

intFind(Stringpat)const;}String&operator()(int58

String::String(constString&ob){

//復(fù)制構(gòu)造函數(shù)：從已有串ob復(fù)制

ch=newchar[maxLen+1];

if(!ch){

cout<<“AllocationError\n”;

exit(1);

}

curLen=

;

strcpy(ch,ob.ch);}

字符串部分操作的實(shí)現(xiàn)String::String(constStrin59String::String(const

char*init){//復(fù)制構(gòu)造函數(shù):從已有字符數(shù)組*init復(fù)制

ch=newchar[maxLen+1];

if(!ch){cout<<“AllocationError\n”;

exit(1);

}

curLen=

strlen(init);

strcpy(ch,init);

}String::String(constchar*i60String::String(

){//構(gòu)造函數(shù)：創(chuàng)建一個(gè)空串

ch=newchar[maxLen+1];

if(!ch){

cout<<“AllocationError\n”;

exit(1);}

curLen=0;

ch[0]=‘\0’;}String::String(){61提取子串的算法示例pos+len-1 pos+len-1

curLen-1

curLen提取子串的算法示例pos+len-1 62String&String::operator()(intpos,

int

len){//從串中第pos個(gè)位置起連續(xù)提取len個(gè)字符

//形成子串返回

if(pos<0

||pos+len-1>=maxLen

||len<0){

temp.curLen=0;

//返回空串

[0]='\0';

}

else{//提取子串

String*temp=newString;//動(dòng)態(tài)分配String&String::63

if(pos+len-1>=curLen)

len=curLen-pos;

temp→curLen=len;//子串長(zhǎng)度

for(inti=0,j=pos;i<len;i++,j++)

temp→ch[i]=ch[j];//傳送串?dāng)?shù)組

temp→ch[len]=‘\0’;//子串結(jié)束

}

return

temp;}

if(pos+len-1>=curLen)64String&String::operator=

(const

String&ob){//串賦值：從已有串ob復(fù)制

if(&ob!=this){

delete[]ch;

ch=new

char[maxLen+1];//重新分配

if(!ch){cerr<<“OutOfMemory!\n”;

exit(1);

}

curLen=;//串復(fù)制

strcpy(ch,);

}String&String::65數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法66作為抽象數(shù)據(jù)類型的數(shù)組一維數(shù)組一維數(shù)組的示例作為抽象數(shù)據(jù)類型的數(shù)組一維數(shù)組67一維數(shù)組的特點(diǎn)連續(xù)存儲(chǔ)的線性聚集（別名向量）除第一個(gè)元素外，其他每一個(gè)元素有一個(gè)且僅有一個(gè)直接前驅(qū)。除最后一個(gè)元素外，其他每一個(gè)元素有一個(gè)且僅有一個(gè)直接后繼。一維數(shù)組的特點(diǎn)連續(xù)存儲(chǔ)的線性聚集（別名向量）68數(shù)組的定義和初始化#include<iostream.h>classszcl{inte; public:

szcl(){e=0;}

szcl(intvalue){e=value;} intget_value(){returne;} }數(shù)組的定義和初始化#include<iostream.h>69main

(){

szcla1[3]={3,5,7},*elem;

for(int

i=0,i<3,i++)

cout<<a1[i].get_value()<<“\n”; //打印靜態(tài)數(shù)組

elem=&a1;

for(int

i=0,i<3,i++){

cout<<elem→get_value()<<“\n”; //打印動(dòng)態(tài)數(shù)組

elem++;

}

return0;}

main(){70一維數(shù)組(Array)類的定義#include<iostream.h>#include<stdlib.h>template<classType>classArray{Type

*elements;//數(shù)組存放空間

intArraySize;//當(dāng)前長(zhǎng)度

voidgetArray();//建立數(shù)組空間

public:Array(intSize=DefaultSize);

Array(const

Array<Type>&x);一維數(shù)組(Array)類的定義#include<iost71~Array(){delete[]elements;} Array<Type>

&

operator

=

(const

Array<Type>

&A);Type&operato[](inti); operatorType*

()

const

{return

elements;}int

Length()const{returnArraySize;} voidReSize(intsz); }~Array(){delete[]e72template<classType>void

Array<Type>::getArray(){

//私有函數(shù)：創(chuàng)建數(shù)組存儲(chǔ)空間

elements=newType[ArraySize];if(elements==0)

cerr<<"MemoryAllocationError"<<endl;}一維數(shù)組公共操作的實(shí)現(xiàn)template<classType>一維數(shù)組公共操73template<classType>void

Array<Type>::Array(intsz){

//構(gòu)造函數(shù)

if(sz<=0){cerr<<"InvalidArraySize"<<

endl;return;}

ArraySize=sz;getArray();

}template<classType>74template<classType> Array<Type>::

Array(const

Array<Type>

&x){

//復(fù)制構(gòu)造函數(shù)

int;

elements=newType[n]; if(elements==0)

cerr

<<"MemoryAllocationError"<<endl;

Type;

Type

*destptr=elements;

while

(n--

)*destptr++=*srcptr++;}template<classType> Array<T75template<classType>Type&Array<Type>::operator[](inti){

//按數(shù)組名及下標(biāo)i，取數(shù)組元素的值

if(i<0

||i>ArraySize-1)

cerr<<"IndexoutofRange"<<

endl;

returnelement[i]; }

使用該函數(shù)于賦值語(yǔ)句

Position[i]=Position[i-1]+Number[i

-1]template<classType>76template<classType>void

Array<Type>::Resize(int

sz){if(sz>=0&&

sz!=ArraySize){Type*newarray=

newType[sz]; if(newarray==0)

cerr

<<"MemoryAllocationError"<<

endl;intn=(sz<=ArraySize)?sz:ArraySize; Type

*srcptr=elements; Type*destptr=newarray; while(n--)*destptr++=*srcptr++;

delete[]elements; elements=newarray; ArraySize=sz; }}

template<classType>77

二維數(shù)組三維數(shù)組行向量下標(biāo)

i頁(yè)向量下標(biāo)i列向量下標(biāo)

j行向量下標(biāo)j

列向量下標(biāo)k二維數(shù)組三維數(shù)組行向量下標(biāo)78數(shù)組的連續(xù)存儲(chǔ)方式一維數(shù)組LOC(i)=LOC(i-1)+l=α+i*l數(shù)組的連續(xù)存儲(chǔ)方式一維數(shù)組LOC(i)=LOC(79

二維數(shù)組行優(yōu)先LOC(j,k)=j*m+k

二維數(shù)組行優(yōu)先LOC(j,k)=j*m80n維數(shù)組各維元素個(gè)數(shù)為

m1,m2,m3,…,mn下標(biāo)為i1,i2,i3,…,in

的數(shù)組元素的存儲(chǔ)地址：n維數(shù)組各維元素個(gè)數(shù)為m1,m2,m3,…,m81順序表(SequentialList)順序表的定義和特點(diǎn)定義n（0）個(gè)表項(xiàng)的有限序列

（a1,a2,…,an）

ai是表項(xiàng)，n是表長(zhǎng)度。 特點(diǎn)順序存取遍歷逐項(xiàng)訪問從前向后從后向前從兩端向中間順序表(SequentialList)順序表的定義和特點(diǎn)82順序表(SeqList)類的定義template<classType> class

SeqList{Type*data;//順序表存儲(chǔ)數(shù)組

intMaxSize; //最大允許長(zhǎng)度

int

last; //當(dāng)前最后元素下標(biāo)public:

SeqList(intMaxSize=defaultSize);

~SeqList()

{delete[]data;}

intLength()

const

{return

last+1;

}

intFind(Type

&x)const;順序表(SeqList)類的定義template<clas83

intIsIn(Type

&x);

int

Insert(Type&x,int

i);

int

Remove(Type

&x);

intNext(Type

&x);

intPrior(Type

&x);intIsEmpty()

{return

last==-1;

} int

IsFull()

{returnlast==MaxSize-1;

} Type

&Get(

inti){return

i<0

||i>last？NULL

:

data[i];}}

intIsIn(Type&x); 84順序表部分公共操作的實(shí)現(xiàn)template<classType>

SeqList<Type>::SeqList(intsz){//構(gòu)造函數(shù)

if(sz>0)

{

MaxSize=sz;last=-1;

data=newType[MaxSize];

} }順序表部分公共操作的實(shí)現(xiàn)template<classT85template<classType> int

SeqList<Type>::Find(Type

&x)const{//搜索函數(shù)：在表中從前向后順序查找x

inti=0;

while

(i<=last&&data[i]

!=x)

i++;

if(i>last)return

-1;

elsereturni; }template<classType> 86順序搜索圖示x=48x=50順序搜索圖示x=4887搜索成功

若搜索概率相等，則

搜索不成功數(shù)據(jù)比較n

次搜索成功

若搜索概率相等，則

88表項(xiàng)的插入表項(xiàng)的插入89template<classType>int

SeqList<Type>::Insert(

Type

&x,

int

i){//在表中第i

個(gè)位置插入新元素x

if(i<0

||

i>last+1

||

last==MaxSize-1)

return0;//插入不成功

else{

last++;

for(

intj=last;j>i;j--

)

data[j]=data[j-1];

data[i]=x;return1;//插入成功

}}template<classType>90表項(xiàng)的刪除表項(xiàng)的刪除91template<classType>int

SeqList<Type>::Remove(

Type

&x){//在表中刪除已有元素x

int

i=Find(x); //在表中搜索x

if(i>=0

){

last--;

for(intj=i;j<=last;j++)

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

return1; //成功刪除

} return0;//表中沒有

x}template<classType>92順序表的應(yīng)用：集合的“并”運(yùn)算

template<classType>void

Union(SeqList<Type>

&LA,SeqList<Type>

&LB){

intn=LA.Length();

intm=LB.Length();

for(inti=1;i<=m;i++){ Type(i);//在LB中取一元素

int(x);//在LA中搜索它

if(k==

-1)//若未找到插入它

{LA.Insert(n+1,x);n++;}}}順序表的應(yīng)用：集合的“并”運(yùn)算template<clas93template<classType> voidIntersection(SeqList<Type>

&LA,SeqList<Type>

&LB){

intn=LA.Length();

intm=LB.Length();inti=1;

while(i<n){Type(i);//在LA中取一元素

int(x);//在LB中搜索它

if(k==

-1){LA.Remove(i);n--;} elsei++;//未找到在LA中刪除它

}}順序表的應(yīng)用：集合的“交”運(yùn)算template<classType> 順序表的應(yīng)用：94多項(xiàng)式(Polynomial)n階多項(xiàng)式Pn(x)有n+1項(xiàng)。系數(shù)a0,a1,a2,…,an

指數(shù)0,1,2,…,n。按升冪排列多項(xiàng)式(Polynomial)n階多項(xiàng)式Pn(x)有n+195classPolynomial

{public:

Polynomial();//構(gòu)造函數(shù)

intoperator!

();//判是否零多項(xiàng)式

CoefficientCoef(Exponente);

Exponent

LeadExp();//返回最大指數(shù)

Polynomial

Add(Polynomial

poly);

Polynomial

Mult(Polynomialpoly);

floatEval(float

x); //求值}多項(xiàng)式(Polynomial)的抽象數(shù)據(jù)類型classPolynomial{多項(xiàng)式(Polynomi96#include<iostream.h>class

power{

double

x;

int

e;

double

mul;

public:

power(double

val,intexp);

double

get_power(){returnmul;}

};創(chuàng)建power類，計(jì)算x的冪#include<iostream.h>創(chuàng)建power類97power::power(double

val,int

exp){

//按val值計(jì)算乘冪

x=val;

e=exp;mul;

if(exp==0)return;

for(;

exp>0;

exp--)mul=mul*x;

}