数据结构(精讲)----应用篇
注意:作者会出两个版本的数据结构的介绍;第一个版本介绍的数据结构会偏向理论性,第二个版本,也就是从这篇文章开始,这个版本会偏向应用性;会带领大家了解数据结构,以及为什么学习数据结构,如何运用数据结构的相关内容,去优化自己的代码。
如果感兴趣的同学们可以关注作者,方便查看后续内容的更新。
为什么学习数据结构
- C语言如何写程序
学数据结构是为了简洁、高效的写程序。
- 如果遇到一个实际问题,需要写代码实现相应功能,需要解决两个问题:
(1)如何表达数据之间的逻辑关系以及怎么存储到计算机中?
数据结构:数据的逻辑结构以及存储操作。
数据:不再是单纯的数字,而是类似于集合的概念。
结构:数据之间的关系。
(2) 采用什么方法去解决?
采用算法去解决
数据结构+算法=程序
问题->数据结构+算法=程序->解决问题
数据结构基础知识
什么是数据结构
数据结构就是数据的逻辑结构以及存储操作(类似数据的运算)
数据结构就是为了教一件事情:如何有效的存储数据
数据
数据:不再是单纯的数字,而是类似集合的概念
数据元素:是数据的基本单位,又若干个数据项组成
数据项:数据的最小单位,描述数据元素的有用信息
数据元素又叫节点
例如:
计算机处理的对象(数据)已不再是单纯的数值:
图书管理中的数据,如下表所列:
数据:图书
数据元素:每一本书
数据项:编号、书名、作者、出版社等
逻辑结构
数据元素并不是孤立存在的,它们之间存在着某种关系(或联系、结构)元素和元素之间的关系
线性关系:
线性结构: 一对一 线性表:顺序表、链表、栈、队列
层次关系:
树形结构:一对多 树:二叉树
网状关系:
图状结构: 多对多 图
例题:
田径比赛的时间安排问题
存储结构
顺序存储:
特点:内存连续、随机存取、每个元素占用较少
实现:数组
链式存储:
通过指针存储
特点:内存不连续、通过指针实现
链表实现:
结构体:
#include <stdio.h>
struct node
{
int data; // 数据域:存放节点中要保存的数据
struct node *next; // 指针域:保存下一个节点的地址,也就是指向了下一个节点(类型为自身结构体指针)
};
int main(int argc, char const *argv[])
{
// 定义三个节点
struct node A = {1, NULL}; // 定义结构体变量同时给每个成员赋值
struct node B = {2, NULL};
struct node C = {3, NULL};
// 连接三个节点
A.next = &B; // 连接A和B界定啊,通过A节点中的指针域保存B的地址
B.next = &C;
// 用结构体变量访问就是用 . 的形式访问
// 通过指针访问就是用 -> 的形式进行访问
printf("A = %d\n", A.data); // 打印A中的数据
printf("%p %p\n", A.next, &B); // 打印A的指针域和B的地址
printf("B = %d\n", (A.next)->data); // 通过A打印B中的数据
printf("C = %d\n", ((A.next)->next)->data); // 通过A打印C中的数据
return 0;
}
索引存储结构:
在存储数据的同时,建立一个附加的索引表。
也就是索引存储结构=索引表+存数据的文件
可以提高查找速度,特点检索速度快,但是占用内存多,删除数据文件要及时更改索引表。
散列存储:
数据存储按照和关键码之间的关系进行存取。关系由自己决定,比如关键码是key, 存储位置也就是关系是key+1。获取关键数据,通过元素的关键码方法的返回值来获取。
存的时候按关系存
取的时候按关系取
操作:
增删改查
算法基础知识
什么是算法
算法就是解决问题的思想方法,数据结构是算法的基础
数据结构+算法=程序
算法的设计
算法的设计:取决于数据结构的逻辑结构
算法的实现:依赖于数据的存储结构
算法的特性
- 有穷性:步骤有限
- 确定性:每一个步骤都有明确的含义、无二义性
- 可行性:在规定时间内可以完成
- 输入
- 输出
评价算法的好坏
- 正确性
- 易读性
- 健壮性:容错处理
- 高效性:执行效率,通过重复执行语句的次数来判断,也就是时间复杂度(时间处理函数)来判断。
时间复杂度
语句频度:用时间规模函数表达
时间规模函数: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+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个具有相同特性的数据元素的有限序列。
包含:顺序表(数组)、链表(单项链表、单项循环链表、双向链表、双向循环链表)、栈(顺序栈、链式栈)、队列(循环队列、链式队列)
逻辑结构:线性结构
存储结构:顺序存储(数组)或链式存储(通过指针)
特点:一对一、每个节点最多有一个前驱和一个后继,首节点没有前驱、尾节点无后继
顺序表
顺序表存储数据的具体实现方案是:将数据全部存储到一整块内存空间中,数据元素之间按照次序挨个存放。
举个简单的例子,将 {1,2,3,4,5} 这些数据使用顺序表存储,数据最终的存储状态如下图所示:
顺序表的特性:
逻辑结构:线性结构
存储结构:顺序存储结构
特点:内存连续
操作:增删改查
操作数组:
例题:
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--)
p[i + 1] = p[i];
//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++)
p[i - 1] = p[i];
}
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);
}
顺序表编程实现
封装结构体:
#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 list; // 最大元素的下标
int data[N];
} seqlist_t, *seqlist_p;
seqlist_p CreateEpSeqlist() // Create 创造空的顺序表
{
// 动态申请一个结构体大小空间
seqlist_p p = (seqlist_p)malloc(sizeof(seqlist_t));
if (NULL == p)
{
perror("malloc lost"); // perror:打印上一个函数的错误信息
return NULL; // 开辟失败返回空
}
// 对结构体初始化
p->list = -1;
return p;
}
// 用于判断顺序表是否已满
int IsFullSeqlist(seqlist_p p)
{
return p->list + 1 == N;
}
// 向顺序表中的指定位置插入数据
int InsertIntoSeqlist(seqlist_p p, int post, int data)
{
if (IsFullSeqlist(p) || post < 0 || post > p->list + 1)
{
printf("IsFullSeqlist err");
return -1; // 有错误返回-1;
}
for (int i = p->list; i >= post; i--)
{
p->data[i + 1] = p->data[i];
}
p->data[post] = data;
p->list++;
return 0;
}
// 判断顺序表是否为空,为空返回1,不为空返回0
int isEpSeqlist(seqlist_p p)
{
return p->list == -1;
}
// 删除指定位置元素
int DeleteIntoSeqlist(seqlist_p p, int post)
{
if (isEpSeqlist(p) || post < 0 || post >= p->list + 1)
{
printf("error!\n");
return -1;
}
for (int i = post + 1; i <= p->list; i++)
{
p->data[i - 1] = p->data[i];
}
p->list--;
return 0;
}
// 遍历打印结构体数组内容
int show(seqlist_p p)
{
if (isEpSeqlist(p))
{
printf("error!\n");
return -1;
}
for (int i = 0; i <= p->list; i++)
{
printf("%d ", p->data[i]);
}
putchar('\n');
return 0;
}
// 修改指定位置元素
int modify(seqlist_p p, int post, int data)
{
if (isEpSeqlist(p) || post < 0 || post >= p->list + 1)
{
printf("error!\n");
return -1;
}
p->data[post] = data;
printf("修改完成\n");
return 0;
}
// 查找指定数据出现的位置,返回下标,未找到返回-1;
int seek(seqlist_p p, int data)
{
for (int i = 0; i <= p->list; i++)
{
if (p->data[i] == data)
{
return i;
}
}
return -1;
}
void clearSeqlist(seqlist_p p){
p->list = -1;
}
int main(int argc, char const *argv[])
{
seqlist_p p = CreateEpSeqlist();
InsertIntoSeqlist(p, 0, 10);
InsertIntoSeqlist(p, 1, 20);
InsertIntoSeqlist(p, 2, 30);
show(p);
DeleteIntoSeqlist(p, 1);
show(p);
modify(p, 1, 99);
show(p);
printf("99:%d\n",seek(p,99));
return 0;
}
分文件编程:
#include <stdio.h>
#include "head.h"
int main(int argc, char const *argv[])
{
seqlist_p p = CreateEpSeqlist();
InsertIntoSeqlist(p, 0, 10);
InsertIntoSeqlist(p, 1, 20);
InsertIntoSeqlist(p, 2, 30);
show(p);
DeleteIntoSeqlist(p, 1);
show(p);
modify(p, 1, 99);
show(p);
printf("99:%d\n",seek(p,99));
return 0;
}
#include "head.h"
#include <stdio.h>
#include <stdlib.h>
seqlist_p CreateEpSeqlist() // Create 创造空的顺序表
{
// 动态申请一个结构体大小空间
seqlist_p p = (seqlist_p)malloc(sizeof(seqlist_t));
if (NULL == p)
{
perror("malloc lost"); // perror:打印上一个函数的错误信息
return NULL; // 开辟失败返回空
}
// 对结构体初始化
p->list = -1;
return p;
}
// 用于判断顺序表是否已满
int IsFullSeqlist(seqlist_p p)
{
return p->list + 1 == N;
}
// 向顺序表中的指定位置插入数据
int InsertIntoSeqlist(seqlist_p p, int post, int data)
{
if (IsFullSeqlist(p) || post < 0 || post > p->list + 1)
{
printf("IsFullSeqlist err");
return -1; // 有错误返回-1;
}
for (int i = p->list; i >= post; i--)
{
p->data[i + 1] = p->data[i];
}
p->data[post] = data;
p->list++;
return 0;
}
// 判断顺序表是否为空,为空返回1,不为空返回0
int isEpSeqlist(seqlist_p p)
{
return p->list == -1;
}
// 删除指定位置元素
int DeleteIntoSeqlist(seqlist_p p, int post)
{
if (isEpSeqlist(p) || post < 0 || post >= p->list + 1)
{
printf("error!\n");
return -1;
}
for (int i = post + 1; i <= p->list; i++)
{
p->data[i - 1] = p->data[i];
}
p->list--;
return 0;
}
// 遍历打印结构体数组内容
int show(seqlist_p p)
{
if (isEpSeqlist(p))
{
printf("error!\n");
return -1;
}
for (int i = 0; i <= p->list; i++)
{
printf("%d ", p->data[i]);
}
putchar('\n');
return 0;
}
// 修改指定位置元素
int modify(seqlist_p p, int post, int data)
{
if (isEpSeqlist(p) || post < 0 || post >= p->list + 1)
{
printf("error!\n");
return -1;
}
p->data[post] = data;
printf("修改完成\n");
return 0;
}
// 查找指定数据出现的位置,返回下标,未找到返回-1;
int seek(seqlist_p p, int data)
{
for (int i = 0; i <= p->list; i++)
{
if (p->data[i] == data)
{
return i;
}
}
return -1;
}
void clearSeqlist(seqlist_p p){
p->list = -1;
}
#ifndef __HEAD_H__
#define __HEAD_H__
#define N 10
typedef struct seqlist
{
int list; // 最大元素的下标
int data[N];
} seqlist_t, *seqlist_p;
seqlist_p CreateEpSeqlist();
int IsFullSeqlist(seqlist_p p);
int InsertIntoSeqlist(seqlist_p p, int post, int data);
int isEpSeqlist(seqlist_p p);
int DeleteIntoSeqlist(seqlist_p p, int post);
int show(seqlist_p p);
int modify(seqlist_p p, int post, int data);
int seek(seqlist_p p, int data);
void clearSeqlist(seqlist_p p);
#endif
CC=gcc
CLFAGS=-c -g -Wall
OBJS:main.o function.o
seq:$(OBJS)
$(CC) $^ -o $@
%.o:%.c
$(CC) $(CLFAGS) $< -o $@
.PHONY:clean
clean:
$(RM) *.o
参考代码:
main.c
#include <stdio.h>
#include <stdlib.h>
#include "seqlist.h"
int main(int argc, char const *argv[])
{
seqlist_p p = CreateEpSeqlist();
InsertIntoSeqlist(p, 0, 10);
InsertIntoSeqlist(p, 1, 20);
InsertIntoSeqlist(p, 2, 30);
ShowSeqlist(p);
DeleteIntoSeqlist(p, 1);
ShowSeqlist(p);
ChangePostSeqList(p, 0, 99);
ShowSeqlist(p);
printf("search 99:%d\n", SearchDataSeqList(p, 99));
return 0;
}
seqlist.c
#include <stdio.h>
#include <stdlib.h>
#include "seqlist.h"
// 创建一个空的顺序表
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)
{
for (int i = 0; i <= p->last; i++)
printf("%d ", p->data[i]);
printf("\n");
}
//判断顺序表是否为空,为空返回1,不为空返回0
int IsEpSeqlist(seqlist_p p)
{
return p->last == -1;
}
//删除顺序表中指定位置的数据,post为删除位置
int DeleteIntoSeqlist(seqlist_p p, int post)
{
//容错判断:判空,对post判断
if (IsEpSeqlist(p) || post < 0 || post > p->last)
{
printf("DeleteIntoSeqlist err\n");
return -1;
}
//从删除位置元素的后一个元素到最后一个元素向前移动一个单位
for (int i = post + 1; i <= p->last; i++)
p->data[i - 1] = p->data[i];
//让last减一,因为删除了一个元素有效元素少了一个
p->last--;
return 0;
}
// 修改指定位置上数据
int ChangePostSeqList(seqlist_p p, int post, int data)
{
//容错判断:判空,对post判断
if (IsEpSeqlist(p) || post < 0 || post > p->last)
{
printf("ChangePostSeqList err\n");
return -1;
}
//修改指定位置数据
p->data[post] = data;
return 0;
}
// 查找指定数据出现的位置,返回下标,未找到返回-1
int SearchDataSeqList(seqlist_p p, int data)
{
for (int i = 0; i <= p->last; i++)
{
if (p->data[i] == data)
return i;
}
return -1;
}
// 清空顺序表(清空:访问不到,但是内存中还有。销毁:内存清空)
void ClearSeqList(seqlist_p p)
{
p->last = -1;
}
seqlist.h
#ifndef __SEQLIST_H__
#define __SEQLIST_H__
#define N 10
typedef struct seqlist //封装顺序表结构体类型
{
int data[N]; //用来存数据的数组
int last; //代表数组中最后一个有效元素的下标
} seqlist_t, *seqlist_p;
// 创建一个空的顺序表
seqlist_p CreateEpSeqlist(); //create创造 empty 空的 seqlist顺序表
//判断顺序表是否为满,满返回1,未满返回0
int IsFullSeqlist(seqlist_p p); //full满
//向顺序表的指定位置插入数据
int InsertIntoSeqlist(seqlist_p p, int post, int data);
//遍历顺序表sequence顺序list表
void ShowSeqlist(seqlist_p p);
//判断顺序表是否为空,为空返回1,不为空返回0
int IsEpSeqlist(seqlist_p p);
//删除顺序表中指定位置的数据,post为删除位置
int DeleteIntoSeqlist(seqlist_p p, int post);
// 修改指定位置上数据
int ChangePostSeqList(seqlist_p p, int post, int data);
// 查找指定数据出现的位置,返回下标,未找到返回-1
int SearchDataSeqList(seqlist_p p, int data);
// 清空顺序表(清空:访问不到,但是内存中还有。销毁:内存清空)
void ClearSeqList(seqlist_p p);
#endif
makefile
CC=gcc
GFLAGS=-c -g -Wall
OBJS=seqlist.o main.o
seqlist:$(OBJS)
$(CC) $^ -o $@
%.o:%.c
$(CC) $(GFLAGS) $< -o $@
.PHONY:clean
clean:
$(RM) seqlist *.o
顺序表特点:
- 顺序表内存空间连续
- 顺序表长度固定
- 插入和删除操作效率低,修改和查找效率高
原文地址:https://blog.csdn.net/Mumyi_/article/details/145267985
免责声明:本站文章内容转载自网络资源,如侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!