数据结构One——绪论

本喵是FW视频封面最终版

宝子，你不点个赞吗？不评个论吗？不收个藏吗？

最后的最后，关注我，关注我，关注我，你会看到更多有趣的博客哦！！！

喵喵喵，你对我真的很重要。

目录

前言

绪论

1.1数据结构的研究的内容

1.2数据结构的基本概念和术语

1.2.1 数据，数据元素，数据项和数据对象

1.2.2数据结构

逻辑结构

存储结构

 数据类型

算法和算法分析

算法的特性

评价算法优劣的基本标准

算法的时间复杂度

算法时间复杂度定义

 最好，最坏和平均时间复杂度

算法的空间复杂度

通讯录数据结构化（凑字数）

SeqList.c

SeqList.h

test.c(这个模块建议自己选择使用，建议先保证每个功能都能正常使用，再写菜单。菜单前面皆为测试）

总结

---

前言

宝子，你喵呜终于更新了，求求，求求，求求支持，拜托拜托！！！

从今天开始我们有开一个新坑，数据结构与算法，莫慌，C语言会回炉重造，喵喵不满意，看它不爽已经很久了，毁灭吧，开始改第四版《小猫猫大课堂》

额，哪这个专题叫什么呢？给个名字嘛！点赞最多的宝子决定它叫啥！

稳着点啊，别开车，会翻的！呜呜

注：这是第一版（书本），后期还会进行课程和实践的完善，上一个通讯录数据结构化吧！

---

绪论

早期的计算机主要用于数值计算，而现在的计算机主要用于非数值计算。

来来来，上图，更清晰

啊，图真的是太美了！爱了爱了

1.1数据结构的研究的内容

数据结构主要研究非数值计算。

举个栗子：

 宝子，你细品，啊就是这个道理，它也可以解决非数值的问题，赞！

1.2数据结构的基本概念和术语

概念和术语贯穿学习始终，我们先来几个概念和术语给出确定的含义

1.2.1 数据，数据元素，数据项和数据对象

数据：是客观事物的符号表示，是所有能输入计算机中并被计算机处理的符号的总称。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

数据项：是组成数据元素的，有独立含义的，不可分割的最小单位。

数据对象：是性质相同的数据元素的集合，是数据的子集。

1.2.2数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

数据结构包括逻辑结构和存储结构两个层次。

逻辑结构

• 集合结构：数据元素之间除了“属于同一集合”的关系外，别无其他关系。
• 线性结构：数据元素之间存在一对一的关系。
• 树结构：数据元素之间存在一对多的关系。
• 图结构或网状结构：数据元素之间存在多对多的关系。

上图

注：集合结构，树结构和图结构或网状结构都属于非线性结构。

线性结构包括线性表，栈和队列，字符串，数组等。（考研重点） 

高低给你整张图，意思意思

存储结构

顺序存储结构：是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系的，通常借助程序设计语言的数组类型来描述。（访问快，随机存取，连续空间，逻辑顺序与存储顺序一致）

上图

 链式存储结构：顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无须占用一整块存储空间。但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。

上图

---

 数据类型

数据类型：是高级程序语言的一个基本概念。定义在其上的操作为加，减，乘，除和取模等算数运算。

抽象数据类型：数据对象，数据对象上关系的集合以及数据对象的基本操作的集合。

---

算法和算法分析

算法：是为了解决某类问题而规定的一个有限长的操作序列。

算法的特性

(1)有穷性:一个算法必须总是在执行有穷步后结束，且每一 一步都必须在有穷时间内

(2)确定性：对于每种情况下所应执行的操作，在算法中都有确切的规定，不会产生二义性，算法的执行者或阅读者都能明确其含义及如何执行。
(3)可行性：算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现。

(4)输入：一个算法有0个或多个输人。当用函数描述算法时，输人往往是通过形参表示
的，在它们被调用时，从主调函数获得输人值。
(5)输出：一个算法在一 个或多个输出、它们是算法进行信息加工后得到的结果，无输出
的算法没有任何意义。当用函数描述算法时，输出多用返回值或引用类型的形参表示。

评价算法优劣的基本标准

(1).正确性。在合理的数据输入下，能够在有限的运行时间内得到正确的结果。

(2)可读性：一个好的算法，首先应便于人们理解和相互交流，其次才是机器可执行性。

可读性强的算法有助于人们对算法的理解，而难懂的算法容易隐藏错误，且难于调试和修改。

(3)健壮性。当输人的数据非法时，好的算法能适当地做出正确反应或进行相应处理、而

不会产生一些莫名其妙的输出结果。

(4)高效性。高效性包括时间和空间两个方面。时间高效是指算法设计合理，执行效率

高，可以用时间复杂度来度量;空间高效是指算法占用存储容量合理，可以用空间复杂度来度

量。时间复杂度和空间复杂度是衡量算法的两个主要指标。

算法的时间复杂度

问题规模：不考虑计算机的软硬件等环境因素，影响算法时间代价的最主要因素是问题规模。问题一规模是算法求解问题输人量的多少，是问题大小的本质表示，一般用整数n表示。

语句频度：一条语句的重复执行次数称作语句频度( Frequency Count)。

一个算法的执行时间大致上等于其所有语句执行时间的总和，而语句的执行时间则为该条语句的重复执行次数和执行-次所需时间的乘积。

算法时间复杂度定义

一般情况下，算法中基本语句重复执行的次数是问题规模m的某个函数(n),算法的时间量度记作:

Tn)= O（f(n))

它表示随着问题规模n的增大，算法执行时间的增长率和0)的增长率相同，称作算法的所近时间复杂度，简称时间复杂度(Tme Complexil)。

举几个栗子

  

好图

 最好，最坏和平均时间复杂度

称算法在最好情况下的时间复杂度为最好时间复杂度，是指算法计算量可能达到的最小值

称算法在最坏情况下的时间复杂度为最坏时间复杂度是指算法计算量可能达到的最大值

算法的平均时间复杂度是指算法在所有可能情况下，按照输人实例以等概率出现时，算法

计算量的加权平均值。

---

算法的空间复杂度

关于算法的存储空间需求，类似于算法的时间复杂度。我们采用渐近空间复杂度(SpeceCopisn)作方算注所需存储空间的量度，简朽空间复杂度，它也是问题规模m的函数，记作:

Sn)= 0(f(n))

一般情况下。一个程序在机器 上执行时，除了需要寄存本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的辅助存储空间。 其中，输人数据所占的具体存储量取决于问题本身，与算法无关，这样只需分析该算法在实现时所需要的辅助空间就可以了。若算法执行时所需要的辅助空间相对于输人数据量而言是个常数，则称这个算法在原地工作，辅助空间为0(1),本节中前面的示例都是如此。有的算法需要占用临时的工作单元数与问题规模n有关，如第8章介绍的归并排序算法就属于这种情况。

举个栗子：

---

练习题啊，下次一定，累了累了。喵呜~

---

用的这本书，仅供参考

---

通讯录数据结构化（凑字数）

SeqList.c

#include"SeqList.h"
void SLInit(SL* ps)
{ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);if (ps->a == NULL){perror("malloc fail");return;}ps->size = 0;ps->capacity = INIT_CAPACITY;
}
void SLDestroy(SL* ps)
{free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
}
void SLPushBack(SL* ps, SLDataType x)
{扩容//SLCheckCapacity(ps);ps->a[ps->size]=x;ps->size++;//ps->a[ps->size++] = x;SLErase(ps, ps->size, x);
}
void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; ++i){printf("%d", ps->a[i]);}printf("\n");
}void SLPopBack(SL* ps)
{/*if (ps->size == 0)return;ps->size--;*/SLErase(ps, ps->size - 1);
}
void SLPushFront(SL* ps, SLDataType x)
{/*assert(ps);SLCheckCapacity(ps);int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];--end;}ps->a[0] = x;ps->size++;*/SLInsert(ps, 0,x);
}
void SLPopFront(SL* ps)
{/*assert(ps->size>0);int begin = 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];++begin;}ps->size--;*/SLErase(ps, 0);}
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity * 2);if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}}
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);int end = ps->size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];--end;}ps->a[pos] = x;ps->size++;
}
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);int begin = pos + 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];++begin;}ps->size--;
}
int SLFind(SL* ps, SLDataType x) 
{assert(ps);for (int i = 0; i < ps->size; ++i){if (ps->a[i] == x){return i;}}return -1;
}

SeqList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDataType;
#define INIT_CAPACITY 4
//动态顺序表--按需申请
typedef struct SeqList
{int size;//有效数据个数int capacity;//空间容量SLDataType* a;
}SL;
//增删查改
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);
void SLCheckCapacity(SL* ps);void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, SLDataType x);

test.c(这个模块建议自己选择使用，建议先保证每个功能都能正常使用，再写菜单。菜单前面皆为测试）

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
SL s;
void TestSeqList1()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPrint(&s);SLDestroy(&s);
}
void TestSeqList2()
{SL s;SLInit(&s);SLPushFront(&s, 1);SLPushFront(&s, 2);SLPushFront(&s, 3);SLPushFront(&s, 4);SLPrint(&s);
}
void menu()
{printf("********************************\n");printf("***1.尾插数据      2.尾删数据*****\n");printf("***7.打印数据      -1退出*********\n");printf("********************************\n");
}
int main()
{int option = 0;while (option != -1){menu();scanf("%d", &option);if (option == 1){printf("请·依次输入要尾插的数据，以-1结束");int x = 0;while (x != -1){scanf("%d", &x);SLPushBack(&s, x);}}else if (option == 7){SLPrint(&s);}}return 0;
}

---

总结

时间紧促，内容繁多，这篇文章还有很多方法，小喵还没有详述，别慌，这坑，得埋。

宝子，多看书，多刷题，少吸电子鸦片，早睡觉，你对我真的很重要。

---

宝子，你不点个赞吗？不评个论吗？不收个藏吗？

最后的最后，关注我，关注我，关注我，你会看到更多有趣的博客哦！！！

喵喵喵，你对我真的很重要。