基本概念

数据：可被计算机识别并加工处理的对象
数据元素：由数据组成的具有一定意义的基本单位
数据项：组成数据元素的、不可分割的最小单位

数据结构

数据结构：某一数据对象及该对象中所有元素之间的关系

逻辑结构、存储结构、数据的运算

逻辑结构

基本逻辑结构：集合、线性、树形、图（结构）

存储结构

存储结构：数据及数据之间的关系在计算机内的表现形式

顺序存储结构：将逻辑上相关的数据元素依次存储在地址连续的存储空间中
链式存储结构：数据元素可以存储在连续/不连续的存储空间，数据元素间的逻辑关系通过指针域来体现
索引存储结构：附加索引表来标识节点地址
散列存储结构：将数据元素的关键字与存储位置之间建立散列表

数据的运算

数据的运算：数据被使用的方式

搜索、插入、删除、更新

算法

特征：输入、输出、可执行、确定性、有穷性

示例

1. 多项式在给定点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;
}

//示例2(better，快一个数量级)
double f(int n,doublea[],double x)
{
	int i;
	double p=a[n];
	for(i=n;i>0;i--)
		p=a[i-1]+x*p;
	return p;
}

2. 数组逆置

将元素线性关系逆置后的顺序存储

#include <stdio.h>

// 定义ElemType为int类型
typedef int ElemType;

typedef struct seqList
{
    int n;
    int maxLength;
    ElemType *element;
} SeqList;

void Invert(SeqList *L)
{
    ElemType temp;
    int i;
    for (i = 0; i < (L->n) / 2; i++) // 当前数组的实际长度时n，故进行n/2次循环即可,切记不可缺省“/2”
    {
        temp = L->element[i];
        L->element[i] = L->element[L->n - 1 - i];
        L->element[L->n - 1 - i] = temp;
    }
}

主函数

int main()
{
    SeqList L;
    int i, n;
    printf("请输入数组长度：");
    scanf("%d", &n);
    L.n = n;
    L.maxLength = n;
    L.element = (ElemType *)malloc(n * sizeof(ElemType));
    printf("请输入%d个元素:", n);
    for (i = 0; i < n; i++)
        scanf("%d", &L.element[i]);
    printf("原数组：");
    for (i = 0; i < n; i++)
        printf("%d ", L.element[i]);
    printf("\n");
    Invert(&L);
    printf("反转后数组：");
    for (i = 0; i < n; i++)
        printf("%d ", L.element[i]);
    printf("\n");
    return 0;
}

逆置后的链表存储

typedef struct node
{
     ElemType element;
     struct node *link;
}Node;

typedef struct singlelist
{
    Node *first;
    int n;
}SingleList;


void invert(SingleList *L)
{
    Node *p = L->first ,*q;     //使p指向首节点
    L->first = NULL;
    while(p != NULL)            //判断p是否指向尾节点
    {
        q = p->link;        //q指向p的下一个节点
        p->link = L->first ;
        L->first = p;
        p = q;
    }
}

数组

C 语言提供的数组并非一个完备的数据结构

1. 不能实现数组的整体赋值
2. 不能将数组作为函数值返回
3. 对数组元素不提供边界检查
4. 数组名作为变量传递，传递的实际上是数组的基地址

数组的抽象数据类型（ADT）

数组是下标 index 和值 value 组成的偶对的集合
注：数据结构中定义的数组不是同类型数据元素的集合（多维—>向量+数据）

数组不能看作线性结构的推广

数组一旦确定，数据元素的容量和位置关系就是固定的，不能进行插入和删除等操作

递归

实现代码

int Fib(int n)
{
	if(n==0||n==1)
		return n;
	return Fib(n-2)+Fib(n-1);
}

递归出口

• 定义了递归的停止条件
• 出口可以不止一个

递归调用主体（子问题划分）

• 子问题与原问题相同
• 子问题规模比原问题小
• 子问题通过一定的形式修改参数调用自身函数
• 若干子问题的解以一定方式组成原问题的解

递归程序执行过程分析

• 工作记录：函数调用执行完成时的 返回地址、局部变量、参数等信息
• 系统栈：程序运行时存放函数调用工作记录的堆栈

递归程序的执行是需要在系统栈中占用一定空间的，对空间和时间的需求都比较高

递归转非递归

int Fib(int n)
{
	int a = 0, b = 1, temp, i;
	if(n==0||n==1)
		return n;
	for(i = 2; i<=n; i++)
	{
		temp = a + b;
		a = b;
		b = temp;
	}
	return temp;
}

堆栈

后进先出

堆栈的顺序表示

#include <stdio.h>
#include <stdbool.h>    //使用布尔类型需要包含的头文件

// 堆栈结构体
typedef struct stack {
    int top;
    int max_size;
    int *element;
}Stack;

// 创建堆栈
void Create(Stack *s, int size)
{
    s->max_size=size;
    s->element=(int*)malloc(size*sizeof(int));
    s->top=-1;
}

// 销毁堆栈
void Destroy(Stack *s)
{
    s->max_size=-1;
    free(s->element);
    s->top=-1;
}

// 清空堆栈，但不销毁堆栈
// 原先存储的数据依然存在，只是栈顶指针指向了栈底
void Clear(Stack *s)
{
    s->top=-1;
}

// 判断堆栈是否已满
bool IsFull(Stack *s)
{
    return s->top==s->max_size-1;
}

// 判断堆栈是否为空
bool IsEmpty(Stack *s)
{
    return s->top==-1;
}

// 获取栈顶元素
bool Top(Stack *s, int *value)
{
    if(IsEmpty(s))  // 栈为空
        return false;
    *value=s->element[s->top];
    return true;
}

//元素进栈
bool Push(Stack *s, int value)
{
    if(IsFull(s))  // 栈已满
        return false;
    s->top++;
    s->element[s->top]=value;
    return true;
}

//元素出栈
bool Pop(Stack *s, int *value)
{
    if(IsEmpty(s))  // 栈为空
        return false;
    s->top--;
    return true;
}

使用 链式表示 也行，这里不多赘述

队列

先进先出
解决假溢出问题——循环队列
把数组从逻辑上看成一个头尾相连的环，利用取余运算 % 实现

#include <stdio.h>
#include <stdbool.h>

typedef struct queue {
    int front, rear, size;
    //front 队头元素前一单元的位置下标
    //rear 队尾元素的位置下标
    int *element;
}Queue;

void Create(Queue *q, int size)
{
    q->size = size;
    q->element = (int*)malloc(size * sizeof(int));
    q->front = q->rear = 0; //表明当前队列为空
}

void Destroy(Queue *q)
{
    free(q->element);
    q->size = -1;
    q->front = q->rear = -1;
}

void Clear(Queue *q)
{
    q->front = q->rear = 0;
    //表明当前队列为空,但并不释放空间
}

bool IsEmpty(Queue *q)
{
    return (q->front == q->rear);
}

bool IsFull(Queue *q)
{
    return ((q->rear + 1) % q->size == q->front);
}

bool Front(Queue *q, int *x)
{
    if (IsEmpty(q))
        return false;
    *x = q->element[q->front];
    return true;
}

// 入队操作
bool EnQueue(Queue *q, int *x)
{
    if (IsFull(q))
        return false;
    q->rear = (q->rear + 1) % q->size;
    q->element[q->rear] = *x;
    return true;
}

// 出队操作
bool DeQueue(Queue *q, int *x)
{
    if (IsEmpty(q))
        return false;
    q->front = (q->front + 1) % q->size;
    return true;
}

使用 链式表示 也行

栈和队列的共同点是：都是线性结构
主要区别是：限定元素插入和删除的位置不同

表达式

前缀表达式

操作符在两操作数前

中缀表达式

操作符在两操作数间，有界限符，有优先级
常用但不适合计算机处理

后缀表达式

操作符在两操作数后，适合计算机顺序处理
无界限符，无优先级

利用后缀表达式求值（堆栈）

从左到右依次扫描元素

• 若当前元素为操作数，进栈
• 为操作符，从栈中弹出两个操作数进行相应处理，将结果进栈

注：先出栈的数放在操作符的后面，后出栈的放前面