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

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

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

存取方式→随机存取、串行(顺序)存取、直接存取

存取方式→顺序、链式、索引、散列

存取 随串直

李明到存钱机取钱,取了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)提出的：

"算法+数据结构=程序”

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

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

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

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

如何设计一个“好”的算法

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

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

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

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

算法与数据结构关系举例

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

存放2个数据项：

姓名+Te1

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

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

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

姓氏，查找效得到提高。

算法与数据结构关系举例

总结

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

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

一个特定算法的“运行工作量”的大小，只依赖于问题的规模(通常用整数量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;
}