资源描述：
《第二章 线性表_1.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第一章回顾1、程序设计和算法、数据结构的关系2、数据结构讨论的内容3、数据结构的定义4、抽象数据类型的概念5、算法及其度量1练习设n为正整数。试确定下列各程序段中前置以记号@的语句的频度i=1;k=0;while(i<=n-1){@k+=10*i;i++;}n-12i=1;k=0;do{@k+=10*i;i++;}while(i<=n-1);n-1,但n=1时特殊,是1次3x=n;y=0;//n是不小于1的常数while(x>=(y+1)*(y+1)){@y++;}4x=91;y=100;while(y>0){@if(x>100){x-=10;y
2、--;}elsex++;}11005数据结构部分的起点：什么是线性结构？6第1章绪论第2章线性表第3章栈和队列第4章串第5章数组第6章树和二叉树第9章查找第10章排序数据库部分目录7线性结构的定义：若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。可表示为：（a1,a2,……,an）简言之，线性结构反映结点间的逻辑关系是的。特点①只有一个首结点和尾结点；特点②除首尾结点外，其他结点只有一个直接前驱和一个直接后继。线性结构包括：线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是---
3、---线性表一对一(1:1)8第2章线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4应用举例9（a1,a2,…ai-1，ai,ai＋1，…,an）2.1线性表的定义：用数据元素的有限序列表示n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长。n≥0空表线性终点10（A,B,C,D,……,Z）学号姓名性别年龄班级012006013112柳华兵男19电子信息工程200604班012006013211陈是男19电子信息工程200605班0120
4、06013309邹礼见男19电子信息工程200606班012006013423刘述博男19电子信息工程200607班012006013526郑欢男19电子信息工程200608班：：：：：例2分析学生情况登记表是什么结构。分析：数据元素都是同类型（记录），元素间关系是线性的。分析：数据元素都是同类型（字母），元素间关系是线性的。注意：同一线性表中的元素必定具有相同特性！例1分析26个英文字母组成的英文表是什么结构。11“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。×是指各元素具有相同的数据类型试判断下列
5、叙述的正误：12线性表的抽象数据类型的定义ADTList{数据对象：D＝{ai
6、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
7、ai-1,ai∈D,i=2,...,n}基本操作：{结构初始化} {销毁结构} {引用型操作}{加工型操作}}ADTList13线性表的抽象数据类型的定义ADTList{数据对象：D＝{ai
8、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
9、ai-1,ai∈D,i=2,...,n}基本操作：{结构初始化}InitList(&L)操作结果
10、：构造一个空的线性表L。{销毁结构}DestroyList(&L)初始条件：线性表L已存在。 操作结果：销毁线性表L。14{引用型操作}ListEmpty(L)初始条件：线性表L已存在。 操作结果：若L为空表，则返回TRUE，否则返回FALSE。ListLength(L)初始条件：线性表L已存在。 操作结果：返回L中元素个数。PriorElem(L,cur_e,&pre_e)初始条件：线性表L已存在。 操作结果：若cur_e是L中的数据元素，但不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。Next
11、Elem(L,cur_e,&next_e)初始条件：线性表L已存在。 操作结果：若cur_e是L中的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。15GetElem(L,i,&e)初始条件：线性表L已存在，1≤i≤LengthList(L)。 操作结果：用e返回L中第i个元素的值。LocateElem(L,e,compare())初始条件：线性表L已存在,compare()是元素判定函数。 操作结果：返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。
12、ListTraverse(L,visit())初始条件：线性表L已存在，visit()为元素的访问函数。 操作结果：依次对L的每个元
