数据 – 是描述客观事物的符号, 是计算机可以操作的对象
结构 – 关系
在计算机中, 数据并不是孤立的,无序的,而是存在一定的关系.
数据存储 :
int age = 19;
char* name = “james”;
int a[] = {1, 2, 3, 4, 5};
char* name[] = {
“maji”, “madong”, “houyaowen”, “guodegang”, “yueyunpeng”};
存储数据 – 名字 – 没问题
缺点 – 没有存储数据之间的关系
变量 数组 结构体 malloc – 记录/存储 数据
数据之间的关系 – no
树结构
数据结构 :
1.如何存储数据
2.存储数据之间的关系
使用这些数据
算法 :
有位大神说过
程序 = 数据结构 + 算法
算法 – 如何处理信息
五个特点:
有穷性、确定性、可行性、输入、输出
目标 – 好的算法
正确性、可读性、健壮性、高效率和低存储
高效率 – 执行速度快
低存储 – 内存占用小
查找算法 – 搜索引擎 高性能数据库
排序算法 – Excel 任务调度 搜索引擎结果显示
高效率 – 时间 – 时间复杂度
时间开销 – 事后统计
机器性能
编程语言
编译的机器
无法事后统计
预先估计 – 时间复杂度
实际预估时间开销 – T
问题规模 – n
void go_home(int n){
int i = 1;
while(i <= n){
printf(“go step : %d\n”, i)
}
printf(“go step more than %d\n”, i)
}
int main(void){
go_home(10000);
}
语句频度:
int i = 1; ——————————>1次
while(i <= n){—————————->10001次
i++;———————————->10000次
printf(“go step : %d\n”, i)———–>10000次
}
printf(“go step more than %d\n”, i)——->1次
T(10000) = 1 + 10001 + 10000*2 + 1 = 3 * 10000 + 3
T(n) = 3n + 3
简化时间复杂度 –
当n的值为足够大的时候, 省略比较低阶的部分, 只保留最高阶的部分
T(n) = 3n
T(n) = n
O(n)
T(n) = n² + n + 1
T(1) = 1 + 1 + 1 = 3
T(10000) = 100000000 + 1000 + 1
= 100010001
O(n²)
很多代码
顺序执行 – 可以忽略
循环执行
多层循环 – 最内层循环
===============================
数据结构主要研究什么问题 –
一、逻辑结构 – 数据和数据之间的关系
1、集合结构
– 集合中的数据,同属于一个集合,没有任何其他关系
2、线性结构
– 线性结构中的数据元素之间是一对一的先后关系
3、树形结构
– 一对多的关系
4、图形结构
– 多对多的关系
二、存储结构/物理结构 – 数据在计算机中的存储形式
1、顺序存储结构
1）数据元素放在连续的存储单元里
2）逻辑上相连的元素在物理上也是相连的
2、链式存储结构
1）逻辑上相邻的数据元素在物理上可以不相邻
2）借助于元素存储的指针来表示元素之间的逻辑关系
3）吃饭排队拿号 – 银行办业务
3、顺序 – 链式
– 顺 – 物理上是连续的
– 链 – 非顺序, 可以是离散的
— 影响存储空间分配的方便程序 – 链式
— 影响数据运算的速度 – 顺序
4、索引存储结构
– 在存储元素信息的同时, 建立附加的索引表
5、散列存储结构 – 哈希存储
– 根据元素的关键字直接计算出该元素的存储地址
三、数据运算
– 运算的定义 – 针对逻辑结构
– 运算的实现 – 针对物理结构
数据结构研究对象:
栈 队列 单链表 双链表 二叉树
————————————————————————————————-
栈：
使用只能在一端进行插入和删除操作的特殊线性表
按照后进先出的原则存储数据
先进入的数据被压入栈底, 最后的数据在栈顶
需要读取数据的时候从栈顶开始读取数据
先进后出 后进先出
内存是连续的
以数组的方式来存储数据 – 具有随机访问的能力
将数据保存到栈的内存中的过程 – 入栈 – 压栈 – push stack
将数据从栈中获取的过程 – 出栈 – 弹栈 – pop stack
声明一个栈的数据结构:
struct stack{
int* arr;//作为栈的首地址
int cap;//作为栈的容量
int top;//栈顶
};
分析:
1.栈的成员
arr – 栈的首地址
cap – 栈的容量
2.将数据放入到栈的哪个位置, 从栈的哪个位置上获取数据
需要有一个标识- 标识可以将数据放到哪里 – 标识可以从哪里获取数据
top – 标识/记录 读写的位置 – 下标
top – 栈顶
在栈中没有任何的数据 此时栈顶的位置应该为多少 – 0
3.初始化
int* arr; – 有没有分配存储区来存储数据
– 仅仅是一个首地址
– 分配栈的存储
cap
top – 没有任何的数据 – 将top初始化为0 – 放入到下标为0的位置上
free(stack)
————————————————————————————————-
代码:
stack.h
#ifndef _STACK_H
#define _STACK_H
//包含的公共头文件
#include <stdio.h>
#include <stdlib.h>
//声明描述栈的属性的结构体
typedef struct stack{
int* arr;
int cap;
int top;
}stack_t;
//声明栈的操作函数
extern void stack_init(stack_t* stack, int cap);//初始化
extern void stack_deinit(stack_t* stack);//释放
extern int stack_full(stack_t* stack);//判断满
extern int stack_empty(stack_t* stack);//判断空
extern void stack_push(stack_t* stack, int data);//入栈
extern int stack_pop(stack_t* stack);//出栈
extern int stack_size(stack_t* stack);//栈的元素个数
#endif //_STACK_H
stack.c
//stack.c
#include "stack.h"
//栈的初始化
void stack_init(stack_t* stack, int cap){
//给栈分配内存
stack->arr = malloc(sizeof(int)*cap);
//初始化容量
stack->cap = cap;
//初始化top
stack->top = 0;
}
//栈的内存的释放
void stack_deinit(stack_t* stack){
free(stack->arr);//释放内存
stack->cap = 0;
stack->top = 0;
}
//判断栈是否为满
int stack_full(stack_t* stack){
//满, 1
//非满, 0
return stack->top == stack->cap;
}
//判断栈是否为空
int stack_empty(stack_t* stack){
//空, 1
//非空, 0
return stack->top == 0;
}
//定义入栈函数
void stack_push(stack_t* stack, int data){
//将数据data放到下表为top的位置
stack->arr[stack->top] = data;
stack->top++;
}
//定义出栈函数
int stack_pop(stack_t* stack){
stack->top--;
return stack->arr[stack->top];
}
//判断栈中有效数据个数的函数
int stack_size(stack_t* stack){
return stack->top;
}
main.c
#include "stack.h"
int main(void){
//定义栈变量
stack_t stack;
//栈的初始化
stack_init(&stack, 20);
int data = 520;
while(!stack_full(&stack))//压栈
stack_push(&stack, data++);
printf("栈中的有效数据个数是:%d个\n", stack_size(&stack));
printf("栈中的数据为:");
//循环出栈
while(!stack_empty(&stack))//非空
printf("%d ", stack_pop(&stack));
printf("\n");
printf("栈中的有效数据个数是:%d个\n", stack_size(&stack));
//栈的内存释放
stack_deinit(&stack);
return 0;
}
数据结构可以简单理解为
存储区 + 操作函数
并没有特别高深的地方
