<初识数据结构+算法实现>数据结构(C语言版)

简介: <初识数据结构+算法实现>数据结构(C语言版)

前言:

●本篇博文基于《数据结构》(C语言版)严蔚敏教授、吴伟民教授、李冬梅教授编著的教材知识及框架主线,以及参考借阅其他相关资料,结合作者的学习所记录的笔记分享。

●由于作者水平有限,文章难免存在谬误之处,敬请读者斧正,俚语成篇,恳望指教

让我们先从一个著名的公式开始:

程序=算法+数据结构

这个公式由图灵奖获得者尼古拉斯·沃斯(Niklaus Wirth)(瑞士计算机科学家)所提出。

1.什么是数据结构?

数据结构(Data Structure)是相互之间存在一种或多种特定关系的数据元素的集合。

◆解释:数据结构是带“结构”的数据元素的集合,“结构”就是指数据元素之间存在的关系。

2.为什么要学数据结构?

★编程基础

★计算机及相关专业考研考博课程

★计算机等级考试课程

★程序员考试课程

3. 数据结构的研究内容、应用及方向:

数据结构的研究内容为: 研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作。

image.gif编辑

image.gif编辑image.gif编辑

4.基本概念和术语 :

▶数据(data)—所有能输入到计算机中去的描述客观事物的符号

          ◆ 数值性数据

          ◆非数值性数据(多媒体信息处理)

▶数据元素(data element)—数据的基本单位,也称结点(node)或记录(record)

▶数据项(data item)—有独立含义的数据最小单位,也称域(field)

三者之间的关系:数据 > 数据元素   >  数据项 

例:学生表 >  个人记录 >  学号、姓名……

▶数据对象(Data Object):相同特性数据元素的集合,是数据的一个子集

5. 数据结构的两个层次:

逻辑结构--- 数据元素间抽象化的相互关系,与数据的存储无关,独立于计算机,它是从具体问题抽象出来的数学模型。

存储结构(物理结构)---- 数据元素及其关系在计算机存储器中的存储方式。

★逻辑结构★

▲划分方法一

(1)线性结构---- 有且仅有一个开始和一个终端结点,并且所有结点都最多只有一个直接前趋和一个后继。 例如:线性表、栈、队列、串

(2)非线性结构---- 一个结点可能有多个直接前趋和直接后继。 例如:树、图

▲划分方法二

集合——数据元素间除“同属于一个集合”外,无其它关系image.gif编辑

线性结构——一个对一个,如线性表、栈、队列

image.gif编辑

树形结构——一个对多个,如树

image.gif编辑

图形结构——多个对多个,如图

image.gif编辑

★存储结构★:

◆顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系

◆链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系

image.gif编辑

image.gif编辑  

image.gif编辑

6.数据类型:

6.1定义:在一种程序设计语言中,变量所具有的数据种类

         ♦FORTRAN语言:整型、实型、和复数型

         ♦C语言:

                 ✔基本数据类型: char  int  float  double  void

                 ✔构造数据类型:数组、结构体、共用体、文件

数据类型是一组性质相同的值的集合, 以及定义于这个集合上的一组运算的总称

6.2抽象数据类型 (ADTs: Abstract  Data Types)

            ☛更高层次的数据抽象

            ☛由用户定义,用以表示应用问题的数据模型

            ☛由基本的数据类型组成, 并包括一组相关的操作

image.gif编辑

image.gif编辑

image.gif编辑

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

抽象数据类型可以通过固有的数据类型(如整型、实型、字符型等)来表示和实现。它有些类似C语言中的结构(struct)类型,但增加了相关的操作 教材中用的是类C语言(介于伪码和C语言之间)作为描述工具

(1) 预定义常量及类型

★函数结果状态代码

#define OK 1

#define ERROR 0

#define OVERFLOW -2

★Status是函数返回值类型,其值是函数结果状态代码。

typedef  int  Status;

(2)数据元素被约定为ElemType 类型,用户需要根据具体情况,自行定义该数据类型。

(3)算法描述为以下的函数形式:            

函数类型 函数名(函数参数表)            

{                

                语句序列;        

}

(4)内存的动态分配与释放

(5)赋值语句 (6)选择语句 (7)循环语句

(8)使用的结束语句形式有:

函数结束语句  return

循环结束语句  break;

异常结束语句  exit(异常代码);

(9)输入输出语句形式有: 输入语句

(10)扩展函数有: 求最大值  max 求最小值  min

7.算法和算法分析

7.1算法定义:一个有穷的指令集,这些指令为解决某一特定任务规定了一个运算序列

7.2算法的描述:  

☛自然语言  

☛流程图  

☛程序设计语言  

☛伪代码

7.3算法的特性:

       ◆输入  有0个或多个输入  

       ◆输出  有一个或多个输出(处理结果)  

       ◆确定性  每步定义都是确切、无歧义的  

       ◆有穷性  算法应在执行有穷步后结束  

       ◆有效性  每一条运算应足够基本

7.3算法的评价

       ✔正确性

       ✔可读性

       ✔健壮性

       ✔高效性(时间代价和空间代价)

7.4算法的效率的度量

▶算法效率:用依据该算法编制的程序在计算机上执行所消耗的时间来度量

              ★事后统计

              ★事前分析估计

  ♜事后统计:利用计算机内的计时功能,不同算法的程序可以用一组或多组相同的统计数据区分

缺点:

            ♦必须先运行依据算法编制的程序

            ♦所得时间统计量依赖于硬件、软件等环境因素,掩盖算法本身的优劣  

  ♜事前分析估计: 一个高级语言程序在计算机上运行所消耗的时间取决于:      

          ♦依据的算法选用何种策略      

          ♦问题的规模      

          ♦程序语言      

         ♦编译程序产生机器代码质量      

         ♦机器执行指令速度    

同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行,效率均不同,———使用绝对时间单位衡量算法效率不合适  

8.时间复杂度和空间复杂度:

8.1时间复杂度:image.gif编辑

题例1:image.gif编辑

n * n阶矩阵加法:
for( i = 0; i < n; i++)
  for( j = 0; j < n; j++)
    c[i][j] = a[i][j] + b[i][j];
image.gif

题例2:

image.gif编辑 题例3:

image.gif编辑

void exam ( float x[ ][ ], int m, int n ) {
     float sum [ ];
     for ( int i = 0; i < m; i++ ) { 
         sum[i] = 0.0;                      
         for ( int j = 0; j < n; j++ ) 
      sum[i] += x[i][j];  
     }
     for ( i = 0; i < m; i++ )
         cout << i << “ : ” <<sum [i] << endl; 
 }
image.gif

题例4:

image.gif编辑

N×N矩阵相乘
for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
     {c[i][j]=0;  
       for(k=1;k<=n;k++)
          c[i][j]=c[i][j]+a[i][k]*b[k][j];
     }
image.gif

题例5:

image.gif编辑

for( i=1; i<=n; i++) 
         for (j=1; j<=i; j++) 
             for (k=1; k<=j; k++)
    x=x+1;
image.gif

image.gif编辑

image.gif编辑

image.gif编辑

题例6:image.gif编辑

有的情况下,算法中基本操作重复执行的次数还随问题的输入数据集不同而不同

题例7:

image.gif编辑image.gif编辑

8.2空间复杂度:

空间复杂度:算法所需存储空间的度量,记作:    S(n)=O(f(n)) 其中n为问题的规模(或大小)

算法要占据的空间

       ♦算法本身要占据的空间,输入/输出,指令,常数,变量等

       ♦算法要使用的辅助空间

image.gif编辑

算法1:S(n) = O(1) 原地工作

算法2:S(n) = O(n)

后记:

本篇博文是作者对《数据结构》(C语言版)的第一篇学习记录,并未涉及算法代码实现。算法代码的实现在《数据结构》学习笔记专栏的后续笔记。

写在最后的话:

非常荣幸每一位读者能够阅读到此处!你好!来自现在以及未来的朋友!

今天期末考试结束了,这学年真的很难忘,很多地方需要总结。  就到这里吧,收拾行李回家了!

image.gif编辑

                                                                     ——By 作者:新晓·故知

                                                                                          2022.01.05

相关文章
|
4天前
|
定位技术 C语言
c语言及数据结构实现简单贪吃蛇小游戏
c语言及数据结构实现简单贪吃蛇小游戏
|
16天前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
79 29
|
16天前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
72 25
|
16天前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
58 23
|
22天前
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
|
1月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
51 2
|
2月前
|
存储 运维 监控
探索局域网电脑监控软件:Python算法与数据结构的巧妙结合
在数字化时代,局域网电脑监控软件成为企业管理和IT运维的重要工具,确保数据安全和网络稳定。本文探讨其背后的关键技术——Python中的算法与数据结构,如字典用于高效存储设备信息,以及数据收集、异常检测和聚合算法提升监控效率。通过Python代码示例,展示了如何实现基本监控功能,帮助读者理解其工作原理并激发技术兴趣。
70 20
|
3月前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
94 1
|
3月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
99 1
|
3月前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?

热门文章

最新文章