数据结构与算法

简介

数据结构

数据结构（Data Structure）是计算机中存储、组织和管理数据的方式，旨在高效地访问和修改数据。

它定义了数据元素之间的逻辑关系、操作（如增删查改）以及如何在内存中物理存储。

算法(Algorithm）

算法是实现的、解决问题的步骤逻辑，强调效率与正确性。

它是编写高性能程序的基础，通常通过函数、循环和数据结构组合实现。

内容:

顺序查找

二分查找

排序：冒泡、快速排序

数据结构

• 基本概念

  • 物理结构
  • 逻辑结构

• 操作数据的方法（增、删、改、查看）

  • 增加数据
  • 删除数据
  • 修改数据
  • 查看数据
  • 初始化数据
  • 销毁数据

内容:

• 线性表
• 动态数组
• 链表
• 栈
• 队列
• 树

顺序存储(数组）

写一个程序，用来存储学生的成绩。

操作方法:

1. 初始化数据结构
2. 添加学生成绩
3. 打印所有的学生成绩
4. 修改第 i 个学生的成绩。
5. 删除某个位置的学生成绩。
6. 销毁数据结构.
7. 在 pos 之前的位置插入学生的成绩

数据结构

struct stu_score {int data[100];  // 用来保存学生的成绩数据int count; // 用来记录学生的个数。
}

初始代码

#include <stdio.h>struct stu_score {int data[100];  // 用来保存学生的成绩数据int count; // 用来记录学生的个数。
};
// 1.  初始化数据结构,成功返回1，不成功返回0
int init_data(struct stu_score *stu) { }
// 2.  添加学生成绩,成功返回1，不成功返回0
int append_data(struct stu_score * stu, int score) {}
// 3.  打印所有的学生成绩
void list_all_data(const struct stu_score * stu) {}
// 4.  修改第 i 个学生的成绩。
int modify_data(struct stu_score * stu, int pos, int score) {}
// 5.  删除某个位置的学生成绩。
int remove_data(struct stu_score * stu, int pos) {}
// 6.  销毁数据结构.
int destroy_data(struct stu_score * stu) {}
// 7.  在 pos 之前的位置插入学生的成绩
int insert_data(struct stu_score * stu, int pos, int score){}int main(int argc, char * argv[]) {struct stu_score stu; // 定义一个顺序存储数据的变量return 0;
}

最终代码：

#include <stdio.h>struct stu_score {int data[100];  // 用来保存学生的成绩数据int count; // 用来记录学生的个数。
};
// 1.  初始化数据结构,成功返回1，不成功返回0
int init_data(struct stu_score *stu) {stu->count = 0;   // (*stu).count = 0;return 1;
}
// 2.  添加学生成绩,成功返回1，不成功返回0
int append_data(struct stu_score * stu, int score) {if (stu->count >= sizeof(stu->data)/sizeof(stu->data[0]) )return 0;stu->data[stu->count] = score;stu->count++;return 1;
}
// 3.  打印所有的学生成绩
void list_all_data(const struct stu_score * stu) {printf("学生个数：%d\n", stu->count);for (int i = 0; i < stu->count; i++) {printf("%d ", stu->data[i]);}printf("\n");
}
// 4.  修改第 i 个学生的成绩。pos 从 0 开始
int modify_data(struct stu_score * stu, int pos, int score){if (pos < 0 || pos >= stu->count)return 0;stu->data[pos] = score;return 1;}
// 5.  删除某个位置的学生成绩。
int remove_data(struct stu_score * stu, int pos) {if (pos < 0 || pos >= stu->count)return 0;for (int i = pos; i < stu->count -1; i++) {stu->data[i] = stu->data[i+1];}stu->count--;return 1;
}
// 6.  销毁数据结构.
int destroy_data(struct stu_score * stu) {return 1;
}
// 7.  在 pos 之前的位置插入学生的成绩
int insert_data(struct stu_score * stu, int pos, int score){if (pos < 0 || pos > stu->count)return 0;for (int i = stu->count - 1; i >= pos; i--) {stu->data[i+1] = stu->data[i];}stu->data[pos] = score;stu->count++;
}int main(int argc, char * argv[]) {struct stu_score stu; // 定义一个顺序存储数据的变量int ret; // 此变量用来保存函数的返回值ret = init_data(&stu);printf("init_data: ret:%d\n", ret);ret = append_data(&stu, 100);printf("append_data: ret:%d\n", ret);ret = append_data(&stu, 90);ret = append_data(&stu, 80);list_all_data(&stu);  // 打印列表ret = modify_data(&stu, 2,99);//将第三个学生的成绩改成99printf("modify_data: ret:%d\n", ret);list_all_data(&stu);  // 打印列表ret = remove_data(&stu, 3);printf("remove_data: ret:%d\n", ret);list_all_data(&stu);  // 打印列表ret = insert_data(&stu, 1, 60);printf("insert_data: ret:%d\n", ret);list_all_data(&stu);  // 打印列表return 0;
}

时间复杂度：

算法的时间复杂度是衡量算法运行时间随输入规模增长而变化的度量，通常用大O符号（O-notation）表示。它描述的是在最坏情况下，算法执行的基本操作次数与输入规模之间的关系，忽略常数项和低阶项，专注于增长趋势。

输入规模（n）

按增长速度从低到高排序：

1. 常数时间
   O(1)：操作次数与输入规模无关（如数组随机访问）。
2. 对数时间
   O(log⁡n)：常见于分治算法（如二分查找）。
3. 线性时间
   O(n)：操作次数与输入规模成正比（如遍历数组）。
4. 线性对数时间
   O(nlog⁡n)：常见于高效排序算法（归并排序）。
5. 平方时间
   O(n2)：常见于双重循环（如冒泡排序）。
6. 指数时间
   O(2n) 或 O(n!)：常见于暴力搜索。

动态数组

动态数组也是顺序存储结构，动态数组使用动态分配的内存存储数据，在数据已经满的情况下，分配更多的内存来存储数据。

动态数组示例

#include <stdio.h>
#include <stdlib.h>struct stu_score {int * data;  // 用来保存学生的成绩数据的指针int count; // 用来记录学生的个数。int max_count;  // 用来记录当前内存能存储的最大数据
};
// 0. 扩大动态数组，将内存长度扩大已被，数据由旧内存复制到新内存
int double_data_volume(struct stu_score *pstu) {int * temp = (int*)malloc(2 * sizeof(int) * pstu->max_count);if (!temp)return 0;for (int i = 0; i < pstu->count; i++) {temp[i] = pstu->data[i];}free(pstu->data); // 释放旧内存pstu->data = temp; // 指向新内存temp = NULL;pstu->max_count *= 2;return 1;
}
// 1.  初始化数据结构,成功返回1，不成功返回0
int init_data(struct stu_score *stu) {stu->count = 0;   // (*stu).count = 0;stu->max_count = 5;stu->data = (int*)malloc(sizeof(stu->data[0]) * 5); if (stu->data == NULL)return 0;return 1;
}
// 2.  添加学生成绩,成功返回1，不成功返回0
int append_data(struct stu_score * pstu, int score) {if (pstu->count >= pstu->max_count) if (!double_data_volume(pstu))return 0;pstu->data[pstu->count] = score;pstu->count++;return 1;
}
// 3.  打印所有的学生成绩
void list_all_data(const struct stu_score * stu) {printf("学生个数：%d\n", stu->count);for (int i = 0; i < stu->count; i++) {printf("%d ", stu->data[i]);}printf("\n");
}
// 4.  修改第 i 个学生的成绩。pos 从 0 开始
int modify_data(struct stu_score * stu, int pos, int score){if (pos < 0 || pos >= stu->count)return 0;stu->data[pos] = score;return 1;}
// 5.  删除某个位置的学生成绩。
int remove_data(struct stu_score * stu, int pos) {if (pos < 0 || pos >= stu->count)return 0;for (int i = pos; i < stu->count -1; i++) {stu->data[i] = stu->data[i+1];}stu->count--;return 1;
}
// 6.  销毁数据结构.
int destroy_data(struct stu_score * pstu) {free(pstu->data);pstu->data = NULL;pstu->count = 0;pstu->max_count = 0;return 1;
}
// 7.  在 pos 之前的位置插入学生的成绩
int insert_data(struct stu_score * pstu, int pos, int score){if (pos < 0 || pos > pstu->count)return 0;if (pstu->count >= pstu->max_count) if (!double_data_volume(pstu))return 0;for (int i = pstu->count - 1; i >= pos; i--) {pstu->data[i+1] = pstu->data[i];}pstu->data[pos] = score;pstu->count++;return 1;
}int main(int argc, char * argv[]) {struct stu_score stu; // 定义一个顺序存储数据的变量int ret; // 此变量用来保存函数的返回值ret = init_data(&stu);printf("init_data: ret:%d\n", ret);for (int i = 10; i <= 50; i+= 10)append_data(&stu, i);list_all_data(&stu);  // 打印列表
// 	ret = modify_data(&stu, 2,99);//将第三个学生的成绩改成99
// 	printf("modify_data: ret:%d\n", ret);
// 	list_all_data(&stu);  // 打印列表
// 	ret = remove_data(&stu, 3);
// 	printf("remove_data: ret:%d\n", ret);
// 	list_all_data(&stu);  // 打印列表ret = insert_data(&stu, 1, 60);printf("insert_data: ret:%d\n", ret);list_all_data(&stu);  // 打印列表return 0;
}

栈

栈是一种先进后出的数据结构。犹如一个很细的玻璃杯装满的乒乓球。先装进去的一定是最后才能取出来。

栈的基本操作

• 初始化栈
• 清空栈
• 判断栈空
• 判断栈满
• 获取栈顶元素
• 获取栈元素个数
• 入栈
• 出栈

使用顺序存储结构来实现栈

struct stack {int data[100];int top;
}

数据结构和算法的网站：Data Structure Visualization

框架代码

#include <stdio.h>struct stack {int data[20];  // 用来保存数据int top; // 用来记录栈顶的位置
};
// 初始化栈
void stack_init(struct stack * pstk) { }
// 清空栈
void stack_clear(struct stack * pstk) { }
// 判断栈空, 栈为空返回 1， 否则返回0
int stack_is_empty(struct stack * pstk) { }
// 判断栈满 栈为满返回 1， 否则返回0
int stack_is_full(struct stack * pstk) { }
// 获取栈顶元素,成功返回1,数据放入pvalue指向的变量,失败返回0
int stack_top_value(struct stack * pstk, int * pvalue) { }
// 获取栈元素个数
int stack_get_value_count(struct stack *pstk) {}
// 入栈:成功返回1,失败返回0
int stack_push(struct stack *pstk, int value) {}
// 出栈:成功返回1,数据放入pvalue指向的变量
int stack_pop(struct stack * pstk, int * pvalue) { }int main(int argc, char * argv[]) {struct stack stk; // 定义一个栈return 0;
}

最终代码

#include <stdio.h>struct stack {int data[20];  // 用来保存数据int top; // 用来记录栈顶的位置
};
// 初始化栈
void stack_init(struct stack * pstk) {pstk->top = 0;
}
// 清空栈
void stack_clear(struct stack * pstk) {stack_init(pstk);
}
// 判断栈空, 栈为空返回 1， 否则返回0
int stack_is_empty(struct stack * pstk) {return pstk->top == 0;
}
// 判断栈满 栈为满返回 1， 否则返回0
int stack_is_full(struct stack * pstk) {return pstk->top == sizeof(pstk->data) / sizeof(pstk->data[0]);
}
// 获取栈顶元素,成功返回1,数据放入pvalue指向的变量,失败返回0
int stack_top_value(struct stack * pstk, int * pvalue) {if (pstk->top == 0)return 0;*pvalue = pstk->data[pstk->top-1];return 1;
}
// 获取栈元素个数
int stack_get_value_count(struct stack *pstk) {return pstk->top;
}
// 入栈:成功返回1,失败返回0
int stack_push(struct stack *pstk, int value) {if (stack_is_full(pstk))return 0;pstk->data[pstk->top] = value;pstk->top++;
}
// 出栈:成功返回1,数据放入pvalue指向的变量
int stack_pop(struct stack * pstk, int * pvalue) {if (stack_is_empty(pstk))return 0;pstk->top--;*pvalue = pstk->data[pstk->top];return 1;
}int main(int argc, char * argv[]) {struct stack stk; // 定义一个栈if (stk.top == 0) return 0;
}

按增长方向分：

• 增栈
• 减栈

按栈指针指向数据形式分：

• 满栈
• 空栈