《数据结构(C语言版)》学习笔记总结(一)绪论

概述

本书第一章是绪论,主要讲了数据结构与算法中的一些最基本的概念和一些术语,这些术语当然不用去死记硬背,记住了OK,记不住也没关系,但是一定要理解其含义,即使不能描述出来,在心里也一定要把它含义搞清楚。

数据结构

什么是数据结构

官方统一定义——没有

  • Sartaj Sahni,《数据结构、算法与应用》

“数据结构是数据对象,以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”

  • Clifford A.Shaffer,《数据结构与算法分析》

“数据结构是ADT (抽象数据类型 Abstract Data Type )的物理实现。”

  • 中文维基百科

“ 数据结构(data structure)是计算机中存储、组织数据的方式。通常情况下,精心选择的数据结构可以带来最优效率的算法。”

所以到底什么是数据结构???

数据对象在计算机中的组织方式

  • 逻辑结构
  • 物理存储结构

数据对象必定与一系列加在其上的 操作 相关联

完成这些操作所用的方法就是算法

基本定义

数据(data)是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素(data element)是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。

数据对象(data object)是性质相同的数据元素的集合,是数据的一个子集。

数据结构(data structure)又称逻辑结构,是相互之间存在一种或多种特定关系的数据元素的集合。通常有以下四类基本结构:集合、线性结构、树形结构、图状结构或网状结构。

存储结构(物理结构)是数据结构在计算机中的表示(又称映像)。

数据类型(data type)是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型(Abstract Data Type)是指一个数学模型以及定义在该模型上的一组操作,可细分为:原子类型、固定聚合类型、可变聚合类型。

抽象数据类型(Abstract Data Type)

  • 数据类型

    • 数据对象集
    • 数据集合相关联的操作集
  • 抽象:描述数据类型的方法不依赖于具体实现

    • 与存放数据的机器无关
    • 与数据存储的物理结构无关
    • 与实现操作的算法和编程语言均无关

只描述数据对象集和相关操作集 只描述数据对象集和相关操作集“ 是什么”,并不涉及“ 如何做到”的问题

“矩阵”的抽象数据类型定义

“矩阵”的抽象数据类型定义

算法(Algorithm)

算法的定义

  • 一个有限指令集
  • 接受一些输入(有些情况下不需要输入)
  • 产生输出
  • 一定在有限步骤之后终止
  • 每一条指令必须

    • 有充分明确的目标,不可以有歧义
    • 计算机能处理的范围之内
    • 描述应不依赖于任何一种计算机语言以及具体的实现手段

算法的特性

算法与数据结构密不可分,算法往往是建立在特定数据结构之上的。

一个算法有5个重要特性:有穷性确定性可行性输入输出

而衡量一个算法是否优秀,则主要从以下几点考虑:正确性可读性健壮性时间复杂度空间复杂度

什么是好的算法?

空间复杂度

  • 空间复杂度S(n)—— 根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限,造成程序非正常中断。

时间复杂度

  • 时间复杂度T(n)—— 根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果。

在分析一般算法的效率时,我们经常关注下面两种复杂度:

什么是好的算法

复杂度的渐进表示法

复杂度的渐进表示法

复杂度分析小窍门

复杂度分析小窍门

说明

为了今后对书中用列测试的方便,本章还预定义了一些会被频繁使用的常量和类型。具体代码如下

/***********************************
 *                                 *
 * 作  者:StrayedKing              *
 *                                 *
 * 文件名: Status.h                 *
 *                                 *
 * 内  容: 相关状态码及宏函数列表     *
 *                                 *
 ***********************************/

#ifndef STATUS_H
#define STATUS_H

/* 状态码 */
#define    TRUE        1            //真 
#define    FALSE        0            //假
#define YES            1            //是
#define NO          0            //否 
#define    OK            1            //通过
#define    ERROR        0            //错误
#define SUCCESS        1            //成功 
#define UNSUCCESS    0            //失败 
#define    INFEASIBLE    -1            //不可行

#ifndef _MATH_H_                 //系统中已有此状态码定义,要避免冲突 
#define    OVERFLOW    -2            //堆栈上溢
#define UNDERFLOW    -3            //堆栈下溢
#endif 

#ifndef NULL
#define NULL ((void*)0)
#endif

/* 状态码识别类型 */
typedef int Status;

/*宏函数*/
//函数暂停一段时间
#define Wait(x)
 {
    double _Loop_Num_;    for(_Loop_Num_=0.01;_Loop_Num_<=100000.0*x; _Loop_Num_+=0.01)
    ;
 }//设立一个空循环 

//摁Enter键继续 
#define PressEnter
 {
    fflush(stdin);
    printf("Press Enter...");
    getchar();
    fflush(stdin);
 }

#endif

此外,为了以后的测试数据方便,在此定义一个从文件中读取数据的函数Scanf,使用的格式与fscanf类似。

/***********************************
 *                                 *
 * 作  者:StrayedKing              *
 *                                 *
 * 文件名: Scanf.c                  *
 *                                 *
 *                                 *
 ***********************************/ 

#ifndef SCANF_C
#define SCANF_C

#include <stdio.h>
#include <string.h>
#include <stdarg.h>                //提供宏va_list、va_start、va_arg、va_end    
#include <ctype.h>                 //提供isprint原型 

/*
    自定义的数据录入函数,用于从文件fp
中读取格式化的输入。

    与fscanf不同之处在于此函数只会读取
西文字符,对于中文字符,则会跳过。 
*/

int Scanf(FILE *fp, char *format, ...)
{
    int *i;
    char *ch, *s;
    float *f;
    int count, k, len, n;        
    int tmp;
    va_list ap;
    
    len = strlen(format);
    
    va_start(ap, format);
    
    for(count=0,k=2; k<=len; k=k+2)
    {
        while((tmp=getc(fp))!=EOF)            //跳过所有非西文字符 
        {
            if((tmp>=0 && tmp<=127))
            {
                ungetc(tmp, fp);            //遇到首个西文字符,将此西文字符放入输入流 
                break;
            }
        }
        
        if(tmp==EOF)
            break;
        
        if(format[k-1]=='c')                //读取字符         
        {
            ch = va_arg(ap, char*);
                        
            if(tmp!=EOF)
                count += fscanf(fp, "%c", ch);                    
        }    
        
        if(format[k-1]=='d')                //读取整型 
        {
            i = va_arg(ap, int*);
            
            while((tmp=getc(fp))!=EOF)
            {
                if((tmp>='0' && tmp<='9') || tmp=='-' || tmp=='+')
                {
                    ungetc(tmp, fp);
                    break;
                }
            }
            
            if(tmp!=EOF)
                count += fscanf(fp, "%d", i);
        }

        if(format[k-1]=='f')                //读取浮点型 
        {
            f = va_arg(ap, float*);
            
            while((tmp=getc(fp))!=EOF)
            {
                if((tmp>='0' && tmp<='9') || tmp=='-' || tmp=='+'|| tmp=='.' )
                {
                    ungetc(tmp, fp);
                    break;
                }
            }
            
            if(tmp!=EOF)
                count += fscanf(fp, "%f", f);
        }
        
        if(format[k-1]=='s')                //读取字符串 
        {
            s = va_arg(ap, char*);
            
            while((tmp=getc(fp))!=EOF && (!isprint(tmp) || tmp==' '))
                ;
            
            n = 0;
            if(!feof(fp))
            {
                ungetc(tmp, fp);
                while((tmp=getc(fp))!=EOF)
                {
                    if(isprint(tmp) && tmp!=' ')
                        s[n++] = tmp;
                    else
                        break;    
                }
                ungetc(tmp, fp);            
            }
                                                                                
            s[n] = '\0';
                    
            count++;        
        }        
    }
        
    va_end(ap);
    
    return count;
}

#endif 

说明

本系列笔记为本人总结或整理,另外参考了网络上的一些资料并在显要位置注明了作者或来源。整理过程中难免有所疏漏,如有错误,欢迎指出!


如果您发现了文章有任何错误欢迎指正,有任何意见或建议,或者有疑问需要我提供帮助,也欢迎在下面留言,只需输入昵称+邮箱即可,网站或博客可选填。对于所有留言内容我会及时回复,非常期待与大家的交流!

版权声明:本文(除特殊标注外)为原创文章,版权归 Geekerstar 所有。

本文链接:http://www.geekerstar.com/technology/377.html

除了有特殊标注文章外欢迎转载,但请务必标明出处,格式如上,谢谢合作。

Last modification:March 10th, 2018 at 05:34 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment