《(3.1)--1.1 线性表的概念程序设计综合实践.ppt》由会员分享，可在线阅读，更多相关《(3.1)--1.1 线性表的概念程序设计综合实践.ppt（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、程序设计课程实践基础算法篇1第一章 线性结构线性表是常见的基本数据结构线性表的链式存储和相关处理是程序设计学习中的难点之一线性表、抽象数据类型等概念算法和算法评价用顺序存储结构和链式存储结构实现抽象数据类型线性表单链表和双链表的典型应用案例程序设计中最为常用的两种特殊线性数据结构：栈和队列2一、线性表的概念计算机应用中，数值、文字、图形、图像、声音等各种形式的信息是对客观事物的符号化编码表示，也称为数据（data）构成数据的、具有相同性质的基本单元称为数据元素（data element）数据项（data item）是构成数据的相对独立的分项，它反映客观事物的某种特性性质相同的数据元素集合组成数
2、据对象（data object）如出版社图书信息管理系统中已出版图书列表，每本书的信息是一个数据元素，由书名、作者、定价信息、出版时间等多个数据项组成。所有这些数据元素构成数据对象，表示该出版社出版的所有图书。3数据对象内的数据元素间可以存在一种或多种关系。数据结构(data structure)是相互之间存在一种或多种特定关系的数据元素的集合，包含数据对象和关系两个组成部分数据结构可以用二元组来表示：Data Structure=(D,S)其中D是数据元素的有限集，S是D上数据元素间关系的有限集。例1.1 一维数组是一种线性的数据结构，它由n个元素有序排列而成，可以用下述方式描述：Array
3、=(D,S)其中：4用二元组描述的数据结构体现出数据元素间的逻辑关系，称为逻辑结构4种基本逻辑结构：线性结构、集合结构、树型结构和图状结构数据结构只有在计算机物理存储器上存储表示后，才能设计程序进行处理，数据结构在计算机物理存储器里的实际存储方案称为存储结构。存储结构需要存储（表示）数据对象和数据元素间的各种关系。同一个逻辑结构，可以采用不同的存储结构。通常采用两种存储结构：1.顺序存储结构。所有数据元素在内存空间中依次存放，数据元素在物理存储器上的位置关系体现了它们在逻辑上的关系，通常用于表示简单的顺序关系。2.链式存储结构。数据元素分散存放，在存放每个数据元素时，必须附加一个或若干专门的数
4、据项来指示其它相关联的数据元素在存储器中的存放位置。5例1.2 数列“10,20,30,40”的顺序结构和链式结构。6(a)数列的顺序存储结构 (b)数列的链式存储结构 图1.1 两种存储结构示意图线性表的定义：线性表是n个数据元素的有限序列，可记为：n是线性表的长度。当n=0时，为一空表。7具有线性表结构特征的数据对象有很多，如：例1.3 斐波那契序列：(0,1,1,2,3,5,8,13,21,34,55)。序列中数据元素类型为整型。例1.4 一个字符串：“Data-Structure”。序列中数据元素类型为字符型。例1.5 课程教材选用表：序列中数据元素类型为结构型（课程教材信息）。8课
5、程 名 称书 名作 者出 版 社定 价ISBN数据结构数据结构实用教程万健电子工业出版社329787121110764面向对象程序设计（C+）C+面向对象程序设计李卫明西安电子科技大学出版社289787560656540程序设计基础C语言程序设计何铭钦 颜晖高等教育出版社359787040346725.l数据类型（data type）和抽象数据类型（abstract data type,ADT）l线性表的抽象数据类型定义ADT List 基本操作：创建空表Create();/创建一个空的线性表 清空Clear(L);/将已有线性表L清空 销毁线性表Destroy(L);/销毁一个线性表L，不再
6、使用 拷贝线性表Copy(L);/根据已有线性表L，复制一个新线性表，内容相同 判空IsEmpty(L);/判断线性表L是否为空表，若是则返回TRUE，否则返回FALSE 求长度Length(L);/返回线性表中数据元素的个数（待续）910 获取起始位置BeginPosition(L);/返回线性表中代表第一个元素的位置 /空表返回EndPosition(L)获取结束位置EndPosition(L);/返回代表线性表结束的位置 迭代下一位置NextPosition(L,pos);/返回线性表中pos有效位置的下个位置 /结束位置返回EndPosition(L)获取元素位置LocatePosit
7、ion(L,i);/返回线性表代表第i个元素所在位置，1in /（设线性表的表长为n）定位元素位置LocateElem(L,e);/根据数据元素e查找它在线性表中出现的位置 /若存在，则返回它的有效位置；否则返回EndPosition(L)获取元素GetElem(L,pos);/返回线性表中pos有效位置的数据元素 设置元素SetElem(L,pos,e);/将线性表中pos有效位置的数据元素设置为e 插入元素InsertBefore(L,pos,e);/在线性表的pos位置前插入一新的数据元素 /pos为EndPosition(L)时添加在尾部 删除元素Delete(L,pos);/删除线性表中pos有效位置所在数据元素