数据结构-第二章01-线性表的定义、存储

1第二章线性表[学习内容]线性表定义线性表的抽象数据结构线性表的顺序存储和操作实现线性表的链接存储和在链表上的操作实现线性表在双向链表操作实现2一、线性表的定义第二章线性表线性表的逻辑结构示意图a…aia2…ai+1an表头元素表尾元素§2.1线性表的类型定义3§2.1线性表的类型定义一、线性表的定义一个线性表可以用一个标识符来命名：A=(a1,a2,…,ai,ai+1,…,an)ai可以是基本数据类型也可以是struct类型4§2.1线性表的类型定义二、线性结构特点在数据元素的非空有限集中•元素个数n—表长度，n=0空表•存在唯一的一个被称作“第一个”的数据元素•存在唯一的一个被称作“最后一个”的数据元素•除第一个外，集合中的每个数据元素均只有一个前趋•除最后一个外，集合中的每个数据元素均只有一个后继•元素同构，且不能出现缺项5学号姓名年龄001张三18002李四19………………数据元素§2.1线性表的类型定义线性表几个具体例子L1=（’a’,’b’,’c’,’4’,’7’,’+’,’-’,’*’,’/’）L2=（25,35,28,49,51,87,46,32,88）L3=（“BASIC”,“PASCAL”,“JAVA”,“OK”）L4=（a,b,c,d,e,f,g,h,i,j,k,x,y,z）6§2.2线性表的顺序存储和实现一、线性表的顺序存储（顺序表）定义：把线性表中所有元素按其逻辑顺序依次存储到指定位置开始的连续空间中。即用一组地址连续的存储单元存放一个线性表特点：实现逻辑上相邻—物理地址相邻实现随机存取实现：（一维）数组7下标位置01…i-1i…n-1…MaxSize-1数组存贮空间a1a2…aiai+1…an…§2.2线性表的顺序存储和实现ElemType类型的数组list[MaxSize]存储线性表A=(a1,a2,…,ai,ai+1,…,an)元素地址计算方法第i个元素的存储位置为：list+(i-1)*sizeof(ElemType)线性表的顺序存储结构示意图8§2.2线性表的顺序存储和实现元素地址计算方法：lLOC(ai)=LOC(a1)+(i-1)*LlLOC(ai+1)=LOC(ai)+L其中：uL一个元素占用的存储单元个数uLOC(ai)—线性表第i个元素的地址9a1an01n-112n内存V数组下标元素序号M-1a2备用空间§2.2线性表的顺序存储和实现10§2.2线性表的顺序存储和实现线性表的顺序存储示例（图书资料）typedefstructcard{intnum;charname[20];charauthor[10];charpublisher[30];floatprice;}DATATYPE;11可以定义为静态数组或变量DATATYPElibrary[M];或动态申请和释放内存DATATYPE*pData；pData=(DATATYPE*)malloc(sizeof(DATATYPE));free(pData)；§2.2线性表的顺序存储和实现线性表的顺序存储示例（图书资料）12§2.2线性表的顺序存储和实现)11(ni插入一个元素定义：线性表的插入是指在第i个元素之前插入一个新的数据元素x，使长度为n的线性表(a1,a2,…,ai-1,ai,…an)变成长度为n+1的线性表(a1,a2,…,ai-1,x,ai,…an)13§2.2线性表的顺序存储和实现插入一个元素图示1内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+114内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1an-1§2.2线性表的顺序存储和实现插入一个元素图示2x15niiaaaaa,,,,1,21变成长度为n-1的线性表niiaaaaa,,,,11,21需将第i+1至第n共（n-i）个元素前移§2.2线性表的顺序存储和实现删除一个元素定义：线性表的删除是指将第i（1in）个元素删除，使长度为n的线性表16内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1§2.2线性表的顺序存储和实现删除一个元素图示117内存a1a2ai+1V数组下标01i-1n-2in-112i元素序号i+1n-1nanai+2§2.2线性表的顺序存储和实现删除一个元素图示218§2.2线性表的顺序存储和实现顺序存储结构的优缺缺点:•插入、删除操作需要移动大量的元素•预先分配空间需按最大空间分配，利用不充分•表容量难以扩充优点:•逻辑相邻，物理相邻•可随机存取任一元素•存储空间使用紧凑19§2.3线性表的基本运算基本信息定义20§2.3线性表的基本运算几个常用输出函数：21§2.3线性表的基本运算(1)初始化InitList(sequenlist*L)。其作用是建立一个空表L(即建立线性表的构架，但不含任何数据元素)。22§2.3线性表的基本运算(2)创建线性表creatlist(sequenlist*L)。其作用是向空线性表中添加数据。23(3)插入insert(sequenlist*L,datatypex,inti)。其作用是在线性表L的第i个位置上增加一个以x为值的新元素，使L由(a1，…，ai-1，ai，…，an)变为(a1，…，ai-1，x，ai，…，an)。参数i的合法取值范围是：1≤i≤n+1§2.3线性表的基本运算24§2.3线性表的基本运算25§2.3线性表的基本运算(4)删除dellist(sequenlist*L,inti)。其作用是删除线性表L的第i个元素ai,使L由(a1，…，ai-1，ai，ai+l，…，an)变为(a1，…，ai-1，ai+1，…，an)。参数i的合法取值范围是：1≤i≤n。26§2.3线性表的基本运算