资源描述：
《数据结构02-线性表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构DataStructures安海忠博士中国地质大学（北京）人文经管学院院长教授博士生导师国土资源部资源环境承载力评价重点实验室主任电话：01082323793（办），13810910701电邮：ahz369@163.com教学内容第一章绪论第二章线性表第三章栈和队列第四章串第六章树和二叉树第七章图第九章查找第十章内部排序第二章线性表2.1线性表的定义2.2用数组实现线性表（顺序表）2.3用指针实现线性表（链表）2.4循环链表2.5用双链表示线性表（双向链表）2.6线性表的应用：一元多项式的表示及相加第二章线性表学习重点线性结构的特点熟练掌握两种存储结构的描述方法。链表是本章的重点和难点
2、熟练掌握顺序表的定义与实现，包括查找、插入、删除算法的实现熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构2.1线性表的定义线性表L是n(n>=0)个相同类型数据元素a1,…，an-1,an构成的有限序列。表示成:L=(a1,…，an-1,an)形式化定义：Linearlist=(D,R)其中：D0为某个数据对象的集合n为线性表长度2.1线性表的定义（a1,a2,…ai-1，ai,ai＋1，…,an）n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长空表线性终点2.1线性表的定义表长--线性表
3、中元素的个数(n),n=0为空表直接前驱--线性表中ai-1是ai的直接前驱元素，a1无直接前驱直接后继--线性表中ai+1是ai的直接后继元素，an无直接后继在线性表中加上一些运算，才可以构成一个抽象数学模型List2.1线性表的定义例分析26个英文字母组成的英文表（A,B,C,D,……,Z）学号姓名性别年龄班级2001011810205于春梅女18计016班2001011810260何仕鹏男18计017班2001011810284王爽女18计011班2001011810360王亚武男18计012班：：：：：例分析学生情况登记表数据元素都是记录;元素间关系是线性数据元素都是字母;元素间关系是
4、线性同一线性表中的元素必定具有相同特性2.1线性表的定义2.1线性表的定义2.2用数组实现线性表（顺序表）线性表的顺序表示又称为顺序存储结构或顺序映像逻辑上相邻，物理上也相邻用一组地址连续的存储单元依次存储线性表的元素，可通过数组来实现若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标）线性表(a1,a1,a2,...an)顺序存储结构的一般形式序号存储状态存储地址1b2b+pib+(i-1)*pnb+(n-1)*p自由区maxlengb+(maxleng-1)*p其中:b----表的首地址/基地址/元素a1的地址。p----1个数据元素所占存储单元的数目。maxlen
5、g----最大长度,为某个常数。a1a2...ai...an//////2.2用数组实现线性表（顺序表）线性表顺序结构在C语言中的定义其中：SqList----结构类型名La----结构类型变量名La.length---表长La.elem[0]----a1La.elem[La.length-1]---an#definemaxleng100structSqList{ElemTypeelem[maxleng];//下标:0,1,...,maxleng-1intlength;//表长};SqListLa;2.2用数组实现线性表（顺序表）顺序存储结构的寻址公式i=12in地址=bb+pb+(i-1)p
6、b+(n-1)p假设:线性表的首地址为b,每个数据元素占p个存储单元,则表中任意元素ai(1≤i≤n)的存储地址是:LOC(i)=LOC(1)+(i-1)*p=b+(i-1)*p(1≤i≤n)例:假设b=1024,p=4,i=35LOC(i)=b+(i-1)*p=1024+(35-1)*4=1024+34*4=1160a1a2...ai...an//////2.2用数组实现线性表（顺序表）在表中插入元素x—插入算法2.2用数组实现线性表（顺序表）插入算法2.2用数组实现线性表（顺序表）插入算法2.2用数组实现线性表（顺序表）插入算法2.2用数组实现线性表（顺序表）插入算法2.2用数组实现线性表
7、（顺序表）在表中删除元素—删除算法2.2用数组实现线性表（顺序表）删除算法2.2用数组实现线性表（顺序表）删除算法2.2用数组实现线性表（顺序表）删除算法2.2用数组实现线性表（顺序表）删除算法2.2用数组实现线性表（顺序表）顺序存储结构的评价优点：(1)是一种随机存取结构，存取任何元素的时间是一个常数，速度快；(2)结构简单，逻辑上相邻的元素在物理上也是相邻的；(3)不使用指针，节省存储空间。缺
