1.什么是数据?
?? ?????????数据是指对事物进行记录并可以鉴别的符号,它不仅仅是数字，还可以是具有
?? ?一定意义的文字、字母、数字符号的组合，视频、音频、图形、图像等等。
?? ?数据经过加工后就成为信息。
?? ?

2.什么是结构?
?? ?????????结构是指数据元素之间的相互关联和相互作用的关系，比如学生
?? ?根据数据元素之间的关系，通常分成4类基本结构 ?
?? ?(1)集合：结构中的数据之间除了"同一个集合"的关系外，没有其它关系
?? ?(2)线性结构:分班的学生，图书馆的图书
?? ?(3)树状结构(层次结构),家族的族谱，公司架构
?? ?(4)网状结构(图状结构)，城市与城市之间的交通网
?? ?

3.什么是数据结构?? ?
?? ?????????数据结构是计算机存储和组织数据的方式
?? ?????????数据分成逻辑结构(算法)和存储结构
?? ?逻辑结构:是指数据与数据之间的内在关系，通常由集合,线性关系(线性表，一对一关系)
?? ?树(一对多关系)，图(多对多的关系)等逻辑结构
?? ?逻辑结构是数据之间的属性，和存储无关
?? ?
?? ?存储形式:顺序存储和链式存储
?? ?

4.什么是算法?
?? ?算法是为了实现计算目的从而制定的一系列规则的计算步骤
?? ?

5.数据结构与算法之间的关系?? ?
?? ?????????数据结构是一门研究如何有效组织数据，并提高数据处理效率的学科。
?? ?通过研究各种数据内部的逻辑关系，使用某种特定的存储形式，
?? ?并在此基础上对数据实施各种操作，这些工作被称为称为广义上的算法
?? ?

6.总结
?? ?程序 ?= 数据结构体+算法
?

7.如何计算程序运行的效率?
?? ?时空复杂度 = 时间复杂度+空间复杂度 是影响程序运行效率的根本原因
?? ?

8.时间复杂度(BigO)
?? ?(1)如何判断一个算法的好坏
?? ?(2)如何对比不同的算法
?? ?
?? ?BigO又称为大O表示法，计算的是算法的渐进时间复杂度
?? ?T(n) = O(f(n))
?? ?T(n) 表示算法的渐进时间复杂度
?? ?f(n) 表示代码执行的次数
?? ?O 表示正比例关系
?? ?
?? ?例子1:
?? ??? ?int i = 0;
?? ??? ?for(;i < N;i++)
?? ??? ?{
?? ??? ??? ?a++;
?? ??? ?}
?? ??? ?O(1+3*N) == O(N)由于N是无限大，所以此程序的时间复杂度是O(N)
?? ??? ?
?? ?例子2：
?? ??? ?for(int i =0;i < N;i++)
?? ??? ?{
?? ??? ??? ?for(int j = 0;j < N;j++)
?? ??? ??? ?{
?? ??? ??? ??? ?a++;
?? ??? ??? ?}
?? ??? ??? ?
?? ??? ?}
?? ??? ?O(N)*O(N) == O(N^2) 时间复杂度为O(N的平方)
?? ?
?? ?例子3:
?? ??? ?for(int i = 0;i < N;i++)
?? ??? ?{
?? ??? ??? ?a++;
?? ??? ?}
?? ??? ?
?? ??? ?for(int i =0;i < N;i++)
?? ??? ?{
?? ??? ??? ?for(int j = 0;j < N;j++)
?? ??? ??? ?{
?? ??? ??? ??? ?a++;
?? ??? ??? ?}
?? ??? ??? ?
?? ??? ?}
?? ??? ?时间复杂度 ： O(N+N^2) 因为N是常数 所以会被忽略掉所以 ?答案是 ?O(N^2)
?? ??? ?
?? ?例子4:
?? ??? ?int a = 1;
?? ??? ?int b = 2;
?? ??? ?int c = 3;
?? ??? ?printf("%d,%d,%d\n",a,b,c);
?? ??? ?时间复杂度 : O(1)
?? ?
?? ?常用的时间复杂度量级
?? ?1.常数阶O(1)
?? ?2.对数O(logN)
?? ?3.线性阶O(N)
?? ?4.线性对数阶O(nlogN)
?? ?5.平方阶O(N^2)
?? ?6.立方阶O(N^3)
?? ?7.K次方阶O(N^K)
?? ?8.指数阶O(2^n)
?? ?9.乘阶O(n!)
?? ?
练习:
?? ?// 片段1
?? ?for(int i = 1; i < n;i=i*2)
?? ?{
?? ??? ?printf(i);
?? ?}
?? ?因为 2^k = n ?所以 k = logN
?? ?
?? ?
?? ?// 片段2
?? ?int i = 0;
?? ?int s = 0;
?? ?while(s < n) ??
?? ?{
?? ??? ?++i;
?? ??? ?s+=i;
?? ?}
?? ?
?? ?因为1+2+3+...+k == k(k+1)/2 >= n ?k为运行的次数 ?---》k(k+1) >= 2n --->k^2+1 >= 2n --->k > (2n)^(1/2)-1 --->因为 当n无限大的时候
?? ??? ?k >= n^(1/2) == 根号n ?
?? ?
?? ?//片段3
?? ?int i = 1;
?? ?while(i < n)?
?? ??? ?i = i*2
?? ?因为 2^k = n ?所以 k = logN
?

9.空间复杂度
?? ?o(1)
?? ?int x = 0;
?? ?int y = 0;
?? ?x++;
?? ?y++;
?? ?
?? ?O(n)空间复杂度
?? ?int *newArray = malloc(n*sizeof(int));
?? ?for(int i = 1;i<n;i++)
?? ??? ?newArray[i] = i;
?

10.数据结构之线性结构，线性表
?? ?例子 ：
?? ??? ?26个英文字母
?? ??? ?学生的学号
?? ?

?? ?什么是线性表
?? ??? ?一对一的数据所组成的关系称为线性表，注意线性表是逻辑结构
?? ??? ?线性表中的数据是可以为任意数据，但是同一线性表中的元素必须是具有相同的特性，即同一数据对象比如(26个英文字母)
?? ??? ?线性表特点:
?? ??? ?(1)存在唯一一个被称为"第一个"的数据元素
?? ??? ?(2)在唯一一个被称为"最后一个"的数据元素
?? ??? ?(3)除了第一个节点外，集合中的每个数据均只有一个前驱节点
?? ??? ?(4)除了最后一个节点外，集合中的每个数据均只有一个后驱节点
?? ?注意:
?? ??? ?1.线性表是一种数据内部的逻辑关系与存储形式无关
?? ??? ?2.线性表既可以采用连续的顺序存储比如数组，也可以采用零散的链式存储(链表)
?? ??? ?

11.线性表的存储方式
?? ?(1)顺序存储,顺序表
?? ??? ?顺序表是一块连续的内存空间依次有序的存储线性表中的数据，其实就是数组
?? ??? ?
?? ?(2)链式存储，链表
?? ??? ?链表中的存储空间不一定是连续的
?? ??? ?1.无头节点的单向链表(LinkedList.c)
?? ??? ?2.有头节点的单向链表(LinkedListWithHead.c)
?? ??? ?3.双向链表(BothwayLinkedList.c)
?? ??? ?4.循环链表(LoopLinkedList.c)
?? ??? ?

?? ??? ?
?? ?