资源描述：
《数据结构与算法 教学课件 作者 王曙燕 chapter2 线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、1第2章线性表2.2线性表的概念及运算2.3线性表的顺序存储2.4线性表的链式存储2.5顺序表和链表的比较2.1应用实例2.6实例分析与实现第2章线性表2.1应用实例应用实例一：约瑟夫环（Josephus）问题约瑟夫环（Josephus）问题是由古罗马的史学家约瑟夫（Josephus）提出的。问题描述为：编号为1，2，…，n的n个人按顺时针方向围坐在一张圆桌周围，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数，报m的那个人出列，将他的密码作为新的m值，从他顺时
2、针方向的下一个人开始重新从1报数，数到m的那个人又出列；如此下去，直至圆桌周围的人全部出列为止。第2章线性表2.1应用实例应用实例二：一元多项式运算器要实现一元多项式运算器，首先要设计表示一元多项式P=p0+p1X+p2X2+…+pnXn的合适的数据结构，并支持多项式的下列运算。（1）建立多项式。（2）输出多项式。（3）+，两个多项式相加，建立并输出和多项式。（4），两个多项式相减，建立并输出差多项式。（5）*,多项式乘法。（6）(),求多项式的值。（7）derivative(),求多项式导数。4第2章线性表2.2线性表的概念及运算
3、定义：线性表(LinearList)是由n(n≥0)个类型相同的数据元素a1,a2,…，an组成的有限序列，记做（a1,a2,…，ai-1，ai，ai+1，…，an）。数据元素之间是一对一的关系，即每个数据元素最多有一个直接前驱和一个直接后继。逻辑结构图：5第2章线性表2.2线性表的概念及运算特点：①同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。②有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。③有序性：线性表中相邻数据元素之间存在着序偶关系。6第2章线性表2.3线性表的顺序存储
4、定义:采用顺序存储结构的线性表通常称为顺序表。假设线性表中每个元素占k个单元，第一个元素的地址为loc(a1)，则第k个元素的地址为：loc(ai)=loc(a1)+(i-1)×k是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中。7第2章线性表2.3线性表的顺序存储...loc(a1)+(maxlen-1)knanloc(a1)+(n-1)k………iailoc(a1)+(i-1)k………2a2Loc(a1)+(2-1)k1a1Loc(a1)逻辑地址内存空间状态存储
5、地址顺序存储结构示意图空闲数据结构与算法8第2章线性表2.3线性表的顺序存储C语言定义#definemaxsize线性表可能达到的最大长度typedefstruct{ElemTypeelem[maxsize]；intlength；}SeqList；//表长9第2章线性表2.3线性表的顺序存储基本运算①查找操作②插入操作③删除操作10数据结构第2章线性表2.3线性表的顺序存储①查找操作按序号查找GetData(L,i)：要求查找线性表L中第i个数据元素，其结果是L.elem[i]。按内容查找Locate（L,x）:要求查找线性表L中与给
6、定值x相等的数据元素，其结果是：若在表L中找到与x相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空序号”，如-1。11第2章线性表2.3线性表的顺序存储按内容查找Locate（L,x）:intLocate(SeqListL，ElemTypex){inti=1;while((i<=L.length)&&(L.elem[i]!=x))i++;if(i<=L.length)return(i);elsereturn(-1);}intOpt_Locate(SeqListL，ElemTypex){inti;L.elem[0]=x;/
7、*标识边界*/i=L.length;while(L.elem[i]!=x)i--;return(i);}12第2章线性表2.2线性表的顺序存储②插入操作是指在表的第i(1≤i≤n+1)个位置，插入一个新元素e，使长度为n的线性表(e1，…，ei-1，ei，…，en)变成长度为n+1的线性表（e1，…,ei-1，x，ei，…，en）。例如：线性表(4,9,15,28,30,30,42,51,62)，需在第4个元素之前插入一个元素“21”。则需要将第9个位置到第4个位置的元素依次后移一个位置，然后将“21”插入到第4个位置。(4,9,15
8、,2128,30,30,42,51,62)#defineOK1#defineERROR0intInsList(SeqList*L,inti,ElemTypex){intk;if((i<1)
9、
10、(i>L->length+1
