文档章节

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

chenxiao60
 chenxiao60
发布于 2016/06/08 20:51
字数 3203
阅读 150
收藏 4
点赞 0
评论 0

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
南京
求前辈教教我!!!!!

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

给我一分钟灵感 ⋅ 2015/11/20 ⋅ 2

业余爱好者的C程序设计学习之路

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

四彩 ⋅ 2016/02/04 ⋅ 2

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

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

小辰GG ⋅ 2017/12/04 ⋅ 0

使用c实现简单的rpc

RPC简介 RPC(Remote Procedure Call)——远程过程调用,它是一种通过网络从远程计算机程序上请求服务,而不需要了解底层网络技术的细节的技术。 通过RPC我们可以充分利用非共享内存的多处理...

摩云菜 ⋅ 2016/01/22 ⋅ 1

一、C语言概述

说明:这个C语言专题,是学习iOS开发的前奏。也为了让有面向对象语言开发经验的程序员,能够快速上手C语言。如果你还没有编程经验,或者对C语言、iOS开发不感兴趣,请忽略 为什么iOS开发要先...

长平狐 ⋅ 2013/03/28 ⋅ 1

小蚂蚁学习C语言(1)——C语言概述

C语言概述 1. 为什么学习C语言 C的起源和发展 1 第一代语言:机器语言 0101 2 第二代语言:汇编语言 add 1,2 3 第三代高级语言: C语言产生和发展过程: 产生时间:1972-1973 产生地点:美国...

嗜学如命的小蚂蚁 ⋅ 2015/11/26 ⋅ 4

如何学好C语言?

  C语言杂谈 如何学好C语言?为什么会有学的既不深,也不扎实,半吊子的感觉      我相信,这可能是很多朋友的问题,我以前也有这样的感觉,编程编到一定的时候,发现能力到了瓶颈,既...

编程大亨 ⋅ 2017/12/20 ⋅ 0

如何学好C语言

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

邪恶的小Y ⋅ 2011/08/16 ⋅ 2

C语言C++新手入门基础学习书籍资料推荐

接下来会陆续介绍各自编程语言和各个领域的学习建议,本文先讲C语言。 1、C语言适合当第一门编程语言学习 、C语言语法相对简单,但又比较完整和严谨,包含该有的各种元素。学完C语言语法,要...

小辰带你看世界 ⋅ 2017/12/31 ⋅ 0

C语言入门学习和书籍推荐

接下来会陆续介绍各自编程语言和各个领域的学习建议,本文先讲C语言。 1、C语言适合当第一门编程语言学习 ①、C语言语法相对简单,但又比较完整和严谨,包含该有的各种元素。学完C语言语法,...

小辰GG ⋅ 2017/12/04 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

vim编辑模式、命令模式

编辑模式 vim要从一般模式进入编辑模式只要按字母 i 、I、a、A、o、O键就可以了 要从编辑模式回到一般模式按键盘上的Esc键即可。 按键 作用 i 在当前字符前插入 I 在光标所在行的行首插入 o ...

黄昏残影 ⋅ 22分钟前 ⋅ 0

OSChina 周五乱弹 —— 如果有一天不当程序员了

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @guanglun :分享off的单曲《我唱情歌给你听》 《我唱情歌给你听》- off 手机党少年们想听歌,请使劲儿戳(这里) @小小编辑 :#如果不做程序...

小小编辑 ⋅ 29分钟前 ⋅ 4

从 Confluence 5.3 及其早期版本中恢复空间

如果你需要从 Confluence 5.3 及其早期版本中的导出文件恢复到晚于 Confluence 5.3 的 Confluence 中的话。你可以使用临时的 Confluence 空间安装,然后将这个 Confluence 安装实例升级到你现...

honeymose ⋅ 今天 ⋅ 0

Java8新增的DateTimeFormatter与SimpleDateFormat的区别

两者最大的区别是,Java8的DateTimeFormatter也是线程安全的,而SimpleDateFormat并不是线程安全。 在并发环境下使用SimpleDateFormat 为了能够在多线程环境下使用SimpleDateFormat,有这三种...

人觉非常君 ⋅ 今天 ⋅ 0

多线程如何控制执行顺序

线程的生命周期说明: 当线程被创建并启动以后,它既不是一启动就进入了执行状态,也不是一直处于执行状态,在线程的生命周期中,它要经过新建(New)、就绪(Runnable)、运行(Running)、...

MarinJ_Shao ⋅ 今天 ⋅ 0

用ZBLOG2.3博客写读书笔记网站能创造今日头条的辉煌吗?

最近两年,著名的自媒体网站今日头条可以说是火得一塌糊涂,虽然从目前来看也遇到了一点瓶颈,毕竟发展到了一定的规模,继续增长就更加难了,但如今的今日头条规模和流量已经非常大了。 我们...

原创小博客 ⋅ 今天 ⋅ 0

MyBatis四大核心概念

本文讲解 MyBatis 四大核心概念(SqlSessionFactoryBuilder、SqlSessionFactory、SqlSession、Mapper)。 MyBatis 作为互联网数据库映射工具界的“上古神器”,训有四大“神兽”,谓之:Sql...

waylau ⋅ 今天 ⋅ 0

以太坊java开发包web3j简介

web3j(org.web3j)是Java版本的以太坊JSON RPC接口协议封装实现,如果需要将你的Java应用或安卓应用接入以太坊,或者希望用java开发一个钱包应用,那么用web3j就对了。 web3j的功能相当完整...

汇智网教程 ⋅ 今天 ⋅ 0

2个线程交替打印100以内的数字

重点提示: 线程的本质上只是一个壳子,真正的逻辑其实在“竞态条件”中。 举个例子,比如本题中的打印,那么在竞态条件中,我只需要一个方法即可; 假如我的需求是2个线程,一个+1,一个-1,...

Germmy ⋅ 今天 ⋅ 0

Django第一期

安装Django 去https://www.djangoproject.com/download/ 下载最新版的Django,然后解压放到Anaconda\Lib\site-packages目录下,然后cmd进入此目录,输入安装命令: python setup.py install ...

大不了敲一辈子代码 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部