C++程序设计与数据结构基础：第9章 线性结构

1、第三部分第三部分 数据结构基础数据结构基础本章内容 数据结构概述 线性表 栈 队列2 2l几个常用术语： 数据：计算机能够识别、存储和处理的符号的集合。 数据元素：数据的基本单位，由一或多个数据项组成。又称结点、顶点、记录、表目等。 数据项：具有独立含义的数据的最小单位，又称为域、字段。 数据对象：具有相同性质的数据元素集合。9.1数据结构概述3 3 例1：英文字母表 A,B.Z 数据对象是整个英文字母表，数据元素是字母字符，每个数据元素只由一个数据项组成。 例2：职工情况表 职工情况表是一个数据对象，每个职工情况为一数据元素，数据元素由多个数据项组成4 4数据结构的概念包括三方面的内容数据数

2、据结构结构数据的逻辑结构集合线性树图数据的存储结构顺序链接索引散列数据的运算插入插入删除删除查找查找更新更新排序排序5 5数据的逻辑结构l数据的逻辑结构只抽象地反映出数据元素之间的逻辑关系，它与数据的存储无关，是独立于计算机的。 集合结构：在集合结构中，数据元素之间的关系是“属于同一集合”，集合是元素关系极为松散的一种结构。 线性结构：除第一个和最后一个元素外，其他每个元素都仅有一个直接前驱元素和一个直接后继元素。 树形结构：每个元素若有直接前驱元素（前件），只能有一个，但可以有多个直接后继元素（后件）。 图形结构：每个元素都可以有多个前件和多个后件。6 6数据的存储结构l 数据的存储结构是逻

3、辑结构在计算机内存储器中的实现。l 四种基本的存储映象方式： 顺序方式 链接方式 索引方式 散列方式7 7顺序方式l 将数据元素按照某种顺序存放到一片连续的存储单元内，数据元素之间的逻辑关系是通过它们在存储器中的相对位置来体现的。l 例：英语字母表的顺序存储。ABCXYZl 优点： 存储密度高。 可对元素随机访问。l 缺点： 插入或删除元素时效率低。 存储空间需预先分配，太大浪费，太小溢出。8 8线性表的插入9 929185663352431470 x1234FB000 x1234FB040 x1234FB080 x1234FB0C0 x1234FB100 x1234FB140 x1234FB

4、180 x1234FB1C0 x1234FB200 x1234FB24392918566339352431470 x1234FB000 x1234FB040 x1234FB080 x1234FB0C0 x1234FB100 x1234FB140 x1234FB180 x1234FB1C0 x1234FB200 x1234FB2429185663352431470 x1234FB000 x1234FB040 x1234FB080 x1234FB0C0 x1234FB100 x1234FB140 x1234FB180 x1234FB1C0 x1234FB200 x1234FB24296335245

5、631470 x1234FB000 x1234FB040 x1234FB080 x1234FB0C0 x1234FB100 x1234FB140 x1234FB180 x1234FB1C0 x1234FB200 x1234FB24线性表的删除101029185663352431472918566335243147392918566335243147链表的插入和删除1111链接方式l 逻辑上相邻的元素在物理位置上未必相邻，元素间的逻辑关系由附加的指针域表示。l 例：链接方式存储的线性结构第一个职工情况第一个职工情况第二个职工情况第二个职工情况最后一个职工情况最后一个职工情况headl 优点： 插

6、入和删除元素时，不会引起大量元素的移动。 可动态申请和释放结点空间。l 缺点： 每个结点中的指针域会耗费一些存储空间。 不能实现对数据元素的随机访问。1212索引方式l 在存储数据元素的同时，建立一个附加的索引表，索引表中的每一行称为一个索引项。l 其一般形式为：（关键字，地址） 关键字：是指能够唯一标识一个数据元素的一个或多个数据项。例如，职工情况表中的“职工号”。l 优点：检索速度快。l 缺点： 增加的索引表会占用较多的存储空间； 在插入和删除数据元素时需要修改索引表，因而会花费更多的时间。1313散列方式l 数据元素的存储地址是用它的关键字计算出来的l 散列方式又称为哈希表、杂凑表等。l

7、 优点：检索、增加和删除元素的操作都很快。l 缺点：如果使用了不好的散列函数，可能会出现存储单元的冲突，为解决冲突需要额外的时间和空间开销。补充：四种存储方式可以组合使用。u如硬盘文件的组织采用顺序和链接结合方式。同一逻辑结构可以采用不同的存储方式，生成不同的数据结构。1414数据的运算l 数据的运算是对数据结构中的数据所进行的加工和处理。l 常用的数据运算包括插入、删除、查找、排序、更新等。l 数据的运算定义在逻辑结构之上，实现在存储结构之上。用算法描述。 算法是对解决问题方法的精确描述，是用来完成某个特定任务的有限步骤序列。1515算法的基本特征1.有穷性：一个算法必须在执行有穷步后结束，

8、并且每一步都能在有限的时间内完成。2.确定性：算法中的每一条指令必须具有确切的含义，且无二义性。3.可行性：算法中描述的所有操作都可以通过让已实现的基本运算执行有限次完成。4.输入：一个算法应该有0个或多个输入。这些输入应取自于某个特定的对象集合。5.输出：一个算法应该有一个或多个输出。这些输出是与输入有某种特定关系的量。1616算法的描述l 自然语言描述、算法语言、程序设计语言（如C+）描述、流程图描述等。算法的评价l 算法的时间复杂度：根据算法编写出的程序在计算机上运行时所消耗的时间。一般把程序运行时（基本）语句的执行次数作为估算程序执行时间的量度。l 算法的空间复杂度：根据算法编写出的程

9、序在计算机上运行时所需要的存储空间的大小。包括指令、常量、变量所占用的空间；输入数据占据的空间；程序执行时需要使用的辅助空间。17179.2线性表l 通常所说的线性表是指其逻辑结构。是由（0）个相同类型的数据元素e0、e1、en-1 组成的有限序列 。可抽象的表示为：（e0，e1，ei-1，ei，ei+1，en-1） 开始元素 中间元素 终端元素 线性表中元素的个数称为表的长度。长度为0的表为空表。元素在表中的序号称做元素的下标。1818线性表的存储结构l 以顺序方式存储的线性表称为顺序表。 可以用一维数组实现顺序表。例如英文字母表的顺序存储。char table26;l 以链接方式存储的线性

10、表称为链表。 常用链表形式有单链表、循环链表和双链表等。线性表常用的基本运算l 创建一个空表；判表空；求表长；l 删除下标为i的数据元素；删除表中所有元素；l 在下标为i的元素之前插入一个新的数据元素；l 取下标为i的数据元素；在表中查找与给定值x相等的数据元素。19192020#include #include #include #include using namespace std;using namespace std;class class SeqListSeqList public:public: SeqListSeqList( (intint m=10); m=10); / /构

11、造函数构造函数 SeqListSeqList()delete element;()delete element;/ /析构函数析构函数 boolbool IsEmptyIsEmpty()return length=0;()return length=0;/ /判表是否为空判表是否为空 intint Length()return length; Length()return length;/ /返回表长返回表长 boolbool Find( Find(intint i i, , intint &x); &x); / /把下标为把下标为i i的元素取至的元素取至x x intint

12、 Search( Search(constconst intint &x); &x); / /返回返回x x在表中的下标在表中的下标 void Insert(void Insert(intint i i, , constconst intint &x); &x); / /在下标在下标i i处插入元素处插入元素x x void Delete( void Delete(intint i i, , intint &x); &x); / /返回下标为返回下标为i i的元素至的元素至x x，并删除之，并删除之 void void ClearListClea

13、rList()length=0;()length=0;/ /将表清空将表清空 void Output(void Output(ostreamostream &out); &out); / /输出表中所有元素的值输出表中所有元素的值 friend friend ostreamostream& operator(& operator(ostreamostream &out, &out, SeqListSeqList &x); &x); private:private:intint MaxsizeMaxsize, length;, le

14、ngth;intint * *element;element; ;/ /构造函数：构造函数：/ /建立一个空表建立一个空表SeqListSeqList:SeqList(int m):SeqList(int m) element=new element=new intintm;m; Maxsize=m; Maxsize=m; length=0; length=0; /Find()/Find()函数：函数：boolbool SeqListSeqList:Find(:Find(intint i i, , intint &x) &x) if( if(i i0|length-1)leng

15、th-1)return false;return false; x=element x=elementi i; ; return true; return true; /Search()/Search()函数：函数：intint SeqListSeqList:Search(:Search(constconst intint &x) &x) for( for(intint i i=0;i=0;ilength;ilength;i+)+) if(element if(elementi i=x) return =x) return i i; ; return -1; return -1

16、; /Insert()/Insert()函数：函数：voidvoid SeqListSeqList:Insert(:Insert(intint i i, , constconst intint &x) &x) if( if(i i0|length)length) coutcout下标越界下标越界n;n; if(length= if(length=MaxsizeMaxsize) ) coutcout= k=length-1; k=i i; k-) ; k-) elementk+1=elementk; elementk+1=elementk; element elementi i=

17、x;=x; length+; length+; /Delete()/Delete()函数：函数：voidvoid SeqListSeqList:Delete(:Delete(intint i i, , intint &x) &x) if(Find( if(Find(i,xi,x) ) for( for(intint k= k=i;ki;klength-1;k+)length-1;k+) elementk=elementk+1; elementk=elementk+1; length-; length-; else else coutcout下标越界下标越界n;n; /Outpu

18、t()/Output()函数：函数：voidvoid SeqListSeqList: : Output(Output(ostreamostream &out) &out) for( for(intint i i=0;i=0;ilength;ilength;i+)+) outelement outelementi i ; ; / /友元方式重载友元方式重载 “” “”：ostreamostream& operator(& operator(ostreamostream &out, &out, constconst SeqListSeqList &a

19、mp;x) &x) x.Outputx.Output(out);(out); return out; return out; / /友元方式重载友元方式重载 “” “”：ostreamostream& operator(& operator(ostreamostream &out, &out, constconst SeqListSeqList &x) &x) for(for(intint i i=0;i=0;ix.length;ix.length;i+)+) out outx.elementx.element i i ; ;return

20、 out;return out; / /重载为成员函数行不行？重载为成员函数行不行？SeqListSeqList & & SeqListSeqList:operator(:operator(ostreamostream &out) &out) for(for(intint i i=0;i=0;ilength;ilength;i+)+) outelement outelementi i ; ; 会有什么问题么？会有什么问题么？调用时：调用时：l 不能写成：不能写成：coutcoutx;x;l 只能写成：只能写成：xxcoutcout; ;线性表的链接存储结构（链表

21、）l 单链表中的结点：l 单链表：datanextl 带头结点的单链表：在一般形式的单链表中进行插入、删除操作时，必须针对不同的情况采取不同的处理方法，这为编写程序带来一定的难度和潜在的危险。在带头结点的单链表中进行插入、删除操作时，无须考虑特殊情况。l 空表 2121结点类的定义2222#include #include #include #include using namespace std;using namespace std;class Chain;class Chain; / /单链表类单链表类ChainChain的前视声明的前视声明class class NodeNode/ /

22、单链表结点类的定义单链表结点类的定义 friend class Chain;friend class Chain; / /定义类定义类ChainChain为友元为友元private:private: intint data; data;/ /结点的数据域结点的数据域 Node Node * *next;next;/ /结点的指针域结点的指针域; ;2323class class ChainChain/ /单链表类的定义单链表类的定义 publicpublic: :Chain();Chain();Chain();Chain();boolbool IsEmptyIsEmpty() return l

23、ength=0; () return length=0; intint Length() return length; Length() return length; boolbool Find( Find(intint i,inti,int &x); &x);intint Search( Search(constconst intint &x); &x); void Insert(void Insert(intint i,consti,const intint &x); &x); void Delete(void Delete(intint i

24、,inti,int &x); &x);void void ClearListClearList();(); void Output(void Output(ostreamostream &out)const; &out)const; friend friend ostreamostream& operator(& operatornext=NULL; head-next=NULL; length=0; length=0; / /析构函数：析构函数：Chain:Chain()Chain:Chain() ClearListClearList();()

25、;delete head;delete head; /Find()/Find()函数：函数：boolbool Chain:Find( Chain:Find(intint i i, , intint &x) &x) if(if(i i0|length-1) return false;length-1) return false;Node Node * *p=head-next;p=head-next;intint k=0; k=0;while(kwhile(knext;p=p-next;k+;k+; x=p-data;x=p-data;return true;return tru

26、e; /Search()/Search()函数：函数：intint Chain:Search( Chain:Search(constconst intint &x) &x) Node Node * *p=head-next;p=head-next;intint i i=0;=0;while(p!=NULL)while(p!=NULL) if(p-data=x) return if(p-data=x) return i i; ;p=p-next;p=p-next;i i+;+; return -1;return -1; void Chain:Insert(void Chain:I

27、nsert(intint i i, , constconst intint &x) &x) if(if(i i0|length)length)coutcout下标越界下标越界n;n; Node Node * *p=head;p=head;intint k=0; k=0;/ /找到第找到第i-1i-1个结点个结点while(knext; k+; while(knext; k+; / /生成新结点生成新结点Node Node * *q=new Node;q=new Node;q-data=x;q-data=x;q-next=p-next;q-next=p-next;p-next=q

28、;p-next=q;length+;length+; void Chain:Delete(void Chain:Delete(intint i i, , intint &x) &x) if(if(i i0|length)length)coutcout下标越界下标越界n;n;/ /找到第找到第i-1i-1个结点个结点 Node Node * *p=head;p=head;for(for(intint k=0;k k=0;knext;+)p=p-next;/ /找到要删除的结点找到要删除的结点Node Node * *q=p-next; q=p-next; x=q-data; x=

29、q-data; / /保存删除结点的值保存删除结点的值p-next=q-next;p-next=q-next;/ /改变第改变第i-1i-1个结点指针域个结点指针域delete q; delete q; / /删除结点删除结点length-;length-; / /ClearListClearList() ()函数清空表函数清空表void Chain:void Chain:ClearListClearList() () Node Node * *p=head-next, p=head-next, * *q;q;while(p!=NULL)while(p!=NULL) q=p;q=p;p=p-n

30、ext;p=p-next;delete q;delete q; head-next=NULL; head-next=NULL; length=0;length=0; /Output()/Output()函数：函数：void Chain:void Chain: Output(utput(ostreamostream &out) &out) Node Node * *p=head-next;p=head-next;while(p!=NULL)while(p!=NULL) outdatanext; outdatanext; / /友元方式重载友元方式重载 “” “”：ostreamo

31、stream& operator(& operator(ostreamostream &out, Chain &x) &out, Chain &x) x.outputx.output(out);(out); return out; return out; 其它形式的链表l 单循环链表l 设置尾指针的单循环链表l 双链表l 双循环链表24249.3栈（STACK）l 栈的定义：只能在一端进行插入和删除运算的线性表。l 栈的特点：后进先出原则（Last In First Out，LIFO） 。l 术语： 栈顶 栈底 入栈 出栈2525栈的基本运算l 入栈、出栈、判栈空、取栈顶元素、置栈空abcabcacbacbbacbacbcabcacabcabcbacba 栈的入栈和出栈操作可以穿插进行，所以对应于相同的入栈序列其出栈序列可以有多种。 讨论：入栈序列为abc，出栈序列有多少种可能？ cabefd和efdcab 等均为不可能出现的出栈序列。2626顺序栈l 以顺序方式存储的栈称为顺序栈。l 顺序栈可以用一维数组实现。l 需要一个整型变量top指示当前栈顶位置 。l 当使用两个栈时，可让它们共享一个一维数组空间，以达到节省存储空间和