数据结构第二章线性表课件.ppt

1、n理解线性表的理解线性表的逻辑结构逻辑结构特性特性n熟练掌握线性表的熟练掌握线性表的顺序存储结构顺序存储结构的描述方的描述方法，以及在该存储结构下的法，以及在该存储结构下的基本操作基本操作n熟练掌握线性表的熟练掌握线性表的链式存储结构链式存储结构的描述方的描述方法，灵活使用法，灵活使用单链表单链表、双链表双链表、循环链表循环链表，学会在相应存储结构下实现其各种学会在相应存储结构下实现其各种基本算基本算法法及相关的时间性能分析及相关的时间性能分析n一元多项式一元多项式的表示和相加的表示和相加第二章第二章 线性表线性表2.1 线性表的类型定义线性表的类型定义2.1 线性表的类型定义线性表的类型定义

2、2.1 线性表的类型定义线性表的类型定义2.1 线性表的类型定义线性表的类型定义ADT List 数据对象：数据对象：D=ai|ai ElemSet,i=1,2,n,n 0 数据关系：数据关系：R1=|ai-1,ai D,i=1,2,n 基本操作：基本操作：InitList(&L)操作结果：操作结果：构造一个空的线性表构造一个空的线性表L DestroyList(&L)初始条件：线性表初始条件：线性表L已存在已存在 操作结果：操作结果：销毁线性表销毁线性表2.1 线性表的类型定义线性表的类型定义 ClearList(&L)初始条件：线性表初始条件：线性表L已存在已存在 操作结果：操作结果：将线

3、性表将线性表L重置为空表重置为空表 ListEmpty(L)初始条件：线性表初始条件：线性表L已存在已存在 操作结果：若操作结果：若L为为空表空表，则返回，则返回TRUE，否则返回否则返回FALSE ListLength(L)初始条件：线性表初始条件：线性表L已存在已存在 操作结果：返回操作结果：返回L中中数据元素个数数据元素个数 2.1 线性表的类型定义线性表的类型定义GetElem(L,i,&e)初始条件：线性表初始条件：线性表L已存在，已存在，1iLengthList(L)操作结果：操作结果：用用e返回返回L中第中第i个元素的值个元素的值 LocateElem(L,e,compare()

4、初始条件：线性表初始条件：线性表L已存在，已存在，compare()是元素判定是元素判定 函数函数 操作结果：操作结果：返回返回L中第中第1个与个与e满足关系满足关系compare()的的 元素的位序元素的位序。若这样的元素不存在，则。若这样的元素不存在，则 返回值为返回值为0 PriorElem(L,cur_e,&pre_e)初始条件：线性表初始条件：线性表L已存在已存在 操作结果：若操作结果：若cur_e是是L的元素，但不是第一个，则的元素，但不是第一个，则 用用pre_e 返回它的前驱返回它的前驱，否则操作失败，否则操作失败，pre_e无定义无定义2.1 线性表的类型定义线性表的类型定义

5、NextElem(L,cur_e,&next_e)初始条件：线性表初始条件：线性表L已存在已存在 操作结果：若操作结果：若cur_e是是L的元素，但不是最后一个，则的元素，但不是最后一个，则用用next_e返回它的后继返回它的后继，否则操作失败，否则操作失败，next_e无定义无定义 ListTraverse(L,visit()初始条件：线性表初始条件：线性表L已存在已存在 操作结果：依次操作结果：依次对对L的每个元素调用函数的每个元素调用函数visit()。一。一 旦旦visit()失败，则操作失败失败，则操作失败 PutElem(L,i,&e)初始条件：线性表初始条件：线性表L已存在，已存

6、在，1iLengthList(L)操作结果：操作结果：L中第中第i个元素赋值同个元素赋值同e的值的值2.1 线性表的类型定义线性表的类型定义2.1 线性表的类型定义线性表的类型定义2.1 线性表的类型定义线性表的类型定义2.1 线性表的类型定义线性表的类型定义2.1 线性表的类型定义线性表的类型定义2.1 线性表的类型定义线性表的类型定义2.1 线性表的类型定义线性表的类型定义2.1 线性表的类型定义线性表的类型定义2.1 线性表的类型定义线性表的类型定义2.2 线性表的顺序表示和实现线性表的顺序表示和实现逻辑地址逻辑地址数据元素数据元素存储地址存储地址 数据元素数据元素0k0Loc(k0)k

7、01k1Loc(k0)+ck1ikiLoc(k0)+i*ckin-1kn-1Loc(k0)+(n-1)*ckn-1 线性表的顺序存储结构示意图线性表的顺序存储结构示意图 11)1(niiisinpE11npi211111ninnEniisniidlinqE1)(nqi12111ninnEnidlLiZhaoQianSunZhouWuZhengWang a1ana2.头指针头指针H头结点头结点H单链表结构：单链表结构：注意注意头指针头指针，头结点头结点等概念的不同含义。等概念的不同含义。HHH HH H作业要求作业要求本章作业1、简述下列概念的区别：头指针，头结点，首元结点（第一个元素、简述下列

8、概念的区别：头指针，头结点，首元结点（第一个元素结点）。结点）。2、填空：、填空：（1）在顺序表中插入或删除一个元素，需要平均移动）在顺序表中插入或删除一个元素，需要平均移动_个元素，个元素，具体移动的元素个数与具体移动的元素个数与_有关。有关。（2）顺序表中逻辑上相邻的元素的物理位置）顺序表中逻辑上相邻的元素的物理位置_紧邻。单链表紧邻。单链表中逻辑上相邻的元素的物理位置中逻辑上相邻的元素的物理位置_紧邻。紧邻。（3）单链表中，除了元首结点外，任一结点的存储位置由）单链表中，除了元首结点外，任一结点的存储位置由_指示。指示。（4）在单链表中设置头结点的作用是）在单链表中设置头结点的作用是_。

9、3、简答：什么情况下用顺序表比链表好？、简答：什么情况下用顺序表比链表好？本章作业4、已知、已知L是无表头结点的单链表，且是无表头结点的单链表，且P结点既不是首元结点，也不结点既不是首元结点，也不是尾元结点，试从一下选项中选择合适的语句序列。是尾元结点，试从一下选项中选择合适的语句序列。A、在、在P结点后插入结点后插入S结点的语句序列是结点的语句序列是_ B、在、在P结点后插入结点后插入S结点的语句序列是结点的语句序列是_ C、在表首插入、在表首插入S结点的语句序列是结点的语句序列是_ D、在表尾插入、在表尾插入S结点的语句序列是结点的语句序列是_（1）P-next=S;(2)P-next=P

10、-next-next;(3)P-next=S-next;（4）S-next=P-next;(5)S-next=L;(6)S-NULL;(7)Q=P;（8）while(P-next!=Q)P=P-next;(9)while(P-next!=NULL)P=P-next;(10)P=Q;(11)P=L;(12)L=S;(13)L=P;5、指出以下算法中的错误和低效（即费时）之处，并将其改写为一个既正确、指出以下算法中的错误和低效（即费时）之处，并将其改写为一个既正确又高效的算法。又高效的算法。Status Delete K（SqList&a,int i,int k）/本过程从顺序存储结构的线性表本过

11、程从顺序存储结构的线性表a /中删除第中删除第i个元素起的个元素起的k个元素个元素 if(i1ka.length)return INFEASIBLE/参数不合法参数不合法 else for(count=1;count=i+1;j-)a.elemj-1=a.elemj;a.length-；return OK；/DeleteK6、设顺序表、设顺序表va中的数据元素递增有序，试写一算法，将中的数据元素递增有序，试写一算法，将x插入到顺序表适当插入到顺序表适当位置上，以保持该表的有序性。位置上，以保持该表的有序性。作作 业业作作 业业111111,.,.,.,.,mmmnnnnma babbbmnLCa ba b aamn以上试题中，1-4必选，5和6任选一，7-11任选一，12必选。上课前交到讲台前面。作作 业业