工學(xué)數(shù)據(jù)結(jié)構(gòu)5-數(shù)組和字符串課件

第5講DATASTRUCTURE第5講DATASTRUCTUREDATASTRUCTURE第4章數(shù)組和字符串?dāng)?shù)組1特殊矩陣2稀疏矩陣3字符串4數(shù)組1DATASTRUCTURE第4章數(shù)組和字符串?dāng)?shù)組1特殊DATASTRUCTURE§4.1.1

數(shù)組ADT數(shù)組的定義數(shù)組是下標(biāo)index和值value組成的序?qū)Φ募稀?/p>

(index,value)一維數(shù)組： A={(0,15),(1,24),(2,33),(3,21)}

012315243321DATASTRUCTURE§4.1.1

數(shù)組ADT數(shù)組的DATASTRUCTURE§4.1.1

數(shù)組ADT數(shù)組ADT

ADTArray{數(shù)據(jù)：

下標(biāo)index和元素值value組成的數(shù)據(jù)對(duì)集合,其中任意兩個(gè)數(shù)據(jù)對(duì)的下標(biāo)index各不相同。運(yùn)算：

Create():建立一個(gè)數(shù)組。

Retrieve(i):返回下標(biāo)為i的元素值。

Store(i,x):將下標(biāo)為i的數(shù)據(jù)對(duì)的值置為x。};

DATASTRUCTURE§4.1.1

數(shù)組ADT數(shù)組ADATASTRUCTURE§4.1.2

數(shù)組的順序表示一維數(shù)組的順序表示

loc(a[i])

=

loc(a[0])+i*k

(

i

=

0,

1,

2,

…,

n-1

)基地址：loc(a[0])每個(gè)元素占

k個(gè)存儲(chǔ)單元。

template<classT>A[]={a0,a1,…,ai,…,an-1};

pA=newT[100];//然后賦值Tb1=pA[i];//獲取第i個(gè)元素Tb2=*(pA+i);//獲取第i個(gè)元素DATASTRUCTURE§4.1.2

數(shù)組的順序表示一DATASTRUCTURE§4.1.2

數(shù)組的順序表示二維數(shù)組的順序表示二維數(shù)組a[m][n]映射到一維的存儲(chǔ)空間時(shí)有兩種順序：行優(yōu)先和列優(yōu)先。大多數(shù)語(yǔ)言如PASCAL、BASIC、C、C++等都是按行優(yōu)先順序存儲(chǔ)的，F(xiàn)ORTRAN是按列優(yōu)先順序存儲(chǔ)的。A[m][n]={{a0,0,a0,1,…a0,n-1},…,{ai,0,ai,1,…ai,n-1},…,{am-1,0,am-1,1,…am-1,n-1}};C/C++行優(yōu)先的存儲(chǔ)方法DATASTRUCTURE§4.1.2

數(shù)組的順序表示二DATASTRUCTURE§4.1.2

數(shù)組的順序表示二維數(shù)組的順序表示

loc(a[i][j])=loc(a[0][0])+(i*n+j)*k

(0i<m;0j<n)基地址：loc(a[0][0])每個(gè)元素占

k個(gè)存儲(chǔ)單元。

DATASTRUCTURE§4.1.2

數(shù)組的順序表示二DATASTRUCTURE§4.1.2

數(shù)組的順序表示C/C++中申請(qǐng)二維數(shù)組的方法：introw=3,col=4;//方法1：=====================================intMtrx[row][col]={{1,2,3,4},{5,6,7,8},{9,10,11,12}};//方法2：=====================================int**ppMtrx=new

int*[row];for(inti=0;i<row;i++) ppMtrx[i]=new

int[col];intn=0;for(i=0;i<row;i++)

for(intj=0;j<col;j++) ppMtrx[i][j]=++n;for(i=0;i<row;i++)

delete[]ppMtrx[i];delete[]ppMtrx;申請(qǐng)指針數(shù)組再為指針數(shù)組申請(qǐng)空間為二維數(shù)組賦值刪除二維數(shù)組DATASTRUCTURE§4.1.2

數(shù)組的順序表示DATASTRUCTURE§4.1.2

數(shù)組的順序表示//方法3：=====================================#definerow3#definecol4typedefintMtrx[row];

main(){

intn=0;

Mtrx*pMtrx=newMtrx[col];//用法與二維數(shù)組相同

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

for(intj=0;j<col;j++) pMtrx[i][j]=++n;

delete[]pMtrx;}

定義二維數(shù)組將數(shù)組定義為數(shù)據(jù)類型DATASTRUCTURE§4.1.2

數(shù)組的順序表示/DATASTRUCTURE§4.1.2

數(shù)組的順序表示多維數(shù)組的順序表示推廣到多維數(shù)組a[m1][m2]…[mn]，數(shù)組元素a[i1][i2]…[in]的存儲(chǔ)地址為：

loc(a[i1][i2]…[in])=

loc(a[0]…[0])+(i1*m2*m3*…*mn+i2*m3*m4*…*mn+…+in-1*mn+in)*k

=DATASTRUCTURE§4.1.2

數(shù)組的順序表示多DATASTRUCTURE§4.1.3

一維數(shù)組的C++類用C++的模板類定義的一維數(shù)組抽象數(shù)據(jù)類型。公有成員函數(shù)包括：

構(gòu)造函數(shù)析構(gòu)函數(shù)重載下標(biāo)操作符：[]

重載下標(biāo)操作符用來(lái)返回指向第i個(gè)元素的引用

重載數(shù)組賦值：＝

賦值操作符實(shí)現(xiàn)數(shù)組的整體賦值。DATASTRUCTURE§4.1.3

一維數(shù)組的C++DATASTRUCTURE§4.1.3

一維數(shù)組的C++類#include<assert.h>template<classT>classArray1D{public:Array1D(intsz=0);~Array1D(){delete[]elements;}T&operator[](inti)const;Array1D<T>&operator=(constArray1D<T>&r);friendistream&operator>>(istream&in,Array1D<T>&r);friendostream&operator<< (ostream&out,constArray1D<T>&r);private:

intsize; T*elements;};取元素值整體賦值缺少拷貝構(gòu)造函數(shù)！DATASTRUCTURE§4.1.3

一維數(shù)組的C++DATASTRUCTURE§4.1.3

一維數(shù)組的C++類構(gòu)造函數(shù)，申請(qǐng)數(shù)組空間template<classT>Array1D<T>::Array1D(intsz){

assert(sz>=0);//越界檢查

size=sz; elements=newT[sz];}運(yùn)算符[]，獲取第i個(gè)元素template<classT>T&Array1D<T>::operator[](inti)const{

assert(i>=0&&i<size);//越界檢查

returnelements[i];}

DATASTRUCTURE§4.1.3

一維數(shù)組的C++DATASTRUCTURE§4.1.3

一維數(shù)組的C++類重載運(yùn)算符=

template<classT>Array1D<T>&Array1D<T>::operator=(constArray1D<T>&r)

//數(shù)組r整體賦值給this{

if(this!=&r){//防止自我賦值

size=r.size;

delete[]elements;//釋放原空間

elements=newT[size];//重新分配空間

for(inti=0;i<size;i++) elements[i]=r.elements[i];}

return*this;}DATASTRUCTURE§4.1.3

一維數(shù)組的C++DATASTRUCTURE§4.1.3

一維數(shù)組的C++類重載流運(yùn)算符>>和<<template<classT>istream&operator>>(istream&in,Array1D<T>&r){

cout<<"Intputarray\n";

for(inti=0;i<r.size;i++)in>>r.elements[i];

returnin;}template<classT>ostream&operator<<(ostream&out,constArray1D<T>&r){

cout<<"Array=";

for(inti=0;i<r.size;i++)out<<r.elements[i]<<''; out<<endl; returnout;}

DATASTRUCTURE§4.1.3

一維數(shù)組的C++DATASTRUCTUREmain中測(cè)試該類的效果#include"array1d.h"main(){Array1D<int>a(5),b(8); Array1D<int>c;//采用缺省長(zhǎng)度0

cin>>a;cout<<"a"<<a;

cin>>b;cout<<"b"<<b;

cout<<"c"<<c;

cout<<"a[0]="<<a[0]<<“;“<<"b[5]="<<b[5]<<endl;c=b;cout<<"c=b,c"<<c;b=a;cout<<"b=a,b"<<b;}§4.1.3

一維數(shù)組的C++類DATASTRUCTUREmain中測(cè)試該類的效果§4.1DATASTRUCTURE§1

C++中有關(guān)數(shù)組的類classArray{public: Array(intsize=0,char*ptr=NULL);

//defaultconstructor Array(constArray&);//copyconstructor ~Array();//destructor

char*getPtr()const{returnm_ptr;}

voidSetArray(intsize,char*ptr);private:

int*m_ptr;//pointertothe //firstelementofthearray.

intm_size;};DATASTRUCTURE§1

C++中有關(guān)數(shù)組的類cDATASTRUCTURE§1

C++中有關(guān)數(shù)組的類Array::Array(intsize,char*ptr/*=NULL*/){m_ptr=NULL; SetArray(size,ptr);}Array::Array(constArray&ar){SetArray(ar.m_size,ar.m_ptr);}Array::~Array(){if(m_ptr!=NULL)delete[]m_ptr;}voidArray::SetArray(intsize,char*ptr)

//有問(wèn)題的函數(shù)！{m_size=size;m_ptr=ptr;}淺拷貝！要改成深拷貝。DATASTRUCTURE§1

C++中有關(guān)數(shù)組的類ADATASTRUCTURE§1

C++中有關(guān)數(shù)組的類#include<iostream.h>#include<string.h>main(){

charstr[9]; strcpy(str,“Software”);

//注意：此處不能用char*str=”Software”;//因?yàn)檫@樣的字符串是只讀的。 Arrayar1(8,str); Arrayar2(ar1);

//調(diào)用拷貝構(gòu)造函數(shù)，其中調(diào)用了SetArray() str[0]=‘6’;//改變數(shù)組內(nèi)容

cout<<ar1.getPtr()<<“”;

cout<<ar2.getPtr()<<endl;}輸出：6oftware6oftware淺拷貝的后果。DATASTRUCTURE§1

C++中有關(guān)數(shù)組的類#DATASTRUCTURE§1

C++中有關(guān)數(shù)組的類voidArray::SetArray(intsize,char*ptr){

if(size==0||ptr==NULL)return;

if(m_ptr!=NULL)delete[]m_ptr;

//釋放原數(shù)組

m_size=size; m_ptr=new

char[size];//申請(qǐng)新的空間

strncpy(m_ptr,ptr,size);//拷貝}

輸出：Software6oftwareDATASTRUCTURE§1

C++中有關(guān)數(shù)組的類vDATASTRUCTURE第4章數(shù)組和字符串?dāng)?shù)組1特殊矩陣2稀疏矩陣3字符串4數(shù)組1特殊矩陣2DATASTRUCTURE第4章數(shù)組和字符串?dāng)?shù)組1特殊DATASTRUCTURE§4.2.1

對(duì)稱矩陣對(duì)稱矩陣和三角矩陣在n×n的矩陣A中，若aij=aji(0<i,j<n)，則稱其為n階對(duì)稱矩陣。對(duì)于對(duì)稱矩陣，可以只存儲(chǔ)上三角(或下三角)中的元素(包括對(duì)角線上的元素)。DATASTRUCTURE§4.2.1

對(duì)稱矩陣對(duì)稱矩陣DATASTRUCTURE§4.2.1

對(duì)稱矩陣如果采用二維數(shù)組，n維對(duì)稱矩陣的元素為n2。如果只存儲(chǔ)三角中元素，則元素個(gè)數(shù)為

n(n+1)/2其中行列序號(hào)與元素序號(hào)的對(duì)應(yīng)關(guān)系：0123…num-1a0,0a1,0a1,1a2,0…an-1,0…an-1,n-1DATASTRUCTURE§4.2.1

對(duì)稱矩陣如果采用DATASTRUCTURE第4章數(shù)組和字符串?dāng)?shù)組1特殊矩陣2稀疏矩陣3字符串4數(shù)組1特殊矩陣2稀疏矩陣3DATASTRUCTURE第4章數(shù)組和字符串?dāng)?shù)組1特殊DATASTRUCTURE§4.3.1

稀疏矩陣ADT稀疏矩陣大多數(shù)元素為零的矩陣稱為稀疏矩陣。對(duì)于稀疏矩陣可只存非零元素。DATASTRUCTURE§4.3.1

稀疏矩陣ADT稀DATASTRUCTURE§4.3.1

稀疏矩陣ADT稀疏矩陣ADT

ADTSparseMatrix{數(shù)據(jù)：絕大多數(shù)元素為零的矩陣。運(yùn)算：

Create():建立一個(gè)稀疏矩陣。

Destroy():撤消一個(gè)稀疏矩陣。

Add(B,C):當(dāng)前矩陣對(duì)象與B相加，C中返回相加和。

Mul(B,C):當(dāng)前矩陣對(duì)象與B相乘，C中返回相乘積。

Transpose(B):B中返回當(dāng)前矩陣對(duì)象的轉(zhuǎn)置矩陣。}

DATASTRUCTURE§4.3.1

稀疏矩陣ADT稀DATASTRUCTURE§4.3.1

稀疏矩陣ADT#include<iostream.h>template<classT>classSparseMatrix{public: SparseMatrix(intmaxRowSize,intmaxColSize){} ~SparseMatrix(){}

virtualvoidAdd(constSparseMatrix<T>&B,SparseMatrix<T>&C)const;

virtualvoidMul(constSparseMatrix<T>&B,SparseMatrix<T>&C)const;

virtualvoidTranspose(SparseMatrix<T>&B)const;private:

intmaxRows,maxCols;};稀疏矩陣的C++類DATASTRUCTURE§4.3.1

稀疏矩陣ADT#DATASTRUCTURE§4.3.2

稀疏矩陣的順序表示三元組表示法按照壓縮存儲(chǔ)的思想，稀疏矩陣Am

n中的每一個(gè)非零元素aij

的值、行號(hào)和列號(hào)可以用一個(gè)三元組（i,j,v）表示。三元組可以按行或按列的順序存儲(chǔ)。三元組的Term類template

<classT>structTerms{

introw,col;Tvalue;};DATASTRUCTURE§4.3.2

稀疏矩陣的順序表DATASTRUCTURE§4.3.2

稀疏矩陣的順序表示0016032205-16111212323-840916215DATASTRUCTURE§4.3.2

稀疏矩陣的順序表DATASTRUCTURE§4.3.2

稀疏矩陣的順序表示#include<iostream.h>template<classT>classSeqTriple{public: SeqTriple(intmSize); ~SeqTriple(){delete[]trip;};

voidAdd(constSeqTriple<T>&B,SeqTriple<T>&C)const;

voidMul(constSeqTriple<T>&B,SeqTriple<T>&C)const;

voidTranspose(SeqTriple<T>&B)const; friendistream&operator>>(istream&input, constSeqTriple<T>&); friendostream&operator<<(ostream&output,

constSeqTriple<T>&);private:

intmaxSize;//最大元素個(gè)數(shù)

intm,n,t;//行數(shù)、列數(shù)和非零元素個(gè)數(shù)

Term<T>*trip;//動(dòng)態(tài)一維數(shù)組的指針};行三元組表的C++類DATASTRUCTURE§4.3.2

稀疏矩陣的順序表DATASTRUCTURE第4章數(shù)組和字符串?dāng)?shù)組1特殊矩陣2稀疏矩陣3字符串4數(shù)組1特殊矩陣2稀疏矩陣3字符串4DATASTRUCTURE第4章數(shù)組和字符串?dāng)?shù)組1特殊DATASTRUCTURE§4.4.1

字符串ADT字符串的定義字符串(簡(jiǎn)稱為串)是由n(≥0)個(gè)字符組成的有限序列。S=“a0

a1…an-1”(n≥0)其中，S

是串名，單引號(hào)括起來(lái)的字符序列是串S的值。n是串中字符個(gè)數(shù)，又稱串長(zhǎng)度，n=0的串稱為空串。要注意區(qū)分空串和空白串。串中任意連續(xù)個(gè)字符組成的子序列稱為該串的子串，包含子串的串稱為主串。通常以子串的首字符在主串中的位置作為子串在主串中的位置。

S=“abcabcaabcbcde”

P=“aabc”DATASTRUCTURE§4.4.1

字符串ADT字符DATASTRUCTURE§4.4.1

字符串ADT字符串ADTADTString{數(shù)據(jù)：字符串是由n(≥0)個(gè)字符組成的有限序列

S

=

“a0a1…an-1”，0

≤

i

<n。運(yùn)算：

Create():建立一個(gè)空串。Destroy():撤消一個(gè)串。Length():返回當(dāng)前串對(duì)象的長(zhǎng)度。Clear():置為空串。

Assign(S):串S的值賦給當(dāng)前串對(duì)象。

Concat(b):將串b連接在當(dāng)前串對(duì)象之后。DATASTRUCTURE§4.4.1

字符串ADT字符DATASTRUCTURE§4.4.1

字符串ADTInsert(P,i):將串P插在當(dāng)前串對(duì)象的位置i處。

Delete(i,len):從當(dāng)前串對(duì)象的位置i起刪除len個(gè)字符。

Substr(i,len):返回當(dāng)前串對(duì)象中，從位置i開始的len個(gè)字符組成的子串。Find(i,P):返回子串P在當(dāng)前串對(duì)象中的位置。若當(dāng)前串對(duì)象不包含串P，則返回-1。}DATASTRUCTURE§4.4.1

字符串ADTDATASTRUCTURE§4.4.2

字符串的存儲(chǔ)表示順序表示串的順序表示可用C++的一維字符數(shù)組來(lái)描述。

#include<string.h>chars[20]=“cdabcde“；鏈接表示…ABCI∧firstfirstABCDEFGHI∧\0

DATASTRUCTURE§4.4.2

字符串的存儲(chǔ)表示DATASTRUCTURE§4.4.2

字符串的存儲(chǔ)表示#include<string.h>classString{public: String();String(const

char*p);~String(){delete[]str;} intFind(inti,String&P);private:

intn;//當(dāng)前串長(zhǎng)

char*str;//動(dòng)態(tài)一維字符數(shù)組的指針};String::String(const

char*p){ n=strlen(p);str=newchar[n+1];strcpy(str,p);}DATASTRUCTURE§4.4.2

字符串的存儲(chǔ)表示DATASTRUCTURE§4.4.2

字符串的存儲(chǔ)表示C語(yǔ)言中字符串操作函數(shù)函數(shù)原型:char*strdup(constchar*s)函數(shù)功能:字符串拷貝，目的空間由該函數(shù)分配函數(shù)返回:指向拷貝后的字符串指針函數(shù)原型:char*strcpy(char*str1,char*str2);函數(shù)功能:把str2指向的字符串拷貝到str1中去函數(shù)返回:返回str1,即指向str1的指針函數(shù)原型:char*strncpy(char*dest, constchar*src，intcount)

函數(shù)功能:將字符串src中的count個(gè)字符拷貝到字符串dest中去函數(shù)返回:指向dest的指針函數(shù)原型:unsignedintstrlen(char*str);函數(shù)功能:統(tǒng)計(jì)字符串str中字符的個(gè)數(shù)(不包括終止符''\0'')函數(shù)返回:返回字符串的長(zhǎng)度.DATASTRUCTURE§4.4.2

字符串的存儲(chǔ)表示DATASTRUCTURE§4.4.2

字符串的存儲(chǔ)表示C語(yǔ)言中字符串操作函數(shù)函數(shù)原型:

char*strchr(char*str,charch);函數(shù)功能:找出str指向的字符串中第一次出現(xiàn)字符ch的位置函數(shù)返回:返回指向該位置的指針,如找不到,則返回空指針函數(shù)原型:char*

strrchr(constchar*s,intc)函數(shù)功能:得到字符串s中最后一個(gè)含有c字符的位置指針函數(shù)返回:位置指針函數(shù)原型:char*strstr(char*str1,char*str2);函數(shù)功能:找出str2字符串在str1字符串中第一次出現(xiàn)的位置(不包括str2的串結(jié)束符)函數(shù)返回:返回該位置的指針,如找不到,返回空指針函數(shù)原型:char*strpbrk(constchar*s1,constchar*s2)

函數(shù)功能:得到s1中第一個(gè)“同時(shí)也出現(xiàn)在s2中”字符的位置指針函數(shù)返回:位置指針DATASTRUCTURE§4.4.2

字符串的存儲(chǔ)表示DATASTRUCTURE§4.4.2

字符串的存儲(chǔ)表示C語(yǔ)言中字符串操作函數(shù)函數(shù)原型:char*

strnset(char*

s,intch,size_tn)函數(shù)功能:將字符串s中前n個(gè)字符設(shè)置為ch的值函數(shù)返回:指向s的指針函數(shù)原型:char*

strset(char*s,intch)函數(shù)功能:將字符串s中所有字符設(shè)置為ch的值函數(shù)返回:指向s的指針函數(shù)原型:char*

strupr(char*s)

函數(shù)功能:將字符串s中的字符變?yōu)榇髮懞瘮?shù)返回:指向s的指針函數(shù)原型:char*

strlwr(char*s)

函數(shù)功能:將字符串中的字符變?yōu)樾懽址瘮?shù)返回:指向s的指針DATASTRUCTURE§4.4.2

字符串的存儲(chǔ)表示DATASTRUCTURE§4.4.2

字符串的存儲(chǔ)表示C語(yǔ)言中字符串操作函數(shù)還有：intmemcmp(constvoid*s1,constvoid*s2,size_tn)intmemicmp(constvoid*s1,constvoid*s2,size_tn)void*memmove(void*dest,constvoid*src,size_tn)DATASTRUCTURE§4.4.2

字符串的存儲(chǔ)表示DATASTRUCTURE習(xí)題

p.52實(shí)現(xiàn)書上程序4.1與程序4.2一維數(shù)組類（要求：增加拷貝構(gòu)造函數(shù)，并在main中增加適當(dāng)測(cè)試代碼）===============================================文件名：

D+學(xué)號(hào)后兩位+姓名+布置作業(yè)日期例如

D01張三0422

工程名：

D+學(xué)號(hào)后兩位+姓名縮寫+布置作業(yè)日期例如

D01ZS0422最后把debug目錄刪除，打包按文件名發(fā)送===============================================§作業(yè)0422DATASTRUCTURE習(xí)題§作業(yè)0422第5講DATASTRUCTURE第5講DATASTRUCTUREDATASTRUCTURE第4章數(shù)組和字符串?dāng)?shù)組1特殊矩陣2稀疏矩陣3字符串4數(shù)組1DATASTRUCTURE第4章數(shù)組和字符串?dāng)?shù)組1特殊DATASTRUCTURE§4.1.1

數(shù)組ADT數(shù)組的定義數(shù)組是下標(biāo)index和值value組成的序?qū)Φ募稀?/p>

(index,value)一維數(shù)組： A={(0,15),(1,24),(2,33),(3,21)}

012315243321DATASTRUCTURE§4.1.1

數(shù)組ADT數(shù)組的DATASTRUCTURE§4.1.1

數(shù)組ADT數(shù)組ADT

ADTArray{數(shù)據(jù)：

下標(biāo)index和元素值value組成的數(shù)據(jù)對(duì)集合,其中任意兩個(gè)數(shù)據(jù)對(duì)的下標(biāo)index各不相同。運(yùn)算：

Create():建立一個(gè)數(shù)組。

Retrieve(i):返回下標(biāo)為i的元素值。

Store(i,x):將下標(biāo)為i的數(shù)據(jù)對(duì)的值置為x。};

DATASTRUCTURE§4.1.1

數(shù)組ADT數(shù)組ADATASTRUCTURE§4.1.2

數(shù)組的順序表示一維數(shù)組的順序表示

loc(a[i])

=

loc(a[0])+i*k

(

i

=

0,

1,

2,

…,

n-1

)基地址：loc(a[0])每個(gè)元素占

k個(gè)存儲(chǔ)單元。

template<classT>A[]={a0,a1,…,ai,…,an-1};

pA=newT[100];//然后賦值Tb1=pA[i];//獲取第i個(gè)元素Tb2=*(pA+i);//獲取第i個(gè)元素DATASTRUCTURE§4.1.2

數(shù)組的順序表示一DATASTRUCTURE§4.1.2

數(shù)組的順序表示二維數(shù)組的順序表示二維數(shù)組a[m][n]映射到一維的存儲(chǔ)空間時(shí)有兩種順序：行優(yōu)先和列優(yōu)先。大多數(shù)語(yǔ)言如PASCAL、BASIC、C、C++等都是按行優(yōu)先順序存儲(chǔ)的，F(xiàn)ORTRAN是按列優(yōu)先順序存儲(chǔ)的。A[m][n]={{a0,0,a0,1,…a0,n-1},…,{ai,0,ai,1,…ai,n-1},…,{am-1,0,am-1,1,…am-1,n-1}};C/C++行優(yōu)先的存儲(chǔ)方法DATASTRUCTURE§4.1.2

數(shù)組的順序表示二DATASTRUCTURE§4.1.2

數(shù)組的順序表示二維數(shù)組的順序表示

loc(a[i][j])=loc(a[0][0])+(i*n+j)*k

(0i<m;0j<n)基地址：loc(a[0][0])每個(gè)元素占

k個(gè)存儲(chǔ)單元。

DATASTRUCTURE§4.1.2

數(shù)組的順序表示二DATASTRUCTURE§4.1.2

數(shù)組的順序表示C/C++中申請(qǐng)二維數(shù)組的方法：introw=3,col=4;//方法1：=====================================intMtrx[row][col]={{1,2,3,4},{5,6,7,8},{9,10,11,12}};//方法2：=====================================int**ppMtrx=new

int*[row];for(inti=0;i<row;i++) ppMtrx[i]=new

int[col];intn=0;for(i=0;i<row;i++)

for(intj=0;j<col;j++) ppMtrx[i][j]=++n;for(i=0;i<row;i++)

delete[]ppMtrx[i];delete[]ppMtrx;申請(qǐng)指針數(shù)組再為指針數(shù)組申請(qǐng)空間為二維數(shù)組賦值刪除二維數(shù)組DATASTRUCTURE§4.1.2

數(shù)組的順序表示DATASTRUCTURE§4.1.2

數(shù)組的順序表示//方法3：=====================================#definerow3#definecol4typedefintMtrx[row];

main(){

intn=0;

Mtrx*pMtrx=newMtrx[col];//用法與二維數(shù)組相同

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

for(intj=0;j<col;j++) pMtrx[i][j]=++n;

delete[]pMtrx;}

定義二維數(shù)組將數(shù)組定義為數(shù)據(jù)類型DATASTRUCTURE§4.1.2

數(shù)組的順序表示/DATASTRUCTURE§4.1.2

數(shù)組的順序表示多維數(shù)組的順序表示推廣到多維數(shù)組a[m1][m2]…[mn]，數(shù)組元素a[i1][i2]…[in]的存儲(chǔ)地址為：

loc(a[i1][i2]…[in])=

loc(a[0]…[0])+(i1*m2*m3*…*mn+i2*m3*m4*…*mn+…+in-1*mn+in)*k

=DATASTRUCTURE§4.1.2

數(shù)組的順序表示多DATASTRUCTURE§4.1.3

一維數(shù)組的C++類用C++的模板類定義的一維數(shù)組抽象數(shù)據(jù)類型。公有成員函數(shù)包括：

構(gòu)造函數(shù)析構(gòu)函數(shù)重載下標(biāo)操作符：[]

重載下標(biāo)操作符用來(lái)返回指向第i個(gè)元素的引用

重載數(shù)組賦值：＝

賦值操作符實(shí)現(xiàn)數(shù)組的整體賦值。DATASTRUCTURE§4.1.3

一維數(shù)組的C++DATASTRUCTURE§4.1.3

一維數(shù)組的C++類#include<assert.h>template<classT>classArray1D{public:Array1D(intsz=0);~Array1D(){delete[]elements;}T&operator[](inti)const;Array1D<T>&operator=(constArray1D<T>&r);friendistream&operator>>(istream&in,Array1D<T>&r);friendostream&operator<< (ostream&out,constArray1D<T>&r);private:

intsize; T*elements;};取元素值整體賦值缺少拷貝構(gòu)造函數(shù)！DATASTRUCTURE§4.1.3

一維數(shù)組的C++DATASTRUCTURE§4.1.3

一維數(shù)組的C++類構(gòu)造函數(shù)，申請(qǐng)數(shù)組空間template<classT>Array1D<T>::Array1D(intsz){

assert(sz>=0);//越界檢查

size=sz; elements=newT[sz];}運(yùn)算符[]，獲取第i個(gè)元素template<classT>T&Array1D<T>::operator[](inti)const{

assert(i>=0&&i<size);//越界檢查

returnelements[i];}

DATASTRUCTURE§4.1.3

一維數(shù)組的C++DATASTRUCTURE§4.1.3

一維數(shù)組的C++類重載運(yùn)算符=

template<classT>Array1D<T>&Array1D<T>::operator=(constArray1D<T>&r)

//數(shù)組r整體賦值給this{

if(this!=&r){//防止自我賦值

size=r.size;

delete[]elements;//釋放原空間

elements=newT[size];//重新分配空間

for(inti=0;i<size;i++) elements[i]=r.elements[i];}

return*this;}DATASTRUCTURE§4.1.3

一維數(shù)組的C++DATASTRUCTURE§4.1.3

一維數(shù)組的C++類重載流運(yùn)算符>>和<<template<classT>istream&operator>>(istream&in,Array1D<T>&r){

cout<<"Intputarray\n";

for(inti=0;i<r.size;i++)in>>r.elements[i];

returnin;}template<classT>ostream&operator<<(ostream&out,constArray1D<T>&r){

cout<<"Array=";

for(inti=0;i<r.size;i++)out<<r.elements[i]<<''; out<<endl; returnout;}

DATASTRUCTURE§4.1.3

一維數(shù)組的C++DATASTRUCTUREmain中測(cè)試該類的效果#include"array1d.h"main(){Array1D<int>a(5),b(8); Array1D<int>c;//采用缺省長(zhǎng)度0

cin>>a;cout<<"a"<<a;

cin>>b;cout<<"b"<<b;

cout<<"c"<<c;

cout<<"a[0]="<<a[0]<<“;“<<"b[5]="<<b[5]<<endl;c=b;cout<<"c=b,c"<<c;b=a;cout<<"b=a,b"<<b;}§4.1.3

一維數(shù)組的C++類DATASTRUCTUREmain中測(cè)試該類的效果§4.1DATASTRUCTURE§1

C++中有關(guān)數(shù)組的類classArray{public: Array(intsize=0,char*ptr=NULL);

//defaultconstructor Array(constArray&);//copyconstructor ~Array();//destructor

char*getPtr()const{returnm_ptr;}

voidSetArray(intsize,char*ptr);private:

int*m_ptr;//pointertothe //firstelementofthearray.

intm_size;};DATASTRUCTURE§1

C++中有關(guān)數(shù)組的類cDATASTRUCTURE§1

C++中有關(guān)數(shù)組的類Array::Array(intsize,char*ptr/*=NULL*/){m_ptr=NULL; SetArray(size,ptr);}Array::Array(constArray&ar){SetArray(ar.m_size,ar.m_ptr);}Array::~Array(){if(m_ptr!=NULL)delete[]m_ptr;}voidArray::SetArray(intsize,char*ptr)

//有問(wèn)題的函數(shù)！{m_size=size;m_ptr=ptr;}淺拷貝！要改成深拷貝。DATASTRUCTURE§1

C++中有關(guān)數(shù)組的類ADATASTRUCTURE§1

C++中有關(guān)數(shù)組的類#include<iostream.h>#include<string.h>main(){

charstr[9]; strcpy(str,“Software”);

//注意：此處不能用char*str=”Software”;//因?yàn)檫@樣的字符串是只讀的。 Arrayar1(8,str); Arrayar2(ar1);

//調(diào)用拷貝構(gòu)造函數(shù)，其中調(diào)用了SetArray() str[0]=‘6’;//改變數(shù)組內(nèi)容

cout<<ar1.getPtr()<<“”;

cout<<ar2.getPtr()<<endl;}輸出：6oftware6oftware淺拷貝的后果。DATASTRUCTURE§1

C++中有關(guān)數(shù)組的類#DATASTRUCTURE§1

C++中有關(guān)數(shù)組的類voidArray::SetArray(intsize,char*ptr){

if(size==0||ptr==NULL)return;

if(m_ptr!=NULL)delete[]m_ptr;

//釋放原數(shù)組

m_size=size; m_ptr=new

char[size];//申請(qǐng)新的空間

strncpy(m_ptr,ptr,size);//拷貝}

輸出：Software6oftwareDATASTRUCTURE§1

C++中有關(guān)數(shù)組的類vDATASTRUCTURE第4章數(shù)組和字符串?dāng)?shù)組1特殊矩陣2稀疏矩陣3字符串4數(shù)組1特殊矩陣2DATASTRUCTURE第4章數(shù)組和字符串?dāng)?shù)組1特殊DATASTRUCTURE§4.2.1

對(duì)稱矩陣對(duì)稱矩陣和三角矩陣在n×n的矩陣A中，若aij=aji(0<i,j<n)，則稱其為n階對(duì)稱矩陣。對(duì)于對(duì)稱矩陣，可以只存儲(chǔ)上三角(或下三角)中的元素(包括對(duì)角線上的元素)。DATASTRUCTURE§4.2.1

對(duì)稱矩陣對(duì)稱矩陣DATASTRUCTURE§4.2.1

對(duì)稱矩陣如果采用二維數(shù)組，n維對(duì)稱矩陣的元素為n2。如果只存儲(chǔ)三角中元素，則元素個(gè)數(shù)為

n(n+1)/2其中行列序號(hào)與元素序號(hào)的對(duì)應(yīng)關(guān)系：0123…num-1a0,0a1,0a1,1a2,0…an-1,0…an-1,n-1DATASTRUCTURE§4.2.1

對(duì)稱矩陣如果采用DATASTRUCTURE第4章數(shù)組和字符串?dāng)?shù)組1特殊矩陣2稀疏矩陣3字符串4數(shù)組1特殊矩陣2稀疏矩陣3DATASTRUCTURE第4章數(shù)組和字符串?dāng)?shù)組1特殊DATASTRUCTURE§4.3.1

稀疏矩陣ADT稀疏矩陣大多數(shù)元素為零的矩陣稱為稀疏矩陣。對(duì)于稀疏矩陣可只存非零元素。DATASTRUCTURE§4.3.1

稀疏矩陣ADT稀DATASTRUCTURE§4.3.1

稀疏矩陣ADT稀疏矩陣ADT

ADTSparseMatrix{數(shù)據(jù)：絕大多數(shù)元素為零的矩陣。運(yùn)算：

Create():建立一個(gè)稀疏矩陣。

Destroy():撤消一個(gè)稀疏矩陣。

Add(B,C):當(dāng)前矩陣對(duì)象與B相加，C中返回相加和。

Mul(B,C):當(dāng)前矩陣對(duì)象與B相乘，C中返回相乘積。

Transpose(B):B中返回當(dāng)前矩陣對(duì)象的轉(zhuǎn)置矩陣。}

DATASTRUCTURE§4.3.1

稀疏矩陣ADT稀DATASTRUCTURE§4.3.1

稀疏矩陣ADT#include<iostream.h>template<classT>classSparseMatrix{public: SparseMatrix(intmaxRowSize,intmaxColSize){} ~SparseMatrix(){}

virtualvoidAdd(constSparseMatrix<T>&B,SparseMatrix<T>&C)const;

virtualvoidMul(constSparseMatrix<T>&B,SparseMatrix<T>&C)const;

virtualvoidTranspose(SparseMatrix<T>&B)const;private:

intmaxRows,maxCols;};稀疏矩陣的C++類DATASTRUCTURE§4.3.1

稀疏矩陣ADT#DATASTRUCTURE§4.3.2

稀疏矩陣的順序表示三元組表示法按照壓縮存儲(chǔ)的思想，稀疏矩陣Am

n中的每一個(gè)非零元素aij

的值、行號(hào)和列號(hào)可以用一個(gè)三元組（i,j,v）表示。三元組可以按行或按列的順序存儲(chǔ)。三元組的Term類template

<classT>structTerms{

introw,col;Tvalue;};DATASTRUCTURE§4.3.2

稀疏矩陣的順序表DATASTRUCTURE§4.3.2

稀疏矩陣的順序表示0016032205-16111212323-840916215DATASTRUCTURE§4.3.2

稀疏矩陣的順序表DATASTRUCTURE§4.3.2

稀疏矩陣的順序表示#include<iostream.h>template<classT>classSeqTriple{public: SeqTriple(intmSize); ~SeqTriple(){delete[]trip;};

voidAdd(constSeqTriple<T>&B,SeqTriple<T>&C)const;

voidMul(constSeqTriple<T>&B,SeqTriple<T>&C)const;

voidTranspose(SeqTriple<T>&B)const; friendistream&operator>>(istream&input, constSeqTriple<T>&); friendostream&operator<<(ostream&output,

constSeqTriple<T>&);private:

intmaxSize;//最大元素個(gè)數(shù)

intm,n,t;//行數(shù)、列數(shù)和非零元素個(gè)數(shù)

Term<T>*trip;//動(dòng)態(tài)一維數(shù)組的指針};行三元組表的C++類DATASTRUCTURE§4.3.2

稀疏矩陣的順序表DATASTRUCTURE第4章數(shù)組和字符串?dāng)?shù)組1特殊矩陣2稀疏矩陣3字符串4數(shù)組1特殊矩陣2稀疏矩陣3字符串4DATASTRUCTURE第4章數(shù)組和字符串?dāng)?shù)組1特殊DATASTRUCTURE§4.4.1

字符串ADT字符串的定義字符串(簡(jiǎn)稱為串)是由n(≥0)個(gè)字符組成的有限序列。S=“a0

a1…an-1”(n≥0)其中，S

是串名，單引號(hào)括起來(lái)的字符序列是串S的值。n是串中字符個(gè)數(shù)，又稱串長(zhǎng)度，n=0的串稱為空串。要注意區(qū)分空串和空白串。串中任意連續(xù)個(gè)字符組成的子序列稱為該串的子串，包含子串的串稱為主串。通常以子串的首字符在主串中的位置作為子串在主串中的位置。

S=“abcabcaabcbcde”

P=“aabc”DATASTRUCTURE§4.4.1

字符串ADT字符DATASTRUCTURE§4.4.1

字符串ADT字符串ADTADTString{數(shù)據(jù)：字符串是由n(≥0)個(gè)字符組成的有限序列

S

=

“a0a1…an-1”，0

≤

i

<n。運(yùn)算：

Create():建立一個(gè)空串。Destroy():撤消一個(gè)串。Length():返回當(dāng)前串對(duì)象的長(zhǎng)度。Clear():置為空串。

Assign(S):串S的值賦給當(dāng)前串對(duì)象。

Concat(b):將串b連接在當(dāng)前串對(duì)象之后。DATASTRUCTURE§4.4.1

字符串ADT字符DATASTRUCTURE§4.4.1

字符串ADTInsert(P,i):將串P插在當(dāng)前串對(duì)象的位置i處。

Delete(i,len):從當(dāng)前串對(duì)象的位置i起刪除len個(gè)字符。

Substr(i,len):返回當(dāng)前串對(duì)象中，從位置i開始的len個(gè)字符組成的子串。Find(i,P):返回子串P在當(dāng)前串對(duì)象中的位置。若當(dāng)前串對(duì)象不包含串P，則返回-1。}DATASTRUCTURE§4.4.1

字符串ADTDA