C++数据结构课件

什麼是數據結構抽象數據類型及面向對象概念數據結構的抽象層次用C++描述面向對象程式演算法定義範本性能分析與度量第一章緒論

“選課單”包含如下資訊

學號課程編號成績時間

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

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

N={0,1,2,…}學生數據對象什麼是數據結構定義:

由某一數據對象及該對象中所有數據成員之間的關係組成。記為：

Data_Structure={D,R}

其中，D是某一數據對象，R是該對象中所有數據成員之間的關係的有限集合。N個網點之間的連通關係

樹形關係網狀關係152436152436抽象數據類型及面向對象概念數據類型

定義：一組性質相同的值的集合,以及定義於這個值集合上的一組操作的總稱.C語言中的數據類型

charintfloatdoublevoid

字元型整型浮點型雙精度型無值

抽象數據類型

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

符號表自然數的抽象數據類型定義ADT

NaturalNumberisobjects:一個整數的有序子集合,它開始於0,

結束於機器能表示的最大整數(MaxInt)。Function:

對於所有的x,

y

NaturalNumber;

False,True

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

Zero():NaturalNumber

返回自然數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面向對象的概念面向對象=對象＋類＋繼承＋通信對象在應用問題中出現的各種實體、事件、規格說明等由一組屬性值和在這組值上的一組服務（或稱操作）構成類(class)，實例(instance)

具有相同屬性和服務的對象歸於同一類，形成類類中的對象為該類的實例屬性aPoint1aPoint2aPoint3aPoint4服務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)服務服務四邊形類及其對象quadrilateral繼承

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

子類特化類(特殊化類)

基類：多邊形

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

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

x,y)contains(aPoint)Polygon的子類Quadrilateral類Quadrilateral線性結構直接存取類數組,檔順序存取類表,棧,佇列,優先佇列

廣義索引類線性索引,搜索樹非線性結構層次結構類樹，二叉樹，堆群結構類集合，圖數據結構的抽象層次線性結構樹形結構樹二叉樹二叉搜索樹1413121123456789103158710119987456623131bindevetclibuser1堆結構

“最大”堆“最小”堆123548711102916410121151236987群聚類圖結構網路結構12564312543611331814665161921數據的兩個視圖數據的邏輯結構面向應用數據的物理結構面向存儲

順序結構鏈表結構散列結構索引結構在該數據結構上的操作為什麼選用面向對象及C++語言講述數據結構？PASCAL與C描述是面向過程的。C++描述兼有面向過程與面向對象的特點。Java描述是面向對象的。用面向對象及C++描述與國際接軌，是市場需要。用C++描述面向對象程式C++的函數特徵C++的數據聲明C++的作用域C++的類C++的對象C++的輸入/輸出C++的函數C++的參數傳遞C++的函數名重載和操作符重載C++的動態存儲分配友元(friend)函数內聯(inline)函数結構(struct)与类聯合(Union)与类演算法定義定義：一個有窮的指令集，這些指令為解決某一特定任務規定了一個運算序列特性：輸入

有0個或多個輸入輸出

有一個或多個輸出(處理結果)

確定性

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

演算法應在執行有窮步後結束有效性

每一條運算應足夠基本事例學習：選擇排序問題明確問題：遞增排序解決方案：逐個選擇最小數據演算法框架：

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

若最小整數在a[k],交換a[i]與a[k];}細化程式：程式SelectSort

演算法設計

自頂向下，逐步求精

voidselectSort(inta[],constintn){

//對n個整數a[0],a[1],…,a[n-1]按遞增順序排序

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

intk=i;

//從a[i]查到a[n-1],找最小整數,在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;}}

範本

(template)定義

適合多種數據類型的類定義或演算法，在特定環境下通過簡單地代換，變成針對具體某種數據類型的類定義或演算法用範本定義用於排序的數據表類#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);}類中所有操作作為範本函數的實現#include“datalist.h”template<classType>voiddataList

<Type>::Swap

(intm1,intm2){

//交換由m1,m2為下標的數組元素的值

Typetemp=Element

[m1];

Element

[m1]=Element

[m2];

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

MaxKey

(intlow,inthigh){

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

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<<“數組內容

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

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

OutStream<<endl;

OuStream<<“數組當前大小

:”<<

OutList.ArraySize<<endl;returnOutStream;}

template<classType>istream&

operator>>(istream&InStream,

dataList<Type>InList){

cout<<“錄入數組當前大小

:”;

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

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

cout

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

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

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

//按非遞減順序對ArraySize個關鍵碼

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

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

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

cin>>TestList;

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

cout<<TestList<<endl;

return0;}

性能分析與度量演算法的性能標準演算法的後期測試演算法的事前估計演算法的性能標準正確性可使用性可讀性效率健壯性演算法的後期測試在演算法中的某些部位插裝時間函數

time

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

(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()

的計時程式

doublestart,stop;time(&start);

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

doublerunTime=stop-start;

cout<<""<<n<<""<< runTime<<endl;演算法的事前估計

空間複雜度時間複雜度空間複雜度度量存儲空間的固定部分

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

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

程式步確定方法

插入計數全局變數count

建表，列出個語句的程式步例以迭代方式求累加和的函數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統計執行語句條數

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

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

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

count++; //針對return語句

returns;}

執行結束得程式步數count=2*n+3程式的簡化形式

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

一個語句本身的程式步數可能不等於該語句一次執行所具有的程式步數。

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

本身的程式步數為1；

一次執行對函數sum(R,n)

的調用需要的程式步數為2*n+3；

一次執行的程式步數為

1+2*n+3=2*n+4計算累加和程式

程式步數計算工作表格時間複雜度的漸進表示法大O表示法加法規則針對並列程式段

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

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

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

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

漸進的空間複雜度

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

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

sum[i]=0.0;//數據累加

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

}

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

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

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

template<classType>//起泡排序

voiddataList<Type>::bubbleSort(){

//對表逐趟比較,ArraySize是表當前長度

inti=1;

intexchange=1;

//當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); //發生逆序,交換

exchange=1; //做“發生交換”標誌

}}作為抽象數據類型的數組一維數組一維數組的示例352749186054778341020123456789一維數組的特點連續存儲的線性表（別名向量）數組的定義和初始化#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”;//靜態

elem=a1;

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

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

elem++;

}

return0;}

一維數組(Array)类的定义

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

Array{Type*elements;//數組存放空間

intArraySize;//當前長度

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

public:Array(intSize=DefaultSize);

Array(constArray<Type>&x);

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

&

operator=//數組複製

(constArray<Type>

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

intLength()const{returnArraySize;}

//取數組長度

voidReSize(intsz); //擴充數組

}

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

//私有函數：創建數組存儲空間

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

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

endl;return;}一維數組公共操作的實現

template<classType>

Array<Type>::Array(intsz){

//構造函數

if(sz<=0){

arraySize=0;cerr<<“非法數組大小”

<<endl;return;}

ArraySize=sz;getArray();

}

template<classType>Array<Type>::

Array(Array<Type>

&x){//複製構造函數

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){

//按數組名及下標

i，取數組元素的值

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

cerr<<“數組下標超界”

<<endl;returnNULL;}

returnelement[i]; }

使用該函數於賦值語句

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

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

//創建新數組

if(newarray==NULL){

cerr<<“存儲分配錯”

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

//按新的大小確定傳送元素個數

Type*srcptr=elements;//源數組指針

Type*destptr=newarray;//目標數組指針

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

//從源數組向目標數組傳送

delete[]

elements; elements=newarray;

ArraySize=sz; }}

二維數組三維數組行向量下標i頁向量下標

i列向量下標j行向量下標

j

列向量下標

k數組的連續存儲方式一維數組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

二維數組行優先

LOC

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

三維數組

各維元素個數為

m1,m2,m3

下標為i1,i2,i3的數組元素的存儲地址：

（按頁/行/列存放）

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

)*l

前i1頁總元素個數第i1頁的前i2行總元素個數

n維數組

各維元素個數為

m1,m2,m3,…,mn

下標為i1,i2,i3,…,in

的數組元素的存儲地址：

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

)*l

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

定義

n（0）個數據元素的有限序列，記作

（a1,a2,…,an）

ai是表中数据元素，n是表長度。

遍曆逐項訪問：

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

定義將線性表中的元素相繼存放在一個連續的存儲空間中。可利用一維數組描述存儲結構特點

線性表的順序存儲方式

遍曆順序訪問

253457164809

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

intMaxSize; //最大允許長度

intlast; //當前最後元素下標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);//前驅

intIsEmpty(){returnlast==-1;

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

}TypeGet(inti){//提取

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

順序表部分公共操作的實現

template<classType>

//構造函數

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{

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

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搜索失敗搜索成功

若搜索概率相等，则

搜索不成功數據比較n

次表項的插入25345716480963

01234567data50插入x2534575016480963

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

i個位置插入新元素

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

}}表項的刪除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}順序表的應用：集合的“並”運算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中刪除它

}}順序表的應用：集合的“交”運算稀疏矩陣

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

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

Typevalue;//非零元素的值}

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

intRows,Cols,Terms;//行/列/非零元素數

Trituple<Type>smArray[MaxTerms];

public://三元組表

SparseMatrix(intMaxRow,intMaxcol);

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

SparseMatrix<Type>&Add(SparseMatrix

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

SparseMatrix<Type>&Multiply(SparseMatrix

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

稀疏矩陣轉置矩陣用三元組表表示的稀疏矩陣及其轉置稀疏矩陣轉置演算法思想設矩陣列數為Cols，對矩陣三元組表掃描Cols次。第k次檢測列號為k的項。第k次掃描找尋所有列號為k

的項，將其行號變列號、列號變行號，順次存於轉置矩陣三元組表。稀疏矩陣的轉置

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;

//轉置矩陣的列數,行數和非零元素個數

if(a.Terms>0){

intCurrentB=0;

//轉置三元組表存放指針

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;}快速轉置演算法建立輔助數組rowSize和rowStart，記錄矩陣轉置後各行非零元素个数和各行元素在轉置三元組表中開始存放位置。掃描矩陣三元組表，根據某項的列號，確定它轉置後的行號，查rowStart表，按查到的位置直接將該項存入轉置三元組表中。

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];稀疏矩陣的快速轉置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)個字元的有限序列，記作S:“c1c2c3…cn”

其中，S是串名字

“c1c2c3…cn”是串值

ci是串中字元

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

constintmaxLen=128;

classString{intcurLen;//串的當前長度

char*ch;//串的存儲數組

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

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

字串抽象數據類型和類定義

intLength()const{

returncurLen;}

//求當前串*this的實際長度

String&operator()(intpos,intlen);

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

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

//判當前串*this與對象串ob是否相等

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

//判當前串*this與對象串ob是否不等

intoperator!()

const

{returncurLen==0;}

//判當前串*this是否空串

String&operator=(String&ob);

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

//將串ob連接到當前串*this之後

char&operator[](inti);

//取當前串*this的第i個字元

intFind(String&pat)const;}

String::String(constString&ob){

//複製構造函數：從已有串ob複製

ch=newchar[maxLen+1];//創建串數組

if(ch==NULL){

cerr<<“存儲分配錯!

\n”;

exit(1);

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

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

}

字串部分操作的實現String::String(const

char*init){//複製構造函數:從已有字元數組*init複製

ch=newchar[maxLen+1];//創建串數組

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

\n”;

exit(1);

}curLen=strlen(init);

//複製串長度

strcpy(ch,init);

//複製串值

}String::String(

){//構造函數：創建一個空串

ch=newchar[maxLen+1];//創建串數組

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個位置起連續提取

len個字元//形成子串返回

String*temp=newString;//動態分配

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];//傳送串數組

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

}

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個字元

if(i<0&&i>=curLen

){cout<<“串下標超界!\n”;

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

st=“university”,使用示例

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

newChar=

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

char*temp=ch;//暫存原串數組

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

ch=new

char[maxLen+1];

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

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

//拷貝原串數組

strcat(ch,ob.ch);

//連接ob串數組

delete[]temp;return

*this;

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

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

目標T:“Beijing”

模式P:“jin”

匹配結果=3

第1趟

T abbaba窮舉的模式

P aba

匹配过程

第2趟

T abbaba P

aba

第3趟

T abbaba P

aba

第4趟

T abba

ba Pa

ba

單鏈表(SinglyLinkedList)特點

每個元素(表項)由結點(Node)構成。線性結構

結點可以不連續存儲表可擴充datalinka0a1a2a3a4

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

freefirst(b)經過一段運行後的單鏈表結構單鏈表的類定義多個類表