/48;/48;/48;1.1什么是数据结构;数据：所有能够输入到计算机中，且能被计算机处理的符号的集合。;Word文档;学号;数据元素：是数据（集合）中的一个“个体”，它是数据的基本单位。
数据项：数据项是用来描述数据元素的，它是数据的最小单位。;;不相邻;逻辑结构;数据的逻辑结构是从数据元素的逻辑关系上描述数据的。
是指数据元素之间的逻辑关系的整体，通常是从求解问题中提炼出来的。
数据逻辑结构与数据的存储无关，是独立于计算机的。;数据的逻辑结构是面向用户的，它有多种表示形式。;1001;一个二元组表示为：
B=(D，R)
其中，B是一种数据结构，它由数据元素的集合D和D上二元关系的集合R所组成。其中：
D={di|1≤i≤n，n≥0}：数据元素的集合
R={rj|1≤j≤m，m≥0}：关系的集合;序偶x，y（x，y∈D）?x为第一元素，y为第二元素。
x为y的前驱元素。
y为x的后继元素。
若某个元素没有前驱元素，则称该元素为开始元素；若某个元素没有后继元素，则称该元素为终端元素。;二元组逻辑表示：;例如，如下数据为一个矩阵：;元素之间关系：无。
特点：数据元素之间除了“属于同一个集合”的关系外，别无其他逻辑关系。是最松散的，不受任何制约的关系。;元素之间关系：一对一。
特点：开始元素和终端元素都是唯一的，除此之外，其余元素都有且仅有一个前驱元素和一个后继元素。;元素之间关系：一对多。
特点：开始元素唯一，终端元素不唯一。除终端元素以外，每个元素有一个或多个后续元素；除开始元素外，每个元素有且仅有一个前驱元素。;【例1-3】有一种数据结构B2=（D，R），其中
D={48，25，64，57，82，36，75}
R={r1，r2}
r1={25，36，36，48，48，57，57，64，
64，75，75，82}
r2={48，25，48，64，64，57，64，82，
25，36，82，75};48;元素之间关系：多对多。
特点：所有元素都可能有多个前驱元素和多个后继元素。;;数据逻辑结构在计算机中的存储表示称为数据的存储结构，也称为物理结构。;顺序存储结构
链式存储结构
索引存储结构
哈希（散列）存储结构;struct
{intno; //存储学号
charname[8]; //存储姓名
intscore; //存储成绩
}Stud[6]={{1001,“张梦”,87},
…,
{1006,王生,90}};;学号;顺序存储结构的特点：;typedefstructscore
{
intnum;
charname[10];
intC_score;
}StuScore;
typedefstructstudentscore
{
StuScoredata;
structstudentscore*next;
}LN_score;//链式存储结构定义学生成绩表;学生成绩表的逻辑结构;学生成绩表的逻辑结构;一个逻辑元素用一个结点存储，每个结点单独分配，所有结点的地址不一定是连续的。
用指针来表示逻辑关系。;学号
（关键字）;查找关键字（如学号）为k的元素时：
先在索引表中快速查找（因为索引表中按关键字有序排列，可以采用二分查找）到相应的关键字k。
然后通过对应地址在主数据表中找到元素。;通过索引表按关键字查找速度快
增加索引表?存储空间较大;哈希存储结构=哈希函数+解决冲突方法。
哈希函数h(key)将关键字为key的元素存放在该地址。
查找关键字为key的元素时，先计算h(key)，由该值和解决冲突方法来确定其存储地址。;学号;地址;按关键字查找速度快
需要解决冲突
但不适合任何数据的存储;同一逻辑结构可以对应多种存储结构。;数据运算是对数据的操作。
数据运算分为两个层次：运算定义（或运算描述）和运算实现。;对于“学生成绩表”这种数据结构，可以进行一系列的运算：;;;同一逻辑结构可以对应多种存储结构。
同样的运算，在不同的存储结构中，其实现过程是不同的。;/48;分析算法占用的资源;算法分析的目的是（）。
A.找出数据结构的合理性
B.研究算法中输入和输出的关系
C.分析算法的效率以求改进
D.分析算法的易读性和可行性;算法中的基本操作一般是最深层循环内的原操作。
算法执行时间大致=基本操作所需的时间×其运算次数。;算法运行时间=一个简单操作所需的时间×简单