《数据结构域算法设计-第2章 线性表1-顺序表示 课件》由会员分享，可在线阅读，更多相关《数据结构域算法设计-第2章 线性表1-顺序表示 课件（29页珍藏版）》请在金锄头文库上搜索。
1、数据结构讲义 第2章 线性表, 顺序表示,知识点 线性表的逻辑结构定义和各种存储结构的描述方法； 在线性表的两类存储结构（即顺序表和链表）上如何实现基本运算。,难点 单链表的基本操作 双链表的基本操作,2.1 线性表的类型定义,线性表的基本概念 抽象数据类型线性表的定义(*) 对抽象数据类型线性表的复杂操作(*),（a1, a2, ai-1，ai, ai1 ，, an）,线性表的基本概念,线性表的定义：是n个数据元素的有限序列,n=0时称为,数据元素,线性起点,ai的直接前趋,ai的直接后继,下标，是元素的序号，表示元素在表中的位置,n为元素总个数，即表长,空表,线性终点,例如：字母表（A,B
2、,C,D,Z）,线性结构的特点,在数据元素的非空有限集中： 1) 存在唯一的一个被称做“第一个”的数据元素； 2) 存在唯一的一个被称做“最后一个”的数据元素； 3) 除第一个之外，集合中每个数据元素均只有一个前驱； 4) 除最后一个之外，集合中每个数据元素均只有一个后继。,抽象数据类型线性表的定义,抽象数据类型线性表的定义： ADT List数据对象：D=ai|aiElemSet,i=1,2,n, n0数据关系：R1=| ai-1, ai D,i=2,n基本操作：12种基本操作（P19-20） ADT List,线性表的其他复杂操作对上述定义的抽象数据类型线性表，还可以进行一些更复杂的操作。
3、如：将两个或两个以上的线性表合并成一个线性表；把一个线性表拆开成两个或两个以上的线性表；重新复制一个线性表等等。例子：书上的P2021的例2-1、2-2（自学，链式表时详细介绍）,2.2线性表的顺序表示和实现,顺序表的表示 顺序表的基本操作（实现）,问题提出顺序表,一条记录有学号和成绩两个数据项，依次输入数据建立一个有序表（按成绩由大到小）。其中输入的数据如下（学号，成绩）：(1,70),(2,85),(3,75), (4,90),(5,60),(6,80),(7,76),(8,50)等等。,问题分析,可用结构体数组来存储记录。 但数组一般固定长度，分配多大空间才合适？ 如何实现每输入一条记录
4、都保持有序？ 如果需要增加其它功能，如删除、修改、查询、排序，如何实现？ 如果数组长度不固定，如何动态分配数组空间？ 如果记录还有姓名、课程等数据项，应如何修改程序？,顺序表示：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。 若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标）。计算方法是：设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为：LOC(ai) = LOC(a1) + L *（i-1）LOC(ai+1) = LOC(ai)+L,线性表的顺序表示,线性表的顺序存储结构
5、示意图,地址 内容 元素在表中的位序,1,i,2,n,空闲区,i+1,L,b=LOC(a1),b + L,b +(i-1)L,b +(n-1)L,b +(max-1)L,小结： 在顺序表中，每个数据元素的存储地址是该数据元素在表中的位置的线性函数。 只要知道基地址和每个数据元素的所占存储空间的大小，就可根据公式求出任一数据元素的存储地址。 因此，顺序表是一种随机存取的存储结构。,一个一维数组，下标的范围是到，每个数组元素用相邻的个字节存储。存储器按字节编址，设存储数组元素的第一个字节的地址是98，则的第一个字节的地址是（ ）,例1,因此：LOC( M3 ) = 98 + 5 (3-0) =11
6、3,解：地址计算通式为：,LOC(ai) = LOC(a1) + L *（i-1）,线性表的顺序存储结构,#define MAXSIZE 100 typedef structElemType elemMAXSIZE;int length;int listsize; SqList;typedef structint no;int grade; ElemType;,线性表的顺序实现,1) 初始化： Status InitList_Sq( SqList / InitList_Sq,2)插入：在线性表的第i个位置前插入一个元素， 并保持数据的大小顺序。,实现步骤： 找到需要插入的位置i，将第n至第i
7、位的元素依次向后移动一个位置； 将要插入的元素写到第i个位置； 表长加1。 注意：事先应判断: 插入位置i 是否合法?表是否已满?,（a1,a2,ai-1,ai,an）,（a1,a2,ai-1,x,ai,an）,Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在顺序表L的第 i 个元素之前插入新的元素e,/ i 的合法范围为 1iL.length+1 / ListInsert_Sq,算法时间复杂度为:,O( ListLength(L) ),q = ,元素右移,实现步骤： 将第i +1至第n 位的元素向前移动一个位置； 表长减1。 注意：
8、 事先需要判断，删除位置i 是否合法?,3)删除：删除线性表的第i个位置上的元素，使长度为n的线性表变为长度为n-1的线性表。,（a1,a2,ai-1,ai,ai+1,an）,（a1,a2,ai-1,ai+1,an）,Status ListDelete_Sq(SqList &L, int i, ElemType &e) / ListDelete_Sq,for (+p; p = q; +p) *(p-1) = *p; / 被删除元素之后的元素左移 -L.length; / 表长减1 return OK;,算法时间复杂度为:,O( ListLength(L),p = / 表尾元素的位置,if (i
9、 L.length) return ERROR; / 删除位置不合法,6 顺序表的运算效率分析,时间效率分析:插入算法花费的时间，主要在于循环中元素的后移。当插入位置i=1时，全部元素都得移动，需n次移动；当i=n时，不需移动元素；在i位置插入时移动次数为n-i+1。,删除算法花费的时间，主要在于循环中元素的前移。当删除位置i=1时，全部元素都得移动，需n-1次移动，当i=n时，不需移动元素，在i位置删除时移动次数为n-i-1.,假定在表中任意位置插入、删除元素都是等概率的， 插入概率p(i)=1/(n+1) ，删除概率q(i)=1/n ，则：,插入操作时间效率（平均移动次数）,删除操作时间效
10、率（平均移动次数）,显然，顺序表的空间复杂度S(n)=O(1) （没有占用辅助空间）,本节小结,线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻； 优点：可以随机存取表中任一元素O(1)；存储空间使用紧凑 缺点：在插入，删除某一元素时，需要移动大量元素O(n);预先分配空间需按最大空间分配，利用不充分;表容量难以扩充 为克服这一缺点，我们引入另一种存储形式：,链式存储结构,习题,1数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为： （A）存储结构 （B）逻辑结构 （C）顺序存储结构 （D）链式存储结构 2.一个向量第一个元素的存储地址是100，每个元
11、素的长度为2，则第5个元素的地址是 （A）110 （B）108 （C）100 （D）120 3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是： (A) 访问第i个结点（1in）和求第i个结点的直接前驱（2in） (B) 在第i个结点后插入一个新结点（1in） (C) 删除第i个结点（1in） (D) 将n个结点从小到大排序,1. C 2. B 3.A,2. 已知一个顺序表中的元素按元素值非递减有序排列，编写一个函数删除表中多余的值相同的元素。 解：本题的算法思想是：由于表中的元素按元素值非递减有序排列，值相同的元素必为相邻的元素，因此依次比较相邻两个元素，若值相同，则删除其中一个
12、，否则继续向后查找。实现本题功能的函数如下： void del(vector A,int n) int i=0;j;while(i=n-1) if(Ai!=Ai+1)i+; /元素值不相等，向下找elsefor(j=i;j=n;j+) Aj=Aj+1; /删除第i个元素n-; /表长减1 ,3. 删除顺序表a中第i个元素起的k个元素 实现本题功能的函数如下： Status DeleteK(SqList /DeleteK,顺序表的大作业,目的：掌握线性表的基本结构和操作方法，培养学生灵活使用结构解决实际问题的能力。 内容：一条记录有学号和成绩两个数据项，依次输入数据建立一个有序表（按成绩由大到小）。其中输入的数据如下（学号，成绩）：(1,70),(2,85),(3,75), (4,90),(5,60),(6,80), (7,76),(8,50)等等。实现其增加、删除、修改、查询、排序等功能。,
