数据结构 day01

大纲

1.数据结构

2.算法

3.线性表

顺序表：数组

链表：单向链表，单向循环链表，双向链表，双向循环链表

栈：顺序栈，链式栈

队列：顺序队列，链式队列

4.树：特性

二叉树：性质，创建，遍历

5.排序方法，查询方法：原理，思路

为什么学数据结构

1.C语言学习如何写程序，数据结构是为了简洁高效的写程序

2.如果遇到一个实际问题，需要写代码实现相应功能，需要解决两方面问题：

1）如何表达数据之间的逻辑关系，以及怎样储存在计算机中

数据结构：数据的逻辑结构，存储结构，操作（数据的运算）

数据：不是单纯的数字，更类似于集合的概念

结构：表达数据之间的关系

2）采用什么方法解决

采用算法解决

程序 = 数据结构 + 算法

问题—》数据结构 + 算法 == 程序—》解决问题

1.什么是数据结构

数据结构：数据的逻辑结构，存储结构，操作（数据的运算）

1.1. 数据

数据：类似于集合的概念

数据元素（节点）：数据的基本单位，由若干数据项组成

数据项：数据的最小单位，描述数据元素的信息

计算机处理对象不是单纯的数值

图书管理中的数据：

1.2. 逻辑结构

数据元素并不是孤立存在的，其间存在某种关系（联系和结构）

1.2.1. 线性关系

逻辑结构：线性结构

特点：一对一

线性结构：顺序表，链表，栈，队列

1.2.2. 层次关系

逻辑结构：树形结构

特点：一对多

树形结构：二叉树

1.2.3. 网状关系

逻辑结构：图状结构

特点：多对多

图状结构：图

1.3. 存储结构

数据的逻辑结构在计算机中具体实现

1.3.1. 顺序存储

数组：连续存储

特点：内存连续，随机存储，每个元素占空间较少

缺点：只能用一块大的且连续的空间，会产生空间的浪费

1.3.2. 链式存储

特点：内存不连续，使用指针实现

链表实现

结构体：

#include <stdio.h>struct node_t
{int data;               // 数据域：存放节点的数据struct node_t *next;    // 指针域：结构体指针指向下一个节点
};int main(int argc, char const *argv[])
{struct node_t A = {1, NULL};struct node_t B = {2, NULL};struct node_t C = {3, NULL};A.next = &B;B.next = &C;return 0;
}

1.3.3. 索引存储结构

在存储数据的同时，建立索引表。即索引存储结构 = 索引表 + 数据文件。

特点：提高查找速度，检索速度快

缺点：占用内存多，删除数据文件要及时更改索引表

1.3.4. 散列存储

数据存储按照和关键码之间的关系进行存取。关系由自己决定。

例如关键码为key，下一个存储的关键码是key+1。

获取关键数据，通过元素的关键码的返回值来获取，存取都按照相应的关系存取

与商场的储物柜类似，给你一个号码，存取物品时查找号码来存取

1.4. 操作

增，删，改，查

2. 什么是算法

算法是解决问题的思想方法，数据结构是算法的基础

2.1. 算法的设计

设计取决于数据的逻辑结构

实现依赖于数据的存储结构

2.2. 特性

有穷性：步骤是有限的

确定性：每一步有明确的含义，不能有争议

可行性：规定时间内能完成

输入输出

2.3. 评价算法的好坏

1）正确性

2）易读性

3）健壮性：有一定容错处理

4）高效性：执行效率，通过重复执行的次数来判断，也就是通过时间复杂度（时间处理函数）来判断

时间复杂度

语句频度：用时间规模函数表达

时间规模函数：T(n) = O(f(n))

T(n) // 时间规模函数

O // 时间数量级

n // 问题规模，a[100], n = 100

f(n) // 算法可执行语句重复执行次数

例题1：求1+2+3+4+……+n 的和

算法1
int sum = 0;
for(int i = 1; i <= n; i++)
{sum+=i;
}
n = 100

f(n) = 100

T(n) = O(n)

算法2

利用等差数列前n项和公式
int sum = n*(1+n)/2;
n = 100，执行一次

f(n) = 1

T(n) = O(1)

例题2
int i, j;
for(i = 0; i < n; i++)
{for(j = 0; j < n; j++){printf("ok\n");}
}
n*n 次

f(n) = n^2

T(n) = O(n^2)

例题3
int i, j;
for(i = 0; i < n; i++)
{for(j = 0; j <= i; j++){printf("ok\n");}
}
执行次数： 1+2+3+……+n

f(n) = n*(1+n)/2 = n^2/2 + n/2

T(n) = O(n^2)

计算方法：

1）根据问题规模 n 写出表达式

2）有常数项时，常数项置1

3）只保留最高项，最高项系数置1

f(n) = 3*n^4 + 2*n^3 + 6*n^7 +10

T(n) = O(n^7)

3. 线性表

线性表是最基本，最简单，最常用的数据结构，可以存储逻辑关系为线性的数据。一个线性表是 n 个具有相同特性的数据元素的有限序列。

包含：

顺序表：数组

链表：单向链表，单向循环链表，双向链表，双向循环链表

栈：顺序栈，链式栈

队列：顺序队列，链式队列

逻辑结构：线性结构

存储结构：顺序存储（数组），链式存储（指针）

特点：一对一，每个节点最多一个前驱，一个后继

首节点无前驱，尾节点无后继

3.1. 顺序表

顺序表存储数据的具体实现方案：将数据全部存储到一整块内存中，数据元素之间按照次序挨个存放。

举个简单的例子，将 {1,2,3,4,5} 这些数据使用顺序表存储，数据最终的存储状态如下

3.1.1. 顺序表的特性

特点：内存连续

逻辑结构：线性结构

存储结构：顺序存储

操作：增删改查

3.1.2. 操作数组

例题

int a[100] = {1, 2, 3, 4, 5, 6, 7, 8};

int last = 7; // 代表最后一个有效元素下标 last = 有效元素个数-1

全局变量 last 表示有效元素的下标

1）插入数组元素

函数：void insetIntoA( int *p, int post, int data);

功能：向数组的第几个位置插入数据

参数：

int *p // 保存数组首地址

int post // 插入元素下标

int data // 数据
#include <stdio.h>// 向数组的第几个位置插数据
void insetIntoA(int *p, int post, int data)
{// 1. 把从最后一个元素p[n-1]开始到插入元素p[post]向后移动一个位置for (int i = last; i >= post; i--){p[i+1] = p[i];}// 插入新元素 data 到定义位置p[post] = data;last++;
}

2）遍历数组中的有效元素

函数：void showA( int *p);

功能：遍历数组中的有效元素

参数：

int *p // 保存数组首地址
// 遍历数组中的有效元素
void showA(int *p, int n)
{for (int i = 0; i < last+1; i++){printf("%d ", p[i]);}printf("\n");
}

3）删除数组元素

函数：void deleteIntoA( int *p, int post);

功能：删除数组中指定元素

参数：

int *p // 保存数组首地址

int post // 删除元素下标
void deleteIntoA(int *p, int n, int post)
{// 从删除位置后一个元素p[post+1]到p[n-1]往前移动一个单位for (int i = post + 1; i < last+1; i++){p[i-1] = p[i];}last--;
}