数据结构C语言--顺序表.ppt

《数据结构C语言--顺序表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章线性表本章主要介绍下列内容线性表的逻辑结构线性表的顺序存储结构线性表的链式存储结构线性表的应用举例退出2.1线性表的逻辑结构2.1.1线性表的定义线性表是由n（n≥0）个类型相同的数据元素组成的有限序列。通常表示成下列形式：L=(a1,a2,...,ai-1,ai,ai+1,...,an)其中：L为线性表名称，习惯用大写书写；ai为组成该线性表的数据元素，习惯用小写书写；当1

2、.2.1线性表的顺序存储结构线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的每个数据元素。如下图2-1所示：其中，L为每个数据元素所占据的存储单元数目。线性表中任意一个数据元素的存储位置的计算公式为：LOC(ai)=LOC(a1)+(i-1)*L在C语言中，实现线性表的顺序存储结构的类型定义：#defineMAXSIZE100/*线性表的最大长度*/typedefstruct{ElemTypedata[MAXSIZE];intlength;/*记录数组的实际长度*/}SeqList;定义一个顺序表：SeqListL;表长=L.length;数据元素的表示：L.dat

3、a[0]~L.data[L.length-1]定义一个指向SeqList类型的指针：SeqList*L;线性表的存储空间通过L=（SeqList*）malloc(sizeof(SeqList))操作来获得。表长=(*L).length或L->length;数据元素的表示：L->data[0]~L->data[L->length-1]2.2.2典型操作的算法实现初始化线性表SeqList*init_SeqList(){SeqList*L;L=（SeqList*）malloc(sizeof(SeqList));L->length=0;returnL;}2.插入操作InsertList

4、(L,x,i)定义：线性表的插入是指在第i（1in+1）个元素之前插入一个新的数据元素x，使长度为n的线性表变成长度为n+1的线性表插入算法的思路1、确定函数的参数顺序表L，插入位置i，插入的元素x2、插入的条件表满的判断位置i的合法性3、如何实现元素的下移4、在适当位置插入元素x5、注意插入后length的变化算法voidInsertList(SeqList*L，ElemTypex，inti){intk;if(L->length>=MAXSIZE){printf(＂表满＂);return;}/*表空间已满，不能插入*/if(i<1

5、

6、i>L->length+1)/*检查插入

7、位置的正确性*/{printf(＂位置错＂);return;}for(k=L->length-1;k>=i-1;k--)L->data[k+1]=L->data[k];/*结点移动*/L->data[i-1]=x;/*新元素插入*/L->length++;/*last仍指向最后元素*/}3.删除Delete_List(L,i)定义：线性表的删除是指将第i（1in）个元素删除，使长度为n的线性表变成长度为n-1的线性表需将第i+1至第n共（n-i)个元素前移删除算法的思路1、确定函数的参数顺序表L，插入位置i2、删除的条件表空的判断位置i的合法性3、如何实现元素的上移4、注意删

8、除后length的变化算法voidDeleteList(SeqList*L,inti){intk;if(i<1

9、

10、i>L->length)/*检查空表及删除位置的合法性*/{printf(＂不存在第i个元素＂);return;}for(k=i;k<=L->length-1;k++)L->data[k-1]=L->data[k];/*向上移动*/L->length--;}顺序存储结构的优缺点优点逻辑相邻，物理相邻可随机存取任一元素存储空间使用紧凑缺点插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配，利用不充分表容量难以扩充在线性表L中检索值为X的数据元素(一)intLo

11、cateSeq(SeqList*L,ElemTypex){inti=0;while(ilength&&L->data[i]!=x)i++;if(i>L->length-1)return-1;elsereturni;/*返回的是存储位置*/}在线性表L中检索值为X的数据元素（二）intLocateSeq(SeqList*L,ElemTypex){inti;for(i=0;ilength;i++)if(L->data[i]==x)returni;return-1;/*