C语言&嵌入式我的大学嵌入式 Linux C ARM

混子数据结构学习之第一章绪论笔记上

2021-11-07  本文已影响0人  那个混子

"磨棱角，褪优越，沉下心"
"不止于心动，更付诸于行动，执行力！“

引言

开始并行学习一下数据结构，基础太重要了，非科班，本科期间也没有学过这些，现在回过来学习。参考青岛大学的王卓老师的资料学习，简单记录一下笔记，方便以后查阅，后续全部学完了，会对笔记进行查缺补漏。

第一章绪论

数据结构的重要性：
程序 = 数据结构 +算法

定义：

数据结构是研究非数值计算的程序设计中计算机的操作对象及它们之间关系和操作的学科。

基本概念术语

举例


数据、数据元素、数据项三者之间的关系：数据>数据元素>数据项。
例：学生表>个人记录>学号、姓名……

数据两种层次结构

一、逻辑结构
（1）线性结构

有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继。例如：线性表、栈、队列、串。

（2）非线性结构

一个结点可能有多个直接前驱和直接后继。例如：树、图。
一对多，多对多的关系。

另外一种分类标准：
二、物理结构（存储结构）
（1）顺序存储结构

把数据元素存放在连续的存储单元里，数据元素之间的逻辑关系是通过数据元素的位置。(在前面的数据元素就存在前面；在后面的数据元素就存在后面)C语言用数组来实现顺序存储结构。

（2）链式存储结构

用一组任意的存储单元存储数据元素(可能连续也可能不连续)，数据元素之间的逻辑关系用指针来表示(用指针存放后继元素的存储地址)，C语言中用指针来实现链式存储结构。就是存储一个元素本身同时，还存储了下一个元素的地址。
举例：现在如银行、医院等地方，设置了排队系统，也就是每个人去了，先领一个号，等着叫号，叫到时去办理业务或看病。在等待的时候，你爱在哪在哪，可以坐着、站着或者走动，甚至出去逛一圈，只要及时回来就行。你关注的是前一个号有没有被叫到，叫到了，下一个就轮到了。

（3）索引存储结构

在存储节点信息的同时，还建立附加索引索引表中的每一项称为一个索引项，索引项的一般形式是：(关键字，地址）关键字是能唯一标识一个结点的那些数据项。
举例：手机通讯录中名字字母排序，点击对应人名即可呼叫对应的号码。

（4）散列存储结构
三、二者的关系

数据类型

抽象数据类型

具体形式：
ADT 抽象数据类型名{
    数据对象:<数据对象的定义>
    数据关系:<数据关系的定义>
    基本操作:<基本操作的定义>
}ADT 抽象数据类型名

其中：数据对象、数据关系的定义用伪代码描述；
基本操作的定义格式为：

基本操作名（参数表）
初始条件：<初始条件描述>
操作结果：<操作结果描述>

①参数表：赋值参数，只为操作提供输入值；引用参数，以&打头，除可提供输入值外，还将返回值操作结果。
②初始条件：描述操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。若初始条件为空，则省略之。
③操作结果：说明操作正常完成之后，数据结构的变化状况和应返回的结果。

举例：

ADT Circle{
    数据对象：D={r,x,y|r,x,y均为实数}
    数据关系：R={<r,x,y>|r是半径,<x,y>是圆心坐标}
    基本操作：
        Circle(&C,r,x,y)
            操作结果：构造一个圆。
        double Area(C)
            初始条件：圆已存在。
            操作结果：计算面积。
        double Circumference(C)
            初始条件：圆已存在。
            操作结果：计算周长。
        ……
}ADT Circle
小结：
借用课程中老师的PPT截图：

抽象数据类型的表示与实现

前面说的一个问题抽象为一个抽象数据类型后，仅是形式上的抽象定义，还没有达到问题解决的目的，要实现这个目标，就要把抽象的变成具体的，即抽象数据类型在计算机上实现，变为一个能用的具体的数据类型。

用C语言真正实现抽象数据类型的定义

例如：抽象数据类型“复数”的实现。
下面以计算复数加法、除法为例，我并没有把+-*/都搞出来，太多了，知道两个就可以，王老师课件对应的代码有问题，指针取地址。

#include "stdio.h"
/*结构体定义，对应数据对象、关系*/
typedef struct
{
 float real_part;  //实部系数
 float imaginary_part; //虚部系数
}Complex;  //定义复数抽象类

//下面函数就对应数据的基本操作
/* 构造复数*/
void assign (Complex *A,float real,float imaginary)
{
    A->real_part = real;
    A->imaginary_part = imaginary;
}
/* 复数加法*/
void add(Complex *C,Complex A,Complex B)
{
    C->real_part = A.real_part + B.real_part;
    C->imaginary_part = A.imaginary_part + B.imaginary_part;
}
/*复数除法*/
void divide(Complex *C,Complex A,Complex B)
{
    C->real_part = (A.real_part * B.real_part + A.imaginary_part * B.imaginary_part) / (B.real_part * B.real_part + B.imaginary_part * B.imaginary_part);//实部 
    C->imaginary_part = (A.imaginary_part * B.real_part - A.real_part * B.imaginary_part) / (B.real_part * B.real_part + B.imaginary_part * B.imaginary_part);//虚部 
}
/* 返回复数的虚部*/
float GetReal(Complex A)
{
    return A.real_part;
}
/* 返回复数的虚部*/
float GetImag(Complex A)
{
    return A.imaginary_part;
}
/*主函数*/
void main()
{
    Complex Z1,Z2,C1,C2; //定义局部变量

    assign(&Z1,8.0,6.0);//构造复数Z1
    assign(&Z2,4.0,3.0);//构造复数Z2
    add(&C1,Z1,Z2);   //Z1+Z2
    divide(&C2,Z1,Z2);//Z1/Z2
    printf("+ Result:\n%f\n%f\n",GetImag(C1),GetReal(C1));
    printf("÷Result:\n%f\n%f\n",GetImag(C2),GetReal(C2));
}

运行结果：

小结：

虽然说是绪论，但是基本概念比较多，主要还是为我们建立一种思维模式以及铺垫一下这些概念的认识。本节主要记录对应资料前4节的内容，主要强调的是数据结构基本概念的东西，绪论还有后半部分，介绍算法的，下次记录了。

参考资料：
青岛大学.王卓.数据结构与算法
《数据结构 C语言版》.严蔚敏

欢迎关注本人微信公众号：那个混子
记录自己学习的过程，分享乐趣、技术、想法、感悟、情感！
单片机类嵌入式交流学习可加企鹅群：120653336
上一篇下一篇

猜你喜欢

热点阅读