数据结构（陈越版）

C语言基础知识简要回顾

基础知识回顾

实现抽象数据类型首先要考虑数据如何存储，其次在确定存储方式的基础上，相应的操作如何实现。

2.1存储

高级语言提供了如数组、链表、结构体等数组织基本实现方式。不同方式有不同优缺点

2.1.1 数组

• 最基本的数据类型，相同数据类型的有序集合。
• 数据具有随机存储优点（数据A[i]存储与下标i无关）

2.1.2 类型定义

• **typedef **建立已经定义好了的数据别名，从而使得代码维护简单，具有更好的可读性和移植性。

2.1.3 指针

• C语言中特色之一，使用指针可以对复杂数据进行处理，对计算机内存进行分配控制，也可以实现函数调用返回多个值。
• 指针基本运算
• 指针与数组区别
  • 几乎相同，数组名的值其实就是数组基地址，即第一个元素的地址，可以看成固定地址，可以看成一个指针常量
• 用指针实现内存的动态分配

2.1.4 结构

• 结构类型允许将一些数据分量聚合成一个整体的数据类型
  • 结构变量的使用 结构成员操作符.
    • 结构变量名.成员名
  • 结构数组
  • 结构指针
    • *访问
    • ->访问
  • 共用体

2.1.5 链表

• 基础的数据结构、可以克服数组需要预先知道数据大小的缺点，充分利用内存空间，实现灵活内存管理
• 单向链表
  • 结构
  • 操作
    • 插入节点
    • 删除节点
    • 遍历
    • 初始化
• 双向链表
• 循环链表

2.2 操作实现

• 分支控制语句，循环控制语句和顺序执行结构
• 模块化
  • 函数是模块化设计的基本手段