C++數(shù)據(jù)結(jié)構(gòu)課件

什麼是數(shù)據(jù)結(jié)構(gòu)抽象數(shù)據(jù)類型及面向?qū)ο蟾拍顢?shù)據(jù)結(jié)構(gòu)的抽象層次用C++描述面向?qū)ο蟪淌窖菟惴ǘx範(fàn)本性能分析與度量第一章緒論

“選課單”包含如下資訊

學(xué)號課程編號成績時(shí)間

學(xué)生選課系統(tǒng)中實(shí)體構(gòu)成的網(wǎng)狀關(guān)係學(xué)生(學(xué)號,姓名,性別,籍貫)課程(課程號,課程名,學(xué)分)選課(學(xué)號,課程號,成績)UNIX檔系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖/(root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp數(shù)據(jù)（data）數(shù)據(jù)是資訊的載體，是描述客觀事物的數(shù)、字元、以及所有能輸入到電腦中，被電腦程式識別和處理的符號的集合。數(shù)值性數(shù)據(jù)非數(shù)值性數(shù)據(jù)數(shù)據(jù)對象

(dataobject)數(shù)據(jù)的子集。具有相同性質(zhì)的數(shù)據(jù)成員（數(shù)據(jù)元素）的集合。整數(shù)數(shù)據(jù)對象

N={0,1,2,…}學(xué)生數(shù)據(jù)對象什麼是數(shù)據(jù)結(jié)構(gòu)定義:

由某一數(shù)據(jù)對象及該對象中所有數(shù)據(jù)成員之間的關(guān)係組成。記為：

Data_Structure={D,R}

其中，D是某一數(shù)據(jù)對象，R是該對象中所有數(shù)據(jù)成員之間的關(guān)係的有限集合。N個(gè)網(wǎng)點(diǎn)之間的連通關(guān)係

樹形關(guān)係網(wǎng)狀關(guān)係152436152436抽象數(shù)據(jù)類型及面向?qū)ο蟾拍顢?shù)據(jù)類型

定義：一組性質(zhì)相同的值的集合,以及定義於這個(gè)值集合上的一組操作的總稱.C語言中的數(shù)據(jù)類型

charintfloatdoublevoid

字元型整型浮點(diǎn)型雙精度型無值

抽象數(shù)據(jù)類型

(ADTs:AbstractDataTypes)由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型由基本的數(shù)據(jù)類型組成,並包括一組相關(guān)的服務(wù)（或稱操作）資訊隱蔽和數(shù)據(jù)封裝，使用與實(shí)現(xiàn)相分離抽象數(shù)據(jù)類型查找登錄刪除修改

符號表自然數(shù)的抽象數(shù)據(jù)類型定義ADT

NaturalNumberisobjects:一個(gè)整數(shù)的有序子集合,它開始於0,

結(jié)束於機(jī)器能表示的最大整數(shù)(MaxInt)。Function:

對於所有的x,

y

NaturalNumber;

False,True

Boolean,+、-、<、==、=等都是可用的服務(wù)。

Zero():NaturalNumber

返回自然數(shù)0IsZero(x):if(x==0)返回True

Booleanelse返回FalseAdd(x,y):if(x+y<=MaxInt)返回x+y

NaturalNumber

else返回MaxIntSubtract(x,y):if(x<y)返回0

NaturalNumberelse返回x-yEqual(x,y):if(x==y)返回True

Booleanelse返回FalseSuccessor(x):if(x==MaxInt)返回xNaturalNumberelse返回x+1end

NaturalNumber面向?qū)ο蟮母拍蠲嫦驅(qū)ο?對象＋類＋繼承＋通信對象在應(yīng)用問題中出現(xiàn)的各種實(shí)體、事件、規(guī)格說明等由一組屬性值和在這組值上的一組服務(wù)（或稱操作）構(gòu)成類(class)，實(shí)例(instance)

具有相同屬性和服務(wù)的對象歸於同一類，形成類類中的對象為該類的實(shí)例屬性aPoint1aPoint2aPoint3aPoint4服務(wù)Draw()move(x,y)contains(aPoint)屬性值屬性值quadrilateral1quadrilateral2(35,10)(50,10)(35,25)(50,25)(45,65)(50,45)(65,66)(60,70)Draw()move(x,y)contains(aPoint)Draw()move(x,y)contains(aPoint)服務(wù)服務(wù)四邊形類及其對象quadrilateral繼承

派生類：四邊形，三角形，…

子類特化類(特殊化類)

基類：多邊形

父類泛化類(一般化類)通信

消息傳遞Draw()move(x,y)contains(aPoint)PolygonreferencePointVerticesPolygon類referencePointVerticesDraw()move(

x,y)contains(aPoint)Polygon的子類Quadrilateral類Quadrilateral線性結(jié)構(gòu)直接存取類數(shù)組,檔順序存取類表,棧,佇列,優(yōu)先佇列

廣義索引類線性索引,搜索樹非線性結(jié)構(gòu)層次結(jié)構(gòu)類樹，二叉樹，堆群結(jié)構(gòu)類集合，圖數(shù)據(jù)結(jié)構(gòu)的抽象層次線性結(jié)構(gòu)樹形結(jié)構(gòu)樹二叉樹二叉搜索樹1413121123456789103158710119987456623131bindevetclibuser1堆結(jié)構(gòu)

“最大”堆“最小”堆123548711102916410121151236987群聚類圖結(jié)構(gòu)網(wǎng)路結(jié)構(gòu)12564312543611331814665161921數(shù)據(jù)的兩個(gè)視圖數(shù)據(jù)的邏輯結(jié)構(gòu)面向應(yīng)用數(shù)據(jù)的物理結(jié)構(gòu)面向存儲

順序結(jié)構(gòu)鏈表結(jié)構(gòu)散列結(jié)構(gòu)索引結(jié)構(gòu)在該數(shù)據(jù)結(jié)構(gòu)上的操作為什麼選用面向?qū)ο蠹癈++語言講述數(shù)據(jù)結(jié)構(gòu)？PASCAL與C描述是面向過程的。C++描述兼有面向過程與面向?qū)ο蟮奶攸c(diǎn)。Java描述是面向?qū)ο蟮摹Ｓ妹嫦驅(qū)ο蠹癈++描述與國際接軌，是市場需要。用C++描述面向?qū)ο蟪淌紺++的函數(shù)特徵C++的數(shù)據(jù)聲明C++的作用域C++的類C++的對象C++的輸入/輸出C++的函數(shù)C++的參數(shù)傳遞C++的函數(shù)名重載和操作符重載C++的動態(tài)存儲分配友元(friend)函數(shù)內(nèi)聯(lián)(inline)函數(shù)結(jié)構(gòu)(struct)與類聯(lián)合(Union)與類演算法定義定義：一個(gè)有窮的指令集，這些指令為解決某一特定任務(wù)規(guī)定了一個(gè)運(yùn)算序列特性：輸入

有0個(gè)或多個(gè)輸入輸出

有一個(gè)或多個(gè)輸出(處理結(jié)果)

確定性

每步定義都是確切、無歧義的有窮性

演算法應(yīng)在執(zhí)行有窮步後結(jié)束有效性

每一條運(yùn)算應(yīng)足夠基本事例學(xué)習(xí)：選擇排序問題明確問題：遞增排序解決方案：逐個(gè)選擇最小數(shù)據(jù)演算法框架：

for(inti=0;i<n-1;i++){//n-1趟 從a[i]檢查到a[n-1];

若最小整數(shù)在a[k],交換a[i]與a[k];}細(xì)化程式：程式SelectSort

演算法設(shè)計(jì)

自頂向下，逐步求精

voidselectSort(inta[],constintn){

//對n個(gè)整數(shù)a[0],a[1],…,a[n-1]按遞增順序排序

for(inti=0;i<n-1;i++){

intk=i;

//從a[i]查到a[n-1],找最小整數(shù),在a[k]

for(intj=i+1;j<n;j++)

if(a[j]<a[k])k=j;

inttemp=a[i];a[i]=a[k];a[k]=temp;}}

範(fàn)本

(template)定義

適合多種數(shù)據(jù)類型的類定義或演算法，在特定環(huán)境下通過簡單地代換，變成針對具體某種數(shù)據(jù)類型的類定義或演算法用範(fàn)本定義用於排序的數(shù)據(jù)表類#include<iostream.h>template<classType> classdataList{ private:Type*Element; intArraySize; voidSwap(intm1,intm2);intMaxKey

(intlow,inthigh);

public:dataList

(intsize=10):ArraySize(size),Element(new

Type[Size]){}~dataList(){delete[]Element;} voidSort(); friendostream&operator<<(ostream&

outStream,datalist<Type>&outList);friendistream&operator>>(istream&

inStream,datalist<Type>&inList);}類中所有操作作為範(fàn)本函數(shù)的實(shí)現(xiàn)#include“datalist.h”template<classType>voiddataList

<Type>::Swap

(intm1,intm2){

//交換由m1,m2為下標(biāo)的數(shù)組元素的值

Typetemp=Element

[m1];

Element

[m1]=Element

[m2];

Element[m2]=temp;}template<classType>intdataList<Type>::

MaxKey

(intlow,inthigh){

//查找數(shù)組Element[low]到Element[high]//中的最大值，函數(shù)返回其位置

intmax=low; for(intk=low+1,k<=high,k++) if(Element[max]<Element[k]) max=k; returnmax;}template<classType>ostream&operator<<(ostream&OutStream,

dataList<Type>OutList){OutStream<<“數(shù)組內(nèi)容

:\n”;for(inti=0;i<OutList.ArraySize;i++)

OutStream<<OutList.Element[i]<<‘’;

OutStream<<endl;

OuStream<<“數(shù)組當(dāng)前大小

:”<<

OutList.ArraySize<<endl;returnOutStream;}

template<classType>istream&

operator>>(istream&InStream,

dataList<Type>InList){

cout<<“錄入數(shù)組當(dāng)前大小

:”;

Instream>>InList.ArraySize; cout<<“錄入數(shù)組元素值

:\n”; for(inti=0;i<InList.ArraySize;i++){

cout

<<“元素”<<i<<“:”;

InStream>>InList.Element[i];}returnInStream;}

template<classType>voiddataList<Type>::Sort(){

//按非遞減順序?qū)rraySize個(gè)關(guān)鍵碼

//Element[0]到Element[ArraySize-1]排序

for(inti=ArraySize-1;i>0;i--){intj=MaxKey(0,i);if(j!=i)swap(j,i);}}使用範(fàn)本的選擇排序演算法的主函數(shù)

#include“selecttm.h”constintSIZE=10;intmain(){dataList<int>TestList(SIZE);

cin>>TestList;

cout<<TestList<<endl;TestList.Sort();

cout<<TestList<<endl;

return0;}

性能分析與度量演算法的性能標(biāo)準(zhǔn)演算法的後期測試演算法的事前估計(jì)演算法的性能標(biāo)準(zhǔn)正確性可使用性可讀性效率健壯性演算法的後期測試在演算法中的某些部位插裝時(shí)間函數(shù)

time

()測定演算法完成某一功能所花費(fèi)時(shí)間順序搜索

(SequenialSearch)intseqsearch(inta[],intn,intx){//在a[0],…,a[n-1]中搜索x

inti=0;

while(i<n&&a[i]!=x)

i++;

if(i==n)return

-1;

returni;}

插裝time()

的計(jì)時(shí)程式

doublestart,stop;time(&start);

intk=seqsearch(a,n,x);time(&stop);

doublerunTime=stop-start;

cout<<""<<n<<""<< runTime<<endl;演算法的事前估計(jì)

空間複雜度時(shí)間複雜度空間複雜度度量存儲空間的固定部分

程式指令代碼的空間，常數(shù)、簡單變數(shù)、定長成分(如數(shù)組元素、結(jié)構(gòu)成分、對象的數(shù)據(jù)成員等)變數(shù)所占空間可變部分

尺寸與實(shí)例特性有關(guān)的成分變數(shù)所占空間、引用變數(shù)所占空間、遞歸棧所用空間、通過new和delete命令動態(tài)使用空間時(shí)間複雜度度量編譯時(shí)間運(yùn)行時(shí)間程式步語法上或語義上有意義的一段指令序列執(zhí)行時(shí)間與實(shí)例特性無關(guān)例如：聲明語句：程式步數(shù)為0;運(yùn)算式：程式步數(shù)為1

程式步確定方法

插入計(jì)數(shù)全局變數(shù)count

建表，列出個(gè)語句的程式步例以迭代方式求累加和的函數(shù)floatsum(floata[],intn){

floats=0.0;

for(inti=0;i<n;i++)s+=a[i];

returns;}在求累加和程式中加入count語句floatsum(floata[],intn

){

float

s=0.0;count++; //count統(tǒng)計(jì)執(zhí)行語句條數(shù)

for(inti=0;i<n;i++){count++; //針對for語句

s+=a[i]; count++;} //針對賦值語句

count++; //針對for的最後一次

count++; //針對return語句

returns;}

執(zhí)行結(jié)束得程式步數(shù)count=2*n+3程式的簡化形式

voidsum(floata[],intn){for(inti=0;i<n;i++)count+=2;count+=3;}注意：

一個(gè)語句本身的程式步數(shù)可能不等於該語句一次執(zhí)行所具有的程式步數(shù)。

例如：賦值語句x=sum(R,n)

本身的程式步數(shù)為1；

一次執(zhí)行對函數(shù)sum(R,n)

的調(diào)用需要的程式步數(shù)為2*n+3；

一次執(zhí)行的程式步數(shù)為

1+2*n+3=2*n+4計(jì)算累加和程式

程式步數(shù)計(jì)算工作表格時(shí)間複雜度的漸進(jìn)表示法大O表示法加法規(guī)則針對並列程式段

T(n,m)=T1(n)+T2(m) =O(max(f(n),g(m)))

c<log2n<n<nlog2n<n2<n3<2n<3n<n!乘法規(guī)則針對嵌套程式段

T(n,m)=T1(n)*T2(m)

=O(f(n)*g(m))

漸進(jìn)的空間複雜度

S(n)=O(f(n))兩個(gè)並列迴圈的例子

voidexam(floatx[][],intm,intn){floatsum[];for(inti=0;i<m;i++){//x中各行

sum[i]=0.0;//數(shù)據(jù)累加

for(intj=0;j<n;j++) sum[i]+=x[i][j];

}

for(i=0;i<m;i++)//列印各行數(shù)據(jù)和

cout<<i<<“:”<<sum[i]<<endl;}

漸進(jìn)時(shí)間複雜度為O(max(m*n,m))

template<classType>//起泡排序

voiddataList<Type>::bubbleSort(){

//對表逐趟比較,ArraySize是表當(dāng)前長度

inti=1;

intexchange=1;

//當(dāng)exchange為0則停止排序

while(i<ArraySize&&exchange){

BubbleExchange(i,exchange);

i++;

} //一趟比較

}

template<classType>voiddataList<Type>::BubbleExchange(inti,int&exchange){exchange=0; //假定元素未交換

for(intj=ArraySize-1;j>=i;j--)

if(Element[j-1]>Element[j]){ Swap(j-1,j); //發(fā)生逆序,交換

exchange=1; //做“發(fā)生交換”標(biāo)誌

}}作為抽象數(shù)據(jù)類型的數(shù)組一維數(shù)組一維數(shù)組的示例352749186054778341020123456789一維數(shù)組的特點(diǎn)連續(xù)存儲的線性表（別名向量）數(shù)組的定義和初始化#include<iostream.h>classszcl{inte; public:

szcl(){e=0;}

szcl(intvalue){e=value;} intget_value(){returne;} }main(){szcla1[3]={3,5,7},*elem;

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

cout<<a1[i].get_value()<<“\n”;//靜態(tài)

elem=a1;

for(inti=0;i<3;i++){

cout<<elem->get_value()<<“\n”;//動態(tài)

elem++;

}

return0;}

一維數(shù)組(Array)類的定義

#include<iostream.h>#include<stdlib.h>template<classType>class

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

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

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

public:Array(intSize=DefaultSize);

Array(constArray<Type>&x);

~Array(){delete[]elements;} Array<Type>

&

operator=//數(shù)組複製

(constArray<Type>

&A);Type&operator[](inti); //取元素值

intLength()const{returnArraySize;}

//取數(shù)組長度

voidReSize(intsz); //擴(kuò)充數(shù)組

}

template<classType>voidArray<Type>::getArray(){

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

elements=newType[ArraySize];if(elements==NULL){

arraySize=0;cerr<<“存儲分配錯！"<<

endl;return;}一維數(shù)組公共操作的實(shí)現(xiàn)

template<classType>

Array<Type>::Array(intsz){

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

if(sz<=0){

arraySize=0;cerr<<“非法數(shù)組大小”

<<endl;return;}

ArraySize=sz;getArray();

}

template<classType>Array<Type>::

Array(Array<Type>

&x){//複製構(gòu)造函數(shù)

intn=ArraySize=x.ArraySize;

elements=newType[n]; if(elements==NULL){

arraySize=0;cerr<<“存儲分配錯”

<<endl;return;}

Type*srcptr=x.elements;

Type*destptr=elements;

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

//按數(shù)組名及下標(biāo)

i，取數(shù)組元素的值

if(i<0||i>ArraySize-1){

cerr<<“數(shù)組下標(biāo)超界”

<<endl;returnNULL;}

returnelement[i]; }

使用該函數(shù)於賦值語句

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

template<classType>voidArray<Type>::Resize(intsz){if(sz>=0&&sz!=ArraySize){Type*newarray=newType[sz];

//創(chuàng)建新數(shù)組

if(newarray==NULL){

cerr<<“存儲分配錯”

<<endl;return;}intn=(sz<=ArraySize)?sz:ArraySize;

//按新的大小確定傳送元素個(gè)數(shù)

Type*srcptr=elements;//源數(shù)組指針

Type*destptr=newarray;//目標(biāo)數(shù)組指針

while(n--)*destptr++=*srcptr++;

//從源數(shù)組向目標(biāo)數(shù)組傳送

delete[]

elements; elements=newarray;

ArraySize=sz; }}

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

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

j

列向量下標(biāo)

k數(shù)組的連續(xù)存儲方式一維數(shù)組352749186054778341020123456789llllllllll

LOC(i)=LOC(i-1)+l=a+i*lLOC(i)=

LOC(i-1)+l=a+i*l,i>0

a,i=0

a+i*la

二維數(shù)組行優(yōu)先

LOC

(j,k)==a+(j*m+k)*l

三維數(shù)組

各維元素個(gè)數(shù)為

m1,m2,m3

下標(biāo)為i1,i2,i3的數(shù)組元素的存儲地址：

（按頁/行/列存放）

LOC(i1,i2,i3)=a+(i1*m2*m3+i2*m3+i3

)*l

前i1頁總元素個(gè)數(shù)第i1頁的前i2行總元素個(gè)數(shù)

n維數(shù)組

各維元素個(gè)數(shù)為

m1,m2,m3,…,mn

下標(biāo)為i1,i2,i3,…,in

的數(shù)組元素的存儲地址：

LOC(i1,i2,…,in)=a+(i1*m2*m3*…*mn+i2*m3*m4*…*mn++……+in-1*mn+in

)*l

線性表(LinearList)線性表的定義和特點(diǎn)

定義

n（0）個(gè)數(shù)據(jù)元素的有限序列，記作

（a1,a2,…,an）

ai是表中數(shù)據(jù)元素，n是表長度。

遍曆逐項(xiàng)訪問：

從前向後從後向前線性表的特點(diǎn)除第一個(gè)元素外，其他每一個(gè)元素有一個(gè)且僅有一個(gè)直接前驅(qū)。除最後一個(gè)元素外，其他每一個(gè)元素有一個(gè)且僅有一個(gè)直接後繼。順序表(SequentialList)順序表的定義和特點(diǎn)

定義將線性表中的元素相繼存放在一個(gè)連續(xù)的存儲空間中?？衫靡痪S數(shù)組描述存儲結(jié)構(gòu)特點(diǎn)

線性表的順序存儲方式

遍曆順序訪問

253457164809

012345data順序表(SeqList)類的定義template<classType> classSeqList{Type*data;//順序表存儲數(shù)組

intMaxSize; //最大允許長度

intlast; //當(dāng)前最後元素下標(biāo)public: SeqList(intMaxSize=defaultSize); ~SeqList(){delete[]data;}

intLength()const

{returnlast+1;

}

intFind(Type&x)const;//查找

intLocate(inti)const; //定位

intInsert(Type&x,inti);//插入

intRemove(Type

&x); //刪除

intNext(Type

&x); //後繼

intPrior(Type

&x);//前驅(qū)

intIsEmpty(){returnlast==-1;

} intIsFull(){returnlast==MaxSize-1;

}TypeGet(inti){//提取

returni<0||i>last？NULL:data[i];}}

順序表部分公共操作的實(shí)現(xiàn)

template<classType>

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

SeqList<Type>::SeqList(intsz){if(sz>0){ MaxSize=sz;last=-1; data=newType[MaxSize];

if(data==NULL){MaxSize=0;last=-1;return;}

}}template<classType> intSeqList<Type>::Find(Type

&x)const{

//搜索函數(shù)：在表中從前向後順序查找

x

inti=0;

while(i<=last&&data[i]!=x)i++;

if(i>last)return

-1;

elsereturni; }順序搜索圖示253457164809

012345data搜索

16i253457164809

i253457164809

i253457164809

i搜索成功2534571648

01234data搜索50i2534571648

i2534571648

i2534571648

i2534571648

i搜索失敗搜索成功

若搜索概率相等，則

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

次表項(xiàng)的插入25345716480963

01234567data50插入x2534575016480963

01234567data50itemplate<classType>intSeqList<Type>::Insert(Type&x,inti){//在表中第

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;//插入成功

}}表項(xiàng)的刪除2534575016480963

01234567data16刪除

x25345750480963

01234567data

template<classType>intSeqList<Type>::Remove(Type&x){

//在表中刪除已有元素

x

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

x

if(i>=0){ last--

;

for(intj=i;j<=last;j++)data[j]=data[j+1];

return1; //成功刪除

} return0;//表中沒有

x}順序表的應(yīng)用：集合的“並”運(yùn)算voidUnion(SeqList<int>

&A,SeqList<int>

&B){

intn=A.Length();

intm=B.Length();

for(inti=1;i<=m;i++){ intx=B.Get(i);//在B中取一元素

intk=A.Find(x);//在A中搜索它

if(k==

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

{A.Insert(n,x);n++;}}}voidIntersection(SeqList<int>

&A,SeqList<int>

&B){

intn=A.Length();

intm=B.Length();inti=0;

while(i<n){intx=A.Get(i);//在A中取一元素

intk=B.Find(x);//在B中搜索它

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

}}順序表的應(yīng)用：集合的“交”運(yùn)算稀疏矩陣

(SparseMatrix)非零元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)少於矩陣元素個(gè)數(shù)稀疏矩陣的抽象數(shù)據(jù)類型template<classType>classSparseMatrix;template<classType>classTrituple{ //三元組friendclassSparseMatrix<Type>private:

introw,col; //非零元素行號/列號

Typevalue;//非零元素的值}

template<classType>classSparseMatrix{//稀疏矩陣類定義

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

Trituple<Type>smArray[MaxTerms];

public://三元組表

SparseMatrix(intMaxRow,intMaxcol);

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

SparseMatrix<Type>&Add(SparseMatrix

<Type>a,SparseMatrix<Type>b);//相加

SparseMatrix<Type>&Multiply(SparseMatrix

<Type>a,SparseMatrix<Type>b);//相乘}

稀疏矩陣轉(zhuǎn)置矩陣用三元組表表示的稀疏矩陣及其轉(zhuǎn)置稀疏矩陣轉(zhuǎn)置演算法思想設(shè)矩陣列數(shù)為Cols，對矩陣三元組表掃描Cols次。第k次檢測列號為k的項(xiàng)。第k次掃描找尋所有列號為k

的項(xiàng)，將其行號變列號、列號變行號，順次存於轉(zhuǎn)置矩陣三元組表。稀疏矩陣的轉(zhuǎn)置

template<classType>SparseMatrix<Type>&SparseMatrix<Type>::Transpose(SparseMatrix<Type>&a){SparseMatrix<Type>b(a.Cols,a.Rows);b.Rows=a.Cols;b.Cols=a.Rows;

b.Terms=a.Terms;

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

if(a.Terms>0){

intCurrentB=0;

//轉(zhuǎn)置三元組表存放指針

for(int

k=0;k<a.Cols;k++)

//對所有列號處理一遍

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

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

b.smArray[CurrentB].col=a.smArray[i].row;

b.smArray[CurrentB].value=a.smArray[i].value;

CurrentB++;

}

}

returnb;}快速轉(zhuǎn)置演算法建立輔助數(shù)組rowSize和rowStart，記錄矩陣轉(zhuǎn)置後各行非零元素個(gè)數(shù)和各行元素在轉(zhuǎn)置三元組表中開始存放位置。掃描矩陣三元組表，根據(jù)某項(xiàng)的列號，確定它轉(zhuǎn)置後的行號，查rowStart表，按查到的位置直接將該項(xiàng)存入轉(zhuǎn)置三元組表中。

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

int*rowSize=newint[a.Cols];

int*rowStart=newint[a.Cols];SparseMatrix<Type>b(a.Cols,a.Rows);b.Rows=a.Cols;b.Cols=a.Rows;

b.Terms=a.Terms;if(a.Terms>0){for(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<a.Cols;i++) rowStart[i]=rowStart[i-1]+rowSize[i-1]; for(i=0;i<a.Terms;i++){ intj=rowStart[a.smArray[i].col]; b.smArray[j].row=a.smArray[i].col; b.smArray[j].col=a.smArray[i].row; b.smArray[j].value=a.smArray[i].value; rowStart[a.smArray[i].col]++;

}}

delete[]rowSize;

delete[]rowStart;

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

其中，S是串名字

“c1c2c3…cn”是串值

ci是串中字元

n是串的長度。例如,S=“TsinghuaUniversity”

constintmaxLen=128;

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

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

public:String(constString&ob);String(constchar*init);String(

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

字串抽象數(shù)據(jù)類型和類定義

intLength()const{

returncurLen;}

//求當(dāng)前串*this的實(shí)際長度

String&operator()(intpos,intlen);

//取*this從pos開始len個(gè)字元組成的子串

intoperator==(constString&ob){returnstrcmp(ch,ob.ch)==0;}

//判當(dāng)前串*this與對象串ob是否相等

intoperator!=(constString&ob)const{returnstrcmp(ch,ob.ch)!=0;}

//判當(dāng)前串*this與對象串ob是否不等

intoperator!()

const

{returncurLen==0;}

//判當(dāng)前串*this是否空串

String&operator=(String&ob);

//將串ob賦給當(dāng)前串*thisString&operator+=(String&ob);

//將串ob連接到當(dāng)前串*this之後

char&operator[](inti);

//取當(dāng)前串*this的第i個(gè)字元

intFind(String&pat)const;}

String::String(constString&ob){

//複製構(gòu)造函數(shù)：從已有串ob複製

ch=newchar[maxLen+1];//創(chuàng)建串?dāng)?shù)組

if(ch==NULL){

cerr<<“存儲分配錯!

\n”;

exit(1);

}curLen=ob.curLen;//複製串長度

strcpy(ch,ob.ch);//複製串值

}

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

char*init){//複製構(gòu)造函數(shù):從已有字元數(shù)組*init複製

ch=newchar[maxLen+1];//創(chuàng)建串?dāng)?shù)組

if(ch==NULL){cerr<<“存儲分配錯!

\n”;

exit(1);

}curLen=strlen(init);

//複製串長度

strcpy(ch,init);

//複製串值

}String::String(

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

ch=newchar[maxLen+1];//創(chuàng)建串?dāng)?shù)組

if(ch==NULL){

cerr<<“存儲分配錯!\n”;

exit(1);}curLen=0;ch[0]=‘\0’;}提取子串的演算法示例pos+len-1 pos+len-1

curLen-1

curLeninfinityinfinitypos=2,len=3pos=5,len=4finity超出String&String::operator()(intpos,intlen){//從串中第

pos個(gè)位置起連續(xù)提取

len個(gè)字元//形成子串返回

String*temp=newString;//動態(tài)分配

if(pos<0||pos+len-1>=maxLen||len<0){

temp->curLen=0;

//返回空串

temp->ch[0]='\0';

}

else{//提取子串

if(pos+len-1>=curLen)len=curLen-pos;

temp->curLen=len;//子串長度

for(inti=0,j=pos;i<len;i++,j++) temp->ch[i]=ch[j];//傳送串?dāng)?shù)組

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

}

return*temp;}

例：串

st=“university”,

pos=3,len=4使用示例

subSt=st(3,4)提取子串subSt=“vers”String&String::operator=(String&ob){//串賦值：從已有串ob複製

if(&ob!=this){

delete[]ch; ch=new

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

if(ch==NULL)

{cerr<<“記憶體不足!\n”;

exit(1);}curLen=ob.curLen;//串複製

strcpy(ch,ob.ch);

}elsecout<<“字串自身賦值出錯!\n”;

return*this;}char&String::operator[](inti){//按串名提取串中第i個(gè)字元

if(i<0&&i>=curLen

){cout<<“串下標(biāo)超界!\n”;

exit(1);}returnch[i];}例：串

st=“university”,使用示例

newSt=st；newChar=st[1];數(shù)組賦值newSt=“university”提取字元

newChar=

‘n’String&String::operator+=(String&ob){//串連接

char*temp=ch;//暫存原串?dāng)?shù)組

curLen+=ob.curLen;//串長度累加

ch=new

char[maxLen+1];

if(ch==NULL){cerr<<“存儲分配錯!\n”;

exit(1);}strcpy(ch,temp);

//拷貝原串?dāng)?shù)組

strcat(ch,ob.ch);

//連接ob串?dāng)?shù)組

delete[]temp;return

*this;

}例：串st1=“beijing”,st2=“university”,使用示例

st1+=st2;連接結(jié)果st1=“beijinguniversity”st2=“university”串的模式匹配定義在串中尋找子串（第一個(gè)字元）在串中的位置辭彙在模式匹配中，子串稱為模式，串稱為目標(biāo)。示例

目標(biāo)T:“Beijing”

模式P:“jin”

匹配結(jié)果=3

第1趟

T abbaba窮舉的模式

P aba

匹配過程

第2趟

T abbaba P

aba

第3趟

T abbaba P

aba

第4趟

T abba

ba Pa

ba

單鏈表(SinglyLinkedList)特點(diǎn)

每個(gè)元素(表項(xiàng))由結(jié)點(diǎn)(Node)構(gòu)成。線性結(jié)構(gòu)

結(jié)點(diǎn)可以不連續(xù)存儲表可擴(kuò)充datalinka0a1a2a3a4

first單鏈表的存儲映像free(a)可利用存儲空間a0a2a1a3

freefirst(b)經(jīng)過一段運(yùn)行後的單鏈表結(jié)構(gòu)單鏈表的類定義多個(gè)類表