第二章 线性表及其顺序存储结构ppt课件.ppt

《第二章 线性表及其顺序存储结构ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构第二章线性表及其顺序存储结构7/28/20211引言线性表是一种线性数据结构，其用途非常广泛，可用于信息检索、存储管理、模拟技术和通信等领域。7/28/20212第二章知识点线性数据结构的基本特征和基本运算线性表的顺序存储结构线性数据结构的简单应用难点利用本章的基本知识，设计有效的算法，解决与线性相关的应用问题7/28/20213线性表要求熟练掌握以下内容：线性表的基本运算了解以下内容：线性表运算时间复杂性分析7/28/20214第二章目录2.1线性表的基本概念2.2栈及其应用2.5队列及其应用2.6字符串小结习题与练习7/28/202152.1.1线性表的基本概念线性表是n个(n≥

2、0)同类型数据元素的有限序列。数据元素之间具有线性逻辑关系。“线性”体现在前后件关系上，记作：(a1，a2，…，an)特点：有且仅有一个根元素，它无前件；有且仅有一个终端元素，它无后件；除根元素外，每个元素只有一个前件；除尾元素外，每个元素只有一个后件。n＝0的线性表为空表。predecessorsuccessor7/28/20216线性表实例英文字母表：(A，B，C，D，…，X，Y，Z)某校1998-2003年计算机数量：(50，100，250，300，500，1200)学生信息表：序号学号姓名性别英语英语英语01990301李晓明男数学数学数学02990302张国庆男物理物理物理3099

3、0330王薇薇女868686体现在顺序关系上记录排列为顺序关系7/28/20217线性表的基本运算设：L-表，i-位序，x-数据元素Length(L)//求表的长度Get(1，i)//在位置i处取出一个元素Modify(L，i)//修改表L中位置i处的元素值Delete(L，i)//删除表L中位置i处的元素Insert(L，i，x)//在表L中位置i处插入元素xSort(L，key)//对表L中所有元素按照key排序Index(L，x)//求表L中元素x所在的位置复杂运算：线性表的合并7/28/202182.1.2线性表的顺序存储结构顺序存储结构(SequentialMapping)用内存中

4、一组地址连续的单元，依次存放表中元素。每个元素的存储空间大小相同。计算元素ai的地址假设每个元素占k个字节，首元素的地址为ADR(a1)，则有:顺序存储结构是一种随机存取结构。在高级语言环境中，常用一维数组来存储线性表。ADR(ai)=ADR(a1)+(i-1)k图7/28/20219图：顺序表空闲…nanb+(n-1)size………iaib+(i-1)size………2a2b+size1a1b位序内存状态储存地址7/28/202110实现线性表类模板信息隐蔽、数据抽象、封装templateclasssq_LList{public:sq_LList(){m=n=0}sq_LLi

5、st(int);intflag_sq_LList()const;boolIns_sq_LList(int,T,int,T);boolDel_sq_LList(int);boolprint_sq_LList()const;protected:intm,n;T*v;//容量、长度、首指针};7/28/202111建立一个容量为m的空顺序表C++描述（使用函数模板）usingnamespacestd;templatevoidinit_sq_LList(T*v,intm,intn){v=newT[m];//动态申请存储空间n=0;//顺序表长度为0。}7/28/2021122.1.3

6、线性表的运算插入删除7/28/202113a0a1…ai1.数据元素的插入(insert)插入操作insert(i,x)：在表中下标为i的元素ai后插入x。若i=-1，则将新元素x插在最前面。若插入成功返回true。后移n-i-1个元素01…ii+1i+2…n-1…m-1an-1x…ai+1…动画演示n-17/28/202114插入算法（新元素插入到位置i之后）边界情况处理若存储空间满，判为“上溢”，不能插入，返回false；若i>=n-1时，插到表尾元素之后；若i<0时，插到首元素之前。将尾元素至i+1元素逐一向后移动一个位置。将新元素插入到第i＋1的位置上，并将顺序表长度增加1，返回tr

7、ue。7/28/202115顺序表的插入(C++描述)templateboolsq_LList::ins_sq_LList(inti,Tx){if(n==m){cout<<"OverFlow"<n-1)i=n;for(intj=n-1;j>i;j--)v[j+1]=v[j];v[i]=x;n++;returntrue;