数据结构没有官方的统一定义。
例1：如何在书架上摆放图书？
图书的摆放应使2个相关操作方便实现：
那么如何分配空间？类别应该分多细？
例2 实现PrintN函数，使得传一个正整数为N的参数后，能顺序打印从1到N的全部正整数。
循环实现：
void PrintN(int N){
int i;
for(i = 1;i <= N;i++){
printf("%d\n", i);
}
return;
}
递归实现：
void PrintN(int N){
if(N){
PrintN(N - 1);
printf("%d\n", N);
}
return;
}
当输入为10、100、1000、10000时两个函数都可以正常输出，但是当输入为100000时，递归实现会内存溢出，所以只输出了100000。这就说明了：
解决问题方法的效率跟空间的利用效率有关。
例3：计算给定多项式在定点 \(x\) 处的值
代码：
double f(int n, double a[], double x){
int i;
double p = a[0];
for(i = 1 ; i <= n ; i++){
p += (a[i] * pow(x, i));
}
return p;
}
标准多项式形式为：
根据秦九韶算法可变形为：
实现代码为：
double f(int n, double a[], double x){
int i;
double p = a[n];
for(i = n ; i > 0 ; i--){
p = a[n - 1] + x * p;
}
return p;
}
利用 clock（） 函数可以计算从程序运行到 clock() 被调用时所耗费的时间，这个时间单位是 clock tick ，即时钟打点。常数 CLK_TCK 即表示机器时钟每秒所走的时钟打点数。常用的代码模板：
#include <stdio.h>
#include <time.h>
clock_t start, stop;
//记录被测函数的运行时间
double duration;
int main(){
start = clock();//开始计时
MyFunction();
stop = clock();//结束计时
duration = ((double)(stop - start)) / CLK_TCK;
return 0;
}
以多项式 \(f(x)=\sum_{9}^{i=0} i \cdot x^i\) 为例，可用以下代码进行测试：
#include <stdio.h>
#include <time.h>
#include <math.h>
clock_t start, stop;
//记录被测函数的运行时间
double duration;
#define MAXN 10
#define MAXK 1e7
double f1(int n, double a[], double x){
int i;
double p = a[0];
for(i = 1 ; i <= n ; i++){
p += (a[i] * pow(x, i));
}
return p;
}
double f2(int n, double a[], double x){
int i;
double p = a[n];
for(i = n ; i > 0 ; i--){
p = a[n - 1] + x * p;
}
return p;
}
int main(int argc, char const *argv[])
{
int i;
double a[MAXN];
for(i = 0 ; i < MAXN ; i++){
a[i] = (double)i;
}
start = clock();
for (int i = 0; i < MAXK; i++){
f1(MAXN - 1, a , 1.1);
}
stop = clock();
double duration1 = (((double)(stop - start)) / CLK_TCK) / MAXK;
printf("ticks1 = %f\n", (double)(stop - start));
printf("duration1 = %6.2e\n", duration1);
start = clock();
for (int i = 0; i < MAXK; i++)
{
f2(MAXN - 1, a , 1.1);
}
stop = clock();
double duration2 = (((double)(stop - start)) / CLK_TCK) / MAXK;
printf("ticks1 = %f\n", (double)(stop - start));
printf("duration2 = %6.2e\n", duration2);
return 0;
}
解决问题的效率与所使用的方法有关。
数据结构是数据对象在计算机中的组织方式。
数据对象必定与一系列加在其上的操作相关联。
完成这些操作的方法被称为算法。
抽象数据类型（Abstract Data Type，ADT） 用于描述数据结构。
只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题。
例4：“矩阵”的抽象数据类型定义
Matrix Create( int M, int N) ：返回一个 \(M \times N\) 的空矩阵；
- 一个有限的指令集
- 接受一些输入（有些情况下不需要输入）
- 产生输出
- 一定是在有限步骤之后终止
- 每一条指令不能有歧义且在计算机处理范围内
- 每一条指令必须不依赖于任何一种计算机语言及具体实现的手段
例1：选择排序算法的伪码描述
void SelectionSort(int List[], int N){
//将N个整数List[0]...List[N]进行非递减排序
for(i = 0;i < N;i++){
//从 List[i] 到 List[N-1] 中找到最小值，并将其所在位置赋值给MinPosition;
MinPosition = SacnForMin(List, i, N-1);
//将未排序部分的最小元素换到有序部分的最后位置;
Swap(List[i], List[MinPosition]);
}
}
在分析一般算法的效率时，常用以下两种复杂度：
- 最坏情况复杂度 \(T_{worst} (n)\)
- 平均复杂度 \(T_{avg} (n)\)
- 若两段算法分别有复杂度 \(T_1(n) = O(f_1(n))\) 和 \(T_2(n) = O(f_2(n))\) ，则有：
- \(T_1(n) + T_2(n) = max(O(f_1(n)), O(f_2(n)))\)
- \(T_1(n) \times T_2(n) = O(f_1(n) \times f_2(n))\)
- 若 \(T(n)\) 是关于 \(n\) 的 \(k\) 阶多项式，那么 \(T(n) = \Theta(n^k)\)
- for 循环的时间复杂度 = 循环次数 \(\times\) 循环体时间复杂度
if-else结构的复杂度取决于if的条件判断复杂度和两个分支部分的复杂度，总体复杂度取三者中最大
例1：最大子列和问题：给定 \(N\) 个整数的序列 \(\{A_1,A_2,\cdot\cdot\cdot,A_n\}\) ，求函数 \(f(i, j) = max\{0, \sum_{k=1}^{j}A_k \}\) 的最大值
算法1（时间复杂度为 \(T(n) = O(n^3)\)）：
int MaxSubSeqSum1(int A[], int N){
int ThisSum, MaxSum = 0;
int i, j, k;
//i为子列左端位置
for(i = 0;i < N;i++){
//j为子列右端位置
for(j = i;j < N;j++){
ThisSum = 0;
// ThisSum为A[i]到A[j]的子列和
for(k = i;k <= j;k++){
ThisSum += A[k];
}
if(ThisSum > MaxSum)
MaxSum = ThisSum;
}
}
return MaxSum;
}
算法2（时间复杂度为 \(T(n) = O(n^2)\)）：
int MaxSubSeqSum2(int A[], int N){
int ThisSum, MaxSum = 0;
int i, j;
//i为子列左端位置
for(i = 0;i < N;i++){
//ThisSum为A[i]到A[j]的子列和
ThisSum = 0;
//j为子列右端位置
for(j = i;j < N;j++){
//对于相同的i，不同的j，只要在j-1次循环的基础上累加1项即可
ThisSum += A[j];
if(ThisSum > MaxSum)
MaxSum = ThisSum;
}
}
return MaxSum;
}
算法3 分而治之（时间复杂度为 \(T(n) = O(n\log n)\)）：
int Max3( int A, int B, int C ){
/* 返回3个整数中的最大值 */
return A > B ? A > C ? A : C : B > C ? B : C;
}
int DivideAndConquer( int List[], int left, int right ){
/* 分治法求List[left]到List[right]的最大子列和 */
int MaxLeftSum, MaxRightSum; /* 存放左右子问题的解 */
int MaxLeftBorderSum, MaxRightBorderSum; /*存放跨分界线的结果*/
int LeftBorderSum, RightBorderSum;
int center, i;
if( left == right ) { /* 递归的终止条件，子列只有1个数字 */
if( List[left] > 0 ) return List[left];
else return 0;
}
/* 下面是"分"的过程 */
center = ( left + right ) / 2; /* 找到中分点 */
/* 递归求得两边子列的最大和 */
MaxLeftSum = DivideAndConquer( List, left, center );
MaxRightSum = DivideAndConquer( List, center+1, right );
/* 下面求跨分界线的最大子列和 */
MaxLeftBorderSum = 0; LeftBorderSum = 0;
for( i=center; i>=left; i-- ) { /* 从中线向左扫描 */
LeftBorderSum += List[i];
if( LeftBorderSum > MaxLeftBorderSum )
MaxLeftBorderSum = LeftBorderSum;
} /* 左边扫描结束 */
MaxRightBorderSum = 0; RightBorderSum = 0;
for( i=center+1; i<=right; i++ ) { /* 从中线向右扫描 */
RightBorderSum += List[i];
if( RightBorderSum > MaxRightBorderSum )
MaxRightBorderSum = RightBorderSum;
} /* 右边扫描结束 */
/* 下面返回"治"的结果 */
return Max3( MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum );
}
int MaxSubseqSum3( int List[], int N ){
/* 保持与前2种算法相同的函数接口 */
return DivideAndConquer( List, 0, N-1 );
}
算法4 在线处理算法（时间复杂度为 \(T(n) = O(n)\)）：
int MaxSubseqSum4( int A[], int N )
{ int ThisSum, MaxSum;
int i;
ThisSum = MaxSum = 0;
for( i = 0; i < N; i++ ) {
ThisSum += A[i]; /* 向右累加 */
if( ThisSum > MaxSum )
MaxSum = ThisSum; /* 发现更大和则更新当前结果 */
else if( ThisSum < 0 ) /* 如果当前子列和为负 */
ThisSum = 0; /* 则不可能使后面的部分和增大，抛弃之 */
}
return MaxSum;
}
原文：https://www.cnblogs.com/vocaloid-fan1995/p/DataStructure01.html