数据结构及其应用（用面向对象方法与C＋＋描述）

2022/11/221数据结构及其应用

（用面向对象方法与C＋＋描述）2022/11/222第一章概述研究对象：信息的表示方法、数据的组织方法、操作算法设计意义地位：数据结构＋算法＝程序程序设计的基础系统软件的核心发展过程：数值计算非数值计算

建立数学模型客体及其关系的表示设计数值计算方法数据的组织操作算法的设计非数值计算应用的发展，促进了数据结构的研究和发展以及其体系的完善。2022/11/223基本术语数据：描述客观事物的且能由计算机处理的数值、字符等符号数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理（记录、结点、表目、元素）数据项：数据元素的某一属性。数据元素可以由若干数据项组成，数据项可以由若干更小的款项（组合项、原子项）组成。数据项又称域、字段关键码：能起唯一标识（数据元素）作用的数据项数据结构：一组同类的数据元素、其间的关系及其上的一组操作所构成的整体，称为一个数据结构2022/11/224数据结构的描述方式逻辑结构：是对数据元素之间逻辑关系（抛开具体的关系含义以及存储方式等）的描述，它可以用一个数据元素的集合和定义在此集合上的几个关系来表示。通常可用图形表示，圆圈表示数据元素，箭头表示关系：物理结构：数据结构在计算机中的具体表示和实现，

又称存储结构EiEi+1数据元素数据元素关系2022/11/225数据结构的分类按逻辑结构分类：

纯集合型结构:数据元素之间除了“同属于一个集合”这一 关系外，别无其他关系线性结构：数据元素之间存在“一个跟着一个”的序列关系树型结构：数据元素之间存在“每个元素只能跟着一个元素 但可以有多个元素跟着它”的层次关系图状结构：任意两个数据元素之间都可能存在关系按存储结构分类：

顺序存储结构链式存储结构 索引存贮结构2022/11/226基本操作：任一数据结构均有一组相应的基本操作，

有时操作不同，用途迥异（如栈和队列）

常用的基本操作有插入、删除、查找、更新、排序等算法：算法是为了解决给定的问题而规定的一个有限长的操作步骤序列，则重于解决问题的方法和步骤。当算法由计算机语言表示时称为程序（代码）算法设计目标：可维护性可靠性（正确性、健壮行）可读性高效率（时间、空间）2022/11/227第二章线性表2。1线性表的逻辑结构

定义：由相同种类的数据元素组成的一个有穷序列称为一个线性表。“一个跟着一个”

符号表示法：L＝（e1,e2,…en）

图形表示法：e2ene12022/11/228其中：

ei---表示线性表L

的第i个数据元素

n---表示线性表L

的表长（n>=0）

n=0

时的线性表称为空表

ei-1

称为ei

的前驱，ei+1

称为ei

的后继线性表的基本操作： （1）初始化（置空表）——可由构造函数实现 （2）求表长（Length） （3）查找或定位（Find） （4）插入（Insert）

（5）删除（Remove） （6）排序（Sort）

（7）判空（IsEmpty）2022/11/2292.2线性表的顺序存储结构

要实现在计算机内表示一个数据结构，要解决两种信息的存贮问题： 数据元素本身的存贮 数据元素之间关系的存贮定义：利用内存物理结构上的邻接特点，实现线性表的“一个跟着一个”这一序列关系的存贮方式， 称为线性表的顺序存贮结构，其上的线性表称 为顺序表。顺序表的类定义：利用数组作为顺序表的存储结构，它被封装在类的私有域中2022/11/2210template<classType>class

SeqList{Public:

SeqList(intMaxSize=defaultSize); ~SeqList(){delete[]data;} intLength()const{returnlast+1;} intFind(Type&x)const; intInsert(Type&x,inti); intRemove(Type&x); intIsEmpty(){returnlast==-1;} intIsfull(){returnlast==MaxSize–1;} Type&Get(inti){returni<0||i>last?NULL:data[i];}Private: Type*data;//用数组存放线性表——顺序存贮结构

intMaxsize;//数组大小，但顺序表的长度为last+1 intlast;}//last为表中最后元素的下标，last=-1时表示空表2022/11/2211

上述顺序表定义中的数据成员Maxsize是为判断顺序表是否为满而设，last是为便于判断顺序表是否为空、求表长、置空表而设：

last=Maxsize–1表示顺序表已满，此时再进行插入操作会导致上溢错误；

last=-1表示顺序表为空表，此时再进行删除操作会导致下溢错误；

last+1代表顺序表的表长； 将last赋值为–1可实现置空表操作。由上可知：合理地设置数据成员可大大简化算法的设计及提高算法的效率。顺序表不仅仅包含存放其数据元素的数组，它还应包括一些有用的数据成员，以及相应的操作，它们是一个整体：2022/11/2212顺序表之整体概念：

data01lastMaxsizelast数组下标

数组变量操作算法Maxsize-1初始化操作插入操作删除操作查找操作排序操作......

.........2022/11/2213顺序表的基本操作（算法）（1）顺序表初始化操作算法template<classType>Seqlist<Type>::Seqlist(intsz)//构造函数，通过指定参数sz定义数组的长度，并将last置为–1//即置空表{ if(sz>0) { Maxsize=sz; last=-1;//last+1=0,表明表中无元素，空表

data=newType[Maxsize]; }}2022/11/2214（2）顺序表查找操作template<classType>intSeqlist<Type>::Find(Type&x)const//查找x在表中位置，若查找成功，函数返回x的位置//否则返回－1{ inti=0; while(i<=last&&data[i]!=x)i++; if(i>last)return–1; elsereturni;}2022/11/2215（3）顺序表插入操作

为了把新元素x插入到i处，必须把从i到last的所有元素成块向后移动一个元素位置，以空出第i个位置供x插入：x231先移动后面元素0i-1ii+1last..................2022/11/2216template<classType>intSeqlist<Type>::Insert(Type&x,inti)//将x插入表中i处，若成功返回1，否则返回0{ 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; }}2022/11/2217（4）顺序表删除操作为了删除第i个元素，必须把从i＋1到last的所有元素向前移动一个元素位置，把第i个元素覆盖掉：12...0i-1ii+1last-1last1...............2022/11/2218template<classType>intSeqlist<Type>::Remove(Type&x)//将x从表中删除。若x在表中并成功删除则返回1，//否则返回0{ inti=Find(x); if(i>=0) { last--; for(intj=i;j<=last;j++)data[j]=data[j+1]; return1; } return0;}2022/11/2219顺序存储结构的优缺点优点： （1）算法简单、可读性好、开发代价低缺点：

（1）插入、删除操作时需要移动大量元素， 效率较低； （2）最大表长难以估计，太大了浪费空间， 太小了容易溢出。2022/11/2220顺序表应用举例当将两个顺序表作集合考虑时的“并”与“交”操作算法template<classType>voidUnion(Seqlist<Type>&LA,Seqlist<Type>&LB)//合并顺序表LA与LB，重复元素只留一个，结果在LA中。{intn=LA.Length(); intm=LB.Length(); for(inti=0;i<=m-1;i++) { Typex=LB.Get(i);//从顺序表LB中取一元素

intk=LA.Find(x);//在顺序表LA中查找该元素

if(k==-1)//未找到

{LA.Insert(x,n);//将该元素追加到LA中

n++; } }}2022/11/2221template<classType>voidIntersection(Seqlist<Type>&LA,Seqlist<Type>&LB)//求顺序表LA与LB的共同元素，结果在LA中{ intn=LA.Length(); intm=LB.Length(); inti=0; while(i<n) { Typex=LA.Get(i);//从LA中取一元素

intk=LB.Find(x);//在LB中查找该元素

if(k==-1)//未找到

{LA.Remove(i);n--;}//则从LA中删除该元素

elsei++; }}2022/11/2222多项式及其运算A(x)=a0x+a1x+a2x+…+an-1x+anx=B(x)=b0x+b1x+b2x+…+bn-1x+bnx=A(x)+B(x)=实际应用中，上述一元多项式中的很多系数有可能为零，即为稀疏多项式，如下式所示：Σaixi=0ni012n-1n012n-1nΣbixii=0Σ(ai+bi)xni=0iP

(x)=1.2+51.3x+3.7x5050101P(x)=Σcixi=0neic0=1.2e0=0c1=51.3e1=50c2=3.7e2=1012022/11/2223多项式的表示对于稀疏多项式，采用二元组表示法可以大大节省存储空间： （1）将稀疏多项式的每一项用二元组<ci,ei>表示

——客体的表示方法 （2）用一顺序表（一维数组）来存放上述的二元组

——数据的组织方法c0c1cicne0e1eien系数指数..............2022/11/2224多项式二元组的类定义——客体的表示方法classPolynomial;//

多项式类的前视声明classterm//多项式中项（二元组）的类定义{ friendPolynomial;//定义Polynomial类为term类的友元类

private: floatcoef;//

系数

intexp;//

指数}2022/11/2225多项式的类定义——数据的表示方法classPolynomial{ public: ...//

成员函数声明（构造、释构、相加等函数）

private: intMaxTerms;//共享空间（顺序表）的最大项数

statictermtermArray[MaxTerms]; //存放二元组的数组，存放多个多项式的共享空间

staticintfree;//共享空间中自由空间之起始下标

intstart,finish;//

多项式在共享空间中的首、尾下标}2022/11/2226多项式的相加

A(x)=ΣaixB(x)=ΣbjxC(x)=A(x)+B(x)nmi=0j=0e

iejA.StartA.finishB.StartB.finishfreeMaxTerm-12022/11/2227多项式A＋B算法思路：

（1）保留A、B两个多项式，将A＋B放人C中； （2）开始时C.start=free； （3）设置两个指针a和b分别作为A与B的检测指针，开始时 分别指向A与B的首项，即：

a=A.start;b=B.start； （4）当两个指针都未超出相应多项式的最末位置时，比较它们所 指示的对应项的指数： 若指数相等，则对应项系数相加，若相加结果不为零，则在 C中加入一个新项 若指数不等，则把指数小者拷贝到C中 （5）当两个指针中有一个超出了相应多项式的最末位置，则将另 一个多项式的剩余部分拷贝到C中2022/11/2228PolynomialPolynomial::Add(PolynomialB){ PolynomialC;inta=start;intb=B.start;C.start=free;floatc; while(a<=finish&&b<=B.finish) switch(compare(termArray[a].exp,termArray[b].exp)){ case‘=‘:c=termArray[a].coef+termArray[b].coef; if(c)NewTerm(c,termArray[a].exp); a++;b++;break; case‘>‘:NewTerm(termArray[b].coef,termArray[b].exp); b++;break; case‘<’:NewTerm(termArray[a].coef,termArray[a].exp); a++;} for(;a<=finish;a++) NewTerm(termArray[a].coef,termArray[a].exp); for(;b<=B.finish;b++) NewTerm(termArray[b].coef,termArray[b].exp); C.finish=free-1; returnC;} 2022/11/2229voidPolynomial::NewTerm(floatc,inte)//把一个新的项（二元组<c,e>）追加到多项式C(x)中{ if(free>=MaxTerms) { cout<<“Toomanytermsinpolynomials”<<endl; return; } termArray[free].coef=c; termArray[free].exp=e; free++;}2022/11/2230作业：

定义多项式类的求表长、查找、插入、删除、判空表判满表、读取（第i个元素）等成员函数，并用这些函数实现前述的两个多项式的相加操作。提示：（1）定义查找指数相等的元素的成员函数（2）仿照前述的顺序表合并操作算法，先从多项式B中读取一元素，在A中查找有无指数相等元素：若无，则有序插入A中；若有，则系数相加： 若和为零，则从A中删除相应元素； 否则用新系数构造新元素，并插入A中相应位置2022/11/2231稀疏矩阵（SparseMatrix）－－数值计算中的顺序表设计 0 0 0 22 0 0 15 0 11 0 0 0 17 0A = 0 0 0 -6 0 0 0 0 0 0 0 0 39 0 91 0 0 0 0 0 0 0 0 28 0 0 0 0矩阵A是一个6行7列的稀疏矩阵，只有8个非零元素，其他均为零。因此用二维数组来存储稀疏矩阵的空间利用率较低，必须考虑对稀疏矩阵的压缩存储表示。2022/11/2232稀疏矩阵的三元组表示法： （1）将稀疏矩阵的非零元素用三元组

<row,column,value>表示（表示稀疏矩阵的 第row行、第column列的值为value）

——客体的表示方法 （2）用一顺序表（一维数组）来存放上述三元组 （每一个三元组即为顺序表的一个数据元素） 并按行优先顺序存放

——数据的组织方法template<classType>classTrituple{ private: introw,col; Typevalue;}2022/11/2233矩阵A的三元组表示：表下标 行(row)列(col)值(value) 0 0 3 22 1 0 6 15 2 1 1 11 3 1 5 17 4 2 3 -6 5 3 5 39 6 4 0 91 7 5 2 282022/11/2234稀疏矩阵的类声明：template<classType>classSparseMatrix{ public: SparseMatrix(intMaxTerms=defaultSize); ~SparseMatrix(){delete[]smArray;} SparseMatrix<Type>Compression(smData<Type>); SparseMatrix<Type>Transpose(); SparseMatrix<Type>Add(SparseMatrix<Type>b); SparseMatrix<Type>Multiply(SparseMatrix<Type>b); private: intRows,Cols,Terms,MaxTerms; Trituple<Type>smArray[MaxTerms];}2022/11/2235说明：（1）压缩前的稀疏矩阵为Rows行,Cols列的矩阵

smData，压缩后的稀疏矩阵存放在一维数组

smArray中，其中的元素为Trituple类型的对象。声明中的Terms对应于顺序表定义中的last，

MaxTerms对应于顺序表定义中的Maxsize，

smArray对应于顺序表定义中的data

（2）为稀疏矩阵声明了四种操作： 压缩（Compression） 转置（Transpose） 相加（Add） 相乘（Multiply） 根据实际需要还可以声明其他操作。（3）数值计算与非数值计算的数据结构中所定义的基 本操作有很大的不同2022/11/2236稀疏矩阵的转置操作快速转置算法思路： （1）引入两个辅助数组rowSize[]和rowStart[] rowSize[i]——表示稀疏矩阵第i列的非零元素个数

rowStart[i]——表示稀疏矩阵第i列的第一个（行号最小）非零元素在转置矩阵的三元组表中的位置。显然应有：

rowStart[i]+rowSize[i]=rowStart[i+1].........共有rowSize[i]个元素2022/11/2237

上述公式表示，若已知稀疏矩阵第i列的第一个非零元素在转置矩阵的三元组表中的位置rowStart[i],以及稀疏矩阵第i列的非零元素个数rowSize[i],就可以算出第i+1列非零元素在转置矩阵的三元组表中的位置rowStart[i+1]另外，根据转置矩阵的定义可知：

rowStart[0]=0因此：

rowStart[1]=rowSize[0]+rowStart[0]=rowSize[0]rowStart[2]=rowSize[1]+rowStart[1]......因此，只要预先统计得到rowSize[i](i=0,1,2,...)就可以得到第i+1列非零元素在转置矩阵的三元组表中的位置2022/11/2238template<classType>SparseMatrix<Type>SparseMatrix<Type>::FastTranspos()//{int*rowSize=newint[Cols]; int*rowStart=newint[Cols]; SparseMatrix<Type>b;b.Rows=Cols;b.Cols=Rows;b.Terms=Terms; if(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<Cols;i++)rowStart[i]=rowStart[i-1]+rowSize[i-1]; for(i=0;i<Terms;i++){ intj=rowStart[smArray[i].col]; b.smArray[j].row=smArray[i].col; b.smArray[j].col=smArray[i].row; b.smArray[j].value=smArray[i].value; rowStart[smArray[i].col]++;} } delete[]rowSize;delete[]rowStart;returnb;}2022/11/22392。5字符串定义：字符串（简称为串）是n(n>=0)个字符的有限序列 通常可记为：

S

=‘a0a1a2…an-1’其中：串名——S

串值——引号中的内容

n——串长，即串中的字符个数（不包括串结束符‘\0’） 空串——n=0的串（但包含串结束符） 空白串——仅由若干个空格字符组成的串，其长度不为零 子串——从非空串中连续取出的若干个字符组成的串 子串的位置——子串的第0个字符在原串中的位置 可以认为：串是限制数据元素为字符的顺序表2022/11/22402.5.1字符串抽象数据类型和类定义classString{public: String(constString&);String(constchar*const);String(); ~String(){delete[]ch;} intLength()const{returncurLen；} String&operator()(intpos,intlen); intoperator==(constString&ob)const{returnstrcmp(ch,ob.ch)==0;} intoperator!=(constString&ob)const{returnstrcmp(ch,ob.ch)!=0;} intoperator!()const{returncurLen==0；} String&operator=(constString&); String&operator+=(constString&); char&operator[](inti); intFind(Stringpat)const;private: intcurLen; char*ch;}2022/11/2241有了上述的串类定义，就可以进行下列操作：Strings1;Strings2(“HelloWorld”);s1=s2;Strings3(“;nicetohere!”);s1+=s3;intlen=s1.length();Strings4;s4=s1(6,5);If(s1==s2)…If(s1!=s2)…If(!s1)…Charc=s1[6];s1[6]=‘w’;2022/11/2242文本编辑

计算机应用中要涉及大量的文本文件，文本文件由大量的串（行）组成，在某些文本文件（如源程序）中，串（行）长差异很大，若每行都用等长的串来存贮，则会浪费存贮空间 解决的办法之一是建立一个很大的字符数组作为所有串的共享空间——串值共享空间，再为每个串建立一个描述子，用于描述该串的长度以及该串在串值共享空间中的位置等信息，并将这些描述子存入一顺序表中，参见下图：2022/11/2243

行表(linelist)串值共享空间（space）MaxSize-1....free行号0123

行长位置行2行3行0行1...........自由空间起始地址0串值共享空间——String（串）行表——Seqlist（顺序表）设计行内字符插入、删除操作算法设计整行插入、删除操作算法2022/11/2244第三章链表顺序表有下列缺点：

（1）插入、删除操作时需要移动大量元素， 效率较低； （2）最大表长难以估计，太大了浪费空间， 太小了容易溢出。因此，在插入和删除操作是经常性操作的应用场合选用顺序存储结构不太合适，此时可以选用链式存储结构。 定义：用指针来表示数据元素之间关系的存储结构 称之为链式存储结构。2022/11/2245定义：用由指针连接起来的一串结点来存储一个线性表的存储结构称为线性链式存储结构，简称链表。当每一结点中只有一个指针，并用来表示一个数据元素到其后继元素之间的接续关系，则称这种存储结构为单链表。注：此处的结点是指通过指针型变量动态索取到的存储空间...^firstfirst——头指针指针域(link)lastlast——尾指针数据元素域(data)^——空指针结点1头结点结点0结点n-12022/11/2246

上述的单链表表头设置了一头结点，头结点的数据域中可以为空，或者存放一些辅助数据。设置头结点的目的是为了简化对空表的特殊处理，使得算法更简单、更有效。对于带头结点的单链表，可以很容易地表示空链表：头指针头结点

first^last尾指针2022/11/2247用模板定义的单链表类template<classType>classList;template<classType>classListNode{friendclassList<Type>;public: ListNode(); ListNode(constType&item); ListNode<Type>*NextNode(){returnlink;} voidInsertAfter(ListNode<Type>*p); ListNode<Type>*GetNode(constType&item, ListNode<Type>*next); ListNode<Type>*RemoveAfter();private: Typedata; ListNode<Type>*link;}2022/11/2248template<classType>classList{ public: List(){last=first=newListNode<Type>(value,NULL);} ~List(); voidMakeEmpty(); intLength()const; ListNode<Type>*Find(Typevalue); ListNode<Type>*Find(inti); intInsert(Typevalue,inti); Type*Remove(inti); Type*Get(inti); private: ListNode<Type>*first,*last;}2022/11/2249ListNode<Type>类（链表结点类）的成员函数的实现template<classType>voidListNode<Type>::ListNode():link(NULL){}template<classType>voidListNode<Type>:: ListNode(constType&item)：data(item),link(NULL){}template<classType>voidListNode<Type>:: InsertAfter(ListNode<Type>*p){p->link=link;link=p;}template<classType>ListNode<Type>*ListNode<Type>:: GetNode(constType&item,ListNode<Type>*next=NULL){ ListNode<Type>*newnode=newListNode<Type>(item,next); Returnnewnode;}template<classType>ListNode<Type>*ListNode<Type>:: RemoveAfter(){ListNode<Type>*tempptr=link; If(link==NULL)returnNULL; link=tempptr->link;returntempptr;}2022/11/2250VoidInsertAfter(ListNode<Type)*p):

功能：将p所指的结点（*p）链接成为当前结点（*this） 的后继结点thisdatalinkdatalink…datalinkpp->link=linkLink=p…(1)(2)当前结点2022/11/2251RemoveAfter()datalinkdatalinkdatalink

当前结点要删除的结点功能：删除当前结点(*this)的后继结点,并返回该结点的指针。(1)tempptr(2)link=tempptr->linkthistempptr->link2022/11/2252List<Type>类（链表类）的成员函数的实现template<classType>voidList<Type>::MakeEmpty(){//将当前链表置为空表

ListNode<Type>*q; while(first->link!=NULL) //循环删除头结点的后继结点，直到无后继结点为止

{q=first->link;first->link=q->link;deleteq;} last=first;//最后让last指向头结点，完成置空表操作}first…(1)q=first->link(2)first->link=q->link(最后)last头结点2022/11/2253template<classType>intList<Type>::Insert(Typevalue,inti);{//将值为value的新数据元素插入到链表中结点i之前

ListNode<Type>*p=Find(i-1);//查找结点i-1 if(p==NULL)return0;//结点i-1不存在，插入失败

ListNode<Type>*newnode=GetNode(value,p->link);//创建新结点

//并使新结点指向结点i(1) if(p->link==NULL)last=newnode;//若结点i不存在，则新结点将

//是表尾结点

p->link=newnode;//让结点i-1指向新结点，实现插入(2) return1;}……

结点i-1

结点i

新结点pnewnode(1)(2)2022/11/2254template<classType>Type*List<Type>::Remove(inti){//删除结点i,若成功，则返回该结点的数据元素（地址），

//否则返回NULL ListNode<Type>*p=Find(i-1),*q;//查找结点i-1 if(p==NULL||p->link==NULL)returnNULL;//若结点i-1或者

//结点i不存在，则返回NULL,删除失败

q=p->link;//(1) p->link=q->link;//(2) Typevalue=q->data; if(q==last)last=p; deleteq; return&value;}……结点i-1结点i结点i+1pq(1)(2)2022/11/2255template<classType>ListNode<Type>*List<Type>::Find(inti){//查找结点i,若找到，则返回该结点的指针，否则返回NULL if(i<-1)returnNULL; if(i==-1)returnfirst;//结点–1即为头结点

ListNode<Type>*p=first->link;//p指向结点0 intj=0; while(p!=NULL&&j<i)//从结点0开始顺序向后查找，若第一个//条件不成立，即p=NULL,则说明i值太大，查找失败；//若第二个条件不成立，则存在结点i,查找成功，p即为指向该结//点的指针

{ p=p->link; j=j++; } returnp;}2022/11/22563.1.6单链表的游标(Iterator)类2022/11/2257单链表游标类声明Template<class