数据结构解析与归纳

  • 更新时间: 2017-12-15
  • 来源: 原创或网络
  • 浏览数: 57次
  • 字数: 24926
  • 发表评论

在计算机科学中,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象(数据元素)以及它们之间的关系和运算等的学科,而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。

“数据结构”作为一门独立的课程在国外是从1968年才开始设立的。 1968年美国唐·欧·克努特教授开创了数据结构的最初体系,他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。“数据结构”在计算机科学中是一门综合性的专业基础课。数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计(特别是非数值性程序设计)的基础,而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。

1 常用的数据结构

数组 (Array)
在程序设计中,为了处理方便, 把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。在C语言中, 数组属于构造数据类型。一个数组可以分解为多个数组元素,这些数组元素可以是基本数据类型或是构造类型。因此按数组元素的类型不同,数组又可分为数值数组、字符数组、指针数组、结构数组等各种类别。

栈 (Stack)
是只能在某一端插入和删除的特殊线性表。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。

队列 (Queue)
一种特殊的线性表,它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为队空。

链表 (Linked List)
是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。

树 (Tree)
是包含n(n>0)个结点的有穷集合K,且在K中定义了一个关系N,N满足以下条件:
1)有且仅有一个结点K0,他对于关系N来说没有前驱,称K0为树的根结点。简称为根(root)。

2)除K0外,K中的每个结点,对于关系N来说有且仅有一个前驱。
3)K 中各结点,对关系N来说可以有m个后继(m>=0)。

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

堆 (Heap)
在计算机科学中,堆是一种特殊的树形数据结构,每个结点都有一个值。通常我们所说的堆的数据结构,是指二叉堆。堆的特点是根结点的值最小(或最大),且根结点的两个子树也是一个堆。

散列表 (Hash)
若结构中存在关键字和K相等的记录,则该记录必定在f(K)的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function),按这个思想建立的表为散列表。

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

2 数据结构表

Array, ArrayList,List,IList,ICollection, Stack, Queue, HashTable, Dictionary, IQueryable, IEnumerable等进行详述。

数据结构解析与归纳,by 5lulu.com

Collection(集合)

Collection是数据记录集合,编写代码过程中,常常需要合适的容器保存临时数据,方便修改和查找,如何选取合适的数据容器,关键在于将执行的数据操作以及数据记录是否大量。

数据结构解析与归纳,by 5lulu.com

Array(数组)

特征

1. 固定大小,数组的大小是初始化时决定无法修改的数值。

2. 强类型,存储数据元素类型必须在初始化时指定,因此在运行时,不需要耗费额外的时间来定义数组类型,能够大大提升运行效率。

3. 可使用Foreach关键字实现数组迭代和查找。

因为数组大小是固定的,且是强类型数据结构,因此在运行时只占用很少的内存,运行时效率很高。

数据结构解析与归纳,by 5lulu.com

ArrayList

1. ArrayList 没有固定的长度,容量可动态增加,可应用于开发人员无法确定数组元素个数等场景,当然这种情况下,在定义结构体的时候会非常耗时。

2. ArrayList 不是强类型,ArrayList中不同元素类型可以不相同,并且需要在运行时根据实际的输入来确定元素类型。因此在运行时消耗内存较多。

3. 可使用Froeach 关键字操作ArrayList。

数据结构解析与归纳,by 5lulu.com

ArrayList支持String,int,以及十进制小数类型。

HashTable(哈希表)

HashTable是一种定义关键字的数据结构体,使用哈希表查找数据非常方便,哈希表既不是强类型也不固定大小限制。

数据结构解析与归纳,by 5lulu.com

Stack

栈是最典型的数据结构,栈具有优先级划分的数据结构,栈为每个内容项定义优先级,表示每个Item入栈和出栈的优先顺序。因此操作栈中的数据,需要先将数据push 到栈的顶部,需要删除元素必须变成栈顶部,即要遵守后进先出(LIFO)的原则。

栈与哈希表一样既不是强类型也不限制元素个数。

数据结构解析与归纳,by 5lulu.com

Push 操作

    //Stack is LIFO: Last in First Out
    System.Collections.Stack objStackPush = new System.Collections.Stack();

    //By Push method you can insert item at the top of the stack
    objStackPush.Push("Mahsa");
    objStackPush.Push("Hassankashi");
    this.lblPop.Text = "";
    this.ListBoxStack.DataSource = objStackPush.ToArray();
    this.ListBoxStack.DataBind();  

Pop操作

    System.Collections.Stack objStackPop = new System.Collections.Stack();

    objStackPop.Push("Mahsa");
    objStackPop.Push("Hassankashi");

    //By Pop method you can remove item from the top of the stack --> Last in First in
    this.lblPop.Text = objStackPop.Pop().ToString();

    this.ListBoxStack.DataSource = objStackPop.ToArray();
    this.ListBoxStack.DataBind();  

Queue

Queue同栈一样也是具有优先级定义的结构体,遵循的规则是先进先出(FIFO),既不是强类型也不具有固定的大小限制。

数据结构解析与归纳,by 5lulu.com

入队操作

    //Queue is FIFO: First in First Out
    System.Collections.Queue objQueue = new System.Collections.Queue();

    //By Enqueue method you can insert item at the END of the Queue
    objQueue.Enqueue("Mahsa");
    objQueue.Enqueue("Hassankashi");
    objQueue.Enqueue("Cosmic");
    objQueue.Enqueue("Verse");

    this.lblQueue.Text = "";
    this.ListBoxQueue.DataSource = objQueue.ToArray();
    this.ListBoxQueue.DataBind();
出队操作
    System.Collections.Queue objQueue = new System.Collections.Queue();

    objQueue.Enqueue("Mahsa");
    objQueue.Enqueue("Hassankashi");
    objQueue.Enqueue("Cosmic");
    objQueue.Enqueue("Verse");

    //By Dequeue method you can remove item from the BEGINING of the Queue --> First in First out FIFO
    this.lblQueue.Text=objQueue.Dequeue().ToString();

    this.ListBoxQueue.DataSource = objQueue.ToArray();
    this.ListBoxQueue.DataBind();  

入队操作

    System.Collections.Queue objQueue = new System.Collections.Queue();

    objQueue.Enqueue("Mahsa");
    objQueue.Enqueue("Hassankashi");
    objQueue.Enqueue("Cosmic");
    objQueue.Enqueue("Verse");

    //By Dequeue method you can remove item from the BEGINING of the Queue --> First in First out FIFO
    this.lblQueue.Text=objQueue.Dequeue().ToString();

    this.ListBoxQueue.DataSource = objQueue.ToArray();
    this.ListBoxQueue.DataBind();  

List

什么情况下需要使用List?

1. List长度可不固定

2. 当数据为通用类型,List是强类型,List中元素类型不需要等到运行时来确定,这种特性使得List 运行时效率非常高。

3. 可使用Foreach关键字。

因为List不需要设定固定的大小,List灵活度高,且效率高常用于开发过程中。

    //Like Array is Strong Type
    //Like ArrayList with No Dimension
    System.Collections.Generic.ListstrList = new List();

    strList.Add("Mahsa");
    strList.Add("Hassankashi");
    strList.Add("Cosmic");
    strList.Add("Verse");

    this.ListBoxListGeneric.DataSource = strList;
    this.ListBoxListGeneric.DataBind();

    System.Text.StringBuilder str = new System.Text.StringBuilder();

    foreach (var item in strList)
    {
    str.Append(" , " + item);
    }
    this.lblList.Text = str.ToString();
数据结构解析与归纳,by 5lulu.com

IList

IList 继承了List,包含多种方法的List接口。如果你无法判断代码改动的可能性,可以使用IList接口,减少模块之间的依赖性。IList是接口因此无法被实例化,所以必须使用List来初始化。

    //Ilist can not be instantiate from Ilist , so it should be instantiate from List
    System.Collections.Generic.IListstrIList = new List();

    strIList.Add("Mahsa");
    strIList.Add("Hassankashi");
    strIList.Add("Cosmic");
    strIList.Add("Verse");

    this.ListBoxListGeneric.DataSource = strIList;
    this.ListBoxListGeneric.DataBind();

    System.Text.StringBuilder str = new System.Text.StringBuilder();

    foreach (var item in strIList)
    {
    str.Append(" , " + item);
    }
    this.lblList.Text = str.ToString();  

我们一起了解一下具体的类和接口之间的区别 

1. 具体类可继承其他类,并实现一个或多个接口。

2. 在内部类中可以定义变量并赋值,接口中不允许此操作。

3. 具体类可包含构造函数,而接口中不能定义构造函数

4. 抽象类中可包含访问修饰符如public,private等,接口中不能包含。


数据结构解析与归纳,by 5lulu.com

    //IEnumerable can not be instantiate from Enumerable , so it should be instantiate from List
    System.Collections.Generic.IEnumerableempIEnumerable = new List{
    new Employee { ID = 1001, Name="Mahsa"},
    new Employee { ID = 1002, Name = "Hassankashi" },
    new Employee { ID = 1003, Name = "CosmicVerse" },
    new Employee { ID = 1004, Name = "Technical" }
    };

    this.GridViewIEnumerable.DataSource = empIEnumerable;
    this.GridViewIEnumerable.DataBind();

    System.Text.StringBuilder str = new System.Text.StringBuilder();

    foreach (Employee item in empIEnumerable)
    {
    str.Append(" , " + item.ID +"-"+item.Name);
    }
    this.lblIEnumerable.Text = str.ToString(); 

IEnumerable

IEnumerable常用于遍历集合元素,但是无法修改(删除或添加)数据,使用IEnumberable 会从服务器端将所有数据拷贝到客户端,并进行一定的过滤,如果服务器端有大量数据会造成内存负载超重。

数据结构解析与归纳,by 5lulu.com

    //IEnumerable can not be instantiate from Enumerable , so it should be instantiate from List
    System.Collections.Generic.IEnumerableempIEnumerable = new List{
    new Employee { ID = 1001, Name="Mahsa"},
    new Employee { ID = 1002, Name = "Hassankashi" },
    new Employee { ID = 1003, Name = "CosmicVerse" },
    new Employee { ID = 1004, Name = "Technical" }
    };


    this.GridViewIEnumerable.DataSource = empIEnumerable;
    this.GridViewIEnumerable.DataBind();

    System.Text.StringBuilder str = new System.Text.StringBuilder();

    foreach (Employee item in empIEnumerable)
    {
    str.Append(" , " + item.ID +"-"+item.Name);
    }
    this.lblIEnumerable.Text = str.ToString();

IQueryable

IQueryable与IEnumberable不同的是,当从服务器端加载过量的数据,IQueryable会自动减少应用负载。IQueryable可保证大数据量时应用程序的高性能。IQueryable会先过滤数据,然后发送给客户端。
    DataAccessEntities ctx = new DataAccessEntities();
    var ctx = new DataAccessEntities();  

数据结构解析与归纳,by 5lulu.com



数据结构解析与归纳,by 5lulu.com


SQL Profiler

如何追踪查询语句生成TSQL,生成需要的数据结构体:

Step 1:
  1. Start -> MS SQL Server 2008 -> Performance Tools -> SQL Server Profiler
数据结构解析与归纳,by 5lulu.com
Step 2:
  1. SQL Server Profiler -> File -> New Trace

数据结构解析与归纳,by 5lulu.com

Step 3:

输入连接数据库的用户名和密码

数据结构解析与归纳,by 5lulu.com

Step 4:
  1. General (Tab) -> Use the Template: Standard

数据结构解析与归纳,by 5lulu.com

Step 5:
    Event Selection (Tab) -> Event : TSQL -> Select : SQL-BatchCompleted | Select Show all Columns

    Press Column Filter -> Database Name: Like: "DataAccess"  

运行

数据结构解析与归纳,by 5lulu.com

Step 6:

查看结果

数据结构解析与归纳,by 5lulu.com

Step 7:
生成 IEnumerable数据 
    SELECT
    [Extent1].[ID] AS [ID],
    [Extent1].[Name] AS [Name],
    [Extent1].[Age] AS [Age]
    FROM [dbo].[Employee] AS [Extent1]  

数据结构解析与归纳,by 5lulu.com

生成 IQueryable :
    SELECT
    [Extent1].[ID] AS [ID],
    [Extent1].[Name] AS [Name],
    [Extent1].[Age] AS [Age]
    FROM [dbo].[Employee] AS [Extent1]
    WHERE 1 = [Extent1].[ID]  

数据结构解析与归纳,by 5lulu.com

ICollection 继承了IEnumberable,但是IEnumberable是基于索引的,ICollection不基于索引。

数据结构解析与归纳,by 5lulu.com

Stack Generic

入栈:

    //Stack is LIFO: Last in First Out
    //Here is for Push Stack in Generic
    //System.Collections.Stack objStackPush = new System.Collections.Stack();
    //Stackcan be instantiated from Stack

    System.Collections.Generic.StackobjStackPush = new System.Collections.Generic.Stack();

    objStackPush.Push(1);
    objStackPush.Push(2);

    this.lblPopGeneric.Text = "";
    this.ListBoxStackGeneric.DataSource = objStackPush.ToArray();
    this.ListBoxStackGeneric.DataBind();
Queue Generic

入队:

    //Stack is LIFO: Last in First Out
    //Here is for Pop Stack in Generic
    //System.Collections.Stack objStackPop = new System.Collections.Stack();
    //Stackcan be instantiated from Stack

    System.Collections.Generic.StackobjStackPop = new System.Collections.Generic.Stack();

    objStackPop.Push(1);
    objStackPop.Push(2);

    this.lblPop.Text = objStackPop.Pop().ToString();
    this.ListBoxStack.DataSource = objStackPop.ToArray();
    this.ListBoxStack.DataBind();  

出队:

    //Queue is FIFO: First in First Out
    //Here is for Enqueue Queue in Generic
    //System.Collections.Queue objQueue = new System.Collections.Queue();
    //Queuecan be instantiated from Queue
    System.Collections.Generic.QueueobjQueue = new System.Collections.Generic.Queue();
    objQueue.Enqueue(1);
    objQueue.Enqueue(2);

    this.lblQueue.Text = "";

    this.ListBoxQueue.DataSource = objQueue.ToArray();
    this.ListBoxQueue.DataBind();

Dictionary 及 IDictionary

Dictionary 可通用,而哈希表不是通用的。Dictionary定义 。IDictionary是Dictionary的接口,如果在后期开发中需要大量修改,建议使用IDictionary。
    System.Collections.Generic.Dictionary objDictionary = new Dictionary();

    objDictionary.Add(1001, "Mahsa");
    objDictionary.Add(1002, "Hassankashi");
    objDictionary.Add(1003, "Cosmicverse");

    string str = objDictionary[1002];

    this.ListBoxDictionary.DataSource = objDictionary;
    this.ListBoxDictionary.DataBind();  
我来评分 :6
0

转载注明:转自5lulu技术库

本站遵循:署名-非商业性使用-禁止演绎 3.0 共享协议