阅读量:0
今天开始学习数据结构的相关知识，大概分为了解数据结构、算法；学习线性表：顺序表、链表、栈、队列的相关知识和树：二叉树、遍历、创建，查询方法、排序方式等。
目录
一、数据结构
数据的逻辑结构、存储结构及操作（数据运算）
数据
数据：不再是单一的数值，而是类似于集合的概念
数据元素：是数据的基本单位，由若干个数据项组成
数据项：是数据的最小单位，描述数据元素信息
节点：就是数据元素
逻辑结构
逻辑结构：元素与元素之间的关系
1.线性结构
线性关系 -------> 线性结构 -------> 一对一 -------> 线性表：顺序表、链表、栈、队列
2.树形结构
层次关系 -------> 树形结构 -------> 一对多 -------> 树
3.图状结构
网状关系 -------> 图状结构 -------> 多对多 -------> 图
存储结构
存储结构：数据的逻辑结构在计算机中的具体实现
1.顺序存储结构
数组：在内存当中一段连续的内存空间中保存数据(如c语言中的一维数组)
2.链式存储结构
特点：数据在内存中是不连续的，通过指针进行连接
链表结构体：
struct node_t
{
int data; //数据域
struct node_t *next; //指针域， 指向自身结构体类型的指针
}；
3.索引存储结构
提高查找速度
索引表 + 数据文件
姓氏 + 地址 名字 + 电话号码
4.散列存储
数据在存储的时候与关键码之间存在某种对应关系
按照对应关系存取
操作（数据的运算）
增、删、改、查
二、算法
解决问题的思想方法
算法与程序
程序：用计算机语言对算法的具体实现
算法与数据结构
算法 + 数据结构 = 程序
算法的设计：取决于选定的逻辑结构
算法的实现：依赖于采用的存储结构（顺序存储、链式存储）
算法的特性
1.有穷性 //算法的执行步骤是有限的
2.确定性 //每一个步骤都有明确含义，无二义性
3.可行性 //能够在有限的时间内完成
4.输入5.输出
判断算法好坏的标准
正确性 //保证算法可以正确的实现想要的功能
易读性 //容易被解读
健壮性 //要有容错处理
高效性 //可执行语句重复的次数（时间复杂度）
低存储性 //占用空间越少越好
时间复杂度
算法的可重复执行语句执行的次数
通常时间复杂度用一个问题规模函数来表达
T(n) = O(f(n))
T(n) //问题规模的时间函数
n //问题规模，输入量的大小
O //时间数量级
f(n) //算法的可执行语句重复执行的次数 用问题规模n的某个函数f(n)来表达
计算大O的方法
(1)根据问题规模n写出表达式 f(n)
(2)只保留最高项，其它项舍去
(3)如果最高项系数不为1，除以最高项系数
(4)如果有常数项，将其置为1 //当f(n)的表达式中只有常数项的时候时有意义的
例如：如果f(n)=8 则O(f(n))----->O(1)
如果f(n) = 3*n^5 + 2*n^3 + 6*n^6 + 10 则O(f(n))----->O(n^6)
空间复杂度
算法占用的空间大小。一般将算法的辅助空间作为衡量空间复杂度的标准。
算法占用的存储空间包括
1.输入输出数据所占空间
2.算法本身所占空间
3.额外需要的辅助空间
三、线性表
顺序表、单向链表、单向循环链表、顺序栈、链式栈、循环队列、链式队列、双向链表、双向循环链表
逻辑结构：线性结构
存储结构：顺序、链式
特点：一对一、每一个节点最多有一个前驱和一个后继，首节点无前驱，尾节点无后继
顺序表
特点
内存连续（数组）
1.逻辑结构：线性结构
2.存储结构：顺序存储
3.操作：增删改查
函数名命名规则
下滑线法：create_empty_seqlist
小驼峰法：createEmptySeqList
大驼峰法：CreateEmptySeqList
顺序表的相关操作案例
头文件seqlist.h:
#ifndef _SEQLIST_H__ #define _SEQLIST_H__ #include <stdio.h> #include <stdlib.h> #define N 5 typedef struct seq { int data[N]; int last; } seqlist_t; // 1.创建一个空的顺序表 seqlist_t *CreateEpSeqlist(); // 返回的是申请空间的首地址 // 2.向顺序表的指定位置插入数据 int InsertIntoSeqlist(seqlist_t *p, int post, int data); // post第几个位置，data插入的数据 // 3.遍历顺序表sequence 顺序 list 表 void ShowSeqlist(seqlist_t *p); // 4.判断顺序表是否为满,满返回１ 未满返回０ int IsFullSeqlist(seqlist_t *p); // 5.判断顺序表是否为空 int IsEpSeqlist(seqlist_t *p); // 6.删除顺序表中指定位置的数据post删除位置 int DeletePostSeqlist(seqlist_t *p, int post); // 7.清空顺序表 void ClearSeqList(seqlist_t *p); // 8.修改指定位置的数据 int ChangePostSeqList(seqlist_t *p, int post, int data); // post被修改的位置，data修改成的数据 // 9.查找指定数据出现的位置 int SearchDataSeqList(seqlist_t *p, int data); // data代表被查找的数据 #endif 顺序表函数seqlist.c：
#include "seqlist.h" // 1.创建一个空的顺序表 seqlist_t *CreateEpSeqlist() // 返回的是申请空间的首地址 { // 1.动态申请一个结构体大小的空间 seqlist_t *p = (seqlist_t *)malloc(sizeof(seqlist_t)); if (p == NULL) { perror("CreateEpSeqlist函数出错"); return NULL; } // 2.对last初始化 p->last = -1; // 表示当前数组为空，有效元素个数为0 return p; } // 2.向顺序表的指定位置插入数据 int InsertIntoSeqlist(seqlist_t *p, int post, int data) // post第几个位置，data插入的数据 { // 0.容错判断 if (post > (p->last + 1) || post < 0 || IsFullSeqlist(p) == 1) { perror("InsertIntoSeqlist函数出错"); return -1; } // 1.将last--->post位置整体向后移动一个单位 for (int i = p->last; i >= post; i--) { p->data[i + 1] = p->data[i]; } // 2.将数据插入顺序表 p->data[post] = data; // 3.最后一个有效元素下标++ p->last++; return 0; } // 3.遍历顺序表sequence 顺序 list 表 void ShowSeqlist(seqlist_t *p) { for (int i = 0; i <= p->last; i++) { printf("%d ", p->data[i]); } printf("\n"); } // 4.判断顺序表是否为满,满返回１ 未满返回０ int IsFullSeqlist(seqlist_t *p) { return p->last == N - 1; } // 5.判断顺序表是否为空 int IsEpSeqlist(seqlist_t *p) { return p->last == -1; } // 6.删除顺序表中指定位置的数据post删除位置 int DeletePostSeqlist(seqlist_t *p, int post) { // 0.容错判断 if (post >= p->last + 1 || post < 0 || IsEpSeqlist(p)) { perror("DeletePostSeqlist函数出错"); return -1; } // 1.将post+1--->last位置整体向前移动一个单位 for (int i = post + 1; i <= p->last; i++) { p->data[i - 1] = p->data[i]; } // 2.最后一个有效元素下标-- p->last--; return 0; } // 7.清空顺序表 void ClearSeqList(seqlist_t *p) { p->last = -1; } // 8.修改指定位置的数据 int ChangePostSeqList(seqlist_t *p, int post, int data) // post被修改的位置，data修改成的数据 { if (post >= (p->last + 1) || post < 0 || IsEpSeqlist(p)) { perror("ChangePostSeqList函数出错"); return -1; } p->data[post] = data; return 0; } // 9.查找指定数据出现的位置 int SearchDataSeqList(seqlist_t *p, int data) // data代表被查找的数据 { int n = -1; // 初始化为-1，表示未找到该数据 for (int i = 0; i <= p->last; i++) { if (data == p->data[i]) { n = i; // 找到数据，记录下标 printf("该数据的下标为：%d\n", n); break; // 找到即可跳出循环 } } if (n == -1) { printf("数组没有该数据\n"); } return 0; }主函数：main.c：
#include "seqlist.h" int main() { seqlist_t *s = CreateEpSeqlist(); InsertIntoSeqlist(s, 0, 1); InsertIntoSeqlist(s, 1, 2); InsertIntoSeqlist(s, 2, 3); InsertIntoSeqlist(s, 3, 4); printf("原始数组为：\n"); ShowSeqlist(s); int post; int data; printf("请输入你要插入的位置和数据\n"); scanf("%d %d", &post, &data); InsertIntoSeqlist(s, post, data); printf("插入以后的数组为：\n"); ShowSeqlist(s); printf("请输入你要删除的位置\n"); scanf("%d", &post); DeletePostSeqlist(s, post); printf("删除以后的数组为：\n"); ShowSeqlist(s); printf("请输入你要修改的位置和数据\n"); scanf("%d %d", &post, &data); ChangePostSeqList(s, post, data); printf("修改以后的数组为：\n"); ShowSeqlist(s); printf("请输入你要查找的数据\n"); scanf("%d", &post); SearchDataSeqList(s, post); printf("清空数据表\n"); ClearSeqList(s); printf("清空以后的数据表为：\n"); ShowSeqlist(s); printf("释放*s的空间\n"); free(s); return 0; }makefile:
CC=gcc CFLAGS=-c -g -Wall OBJS=main.o seqlist.o seqlist:$(OBJS) $(CC) $^ -o $@ %.o:%.c $(CC) $(CFLAGS) $< -o $@ .PHONY:clean clean: $(RM) *.o seqlist