数据结构--第一讲 2018年3月21日

一、数据结构：研究数据(数据元素)之间的关系。(C研究数值型数据之间的简单运算， 数据结构 还研究非数值型之间的运算)

1.逻辑结构(关系)：集合、线性关系、树形关系、图状关系(线性和非线性关系)

2.物理结构(物理关系)：逻辑结构在计算机内存中具体实现的方法，有顺序、链式、 索引、散列等存储方法

3.数据运算：对数据进行的操作，增、删、查、改、排序。

数据即信息的载体。

数据元素是数据的基本单位(又称记录，Record),由若干个基本项(or字段、域属性)组成

数据类型是对数据元素取值范围与运算的限定

  

相关术语概念：

数据Date 数据类型Date Type 数据元素Date Element

数据结构Date Structure 物理结构(存储结构)Physical Structure

顺序存储Sequential Storage 链式存储Linked Storage

索引存储Indexed Storage 散列存储Hash Storage

形式化语言描述(数学表达式)：

DS=(D,R)D数据元素的集合，R D上关系的集合

根据数据元素间的关系的基本特性有四种基本数据结构：

集合——数据元素间除“同属于一个集合”外，无其他关系

线性结构——一个对一个，如线性表、栈、队列

树形结构——一个对多个，如树

图状结构——多个对多个，如图(图是树的拓展，可有树构成)

算法Algorithm一个又穷规则(or语句、指令)的有序集合(对程序的优化，易阅读、调试、维护)

特性：有穷性、确定性、可行性、输入(0-n)、输出(1-n)

程序 = 算法 + 数据结构

算法与程序的区别：

1. 算法与计算机无关，程序依赖于具体的计算机语言

2. 算法重点是在解决问题的思路上

算法分析(好坏)：时间复杂度T(n) 空间复杂度D(n)(不考虑,牺牲来成全时间)Time/Space Complexity

语句的频度：可执行语句程序中重复执行的次数。某语句执行一次耗时t，执行次数f，则该语句总耗时t*f。

量级T(n)=O(n3) 取次数最高的项并去掉系数，作为时间复杂度 。

↑上午 概念

↓下午 线性表 的逻辑和存储结构、相关算法的实现以及线性表的应用举例。

线性表Linear List

首先创建表，再插入表，再增删改查，销毁。

创建：申请一个结构体

结构体声明写在头文件里面

用gedit编辑.h和.c文件

方便的查找，在挨着表的末尾空间在申请一个空间用来存放表的有效个数or最后一个元素下标。

创建表 ：...待写

插入数据：1.首先判断表是否为满。2.判断插入的位置是否有效。3.从后往上移动数据元素。 4.插入元素。5.尾指针last+1

删除数据：1.首先判断表是否为空。2.判断删除的位置是否有效。3.删除后从前往后移动元 素。4.尾指针last-1。5移动后，之前的最后一个数据，直接忽视不用了，但是 还在。