数据结构 day01
大纲
1.数据结构
2.算法
3.线性表
顺序表：数组
链表：单向链表，单向循环链表，双向链表，双向循环链表
栈：顺序栈，链式栈
队列：顺序队列，链式队列
4.树：特性
二叉树：性质，创建，遍历
5.排序方法，查询方法：原理，思路
为什么学数据结构
1.C语言学习如何写程序，数据结构是为了简洁高效的写程序
2.如果遇到一个实际问题，需要写代码实现相应功能，需要解决两方面问题：
1）如何表达数据之间的逻辑关系，以及怎样储存在计算机中
数据结构：数据的逻辑结构，存储结构，操作（数据的运算）
数据：不是单纯的数字，更类似于集合的概念
结构：表达数据之间的关系
2）采用什么方法解决
采用算法解决
程序 = 数据结构 + 算法
问题—》数据结构 + 算法 == 程序—》解决问题
1.什么是数据结构
数据结构：数据的逻辑结构，存储结构，操作（数据的运算）
1.1. 数据
数据：类似于集合的概念
数据元素（节点）：数据的基本单位，由若干数据项组成
数据项：数据的最小单位，描述数据元素的信息
计算机处理对象不是单纯的数值
图书管理中的数据：
1.2. 逻辑结构
数据元素并不是孤立存在的，其间存在某种关系（联系和结构 ）
1.2.1. 线性关系
逻辑结构：线性结构
特点：一对一
线性结构：顺序表，链表，栈，队列
1.2.2. 层次关系
逻辑结构：树形结构
特点：一对多
树形结构：二叉树
1.2.3. 网状关系
逻辑结构：图状结构
特点：多对多
图状结构：图
1.3. 存储结构
数据的逻辑结构在计算机中具体实现
1.3.1. 顺序存储
数组：连续存储
特点：内存连续，随机存储，每个元素占空间较少
缺点：只能用一块大的且连续的空间，会产生空间的浪费
1.3.2. 链式存储
特点：内存不连续，使用指针实现
链表实现
结构体：
#include <stdio.h>
struct node_t
{
int data; // 数据域：存放节点的数据
struct node_t *next; // 指针域：结构体指针指向下一个节点
};
int main(int argc, char const *argv[])
{
struct node_t A = {1, NULL};
struct node_t B = {2, NULL};
struct node_t C = {3, NULL};
A.next = &B;
B.next = &C;
return 0;
}
1.3.3. 索引存储结构
在存储数据的同时，建立索引表。即索引存储结构 = 索引表 + 数据文件。
特点：提高查找速度，检索速度快
缺点：占用内存多，删除数据文件要及时更改索引表
1.3.4. 散列存储
数据存储按照和关键码之间的关系进行存取。关系由自己决定。
例如关键码为key，下一个存储的关键码是key+1。
获取关键数据，通过元素的关键码的返回值来获取，存取都按照相应的关系存取
与商场的储物柜类似，给你一个号码，存取物品时查找号码来存取
1.4. 操作
增， 删， 改，查
2. 什么是算法
算法是解决问题的思想方法，数据结构是算法的基础
2.1. 算法的设计
设计取决于数据的逻辑结构
实现依赖于数据的存储结构
2.2. 特性
有穷性：步骤是有限的
确定性：每一步有明确的含义，不能有争议
可行性：规定时间内能完成
输入 输出
2.3. 评价算法的好坏
1）正确性
2）易读性
3）健壮性：有一定容错处理
4）高效性：执行效率，通过重复执行的次数来判断，也就是通过时间复杂度（时间处理函数）来判断
时间复杂度
语句频度：用时间规模函数表达
时间规模函数：T(n) = O(f(n))
T(n) // 时间规模函数
O // 时间数量级
n // 问题规模，a[100], n = 100
f(n) // 算法可执行语句重复执行次数
例题1：求1+2+3+4+……+n 的和
算法1
int sum = 0; for(int i = 1; i <= n; i++) { sum+=i; }n = 100
f(n) = 100
T(n) = O(n)
算法2
利用等差数列前n项和公式
int sum = n*(1+n)/2;n = 100，执行一次
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 次
f(n) = n^2
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+3+……+n
f(n) = n*(1+n)/2 = n^2/2 + n/2
T(n) = O(n^2)
计算方法：
1）根据问题规模 n 写出表达式
2）有常数项时，常数项置1
3）只保留最高项，最高项系数置1
f(n) = 3*n^4 + 2*n^3 + 6*n^7 +10
T(n) = O(n^7)
3. 线性表
线性表是最基本，最简单，最常用的数据结构，可以存储逻辑关系为线性的数据。一个线性表是 n 个具有相同特性的数据元素的有限序列。
包含：
顺序表：数组
链表：单向链表，单向循环链表，双向链表，双向循环链表
栈：顺序栈，链式栈
队列：顺序队列，链式队列
逻辑结构：线性结构
存储结构：顺序存储（数组），链式存储（指针）
特点：一对一，每个节点最多一个前驱，一个后继
首节点无前驱，尾节点无后继
3.1. 顺序表
顺序表存储数据的具体实现方案：将数据全部存储到一整块内存中，数据元素之间按照次序挨个存放。
举个简单的例子，将 {1,2,3,4,5} 这些数据使用顺序表存储，数据最终的存储状态如下
3.1.1. 顺序表的特性
特点：内存连续
逻辑结构：线性结构
存储结构：顺序存储
操作：增删改查
3.1.2. 操作数组
例题
int a[100] = {1, 2, 3, 4, 5, 6, 7, 8};
int last = 7; // 代表最后一个有效元素下标 last = 有效元素个数-1
全局变量 last 表示有效元素的下标
1）插入数组元素
函数：void insetIntoA( int *p, int post, int data);
功能：向数组的第几个位置插入数据
参数：
int *p // 保存数组首地址
int post // 插入元素下标
int data // 数据
#include <stdio.h> // 向数组的第几个位置插数据 void insetIntoA(int *p, int post, int data) { // 1. 把从最后一个元素p[n-1]开始到插入元素p[post]向后移动一个位置 for (int i = last; i >= post; i--) { p[i+1] = p[i]; } // 插入新元素 data 到定义位置 p[post] = data; last++; }
2）遍历数组中的有效元素
函数：void showA( int *p);
功能：遍历数组中的有效元素
参数：
int *p // 保存数组首地址
// 遍历数组中的有效元素 void showA(int *p, int n) { for (int i = 0; i < last+1; i++) { printf("%d ", p[i]); } printf("\n"); }
3）删除数组元素
函数：void deleteIntoA( int *p, int post);
功能：删除数组中指定元素
参数：
int *p // 保存数组首地址
int post // 删除元素下标
void deleteIntoA(int *p, int n, int post) { // 从删除位置后一个元素p[post+1]到p[n-1]往前移动一个单位 for (int i = post + 1; i < last+1; i++) { p[i-1] = p[i]; } last--; }