数据结构基础

一、基本数据单位

一个数据对象有多个数据元素，一个数据元素有多个数据项

基本数据单位

//声明一个结构体类型
struct Teacher{     //一种数据结构
    char *name;     //数据项--名字
    char *title;    //数据项--职称
    int  age;       //数据项--年龄
};

int main(int argc, const char * argv[]) {
    Teacher t1;     //数据元素;
    Teacher tArray[10]; //数据对象;
    
    t1.age = 18;       //数据项
    t1.name = "李德胜";    //数据项
    t1.title = "教员";  //数据项
    
    printf("老师姓名:%s\n",t1.name);
    printf("老师年龄:%d\n",t1.age);
    printf("老师职称:%s\n",t1.title);
    return 0;
}

二、数据结构类型：逻辑结构和物理结构

1、逻辑结构：数据以某种逻辑关系组合在一起的结构，大概有4种即集合结构、线性结构、图形结构、树形结构

图1.集合结构 图2.线性结构 图3.图形结构 图4.树形结构

2、物理结构：数据在内存中是否占用连续的空间，有2种，即顺序存储结构和链式存储结构

图5.顺序结构 图6.链式结构

三、算法

1、定义

算法就是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每个指令表示⼀个或多个操作.

2、特性

• 输入输出：有足够的条件输入，才能得到有效的结果
• 有穷性：能够在时间段内完成
• 确定性：每一个指令都必须有明确的定义，不允许有模棱两可的解释和多义性
• 可行性：执行后能够得到满意的结果

3、数据结构与算法的关系

图7.数据结构与算法的关系-相辅相成，缺一不可

四、算法的比较

1、设计算法的要求

• 正确性：至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案
• 可读性：便于阅读、理解和交流
• 健壮性：容错处理，不因错误的输入导致崩溃
• 时间效率高和存储量低：算法运行时满足，只需足够低的运算时间和足够低的内存占用，即可完成运行

2、衡量算法效率的办法

一个算法效率的高低，由两个因素运算时间和占用空间决定，即时间复杂度和空间复杂度，其使用大O计数法表示

a、时间复杂度

常见的时间复杂度

其大小关系

O(1)<O(log n)<O(n)<O(nlog n)<O(n^2)<O(n3)<O(2^n)<O(n!)<O(nn)
注意：指数阶的算法除非n非常小，否则会造成极大的资源损耗，说明这是一种不切实际的算法，一般不做考虑

b、空间复杂度

通过计算其所需的存储空间实现,算法空间复杂度的计算公式记做: S(n) = n(f(n)),其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数 。
程序空间计算因素：
1、寄存本身的指令
2、常数
3、变量
4、输入
5、对数据进行操作的辅助空间
其中5是空间复杂度最主要的考虑因素