数据结构（逻辑结构,物理结构,特点）

malloc函数为动态分配空间；

原型为: void * malloc(int size);

使用方法一般为：

假设你要定义一个名为a的Node类型的指针变量，使用以下语句：

Node * a=（Node *）malloc(sizeof(Node))；

其中（Node *）为强制转换，把返回类型void *转换为Node *，sizeof（Node）为获取Node类型占据空间的大小，如在我机子上int类型占4字节，sizeof（int）就返回4；

使用malloc需要包含＃include

学习数据结构有什么用？

计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。

同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。

程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。

程序=数据结构+算法(尼克劳斯.沃尔斯）

目标：

“数据结构” 课程的教学目标是要求学生学会分析数据对象特征，掌握数据组织方法和计算机的表示方法，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及相应算法，初步掌握算法时间空间分析的技巧，培养良好的程序设计技能。

意义

1. 算法和数据结构是计算机科学的两大支柱

2.数据结构是程序设计的基础

程序=数据结构+算法

--图灵奖获得者：Nicklaus Wirth（瑞士）

数据结构是设计OS、DBMS、编译等系统程序和各种应用程序的重要基础

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。

术语：

数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

蜂考数据结构答案

1.什么是数据结构?

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。结构包括逻辑结构和物理结构。

数据的逻辑结构包括4种

(1)集合：数据元素之间除了有相同的数据类型再没有其他的关系

(2)线性结构：数据元素之间是一对一的关系 ——线性表、栈、队列

(3)树形结构：数据元素之间是一对多的关系

(4)图状结构：数据元素之间是多对多的关系。

物理结构包括顺序存储结构和链式存储结构。

2.解释一下顺序存储与链式存储

顺序存储结构是用一段连续的存储空间来存储数据元素，可以进行随机访问，访问效率较高。链式存储结构是用任意的存储空间来存储数据元素，不可以进行随机访问，访问效率较低。

3.头指针和头结点的区别?

头指针：是指向第一个节点存储位置的指针，具有标识作用，头指针是链表的必要元素，无论链表是否为空，头指针都存在。 头结点：是放在第一个元素节点之前，便于在第一个元素节点之前进行插入和删除的操作，头结点不是链表的必须元素，可有可无，头结点的数据域也可以不存储任何信息。

4.线性结构的特点

(1)集合中必存在唯一的一个"第一个元素";

(2)集合中必存在唯一的一个"最后的元素";

(3)除最后元素之外，其它数据元素均有唯一的"后继";

(4)除第一元素之外，其它数据元素均有唯一的"前驱"。

5.数组和链表的区别?

从逻辑结构来看：数组的存储长度是固定的，它不能适应数据动态增减的情况。链表能够动态分配存储空间以适应数据动态增减的情况，并且易于进行插入和删除操作。

从访问方式来看：数组在内存中是一片连续的存储空间，可以通过数组下标对数组进行随机访问，访问效率较高。链表是链式存储结构，存储空间不是必须连续的，可以是任意的，访问必须从前往后依次进行，访问效率较数组来说比较低。

如果从第i个位置插入多个元素，对于数组来说每一次插入都需要往后移动元素，每一次的时间复杂度都是O(n)，而单链表来说只需要在第一次寻找i的位置时时间复杂度为O(n)，其余的插入和删除操作时间复杂度均为O(1)，提高了插入和删除的效率。

第1章 绪 论

1.1 什么是数据结构

数据与数据之间的关系

1.2 基本概念和术语

1.基本定义

(1).数据(Data) ：是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素(Data Element) ：是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。

(2)数据项(Data Item)： 一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。

数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。

2.举例

如字符集合C={‘A’,‘B’,‘C’,…}

--C表示字符对象；A ，B等表示数据元素；

再如学生集合

Students={“Zhangsan”, “Lisi”，…}

Zhangsan(ID,name,age,grade,…)

……

--Students表示学生对象；“Zhangsan”、 “Lisi”表示数据元素；Zhangsan的ID、name、

age等表示数据项。

3.数据结构的形式定义

数据结构的形式定义是一个二元组：

Data-Structure=(D，S)

其中：D是数据元素的有限集，S是D上关系的有限集 4.逻辑结构与物理结构

(1)数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为定义的关系，这种自然或人为定义的 “关系”称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。

(2)数据结构在计算机中的表示（映像）称为数据的物理结构。

数据结构的存储方式

1)顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构(关系)。

2)链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针(pointer )，用该指针来表示数据元素之间的逻辑结构(关系)。

第1章 绪论

内容提要：

◆ 数据结构研究的内容。

针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。

数据结构涵盖的内容：

◆ 基本概念：数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型。

数据——所有能被计算机识别、存储和处理的符号的集合。

数据元素——是数据的基本单位，具有完整确定的实际意义。

数据对象——具有相同性质的数据元素的集合，是数据的一个子集。

数据结构——是相互之间存在一种或多种特定关系的数据元素的集合，表示为：

Data_Structure=（D, R）

数据类型——是一个值的集合和定义在该值上的一组操作的总称。

抽象数据类型——由用户定义的一个数学模型与定义在该模型上的一组操作，

它由基本的数据类型构成。

◆ 算法的定义及五个特征。

算法——是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。

算法的基本特性：输入、输出、有穷性、确定性、可行性

◆ 算法设计要求。

①正确性、②可读性、③健壮性、④效率与低存储量需求

◆ 算法分析。

时间复杂度、空间复杂度、稳定性

学习重点：

◆ 数据结构的“三要素”：逻辑结构、物理（存储）结构及在这种结构上所定义的操作（运算） 。

◆ 用计算语句频度来估算算法的时间复杂度。 第二章 线性表

内容提要：

◆ 线性表的逻辑结构定义，对线性表定义的操作。

线性表的定义：用数据元素的有限序列表示

◆ 线性表的存储结构：顺序存储结构和链式存储结构。

顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。

链式存储结构:

其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。通过指针来实现！

◆ 线性表的操作在两种存储结构中的实现。

数据结构的基本运算：修改、插入、删除、查找、排序

1) 修改——通过数组的下标便可访问某个特定元素并修改之。