资源描述：
《第2课线性表及其顺序存储结构ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、教学目的：掌握线性表的概念和类型定义教学重点：线性表的顺序存储结构和链式存储结构教学难点：链表的操作第2章线性表2021/7/271线性表（Linearlist）是最简单且最常用的一种数据结构。这种结构逻辑上具有下列特点：存在一个唯一的没有前驱的数据元素——称为表头；存在一个唯一的没有后继的数据元素——称为表尾；其它数据元素均有且仅有一个直接前驱和一个直接后继.本章学习导读2021/7/2721.线性表的概念和类型定义2.线性表的顺序存储结构及算法实现3.补充:C语言中结构体与指针操作教学重点：线性表的插
2、入、删除操作本课内容2021/7/273线性表由一组具有相同属性的数据元素构成。数据元素的含义很广泛，在不同的具体情况下，可以有不同的含义。1.线性表的定义线性表L是n（n≥0）个具有相同属性的数据元素a1，a2，a3，…，an组成的有限序列，其中序列中元素的个数n称为线性表的长度。当n=0时称为空表，即不含有任何元素。2.1线性表的基本概念2021/7/274例1、26个英文字母组成的字母表（A，B，C、…、Z）例2、从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92
3、，188）例3、学生统计表2021/7/275从以上例子可看出,线性表的特点：（1）有序性：线性表长度是有限的；（2）有序性：元素之间是有顺序限制的，并且用直接前驱和后继来描述；（3）同型性：所有元素是同一数据类型；（4）抽象性：数据元素的类型没有具体定义，只是给出一个抽象说明（Elemtype)。即可以是简单类型，也可以是复杂的构造类型；（5）原子性：数据元素整体上作为一个独立的存储对象，不再分解为更小的数据单位进行存储。2021/7/276线性表的ADT定义ADTLiner_list{数据对象定义：D
4、={ei
5、ei∈ElemType&&0≤i≤n&&n≥0}数据关系定义：R={
6、ei-1,ei∈D&&2≤i≤n}数据运算定义：（一组操作说明）初始化线性表Initlist(L）求线性表的长度Getlen(L)取第i个元素Getelem(L,i):插入元素InsElem(L,i,x)删除元素Delelem(L,i)清空表ClearList(L)释放表Destroy(L)2021/7/2772.2线性表的顺序结构及实现线性表的顺序存储结构可以有静态结构和动态结构两种不同的方式。顺序存储结构
7、的特点：在内存中用地址连续的存储单元按照数据元素的逻辑顺序、依次“一个接一个”地存放线性表的所有数据元素，通过物理位置的相邻来表示元素之间的逻辑关系。所谓静态结构指：线性表所占的存储空间是在编译时就确定的，一经分配不再改变。动态结构指：线性表所需的存储空间可以在运行时分配，并且能够根据需要动态增加或释放。2021/7/278线性表的顺序存储结构需要两个分量描述：用于存储数据元素的数组data，以及表长length。通常将它们定义在一个结构类型中。可用结构类型sqList定义来描述顺序表(静态)：#defi
8、neMaxLen100//线性表的容量typedefstruct{ElemTypedata[MaxLen];//定义存储表中元素的数组intlength;//线性表的实际长度}sqList;typedefintElemType//元素类型ElemType简化为int型时2.2.1线性表的顺序静态结构及实现2021/7/2791．初始化顺序表Initlist(L)的实现顺序表的初始化即构造一个空表，只要将表L中的表长度置为0，就可以实现建空表的功能（数据元素的存储空间data已由编译程序实现）。voidin
9、itlist(sqList*L){L->length=0;}2．求线性表长度GetLen(L)的实现intGetlen(sqList*L){returnL->length;}该算法的时间复杂度为O(1)2.2.1线性表的顺序静态结构及实现2021/7/27103．按序号取元素GetElem(L,i)的实现根据约定，序号为i的元素存储在数组下标为i-1的数组元素中，所以可直接从该数组元素中取得值。i的有效值应大于等于1和小于等于线性表的实际长度。ElemTypeGetElem(sqLlist*L,inti)
10、{if(i<1
11、
12、i>L->length)/*判断参数是否合法*/{printf(“error”);exit(1);}returnL->data[i-1];}2.2.1线性表的顺序静态结构及实现2021/7/27115．顺序表的插入算法(重点)顺序表的插入是指在表的第i个位置上插入一个值为x的新元素，插入后使原表长为n的表(a1,a2,…，ai-1,ai,ai+1,…,an)成为表长为n+1的线性表需要注意的是:插入后形成的新
