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

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

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

2、1.1线性表的基本概念线性表:是n个(表长n≥0)同类型数据元素的有限序列。元素间是线性逻辑关系，排成线性序列。线性体现在前后件关系上。记作：(a1，a2，…，an)特点：有且仅有一个根结点，它无前件；有且仅有一个终端结点，它无后件；除根结点外，每个结点只有一个前件；除尾结点外，每个结点只有一个后件。n＝0的线性表为空表。predecessorsuccessor7线性表实例英文字母表：(A，B，C，D，…，X，Y，Z)某校1998-2003年计算机数量(50，100，250，300，500，1200)学生信息表序号

3、学号姓名性别英语英语英语01990301李晓明男数学数学数学02990302张国庆男物理物理物理30990330王薇薇女868686体现在顺序关系上记录排列为顺序关系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-数据元素复杂运算线性表的合并；对有序表的插入、删除等92.1.2线性表的顺序存储结构顺序存储结构(SequentialMapping)用内存中一组地址连续的单元依

4、次存放表中元素，每个元素的存储空间大小相同。计算元素ai的地址假设每个元素占k个字节，首元素的地址为ADR(a1)，则有:顺序存储结构是一种随机存取结构。在高级语言环境中，常用一维数组来存储线性表。ADR(ai)=ADR(a1)+(i-1)k102.1.2线性表的顺序存储结构-顺序表长度为n的线性表:(a1，a2，…，ai，…，an).顺序存储结构为:11有一个长度为8的线性表(29,18,56,63,35,24,31,47)例如:12顺序表类声明为更好体现信息隐蔽原则和数据抽象原则，把线性表封装起来。(使用类模板

5、)templateclasssq_LList{private:intm;//存储空间容量intn;//顺序表的长度T*V;//顺序表存储空间首指针};······V→mmnn13线性表类声明templateclasssq_LList{public:sq_LList(){m=0;n=0}sq_LList(int);VoidPrt_sq_LList();intflag_sq_LList()const;VoidIns_sq_LList(int,T);VoidDel_sq_LList(int

6、);};142.1.3线性表的基本运算插入删除15a0a1…ai1、数据元素的插入插入操作ins_sq_List(T*V,intm,int*n,inti,Tx)：在表中下标为i的元素ai后插入x。后移n-i-1个元素01…ii+1i+2…n-1…m-1an-1x…ai+1…操作演示n-116插入算法描述（新元素插入到位置i之后处）边界情况处理存储空间满(nn=mm)，“上溢”，不能插入，结束若i>nn时，插到表尾元素之后；(最后一个元素)若i<1时，插到首元素(第1个元素)之前。将尾元素nn-1至i+1元素逐一向后

7、移动一个位置。将新元素插入到第i＋1的位置上，并将顺序表长度增加1。17顺序表的插入(C++描述)templateVoidsq_LList::ins_sq_LList(inti,Tx){intk;if(nn==mm){cout<<"OverFlow"<nn-1)i=nn;for(intk=nn-1;k>=i;k--)v[k+1]=v[k];v[k]=x;n++;return;}182、数据元素的删除aia0…ai-1删除操作Delet

8、e(i)：删除元素ai。前移n-i-1个元素0…i-1ii+1…n-1m-1an-1……删除它ai+1ain-1操作演示19删除算法描述（删除位置为i元素）边界情况处理若存储空间空，为“下溢”，无删除，返回；若i<0orI>n-1时，待删除元素不在表中，无删除操作，返回；将表中i+1元素至尾元素逐一向前移动一个位置，并将顺序表长度减少1，返回。20顺序表的删