数据结构.

1:基本大纲

1. 数据结构、算法
2. 线性表：顺序表、链表、栈、队列
3. 树：二叉树、遍历、创建
4. 查询方法、排序方式

2:数据结构（逻辑结构，存储结构，操作（数据的运算））

2.1：数据：不是单一数值，与集合类似

        数据元素：数据基本单位，由若干数据项组成

        数据项：数据的最小单位

2.2：节点：数据元素

2.3;逻辑结构

线性关系：一对一      线性结构    --> 线性表：顺序表，链表 ，栈，队列

层次关系：一对多    树形结构    --> 树

网状关系：多对多     图状结构 --> 图

2.3:存储结构

2.3.1：顺序存储结构（数组，链式存储（链表））

3：链式存储结构

特点：数据在内存中是不连续的，通过指针进行连接

链表结构体 ：

struct  node_t
{int data;//数据域struct  node_t *next;//指针域， 指向自身结构体类型的指针
}；

struct node_t A={1,NULL};

struct node_t B={2,NULL};

struct node_t C={3,NULL};

1. A.next = &B;
2. B.next = &C; 

3.1：索引存储结构

提高查找速度

索引表 + 数据文件

 3.2：散列存储

数据在存储的时候与关键码之间存在某种对应关系

存的时候按照对应关系存

取的时候按照对应关系取

4：操作： 增、删、改、查

二：算法

2.1：算法的特性：

1：有穷性：执行步骤有限

2：确定性：

3：可行性：有限时间内完成

4：输入和输出

2.2：如何评价算法好坏？

正确性：保证可以正确实现功能

易读性：容易被解读

健壮性：容错处理

高效性：可执行语句重复执行的次数来衡量算法是否高效（时间复杂度）

低存储性：占用空间少

2.3：时间复杂度

算法的可重复执行语句执行的次数

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

T(n) //问题规模的时间函数

n //问题规模，输入量的大小

O //时间数量级

f(n) //算法的可执行语句重复执行的次数 用问题规模n的某个函数f(n)来表达

例1：

求1+2+3+。。。+n

方法1：

sum = 0;

for(int i = 1;i<=n;i++) n==100 10000

sum+=i; 100次 10000

f(n) = n

T(n)=O(n)

方法2：

等差数列{an}的通项公式为：an=a1+(n-1)d。前n项和公式为：Sn=n*a1+n(n-1)d/2或Sn=n(a1+an)/2 。

int sum = n(1+n)/2; n=100,1次

f(n)=1

T(n)=O(1)

例2：

int i,j;

for(i=0;i<n;i++) //n

for(j=0;j<n;j++) //n

printf(“ok\n”);

T(n) = O(n^2);

例3：

int i,j;

for(i=0;i<n;i++)

for(j=0;j<=i;j++)

printf(“ok\n”);

i 次数

0 1

1 2

2 3

n-1 n

f(n) = 1+2+3+...+n = n(1+n)/2 = n/2 + n^2/2 ----> n^2

3：计算大O的方法

(1)根据问题规模n写出表达式 f(n)

1. 只保留最高项，其它项舍去
2. 如果最高项系数不为1，除以最高项系数
3. 如果有常数项，将其置为1 //当f(n)的表达式中只有常数项的时候，有意义 f(n) = 8

f(n)=8 O(1)

//f(n) = 3n^5 + 2n^3 + 6*n^6 + 10

3.6空间复杂度

算法占用的空间大小。一般将算法的辅助空间作为衡量空间复杂度的标准。

算法占用的存储空间包括：

1）输入输出数据所占空间

2）算法本身所占空间

3）额外需要的辅助空间

顺序表总结：

1. 顺序表在内存中连续存储
2. 顺序表的长度是固定的，#define N 5
3. 顺序表查找数据、修改数据比较方便的，插入和删除麻烦