数据结构基础知识
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.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的方法
- 根据问题规模n写出表达式f(n)
- 如果有常数项,将其置为1 //当f(n)的表达式中只有常数项,例如f(n) = 8 ==> O(1)
- 只保留最高项,其他项舍去。
- 如果最高项系数不为1,则除以最高项系数。
f(n) = 3*n^4 + 2*n^3 + 6*n^7 +10;
==> O(n^7)
- 线性表
线性表是最基本、最简单、也是最常用的一种数据结构,可以存储逻辑关系为线性的数据。线性表(linear list)是数据结构的一种,一个线性表是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};
函数命名规则:
下划线法:create_empty_seqlist
小驼峰法:createEmptySeqList
大驼峰法:CreateEmptySeqList
数组的增删操作:
#include <stdio.h>/*
功能:向数组的第几个位置插数据
函数:void insetIntoA(int *p,int n, int post, int data);
参数:
int *p: 保存数组首地址
int n: 有效数据元素的个数
int post: 插入元素下标
int data: 数据
*/
void insertIntoA(int *p, int n, int post, int data) //insert插入 //p=a, n=8,post=4, data=100
{int i;//1.从最后一个元素到插入位置的元素向后移动一个单位for (i = n - 1; i >= post; i--) //i=7 , 7>=4; i=6, 6>=4; i=5, 5>=4; i=4, 4>=4; i=3 3>=4(不满足退出循环)
p[i + 1] = p[i]; //p[8]=p[7]; p[7]=[6]; p[6]=p[5]; p[5]=p[4]//2.插入新元素data到指定位置
p[post] = data; //p[4] = 100
}/* (2)遍历数组中的有效元素
功能:遍历数组中的有效元素
函数:void showA(int *p,int n);
参数:
int *p:保存数组收地址
int n:有效数据元素的个数
*/
void showA(int *p, int n)
{for (int i = 0; i < n; i++)printf("%d ", p[i]);printf("\n");
}/* (3)删除数组元素
功能:删除数组中指定元素
函数:void deleteIntoA(int *p,int n, int post);
参数:
int *p: 保存数组首地址
int n: 有效数据元素的个数
int post: 删除元素下标
*/
void deleteIntoA(int *p, int n, int post) //delet删除 //p=a, n=9, post=4
{int i;//从删除位置元素的后一个元素到最后一个元素向前移动一个单位for (i = post + 1; i < n; i++) //i = 5, i<9; i=6,6<9; i=7,i<9; i=8; i=9(出循环)
p[i - 1] = p[i]; //p[4]=p[5]; p[5]=p[6]; p[6]=p[7]; p[7]=p[8];
}int main()
{int a[100] = {1, 2, 3, 4, 5, 6, 7, 8};insertIntoA(a, 8, 4, 100);showA(a, 9);deleteIntoA(a, 9, 4);showA(a, 8);
}
通过添加全局变量last表示最后一个有效元素的下标:
#include <stdio.h>
int last = 7; //代表最后一个有效元素下标 last = 有效元素个数-1/*
功能:向数组的第几个位置插数据
函数:void insetIntoA(int *p,int post, int data);
参数:
int *p: 保存数组首地址
int post: 插入元素下标
int data: 数据
*/
void insertIntoA(int *p, int post, int data) //insert插入
{
int i;
//1.从最后一个元素到插入位置的元素向后移动一个单位
for (i = last; i >= post; i--)
p[i + 1] = p[i]; //2.插入新元素data到指定位置
p[post] = data; //p[4] = 100 //3. 让last加一,因为插入一个元素,有效元素多了一个
last++;
}/* (2)遍历数组中的有效元素
功能:遍历数组中的有效元素
函数:void showA(int *p);
参数:
int *p:保存数组收地址
*/
void showA(int *p)
{
for (int i = 0; i <= last; i++)
printf("%d ", p[i]);
printf("\n");
}/* (3)删除数组元素
功能:删除数组中指定元素
函数:void deleteIntoA(int *p, int post);
参数:
int *p: 保存数组首地址
int post: 删除元素下标
*/
void deleteIntoA(int *p, int post) //delet删除
{
int i;
//从删除位置元素的后一个元素到最后一个元素向前移动一个单位
for (i = post + 1; i <= last; i++)
p[i - 1] = p[i]; //让last减一,因为删除了一个元素有效元素少了一个
last--;
}int main()
{
int a[100] = {1, 2, 3, 4, 5, 6, 7, 8};
insertIntoA(a, 4, 100);
showA(a);
deleteIntoA(a, 4);
showA(a);
}
3.1.3 顺序表编程实现
封装结构体:
#define N 10
typedef struct seqlist //封装顺序表结构体类型
{
int data[N]; //用来存数据的数组
int last; //代表数组中最后一个有效元素的下标
} seqlist_t, *seqlist_p;
//seqlist_t A; // 等同于struct seqlist A
//seqlist_p p; //等同于 struct seqlist *p;
创建空顺序表:
#include <stdio.h>
#include <stdlib.h>
#define N 10
typedef struct seqlist //封装顺序表结构体类型
{int data[N]; //用来存数据的数组int last; //代表数组中最后一个有效元素的下标
} seqlist_t, *seqlist_p;// 创建一个空的顺序表
seqlist_p CreateEpSeqlist() //create创造 empty 空的 seqlist顺序表
{//动态申请一块顺序表结构体大小空间
seqlist_p p = (seqlist_p)malloc(sizeof(seqlist_t));if (NULL == p){perror("malloc lost"); //perror打印上一个函数报的错误信息return NULL; //错误情况让函数返回空指针}//对结构体初始化
p->last = -1;return p;
}//判断顺序表是否为满,满返回1,未满返回0
int IsFullSeqlist(seqlist_p p) //full满
{return p->last + 1 == N;
}//向顺序表的指定位置插入数据
int InsertIntoSeqlist(seqlist_p p, int post, int data)
{//容错判断:判满,对post做判断if (IsFullSeqlist(p) || post < 0 || post > p->last + 1){printf("InsertIntoSeqlist err\n");return -1; //错误返回}//让最后一个元素到插入位置的元素向后移动一个单位for (int i = p->last; i >= post; i--)
p->data[i + 1] = p->data[i];//插入数据
p->data[post] = data;//让last加一
p->last++;return 0;
}//遍历顺序表sequence顺序list表
void ShowSeqlist(seqlist_p p)
{
}int main(int argc, char const *argv[])
{
seqlist_p p = CreateEpSeqlist();return 0;
}