你的位置:首页 > ASP.net教程

[ASP.net教程]C# 数据结构 基础 论述


 

 

问题:

信息世界中,计算机是加工处理的信息的载体,在这个过程中面临着三个问题:

1.如何方便高效的组织数据

2.如何在计算机中存储数据(内存和外存)

3.如何对存储的数据进行高效的操作

 

目的:

我们都知道,我们都会表述一件事,老板交代你一件事情,你要陈述给你的员工,让他们明白你的意思,有些人可能简要的几句话

就把事情表达清楚,可是有的人说了一大堆才明白他说什么,这个比喻不太恰当,同样在面对同一个程序的时候我们就可以出现两

种程序:有的人写出来的程序效率很高,有的人却用复杂的方法来解决一个简单的问题。

简而言之目的有三个:

1.形成自己数据结构知识库

2.提高程序设计水平

3.提供程序设计者的基本技能

 

 

 

基本概念和术语

1.数据(Data):能被计算机识别的信息的载体,数值数据,声音,文字等等

2.数据元素(Data Element)和数据项(Data Item)DE:数据的实体 DI:数据的属性 最常见的是数据表的一条记录(用户) 和

字段(用户名,密码,性别等等)

3.数据对象(Data Object)性质相同的数据元素的集合 例如:{0,1,2,3,4} , {a,b,c,d} , {用户A,用户B,用户C….}

4.数据类型(Data Type)int,string等等

 

5.数据结构(Data Structure) 在数据集合的基础上组织起来的有关系数据结构,通常有四类节本数据结构:A集合 B线性结构 C树形结

构 D 网状结构或者图形结构

 

image

 

A Set   B Linear Structure      C Tree Structure     D Graphic Structure

数据结构记做 DS(Data Structure) 是一个二元组 DS=(D,R) D是有限的数据元素集合 R 是元素之间关系

 

 

通过例子理解后三种数据结构:

 

B 线性数据结构 学生信息表

一行:数据元素 列:数据项  元素与元素的关系:1对1

 

 

image

 

 

C 树形结构 家谱

 

 

image

 

 

这个不多解释。节点:数据元素  关系:一对多 或者 多对一

 

 

D 图形结构

 

 

image

 

 

图形结构:交通图 元素:城市 关系多对多

 

数据结构

包括数据的逻辑结构和数据的物理结构,物理结构也叫存储结构,我们讨论数据结构的目的是为了在计算机中实

现对它的操作,还要在计算机表示和存储,数据存储结构分为:顺序存储结构和链式存储结构,顺序存储结构:是把相邻

数据存储在物理上相同存储单元中,在C#中用数组来实现顺序存储,最常见的是 数组;链式存储,Node+Reference

Domain 在.net 中内存栈区和堆区,栈顺序存储,对应的对象在堆中,则指向了堆中的地址。

 

算法

算法与数据结构关系非常密切。

算法的特性:1有穷性  2确定性  3输出和输出 4能行性

评定标准:1正确性  2可读性 3健壮性  4运行时间(时间复杂度Time Complexity)  5占用空间(空间复杂度Space Complexity)

影响性能因素:1.硬件条件  2.实现计算机的语言(语言越高级 效率越低) 3编程语言的编译器和解释器 4 操作系统

 

算法的时间复杂度

算法是由控制结构和原操作构成的,其执行的时间取决于二者的综合效果。为了便于比较同一问题的不同算法,通常把算法中基本操作

重复执行的次数(频度)作为算法的时间复杂度。T(n)=0(f(n)),如果一个算法没有循环语句,那么算法中的节本操作的执行频率与问题

无关,记做0(1),也成为常数阶,如果算法只有一重循环纳闷算法执行频率与问题规模N呈线性增大关系,记做 0(n),也叫线性阶

常用的还有平方阶乘0(n*n) 立方阶0(n*n*n)等等

例 1:x=n;

y=0;

while(y<x)

{

y=y+1; // T(n) 时间复杂度

}

 这是一个一重循环,循环次数为N 时间复杂度为线性:记做T(n)=0(0)

例 2:for(i=1;i<n;i++)

{

  for(j=0;j<n;j++)

{

   A[i][j]=i*j; //T(n) 时间复杂度

}

}

双重循环 外层循环的循环次数是 N 内层for循环次数为 N 时间复杂度 T(n)=0(n*n);

 

例3 : x=n;

y=0;

while(x>=(y+1)*(y+1))

{

y=y+1; //T(n) 时间复杂度

}

 

一重循环 while 的循环次数为 根号 N 所以时间复杂度 T(n)=0(根号N)

 

例4 :for(i=0;i<m;i++)

{

for(j=0;j<t;j++)

{

    for(k=0;k<n;k++)

    {

      c[i][j]=c[i][j]+a[i][k]*b[k][j];//T(n) 时间复杂度 被执行次数

    }

}

}

三重循环:时间复杂度 T(n)=0(m*t*j);

 

数学基本概念

想到算法就不得不想到数学,集合表示法:穷举法S={0,5,8,9} 描述法:S={x|x是偶数,且0<X<10};

集合的特点:确定性,互异性,无序性

1000个不同编码需要多少位?⌈log21000⌉=10 位

10 位可以表示多少个不同的编码? 10 位可以产生 1024 个不同的可用编码

经典的例子:折半算法 打个不靠谱的比喻啊 网线坏了 不知道那个地方坏了 网线为100米(最大了)要查多

少次,才能找到故障点,使用折半算法(也叫二分查找法)log2 100 次

指数和对数是基本概念也是相互转化的过程。

 

C# 知识点:接口 Icomparable,IEnumerable,IEnumberator,ICollection,IDictionary,IList

,装箱拆箱,泛型

 

未完待续……