《数据结构域算法设计-第二章 线性表及其顺序存储结构1 课件》由会员分享，可在线阅读，更多相关《数据结构域算法设计-第二章 线性表及其顺序存储结构1 课件（87页珍藏版）》请在金锄头文库上搜索。
1、第二章 线性表及其顺序存储结构1 1引引 言言线性表是一种线性数据结构，其用线性表是一种线性数据结构，其用途非常广泛，可用于信息检索、存途非常广泛，可用于信息检索、存储管理、模拟技术和通信等领域。储管理、模拟技术和通信等领域。2 2第二章 l知 识 点 n线性数据结构的基本特征和基本运算n顺序存储结构n线性数据结构的简单应用 l难 点 n利用本章的基本知识，设计有效的算法，解决与线性相关的应用问题 3 3线性表l要 求 n 熟练掌握以下内容：u线性表的基本运算n 了解以下内容： u线性表运算时间复杂性分析4 4第二章 目录2.1 线性表的基本概念 2.2 栈及其应用2.5 队列及其应用2.6
2、字符串小 结习题与练习5 5第二章 线性表l 逻辑结构l 关系-线性l 存储结构-顺序存储-顺序表6 62.1.1 线性表的基本概念 l线性表: 是n个(表长n0)同类型数据元素的 有限序列。元素间是线性逻辑关系，排成线性序列 。线性体现在前后件关系上。记作： (a1，a2，an) l特点：v有且仅有一个根结点，它无前件；v有且仅有一个终端结点，它无后件；v除根结点外，每个结点只有一个前件；v除尾结点外，每个结点只有一个后件。vn0的线性表为空表。 predecessorpredecessorsuccessorsuccessor7 7线性表实例l 英文字母表：(A，B，C，D，X，Y，Z) l
3、 某校1998-2003年计算机数量(50，100，250，300，500，1200) l 学生信息表序号学号姓名性别别英语语英语语英语语01990301李晓晓明男数学数学数学 02990302张张国庆庆男物理物理物理30990330王薇薇女868686体现在 顺序关系上记录排列为 顺序关系8 8线性表的基本运算 Length(L) Get(1，i ) Modify(L，i) Delete(L，i) Insert(L，i，x) Sort(L，key) Index(L，x)其中：L-表，i-位序，x-数据元素复杂运算 线性表的合并；对有序表的插入、删除等9 92.1.2 线性表的顺序存储结构 l
4、顺序存储结构(Sequential Mapping)用内存中一组地址连续的单元依次存放表中元素， 每个元素的存储空间大小相同。n计算元素 ai 的地址假设每个元素占k个字节，首元素的地址为ADR(a1) ，则有:l 顺序存储结构是一种随机存取结构。 l 在高级语言环境中，常用一维数组来存储线性表。ADR(ai) = ADR(a1) + (i-1) k10102.1.2 线性表的顺序存储结构-顺序表长度为n的线性表: (a1，a2，ai，an).顺序存储结构为:1111有一个长度为8的线性表(29,18,56,63,35,24,31,47)例如:1212顺序表类声明l为更好体现信息隐蔽原则和数据
5、抽象原则，把线 性表封装起来。(使用类模板)template class sq_LList private: int m; /存储空间容量int n; /顺序表的长度T *V; /顺序表存储空间首指针;Vmmnn1313线性表类声明l template class sq_LList public: sq_LList() m=0; n=0 sq_LList( int ); Void Prt_sq_LList();int flag_sq_LList() const; Void Ins_sq_LList(int , T );Void Del_sq_LList(int ) ; ;14142.1.3 线
6、性表的基本运算l 插入 l 删除 1515a a0 0 a a1 1 a ai i1、数据元素的插入l l 插入操作插入操作 l lins_sq_Listins_sq_List(T (T *V,int*V,int m,intm,int *n,int*n,int i, T x) i, T x)：在表中下标为在表中下标为i i的元素的元素a ai i后后插入插入x x。后移后移n-i-1n-i-1个元素个元素0 1 i i+1 i+2 n-1 0 1 i i+1 i+2 n-1 m m-1-1a an-1n-1x xa ai+1i+1操作演示n-11616插入算法描述l （新元素插入到位置 i 之
7、后处）n 边界情况处理u存储空间满(nn=mm)， “上溢”，不能插入，结束u 若 i nn 时，插到表尾元素之后；(最后一个元素)u 若 i Void sq_LList : ins_sq_LList( int i, T x ) int k;if (nn = mm ) cout nn-1 ) i = nn;for ( int k = nn-1; k=i; k- ) vk+1 = vk;v k = x;n+;return ; 18182、数据元素的删除 ai a0 ai-1l l 删除操作删除操作Delete(i)Delete(i)： 删除元素删除元素a ai i。前移n-i-1个元素0 i-1
8、 i i+1 n-1 m-1an-1删除它ai+1ain-1操作演示1919删除l 算法描述（删除位置为i 元素）n 边界情况处理u 若存储空间空，为“下溢”，无删 除，返回；u 若 i n-1 时，待删除 元素不在表中，无删除操作，返回；n将表中i+1元素至尾元素逐一向前移动一 个位置，并将顺序表长度减少1，返回。2020顺序表的删除(C+描述)template bool sq_LList : Del_sq_LList(int i ) int k;if ( nn=0 ) coutnn-1 ) cout class Stack public:virtual bool flag() const=
9、0;virtual bool readTop(T ) const=0;virtual bool push(T )=0;virtual bool pop()=0; virtual bool print() const=0; 3434l 2.2.3 顺序栈类（C+描述）template class SqStack : public Stack private:int mm; / 栈容量int top; /总是指向栈顶元素T *s; / 线性表指针 public:Sq_Stack(int);void Prt_sq_stack()int falg_sq_stack() ;void ins_sq_sta
10、ck(T );T del_sq_stack();T read_sq_stack(); Push(T) Pop( ) top( )3535/入栈template void sq_stack:ins_sq_stack(T x) if (top=mm) /存储空间已满，上溢错误 cout T sq_stack:del_sq_stack() T y;if (top=0) /栈为空，下溢错误 cout T sq_stack:read_sq_stack() if (top=0) /栈为空 cout ,= 4,= 4=,!= 3=,!= 3），则结束整个表达式的计算； 若（该运算符 topp-运算符）， 则
11、将该运算符压入运算符栈； 否则，则从操作数栈连续弹出两个 操作数，从运算符栈弹出topp-运算符，做相 应计算后，将结果压入操作数栈；（注：当前 读出的运算符下次不再重读）。4444AB*CD/E计算过程4545AB*CD/E计算过程4646AB*CD/E计算过程4747AB*CD/E计算过程4848例：表达式 A+B*C-D/E 的计算过程OPSOPSOVSOVS/-DECB*+A;TOPvTOPp+* ? ? 运算符比较：运算符比较： ()表达式表达式 ：真真-*假假 计算：计算：T2 = A + T1T1/T2T1 = B * C；;-T3 = D / ET3/T4 = T2 T3T4;
12、=结果：T4开始：构造堆栈开始：构造堆栈读符号进栈：读符号进栈：A A 、 + + 、B B读符号：读符号：* *读符号：读符号：C C读符号：读符号：- -再判符号：再判符号：- -读符号：读符号：D D、/ /读符号：读符号：E E、; ;再判符号：再判符号：; ;再次判别符号：再次判别符号：; ;4949带括号的表达式计算l例： A * ( B + C / D ) E * F请学生画出图，分析堆栈中数据变化。5050例2.5：编写一个程序，从键盘输入一个 表达式字符串，其中包括数值子字符串以 及+、-、*、/四个运算符号与左右括号， 然后计算并输出该表达式的值。（假设， 输入的字符串长度
13、不超过60）。l书中P49-P50lC+程序51512.3 队列（Queue）52522.3.1 队列概念 l队列的定义队列(queue)是在一端进行插入，在另一端进行删 除操作的线性表。First In First Out - FIFOa1a2a3a4a5 出队出队进队进队队头队头 队尾队尾QueueQueue53532.3.2 队列的运算和声明lInsQ(x)：在队列尾部插入一个新元素x。 lDelQ()：删除队列中队首元素。 lEmptyQ()：测试队列是否为空,为空时返回一个真值，否则返回一个假值。 lFrontQ()： 取得队列中队首元素。 lSetNULL(Q)：创建一个空队列Q。
14、 5454队列类模板（C+描述）template class Queue public:virtual bool ins_Queue(const T )=0; virtual bool del_Queue()=0;virtual bool prt_Queue(T virtual bool flag_Queue() const=0; ;5555顺序队列类模板template class sq_Queue : public Queue public:sq_Queue( int );bool flag_Queue() const； bool prt_Queue (Tbool ins_Queue (T
15、 x);bool del_Queue ();private:int front, rear, n ; T *q; ;56562.3.3 循环队列及其运算l 把队列空间从逻辑上看成是一个首尾相连的环。 l 如何判断一个循环队列是满还是空？ frontfront rearrear5 54 40 01 12 23 3a6a6a5a5a1a1a7a7a4a4 a3a3 a2a2 队列空队列满l 逻辑上循环：front=(front+1)%6; fear=(rear+1)%65757如何判断循环队列是空？是满？l判满条件(设n=6)：l l判空条件：判空条件：5 54 40 01 12 23 3frontfront rearrear5 54 40 01 12 23 3a1a2
