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