• 数据结构四章总结

    2014-12-03 18:12:18
    在第四章里,我们学习了字符串和多维数组。字符串是个或多个字符组成的有限序列。其操作主要有:赋值操作、判断操作、求长度、求子串、定位、替换、插入、删除。空白串:指串中包含一个或多个空格字符的串。串是特殊...

                    在第四章里,我们学习了字符串和多维数组。字符串是个或多个字符组成的有限序列。其操作主要有:赋值操作、判断操作、求长度、求子串、定位、替换、插入、删除。空白串:指串中包含一个或多个空格字符的串。串是特殊的线性表(结点是字符),所以串的存储结构与线性表的存储结构类似。串的顺序存储结构简称为顺序串: 顺序串又可按存储分配的不同分为:静态存储分配:直接用定长的字符数组来定义。优点是涉及串长的操作速度快,但不适合插入、链接操作。动态存储分配:是在定义串时不分配存储空间,需要使用时按所需串的长度分配存储单元。串的链式存储就是用单链表的方式存储串值,串的这种链式存储结构简称为链串。链串与单链表的差异只是它的结点数据域为单个字符。顺序串上子串定位的运算:又称串的“模式匹配”或“串匹配”,是在主串中查找出子串出现的位置。 

          多维数组:数组一般用顺序存储的方式表示。存储的方式有:1.行优先顺序,也就是把数组逐行依次排列。2.列优先顺序,就是把数组逐列依次排列。 地址的计算方法:按行优先顺序排列的数组:LOCaij=LOCa11+((i-1*n+j-1))*d.。按列优先顺序排列的数组:LOCaij=LOCa11+((j-1*n+i-1))*d. 矩阵的压缩存储:为多个相同的非零元素分配一个存储空间;对零元素不分配空间。特殊矩阵的概念:所谓特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。稀疏矩阵的概念:一个矩阵中若其非零元素的个数远远小于零元素的元素总个数,则该矩阵称为稀疏矩阵。特殊矩阵的类型:①对称矩阵:满足aij=aji)。②三角矩阵:上三角阵:k=i*2n-i+1/2+j-iLOCaij=LOCsa[0]+k*d. ③ 下三角LOCaij=LOCsa[0]+k*d.  ④ 对角矩阵稀疏矩阵的压缩存储方式用三元组表把非零元素的值和它所在的行号列号做为一个结点存放在一起,用这些结点组成的一个线性表来表示。但这种压缩存储方式将失去随机存储功能。加入行表记录每行的非零元素在三元组表中的 起始位置,即带行表的三元组表。

    展开全文
  • 数据结构 第一:绪论 1.数据存储结构包括哪几种类型?数据逻辑结构包括哪几种类型? 存储结构包括顺序存储、链式存储、索引存储、散列存储。 逻辑结构包括线性结构, 非线性结构(集合、树形结构、图形...

    数据结构

    第一章:绪论

    1.数据存储结构包括哪几种类型?数据逻辑结构包括哪几种类型?

           存储结构包括顺序存储、链式存储、索引存储、散列存储。

           逻辑结构包括线性结构,

    非线性结构(集合、树形结构、图形(网状)结构)

    2.数据结构是一门研究什么内容的学科?

           数据结构是一门研究在非数值计算的程序设计问题中,计算机的操作对象对象间的关系施加于对象的操作的学科。

    3.数据元素之间的关系在计算机中有几种表示方法?各有什么特点?

           四种表示方法:

    1. 顺序存储方式

    数据元素顺序存放,每个存储结点只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大,但有些操作(如插入、删除)效率较差。

    1. 链式存储方式

    每个存储结点除包含数据元素信息外还包含一组(至少一个)

    指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续,便于动态操作(如插入、删除等),但存储空间开销大(用于指针),另外不能折半查找等。

    1. 索引存储方式

    除数据元素存储在一地址连续的存储空间外,尚需建立一个索引表,索引表的索引项指示存储结点的存储位置(下标)或存储区间端点(下标,非稠密索引),兼有静态和动态特性。

    1. 散列存储方式

    利用散列函数和解决冲突的方法,将关键字散列在连续的有限的地址空间内,并将散列函数的值解释成关键字所在元素的存储地址。其特点是存取速度快,只能按关键字随机存取,不能顺序存取,也不能折半存取。

    4.数据类型和抽象数据类型是如何定义的?二者有何相同和不同之处?抽象数据类型的主要特点是什么?使用ADT的主要好处是什么?

    “数据类型”是程序设计语言中的一个概念,它是一个值的集合和操作的集合,如C语言中的整型、实型、字符型等。整型值(对具体机器都应有整数范围)的操作有加、减、乘、除、求余等。实际上,数据类型是厂家提供给用户的已实现了的数据结构

    “ADT”是指一个数学模型及定义在该模型上的一组操作。“抽象”的意义在于数据类型的数学抽象特性。抽象数据类型的定义仅取决于它的逻辑特性,而与其在计算机内部如何表示和实现无关。无论其内部结构如何变化,只要它的数学特性不变就不影响它的外部使用。

    抽象数据类型和数据类型实质上是一个概念,但是抽象数据类型的范围更广,它已不再局限于机器已定义和实现的数据类型,还包括用户在设计软件系统时自行定义的数据类型

    使用抽象数据类型定义的软件模块含定义、表示、实现三部分,封装在一起,对用户透明(提供接口),而不必了解实现细节。

    抽象数据类型的出现使程序设计不再是“艺术”,而是向“科学”迈进了一步。

     

    5.

    1. 在数据结构课程中,数据的逻辑结构、数据的存储结构、数据的运算之间存在着什么关系?

    数据的逻辑结构反映数据元素之间的逻辑关系(即数据元素之间的关联方式或“邻接关系”)。

    数据的存储结构是数据结构在计算机中的表示,包括数据元素的表示及其关系的表示。

    数据的运算是对数据定义的一组操作,运算是定义在逻辑结构上的,和存储结构无关,而运算的实现则依赖与存储结构。

     

    1. 若逻辑结构相同但存储结构不同,则为不同的数据结构。这样的说法对吗?举例说明。

    逻辑结构相同但存储结构不同,可以是不同的数据结构。

    例如:线性表的逻辑结构属于线性结构,采用顺序存储结构为顺序表,而采用链式存储结构称为线性链表。

    1. 在给定的逻辑结构及其存储表示上可以定义不同的运算集合,从而得到不同的数据结构。这样的说法对吗?举例说明之。

    对,栈和队列的逻辑结构相同,其存储表示也可相同(顺序存储和链式存储),但由于其运算集合不同称为不同的数据结构

    1. 评价各种不同数据结构的标准是什么?

    数据结构的评价非常复杂,可以考虑两个方面:

    一是所选数据结构是否准确、完整地刻画了问题的基本特征

    二是是否容易实现(如对数据分解是否恰当;

    逻辑结构的选择是否适合于运算的功能,

    是否有利于运算的实现;

    基本运算的选择是否恰当)

    6.评价一个好的算法,你是从哪几个方面来考虑的?

           评价好的算法有四个方面:

           一:算法的正确性

           二:算法的易读性

           三:算法的健壮性

           四:算法的时空效率(效率与低存储量需求)

    7.解释和比较一下各组概念:

    1. 算法的时间复杂性

    算法的时间复杂性是算法输入规模的函数

    算法的输入规模或问题的规模是作为该算法输入的数据所含数据元素的数目或与此数目有关的其他参数。有时考虑算法在最坏情况下的时间复杂度或平均时间复杂度。

    1. 算法

    算法是对特定问题求解步骤的描述,是指令的有限序列,其中每一条指令表示一个或多个操作。算法具有五个重要特性:有穷性、确定性、可行性、输入和输出

    1. 频度

    在分析算法时间复杂度时,有时需要估算基本操作的原操作,它是执行次数最多的一个操作,该操作重复执行的次数称为频度。

    8.数据结构与数据类型有什么区别?

           “数据结构”这一术语有两种含义:一是作为一门课程的名称;二是作为一个科学的概念。作为科学概念,目前尚无公认定义,一般认为,讨论数据结构要包括三个方面,数据的逻辑结构、数据的存储结构、数据的运算。

    “数据类型”是值的集合和操作的集合,可以看作是已实现了的数据结构,后者是前者的一种简化情况。

    9.请简要列出影响一个算法(或程序)时间效率的主要因素,并指出其中与算法(或程序)本身直接有关的因素。

           事先估算算法运行时间主要考虑问题的“规模”算法执行的“基本操作”的次数

           问题的“规模”指待解决问题的数量,如查找中元素的个数,元素个数越多,查找需要的时间越长,这是影响算法运行时间的主要因素。

           “基本操作”是算法在解决某问题时的主要操作,如在查找运算中元素间的比较操作可以看作是基本操作,执行基本操作的次数越少,运行时间越短,执行基本操作的次数越多,运行时间就越长。

    展开全文
  • 数据结构分别为逻辑结构、(存储)物理结构和数据的运算个部分。 为什么要学数据结构? 首先,因为数据结构作为计算机专业的专业基础课程,是计算机考研的必考科目之一,如果打算报考计算机专业的研究生,你...

    系列文章

    第一章:基础知识

    第二章:线性表

    第三章:栈和队列 

    第四章:字符串和数组

    第五章:树和二叉树

    第六章:图

    第七章:排序算法


    前言

    数据结构:是指相互之间存在一种或多种特定关系的数据元素的集合用计算机存储、组织数据的方式。数据结构分别为逻辑结构、(存储)物理结构和数据的运算三个部分

    为什么要学数据结构?

    首先,因为数据结构作为计算机专业的专业基础课程,是计算机考研的必考科目之一,如果打算报考计算机专业的研究生,你必须学好它;其次,数据结构是计算机软考、计算机等级考试等相关考试的必考内容之一,想要顺利通过这些考试,你也必须学好它;最后,数据结构还是你打算今后学习计算专业其他课程的基础,如操作系统、编辑原理、数据库管理系统、软件工程、人工智能等。总而言之,你既然已经与计算机接轨就必须掌握好它。

    如何学习数据结构?

    对于初学者来说,数据结构是门概念上比较抽象的课程,不是太容易掌握,需要构思和理解。万事开头难,只要你掌握了学习这门课的方法和技巧,就会变得很容易了。不管学什么,首先应该做好充分的心理准备,建立好自信心,拥有一颗战胜困难的决心,才能不畏惧、不退缩,直至胜利归来。其次,就是最好有C语言基础,这样学起来事半功倍,当然没有C语言基础也行,可以一边学数据结构一边巩固C语言知识。最后,就是多动手!多动手!多动手!重要的事情说三遍!只有亲自动手上机操作或用笔在纸上画画写写才能加深映像,方便理解记忆。?


    第一章:基础知识

    第1节:数据结构概述

      1.1 概念术语

      1.2数据的逻辑结构

      1.3数据的存储(物理)结构

      1.4抽象数据类型

      1.5算法

    1.6时间复杂度

    1.7空间复杂度

    第2节:C语言基础

    2.1 开发环境

    2.2 递归与非递归(重点)

    2.3参数传递

    2.4 结构体和联合体

    2.5 链表

    2.6 内存的分配与释放


     

    第1节:数据结构概述

    数据结构的主要任务是通过分析数据对象的结构特征,包括逻辑结构及数据对象之间的关系,然后把逻辑结构表示成计算机课实现的物理结构,从而便于计算机处理。

     

      1.1 概念术语

    (1)数据(Data)是能被计算机处理的符号或符号集合,含义广泛,可理解为“原材料”。如字符、图片、音视频等。

    (2)数据元素(data element)是数据的基本单位。例如一张学生统计表。

    (3)数据项(data item)组成数据元素的最小单位。例如一张学生统计表,有编号、姓名、性别、籍贯等数据项。

    (4)数据对象(data object)是性质相同的数据元素的集合,是数据的一个子集。例如正整数N={1,2,3,····}。

    (5)数据结构(data structure)是数据的组织形式,数据元素之间存在的一种或多种特定关系的数据元素集合。

    (6)数据类型(data type)是按照数据值的不同进行划分的可操作性。在C语言中还可以分为原子类型和结构类型。原字类型是不可以再分解的基本类型,包括整型、实型、字符型等。结构类型是由若干个类型组合而成,是可以再分解的。

     

      1.2数据的逻辑结构

    逻辑结构(logical structure)是指在数据中数据元素之间的相互关系。数据元素之间存在不同的逻辑关系构成了以下4种结构类型。

    (1)集合结构:集合的数据元素没有其他关系,仅仅是因为他们挤在一个被称作“集合”的盒子里。

    (2)线性结构:线性的数据元素结构关系是一对一的,并且是一种先后的次序,就像a-b-c-d-e-f-g·····被一根线穿连起来。

    (3)树形结构:树形的数据元素结构关系是一对多的,这就像公司的部门级别,董事长-CEO\CTO-技术部\人事部\市场部.....。

    (4)图结构:图的数据元素结构关系是多对多的。就是我们常见的各大城市的铁路图,一个城市有很多线路连接不同城市。

     

      1.3数据的存储(物理)结构

    存储结构(storage structure)也称为物理结构(physical structure),指的是数据的逻辑结构在计算机中的存储形式。数据的存储结构一般可以反映数据元素之间的逻辑关系。分为顺序存储结构和链式存储结构。

    (1)顺序存储结构:是把数据元素存放在一组存储地址连续的存储单元里,其数据元素间的逻辑关系和物理关系是一致的。

    (2)链式存储结果:是把数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的,数据元素的存储关系并不能反映其逻辑关系,因此需要借助指针来表示数据元素之间的逻辑关系。

     

    小结:数据的逻辑结构和物理结构是密切相关的,在学习数据的过程中会发现,任何一个算法的设计取决于选定的数据逻辑结构,而算法的实现依赖于所采用的存储结构。

     

      1.4抽象数据类型

    抽象数据类型(abstract data type,ADT)是描述具有某种逻辑关系的数据模型,并对在数学模型上进行的一组操作。抽象数据类型描述的是一组逻辑上的特性,与在计算机内部表示无关,计算机中的整数数据类型是一个抽象数据类型,不同处理器可能实现方法不同,但其逻辑特性相同,即加、减、乘、除等运算是一致的。“抽象”的意思是数据类型的数学抽象特性而不是指它们的实现方法。抽象数据类型体现了程序设计中的问题分解、抽象、信息隐藏等特性,可以把现实中的大问题分解为多个规模小且容易处理的小问题,然后建立起一个能被计算机处理的数据,并把每个功能模块的实现细节作为一个独立的单元,从而使具体实现过程隐藏起来。就类似建一栋房子,分成若干个小任务,如地皮规划、图纸设计、施工、装修等,整个过程与抽象数据类型中的问题分解类似。而搬砖人不需要了解图纸设计如何,设计图纸人员不需要了解施工的地基、砌墙的具体细节,装修工人不用关系图纸和搬砖过程,这就是抽象类型中的信息隐藏。

    抽象数据类型的概念可能让初学者不太容易理解。例如线性表的抽象数据类型的描述数据对象集合:线性表的数据对象集合为{a1,a2,a3,····,an},每个元素的类型均为DataType。其中,除了第一个元素a1外,每一个元素有且只有一个直接前驱元素;除了最后一个元素an外,每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的。

     

      1.5算法

    算法(algorithm)是解决特定问题求解步骤的描述,在计算机中表现为有限的操作序列。在数据类型建立起来之后,就要对这些数据类型进行操作,建立起运算的集合即程序。运算的建立、方法好坏直接决定着计算机程序原型效率的高低。

    (1)数据结构和算法的关系

    两者基友联系又有区别。联系是程序=算法+数据结构。数据结构是算法实现的基础,算法总是要依赖某种数据结构来实现的。算法的操作对象是数据结构。区别是数据结构关注的是数据的逻辑结构、存储结构有一集基本操作,而算法更多的是关注如何在数据结构的基本上解决实际问题。算法是编程思想,数据结构则是这些思想的基础。

    (2)算法的五大特性

    有穷性,是指算法在执行有限的步骤之后,自动结束而不是出现无限循环,并且每一个步骤在可接受的时间内完成。

    确定性,是指算法执行的每一步骤在一定条件下只有一条执行路径,也就是相同输入只能有一个唯一的输出结果。

    可行性,是指算法每一步骤都必须可行,能够通过有限的执行次数完成。

    输入,是指算法具有零个或多个输入。

    输出,是指算法至少有一个或多个输出。

     

    1.6时间复杂度

    在进行算法分析时,语句总是执行次数 T(n) 是关于问题规模 n 的函数。进而分析次数T(n)随规模n的变化情况并确定T(n)的数量级。算法的时间复杂度就是算法的时间度量,记作T(n) = O(f(n))。它表示随问题规模n的增大,算法的执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度。其中,f(n)是问题规模n的某个函数。

    算法的时间复杂度是衡量一个算法好坏的重要指标。一般情况下,随着规模n的增大,次数T(n)的增长较慢的算法为最优算法。常见时间复杂度从小到大依次排列:O(1) < O(log2n) < O(n) < O(n²)<O(n³) ····<O(n!)

    例如:

    (a) 1;      // 时间复杂度为O(1)

    (b)for(i =1 ; i<=n ;i++){  x= x+1;}    // 时间复杂度为O(n),称为线性阶

    (c)for(i =1 ; i<=n ; i++){for(j=1;j<=n;j++){  x=x+1 } }  // 时间复杂度为O(n²),称为平方阶

     

    1.7空间复杂度

    空间复杂度(space complexity)作为算法所需存储空间的量度,记做S(n) = O (f(n))。其中,n为问题的规模;f(n)为语句关于n的所占存储空间的函数。

    一般情况下,一个程序在机器上运行时,除了需要存储程序本身的指令、常数、变量和输入数据外,还需要存储对数据操作的存储单位。若输入数据所占空间只取决于问题本身,和算法无关,这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常量,则称此算法为原地工作,空间复杂度为O(1)。

     

    第2节:C语言基础

    C语言作为数据结构的算法描述语言,广泛应用于系统软件和应用软件的开发。在真正开发学习数据结构知识之前,先复习一下C语言基础,为数据结构的学习扫清障碍。本节主要针对重点和难点部分详细讲解,包括开发环境、函数与递归、指针、参数传递、动态内存分配及结构体、联合体。

     

    2.1 开发环境

    C语言常见的开发环境有很多种,如LCC、Turbo C2.0、Visual C++、Borland C++,本章主要介绍使用最多的Turbo C 2.0和Visual C++ 6.0。

    (1)Turbo C 2.0 :1989年,美国Borland公司推出,简称TC。它集编辑、编译、连接和运行一体的C程序集成开发环境。界面简单、上手容易、使用方便,通过一个简单的主界面可以很容易编辑、编译和链接程序,也是初学者广发使用的开发工具。

    (2)Visual C++6.0:是强大的C/C++软件开发工具,使用非常广泛,已经成为首选的开发工具。利用它可以开发Windows SDK、MFC等应用程序。

     

    2.2 递归与非递归(重点)

    在数据结构与算法实践过程中,经常会遇到利用递归实现算法的情况。递归是一种分而治之、将复杂问题转换成简单问题的求解方法。使用递归可以使编写的程序简洁、结构清晰,程序的正确性很容易证明,不需要了解递归调用的具体细节。

    (1)函数的递归:就是函数自己调用自己,即一个函数在调用其他函数的过程中,又出现对自身的调用,这种函数称为递归函数。函数的递归调用就是自己调用自己,可以直接调用自己也可以间接调用。其中,在函数中直接调用自己称为函数的直接递归调用;如果函数f1调用了函数f2又再次调用了函数f1,这种调用的方式我们称之为间接递归调用。

    例1:利用递归求n! :有两种情况,当n=0递归结束,返回值为1 ;当n !=0时,继续递归。

    //递归求n!函数实现
    
    int factorial (int  n){
    
        if(n ==0 )
            return 1;
    
        else
            return n*factorial(n-1);
    }
    

      例2:已知有数组a[] ,要求利用递归实现求n个数中的最大值。

    a[] ={0,···,n-1};
    
    int findMax(int a[] ,int n){
    
        int  m ;
    
        if (n<=1)
            return a[0];
    
        else
        {
            m = findMax(a,n-1);
            return a[n-1] >= m ?a[n-1] : m ;//找到最大值
        }
    }

     

    (2)迭代与递归

    迭代与递归是程序设计中最常用的两种结构。任何能使用递归解决的问题都能使用迭代的方法解决。迭代和递归的区别是,迭代使用的是循环结构,递归使用的是选择结构。大量的递归会耗费大量的时间和内存,每次递归调用都会建立函数的一个备份,会占用大量的内存空间。迭代则不需要反复调用函数和占用额外的内存。对于较为简单的递归问题,可以利用简单的迭代将其转化为非递归。而对于较为复杂的递归问题,需要通过利用数据结构中的栈来消除递归。

    (3)指针

    是C语言中一个重要概念,也是最不容易掌握的内容。指针常常用在函数的参数传递和动态内存分配中。指针与数组相结合,使引用数组成分的形式更加多样化,访问数组元素的手段更加灵活;指针与结构体结合,利用系统提供的动态存储手段,能构造出各种复杂的动态数据结构;利用指针形参,使函数能实现传递地址形参和函数形参的要求。接下里会介绍指针变量的概念、指针与数组、函数指针与指针函数。

    指针是一种变量,也称之为指针变量,它的值不少整数、浮点数和字符,而是内存地址。指针的值就是变量的地址,而变量又拥有一个具体的值。因此,可以理解为变量名直接引用了一个值,指针间接地引用了一个值。

    指针可以与变量结合,也可以与数组结合使用。指针数组是一种存放一组变量的地址。数组指针是一个指针,表示该指针指向数组的指针。数组指针可以进行自增或自减运算,但是数组名则不能进行自增或自减运算,这是因为数组名是一个常量指针,它是一个常量,常量值是不能改变的。函数指针与指针函数同理。

     

    2.3参数传递

    (1)传值调用:分为实际参数和形式参数。例如:

    int GCD(int m ,int n);
    
    void main(){
        int a,b,v,
        v = GCD(a,b);  //实际参数
    }
    
    int GCD(int m ,int n){ //形式参数
        int r;
        r = m;
        do{
            m=n;
            n=r;
            r=m&n;
          }while(r);
    
        return n;
    }

    上面的函数参数传递属于参数的单向传递,即a和b可以把值传递给m和n,而不是可以把m和n传递给a和b。实际参数和形式参数的值的改变都不会互相收到影响。

    (2)传指针地址参数:略

     

    2.4 结构体和联合体

    也称共用体,是自定义的数据类型,用于构造非数值数据类型,在处理实际问题中应用非常广泛。数据结构中的链表、队列、树、图等结构都需要用到结构体。教师表结构体如下所示。

    //结构体类型
    struct teacher{
        //数据项
        int no;
        char name[20];
        char sex[4];
        char headship[8];
        char degree[6];
        long int phone;
    }

    与结构体一样,联合体也是一种派生的数据类型。但是与结构体不同的是,联合体的成员共享同一个存储空间。定义联合体一般形式如下所示。

    union 共用体名{
    
        成员列表;
    }
    变量列表;
    
    ——————————————————————————
    union data{
    
        int a ;
        float b;
        char c;
        double d;
    }abc;
    
    //或写成
    union data{
        int a;
        float b;
        char c;
        double d;
    };
    union data abc;
    
    

     

    2.5 链表

    在C语言中,处理已知数据可以使用数组。如果事先并不知道要处理的数据的个数,则需要使用链表结构。链表需要动态分配内存,链表的长度随时可以发生变化。链表有一个指针类型的成员指向自身,该指针指向与结构体一样的类型。例如如下语句:

    struct node{
        int data;
        struct data *next;
    }
    

    自引用结构体类型为struct node,该结构体类型有两个成员:整数成员data,指针成员next。成员next是指向结构体为struct node类型的指针。通过这种形式定义的结构体通过next指针把两个结构体变量连在一起。这种自引用结构体单元称为结点,结点之间通过箭头连接起来,构成一张表,称为链表。

    链表中第一个结点的指针称为头指针且可以访问链表的每一个结点。为了方便操作,在链表的第一个结点之前增加一个头结点。

    2.6 内存的分配与释放

    (1)malloc函数主要作用是分配一块长度为size的内存空间。void *malloc(unsigned int size);其中,size就是要分配的内存空间大小字节。使用时最好先检查一下是否分配成功,否则返回null,可以保证程序的正确运行。使用完分配后的空间要利用free函数及时释放。

    (2)free函数主要作用是将内存空间释放。void free (void *p); 其中,参数p指向要释放的内存空间。不能使用已经被free函数释放的内存空间。

     


    下一章:

    数据结构与算法——从零开始学习(二)线性表

     

     

    欢迎,😆大家关注公众号:(推送数据结构+算法+Java+人生感悟+理财知识+互联网事件等)

    展开全文
  • 数据结构思维导图

    2018-10-08 18:41:50
    数据结构宏观导图 &...数据结构三章-栈、队列、数组 &nbsp; &nbsp; 数据结构四章-树与二叉树 &nbsp; &nbsp; 数据结构第五–图 &nbsp; &nbsp; 数据结构第六...

    数据结构宏观导图

     


    这里写图片描述

     

    数据结构-第一章概论

    数据结构第二章-线性表

     


    这里写图片描述

     

    数据结构第三章-栈、队列、数组

     


    这里写图片描述

     

    数据结构第四章-树与二叉树

     


    这里写图片描述

     

    数据结构第五章–图

     


    这里写图片描述

     

    数据结构第六章–查找

     


    这里写图片描述

    展开全文
  • 4.1采用顺序结构存储串,编写一个实现串通配符匹配的算法pattern_index(),其中的通配符只有“?”,它可以和任一字符匹配成功,例如,pattern_index("?re","there are"),返回的结果是2。 代码: #include #include...

    4.1采用顺序结构存储串,编写一个实现串通配符匹配的算法pattern_index(),其中的通配符只有“?”,它可以和任一字符匹配成功,例如,pattern_index("?re","there are"),返回的结果是2。

    代码:

    #include <iostream>
    #include <malloc.h>
    #include <cstring>
    #include <cstdio>
    using namespace std;
    #define MaxSize 100
    typedef struct
    {
        char data[MaxSize];
        int length;
    } SqString;
    void StrAssign(SqString *&s,char a[])
    {
        s=(SqString *)malloc(sizeof(SqString));
        int i;
        for(i=0; a[i]!='\0'; i++)
        {
            s->data[i]=a[i];
        }
        s->length=i;
    }
    int pattern_index(char c[],SqString *s)
    {
        int count=0;
        for(int i=0; i<s->length; i++)
        {
            int j,k;
            for(j=i,k=0; k<strlen(c)&&(s->data[j]==c[k]||c[k]=='?'); j++,k++); //循环完看k的值,也就是看是否能循环完子串的长度
            if(k==strlen(c))
                count++;
        }
        if(count!=0)
            return count;
        else
            return -1;
    }
    int main()
    {
        SqString *s;
        char ch1[100],ch2[100];
        gets(ch1);
        gets(ch2);
        StrAssign(s,ch1);
        cout<<pattern_index(ch2,s)<<endl;
        return 0;
    }
    


    展开全文
  • 数据结构(C语言版本) 第1 绪论 1.常用的数据结构类型:集合、线性、树形、图状。 2.数据结构: - 逻辑结构:数据元素之间的关系 - 存储结构:数据结构在计算机中的表示。存储结构分为:顺序存储结构和...
  • Caché 算法与数据结构

    2020-07-01 11:43:50
    三章 Caché 算法与数据结构 链表原理 第四章 Caché 算法与数据结构 栈原理 第五 Caché 算法与数据结构 队列原理 第六 Caché 算法与数据结构 循环队列 第七 Caché 算法与数据结构 双端队列 第八 Cach...
  • 一直在说要扎实自己的数据结构与算法的能力,可是到底什么是数据结构,到底什么是算法呢? 数据结构与算法有啥区别呢? 突然想起来,得把最经典的数据结构(C语言) 严蔚敏、吴伟民编著的教材翻翻了。 全书...
  • 第一数据结构的 基本概念 定义 在任何问题中,数据元素都不是孤立存在的,而是在它们之间存在着某种关系,这种数据元素相互之间的关系称为结构(Structure)。数据结构是相互之间存在一种或多种特定关系的数据...
  • 如果计算机系只开三门课,那么这三门课就一定是:离散数学,数据结构与算法,编译原理。 如果只开一门课,那剩下的就一定是:数据结构与算法。 下面列出一份数据结构算法书目,先从最著名的说起 A ...
  • 串  目录 ...系列索引:《数据结构》C语言版 (清华严蔚敏考研版) 全书知识梳理   1.理解串的基本概念。 2.掌握串的一些基本操作及其实现。   3.了解串的种基本存储结构。 ...
  • 数据结构笔记链接: 第一 绪论 第二 线性表 第三章 栈和队列 第四章 串 第五 数组和广义表 第六 树和二叉树 第七 图 第八 排序 第九 查找 9.1 基本概念 9.2 基于线性表的查找 9.2.1 ...
  • 数据结构期末复习必备第一 绪 论考点习题1.数据结构是一门研究非数值计算程序设计中计算机的 ① 以及它们之间的 ② 和运算等的学科。2.从逻辑上可以把数据结构分为 。3.线性结构的顺序存储结构是一种 ① 的存储...
  • 我在学习和开发软件应用程序时就开始发现用计算机能解决很多问题,而遇到的实际问题很多都是关于数据表示和数据处理,从第一遍快速看了《数据结构导论》,发现数据表示和数据处理的核心问题之一是数据结构及其实现。...
  • 数据结构知识整理

    2018-09-25 12:02:45
    1.数据结构:是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作等的学科。 2.数据结构涵盖的内容: 3.基本概念和术语: 数据:对客观事物的符号表示,在计算机科学中是指所有能...
  • 第一 绪论上 第一 绪论 下 第二 向量 上 第二 向量 下 第三章 列表 第四章 栈与队列 第五 二叉树 第六 图 第七 搜索树 第八 高级搜索树(上) 第八 高级搜索树(下) 第九 词典 第十 ...
  • 数据结构(C语言版第二版)思维导图 第一 第二三章四章 第五 第六 第七 第八
  • 数据结构第一绪论已经结束。
  • 第一作为绪论,主要介绍了数据结构与算法中的一些基本概念和术语。对于这些概念术语,我个人不推崇死记硬背,记住了当然好,记不住也没关系,但是一定要做到完全理解。就算嘴上说不出来,心里也一定要明白这个...
1 2 3 4 5 ... 20
收藏数 128,107
精华内容 51,242