数据结构第02章 (清华 殷人昆版).pptx

《数据结构第02章 (清华 殷人昆版).pptx》由会员分享，可在线阅读，更多相关《数据结构第02章 (清华 殷人昆版).pptx（66页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、作为抽象数据类型的数组作为抽象数据类型的数组n n一维数组一维数组uu 一维数组的示一维数组的示例例35 27 49 18 60 54 77 83 41 020 1 2 3 4 5 6 7 8 9第1页/共66页一维数组的特点一维数组的特点n n连续存储的线性表（别名连续存储的线性表（别名 向量向量）第2页/共66页数组的定义和初始化数组的定义和初始化#include class szcl int e;public:szcl()e=0;szcl(int value)e=value;int get_value()return e;第3页/共66页main()szcl a13=3,5,7,*ele

2、m;for(int i=0;i 3;i+)cout a1i.get_value()“n”;/静态 elem=a1;for(int i=0;i 3;i+)cout get_value()“n”;/动态 elem+;return 0;第4页/共66页一维数组一维数组(Array)类的定义类的定义#include#include template class Array Type*elements;/数组存放空间 int ArraySize;/当前长度 void getArray();/建立数组空间 public:Array(int Size=DefaultSize);Array(const Arr

3、ay&x);第5页/共66页 Array()delete elements;Array&operator=/数组复制 (const Array&A);Type&operator (int i);/取元素值 int Length()const return ArraySize;/取数组长度 void ReSize(int sz);/扩充数组 第6页/共66页 template void Array:getArray()/私有函数：创建数组存储空间 elements=new TypeArraySize;if(elements=NULL)arraySize=0;cerr “存储分配错！endl;re

4、turn;一维数组公共操作的实现一维数组公共操作的实现第7页/共66页 template Array:Array(int sz)/构造函数 if(sz=0)arraySize=0;cerr “非法数组大小”endl;return;ArraySize=sz;getArray();第8页/共66页 template Array:Array(Array&x)/复制构造函数 int n=ArraySize=x.ArraySize;elements=new Typen;if(elements=NULL)arraySize=0;cerr “存储分配错”endl;return;Type*srcptr=x.e

5、lements;Type*destptr=elements;while(n-)*destptr+=*srcptr+;第9页/共66页template Type&Array:operator (int i)/按数组名及下标 i，取数组元素的值 if(i ArraySize-1)cerr “数组下标超界”endl;return NULL;return elementi;使用该函数于赋值语句 Pos=Positioni-1+Numberi-1第10页/共66页 template void Array:Resize(int sz)if(sz=0&sz!=ArraySize)Type*newarray=

6、new Typesz;/创建新数组 if(newarray=NULL)cerr “存储分配错”endl;return;int n=(sz 0 a,i=0 a+i*la第14页/共66页n n 二维数组二维数组行优先行优先 LOC(j,k)=a+(j*m+k)*l第15页/共66页n n 三维数组三维数组F 各维元素个数为各维元素个数为 m1,m2,m3F 下标为下标为 i1,i2,i3的数组元素的存储地的数组元素的存储地址：址：（按页（按页/行行/列存放）列存放）LOC(i1,i2,i3)=a+(i1*m2*m3+i2*m3+i3)*l 前前i1页总页总元素个数元素个数第第i1页的页的前前i2

7、行行总总元素个数元素个数第16页/共66页n n n 维数组维数组F 各维元素个数为各维元素个数为 m1,m2,m3,mnF 下标为下标为 i1,i2,i3,in 的数组元素的的数组元素的存储地址：存储地址：LOC(i1,i2,in)=a+(i1*m2*m3*mn+i2*m3*m4*mn+in-1*mn+in)*l 第17页/共66页线性表线性表(Linear List)n n线性表的定义和特点线性表的定义和特点uu 定义定义 n（0）个数据元素的个数据元素的有限序列，记作有限序列，记作 （a1,a2,an）ai 是表中数据元素，是表中数据元素，n 是表长度。是表长度。uu 遍历遍历 逐项访问

8、：逐项访问：从前向后从前向后 从后向前从后向前 第18页/共66页线性表的特点线性表的特点n n除第一个元素外，其他每一个元素除第一个元素外，其他每一个元素有一个且仅有一个有一个且仅有一个直接前驱直接前驱。n n除最后一个元素外，其他每一个元除最后一个元素外，其他每一个元素有一个且仅有一个素有一个且仅有一个直接后继直接后继。第19页/共66页顺序表顺序表(Sequential List)n n顺序表的定义和特点顺序表的定义和特点uu 定义定义 将线性表中的元素相继将线性表中的元素相继存放在一个连续的存储空间中。存放在一个连续的存储空间中。uu 可利用可利用一维数组一维数组描述描述存储结构存储结

9、构uu 特点特点 线性表的顺序存储方式线性表的顺序存储方式uu 遍历遍历 顺序顺序访问访问 25 34 57 16 48 09 0 1 2 3 4 5 data第20页/共66页顺序表顺序表(SeqList)类的定义类的定义template class SeqList Type*data;/顺序表存储数组 int MaxSize;/最大允许长度 int last;/当前最后元素下标public:SeqList(int MaxSize=defaultSize);SeqList()delete data;int Length()const return last+1;第21页/共66页 int F

10、ind(Type&x)const;/查找 int Locate(int i)const;/定位 int Insert(Type&x,int i);/插入 int Remove(Type&x);/删除 int Next(Type&x);/后继 int Prior(Type&x);/前驱 int IsEmpty()return last=-1;int IsFull()return last=MaxSize-1;Type Get(int i)/提取 return i last？NULL:datai;第22页/共66页顺序表部分公共操作的实现顺序表部分公共操作的实现 template /构造函数 Se

11、qList:SeqList(int sz)if(sz 0)MaxSize=sz;last=-1;data=new TypeMaxSize;if(data=NULL)MaxSize=0;last=-1;return;第23页/共66页template int SeqList:Find(Type&x)const /搜索函数：在表中从前向后顺序查找 x int i=0;while(i last)return-1;else return i;第24页/共66页顺序搜索图示顺序搜索图示25 34 57 16 48 09 0 1 2 3 4 5 data搜索搜索 16 i25 34 57 16 48 09

12、 i25 34 57 16 48 09 i25 34 57 16 48 09 i搜索成功搜索成功第25页/共66页25 34 57 16 48 0 1 2 3 4data搜索 50 i25 34 57 16 48 i25 34 57 16 48 i25 34 57 16 48 i25 34 57 16 48 i搜索失败搜索失败第26页/共66页搜索成功搜索成功 若搜索概率相等，则若搜索概率相等，则搜索不成功搜索不成功 数据比较数据比较 n 次次第27页/共66页表项的插入表项的插入25 34 57 16 48 09 63 0 1 2 3 4 5 6 7data50插入 x25 34 57 50

13、 16 48 09 63 0 1 2 3 4 5 6 7data50i第28页/共66页template int SeqList:Insert(Type&x,int i)/在表中第 i 个位置插入新元素 x if(i last+1|last=MaxSize-1)return 0;/插入不成功 else last+;for(int j=last;j i;j-)dataj=dataj-1;datai=x;return 1;/插入成功 第29页/共66页表项的删除表项的删除25 34 57 50 16 48 09 63 0 1 2 3 4 5 6 7data16删除 x25 34 57 50 48

14、09 63 0 1 2 3 4 5 6 7data第30页/共66页 template int SeqList:Remove(Type&x)/在表中删除已有元素 x int i=Find(x);/在表中搜索 x if(i=0)last-;for(int j=i;j=last;j+)dataj=dataj+1;return 1;/成功删除 return 0;/表中没有 x 第31页/共66页顺序表的应用：顺序表的应用：集合的集合的“并并”运算运算void Union(SeqList&A,SeqList&B)int n=A.Length();int m=B.Length();for(int i=1

15、;i=m;i+)int x=B.Get(i);/在B中取一元素 int k=A.Find(x);/在A中搜索它 if(k=-1)/若未找到插入它 A.Insert(n,x);n+;第32页/共66页 void Intersection(SeqList&A,SeqList&B)int n=A.Length();int m=B.Length();int i=0;while(i n)int x=A.Get(i);/在A中取一元素 int k=B.Find(x);/在B中搜索它if(k=-1)A.Remove(i);n-;else i+;/未找到在A中删除它 顺序表的应用：顺序表的应用：集合的集合的“

16、交交”运算运算第33页/共66页稀疏矩阵稀疏矩阵(Sparse Matrix)非零元素个数非零元素个数远远少于矩阵元素个数远远少于矩阵元素个数第34页/共66页稀疏矩阵的抽象数据类型稀疏矩阵的抽象数据类型template class SparseMatrix;template class Trituple /三三元组元组friend class SparseMatrix private:int row,col;/非零元素行号非零元素行号/列号列号 Type value;/非零元素的值非零元素的值template class SparseMatrix/稀疏矩阵类定义稀疏矩阵类定义 第35页/共6

17、6页 int Rows,Cols,Terms;/行行/列列/非零元素数非零元素数 Trituple smArrayMaxTerms;public:/三元组表三元组表 SparseMatrix(int MaxRow,int Maxcol);SparseMatrix&Transpose (SparseMatrix&);/转置转置 SparseMatrix&Add(SparseMatrix a,SparseMatrix b);/相加相加 SparseMatrix&Multiply(SparseMatrix a,SparseMatrix b);/相乘相乘 第36页/共66页稀疏矩阵稀疏矩阵第37页/共

18、66页转置矩阵转置矩阵第38页/共66页用三元组表表示的稀疏矩阵及其转置用三元组表表示的稀疏矩阵及其转置第39页/共66页稀疏矩阵转置算法思想稀疏矩阵转置算法思想n n设矩阵列数为设矩阵列数为 Cols，对矩阵三元，对矩阵三元组表扫描组表扫描Cols 次。第次。第 k 次检测列次检测列号为号为 k 的项。的项。n n第第 k 次扫描找寻所有列号为次扫描找寻所有列号为 k 的的项，将其行号变列号、列号变行号，项，将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。顺次存于转置矩阵三元组表。第40页/共66页稀疏矩阵的转置稀疏矩阵的转置 template SparseMatrix&SparseM

19、atrix:Transpose (SparseMatrix&a)SparseMatrix b(a.Cols,a.Rows);b.Rows=a.Cols;b.Cols=a.Rows;b.Terms=a.Terms;/转置矩阵的列数转置矩阵的列数,行数和非零元素个数行数和非零元素个数 if(a.Terms 0)int CurrentB=0;/转置三元组表存放指针转置三元组表存放指针第41页/共66页 for(int k=0;k a.Cols;k+)/对所有列号处理一遍 for(int i=0;i a.Terms;i+)if(a.smArrayi.col=k)b.smArrayCurrentB.ro

20、w=k;b.smArrayCurrentB.col=a.smArrayi.row;b.smArrayCurrentB.value=a.smArrayi.value;CurrentB+;第42页/共66页 return b;快速转置算法快速转置算法n n建立辅助数组建立辅助数组 rowSize 和和 rowStart，记录矩阵转置后，记录矩阵转置后各行非零元素个数各行非零元素个数和和各行元素在转置三元组表中开始存各行元素在转置三元组表中开始存放位置放位置。第43页/共66页n n扫描矩阵三元组表，根据某项的列扫描矩阵三元组表，根据某项的列号，确定它转置后的行号，查号，确定它转置后的行号，查 ro

21、wStart 表，按查到的位置直接将表，按查到的位置直接将该项存入转置三元组表中。该项存入转置三元组表中。第44页/共66页 for(int i=0;i a.Cols;i+)rowSizei=0;for(i=0;i a.Terms;i+)rowSizea.smArrayi.col+;rowStart0=0;for(i=1;i Cols;i+)rowStarti=rowStarti-1+rowSizei-1;第45页/共66页稀疏矩阵的快速转置稀疏矩阵的快速转置template SparseMatrix&SparseMatrix:FastTranspos (SparseMatrix&a)int*

22、rowSize=new inta.Cols;int*rowStart=new inta.Cols;SparseMatrix b(a.Cols,a.Rows);b.Rows=a.Cols;b.Cols=a.Rows;b.Terms=a.Terms;if(a.Terms 0)for(int i=0;i Cols;i+)rowSizei=0;第46页/共66页for(i=0;i Terms;i+)rowSizesmArrayi.col+;rowStart0=0;for(i=1;i a.Cols;i+)rowStarti=rowStarti-1+rowSizei-1;for(i=0;i a.Terms

23、;i+)int j=rowStarta.smArrayi.col;b.smArrayj.row=a.smArrayi.col;b.smArrayj.col=a.smArrayi.row;b.smArrayj.value=a.smArrayi.value;rowStarta.smArrayi.col+;第47页/共66页 delete rowSize;delete rowStart;return b;第48页/共66页字符串字符串(String)字符串是字符串是 n(0)个字符的有限序个字符的有限序列，列，记作记作 S:“c1c2c3cn”其中，其中，S 是串名字是串名字 “c1c2c3cn”是

24、串值是串值 ci 是串中字符是串中字符 n 是串的长度。是串的长度。例如例如,S=“Tsinghua University”第49页/共66页 const int maxLen=128;class String int curLen;/串的当前长度串的当前长度 char*ch;/串的存储数组串的存储数组 public:String(const String&ob);String(const char*init);String();String()delete ch;字符串抽象数据类型和类定义字符串抽象数据类型和类定义第50页/共66页 int Length()const return curL

25、en;/求当前串求当前串*this的实际长度的实际长度 String&operator()(int pos,int len);/取取*this从从pos开始开始len个字符组成的子个字符组成的子串串 int operator=(const String&ob)return strcmp(ch,ob.ch)=0;/判当前串判当前串*this与对象串与对象串ob是否相等是否相等 int operator!=(const String&ob)const return strcmp(ch,ob.ch)!=0;/判当前串判当前串*this与对象串与对象串ob是否不等是否不等 第51页/共66页 int

26、operator!()const return curLen=0;/判当前串判当前串*this是否空串是否空串 String&operator=(String&ob);/将串将串ob赋给当前串赋给当前串*this String&operator+=(String&ob);/将串将串ob连接到当前串连接到当前串*this之后之后 char&operator (int i);/取当前串取当前串*this的第的第 i 个字符个字符 int Find(String&pat)const;第52页/共66页 String:String(const String&ob)/复制构造函数：从已有串ob复制 ch

27、=new charmaxLen+1;/创建串数组 if(ch=NULL)cerr “存储分配错!n”;exit(1);curLen=ob.curLen;/复制串长度 strcpy(ch,ob.ch);/复制串值 字符串部分操作的实现字符串部分操作的实现第53页/共66页String:String(const char*init)/复制构造函数:从已有字符数组*init复制 ch=new charmaxLen+1;/创建串数组 if(ch=NULL)cerr “存储分配错!n”;exit(1);curLen=strlen(init);/复制串长度 strcpy(ch,init);/复制串值 第5

28、4页/共66页String:String()/构造函数：创建一个空串构造函数：创建一个空串 ch=new charmaxLen+1;/创建串数组 if(ch=NULL)cerr “存储分配错!n”;exit(1);curLen=0;ch0=0;第55页/共66页提取子串的算法示例提取子串的算法示例pos+len-1 pos+len-1 curLen-1 curLeni n f i n i t yi n f i n i t ypos=2,len=3pos=5,len=4f i ni t y超出超出第56页/共66页String&String:operator()(int pos,int len)

29、/从串中第 pos 个位置起连续提取 len 个字符/形成子串返回 String*temp=new String;/动态分配 if(pos=maxLen|lencurLen=0;/返回空串 temp-ch0=0;else /提取子串if(pos+len-1=curLen)len=curLen-pos;第57页/共66页 temp-curLen=len;/子串长度 for(int i=0,j=pos;i chi=chj;/传送串数组 temp-chlen=0;/子串结束 return*temp;例：串 st=“university”,pos=3,len=4使用示例 subSt=st(3,4)提取

30、子串提取子串 subSt=“vers”第58页/共66页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);else cout “字符串自身赋值出错!n”;return*this;第59页/共66页char&String:operator (int i)/按串名提取串中第 i 个字符 if(i=curLen)c

31、out “串下标超界!n”;exit(1);return chi;例：串 st=“university”,使用示例 newSt=st；newChar=st1;数组赋值 newSt=“university”提取字符 newChar=n第60页/共66页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,

32、ob.ch);/连接ob串数组 delete temp;return*this;第61页/共66页例：串例：串 st1=“beijing”,st2=“university”,使用示例 st1+=st2;连接结果 st1=“beijing university”st2=“university”第62页/共66页串的模式匹配串的模式匹配n n定义定义 在串中寻找子串（第一个在串中寻找子串（第一个字符）在串中的位置字符）在串中的位置n n词汇词汇 在模式匹配中，子串称为在模式匹配中，子串称为模式模式，串称为，串称为目标目标。n n示例示例 目标目标 T:“Beijing”模式模式 P:“jin”匹配

33、结果匹配结果=3 第63页/共66页第第1趟趟 T a b b a b a 穷举的模式穷举的模式 P a b a 匹配过程匹配过程 第第2趟趟 T a b b a b a P a b a 第第3趟趟 T a b b a b a P a b a第第4趟趟 T a b b a b a P a b a 第64页/共66页 int String:Find(String&pat)const /穷举的模式匹配 for(int i=0;i=curLen-pat.curLen;i+)/逐趟比较 int j=0;/从chi与模式pat.ch比较 while(j pat.curLen)if(chi+j=pat.chj)j+;else break;if(j=pat.curLen)return i;/pat扫描完,匹配成功 第65页/共66页感谢您的观看！第66页/共66页