《C++程序设计与数据结构基础：第9章 线性结构》由会员分享，可在线阅读，更多相关《C++程序设计与数据结构基础：第9章 线性结构（33页珍藏版）》请在金锄头文库上搜索。
1、第三部分第三部分 数据结构基础数据结构基础第九章 线性结构本章内容 数据结构概述 线性表 栈 队列2l几个常用术语：数据：计算机能够识别、存储和处理的符号的集合。 数据元素：数据的基本单位，由一或多个数据项组成。又称结点、顶点、记录、表目等。数据项：具有独立含义的数据的最小单位，又称为域、字段。数据对象：具有相同性质的数据元素集合。9.1数据结构概述3例1：英文字母表 A,B.Z 数据对象是整个英文字母表，数据元素是字母字符，每个数据元素只由一个数据项组成。例2：职工情况表 职工情况表是一个数据对象，每个职工情况为一数据元素，数据元素由多个数据项组成4数据结构的概念包括三方面的内容数据数据结构
2、结构数据的逻辑结构集合线性树图数据的存储结构顺序链接索引散列数据的运算插入插入删除删除查找查找更新更新排序排序5数据的逻辑结构l数据的逻辑结构只抽象地反映出数据元素之间的逻辑关系，它与数据的存储无关，是独立于计算机的。集合结构：在集合结构中，数据元素之间的关系是“属于同一集合”，集合是元素关系极为松散的一种结构。线性结构：除第一个和最后一个元素外，其他每个元素都仅有一个直接前驱元素和一个直接后继元素。树形结构：每个元素若有直接前驱元素（前件），只能有一个，但可以有多个直接后继元素（后件）。图形结构：每个元素都可以有多个前件和多个后件。6数据的存储结构l数据的存储结构是逻辑结构在计算机内存储器中
3、的实现。l四种基本的存储映象方式：顺序方式链接方式索引方式散列方式7顺序方式l将数据元素按照某种顺序存放到一片连续的存储单元内，数据元素之间的逻辑关系是通过它们在存储器中的相对位置来体现的。l例：英语字母表的顺序存储。ABCXYZl优点：存储密度高。可对元素随机访问。l缺点：插入或删除元素时效率低。存储空间需预先分配，太大浪费，太小溢出。8线性表的插入929185663352431470x1234FB000x1234FB040x1234FB080x1234FB0C0x1234FB100x1234FB140x1234FB180x1234FB1C0x1234FB200x1234FB24392918
4、566339352431470x1234FB000x1234FB040x1234FB080x1234FB0C0x1234FB100x1234FB140x1234FB180x1234FB1C0x1234FB200x1234FB2429185663352431470x1234FB000x1234FB040x1234FB080x1234FB0C0x1234FB100x1234FB140x1234FB180x1234FB1C0x1234FB200x1234FB24296335245631470x1234FB000x1234FB040x1234FB080x1234FB0C0x1234FB100x1234
5、FB140x1234FB180x1234FB1C0x1234FB200x1234FB24线性表的删除1029185663352431472918566335243147392918566335243147链表的插入和删除11链接方式l逻辑上相邻的元素在物理位置上未必相邻，元素间的逻辑关系由附加的指针域表示。l例：链接方式存储的线性结构第一个职工情况第一个职工情况第二个职工情况第二个职工情况最后一个职工情况最后一个职工情况headl优点：插入和删除元素时，不会引起大量元素的移动。可动态申请和释放结点空间。l缺点：每个结点中的指针域会耗费一些存储空间。不能实现对数据元素的随机访问。12索引方式l在
6、存储数据元素的同时，建立一个附加的索引表，索引表中的每一行称为一个索引项。l其一般形式为：（关键字，地址）关键字：是指能够唯一标识一个数据元素的一个或多个数据项。例如，职工情况表中的“职工号”。l优点：检索速度快。l缺点：增加的索引表会占用较多的存储空间；在插入和删除数据元素时需要修改索引表，因而会花费更多的时间。13散列方式l数据元素的存储地址是用它的关键字计算出来的l散列方式又称为哈希表、杂凑表等。l优点：检索、增加和删除元素的操作都很快。l缺点：如果使用了不好的散列函数，可能会出现存储单元的冲突，为解决冲突需要额外的时间和空间开销。补充：四种存储方式可以组合使用。u如硬盘文件的组织采用顺
7、序和链接结合方式。同一逻辑结构可以采用不同的存储方式，生成不同的数据结构。14数据的运算l数据的运算是对数据结构中的数据所进行的加工和处理。l常用的数据运算包括插入、删除、查找、排序、更新等。l数据的运算定义在逻辑结构之上，实现在存储结构之上。用算法描述。算法是对解决问题方法的精确描述，是用来完成某个特定任务的有限步骤序列。15算法的基本特征1.有穷性：一个算法必须在执行有穷步后结束，并且每一步都能在有限的时间内完成。2.确定性：算法中的每一条指令必须具有确切的含义，且无二义性。3.可行性：算法中描述的所有操作都可以通过让已实现的基本运算执行有限次完成。4.输入：一个算法应该有0个或多个输入。
8、这些输入应取自于某个特定的对象集合。5.输出：一个算法应该有一个或多个输出。这些输出是与输入有某种特定关系的量。16算法的描述l自然语言描述、算法语言、程序设计语言（如C+）描述、流程图描述等。算法的评价l算法的时间复杂度：根据算法编写出的程序在计算机上运行时所消耗的时间。一般把程序运行时（基本）语句的执行次数作为估算程序执行时间的量度。l算法的空间复杂度：根据算法编写出的程序在计算机上运行时所需要的存储空间的大小。包括指令、常量、变量所占用的空间；输入数据占据的空间；程序执行时需要使用的辅助空间。179.2线性表l通常所说的线性表是指其逻辑结构。是由（0）个相同类型的数据元素e0、e1、en
9、-1 组成的有限序列 。可抽象的表示为：（e0，e1，ei-1，ei，ei+1，en-1） 开始元素 中间元素 终端元素 线性表中元素的个数称为表的长度。长度为0的表为空表。元素在表中的序号称做元素的下标。18线性表的存储结构l以顺序方式存储的线性表称为顺序表。可以用一维数组实现顺序表。例如英文字母表的顺序存储。char table26;l以链接方式存储的线性表称为链表。常用链表形式有单链表、循环链表和双链表等。线性表常用的基本运算l创建一个空表；判表空；求表长；l删除下标为i的数据元素；删除表中所有元素；l在下标为i的元素之前插入一个新的数据元素；l取下标为i的数据元素；在表中查找与给定值x
10、相等的数据元素。1920#include #include using namespace std;class SeqListpublic: SeqList(int m=10); /构造函数构造函数 SeqList()delete element;/析构函数析构函数 bool IsEmpty()return length=0;/判表是否为空判表是否为空 int Length()return length;/返回表长返回表长 bool Find(int i, int &x); /把下标为把下标为i的元素取至的元素取至x int Search(const int &x); /返回返回x在表中的下标
11、在表中的下标 void Insert(int i, const int &x); /在下标在下标i处插入元素处插入元素x void Delete(int i, int &x); /返回下标为返回下标为i的元素至的元素至x，并删除之，并删除之 void ClearList()length=0;/将表清空将表清空 void Output(ostream &out); /输出表中所有元素的值输出表中所有元素的值 friend ostream& operator(ostream &out, SeqList &x); private:int Maxsize, length;int *element;/构
12、造函数：构造函数：/建立一个空表建立一个空表SeqList:SeqList(int m) element=new intm; Maxsize=m; length=0;/Find()函数：函数：bool SeqList:Find(int i, int &x) if(ilength-1)return false; x=elementi; return true;/Search()函数：函数：int SeqList:Search(const int &x) for(int i=0;ilength;i+) if(elementi=x) return i; return -1;/Insert()函数：函
13、数：void SeqList:Insert(int i, const int &x) if(ilength) cout下标越界下标越界n; if(length=Maxsize) cout=i; k-) elementk+1=elementk; elementi=x; length+;/Delete()函数：函数：void SeqList:Delete(int i, int &x) if(Find(i,x) for(int k=i;klength-1;k+) elementk=elementk+1; length-; else cout下标越界下标越界n;/Output()函数：函数：void
14、SeqList: Output(ostream &out) for(int i=0;ilength;i+) outelementi ;/友元方式重载友元方式重载 “”：ostream& operator(ostream &out, const SeqList &x) x.Output(out); return out;/友元方式重载友元方式重载 “”：ostream& operator(ostream &out, const SeqList &x) for(int i=0;ix.length;i+) outx.elementi ;return out;/重载为成员函数行不行？重载为成员函数行不
15、行？SeqList & SeqList:operator(ostream &out) for(int i=0;ilength;i+) outelementi ;会有什么问题么？会有什么问题么？调用时：调用时：l不能写成：不能写成：coutx;l只能写成：只能写成：xcout;线性表的链接存储结构（链表）l单链表中的结点：l单链表：datanextl带头结点的单链表：在一般形式的单链表中进行插入、删除操作时，必须针对不同的情况采取不同的处理方法，这为编写程序带来一定的难度和潜在的危险。在带头结点的单链表中进行插入、删除操作时，无须考虑特殊情况。l空表 21结点类的定义22#include #in
16、clude using namespace std;class Chain; /单链表类单链表类Chain的前视声明的前视声明class Node/单链表结点类的定义单链表结点类的定义 friend class Chain; /定义类定义类Chain为友元为友元private: int data;/结点的数据域结点的数据域 Node *next;/结点的指针域结点的指针域;23class Chain/单链表类的定义单链表类的定义public:Chain();Chain();bool IsEmpty() return length=0; int Length() return length; b
17、ool Find(int i,int &x);int Search(const int &x); void Insert(int i,const int &x); void Delete(int i,int &x);void ClearList(); void Output(ostream &out)const; friend ostream& operatornext=NULL; length=0;/析构函数：析构函数：Chain:Chain() ClearList();delete head;/Find()函数：函数：bool Chain:Find(int i, int &x)if(ile
18、ngth-1) return false;Node *p=head-next;int k=0;while(knext;k+;x=p-data;return true;/Search()函数：函数：int Chain:Search(const int &x) Node *p=head-next;int i=0;while(p!=NULL)if(p-data=x) return i;p=p-next;i+;return -1;void Chain:Insert(int i, const int &x) if(ilength)cout下标越界下标越界n; Node *p=head;int k=0;/
19、找到第找到第i-1个结点个结点while(knext; k+; /生成新结点生成新结点Node *q=new Node;q-data=x;q-next=p-next;p-next=q;length+;void Chain:Delete(int i, int &x) if(ilength)cout下标越界下标越界n;/找到第找到第i-1个结点个结点 Node *p=head;for(int k=0;knext;/找到要删除的结点找到要删除的结点Node *q=p-next; x=q-data; /保存删除结点的值保存删除结点的值p-next=q-next;/改变第改变第i-1个结点指针域个结点指
20、针域delete q; /删除结点删除结点length-;/ClearList()函数清空表函数清空表void Chain:ClearList()Node *p=head-next, *q;while(p!=NULL)q=p;p=p-next;delete q;head-next=NULL; length=0;/Output()函数：函数：void Chain: Output(ostream &out)Node *p=head-next;while(p!=NULL) outdatanext; /友元方式重载友元方式重载 “”：ostream& operator(ostream &out, Ch
21、ain &x) x.output(out); return out;其它形式的链表l单循环链表l设置尾指针的单循环链表l双链表l双循环链表249.3栈（STACK）l栈的定义：只能在一端进行插入和删除运算的线性表。l栈的特点：后进先出原则（Last In First Out，LIFO） 。l术语：栈顶栈底入栈出栈25栈的基本运算l入栈、出栈、判栈空、取栈顶元素、置栈空abcacbbacbcacabcba栈的入栈和出栈操作可以穿插进行，所以对应于相同的入栈序列其出栈序列可以有多种。讨论：入栈序列为abc，出栈序列有多少种可能？cabefd和efdcab 等均为不可能出现的出栈序列。26顺序栈l以
22、顺序方式存储的栈称为顺序栈。l 顺序栈可以用一维数组实现。l 需要一个整型变量top指示当前栈顶位置 。l当使用两个栈时，可让它们共享一个一维数组空间，以达到节省存储空间和降低上溢发生频率的目的。28a034a115a243a3a4a5a6a7a8a9栈底底栈顶top=3栈顶top=455a0a1a2a3a4a543a615a734a828a9栈底底栈顶top=10-455栈顶top=10-527链式栈l以链接方式存储的栈称为链式栈。l可以用不带头结点的单链表实现链式栈。l用头指针top指示当前栈顶位置 。 C B Atop D289.4队列（QUEUE）l队列的定义：在一端进行插入，另一端进
23、行删除的线性表。l队列的特点：先进先出原则（ First In First Out，FIFO） 。l术语：队头（front）队尾（rear）入队出队29队列的基本运算l入队、出队、判队空、取队头元素、置队空顺序队列l顺序方式存储的队列称为顺序队列。l顺序队列可以用一维数组实现。l设置整型变量 front（队头指示器）指示当前队头，设置整型变量 rear（队尾指示器） 指示将要入队元素所在的位置 。28a034a115a243a355a467a5a6a7a8a9队头front对尾尾rear5528328821341530l顺序队列会出现假溢出问题，即存储队列的空间中还有空余，但不能进行入队操作，
24、它是由队列的操作方式决定的 。l解决假溢出问题的三种方法。1.建立一个足够大的存储空间，但这样会造成空间的浪费。2.采用平移元素的方法。每当出现“假溢出”时，将队列中所有元素平移，使当前队头元素位于数组的最前端，并修改队头和队尾指示器。此方法效率很低。 3.采用循环队列方式。把存储队列的一维空间看成是一个首尾相接的圆环，这样就可以实现对由于元素出队而空出来的空间的循环使用。31讨论：在实现循环顺序队列时，如果不使用count，可以利用front和rear的值判断“队空”和“队满”：(设m是队列空间能容纳的元素个数） 队空时： front=rear 队满时：(rear+1)%m=front 队列长度：(m+rear-front)%m28a034a115a2a3a4a5a6a7a8a955328821a0a1a243a355a467a5a6a7a8a9frontrearrearfront32链式队列l以链接方式存储的队称为链式队。l链式队可以用只允许在表头删除和在表尾插入的单链表实现。l 设置指向队头结点的指针变量 front和指向队尾结点的指针变量 rear。frontrear33
