第一章:绪论(数据结构)

 ；

不同结构操作效率是不一样的.

顺序存储结构也叫连续存储结构

 ；

 ；

存取方式&rarr；随机存取、串行(顺序)存取、直接存取

存取方式&rarr；顺序、链式、索引、散列

存取 随串直

李明到存钱机取钱,取了100元,去小吃摊买了1瓶矿泉水和1窜羊肉串和1个芝麻饼

存储 ； 顺链索散

然后去商店买了老陈醋,正准备回家是,发现孙子把自行车链子用索锁住了,他气愤冲了过去扇了孙子一巴掌

 ；

 ；

 ； ； ； ； ； ； ； ； ； ；

 ； ； ； ； ； ； ； ； ； ； ； ； ； ； ； ； ； ； 定义/特点 ； ；

 ；

 ；

抽象数据类型 ADT\(\begin{equation}\begin{cases}     存储+操作,  \\     描素规则  \\ \end{cases}\end{equation}\)

ADT ； 类型名

{

 ； ； ； ；实现每一个操作

 ；

}

数据结构的定义(DS)+算法评价方法+ADT 描述形式

1.1数据结构的基本概念和术语

1.基本术语

（1）数据：描述客观事物的数字、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。（数字、字符、声音、图形、图像等等）

（2）数据元素：数据的基本单位，在计算机程序中常常作为一个整体进行考虑和处理，如纪录/结构。

（3）数据项：数据的不可分割的最小单位，如结构中的域。

（4）数据对象：性质相同的数据元素的集合，是数据的一个子集。

 ；

2．数据结构

（1)定义：是相互之间存在一种或多种特定关系的数据元素的集合。

另一种定义：按照逻辑关系组织起来的一批据，按一定的存储方法把它存储在计算机中，并在这些据上定义了一个运算的集合。

 ；

（2）四种基本结构（逻辑结构）

集合：元素仅属于同一个集体，没有其他关系。

能线性结构：存在一对一关系，序列相邻，次序关系。

树型结构：存在一对多关系，层次关系

图状结构（网状结构）：存在多对多关系，任意性。

存储器模型：一个存储器M是一系列固定大小的储单元

每个单元U有一唯一的地址A（U)，该地址被连地编码

每个单元U有一个唯一的后继单元U'；=succ(U)

四种存储结构：顺序存储、链接存储、索引存储、散列存储

 ；

 ；

3．数据结构的划分

(1）按数据结构的性质划分

集合：元素仅属于同一个集体，没有其他关系。

数据的逻辑结构一数据元素之间的逻辑关系

（设计算法一数学模型）。数据的物理结构一数据结构在计算机中的映像

（存储结构，算法的实现）

1.2抽象数据类型一ADT

定义：是指基于一个逻辑类型的数据模型以及定义在该模型上的一组操作。每一个操作由它的输入和输出定义。

 ；抽象的与具体的相对应

示例：

int a,b；则a和b可以进行+,一,*,/的运算

2和6则是具体的int数据

1.3算法和算法分析

1.算法

定义：指一系列确定的而且是在有限步骤内能完成的操作。

 ；

 ；

3 .算法设计的要求

（ 1) 正确性

（ 2 ）可读性

首先是给人读，然后才是机器执行

（ 3 ）健壮性容错性

（ 4 ）效率与低存储量需求

 ；

 ；

2．算法与数据结构的关系

数据计算机科学家沃斯（N.Wirth)提出的：

"；算法+数据结构=程序&rdquo；

揭示了程序设计的本质:实问题选择了种好的数据

结构，加上设计一个好的《于描述际问题的数据结构。算与数据结构是互相互相系的。

一个算法总是建立在一定数据结构上的：反之，算法不确

定，就无法决定如何构造数据。

如何设计一个&ldquo；好&rdquo；的算法

正确性 算法应能够正确地解决求解问题

可读性 ； 算法应具有良好的可读性，以帮助人们理解

健壮性 ； 输入非法数据时，算法能适应的做出反应或进行处理

效率与存储量 ； 效率是指算法执行时间，存储量需求是指算法执行过程中所需最大存储空间

 ；

算法与数据结构关系举例

例1：编写程序查询某城市某人的电话号码建立一张登记表，

存放2个数据项：

姓名+Te1

好的算法取决于这张表的结构及存储方式：

&radic；将出结点照姓名顺序地存储在计算机中，依次查找，

&radic；建立一张姓氏引表：姓+表中的起始地址则不需查找其他

姓氏，查找效得到提高。

 ；

算法与数据结构关系举例

总结

解决问题的关键步骤是先选取合适的数据结构表示问题，才能写出有效的算法。

 ；

 ；

 ；

(三)算法效率的衡量方法和准则

一个特定算法的&ldquo；运行工作量&rdquo；的大小，只依赖于问题的规模(通常用整数量n表示)或者说，它是问题规模的函数。

假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作:

T (n) = O(f(n))

称T (n)为算法的(渐近)时间复杂度。

 ；

如何估算算法的时间复杂度?

算法=控制结构+原操作

(固有数据类型的操作)

算法的执行时间=原操作(i)的执行次数X原操作(i)的执行时间

算法的执行时间与原操作执行次数之和成正比

对 数 函 数 く 幂 ；函 数 く 指 数 函 数

6．空间复杂度

（1)存储算法本身所占用的空间

（2）算法的输入/输出数据占用的空间

（3）算法在运行过程中临时占用的辅助空间

原地工作：若辅助空间相对于输入数据量是常数，则称算法是原地工作。

若所占空间量依赖于特定的输入，按最坏情况来分析

 ；

 ；

 ；结构体:不同类型变量组合在一起构成的变量。

typedef struct

{

    int a；

    float b；

    char C；

    …

}结构体名

typedef struct 结构名

{

    int a；

    float b；

    char C；

    struct 结构名 *d；

    …

}结构体名

int*P=NULL；

void getResult (int *&；P)

{

    …

    p=q；

    …

}



调用: getResult (p) ；

 ；

 ；

C++转变成c语言

​
 int result =0；

void getResult(int &；r)

{

    ++r；

}

调用getResult(result)；

↓ plainc

int result = 0；

void getResult(int *r)

{

    ++r；

}

调用getResult(&；result)；

​

 ；

int *p = NULL；

void getResult(int *p)

{

    …

    p = q；

    …

}

调用getResult(p)；

↓ plainc

int *p = NULL；

void getResult(int **p)

{

    …

    *p = q；

    …

}

调用getResult(&；p)；

for(i=1；i<；=9；i++)
    for(j=i+1；j<；=10；j++)
        i++；

#include<；stdio.h>；
#pragma warning(disable:4996)
void pr()
{
char ch；
scanf("%c", &；ch)；
if (ch != '#')pr()；
printf("% c", ch)；
}

int main()
{
pr()；
return 0；
}