下载文档原格式
线性结构与非线性结构一、引言在计算机科学中，数据结构是指组织和存储数据的方式。
线性结构和非线性结构是数据结构中的两种常见类型，它们在组织和存储数据方面具有不同的特点和应用场景。
本文将重点讨论线性结构和非线性结构的定义、特点以及常见的应用。
二、线性结构1. 定义线性结构是数据元素之间存在一对一的顺序关系的结构。
每个数据元素只能有一个直接前驱和一个直接后继。
线性结构中的数据元素之间不存在分支和循环。
2. 特点- 线性结构可以用线性表来表示，常见的线性表包括数组和链表。
- 线性结构具有简单直观的顺序关系，易于理解和实现。
- 在线性结构中，插入和删除操作相对简单，时间复杂度为O(1)或O(n)。
3. 应用- 数组是一种常见的线性结构，适用于元素个数固定且需要频繁访问的场景，如存储学生成绩、图像像素等。
- 链表也是一种常见的线性结构，适用于元素个数不固定、频繁插入和删除操作的场景，如实现栈、队列等。
三、非线性结构1. 定义非线性结构是数据元素之间存在一对多或多对多的关系的结构。
非线性结构中的数据元素之间可以存在分支和循环。
2. 特点- 非线性结构能够更灵活地表达数据元素之间的关系，能够更好地表示实际问题的特点。
- 非线性结构的实现相对复杂，需要通过指针、引用或其他数据结构来建立关系。
3. 应用- 树是一种常见的非线性结构，适用于表示具有层次结构的数据，如文件系统、组织结构等。
- 图是另一种常见的非线性结构，适用于表示各种复杂关系网络，如社交网络、交通网络等。
四、线性结构与非线性结构的比较1. 存储方式线性结构可以使用连续的内存空间来存储，如数组。
非线性结构需要使用指针或其他数据结构来建立关系，如树和图。
2. 增删操作线性结构中的增删操作相对简单，时间复杂度为O(1)或O(n)。
非线性结构中的增删操作相对复杂，时间复杂度取决于结构的规模和复杂程度。
3. 数据组织方式线性结构中的数据元素之间存在简单直观的顺序关系，适用于有序数据。
第1章绪论内容提要：◆数据结构研究的内容。
针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。
数据结构涵盖的内容：◆基本概念：数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型。
数据——所有能被计算机识别、存储和处理的符号的集合。
数据元素——是数据的基本单位，具有完整确定的实际意义。
数据对象——具有相同性质的数据元素的集合，是数据的一个子集。
数据结构——是相互之间存在一种或多种特定关系的数据元素的集合，表示为：Data_Structure=（D, R）数据类型——是一个值的集合和定义在该值上的一组操作的总称。
抽象数据类型——由用户定义的一个数学模型与定义在该模型上的一组操作，它由基本的数据类型构成。
◆算法的定义及五个特征。
算法——是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。
算法的基本特性：输入、输出、有穷性、确定性、可行性◆算法设计要求。
①正确性、②可读性、③健壮性、④效率与低存储量需求◆算法分析。
时间复杂度、空间复杂度、稳定性学习重点：◆数据结构的“三要素”：逻辑结构、物理（存储）结构及在这种结构上所定义的操作（运算）。
◆用计算语句频度来估算算法的时间复杂度。
第二章线性表内容提要：◆线性表的逻辑结构定义，对线性表定义的操作。
线性表的定义：用数据元素的有限序列表示◆线性表的存储结构：顺序存储结构和链式存储结构。
顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
链式存储结构: 其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。
通过指针来实现！◆线性表的操作在两种存储结构中的实现。
数据结构的基本运算：修改、插入、删除、查找、排序1)修改——通过数组的下标便可访问某个特定元素并修改之。
核心语句:V[i]=x;顺序表修改操作的时间效率是O(1)2) 插入——在线性表的第i个位置前插入一个元素实现步骤：①将第n至第i 位的元素向后移动一个位置；②将要插入的元素写到第i个位置；③表长加1。
《数据结构》讲义(总158页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--《数据结构》讲义第一章：绪论课程：数据结构课题：第一章—小节（共4个课时）什么是数据结构基本概念和术语抽象数据类型的表现与实现算法和算法分析目的要求：理解数据、数据元素、数据项的概念；掌握逻辑结构和存储结构的关系；理解算法的基本概念；学会分析算法的时间复杂性和空间复杂性。
新课重点、难点：数据、数据元素、数据项、时间复杂性和空间复杂性教学方法：课堂讲解、例题演示，课件演示教学内容及过程：……………………………第1-2课时……………………………计算机的应用不再局限于科学计算，更多地用于控制，管理，数据处理等非数值计算的处理工作。
计算机加工处理的对象：数值，字符，表格，图形声音，图象等具有一定结构的数据。
进行程序设计时必须分析待处理的对象的特性及各对象之间存在的关系———产生背景。
什么是数据结构计算机解题步骤：建立数学模型——设计解此数学模型的算法——编制程序——进行测试调整——解答。
其中建立数学模型的实质：找出操作对象之间的关系。
例1. 图书馆书目检索——对应线性关系例2. 博奕树——对应树型关系例3. 交叉路口交通灯管理——对应图状结构。
数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及它们之间的关系和操作等的学科。
（地位）数据结构的基本概念和术语1. 数据（Data）数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。
换句话说，数据是对客观事物采用计算机能够识别、存储和处理的形式所进行的描述；是计算机加工处理的对象。
包括数值、字符、声音、图象等。
2. 数据元素（Data Element）数据元素是组成数据的基本单位, 是数据集合的个体，在计算机中通常作为一个逻辑整体进行考虑和处理。
一个数据元素可由若干个数据项组成（Data Item）。
3. 数据对象（Data Object）数据对象是性质相同的数据元素的集合，是数据的一个子集。
“数据结构知识导入全程目标•数据结构的基本概念–逻辑结构–物理结构–运算结构•数据结构的基本实现–堆栈–队列–链表–二叉树知识讲解数据结构的基本概念•数据结构是相互之间存在一种或多种特定关系的数据的集合•数据结构是计算机存储、组织数据的方式•数据结构的选择直接影响计算机程序的运行效率(时间复杂度)和存储效率(空间复杂度)•计算机程序设计=算法+数据结构•数据结构的三个层次–抽象层——逻辑结构–结构层——物理结构–实现层——运算结构识讲解•集合结构(集)–结构中的数据元素除了同属于一个集合外没有其它关系识讲解•线性结构(表)–结构中的数据元素具有一对一的前后关系识讲解•树型结构(树)–结构中的数据元素具有一对多的父子关系知识讲解实现双向线性链表•删除节点识讲解•树形结构的最简模型，每个节点最多有两个子节点•每个子节点有且仅有一个父节点，整棵树只有一个根节点•具有递归的结构特征，用递归的方法处理，可以简化算法•三种遍历序–前序遍历：D-L-R–中序遍历：L-D-R–后序遍历：L-R-D识讲解•二叉树的一般形式–根节点、枝节点和叶节点–父节点和子节点–左子节点和右子节点–左子树和右子树–大小和高度(深度)识讲解•满二叉树–每层节点数均达到最大值–所有枝节点均有左右子树知识讲解二叉树•完全二叉树–除最下层外，各层节点数均达到最大值–最下层的节点都连续集中在左边识讲解•顺序存储–从上到下、从左到右，依次存放–非完全二叉树需用虚节点补成完全二叉树识讲解•链式存储–二叉链表，每个节点包括三个域，一个数据域和两个分别指向其左右子节点的指针域识讲解•链式存储–三叉链表，每个节点包括四个域，一个数据域、两个分别指向其左右子节点的指针域和一个指向其父节点的指针域知识讲解实现有序二叉树•有序二叉树亦称二叉搜索树，若非空树则满足：–若左子树非空，则左子树上所有节点的值均小于等于根节点的值–若右子树非空，则右子树上所有节点的值均大于等于根节点的值–左右子树亦分别为有序二叉树•基于有序二叉树的排序和查找，可获得O(logN)级的平均时间复杂度知识讲解逻辑结构•网状结构(图)–结构中的数据元素具有多对多的交叉映射关系识讲解•顺序结构–结构中的数据元素存放在一段连续的地址空间中识讲解•顺序结构–随机访问方便，空间利用率低，插入删除不方便识讲解•链式结构–结构中的数据元素存放在彼此独立的地址空间中–每个独立的地址空间称为节点–节点除保存数据外，还需要保存相关节点的地址识讲解•链式结构–插入删除方便，空间利用率高，随机访问不方便知识讲解逻辑结构与物理结构的关系•每种逻辑结构采用何种物理结构实现，并没有一定之规，通常根据实现的难易程度，以及在时间和空间复杂度方面的要求，选择最适合的物理结构，亦不排除复合多种物理结构实现一种逻辑结构的可能知识讲解运算结构•创建与销毁–分配资源、建立结构、释放资源•插入与删除–增加、减少数据元素•获取与修改–遍历、迭代、随机访问•排序与查找–算法应用知识讲解数据结构的基本实现•堆栈–基于顺序表的实现–基于链式表的实现•队列–基于顺序表的实现–基于链式表的实现•链表–双向线性链表的实现•二叉树–有序二叉树(二叉搜索树)的实现知识讲解堆栈•后进(压入/push)先出(弹出/pop)识讲解•初始化空间、栈顶指针、判空判满识讲解•动态分配、栈顶指针、注意判空知识讲解队列•先进(压入/push)先出(弹出/pop)识讲解•初始化空间、前弹后压、循环使用、判空判满识讲解•动态分配、前后指针、注意判空知识讲解链表•地址不连续的节点序列，彼此通过指针相互连接•根据不同的结构特征，将链表分为：–单向线性链表–单向循环链表–双向线性链表–双线循环链表–数组链表–链表数组–二维链表识讲解•单向线性链表识讲解•单向循环链表识讲解•双向线性链表识讲解•双向循环链表识讲解•数组链表识讲解•链表数组识讲解•二维链表识讲解•结构模型识讲解•插入节点。
数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。
换句话说，数据是对客观事物采用计算机能够识别、存储和处理的形式所进行的描述；是计算机加工处理的对象。
包括数值、字符、声数据元素是组成数据的基本单位一个数据元素可由若干个数据项组成（）数据对象是性质相同的数据元素的集合，是数据的一个子集。
…}，字母字符数据对象是集合象。
由此可看出，不论数据元素集合是无限集（如整数集）Data Structure）数据元素相互之间的关系称为结构（ Structure ），有四种基本结构。
集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。
线性结构：结构中的数据元素之间存在着一对一的线性关系。
图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。
为数据结构的有限集，S是D上关系的有限集。
表示复数的虚部。
存储结构（又称物理结构）是逻辑结构在计算机中的存储映象，是逻辑结构在计算机中的实现，它包括据元素的表示和关系的表示形式化描述：要存入机器中，建立一从，使S（D逻辑结构与存储结构的关系为：数据结构的内容可归纳为三个部分：逻辑结构、存储结构和运算集合。
按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合，(Data Type)数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称合，即该类型的取值范围，以及该类型中可允许使用的一组运算。
例如高级语言中的数据类型就是已经实现的从这个意义上讲，数据类型是高级语言中允许的变量种类，计算机中使用的是二进制数，汇编语言中则可给出各种数据的十进制表示，如二进制数据的抽象; 使用者在编程时可以直接使用据抽象，出现了数据类型，(Abstract Data Type)）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。
抽象数据类型的定义取决于客观存在的一组逻辑特性，而与其在计算机内如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。
第一章绪论计算机科学是一门研究数据表示和数据处理的科学。
数据是计算机化的信息，它是计算机可以直接处理的最基本和最重要的对象。
无论是进行科学计算或数据处理、过程控制以及对文件的存储和检索及数据库技术等计算机应用领域中，都是对数据进行加工处理的过程。
因此，要设计出一个结构好效率高的程序，必须研究数据的特性及数据间的相互关系及其对应的存储表示，并利用这些特性和关系设计出相应的算法和程序。
1．1 数据结构的概念数据结构是计算机科学与技术专业的专业基础课，是十分重要的核心课程。
所有的计算机系统软件和应用软件都要用到各种类型的数据结构。
要想有效地使用计算机、充分发挥计算机的性能，还必须学习和掌握好数据结构的有关知识。
打好“数据结构”这门课程的扎实基础，对于学习计算机专业的其他课程，如操作系统、编译原理、数据库管理系统、软件工程、人工智能等都是十分有益的。
1.1.1 为什么要学习数据结构当我们使用计算机来解决一个具体问题时，一般需要经过下列几个步骤：首先要从该具体问题抽象出一个适当的数学模型，然后设计或选择一个解此数学模型的算法，最后编出程序进行调试、测试，直至得到最终的解答。
随着计算机应用领域的扩大和软、硬件的发展，非数值计算问题越来越显得重要。
据统计，当今处理非数值计算性问题占用了90%以上的机器时间。
这类问题涉及到的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。
因此，解决这类问题的关键不再是数学分析和计算方法，而是要设计出合适的数据结构，才能有效地解决问题。
下面所列举的就是属于这一类的具体问题。
[例1]学生信息检索系统。
当我们需要查找某个学生的有关情况的时候；或者想查询某个专业或年级的学生的有关情况的时候，只要我们建立了相关的数据结构，按照某种算法编写了相关程序，就可以实现计算机自动检索。
由此，可以在学生信息检索系统中建立一张按学号顺序排列的学生信息表和分别按姓名、专业、年级顺序排列的索引表，如图1.1所示。
第一章绪论第一节什么是数据结构？估猜以下软件的共性：学生信息管理、图书信息管理、人事档案管理。
数学模型：用符号、表达式组成的数学结构，其表达的内容与所研究对象的行为、特性基本一致。
信息模型：信息处理领域中的数学模型。
数据结构：在程序设计领域，研究操作对象及其之间的关系和操作。
忽略数据的具体含义，研究信息模型的结构特性、处理方法。
第二节概念、术语一、有关数据结构的概念数据：对客观事物的符号表示。
例：生活中还有什么信息没有被数字化？身份证，汽车牌号，电话号码，条形代码……数据元素：数据的基本单位。
相当于"记录"。
一个数据元素由若干个数据项组成，相当于"域"。
数据对象：性质相同的数据元素的集合。
数据结构：相互之间存在特定关系的数据集合。
四种结构形式：集合、线性、树形、图(网)状形式定义：(D，S，P)D：数据元素的集合(数据对象)S：D上关系的有限集P：D上的基本操作集逻辑结构：关系S描述的是数据元素之间的逻辑关系。
存储结构：数据结构在计算机中的存储形式。
顺序映象、非顺序映象、索引存储、哈希存储逻辑结构与存储结构的关系：逻辑结构：描述、理解问题，面向问题。
存储结构：便于机器运算，面向机器。
程序设计中的基本问题：逻辑结构如何转换为存储结构？二、有关数据类型的概念数据类型：值的集合和定义在该值集上的一组操作的总称。
包括：原子类型、结构类型。
抽象数据类型(ADT)：一个数学模型及该模型上的一组操作。
核心：是逻辑特性，而非具体表示、实现。
课程任务：学习ADT、实践ADT。
如：线性表类型、栈类型、队列类型、数组类型、广义表类型、树类型、图类型、查找表类型……实践指导：为了代码的复用性，采用模块结构。
如：C中的头文件、C++中的类第三节 ADT的表示与实现本教材中，算法书写习惯的约定。
数据元素类型ElemType：int,float,char, char[] ……引用参数 &算法：void add(int a,int b,int &c) { c=a+b; }程序：void add(int a,int b,int *p_c){ *p_c=a+b; }第四节算法的描述及分析一、有关算法的概念算法：特定问题求解步骤的一种描述。
