零零散散学算法之详解几种数据存储结构

简介: 所谓数据存储结构,就是数据的元素与元素之间在计算机中的一种表示,它的目的是为了解决空间规模问题,或者是通过空间规模问题从而间接地解决时间规模问题。
所谓数据存储结构,就是数据的元素与元素之间在计算机中的一种表示,它的目的是为了解决空间规模问题,或者是通过空间规模问题从而间接地解决时间规模问题。我们知道,随着输入的数据量越来越大,在有限的内存里,不能把这些数据完全的存下来,这就对数据存储结构和设计存储的算法提出了更高的要求。

       本文将介绍几种存储结构,分别为链式结构、树形结构、图结构以及矩阵结构。

第一节 链式存储结构

       所谓链式存储结构,一般就是用一个头指针指向链表的第一个节点,如果你要增加新的存储元素时,只需在已有节点的后面插入新结点即可。

       链表通常有单链表、双链表、循环链表。在这,我只介绍单链表,双链表和循环链表只是单链表的拓展罢了。下图就是一个简单的单链表图示。

单链表的类型描述如下代码:
  1. typedef char DataType;  /***假设结点的数据域类型为字符***/  
  2. typedef struct node{    /***结点类型定义***/  
  3.     DataType data;      /***结点的数据域***/  
  4.     struct node *next;  /***结点的指针域***/  
  5.     }ListNode;  
  6.     typedef ListNode *LinkList;  
  7.     ListNode *p;  
  8.     LinkList head;  
  9. 附注:   
  10.     ① LinkList和ListNode *是不同名字的同一个指针类型(命名的不同是为了概念上更明确)  
  11.     ② LinkList类型的指针变量head表示它是单链表的头指针  
  12.     ③ ListNode *类型的指针变量p表示它是指向某一节点的指针  

下面我们来看单链表的操作:创建节点、增加节点、删除节点、查询、修改。

1.创建节点:声明一个节点并为其申请一段内存空间,此节点有数据域和指针域。
  1. node = (struct List *)malloc(sizeof(struct List));  

2.增加节点:插入节点,分为头插入、尾插入和非头尾插入。
     ①. 在表头插入节点如图

插入头节点的代码如下:
  1. if(p == head)   /***其中p为链表中的某一节点***/  
  2. {  
  3.     struct list *s = NULL;  
  4.     s = (struct list *)malloc(sizeof(struct list)); /***申请空间***/  
  5.     s->DataNumber = data;    /***为节点s的数据域赋值***/  
  6.   
  7.     /***将节点s插入表头***/  
  8.     s->next = p;  
  9.     head = s;  
  10. }  

  ②. 在表尾插入节点如图

插入尾节点的代码如下:
  1. if(p->next == NULL)  /***其中p为链表中的某一节点***/  
  2. {  
  3.     struct list *s = NULL;  
  4.     s = (struct list *)malloc(sizeof(struct list)); /***申请空间***/  
  5.     s->DataNumber = data;    /***为节点s的数据域赋值***/  
  6.       
  7.     /***将节点s插入表尾***/  
  8.     p->next = s;  
  9.     s->next = NULL;  
  10. }  

   ③. 在表中插入非头尾节点如图

插入非头尾节点的代码如下:
  1. struct list *s = NULL;  
  2. s = (struct list *)malloc(sizeof(struct list)); /***申请空间***/  
  3. s->DataNumber = data;    /***为节点s的数据域赋值***/  
  4.   
  5. /***将节点s插入表中***/  
  6. s->next = p; /***其中p为链表中的某一节点***/  
  7. q->next = s; /***其中q为链表中p节点的前一个节点***/  

3.删除节点:分为删除头结点,删除尾节点,删除头尾节点。


①. 删除表头结点如图

删除头结点的代码如下:
  1. if(p == head)   /***p指向链表中的某一节点***/  
  2. {  
  3.     head = p->next;  
  4. }  

②. 删除表尾节点,如图

附注说明:上图中删完尾节点之后,新链表的尾节点下标应为n-1。不过由于作图时只做了尾节点,故用图中的n2节点代替。

删除尾节点的代码如下:

  1. if(p->next == NULL)  /***p指向链表中的某一节点***/  
  2. {  
  3.     q->next = NULL;  /***q指向链表中的p节点的前一节点**/  
  4. }  

③. 删除非头尾节点,如图

删除非头尾节点的代码如下:

  1. q->next = p->next;    /***p指向链表中的某一节点,q指向链表中的p节点的前一节点***/  

4.查询节点:在链表中找到你想要找的那个节点。此操作是根据数据域的内容来完成的。查询只能从表头开始,当要找的节点的数据域内容与当前不相符时,只需让当前节点指向下一结点即可,如此这样,直到找到那个节点。

附注:此操作就不在这用图和代码说明了。


5.修改节点:修改某个节点数据域的内容。首先查询到这个节点,然后对这个节点数据域的内容进行修改。
附注:同上


       ok,链表的几种操作介绍完了,接下来我们来总结一下链表的几个特点。

       链式存储结构的特点:
              1.易插入,易删除。不用移动节点,只需改变节点中指针的指向。
              2.查询速度慢:每进行一次查询,都要从表头开始,速度慢,效率低。

扩展阅读
链表:http://public.whut.edu.cn/comptsci/web/data/512.htm


第二节 树形存储结构

       所谓树形存储结构,就是数据元素与元素之间存在着一对多关系的数据结构。在树形存储结构中,树的根节点没有前驱结点,其余的每个节点有且只有一个前驱结点,除叶子结点没有后续节点外,其他节点的后续节点可以有一个或者多个。

如下图就是一棵简单的树形结构:

       说到树形结构,我们最先想到的就是二叉树。我们常常利用二叉树这种结构来解决一些算法方面的问题,比如堆排序、二分检索等。所以在树形结构这节我只重点详解二叉树结构。那么二叉树到底是怎样的呢?如下图就是一颗简单的二叉树:

附注:有关树的概念以及一些性质在此不做解释,有意者请到百科一览。


二叉树的类型描述如下:

  1. typedef struct tree  
  2. {  
  3.     char data;  
  4.     struct tree * lchild, * rchild; /***左右孩子指针***/  
  5. }tree;  

二叉树的操作:创建节二叉树,创建节点,遍历二叉树,求二叉树的深度。

1.创建二叉树:声明一棵树并为其申请存储空间。

  1. struct tree * T = NULL;  
  2. T = (struct tree *)malloc(sizeof(struct tree));  

2.创建节点:除根节点之外,二叉树的节点有左右节点之分。

创建节点的代码如下:

  1. struct tree * createTree()  
  2. {  
  3.     char NodeData;  
  4.     scanf(" %c", &NodeData);  
  5.     if(NodeData == '#')  
  6.         return NULL;  
  7.     else  
  8.     {  
  9.         struct tree * T = NULL;  
  10.         T = (struct tree *)malloc(sizeof(struct tree));  
  11.         T->data = NodeData;  
  12.         T->lchild = createTree();  
  13.         T->rchild = createTree();  
  14.         return T;  
  15.     }  
  16. }  

3.遍历二叉树:分为先序遍历、中序遍历、后续遍历。

    ①.先序遍历:若二叉树非空,则依次执行如下操作:
                    (1) 访问根结点;
                    (2) 遍历左子树;
                    (3) 遍历右子树。

如图:

先序遍历的代码如下:

  1. void PreTravser(struct tree * T)  
  2. {  
  3.     if(T == NULL)  
  4.         return;  
  5.     else  
  6.     {  
  7.         printf("%c",T->data);  
  8.         PreTravser(T->lchild);  
  9.         PreTravser(T->rchild);  
  10.     }  
  11. }  

②.中序遍历:若二叉树非空,则依次执行如下操作:
                 (1)遍历左子树;
                 (2)访问根结点;
                 (3)遍历右子树。
如图:

中序遍历的代码如下:

  1. void MidTravser(struct tree * T)  
  2. {  
  3.     if(!T)  
  4.     {  
  5.         return;  
  6.     }  
  7.     else  
  8.     {  
  9.         MidTravser(T->lchild);  
  10.         printf("%c",T->data);  
  11.         MidTravser(T->rchild);  
  12.     }  
  13. }  

③.后续遍历:若二叉树非空,则依次执行如下操作:
                 (1)遍历左子树;
                 (2)遍历右子树;
                 (3)访问根结点。

如图:

后续遍历的代码如下:
  1. void PostTravser(struct tree * T)  
  2. {  
  3.     if(!T)  
  4.         return;  
  5.     else  
  6.     {  
  7.         PostTravser(T->lchild);  
  8.         PostTravser(T->rchild);  
  9.         printf("%c->",T->data);  
  10.     }  
  11. }  

4.求二叉树的深度:树中所有结点层次的最大值,也称高度。
二叉树的深度表示如下图:

求二叉树深度的代码如下:
  1. int treeDeepth(struct tree * T)  
  2. {  
  3.     int i, j;  
  4.     if(!T)  
  5.         return 0;  
  6.     else  
  7.     {  
  8.         if(T->lchild)  
  9.             i = treeDeepth(T->lchild);  
  10.         else  
  11.             i = 0;  
  12.           
  13.         if(T->rchild)  
  14.             j = treeDeepth(T->rchild);  
  15.         else  
  16.             j = 0;  
  17.     }  
  18.     return i > j? i+1:j+1;   
  19. }  

好了,二叉树的几种操作介绍完了。

拓展阅读
二叉树:http://student.zjzk.cn/course_ware/data_structure/web/DOWNLOAD/%CA%FD%BE%DD%BD%E1%B9%B9%D3%EB%CB%E3%B7%A82.htm
赫夫曼编码:http://blog.csdn.net/fengchaokobe/article/details/6969217

第三节 图型存储结构
       所谓图形结构,就是数据元素与元素之间的关系是任意的,任意两个元素之间均可相关,即每个节点可能有多个前驱结点和多个后继结点,因此图形结构的存储一般是采用链接的方式。图分为有向图和无向图两种结构,如下图


       通过图,我们可以判断两个点之间是不是具有连通性;通过图,我们还可以计算两个点之间的最小距离是多少;通过图,我们还可以根据不同的要求,寻找不同的合适路径。

1.图的结构有好几种,在实际应用中需根据具体的情况选择合适的结点结构和表结构。常用的有数组结构、邻接表。
   ①.数组结构
   数组结构的类型描述如下:
  1. typedef char VertexType;    /***顶点类型***/  
  2. typedef int EdgeType;   /***边权值类型***/  
  3. #define maxvex 100  /***顶点的最大个数***/  
  4.   
  5. typedef struct  
  6. {  
  7.     VertexType vexs[maxvex];    /***顶点个数***/  
  8.     EdgeType arc[maxvex][maxvex];   /***两顶点构成边的权值***/  
  9. }Mgraph;  
附注:当前图为无向图时,图中某两个顶点VA和VB构成一条边时,其权值可表示为EdgeType arc[VA][VB];当前图为有向图时,图中某两个顶点VA和VB构成一条边时,并且是由VA指向VB,其权值可表示为EdgeType arc[VA][VB],如果是由VB指向VA,其权值可表示为EdgeType arc[VB][VA]。

   ②.邻接表
   邻接表的类型描述如下:
  1. typedef char VertexType;   // 顶点类型  
  2. typedef int EdgeType;     //边权值类型  
  3.   
  4. typedef struct EdgeNode  //边表节点  
  5. {  
  6.    int adjvex;              //邻接点域,存储该顶点对应的下标  
  7.    EdgeType weight;         //用于存储权值  
  8.    struct EdgeNode *next;   //链域,指向下一个邻接点  
  9. }EdgeNode;  
  10.   
  11. typedef struct VertexNode   //顶点表节点  
  12. {  
  13.    VertexType data;       //顶点域,存储顶点信息  
  14.    EdgeNode * firstedge;  //边表头指针  
  15. }VertexNode,AdjList[MAXVEX];  
  16.   
  17. typedef struct  
  18. {  
  19.     AdjList adjList;  
  20.     int numVertexes,numEdges;   //图当前顶点数和边数  
  21. }GraphAdjList;  

2.图的遍历:从图中的某一节点出发访问图中的其余节点,且使每一节点仅被访问一次。图的遍历算法是求解图的连通性问题、拓扑排序和求路径等算法的基础。图的遍历分为深度优先遍历和广度优先遍历,且它们对无向图和有向图均适用。

   ①. 深度优先遍历
   定义说明:假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点V为初始出发点,则深度优先遍历可定义如下:首先访问出发点V,并将其标记为已访问过;然后依次从V出发搜索v的每个邻接点W。若W未曾访问过,则以W为新的出发点继续进行深度优先遍历,直至图中所有和源点V有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点,则另选一个尚未访问的顶点作为新的源点重复上述过程,直至图中所有顶点均已被访问为止。

深度遍历过程如下图:


②. 广度优先遍历
   定义说明:假设从图中某顶点V出发,在访问了V之后一次访问V的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问,直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有顶点未被访问,则另选图中一个未曾被访问的顶点作为起始点,重复上述过程,直至图中所有顶点都被访问到为止。换句话说,广度优先遍历图的过程是以V为起点,由近至远,依次访问和V有路径相同且路径长度为1,2,...的顶点。


广度遍历过程如下图:


扩展阅读
最小生成树:Prim算法,Kruskal算法
最短路径:Dijkstra算法,Floyd算法
相关文章
|
7月前
|
负载均衡 算法 应用服务中间件
面试题:Nginx有哪些负载均衡算法?Nginx位于七层网络结构中的哪一层?
字节跳动面试题:Nginx有哪些负载均衡算法?Nginx位于七层网络结构中的哪一层?
135 0
|
1月前
|
算法 测试技术 开发者
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗;代码审查通过检查源代码发现潜在问题,提高代码质量和团队协作效率。本文介绍了一些实用的技巧和工具,帮助开发者提升开发效率。
39 3
|
2月前
|
存储 缓存 算法
如何通过优化算法和代码结构来提升易语言程序的执行效率?
如何通过优化算法和代码结构来提升易语言程序的执行效率?
|
6月前
|
存储 算法
【数据结构和算法】--- 二叉树(4)--二叉树链式结构的实现(2)
【数据结构和算法】--- 二叉树(4)--二叉树链式结构的实现(2)
40 0
|
6月前
|
存储 算法 Linux
【数据结构和算法】---二叉树(1)--树概念及结构
【数据结构和算法】---二叉树(1)--树概念及结构
53 0
|
6月前
|
存储 算法
【数据结构和算法】--队列的特殊结构-循环队列
【数据结构和算法】--队列的特殊结构-循环队列
34 0
|
7月前
|
存储 监控 NoSQL
Redis处理大量数据主要依赖于其内存存储结构、高效的数据结构和算法,以及一系列的优化策略
【5月更文挑战第15天】Redis处理大量数据依赖内存存储、高效数据结构和优化策略。选择合适的数据结构、利用批量操作减少网络开销、控制批量大小、使用Redis Cluster进行分布式存储、优化内存使用及监控调优是关键。通过这些方法,Redis能有效处理大量数据并保持高性能。
99 1
|
4月前
|
机器学习/深度学习 算法 文件存储
【博士每天一篇文献-算法】 PNN网络启发的神经网络结构搜索算法Progressive neural architecture search
本文提出了一种名为渐进式神经架构搜索(Progressive Neural Architecture Search, PNAS)的方法,它使用顺序模型优化策略和替代模型来逐步搜索并优化卷积神经网络结构,从而提高了搜索效率并减少了训练成本。
58 9
|
4月前
|
存储 缓存 算法
深入解析B树:数据结构、存储结构与算法优势
深入解析B树:数据结构、存储结构与算法优势
|
5月前
|
存储 算法 Java
Java面试题:解释JVM的内存结构,并描述堆、栈、方法区在内存结构中的角色和作用,Java中的多线程是如何实现的,Java垃圾回收机制的基本原理,并讨论常见的垃圾回收算法
Java面试题:解释JVM的内存结构,并描述堆、栈、方法区在内存结构中的角色和作用,Java中的多线程是如何实现的,Java垃圾回收机制的基本原理,并讨论常见的垃圾回收算法
73 0