资源描述：
《最新数据结构教程第2章--线性表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构教程第2章--线性表数据结构课程——涉及数学、计算机硬件和软件数据结构定义——指相互有关联的数据元素的集合，用D_S=(D,R)表示数据结构内容——数据的逻辑结构、存储结构和运算算法效率指标——时间效率和空间效率要点回顾数据的逻辑结构数据的存储结构数据的运算线性结构非线性结构顺序存储链式存储线性表、栈、队列、串、数组树形结构图形结构散列存储索引存储插入、删除、修改、查找、排序等逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构例1分析26个英文字母组成的英文表（A,B,C,D,……,Z）学号姓名性别年龄班级09048001于春梅女18微电09109048002何仕鹏男18电子09109
2、048003王爽女18通信09109048004王亚武男18通信091：：：：：例2分析学生情况登记表每个数据元素由5个数据项组成;元素之间的关系是线性的数据元素都是字母;元素之间的关系是线性的同一线性表中的元素必定具有相同特性2.线性表的基本操作Initiate(L)初始化操作。建立一个空线性表L。Length(L)求表长。求给定线性表L中数据元素的个数。Get(L,i)读取元素。读取线性表L中第i个数据元素。Insert(L,i,x)前插。在线性表L中第i个数据元素ai之前插入一个新的数据元素x。Delete(L,i,x)删除。删除线性表L中第i个的数据元素,并将其保存在x中。Locate
3、(L,x)定位函数。返回线性表L中元素值等于x的数据元素ai的序号i。2.2线性表的顺序存储结构—顺序表一、顺序表用一组地址连续的存储单元存储线性表的各个数据元素，称作线性表的顺序存储结构，简称顺序表。顺序表的特点：1.逻辑上相邻的数据元素，其物理上也相邻；2.若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标，参见存储结构示意图）。逻辑地址数据元素存储地址数据元素0a0Loc(a0)a01a1Loc(a0)+Ka1…………iaiLoc(a0)+i*Kai……n-1an-1Loc(a0)+(n-1)*Kan-1线性表的顺序存储结构示意图首地址每个元素占K字节一个线性表，
4、数据元素M下标的范围是０到９，每个数据元素用相邻的５个字节存储。设存结点Ｍ[０]的第一个字节的地址是98，则Ｍ[３]的第一个字节的地址是113例1：因此：LOC(M[3])=98+5×3=113解：地址计算通式为：LOC(ai)=LOC(a0)+L*i用c语言定义顺序表#defineMaxlen100typedefstruct{charname[10];charsex[3];intage;}elemtype;elemtypeList[Maxlen];intnum=0;/*定义数据类型*//*定义顺序表*//*顺序表的长度*//*顺序表最大长度*/姓名性别年龄张三男18李四女19………………ty
5、pedefstruct{elemtypeList[Maxlen];intnum;}SeqList;LL->numL->List[0]L->List[1]L->List[2]…L->List[Maxlen-1]SeqLista;SeqList*L;a.num，a.List[0]……numList[0]List[1]…用c语言定义顺序表二、顺序表的基本操作1.初始化ListInitiate(L)voidListInitiate(SeqList*L){L->num=0;}/*num表示顺序表的长度，或结点个数*/2.求表长ListLength(L)intListLength(SeqListL){re
6、turnL.num;}3.取数据元素ListGet(L，i，x)intListGet(SeqListL,inti,elemtype*x){if(i<0
7、
8、i>L.num－1){printf(“ERROR!”);return0;}else{*x=L.List[i];return1;}}4.插入（在第i个（0<=i<=num）数据元素之前插入一个新的数据元素x）a0a1…ai-1插入位置01…i-1ii+1…n-1…Maxlen-1an-1…ai+1aixaiai+1…an-101…i-1ii+1…n-1…Maxlen-1a0a1…ai-1i位置非法？开始表满？n-1至i位置的元素依次后移将元
9、素x存放在i位置表长加1结束i非法表满NYNY前插算法流程图是否满足0≤i≤numnum=i;j--)a[j+1]=a[j];a[i]=x;num++;注意：n表示数据元素的个数,num是线性表的长度增强健壮性intListInsert(SeqList*L,inti,elemtypex){intj;if(i<0
10、
11、i>L->num){printf(“e
