《数据结构域算法设计-第二章 线性表及其顺序存储结构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