




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
第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
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024年中國(guó)餐具洗滌用品研究報(bào)告
- 2025年度快遞業(yè)務(wù)客戶關(guān)系管理承包合同
- 2025年度綠色環(huán)保產(chǎn)業(yè)承包經(jīng)營(yíng)合同范本
- 2025年度電梯安全評(píng)估與整改服務(wù)合同
- 2025年度電子商務(wù)行業(yè)區(qū)塊鏈技術(shù)應(yīng)用合同
- 班級(jí)志愿者活動(dòng)計(jì)劃
- 團(tuán)隊(duì)激勵(lì)機(jī)制的設(shè)計(jì)計(jì)劃
- 促進(jìn)員工團(tuán)隊(duì)意識(shí)的措施計(jì)劃
- 理論學(xué)習(xí)與實(shí)踐應(yīng)用的結(jié)合計(jì)劃
- 績(jī)效考核體系年度優(yōu)化計(jì)劃
- 《教育強(qiáng)國(guó)建設(shè)規(guī)劃綱要(2024-2035年)》全文
- 中國(guó)服裝零售行業(yè)發(fā)展環(huán)境、市場(chǎng)運(yùn)行格局及前景研究報(bào)告-智研咨詢(2025版)
- 臨床提高膿毒性休克患者1h集束化措施落實(shí)率PDCA品管圈
- DB53∕T 1269-2024 改性磷石膏用于礦山廢棄地生態(tài)修復(fù)回填技術(shù)規(guī)范
- 2024-2025學(xué)年全國(guó)中學(xué)生天文知識(shí)競(jìng)賽考試題庫(kù)(含答案)
- JBT 14727-2023 滾動(dòng)軸承 零件黑色氧化處理 技術(shù)規(guī)范 (正式版)
- 思維第一:全面提升學(xué)習(xí)力
- 蒸汽吹掃吹管系數(shù)計(jì)算
- 公共資源交易中心管理辦法
- 中餐烹飪技術(shù)
- 與領(lǐng)導(dǎo)班子談心談話
評(píng)論
0/150
提交評(píng)論