本文目录：



数据结构分类
1、数组
2、栈
3、队列
4、链表
5、树
6、散列表
7、堆
8、图




数据结构分类

数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。 

常用的数据结构有：数组，栈，链表，队列，树，图，堆，散列表等，如图所示： 

 

每一种数据结构都有着独特的数据存储方式，下面为大家介绍它们的结构和优缺点。



1、数组

数组是可以再内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问，数组下标从0开始。例如下面这段代码就是将数组的第一个元素赋值为 1。



int[] data = new int[100]；data[0]  = 1;


优点： 

1、按照索引查询元素速度快 

2、按照索引遍历数组方便

缺点：  

1、数组的大小固定后就无法扩容了 

2、数组只能存储一种类型的数据 

3、添加，删除的操作慢，因为要移动其他的元素。

适用场景： 

频繁查询，对存储空间要求不大，很少增加和删除的情况。



2、栈

栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。 栈的特点是：先进后出，或者说是后进先出，从栈顶放入元素的操作叫入栈，取出元素叫出栈。 

 

栈的结构就像一个集装箱，越先放进去的东西越晚才能拿出来，所以，栈常应用于实现递归功能方面的场景，例如斐波那契数列。



3、队列

队列与栈一样，也是一种线性表，不同的是，队列可以在一端添加元素，在另一端取出元素，也就是：先进先出。从一端放入元素的操作称为入队，取出元素为出队，示例图如下： 

 

使用场景：因为队列先进先出的特点，在多线程阻塞队列管理中非常适用。



4、链表

链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。 

 

链表的优点： 

链表是很常用的一种数据结构，不需要初始化容量，可以任意加减元素； 

添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加，删除很快；

缺点： 

因为含有大量的指针域，占用空间较大； 

查找元素需要遍历链表来查找，非常耗时。

适用场景： 

数据量较小，需要频繁增加，删除操作的场景



5、树

树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：


每个节点有零个或多个子节点； 
没有父节点的节点称为根节点；
每一个非根节点有且只有一个父节点；
除了根节点外，每个子节点可以分为多个不相交的子树；


在日常的应用中，我们讨论和用的更多的是树的其中一种结构，就是二叉树。 

 

二叉树是树的特殊一种，具有如下特点：

1、每个结点最多有两颗子树，结点的度最大为2。 

2、左子树和右子树是有顺序的，次序不能颠倒。 

3、即使某结点只有一个子树，也要区分左右子树。 

二叉树是一种比较有用的折中方案，它添加，删除元素都很快，并且在查找方面也有很多的算法优化，所以，二叉树既有链表的好处，也有数组的好处，是两者的优化方案，在处理大批量的动态数据方面非常有用。

扩展： 

二叉树有很多扩展的数据结构，包括平衡二叉树、红黑树、B+树等，这些数据结构二叉树的基础上衍生了很多的功能，在实际应用中广泛用到，例如mysql的数据库索引结构用的就是B+树，还有HashMap的底层源码中用到了红黑树。这些二叉树的功能强大，但算法上比较复杂，想学习的话还是需要花时间去深入的。



6、散列表

散列表，也叫哈希表，是根据关键码和值 (key和value) 直接进行访问的数据结构，通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。

记录的存储位置=f(key) 

这里的对应关系 f 成为散列函数，又称为哈希 (hash函数)，而散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里，这种存储空间可以充分利用数组的查找优势来查找元素，所以查找的速度很快。

哈希表在应用中也是比较常见的，就如Java中有些集合类就是借鉴了哈希原理构造的，例如HashMap，HashTable等，利用hash表的优势，对于集合的查找元素时非常方便的，然而，因为哈希表是基于数组衍生的数据结构，在添加删除元素方面是比较慢的，所以很多时候需要用到一种数组链表来做，也就是拉链法。拉链法是数组结合链表的一种结构，较早前的hashMap底层的存储就是采用这种结构，直到jdk1.8之后才换成了数组加红黑树的结构，其示例图如下： 

 

从图中可以看出，左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。 

哈希表的应用场景很多，当然也有很多问题要考虑，比如哈希冲突的问题，如果处理的不好会浪费大量的时间，导致应用崩溃。



7、堆

堆是一种比较特殊的数据结构，可以被看做一棵树的数组对象，具有以下的性质：


堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。


将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。 

(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)，满足前者的表达式的成为小顶堆，满足后者表达式的为大顶堆，这两者的结构图可以用完全二叉树排列出来，示例图如下： 

 

因为堆有序的特点，一般用来做数组中的排序，称为堆排序。



8、图

图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。 

按照顶点指向的方向可分为无向图和有向图： 

 

 

图是一种比较复杂的数据结构，在存储数据上有着比较复杂和高效的算法，分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构，这里不做展开，读者有兴趣可以自己学习深入。

1.	什么是数据结构
算法+数据结构=程序设计

数据结构是由数据和结构两方面组成，下面举一个例子可以让大家很快地理解数据结构：

比如我们实验楼的课程管理系统，每一门课程由课程号、课程名、类别、作者等组成，每门课的课程号是唯一的，但不同的课程可能属于同一个类别，或者是同一个作者写的，由此我们可以建立一张按课程号顺序排列的课程表和两张按类别和作者名顺序排列的索引表，如下图所示，这样我们就可以按课程号或课程名或类别或作者名快速地找到我们想要学的那门课程。
在这个例子中，数据就是课程、类别和作者，结构就是课程与类别和作者的关系，它体现了一种最简单的线性关系，除了线性结构外，还有集合结构和更为复杂的树形结构和图结构，简单来说，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科，，学好数据结构可以使计算机更高效地工作。
2. 数据的逻辑结构和物理结构
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
一、数据的逻辑结构：指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后件关系，而与他们在计算机中的存储位置无关。逻辑结构包括：
1.集合
数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；
2.线性结构
数据结构中的元素存在一对一的相互关系；
3.树形结构
数据结构中的元素存在一对多的相互关系；
4.图形结构
数据结构中的元素存在多对多的相互关系。
二、数据的物理结构：指数据的逻辑结构在计算机存储空间的存放形式。
数据的物理结构是数据结构在计算机中的表示（又称映像），它包括数据元素的机内表示和关系的机内表示。由于具体实现的方法有顺序、链接、索引、散列等多种，所以，一种数据结构可表示成一种或多种存储结构。

数据元素的机内表示（映像方法）： 用二进制位（bit）的位串表示数据元素。通常称这种位串为节点（node）。当数据元素有若干个数据项组成时，位串中与个数据项对应的子位串称为数据域（data field）。因此，节点是数据元素的机内表示（或机内映像）。

关系的机内表示（映像方法）：数据元素之间的关系的机内表示可以分为顺序映像和非顺序映像，常用两种存储结构：顺序存储结构和链式存储结构。顺序映像借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映像借助指示元素存储位置的指针（pointer）来表示数据元素之间的逻辑关系。
3. 常用结构
数组
在程序设计中，为了处理方便， 把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。在C语言中， 数组属于构造数据类型。一个数组可以分解为多个数组元素，这些数组元素可以是基本数据类型或是构造类型。因此按数组元素的类型不同，数组又可分为数值数组、字符数组、指针数组、结构数组等各种类别。
栈
是只能在某一端插入和删除的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。
队列
一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列是按照“先进先出”或“后进后出”的原则组织数据的。队列中没有元素时，称为空队列。
链表
是一种物理存储单元上非连续、非顺序的存储结构，它既可以表示线性结构，也可以用于表示非线性结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
树
是包含n（n>0）个结点的有穷集合K，且在K中定义了一个关系N，N满足 以下条件：

（1）有且仅有一个结点 K0，他对于关系N来说没有前驱，称K0为树的根结点。简称为根（root）。　 （2）除K0外，K中的每个结点，对于关系N来说有且仅有一个前驱。

（3）K中各结点，对关系N来说可以有m个后继（m>=0）。
图
图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。
堆
在计算机科学中，堆是一种特殊的树形数据结构，每个结点都有一个值。通常我们所说的堆的数据结构，是指二叉堆。堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆。
散列表
若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function)，按这个思想建立的表为散列表。

                                                                      

                                                                   数据结构之线性表（C语言版）

 

 

#include<stdio.h>  
#include<stdlib.h>  
#define List_Init_Size 100  
#define LISTINCREMENT 10  
//定义线性表结构  
typedef struct{  
    int *elem;  
    int length;  
    int Listsize;  
}Sqlist;  
//初始化线性  
void InitList_sq(Sqlist  *L){  
    (*L).elem=(int *)malloc(List_Init_Size*sizeof(int));  
    if(!(*L).elem)  
        exit(0);  
    (*L).length=0;  
    (*L).Listsize=List_Init_Size;  
      
}  
//插入线性表  
void ListInsert_sq(Sqlist * L,int i,int e){  
    int *newbase;  
    int *p,*q;  
     if( i<1||i>(*L).length+1)  
         exit(0);  
     if((*L).length>=(*L).Listsize){   //注意：此处的>=是严蔚敏书上说的。其实==也行，因为length是递增的。我在VC++6.0上实验通过。  
         newbase=(int *)realloc((*L).elem,((*L).Listsize+LISTINCREMENT)*sizeof(int));  
         if(!(*L).elem)   
             printf("meiyou\n");  
         (*L).elem=newbase;  
          (*L).Listsize+=LISTINCREMENT;  
     }  
     q=&((*L).elem[i-1]);  
     for(p=&((*L).elem[(*L).length-1]);p>=q;p--)  
         *(p+1)=*p;  
     *q=e;  
     (*L).length++;  
  
}  
//删除节点  
void Listdel_sq(Sqlist *L,int i){  
      int *q,*p;  
      if((i<1)||(i>(*L).length))  
          exit(0);  
      q=&((*L).elem[i-1]);  
      for(p=&((*L).elem[(*L).length-1]);q<=p;q++)  
          *(q)=*(q+1);  
      (*L).length--;  
}  
//打印线性表  
void Listprint_sq(Sqlist * L){  
    int i;  
     for(i=1;i<=(*L).length;i++)  
     { printf("%d    ",(*L).elem[i-1]);  
         printf("%d\n",&(L->elem[i-1]));  //输出变量地址  
     }  
}  
//主函数  
int main(){  
      
   Sqlist M;  
   int i,k,x,y;  
     
   InitList_sq(&M);  
   printf("          初始化线性表.......\n");  
   for(i=1;i<=12;i++)  
   ListInsert_sq(&M,i,i);  
   printf("十二个数字的线性表已经建立\n");  
   Listprint_sq(&M);  
   printf("~~~~~~~~~~~请输入序号进行操作：\n");  
       printf("1:插入      2:删除      3:退出\n");  
         
    scanf("%d",&k);  
   while(k!=3){  
   switch(k)  
   {  
       case 1: printf("请输入要插入元素的位置和值\n");  
               scanf("%d%d",&x,&y);  
               ListInsert_sq(&M,x,y);  
               Listprint_sq(&M);  
               break;  
       case 2:   printf("请输入要删除元素的位置\n");  
                scanf("%d",&x);  
                Listdel_sq(&M,x);  
                Listprint_sq(&M);  
                break;  
       default:  
                printf("非法输入\n");  
   }  
       printf("~~~~~~~~~~~~~~~~~~~请输入序号进行操作：\n");  
       printf("1:插入      2:删除      3:退出\n");  
   scanf("%d",&k);  
   }  
   exit(0);  
   return 0;  
} 

 

 

 

 

 

程序运行图：



 

 

 

                                

                                                                         

                                                                                                                                                                 2016_10_13

系列文章

第一章：基础知识

第二章：线性表

第三章：栈和队列 

第四章：字符串和数组

第五章：树和二叉树

第六章：图

第七章：排序算法

前言

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



为什么要学数据结构？

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

如何学习数据结构？

对于初学者来说，数据结构是门概念上比较抽象的课程，不是太容易掌握，需要构思和理解。万事开头难，只要你掌握了学习这门课的方法和技巧，就会变得很容易了。不管学什么，首先应该做好充分的心理准备，建立好自信心，拥有一颗战胜困难的决心，才能不畏惧、不退缩，直至胜利归来。其次，就是最好有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+人生感悟+理财知识+互联网事件等）