文档章节

C语言数据结构+数据库+操作系统

chenxiao60
 chenxiao60
发布于 2016/06/08 20:51
字数 3203
阅读 155
收藏 4

http://cv.qiaobutang.com/post/55c419b20cf2009bd4607795

第二部分是专业相关的C ,数据库,操作系统,数据结构。

http://c.biancheng.net/cpp/u/shuju/

数据(Data)是信息的载体,它能够被计算机识别、存储和加工处理。它是计算机程序加工的原料,应用程序处理各种各样的数据。计算机科学中,所谓数据就是计算机加工处理的对象,它可以是数值数据,也可以是非数值数据。数值数据是一些整数、实数或复数,主要用于工程计算、科学计算和商务处理等;非数值数据包括字符、文字、图形、图像、语音等。

数据结构(Data Structure)是指互相之间存在着一种或多种关系的数据元素的集合。在任何问题中,数据元素之间都不会是孤立的,在它们之间都存在着这样或那样的关系,这种数据元素之间的关系称为结构。根据数据元素间关系的不同特性,通常有下列四类基本的结构:

  1. 集合结构。在集合结构中,数据元素间的关系是“属于同一个集合”。集合是元素 关系极为松散的一种结构。
  2. 线性结构。该结构的数据元素之间存在着一对一的关系。
  3. 树型结构。该结构的数据元素之间存在着一对多的关系。
  4. 图形结构。该结构的数据元素之间存在着多对多的关系,图形结构也称作网状结构。

 数据的存储结构可采用顺序存储或链式存储的方法。

顺序存储方法是把逻辑上相邻的元素存储在物理位置相邻的存储单元中,由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法,通常借助于程序设计语言中的数组来实现。

链式存储方法对逻辑上相邻的元素不要求其物理位置相邻,元素间的逻辑关系通过附设的指针字段来表示,由此得到的存储表示称为链式存储结构,链式存储结构通常借助于程序设计语言中的指针类型来实现。

除了通常采用的顺序存储方法和链式存储方法外,有时为了查找的方便还采用索引存储方法和散列存储方法。

 

 数据类型

在高级程序设计语言中,数据类型可分为两类:一类是原子类型,另一类则是结构类型。原子类型的值是不可分解的。如C 语言中整型、字符型、浮点型、双精度型等基本类型,分别用保留字int、char、float、double 标识。而结构类型的值是由若干成分按某种结构组成的,因此是可分解的,并且它的成分可以是非结构的,也可以是结构的。例如,数组的值由若干分量组,每个分量可以是整数,也可以是数组等。在某种意义上,数据结构可以看成是“一组具有相同结构的值”,而数据类型则可被看成是由一种数据结构和定义在其上的一组操作所组成的。

⒈时间复杂度

一个程序的时间复杂度(Time complexity)是指程序运行从开始到结束所需要的时间。

一个算法是由控制结构和原操作构成的,其执行时间取决于两者的综合效果。为了便于比较同一问题的不同的算法,通常的做法是:从算法中选取一种对于所研究的问题来说基本运算的原操作,以该原操作重复执行的次数作为算法的时间度量。一般情况下,算法中原操作重复执行的次数是规模n 的某个函数T(n)。许多时候要精确地计算T(n)是困难的,我们引入渐进时间复杂度在数量上估计一个算法的执行时间,也能够达到分析算法的目的。

定义(大Ο记号):如果存在两个正常数c 和n0,使得对所有的n,n≥n0,有:

f(n) ≤ cg(n)

则有:

f(n) = Ο(g(n))


例如,一个程序的实际执行时间为T(n)=2.7n3+3.8n2+5.3。则T(n)=Ο(n3)。使用大Ο记号表示的算法的时间复杂度,称为算法的渐进时间复杂度(Asymptotic Complexity)。

通常用Ο(1)表示常数计算时间。常见的渐进时间复杂度有:

Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<Ο(2n)

 

⒉空间复杂度


一个程序的空间复杂度(Space complexity)是指程序运行从开始到结束所需的存储量。

程序的一次运行是针对所求解的问题的某一特定实例而言的。例如,求解排序问题的排序算法的每次执行是对一组特定个数的元素进行排序。对该组元素的排序是排序问题的一个实例。元素个数可视为该实例的特征。程序运行所需的存储空间包括以下两部分:

⑴固定部分。这部分空间与所处理数据的大小和个数无关,或者称与问题的实例的特征无关。主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。

⑵可变部分。这部分空间大小与算法在某次执行中处理的特定数据的大小和规模有关。例如100 个数据元素的排序算法与1000 个数据元素的排序算法所需的存储空间显然是不同的。

线性表的定义


线性表是一种线性结构。线性结构的特点是数据元素之间是一种线性关系,数据元素“一个接一个的排列”。在一个线性表中数据元素的类型是相同的,或者说线性表是由同一类型的数据元素构成的线性结构。在实际问题中线性表的例子是很多的,如学生情况信息表是一个线性表:表中数据元素的类型为学生类型; 一个字符串也是一个线性表:表中数据元素的类型为字符型,等等。

综上所述,线性表定义如下:线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列,通常记为:

(a1,a2,… ai-1,ai,ai+1,…an)

其中n为表长, n=0 时称为空表。
表中相邻元素之间存在着顺序关系。将ai-1 称为ai 的直接前趋,ai+1 称为ai 的直接后继。就是说:对于ai,当i=2,...,n 时,有且仅有一个直接前趋ai-1.,当i=1,2,...,n-1 时,有且仅有一个直接后继ai+1,而a1 是表中第一个元素,它没有前趋,an 是最后一个元素无后继。

 线性表的基本操作


在第一章中提到,数据结构的运算是定义在逻辑结构层次上的,而运算的具体实现是建立在存储结构上的,因此下面定义的线性表的基本运算作为逻辑结构的一部分,每一个操作的具体实现只有在确定了线性表的存储结构之后才能完成。

线性表上的基本操作有:

⑴ 线性表初始化:Init_List(L)
初始条件:表L不存在操作结果:构造一个空的线性表

⑵ 求线性表的长度:Length_List(L)
初始条件:表L存在
操作结果:返回线性表中的所含元素的个数

⑶ 取表元:Get_List(L,i)
初始条件:表L存在且1<=i<=Length_List(L)
操作结果:返回线性表L中的第i个元素的值或地址

⑷ 按值查找:Locate_List(L,x),x是给定的一个数据元素。
初始条件:线性表L存在
操作结果:在表L中查找值为x的数据元素,其结果返回在L中首次出现的值为x的那个元素的序号或地址,称为查找成功; 否则,在L中未找到值为x的数据元素,返回一特殊值表示查找失败。

⑸ 插入操作:Insert_List(L,i,x)
初始条件:线性表L存在,插入位置正确(1<=i<=n+1,n为插入前的表长)。
操作结果:在线性表L的第i 个位置上插入一个值为x 的新元素,这样使原序号为i , i+1, ... , n 的数据元素的序号变为i+1,i+2, ... , n+1,插入后表长=原表长+1。

⑹ 删除操作:Delete_List(L,i)
初始条件:线性表L存在,1<=i<=n。
操作结果:在线性表L中删除序号为i的数据元素,删除后使序号为i+1, i+2,..., n的元素变为序号为i, i+1,...,n-1,新表长=原表长-1。

线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素,用这种存储形式存储的线性表称其为顺序表。因为内存中的地址空间是线性的,因此,用物理上的相邻实现数据元素之间的逻辑相邻关系是既简单,又自然的。如图2.1 所示。

设a1的存储地址为Loc(a1),每个数据元素占d个存储地址,则第i个数据元素的地址为:

Loc(ai)=Loc(a1)+(i-1)*d 1<=i<=n

单链表


链表是通过一组任意的存储单元来存储线性表中的数据元素的,那么怎样表示出数据元素之间的线性关系呢?为建立起数据元素之间的线性关系,对每个数据元素ai,除了存放数据元素的自身的信息ai 之外,还需要和ai一起存放其后继ai+1 所在的存贮单元的地址,这两部分信息组成一个“结点”,结点的结构如图2.6 所示,每个元素都如此。存放数据元素信息的称为数据域,存放其后继地址的称为指针域。因此n个元素的线性表通过每个结点的指针域拉成了一个“链子”,称之为链表。因为每个结点中只有一个指向后继的指针,所以称其为单链表。

链表是由一个个结点构成的,结点定义如下:
typedef struct node
{ datatype data;
struct node *next;
} LNode,*LinkList;

定义头指针变量:
LinkList H;

 

在链表的头部插入结点建立单链表

链表与顺序表不同,它是一种动态管理的存储结构,链表中的每个结点占用的存储空间不是预先分配,而是运行时系统根据需求而生成的,因此建立单链表从空表开始,每读入一个数据元素则申请一个结点,然后插在链表的头部,如图2.10 展现了线性表:(25,45,18,76,29)之链表的建立过程,因为是在链表的头部插入,读入数据的顺序和线性表中的逻辑顺序是相反的。

在单循环链表上的操作基本上与非循环链表相同,只是将原来判断指针是否为NULL变为是否是头指针而已,没有其它较大的变化。

下面先请看图2.22 ,在图2.22中,规模较大的结构数组sd[MAXSIZE] 中有两个链表:

其中链表SL是一个带头结点的单链表,表示了线性表(a1, a2, a3, a4, a5),而另一个单链表AV是将当前sd 中的空结点组成的链表。

 

© 著作权归作者所有

共有 人打赏支持
chenxiao60
粉丝 9
博文 18
码字总数 23326
作品 0
南京
私信 提问
我们要分方向了,亲们~

我现在在大一,学的是软件工程专业。 这个礼拜就要分方向了,在这里咨询一下大家,给我提一些好的建议。 我们学校一共十个方向,有几个我定了不选了,所以我就说剩下的好了~ ♥ A:软件开发与...

溪啊溪
2013/05/07
2.1K
27
业余爱好者的C程序设计学习之路

我学习和工作的方向都是化工,和 IT 专业一点边都不搭,属于程序设计爱好者一类。坚持了很多年了,谈谈我的认识。 一、为什么是C 汇编太难,直接下手会吓死宝宝的。 basic 不能考虑,因为“对...

四彩
2016/02/04
107
2
求前辈教教我!!!!!

我现在学了很多课程,譬如java、javaee、数据库、计算机原理、操作系统、网络、数据结构、C语言、c++等等,该怎么去总结,写博客,还是怎么样?做一个项目?求前辈教教我

56654455
2015/11/20
215
2
十一年C/C++编程老手给小白学习C语言的句句肺腑之言,令人深思

我相信,这可能是很多朋友的问题,我以前也有这样的感觉,编程编到一定的时候,发现能力到了瓶颈,既不深,也不扎实,半吊子。比如:你长期地使用Java和.NET ,这些有虚拟机的语言对于开发便...

小辰GG
2017/12/04
0
0
现在想去学安卓开发,哪些课程需要需要掌握:C语言程序设计、数据库、数据结构、Java SE、Java EE、HTML5、计算机操作系统,网络等等、哪些需要熟悉掌握的,对开发安卓来说

现在想去学安卓开发,哪些课程需要需要掌握:C语言程序设计、数据库、数据结构、Java SE、Java EE、HTML5、计算机操作系统,网络等等、哪些需要熟悉掌握的,对开发安卓来说

56654455
2015/11/12
446
6

没有更多内容

加载失败,请刷新页面

加载更多

解析JQuery中each方法的使用

each() 方法规定为每个匹配元素规定运行的函数。写的十分的全面细致,具有一定的参考价值,对此有需要的朋友可以参考学习下。如有不足之处,欢迎批评指正。 概述: each() 方法规定为每个匹配...

前端攻城小牛
4分钟前
0
0
深入解析Vue开发动态刷新Echarts组件的教程

需求背景:dashboard作为目前企业中后台产品的“门面”,如何更加实时、高效、炫酷的对统计数据进行展示,是值得前端开发工程师和UI设计师共同思考的一个问题。今天就从0开始,封装一个动态渲...

peakedness丶
17分钟前
2
0
memcached

memcached 为了避免内存碎片化(传统的内存管理方式是,使用完通过malloc分配的内存后通过free来回收内存,这种方式容易产生内存碎片并降低操作系统对内存的管理效率),采用了 slab allocatio...

Cobbage
17分钟前
2
0
keepalived的介绍及配置高可用集群

12月19日任务 18.1 集群介绍 18.2 keepalived介绍 18.3/18.4/18.5 用keepalived配置高可用集群 集群介绍 根据功能划分为2类:高可用和负载均衡 高可用集群:通常为两台服务器,一台工作,另外...

robertt15
18分钟前
5
0
WiFi攻击的三种方式

导读 WiFi的安全问题已经引起了不少的使用者重视,甚至已经出现草木皆兵的现象。那么黑客到底是如何做到绕过身份验证来获取WiFi使用权的呢?主要有以下三种方式,其中最后一种方式十分简单。 ...

问题终结者
32分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部