数据结构_day1

目录

大纲

1.数据结构基础知识

1.1 什么是数据结构

1.2 数据

1.3 逻辑结构

1.4 存储结构

1.4.1 顺序存储

1.4.2 链式存储

1.4.3 索引存储结构

1.4.4 散列存储

1.5 操作

2.算法基础知识

2.1 什么是算法

2.2 算法的设计

2.3 算法的特性

2.4 评价算法的好坏

---

大纲

数据结构、算法(理解)

线性表：顺序表(数组)、链表(单向链表、单向循环链表、双向链表、双向循环链表)、栈(顺序栈、链式栈)、队列(循环队列、链式队列)

树：特性、二叉树(性质、创建、遍历)

排序方法、查询方法(原理、思路)

1.数据结构基础知识

1.1 什么是数据结构

数据结构就是数据的逻辑结构以及存储操作 (类似数据的运算)

数据结构就教会你一件事：如何更有效的存储数据

1.2 数据

数据：不再是单纯的数字，而是类似于集合的概念。

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

数据项：数据的最小单位，描述数据元素的有用的信息。

数据元素又叫节点

例如：

计算机处理的对象(数据)已不再是单纯的数值：

图书管理中的数据，如下表所列:

数据：图书

数据元素：每一本书

数据项：编号、书名、作者、出版社等

1.3 逻辑结构

数据元素并不是孤立存在的，它们之间存在着某种关系(或联系、结构)。元素和元素之间的关系：

• 线性关系

线性结构 ==> 一对一 ==> 线性表：顺序表、链表、栈、队列

• 层次关系

树形结构 ==> 一对多 ==> 树：二叉树

• 网状关系

图状结构 ==> 多对多 ==> 图

例题：

田径比赛的时间安排问题

1.4 存储结构

数据的逻辑结构在计算机中的具体实现（数据的运算）

1.4.1 顺序存储

特点：内存连续、随机存取、每个元素占用较少

实现：数组

1.4.2 链式存储

通过指针存储

特点：内存不连续，通过指针实现

链表实现：

结构体：

#include <stdio.h>struct node
{int data;          //数据域：存放节点中要保存的数据struct node *next; //指针域：保存下一个节点的地址，也就是说指向了下一个节点 (类型为自身结构体指针)
};int main()
{//定义三个节点struct node A = {1, NULL}; //定义结构体变量的同时给每个成员赋值struct node B = {2, NULL};struct node C = {3, NULL};// struct node D;   //先定义结构体变量，再单独给其中成员赋值// D.data=4;// D.next=NULL;//连接三个节点A.next = &B; //连接A和B节点，通过让A中的指针域保存B的地址B.next = &C;printf("%d\n", A.data);printf("%d\n", A.next->data);printf("%d\n", A.next->next->data);
}

1.4.3 索引存储结构

在存储数据的同时，建立一个附加的索引表。

也就是索引存储结构 = 索引表 + 存数据的文件

可以提高查找速度，特点检索速度快，但是占用内存多，删除数据文件要及时更改索引表。

1.4.4 散列存储

数据存储按照和关键码之间的关系进行存取。关系由自己决定，比如关键码是key, 存储位置也就是关系是key+1。获取关键数据，通过元素的关键码方法的返回值来获取。

存的时候按关系存

取的时候按关系取

1.5 操作

增删改查

2.算法基础知识

2.1 什么是算法

算法就是解决问题的思想方法，数据结构是算法的基础。

数据结构 + 算法 = 程序

2.2 算法的设计

算法的设计： 取决于数据的逻辑结构

算法的实现：依赖于数据的存储结构

2.3 算法的特性

有穷性： 步骤是有限

确定性：每一个步骤都有明确的含义，无二义性

可行性：在规定时间内可以完成

输入

输出

2.4 评价算法的好坏

正确性

易读性

健壮性：容错处理

高效性：执行效率，通过重复执行语句的次数来判断，也就是时间复杂度(时间处理函数)来判断。

时间复杂度：

语句频度：用时间规模函数表达

时间规模函数: T(n)=O(f(n))

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

O //时间数量级

n //问题规模，例如：a[100], n=100

f(n) //算法可执行重复语句的次数

称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

渐进时间复杂度用大写O来表示，所以也被称为大O表示法。直白的讲，时间复杂度就是把时间规模函数T(n)简化为一个数量级，如n，n^2，n^3。

例1：

求1+2+3+4+...+n的和

算法1：

int sum=0;
for(int i=1;i<=n;i++)
{sum += i; //重复执行n次
}

f(n) = n

==>T(n) = O(n)

算法2：

利用等差数列前n项和公式：Sn=n*a1+n(n-1)d/2 或 Sn=n(a1+an)/2 (d是公差）

int sum = (1+n)*n/2;   //重复执行1次

f(n) = 1

==> T(n) = O(1)

例2：

int i,j;
for(i=0;i<n;i++)
{for(j=0;j<n;j++){printf("ok\n");        //重复执行n*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");  }
}

1 + 2 + ... n

f(n) = n*(1+n)/2 = n^2/2 + n/2 //只保留最高项n^2/2, 除以最高项系数 得到n^2

T(n) = O(n^2)

计算大O的方法

1. 根据问题规模n写出表达式f(n)
2. 如果有常数项，将其置为1 //当f(n)的表达式中只有常数项，例如f(n) = 8 ==> O(1)
3. 只保留最高项，其他项舍去。
4. 如果最高项系数不为1，则除以最高项系数。

f(n) = 3*n^4 + 2*n^3 + 6*n^7 +10;

==> O(n^7)