呜呜呜笔试的痛，基础一定要打好啊！要不然就像我一样要把知识重新捡回来了。我大一学数据结构就是跟着郝斌老师学的，非常nice！【郝斌】数据结构入门

由于郝斌老师的视频不完整，所以我又找了数据结构与算法基础（青岛大学-王卓）补上缺的那部分的知识。

记笔记记到一半上来感慨一下，绝了姐妹们！温故而知新，我把之前学的知识串通起来了！

1. 预备知识

数据结构定义：我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器(内存)中，以及在此基础上为实现某个功能(比如查找、删除、排序)而执行的相应操作，这个相应的操作也就是算法。

数据结构 = 个体 + 个体的关系

算法 = 对存储数据的操作

程序 = 数据结构 + 算法

衡量算法的标准：

时间复杂度：程序要执行的次数，而非确定时间
空间复杂度：算法执行过程中所占用的最大内存
难易程度
健壮性

1.1 指针

地址：内存单元的编号，范围从00000000 — FFFFFFFF（0~4G-1）。

指针：指针(*p)就是地址，地址就是指针。指针变量(p)是存放内存单元地址的变量。指针的本质是一个操作受限的非负整数。指针不等于指针变量。所有指针变量只占4个字节。

变量：给地址起了个别名。

#include <stdio.h>
int main(void)
{
    int *p;		//p是个指针变量，int *表示p变量只能存储int类型变量的地址
    int j = 10;
    int i;
    char ch = 'A';
    
    //j = *p;	//*p是野指针，因为没有被初始化
    //p = &ch;	//数据类型不一致
    p = &j;
    *p = j;		//等价于j = j;
    i = *p;
    int *q = &j;
    printf("i = %d, j = %d, *p = %d, *q = %d\n", i, j, *p, *q);
    
    return 0;
}
/**
i = 10, j = 10, *p = 10, *q = 10
*/

#include <stdio.h>

void f(int i)
{
    i = 100;
}

int main(void)
{
    int i = 9;
    f(i);
    printf("i = %d\n", i);
}
/**
i = 9
*/

#include <stdio.h>

void f(int *i)
{
    *i = 100;
}

int main(void)
{
    int i = 9;
    f(&i);
    printf("i = %d\n", i);
}
/**
i = 100
*/

#include <stdio.h>

void f(int **q)
{
    **q = 100;
    *q = (int *)0xFFFFFFFF;
}

int main(void)
{
    int i = 9;
    int *p = &i;
    printf("%p\n", p);		//p变量存的内容以地址的形式输出，也就是打印i的地址
    //printf("%p\n", &p);	//打印p变量的地址
    f(&p);
    printf("i = %d, p = %p\n", i, p);
}
/**
0101F86C
i = 100, p = FFFFFFFF
*/

1.2 数组

#include <stdio.h>

int main()
{
    int a[5] = {1,2,3,4,5};		//a[i] == *(a+i) == *(i+a) == i[a]
    printf("%p\n", a + 1);
    printf("%p\n", a + 2);
    printf("%d\n", *a + 3);		//*a+3 == a[0]+3
    return 0;
}
/**
0056FB1C
0056FB20
4
*/

#include <stdio.h>

void Show_Array(int *p, int len)
{
    p[2] = -1;
    for(int i=0; i<len; i++)
        printf("%d ", p[i]);
}

int main()
{
    int a[5] = {1,2,3,4,5};
    Show_Array(a, 5);		//a等价于&a[0],&a[0]本身就是int *类型
}
/**
1 2 -1 4 5
*/

1.3 结构体

为什么会出现结构体：为了表示一些复杂的数据，而普通的基本类型变量无法满足要求。

结构体定义：结构体是用户根据实际需要自己定义的复合数类型。

#include <stdio.h>
#include <string.h>

struct Student
{
    int sid;
    char name[20];
    int age;
};

int main(void)
{
    struct Student st = {1000, "zhangsan", 20};
    printf("%d %s %d\n", st.sid, st.name, st.age);
    st.sid = 2000;
    //st.name = "lisi";		//name是个数组指针变量，左右数据类型不一致
    strcpy(st.name, "lisi");
    st.age = 21;
    printf("%d %s %d\n", st.sid, st.name, st.age);
    return 0;
}
/**
1000 zhangsan 20
2000 lisi 21
*/

#include <stdio.h>
#include <string.h>

struct Student
{
    int sid;
    char name[20];
    int age;
};

int main(void)
{
    struct Student st;		//类似于int i;
    struct Student * pst;	//类似于int *p;
    pst = &st;				//类似于p = &i;
    pst->sid = 99;			//类似于*p = 99;
    //pst->sid等价于(*pst).sid等价于st.sid
    //结构体指针变量后是"->"
}

注意事项：结构体变量不能进行算术运算，但是可以相互赋值；普通结构体变量和结构体指针变量作为函数传参的问题，推荐使用传递结构体指针的方式，这样效率高、节约内存。

#include <stdio.h>
#include <string.h>

struct Student
{
    int sid;
    char name[20];
    int age;
};

void f(struct Student * pst)
{
    (*pst).sid = 99;
    strcpy(pst->name, "zhangsan");
    pst->age = 23;
}

/**	
//这种方式耗内存，耗时间，不推荐
void g(struct Student st)
{
    printf("%d %s %d\n", st.sid, st.name, st.age);
}
*/

void k(struct Student * pst)
{
    printf("%d %s %d\n", pst->sid, pst->name, pst->age);
}

int main(void)
{
    struct Student st;
    f(&st);
    //printf("%d %s %d\n", st.sid, st.name, st.age);
    //g(st);	
    k(&st);
    return 0;
}

1.4 动态内存分配

#include <stdio.h>
#include <malloc.h>

int main(void)
{
    //静态数组
    int a[5] = {1,2,3,4,5};
    
    //动态数组
    int len;
    printf("请输入需要分配数组的长度：length = ");
    scanf("%d", &len);	//将输入写到len变量这个地址中去
    len = 5;
    int * pArr = (int *)malloc(sizeof(int) * len);
    *pArr = 4;			//类似于a[0] = 4;
    pArr[1] = 10;		//类似于a[1] = 10;
   
    for(int i=0; i<len; i++)
    {
        pArr[i] = i * i;
        printf("%p\n", &pArr[i]);	//取动态数组的每个元素的地址并输出
    }
    free(pArr);			//把pArr所代表的动态分配所有个字节的内存释放
    
    return 0;
}
/**
//动态数组的地址也是连续的
009F6B18
009F6B1C
009F6B20
009F6B24
009F6B28
*/

1.5 跨函数使用内存

#include <stdio.h>

int f();

int main(void)
{
    int i = 10;
    i = f();
    printf("i = %d\n", i);
    
    return 0;
}

int f()
{
    int j = 20;
    return j;
}
/**
i = 20
*/

#include <stdio.h>

/*
void f(int **q)
{
    int s;
    *q = &s;
}
*/

void g(int **q)
{
    *q = (int *)malloc(sizeof(int));
}

int main(void)
{
    int *p;
    //f(&p);	//p调用完f()还是野指针，因为调用完f()，f()中的局部变量都没了
    g(&p);
}

#include <stdio.h>
#include <malloc.h>

struct Student
{
    int sid;
    int age;
};

struct Student * CreateStudent();
void ShowStudent(struct Student *);

int main()
{
    struct Student * pst;
    pst = CreateStudent();
    ShowStudent(pst);
}

struct Student * CreateStudent()
{
    struct Student * p = (struct Student *)malloc(sizeof(struct Student));
    p->sid = 99;
    p->age = 22;
    return p;
}

void ShowStudent(struct Student * ps)
{
    printf("%d %d\n", ps->sid, ps->age);
}
/**
99 22
*/

2. 线性结构

2.1 连续存储【数组】

优点：存取速度快、方便查找

缺点：事先知道数组的长度、插入删除元素慢、空间通常有限制、需要大块连续内存

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

struct Arr
{
    int* pBase;		//存储的是数组第一个元素的地址
    int len;		//数组所能容纳的最大元素的个数
    int cnt;		//当前数组有效元素的个数
};

void init_arr(struct Arr*, int);
bool append_arr(struct Arr*, int);		//追加
bool insert_arr(struct Arr*, int, int);
bool delete_arr(struct Arr*, int, int*);//删除的元素放在int*
bool is_empty(struct Arr*);
bool is_full(struct Arr*);
void sort_arr(struct Arr*);
void show_arr(struct Arr*);
void reverse_arr(struct Arr*);

int main()
{
    struct Arr arr;
    init_arr(&arr, 6);
    show_arr(&arr);
    append_arr(&arr, 1);
    append_arr(&arr, 2);
    append_arr(&arr, 3);
    append_arr(&arr, 4);
    append_arr(&arr, 5);
    show_arr(&arr);
    insert_arr(&arr, 4, 99);
    show_arr(&arr);
    
    int val;
    if (delete_arr(&arr, 1, &val))
    {
        printf("删除成功！\n");
        printf("您删除的元素是：%d\n", val);
    }
    else
    {
        printf("删除失败！\n");
    }
    show_arr(&arr);

    reverse_arr(&arr);
    show_arr(&arr);

    sort_arr(&arr);
    show_arr(&arr);

    return 0;
}

void init_arr(struct Arr* pArr, int length)
{
    //(*pArr).len = 99;
    pArr->pBase = (int*)malloc(sizeof(int) * length);

    //分配内存失败，会把NULL赋值给pBase
    if (NULL == pArr->pBase)
    {
        printf("动态内存分配失败！\n");
        exit(-1);
    }
    else
    {
        pArr->len = length;
        pArr->cnt = 0;
    }

    return;
}

bool is_empty(struct Arr* pArr)
{
    if (0 == pArr->cnt)
        return true;
    else
        return false;
}

void show_arr(struct Arr* pArr)
{
    if (is_empty(pArr))
        printf("数组为空！\n");
    else
    {
        for (int i = 0; i < pArr->cnt; i++)
        {
            printf("%d ", pArr->pBase[i]);
        }
        printf("\n");
    }
}

bool is_full(struct Arr* pArr)
{
    if (pArr->cnt == pArr->len)
        return true;
    else
        return false;
}

bool append_arr(struct Arr* pArr, int val)
{
    //满时返回false
    if (is_full(pArr))
        return false;

    //没满时追加
    pArr->pBase[pArr->cnt] = val;
    pArr->cnt++;
    return true;
}

bool insert_arr(struct Arr* pArr, int pos, int val)
{
    if (is_full(pArr))
    {
        printf("数组已满，不能进行插入操作！\n");
        return false;
    }

    if (pos<0 || pos>pArr->cnt + 1)
    {
        printf("插入位置不合法！\n");
        return false;
    }

    int tmp;
    for (int i = pArr->cnt - 1; i >= pos; i--)
    {
        pArr->pBase[i + 1] = pArr->pBase[i];
    }
    pArr->pBase[pos] = val;
    pArr->cnt++;
    return true;
}

bool delete_arr(struct Arr* pArr, int pos, int* pVal)
{
    if (is_empty(pArr))
    {
        printf("数组为空，不能进行删除操作！\n");
        return false;
    }

    if (pos<0 || pos>pArr->cnt-1)
    {
        printf("删除位置不合法！\n");
        return false;
    }

    *pVal = pArr->pBase[pos];
    for (int i = pos; i < pArr->cnt - 1;i++)
    {
        pArr->pBase[i] = pArr->pBase[i + 1];
    }
    pArr->cnt--;
    return true;
}

void reverse_arr(struct Arr* pArr)
{
    int i = 0;
    int j = pArr->cnt - 1;
    int t;

    while (i < j)
    {
        t = pArr->pBase[i];
        pArr->pBase[i] = pArr->pBase[j];
        pArr->pBase[j] = t;
        ++i;
        --j;
    }

    return;
}

void sort_arr(struct Arr* pArr)
{//选择排序
    int i, j, t;
    for (i = 0; i < pArr->cnt-1; i++)
    {
        for (j = i+1; j < pArr->cnt; j++)
        {
            if (pArr->pBase[i] > pArr->pBase[j])
            {
                t = pArr->pBase[i];
                pArr->pBase[i] = pArr->pBase[j];
                pArr->pBase[j] = t;
            }
        }
    }

    return;
}

2.2 离散存储【链表】

优点：空间没有限制、插入删除元素很快

缺点：存取速度慢

2.2.1 typedef的用法

#include <stdio.h>

//int为已经存在的数据类型，ZHANGSAN是给数据类型起个别名
//typedef int ZHANGSAN;
typedef struct Student
{
    int sid;
    char name[100];
    char sex;
}ST;	//struct Student是已经存在的数据类型，ST是别名

int main()
{
    //ZHANGSAN i = 10;
    //printf("%d\n", i);
    
    ST st;		//等价于struct Student st;
    st.sid = 100;
    printf("%d\n", st.sid);
    
    return 0;
}

#include <stdio.h>

typedef struct Student
{
    int sid;
    char name[100];
    char sex;
}ST, * PST;		//PST等价于struct Student *		

int main()
{
    ST st;
    PST ps = &st;
    ps->sid = 199;
    printf("%d\n", ps->sid);
    
    return 0;
}

2.2.2 链表

链表的定义：n个节点离散分配，彼此通过指针相连，每个节点只有一个前驱节点同时每个节点只有一个后续节点，首节点没有前驱节点，尾节点没有后续节点。

专业术语：

首节点：存放第一个有效数据的节点
尾节点：存放最后一个有效数据的节点
头节点：位于首节点之前的一个节点，头结点并不存放有效的数据，加头结点的目的主要是为了方便对链表的操作
头指针：指向头结点的指针变量
尾指针：指向尾节点的指针变量

确定一个链表需要几个参数：只需要一个头指针参数，因为我们通过头指针可以推算出链表的其他所有信息。

#include <stdio.h>

typedef struct Node
{
    int data;
    struct Node * pNext;	//指向下一个与自己一模一样的数据类型
}NODE, * PNODE;

int main()
{
    return 0;
}

链表的分类：

单链表：每一个节点只有一个指针域
双链表：每一个节点有两个指针域
循环链表：能通过任何一个节点找到其他所有的节点
非循环链表：不能通过任何一个节点找到其他所有的节点

循环链表属于双链表的一种特殊形式，即循环链表是双链表的一个子集。

2.2.2.1 链表的插入

r = p->pNext; p->pNext = q; q->pNext = r;
q->pNext = p->pNext; p->pNext = q;

2.2.2.2 链表的删除

r = p->pNext; p->pNext = p->pNext->pNext; free(r);

2.2.3 链表的实现

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

typedef struct Node
{
    int data;//数据域
    struct Node * pNext;//指针域
}NODE,*PNODE；//NODE相当于struct Node，*PNODE相当于struct Node *

//创建链表
PNODE create_list(void);
//遍历链表
void traverse_list(PNODE pHead);
//判断是否为空
bool is_empty(PNODE pHead);
//返回链表长度
int length_list(PNODE pHead);
//在指定节点处插入某个元素
bool insert_list(PNODE,int,int);
//删除指定位置的元素
bool delete_list(PNODE,int,int *);
//对链表排序
void sort_list(PNODE pHead);

int main(void)
{
    PNODE pHead = NULL;//定义头节点
    pHead = create_list();
    traverse_list(pHead);
    if(is_empty(pHead))
        printf("链表为空！\n");
    else
        printf("链表非空！\n");
    int len = length_list(pHead);
    printf("链表的长度是%d\n", len);
    
    sort_list(pHead);
    traverse_list(pHead);
    
    insert_list(pHead, 4, 33);
    traverse_list(pHead);
    
    delete_list(pHead, 4, &val);
    traverse_list(pHead);
    
    return 0;
}

PNODE create_list(void)
{
    int len;//链表成员个数，由用户输入
    int i;
    int val;//链表成员值，由用户输入

    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    if (NULL == pHead)
    {
        printf("分配内存失败，程序结束");
      	exit(-1);
    }

    printf("请输入链表长度,len=");
    scanf("%d",&len);

    PNODE pTail = pHead;
    pTail->pNext = NULL;

    for(i=0; i < len; i++)
    {
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
      	if (NULL == pNew)
        {
            printf("分配内存失败，程序结束");
            exit(-1);
        }
      	printf("请输入要插入链表的值,val=");
        scanf("%d",&val);

      	pNew->data = val;
      	pTail->pNext = pNew;
      	pNew->pNext = NULL;
      	pTail = pNew;
    }
    return pHead;
}

void traverse_list(PNODE pHead)
{
    PNODE p = pHead->pNext;		//p指向首节点
    if (NULL != p)
    {
        printf("%d\t",p->data);
        p = p->pNext;
    }
    printf("\n");
    
    return;
}

bool is_empty(PNODE pHead)
{
    if (NULL == pHead->pNext)
        return true;
	else
    	return false;
}

int length_list(PNODE pHead)
{
    int len = 0;
	PNODE p = pHead->pNext;
	while(NULL != p)
	{
        ++len;
        p = p->pNext;
	}
	return len;
}

bool insert_list(PNODE pHead, int pos, int val)
{//这里算上了头结点，所以在第2个位置插入元素，也就是把下标为2及以后的元素往后移，将新节点放到下标为2的位置
    int i;
	PNODE p = pHead;
 	
    //循环到p指向pos-1的位置
 	while( NULL != p && i < pos - 1)
 	{
   		p = p->pNext;
     	++i;
	}
	if (NULL == p || i > pos -1)
	{
		return false;
	}
	
    //插入的数申请内存
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	if (NULL == pNew)
    {
        printf("分配内存失败，程序终止！\n");
        exit(-1);
    }
	pNew->data = val;
	PNODE q = p->pNext;
	p->pNext = pNew;
	pNew->pNext = q;
	
    return ture;
}

bool delete_list(PNODE pHead, int pos, int *pVal)
{
    int i;
	PNODE p = pHead;
	
    //循环到p指向pos-1的位置
	while( NULL != p->pNext && i < pos - 1)
	{
		p = p->pNext;
     	++i;
	}
	if (NULL == p->pNext || i > pos - 1)
	{
        return false;
	}
	PNODE q = p->pNext;
    *pVal = p->data;
    p->pNext = q->pNext;
    free(q);
    q=NULL;
    
    return true;
}

//选择排序
void sort_list(PNODE pHead)
{
    int i,j,t;
    PNODE p,q;
    int len = length_list(pHead);
    for(i=0,p=pHead->pNext; i<len-1; i++,p=p->pNext)
     {
         for(j=i+1,q=p->pNext; j<len; j++,q=q->pNext)
         {
             if(p->data > q->data)
             {
                 t = p->data;
                 p->data = q->data;
                 q->data = t;
             }
         }
     }
    return;
}

2.3. 线性结构的两种常见应用之一栈

定义：一种可以实现“先进后出”的存储结构
分类：静态栈；动态栈(链式栈)
算法：压栈；出栈
应用：函数调用；中断；表达式求值；内存分配；缓冲处理；迷宫

#include <stdio.h>

void f(int k)
{
    int m;
    double *q = (double *)malloc(sizeof(double) * 50);
}

int main()
{
    int i = 10;
    int *p = (int *)malloc(sizeof(int) * 50);
    return 0;
}
/**
k,m,q,i,p都分配在栈中，而malloc分配的空间是在堆中
*/

/**
动态栈利用头插法链表
*/
# include <stdio.h>
# include <malloc.h>
# include <stdlib.h>

typedef struct Node
{
    int data;
    struct Node * pNext;
}NODE, * PNODE;

typedef struct Stack
{
    PNODE pTop;			//pTop是尾指针，指向尾结点	
    PNODE pBottom;		//pBottom是头指针，指向头结点
}STACK, * PSTACK; //PSTACK 等价于 struct STACK *

//函数声明
void init(PSTACK);
void push(PSTACK, int); //压栈
void traverse(PSTACK);
bool pop(PSTACK, int *); //出栈
void clear(PSTACK);

int main()
{
    STACK S; //STACK 等价于 struct Stack
    int val;

    init(&S); //目的是造出一个空栈
    push(&S, 1); //压栈
    push(&S, 2);
    push(&S, 3);
    push(&S, 4);
    push(&S, 5);
    push(&S, 6);
    traverse(&S);//遍历输出

    if( pop(&S, &val) )
        printf("出栈成功，出栈的元素是%d\n",val);
    else
        printf("出栈失败！\n");
    
    clear(&S);
    traverse(&S);

    

    return 0;
}

void init(PSTACK pS)
{
    pS->pTop = (PNODE)malloc(sizeof(NODE));
    if(NULL == pS->pTop)
    {
        printf("动态内存分配失败！\n");
        exit(-1);
    }
    else
    {//创建一个空栈
        pS->pBottom = pS->pTop;
        pS->pBottom->pNext = NULL; //也可写pS->pTop->pNext = NULL;
    }
}

void push(PSTACK pS,int val)
{
    PNODE pNew = (PNODE)malloc(sizeof(NODE));

    pNew->data = val;
    pNew->pNext = pS->pTop; //pS->pTop不能改成pS->pBottom
    pS->pTop = pNew;

    return;
}

void traverse(PSTACK pS)
{
    PNODE p = pS->pTop;

    while(p != pS->pBottom)
    {
        printf("%d ",p->data);
        p = p->pNext;
    }
    printf("\n");

    return;
}

//判断栈是否为空
bool empty(PSTACK pS)
{
    if(pS->pTop == pS->pBottom)
        return true;
    else
        return false;
}

//把pS所指向的栈出栈，并把出栈的元素存入pVal形参所指向的变量中，如果出栈失败，返回false，否则返回true
bool pop(PSTACK pS, int * pVal)
{
    if( empty(pS) ) //pS本身存放的就是S的地址
    {
        return false;
    }
    else
    {
        PNODE r = pS->pTop;
        * pVal = r->data;
        pS->pTop = r->pNext;
        free(r);
        r = NULL;
        return true;
    }
}

//clear清空
void clear(PSTACK pS)
{
    if(empty(pS))
        return;
    else
    {
        PNODE p = pS->pTop;
        PNODE q = NULL;

        while(p != pS->pBottom)
        {
            //q永远是p的下个元素，最后p,q都指向了头结点
            q = p->pNext;
            free(p);
            p = q;
        }
        pS->pTop = pS->pBottom;
    }
}

2.4 线性结构的两种常见应用之二队列

定义：一种可以实现“先进先出”的存储结构
分类
- 链式队列——用链表实现
- 静态队列——用数组实现
  1. 静态队列通常都必须是循环队列
  2. 循环队列的讲解
    - 静态队列为什么必须是循环队列
      
      如果不是循环队列，静态队列(数组)里的空间只能使用一次
    - 循环队列需要几个参数来确定
      
      需要两个参数来确定队列，front 和 rear
    - 循环队列各个参数的含义
      队列初始化：front和rear的值都是0
      
      队列非空：front代表的是队列的第一个元素，rear代表的是队列的最后一个有效元素的下一个位置
      
      队列空：front和rear的值相等，但不一定是0
    - 循环队列入队伪算法
      将值存入rear所代表的位置
      
      rear = (rear + 1) % 数组的长度
    - 循环队列出队伪算法
      front = (front + 1) % 数组的长度
    - 如何判断循环队列是否为空
      
      if (front == rear)
    - 如何判断循环队列是否已满
      两种方式：
      
      if ((rear + 1 % 数组的长度) == front)（通常使用这种方式）
      
      元素个数 = 数组长度 - 1
  3. 队列的具体应用：所有和时间有关的操作都与队列有关

#include <stdio.h>
#include <malloc.h>

typedef struct Queue
{
    int * pBase;
    int front;
    int rear;
}QUEUE;

void init(QUEUE *);
bool en_queue(QUEUE *, int); //入队
void traverse_queue(QUEUE *);
bool full_queue(QUEUE *);
bool out_queue(QUEUE *, int *);
bool emput_queue(QUEUE *);

int main ()
{
    QUEUE Q;
    int val;

    init(&Q);
    en_queue(&Q, 1);
    en_queue(&Q, 2);
    en_queue(&Q, 3);
    en_queue(&Q, 4);
    en_queue(&Q, 5);
    en_queue(&Q, 6);
    en_queue(&Q, 7);
    en_queue(&Q, 8);    
    traverse_queue(&Q);

    if( out_queue(&Q, &val) )
        printf("出队成功，队列出队的元素是：%d\n", val);
    else
        printf("出队失败！\n");
    traverse_queue(&Q);
    
    return 0;
}

void init(QUEUE *pQ)
{
    pQ->pBase = (int *)malloc(sizeof(int) * 6);
    pQ->front = 0;
    pQ->rear = 0;
}

bool full_queue(QUEUE * pQ)
{
    if( (pQ->rear + 1) % 6 == pQ->front )
        return true;
    else
        return false;
}

bool en_queue(QUEUE * pQ, int val)
{
    if( full_queue(pQ) )
    {
        return false;
    }
    else
    {
        pQ->pBase[pQ->rear] = val;
        pQ->rear = (pQ->rear + 1) % 6;
        return true;
    } 
}

void traverse_queue(QUEUE * pQ)
{
    int i = pQ->front;

    while(i != pQ->rear)
    {
        printf("%d ", pQ->pBase[i]);
        i = (i+1) % 6;
    }
    printf("\n");

    return;
}

//判断队列是否为空
bool emput_queue(QUEUE * pQ)
{
    if( pQ->front == pQ->rear)
        return true;
    else
        return false;
}

bool out_queue(QUEUE * pQ, int * pVal)
{
    if ( emput_queue(pQ) )
    {
        return false;
    }
    else
    {
        *pVal = pQ->pBase[pQ->front];
        pQ->front = (pQ->front + 1) % 6;
        return true;
    }
    
}

2.5 递归

定义：一个函数自己直接或间接调用自己

递归满足三个条件：

递归必须得有一个明确的中止条件
该函数所处理的数据规模必须在递减
这个转化必须是可解的

循环和递归的区别：

递归
- 易于理解
- 速度慢
- 存储空间大
循环
- 不易理解
- 速度快
- 存储空间小

函数的调用：

当在一个函数的运行期间调用另一个函数时，在运行被调函数之前，系统需要完成三件事：
1. 将所有的实际参数、返回地址等信息传递给被调函数保存。
2. 为被调函数的局部变量（也包括行参）分配存储空间。
3. 将控制转移到被调函数的入口。
从被调函数返回函数之前，系统也要完成三件事：
1. 保存被调函数的返回结果。
2. 释放被调函数所占的存储空间。
3. 依照被调函数保存的返回地址将控制转移到调用函数。
当有多个函数相互调用时，按照“后调用先返回”的原则，上述函数之间信息传递和控制转移必须借助“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就在栈顶分配一个存储区，进行压栈操作，每当一个函数退出时，就释放它的存储区，就做出栈操作，当前运行的函数永远都在栈顶位置。
A函数调用A函数和A函数调用B函数在计算机看来是没有任何区别的，只不过用我们日常的思维方式理解比较怪异而已！

递归的应用：

树和森林就是以递归的方式定义的
树和图的很多算法
很多数学公式：例如斐波拉契数列

2.5.1 1+2+3+…+100的和

# include <stdio.h>

long sum(int n)
{
    //常量不能被赋值，所以如果误写成1 = n会报错
    if(1 == n)
        return 1；
    else
        return n + sum(n-1);
}

int main()
{
    printf("%ld\n",sum(100));
    return 0;
}

2.5.2 求阶乘

# include <stdio.h>

//假定n的值是1或大于1的值
long f(long n)
{
    if( 1 == n )
        return 1;
    else
        return f(n-1) * n;
}

int main()
{
    printf("%d\n", f(5));		//120
    //printf("%d\n", f(100));	//0,因为超过long型的最大范围
    
    return 0;
}

2.5.3 汉诺塔

# include <stdio.h>

void tower_of_hanoi(int n, char A, char B, char C)
{
/*
    如果是1个盘子
        直接将A柱子上的盘子从A移到C
    否则
        先将A柱子上的n-1个盘子借助C移到B
        直接将A柱子上的盘子从A移到C
        最后将B柱子上的n-1个盘子借助A移到C
*/
    if(1 == n)
        //盘子从上往下编号
        printf("将编号为%d的盘子直接从%c柱子移到%c柱子\n", n, A, C);
    else
    {
        tower_of_hanoi(n-1, A, C, B);
        printf("将编号为%d的盘子直接从%c柱子移到%c柱子\n", n, A, C);
        tower_of_hanoi(n-1, B, A, C);
    }
}

int main()
{
    char ch1 = 'A';
    char ch2 = 'B';
    char ch3 = 'C';
    int n;

    printf("请输入要移动盘子的个数：");
    scanf("%d", &n);

    tower_of_hanoi(n,'A','B','C');
}

2.6 串

串中元素逻辑关系与线性表的相同，串可以采用与线性表相同的存储结构。串有顺序存储结构(顺序串)和链式存储结构(链串)。

2.6.1 串的顺序存储结构

#define MAXLEN 255
typedef struct
{
    char ch[MAXLEN + 1];	//存储串的一维数组
    int length;				//串的当前长度
}SString;

2.6.2 串的链式存储结构——块链结构

#define CHUNKSIZE 80		//块的大小由用户定义
typedef struct Chunck
{
    char ch[CHUNKSIZE];
    struct Chunk *next;
}Chunk;

typedef struct
{
    Chunk *head, *tail;		//串的头指针和尾指针
    int length;				//串的当前长度
}LString;					//字符串的块链结构

2.6.3 串的模式匹配算法

算法目的：确定主串中所含子串(模式串)第一次出现的位置。

2.6.3.1 BF算法

Brute-Force简称为BF算法，亦称简单匹配算法。采用穷举法的思路。

#define MAXLEN 255
typedef struct
{
    char ch[MAXLEN + 1];	//存储串的一维数组
    int length;				//串的当前长度
}SString;

int Index_BF(SString S, SString T, int pos)
{
    int i=pos, j=1;			//下标从1开始，下标0经常存储串的长度
    while(i<=S.length && j<=T.length)
    {
        if(s.ch[i] == t.ch[j])
        {
            i++;
            j++;
        }
        else
        {
            i = i - j + 2;	//i回到主串下一个字符
            j = 1;			//j重头开始
        }
    }
    if(j<=T.length)
        return i - T.length;
    else
        return 0;
}

时间复杂度：若n为主串长度，m为子串长度。

最好的情况是开头就是需要匹配的子串，所以时间复杂度为O(m)。

最坏情况是主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位各比较了m次，最后m位也各比较了1次。

$总次数为：(n-m)*m+1*m=(n-m+1)*m$

若m<<n，则算法复杂度为O(n*m)。

2.6.3.2 KMP算法

天勤率辉 KMP算法易懂版

#define MAXLEN 255
typedef struct
{
    char ch[MAXLEN + 1];	//存储串的一维数组
    int length;				//串的当前长度
}SString;

void get_next(SString T, int &next[])
{
    int i = 1;
    next[1] = 0;
    int j = 0;
    while(i < T.length)
    {
        if(j == 0 || T.ch[i] == T.ch[j])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
            j = next[j];
    }
}

int Index_KMP(SString S, SString T, int pos)
{
    int i=pos, j=1;			//下标从1开始，下标0经常存储串的长度
    while(i<S.length && j<T.length)
    {
        if(j == 0 || s.ch[i] == t.ch[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];	//i不变，j后退
        }
    }
    if(j > T.length)
        return i - T.length;
    else
        return 0;
}

KMP的时间复杂度为O(n+m)。

2.7 数组

2.7.1 特殊矩阵的压缩存储

若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间。

一些特殊矩阵有：对称矩阵、对角矩阵、三角矩阵、稀疏矩阵(矩阵中非零元素的个数较少，一般小于5%)

2.7.2 对称矩阵

在n*n的矩阵a中，满足如下性质：

$a_{ij} = a_{ji}(1\le i,j\le n)$

存储方法：利用一维数组只存储下(或上)三角(包括主对角线)的数据元素，共占用个元素空间。

2.7.3 三角矩阵

对角线以下(或以上)的数据元素(不包括对角线)全部为常数C。

存储方法：重复元素C共享一个元素存储空间，共占用个元素空间。

2.7.4 对角矩阵

在n*n的方阵中，所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。

存储方法：用二维数组以对角线的顺序存储。

2.7.5 稀疏矩阵

稀疏矩阵顺序存储结构：三元组。

三元组顺序表又称有序的双下标法。

优点：非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。

缺点：不能随机存取。若按行号存取某一行中的非零元，则需从头开始进行查找。

稀疏矩阵链式存储结构：十字链表。

优点：它能够灵活地插入因运算而产生的新的非零元素，删除因运算而产生的新的零元素，实现矩阵的各种运算。

2.8 广义表

广义表(又称列表Lists)是个元素$a0,a_1,…,a{n-1} $的有限序列，其中每一个$ a_i$或者是原子，或者是一个广义表。

广义表通常记作，其中LS为表名，n为表的长度，每一个为表的元素。习惯上，一般用大写字母表示广义表，小写字母表示原子。

表头：若LS非空()，则其第一个元素就是表头，记作。注：表头可以是原子，也可以是子表。

表尾：除表头之外的其它元素组成的表，记作。注：表尾不是最后一个元素，而是一个子表。

广义表可以看成是线性表的推广，线性表是广义表的特例。广义表的结构相当灵活，在某种前提下，它可以兼容线性表、数组、树和有向图等各种常用的数据结构。

当二维数组的每行(或每列)作为子表处理时，二维数组即为一个广义表。另外，树和有向图也可以用广义表来表示。

比如操作系统中的“多级目录结构”。

3. 非线性结构

3.1 树

树的定义

专业定义：
1. 有且只有一个称为根的节点
2. 有若干个互不相交的子树，这些子树本身也是一颗树
通俗定义：
1. 树是由节点和边组成
2. 每个节点只有一个父节点但可以有多个子节点
3. 但有一个节点例外，该节点没有父节点，此节点称为根节点
专业术语：
- 节点，父节点，子节点
- 子孙，堂兄弟
- 深度：从根节点到最底层节点的层数称之为深度，根节点是第一层
- 叶子节点：没有子节点的节点
- 非终端节点：实际就是非叶子节点
- 度：子节点的个数

树的分类

一般树：任意一个节点的子节点的个数都不受限制
二叉树：任意一个节点的子节点个数最多两个，且子节点的位置不可更改
- 分类
  - 一般二叉树
  - 满二叉树：在不增加树层数的前提下，无法再多添加一个节点的二叉树就是满二叉树
  - 完全二叉树：如果只是删除了满二叉树最底层最右边的连续若干个节点，这样形成的二叉树就是完全二叉树。（满二叉树是完全二叉树的一个特例）
森林：n个互不相交的树的集合

树的存储

二叉树的存储
- 连续存储【完全二叉树】
  
  优点：查找某个节点的父节点和子节点（也包括判断有没有子节点）速度很快
  
  缺点：耗用内存空间过大
- 链式存储
一般树的存储
- 双亲表示法：求父节点方便
- 孩子表示法：求子节点方便
- 双亲孩子表示法：求父节点和子节点都很方便
- 二叉树表示法：把一个普通树转化成二叉树来存储
  
  具体转换方法：
  
  设法保证任意一个节点的左指针域指向它的第一个孩子，右指针域指向它的亲兄弟，只要满足此条件，就可以把一个普通树转化为二叉树。
  
  一个普通树转化成的二叉树一定没有右子树。
森林的存储

先把森林转化为二叉树，再存储二叉树：

将相邻的父节点依次作为节点的右子树再对各父节点进行转化

树的操作

遍历
- 先序遍历【先访问根节点】
  1. 先访问根节点
  2. 再先序访问左子树
  3. 最后先序访问右子树
    
    例子：
    1
    2
    3
    4
    5
    6
    7
    A
    / \
    B C
    / \ \
    D E F
    / \ \ / \
    G H I J k
    先序遍历结果：ABDGHEICFJK
- 中序遍历【中间访问根节点】
  1. 中序遍历左子树
  2. 再访问根节点
  3. 再中序遍历右子树
    
    例子：
    1
    2
    3
    4
    5
    6
    7
    A
    / \
    B C
    / \ \
    D E F
    / \ \ / \
    G H I J k
    中序遍历结果：GDHBEIACJFK
- 后序遍历【最后访问根节点】
  1. 先中序遍历左子树
  2. 再中序遍历右子树
  3. 最后遍历根节点
    
    例子：
    1
    2
    3
    4
    5
    6
    7
    A
    / \
    B C
    / \ \
    D E F
    / \ \ / \
    G H I J k
    后序遍历结果：GHDIEBJKFCA

已知两种遍历序列求原始二叉树

通过先序和中序或者中序和后序我们可以还原出原始二叉树，但是通过先序和后序是无法还原出原始二叉树。

例子1：

先序：ABCDEFGH，中序：BDCEAFHG，求后序？
分析：按照先序的定义，A为最外层根节点，按照中序的定义和前面的结论可知BDCE为A节点的左子树节点，FHG为A节点的右子树，再依次按照两个遍历定义可以推出原始二叉树为：        
			 A       
		    / \ 
       	   B   F
               \    \
             	C    G
              / \  /  
             D  E  H
那么此二叉树的后序为：DECBHGFA

例子2：

先序：ABDGHCEFI，中序：GDHBAECIF，求后序？
分析：按照先序的定义得到A为最外层根节点，再根据中序结果可知GDHB为A的左子树，ECIF为A的右子树；B先出现在先序结果中可知B为左子树的根节点，再根据中序结果知B节点没有右子树，GDH均为B节点的左子树，再根据先序结果D先出现，知D为B左子树的根节点，再根据先序发现G在D的后面且中序中G在D的前面得出G为D左子树的根节点，那么D的右子树的根节点就是H了，依次类推A的右子树，得出原始二叉树为：      
	 A
	/ \
	B   C
      /   / \
    D   E   F
  / \     /
G   H   I
那么此二叉树的后序为：GHDBEIFCA

例子3：

中序：BDCEAFHG，后序：DECBHGFA，求先序？
分析：由后序结果知A为最外层根节点，再根据中序结果知BDCE为A节点的左子树，FHG为A的右子树；A的左子树中B最靠近A那么根据后序规则得出B为左子树的根节点，再根据中序结果B在结果的第一位，由中序规则知B没有左子树，DCE均为B的右子树，在DCE中后序结果C最靠近B，得出C为B的右子树的根节点，再依据中序结果知C前面是D后面是E得出D为C的左子树，E为C的右子树，同理可以推出A的右子树，得出原始二叉树为：        
		     A       
			/ \
               B   F
                \   \
        	      C   G
                / \  /
               D   E H
那么此二叉树的先序为：ABCDEFGH

树的应用

树是数据库中数据组织的一种重要形式
操作系统子父进程的关系本身就是一棵树
面向对象语言中类的继承关系本身就是一棵树
赫夫曼树

3.1.1 链式二叉树的遍历

# include <stdio.h>
# include <malloc.h>

struct BTNode
{
    int data;
    struct BTNode * pLchild; //p是指针 L是左 child是孩子
    struct BTNode * pRchild;
};

void PreTraverseBTree(struct BTNode *);
void InTraverseBTree(struct BTNode *);
void PostTraverseBTree(struct BTNode *);
struct BTNode * CreateBTree();

int main()
{
    struct BTNode * pT = CreateBTree();

    PreTraverseBTree(pT); //先序
    InTraverseBTree(pT); //中序
    PostTraverseBTree(pT); //后序

    return 0;
}

void PreTraverseBTree(struct BTNode * pT)
{
    if (NULL != pT)
    {
        printf("%c\n", pT->data);

        if (NULL != pT->pLchild)
        {
            PreTraverseBTree(pT->pLchild); //pT->pLchild可以代表整个左子树
        }

        if (NULL != pT->pRchild)
        {
            PreTraverseBTree(pT->pRchild);
        }
    }
/*
    先访问根节点
    再先序访问左子树
    再先序访问右子树
*/
}

void InTraverseBTree(struct BTNode * pT)
{
    if (NULL != pT)
    {
        if (NULL != pT->pLchild)
        {
            InTraverseBTree(pT->pLchild); //pT->pLchild可以代表整个左子树
        }

        printf("%c\n", pT->data);

        if (NULL != pT->pRchild)
        {
            InTraverseBTree(pT->pRchild);
        }
    }
/*
    先访问左子树
    再访问根
    再访问右子树
*/
}

void PostTraverseBTree(struct BTNode * pT)
{
    if (NULL != pT)
    {
        if (NULL != pT->pLchild)
        {
            PostTraverseBTree(pT->pLchild); //pT->pLchild可以代表整个左子树
        }

        if (NULL != pT->pRchild)
        {
            PostTraverseBTree(pT->pRchild);
        }

        printf("%c\n", pT->data);
    }
/*
    先访问左子树
    再访问右子树
    再访问根
*/
}

struct BTNode * CreateBTree()
{
    struct BTNode * pA = (struct BTNode *)malloc(sizeof(struct BTNode));
    struct BTNode * pB = (struct BTNode *)malloc(sizeof(struct BTNode));
    struct BTNode * pC = (struct BTNode *)malloc(sizeof(struct BTNode));
    struct BTNode * pD = (struct BTNode *)malloc(sizeof(struct BTNode));
    struct BTNode * pE = (struct BTNode *)malloc(sizeof(struct BTNode));

    pA->data = 'A';
    pB->data = 'B';
    pC->data = 'C';
    pD->data = 'D';
    pE->data = 'E';

    pA->pLchild = pB;
    pA->pRchild = pC;
    pB->pLchild = pB->pRchild = NULL;
    pC->pLchild = pD;
    pC->pRchild = NULL;
    pD->pLchild = NULL;
    pD->pRchild = pE;
    pE->pLchild = pE->pRchild = NULL;

    return pA;
}

3.1.2 哈夫曼树(最优二叉树)

结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树。

权(weight)：将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。

结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积。

树的路径长度：从树根到每一个结点的路径长度之和，记作TL。

树的带权路径长度：树中所有叶子结点的带权路径长度之和，记作WPL。

哈夫曼树就是带权路径长度(WPL)最短的二叉树(最优二叉树)。

在哈夫曼算法中，初始时有n棵二叉树，要经过n-1次合并最终形成哈夫曼树。经过n-1次合并产生n-1个新结点，且这n-1个新结点都是具有两个孩子的分支结点。可见，哈夫曼树中共有n+n-1=2n-1个结点，且其所有的分支结点的度均不为1。

typedef struct
{
    int weight;
    int parent, lch, rch;
}HTNode, *HuffmanTree;

void CreateHuffmanTree(HuffmanTree HT, int n)
{
    if(n <= 1)
        return;
    m = 2 * n - 1;	//数组共2n-1个元素
    HT = new HTNode[m+1];	//0号单元未用，HT[m]表明根结点
    for(i=1; i<=m; i++)
    {//初始化哈夫曼树
        HT[i].lch = 0;
        HT[i].rch = 0;
        HT[i].parent = 0;
    }
    for(i=1; i<=n; i++)
        cin >> HT[i].weight;	//输入前n个元素的权值
    
    //建立哈夫曼树
    for(i=n+1; i<=m; i++)
    {
        Select(HT, i-1, s1, s2);//合并产生n-1个结点，在HT[k](1<=k<=i-1)中选择两个其双亲域为0，且权值最小的结点，并返回它们在HT中的序号s1和s2
        HT[s1].parent = i;
        HT[s2].parent = i;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
    }
}

3.1.3 哈夫曼树的应用——哈夫曼编码

将编码设计为长度不等的二进制编码，即让待传字符串中出现次数较多的字符采用尽可能短的编码，则转换的二进制字符串便可能减少。

关键：设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的前缀，这种编码称作前缀编码。

方法：

统计字符集中每个字符在电文中出现的平均概率(概率越大，要求编码越短)
利用哈夫曼树的特点：权越大的叶子离根越近，将每个字符的概率值作为权值，构造哈夫曼树。概率越大的结点，路径越短。
在哈夫曼树的每个分支上标上0或1：

结点的左分支标0，右分支标1

把从根到每个叶子的路径上的标号连接起来，作为该叶子代表的字符的编码

思考：

为什么哈夫曼编码能够保证是前缀编码？

因为没有一片树叶是另一片树叶的祖先，所以每个叶结点的编码就不可能是其它叶结点编码的前缀。
为什么哈夫曼编码能够保证字符编码总长最短？

因为哈夫曼树的带权路径长度最短，故字符编码的总长最短。

void CreateHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)
{//从叶子到根逆向求每个字符的哈夫曼编码，存储在编码表HC中
    HC = new char *[n+1];		//分配n个字符编码的头指针矢量
    cd = new char [n];			//分配临时存放编码的动态数组空间
    cd[n-1] = '\0';				//编码结束符
    for(int i=1; i<=n; i++)		//逐个字符求哈夫曼编码
    {
        start = n - 1;
        c = i;
        f = HT[i].parent;
        while(f != 0)			//从叶子结点开始向上回溯，直到根结点
        {
            --start;			//回溯一次start向前指一个位置
            if(HT[f].lch == c)
                cd[start] = '0';//结点c是f的左孩子，置0
            else
                cd[start] = '1';//右孩子置1
            c = f;				//继续向上回溯
            f = HT[f].parent;	//求出第i个字符的编码
        }
        HC[i] = new char [n-start];
        strcpy(HC[i], &cd[start]);//将求得的编码从临时空间cd复制到HC的当前行中
    }
    delete cd;
}

3.2 图

离散数学的知识，我恨！我不想再记多一门课的笔记了呜呜呜。

3.2.1 图的概念

图：G = (V, E)，V是顶点(数据元素)的有穷非空集合，E是边的有穷集合。

无向图：每条边都是无方向的。

有向图：每条边都是有方向的。

完全图：任意两个点都有一条边相连。

顶点的度：与该顶点相关联的边的数目，记为TD(v)

在有向图中，顶点的度等于该顶点的入度与出度之和。顶点v的入度是以v为终点的有向边的条数，记作ID(v)；顶点v的出度是以v为始点的有向边的条数，记作OD(v)。

路径：接续的边构成的顶点序列。

路径长度：路径上边或弧的数目/权值之和。

回路(环)：第一个顶点和最后一个顶点相同的路径。

简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径。

简单回路(简单环)：除路径起点和终点相同外，其余顶点均不相同的路径。

连通图(强连通图)：在无(有)向图G=(V,{E})中，若对任何两个顶点v、u都存在从v到u的路径，则称G是连通图(强连通图)。

权：图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。

网：带权的图。

3.2.2 图的存储结构

图的逻辑结构：多对多。

图没有顺序存储结构，但可以借助二维数组来表示元素间的关系。数组表示法：邻接矩阵。

多重链表：邻接表、邻接多重表、十字链表。

3.2.2.1 邻接矩阵

建立一个顶点表(记录各个顶点信息)和一个邻接矩阵(表示各个顶点之间关系)。设图A=(V,E)有n个顶点，则

i	0	1	2	…	n-1
Vexs[i]	V1	V2	V3	…	Vn

图的邻接矩阵是一个二维数组A.arcs[n][n]，定义为：

$A.arcs[i][j]=\begin{cases}1，如果<i,j>\in E或者(i,j)\in E\\\\ 0，否则\end{cases}$

无向图的邻接矩阵是对称的。顶点i的度=第i行(列)中1的个数。完全图的邻接矩阵中，对角元素为0，其余为1。

在有向图的邻接矩阵中，第i行表示以结点为尾的弧(即出度边)，第i列表示以结点为头的弧(即入度边)。

有向图的邻接矩阵可能是不对称的。顶点的出度=第i行元素之和，顶点的入度=第i列元素之和，顶点的度=第i行元素之和+第i列元素之和。

网(即有权图)的邻接矩阵表示法：

$A.arcs[i][j]=\begin{cases}W_{ij}，<v_i,v_j>或(v_i,v_j)\in VR\\\\ \infty，无边(弧)\end{cases}$

//邻接矩阵的存储表示：用两个数组分别存储顶点表和邻接矩阵
#define MaxInt 32767	//表示无穷
#define MVNum 100		//定义最大顶点数
typedef char VerTexType;//设顶点的数据类型为字符型
typedef int ArcType;	//边的权值
typedef struct
{
    VerTexType vexs[MVNum];	//顶点表
    ArcType arcs[MVNum][MVNum];//邻接矩阵
    int vexnum,arcnum;		//图的当前点和边数
}AMGraph;

算法思想：

输入总顶点数和总边数
依次输入点的信息存入顶点表中
初始化邻接矩阵，使每个权值初始化为极大值
构造邻接矩阵

Status CreateUDN(AMGraph &G)
{//采用邻接矩阵表示法，创建无向网G
    cin >> G.vexnum >> G.arcnum;//输入总顶点数和总边数
    for(int i=0; i<G.vexnum; i++)
        cin >> G.vexs[i];		//依次输入点的信息
    for(i=0; i<G.vexnum; i++)
        for(int j=0; j<G.vexnum; j++)
            G.arcs[i][j] = MaxInt;	//初始化邻接矩阵
    for(int k=0; k<G.vexnum; k++)
    {//构造邻接矩阵
        cin >> v1 >> v2 >> w;	//输入一条边所依附的顶点及边的权值
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);	//确定v1和v2在G中的位置
        G.arcs[i][j] = w;		//边<v1,v2>的权值置位w
        G.arcs[j][i] = G.arcs[i][j];//无向图，所以是对称的
    }
    return OK;
}

int LocateVex(AMGraph G, VertexType u)
{//图G中查找顶点u，存在则返回顶点表中的下标；否则返回-1
    int i;
    for(i=0; i<G.vexnum; i++)
        if(u == G.vexs[i])
            return i;
    return -1;
}

邻接矩阵存储图的优点：

直观、简单、好理解
方便检查一堆顶点间是否存在边
方便找任一顶点的所有“邻接点”(有边直接相连的顶点)
方便计算任一顶点的“度”(从该点发出的边为“出度”，指向该点的边为“入度”)

无向图：对应行(或列)非0元素的个数

有向图：对应行非0元素的个数为“出度”，对应列非0元素的个数为“入度”

缺点：

不便于增加和删除顶点
浪费空间——存稀疏图(点很多而边很少)有大量无效元素()
浪费时间——统计稀疏图中一共有多少条边()

3.2.2.2 邻接表

顶点：按编号顺序将顶点数据存储在一维数组中。

关联同一顶点的边(以顶点为尾的弧)：用线性链表存储。

无向图邻接表的特点：

邻接表不唯一
若无向图中有n个顶点、e条边，则其邻接表需n个头结点和2e个表结点。适宜存储稀疏图。空间复杂度O(n+2e)
无向图中顶点的度为第i个单链表中的结点数

有向图的邻接表的特点：

顶点的出度为第i个单链表中的结点个数
顶点的入度为整个单链表中邻接点域值是i-1的结点个数
由于找出度容易，找入度难，所以可以弄一个逆邻接表存储入度边

#define MVNum 100		//定义最大顶点数
typedef char VerTexType;
typedef struct ArcNode	//边结点
{
    int adjvex;					//该边所指向的顶点的位置
    struct ArcNode * nextarc;	//指向下一条边的指针
    OtherInfo info;				//和边相关的信息，权值等
}ArcNode;

typedef struct VNode
{
    VerTexType data;		//顶点信息
    ArcNode *firstarc;		//指向第一条依附该顶点的边的指针
}VNode, AdjList[MVNum];		//AdjList表示邻接表类型

typedef struct
{
    AdjList vertices;
    int vexnum, arcnum;		//图的当前顶点数和弧数
}ALGraph;

算法思想：

输入总顶点数和总边数
建立顶点表

依次输入点的信息存入顶点表中

使每个表头结点的指针域初始化为NULL
创建邻接表

依次输入每条边依附的两个顶点

确定两个顶点的序号i和j，建立边结点

将此边结点分别插到和对应的两个比链表的头部

Status CreateUDG(ALGraph &G)
{//采用邻接表创建无向图G
    cin >> G.vexnum >> G.arcnum;//输入总顶点数和总边数
    for(int i=0; i<G.vexnum; i++)
    {
        cin >> G.vertices[i].data;//输入顶点值
        G.vertices[i].firstarc = NULL;//初始化表头结点的指针域
    }
    for(int k=0; k<G.arcnum; k++)//输入各边，构造邻接表
    {
        cin >> v1 >> v2;		//输入一条边依附的两个顶点
        i = LocateVex(G, v1);
        j = LOcateVex(G, v2);
        
        p1 = new ArcNode;			//生成一个新的边结点p1
        p1->adjvex = j;				//邻接点序号为j
        p1->nextarc = G.vertices[i].firstarc;//头插法
        G.vertices[i].firstarc = p1;//将新结点p1插入顶点vi的边表头部

        p2 = new ArcNode;
        p2->adjvex = i;
        p2->nextarc = G.vertices[j].firstarc;
        G.vertices[j].firstarc = p2;//将新结点p1插入顶点vi的边表头部
    }
    return OK;
}

3.2.2.3 邻接矩阵和邻接表的关系

联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。

区别：①对于任一确定的无向图，邻接矩阵是唯一的(行列号与顶点编号一致)，但邻接表不唯一(链接次序与顶点编号无关)；②邻接矩阵的空间复杂度为，而邻接表的空间复杂度为。

用途：邻接矩阵多用于稠密图，邻接表多用于稀疏图。

3.2.2.4 十字链表

有向图的邻接表有个缺点就是求出度或入度难，所以引入了十字链表。

十字链表是有向图的另一种链式存储结构，可以看成是将有向图的邻接表和逆邻接表结合起来形成的一种链表。

有向图中的每一条弧对应十字链表中的一个弧结点，同时有向图中的每个顶点在十字链表中对应一个结点，叫做顶点结点。

3.2.2.5 邻接多重表

邻接多重表解决无向图每条边都要存储两遍的缺点。

3.2.3 图的遍历

遍历定义：从已给的连通图种某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。

遍历实质：找每个顶点的邻接点的过程。

图的特点：图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。

怎么避免重复访问？

解决思路：设置辅助数组visited[n]，用来标记每个被访问过的顶点。初始状态visited[i]为0，顶点i被访问，改visited[i]为1，防止被多次访问。

3.2.3.1 深度优先搜索(DFS)

一条路走到黑，不撞南墙不回头。

void DFS(AMGraph G, int V)
{//采用邻接矩阵实现图的深度优先遍历
    cout << v;				//访问第v个结点
    visited[v] = true;
    for (w=0; w<G.vexnum; v++)//依次检查邻接矩阵v所在的行
        if((G.arcs[v][w]!=0) && (!visited[w]))
            DFS(G,w);
    //w是v的邻接点，如果w未访问，则递归调用DFS
}

用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为。

用邻接表来表示图，虽然有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，时间复杂度为。

稠密图适于在邻接矩阵上进行深度遍历；稀疏图适于在邻接表上进行深度遍历。

3.2.3.2 广度优先搜索(BFS)

方法：从图的某一结点出发，首先依次访问该结点的所有邻接顶点，再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点，重复此过程，直至所有顶点均被访问为止。

void BFS(Graph G, int v)
{//采用邻接表实现图的广度优先遍历
    cout << v;
    visited[v] = true;
    InitQueue(Q);		//初始化辅助循环队列，置空
    EnQueue(Q, v);		//v进队
    while(!QueueEmpty(Q))
    {
        DeQueue(Q, u);	//队列非空队头元素并置u
        for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w))
            if(!visited[w])
            {//w为u的尚未访问的邻接顶点
                cout << w;
                visited[w] = true;//w进队
                EnQueue(Q,w);
            }
    }
}

如果使用邻接矩阵，则BFS遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为。

用邻接表来表示图，虽然有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，时间复杂度为。

3.2.3.3 DFS和BFS的比较

空间复杂度相同，都是O(n)(借用了堆栈或队列)
时间复杂度只与存储结构(邻接矩阵或邻接表)有关，而与搜索算法无关

3.2.4 图的应用

3.2.4.1 最小生成树

生成树：所有顶点均由边连接在一起，但不存在回路的图。

一个图可以有许多棵不同的生成树。

所有生成树具有以下共同特点：

生成树的顶点个数与图的顶点个数相同
生成树是图的极小连通子图，去掉一条边则非连通
一个有n个顶点的连通图的生成树有n-1条边
在生成树中再加一条边必然形成回路
生成树中任意两个顶点间的路径是唯一的

含n个顶点n-1条边的图不一定是生成树。

最小生成树：给定一个无向网络，在该网的所有生成树中，使得各边权值之和最小的那棵生成树称为该网的最小生成树，也叫最小代价生成树。最小生成树可能不唯一。

MST性质(Minimum Spanning Tree)：设N=(V,E)是一个连通网，U是顶点集V的一个非空子集。若边(u,v)是一条具有最小权值的边，其中，则必存在一棵包含边(u,v)的最小生成树。

3.2.4.1.1 普利姆(Prim)算法

算法思想：设N=(V,E)是连通网，TE是N上最小生成树中边的集合。初始令。在所有的边中，找一条代价最小的边。将并入集合TE，同时并入U。重复上述操作直至U=V为止，则T=(V,TE)为N的最小生成树。

3.2.4.1.2 克鲁斯卡尔(Kruskal)算法

算法思想：设连通网N=(V,E)，令最小生成树初始状态为只有n个顶点而无边的非连通图T=(V,{})，每个顶点自成一个连通分量。在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上(即：不能形成环)，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边。以此类推，直至T中所有顶点都在同一连通分量上为止。

3.2.4.1.3 两种算法的比较

算法名	普利姆算法	克鲁斯卡尔算法
算法思想	选择点	选择边
时间复杂度	(n为顶点数)	(e为边数)
适用范围	稠密图	稀疏图

3.2.4.2 最短路径

在有向图中A点(源点)到达B点(终点)的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。最短路径与最小生成树不同，路径上不一定包含n个顶点，也不一定包含n-1条边。

两种常见的最短路径问题：

单源最短路径——用迪杰斯特拉(Dijkstra)算法
所有顶点间的最短路径——用弗洛伊德(Floyd)算法

3.2.4.2.1 Dijkstra算法

算法思想：

初始化：先找出从源点到各终点的直达路径，即通过一条弧到达的路径
选择：从这些路径中找出一条长度最短的路径
更新：然后对其余各条路径进行适当调整

若在图中存在弧，且，则以路径代替

在调整后的各条路径中，再找长度最短的路径，以此类推

时间复杂度为。

3.2.4.2.2 Floyd算法

求所有顶点间的最短路径：

方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次。时间复杂度为。

方法二：Floyd算法，时间复杂度也是。

算法思想：

逐个顶点试探
从到的所有可能存在的路径中选出一条长度最短的路径

3.2.4.3 有向无环图及其应用

有向无环图：无环的有向图，简称DAG图。

有向无环图常用来描述一个工程或系统的进行过程。一个工程可以分为若干个子工程，只要完成了这些子工程(活动)就可以导致整个工程的完成。

AOV网：用一个有向图表示一个工程的各子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称AOV网。AOV网应用于拓扑排序。

AOE网：用一个有向图表示一个工程的各子工程及其相互制约的关系，其中以弧表示活动，顶点表示活动的开始或结束事件，称这种有向图为边表示活动的网，简称AOE网。AOE网应用于关键路径问题。

3.2.4.3.1 拓扑排序

AOV网的特点：

若从i到j有一条有向路径，则i是j的前驱；j是i的后继
若是网中有向边，则i是j的直接前驱；j是i的直接后继
AOV网中不允许有回路，因为如果有回路存在，则表明某项活动以自己为先决条件，显然这是荒谬的

问题：如何判断AOV网中是否有回路？

在AOV网没有回路的前提下，我们将全部活动排列成一个线性序列，使得若AOV网中有弧存在，则在这个序列中，i一定排在j的前面，具有这种性质的线性序列称为拓扑有序序列，相应的拓扑有序排序的算法称为拓扑排序。

拓扑排序的方法：

在有向图中选一个没有前驱的顶点且输出之
从图中删除该顶点和所有以它为尾的弧
重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止

一个AOV网的拓扑序列不是唯一的。

拓扑排序的一个重要应用：检测AOV网中是否存在环的方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。

3.2.4.3.2 关键路径

把工程计划表示为边表示活动的网络，即AOE网，用顶点表示事件，弧表示活动，弧的权表示活动持续时间。事件表示在它之前的活动已经完成，在它之后的活动可以开始。

设一个工程有11项活动，9个事件。

事件v1——表示整个工程开始(源点：入度为0的顶点)

事件v9——表示整个工程结束(汇点：出度为0的顶点)

对于AOE网，我们关心两个问题：

完成整项工程至少需要多长时间？
哪些活动是影响工程进度的关键？

本质上是求解关键路径的问题。如何确定关键路径，需要定义4个描述量：

——表示事件的最早发生时间
——表示事件的最迟发生时间
e(i)——表示活动ai的最早开始时间
l(i)——表示活动ai的最迟开始时间

l(i)-e(i)——表示完成活动ai的时间余量

关键活动——关键路径上的活动，即l(i)==e(i)的活动

如何找l(i)==e(i)的关键活动？

设活动ai用弧表示，其持续时间记为：$w{j,k} $，则有：$ e(i)=ve(j)，l(i)=vl(k)-w{j,k}$

如何求ve(j)和vl(j)？

从ve(1)=0开始向前递推
$ve(j)=\max_{i}\{ve(i)+w_{i,j}\},<i,j>\in T,2\le j\le n$
其中T是所有以j为头的弧的集合
从vl(n) = ve(n)开始向后递推
$vl(i)=\min_{j}\{vl(j)-w_{i,j} \},<i,j>\in S, 1\le i\le n-1$
其中S是所有以i为尾的弧的集合

4. 查找和排序

排序和查找的关系：排序是查找的前提，排序是重点。

4.1 冒泡排序

冒泡排序的基本思想：重复走访过要排序的元素列，依次比较两个相邻的元素，如果顺序错误就把它们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

#include <stdio.h>
 
#define ARR_LEN 255 /*数组长度上限*/
#define elemType int /*元素类型*/
 
/* 冒泡排序 */
/* 1. 从当前元素起，向后依次比较每一对相邻元素，若逆序则交换 */
/* 2. 对所有元素均重复以上步骤，直至最后一个元素 */
/* elemType arr[]: 排序目标数组; int len: 元素个数 */
void bubbleSort (elemType arr[], int len) {
    elemType temp;
    int i, j;
    for (i=0; i<len-1; i++) /* 外循环为排序趟数，len个数进行len-1趟 */
        for (j=0; j<len-1-i; j++) { /* 内循环为每趟比较的次数，第i趟比较len-i次 */
            if (arr[j] > arr[j+1]) { /* 相邻元素比较，若逆序则交换（升序为左大于右，降序反之） */
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
}
 
int main (void) {
    elemType arr[ARR_LEN] = {3,5,1,-7,4,9,-6,8,10,4};
    int len = 10;
    int i;
     
    bubbleSort (arr, len);
    for (i=0; i<len; i++)
        printf ("%d\t", arr[i]);
    putchar ('\n');
     
    return 0;
}

4.2 选择排序

选择排序的基本思想：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

#include <stdio.h>

void choseSort(int arr[], int n) {
    int i, j;
    int min, temp;
    // 每次从未排序的部分选出一个最小的元素，最后一次只剩一个元素未排序
    // 此时实际上已经排好序，故只需要n-1次外层大循环
    for (i = 0; i < n - 1; ++i) {
        min = i;    // 假定未排序部分的第一个元素为最小的元素
        // 遍历剩下的部分，找到最小的元素
        for (j = i + 1; j < n; ++j) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        // 如果第一个元素就是最小的元素，就不需要交换了
        if (min != i) {
            temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
}

int main() {
    int i = 0;
    int arr[10] = {5, 2, 3, 8, 1, 2, 6, 9, 3, 7};
    choseSort(arr, 10);
    for (i = 0; i < 10; ++i) {
        printf("%d ", arr[i]);
    }
    return 0;
}

4.3 插入排序

插入排序的基本思想：将第一个待排序元素看做是一个有序序列，用下一个未排序元素，从后往前比较，然后放入到相应的位置，每比较一次有序序列就增加一个元素，这样就能把每个未排序的元素插入到相应的位置，将序列变得有序。

#include <stdio.h> 
#include <stdlib.h> 

//插入排序 
void InsertSort(int* a, int len);

//输出数组中的元素 
void OutputArray(int* a, int len);

void main()
{
    int a[7] = { 2, 9, 5, 4, 8, 1, 6 };

    //输出数组中的元素 
    printf("排序前的数据:");
    OutputArray(a, 7);

    //插入排序 
    InsertSort(a, 7);

    //输出排序后的结果 
    printf("排序后的数据:");
    OutputArray(a, 7);

    system("pause");
}

//插入排序 
void InsertSort(int *a, int len)
{
    int i, j;
    int temp;
    for (i = 1; i < len; i++)
    {
        temp = a[i];
        for (j = i; j > 0 && a[j - 1] > temp; j--)
        {
            a[j] = a[j - 1];
        }
        a[j] = temp;
    }
}

//输出数组中的元素 
void OutputArray(int* a, int len)
{
    for (int i = 0; i < len; i++)
    {
        printf("%d ", a[i]);
    }

    printf("\n");
}

4.4 快速排序

快速排序是对冒泡排序的一种改进。

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。

(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。

(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

# include <stdio.h>

void QuickSort(int *, int, int);
int FindPos(int *, int, int);

int main()
{
    int a[6] = {2, 1, 0, 5, 4, 3};
    int i;

    QuickSort(a, 0 , 5); //第二个参数表示第一个元素的下标，第三个参数表示最后一个元素的下标

    for(i=0;i<6;i++)
        printf("%d ",a[i]);
    printf("\n");

}

void QuickSort(int * a, int low, int high)
{
    int pos;

    if(low < high)
    {
        pos = FindPos(a, low, high);
        QuickSort(a, low, pos-1);
        QuickSort(a, pos+1, high);
    }
}

int FindPos(int * a, int low, int high)
{
    int val = a[low];
    while(low < high)
    {
        while(low<high && a[high]>=val)
            --high;
        a[low] = a[high];

        while(low<high && a[low]<=val)
            ++low;
        a[high] = a[low];
    } //终止while循环之后low和high一定是相等的

    a[low] = val;

    return high; //high可以改为low，但不能改为val 也不能改为a[low] 也不能改为a[high]
}

4.5 归并排序

归并排序是建立在归并操作上的一种有效、稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

#include <stdlib.h>
#include <stdio.h>
 
void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex)
{
    int i = startIndex, j=midIndex+1, k = startIndex;
    while(i!=midIndex+1 && j!=endIndex+1)
    {
        if(sourceArr[i] > sourceArr[j])
            tempArr[k++] = sourceArr[j++];
        else
            tempArr[k++] = sourceArr[i++];
    }
    while(i != midIndex+1)
        tempArr[k++] = sourceArr[i++];
    while(j != endIndex+1)
        tempArr[k++] = sourceArr[j++];
    for(i=startIndex; i<=endIndex; i++)
        sourceArr[i] = tempArr[i];
}
 
//内部使用递归
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex)
{
    int midIndex;
    if(startIndex < endIndex)
    {
        midIndex = startIndex + (endIndex-startIndex) / 2;//避免溢出int
        MergeSort(sourceArr, tempArr, startIndex, midIndex);
        MergeSort(sourceArr, tempArr, midIndex+1, endIndex);
        Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);
    }
}
 
int main(int argc, char * argv[])
{
    int a[8] = {50, 10, 20, 30, 70, 40, 80, 60};
    int i, b[8];
    MergeSort(a, b, 0, 7);
    for(i=0; i<8; i++)
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}

4.6 折半查找

折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功或所有查找区域无记录，查找失败。

#include <stdio.h>
#include <stdlib.h>

//折半查找,又称为二分查找,条件保证要升序排序
int Binary_Search(int *a,int n,int key)
{
    int low,high,mid;
    low = 0;    //定义最低下标为记录首位
    high = n;   //记录最高下标为记录末位

    while ( low <= high )
    {
        mid = (low + high) / 2;
        if (key < a[mid]) {
            high = mid - 1;//最高位下标调小 一位
        } else if(key > a[mid]){
            low = mid + 1; //最低下标调整到中位下标大一位
        } else{
            return mid; //代表就是次位置
        }
    }
    return -1; //没有找到返回-1
}

void main()
{
    int a[] = {1,2,3,4,5,6,7,8,9,10};

    //需求要查找8, 如果用传统的方式 要查找8次才能得出
    int index;
    index = Binary_Search(a, sizeof(a) / sizeof(int),8);

    if (index == -1)
        printf("没有找到！\n");
    else
        printf("找到了,index为:%d\n",index);
}

1. 预备知识

1.1 指针

1.2 数组

1.3 结构体

1.4 动态内存分配

1.5 跨函数使用内存

2. 线性结构

2.1 连续存储【数组】

2.2 离散存储【链表】

2.2.1 typedef的用法

2.2.2 链表

2.2.2.1 链表的插入

2.2.2.2 链表的删除

2.2.3 链表的实现

2.3. 线性结构的两种常见应用之一 栈

2.4 线性结构的两种常见应用之二 队列

2.5 递归

2.5.1 1+2+3+…+100的和

2.5.2 求阶乘

2.5.3 汉诺塔

2.6 串

2.6.1 串的顺序存储结构

2.6.2 串的链式存储结构——块链结构

2.6.3 串的模式匹配算法

2.6.3.1 BF算法

2.6.3.2 KMP算法

2.7 数组

2.7.1 特殊矩阵的压缩存储

2.7.2 对称矩阵

2.7.3 三角矩阵

2.7.4 对角矩阵

2.7.5 稀疏矩阵

2.8 广义表

3. 非线性结构

3.1 树

3.1.1 链式二叉树的遍历

3.1.2 哈夫曼树(最优二叉树)

3.1.3 哈夫曼树的应用——哈夫曼编码

3.2 图

3.2.1 图的概念

3.2.2 图的存储结构

3.2.2.1 邻接矩阵

3.2.2.2 邻接表

3.2.2.3 邻接矩阵和邻接表的关系

3.2.2.4 十字链表

3.2.2.5 邻接多重表

3.2.3 图的遍历

3.2.3.1 深度优先搜索(DFS)

3.2.3.2 广度优先搜索(BFS)

3.2.3.3 DFS和BFS的比较

3.2.4 图的应用

3.2.4.1 最小生成树

3.2.4.1.1 普利姆(Prim)算法

3.2.4.1.2 克鲁斯卡尔(Kruskal)算法

3.2.4.1.3 两种算法的比较

3.2.4.2 最短路径

3.2.4.2.1 Dijkstra算法

3.2.4.2.2 Floyd算法

3.2.4.3 有向无环图及其应用

3.2.4.3.1 拓扑排序

3.2.4.3.2 关键路径

4. 查找和排序

4.1 冒泡排序

4.2 选择排序

4.3 插入排序

4.4 快速排序

4.5 归并排序

4.6 折半查找

2.3. 线性结构的两种常见应用之一栈

2.4 线性结构的两种常见应用之二队列