郝斌老师数据结构学习笔记（评论区附视频和源代码）

发布于：2022-11-15 ⋅ 阅读:(911) ⋅ 点赞:(0)

文章目录

数据结构概述

定义

我们如何把现实中大量而复杂的问题以特定的数据类型（个体）和特定的存储结构（个体关系）保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找某个元素，删除某个元素，对所有元素进行排序）而执行的相应操作，这个操作也叫算法。

数据结构 = 个体 + 个体关系
算法 = 对存储数据的操作

数据结构

  1. 线性结构

特点：除第一个元素只有一个“后继”和最后一个元素只有一个“前驱”，其它每个元素只有一个“前驱”元素和一个“后继”元素。

常见的线性结构有: 数组、链表、栈以及队列。****注意：栈和队列本身不是一种数据结构，可通过数组或链表实现。

1.1 线性结构又分为顺序存储和链式存储

线性结构又分为顺序存储和链式存储，顺序存储：****各个元素存储的地址空间连续，逻辑相邻的元素在物理内存中也相邻，如数组；

链式存储*****：各个元素存储在任意的地址空间，逻辑相邻的元素在物理内存中没有联系，如链表。*

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-146nnUNX-1668509707370)(https://cyuyan.oss-cn-beijing.aliyuncs.com/img/wps1.jpg)]

1.2 顺序存储和链式存储的区别

1.2.1 顺序存储

优点：① 因为各个元素是连续储存*，而且当元素类型一致时占用空间大小一致*，所以可以直接通过首元素地址计算某个元素的内存地址，从而*****访问特定元素*效率很高

② 对于有序数组*，还可以通过二分查找提高元素查找*的速度

缺点：① 由于顺序存储的特点，所以在删除或插入元素后需要移动其它元素使得整体的存储空间依然是连续的，所以*****删除、插入元素效率低，如下图*。

② 由于元素存储空间连续，所以当有大数据时，****较难分配一块连续的大内存空间。

img

1.2.2 链式存储

优点：① 由于链式存储的特点，删除或插入节点很方便，不需要移动其它元素，改变元素“连接”关系即可，所以删除、插入元素效率高，如下图。

缺点：① 因为存储的任意性，只能通过前一个元素访问下一个元素，每一次访问元素都从头节点开始遍历，所以*****访问特定元素或查找元素效率低*。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sfYGvjQJ-1668509707371)(https://cyuyan.oss-cn-beijing.aliyuncs.com/img/wps3.jpg)]

非线性结构

特点：每个元素可以和多个元素“连接”。

常见的非线性结构：二维数组、树和图。

逻辑结构

线性结构

数组

链表

栈和队列是一种特殊的线性结构

非线性结构

树

图

物理结构

算法

解题的方法和步骤

衡量算法的标准

  1. 时间复杂度
    大概程序要执行的次数，而非执行的时间
  2. 空间复杂度
    算法执行过程中大概所占用的最大内存
  3. 难易程度
  4. 健壮性

数据结构的地位

数据结构是软件中最核心的课程

程序 = 数据的存储 + 数据的操作 + 可以被计算机执行的语言

预备知识

指针

指针的重要性

指针是c语言的灵魂

定义

地址

内存单元的编号

从0开始的非负整数

范围：0 – FFFFFFFF【0 – 4G-1】

指针

指针就是地址 地址就是指针

指针变量是存放内存单元地址的变量

指针的本质是一个操作受限的非负整数【只能在某种情况下相减】

分类

基本类型指针

# include <stdio.h>

int main(void)
{
	int * p;//p是一个变量名，int *表示该p变量只能存储int类型变量的地址
	int i = 10;
	int j;
    
    p = &i;
    //p = 10;//error
    j = *p;
    printf("i = %d,j = %d,*p = %d\n",i,j,*p);
}

指针和数组的关系

指针和一维数组
数组名

一维数组名是个指针常量

它存放的是一维数组第一个元素的地址

它的值不能改变

一维数组名指向的是数组的第一个元素

下标的指针的关系

a[i] <<==>> *(a+1)

/*
	数组名a是一个指针常量
	a保存的是第一元素的地址
	*a就是第一个元素
	故 *(a+i)就是第i+1个元素
*/

# include <stdio.h>

int main(void)
{
	int a[5] = {1,2,3,4,5};
    
    a[3] == *(a+3);
    3[a] == *(3+a);//把方括号理解为一种运算符 
}

假设指针变量的名字是p

则p+i的值是第i+1个元素的值

# include <stdio.h>

int main(void)
{
	int a[5] = {1,2,3,4,5};
	
	printf("%p\n",a+1);
	printf("%p\n",a+2);
	printf("%p\n",a+3);//*a+3等价于a[0]+3
	
	return 0;
}

/*
000000000062FE04
000000000062FE08
000000000062FE0C
*/

p + i的值是 p + i * (p所指向的变量所占的字节数)

结构体

为什么需要结构体

为了表示一些复杂的数据，而普通的基本变量无法满足要求。

什么叫结构体

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

如何使用结构体
两种方式
struct Student st = {1000,"zhangsan",20};
struct Student * pst = &st;
1.
    st,sid;
2.
    pst->sid;
	pst 所指向的结构体变量中的sid这个变量
注意事项

结构体变量不能加减乘除，但可以相互赋值

普通结构体变量和结构体指针变量作为函数传参的问题

​ 传给结构体变量的首地址即可

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

void f(struct Student * pst);
void g(struct Student st);//占据内存 
void g2(struct Student * st1);


struct Student		//定义了一个数据类型 
{
	int sid;
	char name[100];
	int age;
};

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

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

void g(struct Student st)
{
	printf("%d %s %d\n",st.age,st.name,st.sid);
}

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

动态内存的分配和释放

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

int main(void)
{
	int a[5] = {1,2,3,4,5};
	int len,i;
	
	scanf("%d",&len);
	
	int * pArr = (int *)malloc(sizeof(int)*len);//动态分配完内存单元后，强制转换为int *类型，也就是将内存区块化，4个4个分好
	
//	pArr[1] = 10;
//	printf("%d\n",*(pArr +1)); 
    
    *pArr = 10;			//类似于a[0] = 10; 
	*(pArr+3) = 23;		//如果p是个指针变量，则 p[i] 永远等价于 *(p+i), 类似于a[3] = 23;
	pArr[2] = 21;		//类似于a[2] = 21;
	
	printf("%d %d %d\n",pArr[0],pArr[3],pArr[2]); 

    //我们可以吧pArr当做普通数组来使用
	for(i = 0;i<len;i++)
	{
		scanf("%d",&pArr[i]);
	}
	
		for(i = 0;i<len;i++)
	{
		printf("%d\n",*(pArr+i));
	}
    
   	free(pArr);			//把pArr所代表的动态分配的内存释放 

	
	return 0;
}

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

struct Student 
{
	int sid;
	int age;
};

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

int main()
{
	struct Student * st;
	
	st = CreateStudent();
	ShowStudent(st);
	
	return 0;
} 

struct Student *CreateStudent(void)
{
	struct Student * p = (struct Student *)malloc(sizeof(struct Student));
	p->sid = 88;
	p->age = 66;
	return p;
}

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

模块一：线性结构【把所有的结点用一根直线穿起来】

连续存储【数组】

什么叫数组

元素类型相同，大小相等

数组的优缺点

image-20221001173136793

离散存储【链表】

定义

  1. n个节点离散分配
  2. 彼此通过指针相连
  3. 每个节点只有一个前驱节点，每个节点只有一个后继节点
  4. 首节点没有前驱结点，尾结点没有后继节点

专业术语

首节点：第一个有效节点

尾节点：最后一个有效节点

头结点：第一个有效节点之前的那个节点，头结点并不存放有效数据，加头结点的目的主要是为了方便对链表的操作

头指针：指向头结点的指针变量

尾指针：指向尾结点的指针变量

image-20221002091447336

如果希望通过一个函数来对链表进行处理，我们至少需要接收链表的哪些参数

只需要一个参数：头指针

因为我们通过头指针可以推算出链表的其他所有参数

image-20221002082930861

分类

泛型：利用某种技术达到的效果就是：不同的存储方式，执行的操作是一样的。

单链表

双链表

每一个节点有两个指针域

循环链表

能通过任何一个节点找到其它所有的节点

非循环链表

算法

遍历

查找

清空

销毁

求长度

排序

删除节点

伪算法分析

image-20221002101936913

插入节点

伪算法分析image-20221002101346681image-20221002153510958

# include <stdio.h>
# include <malloc.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);  //求链表长度
bool insert_list(PNODE pHead, int pos, int val);  //在pHead所指向链表的第pos个节点的前面插入一个新的结点，该节点的值是val， 并且pos的值是从1开始
bool delete_list(PNODE pHead, int pos, int * pVal);  //删除链表第pos个节点，并将删除的结点的值存入pVal所指向的变量中,  并且pos的值是从1开始
void sort_list(PNODE);  //对链表进行排序


int main(void)
{
	PNODE pHead = NULL; //等价于 struct Node * pHead = NULL;
	int val;

	pHead = create_list();  //create_list()功能：创建一个非循环单链表，并将该链表的头结点的地址付给pHead
	traverse_list(pHead);
	
	//insert_list(pHead, -4, 33);
	if ( delete_list(pHead, 4, &val) )
	{
		printf("删除成功，您删除的元素是: %d\n", val);
	}
	else
	{
		printf("删除失败!您删除的元素不存在!\n");
	}

	traverse_list(pHead);
	
	//int len = length_list(pHead);
	//printf("链表的长度是%d\n", len);

	//sort_list(pHead);
	//traverse_list(pHead);
	
/*	if ( is_empty(pHead) )
		printf("链表为空!\n");
	else
		printf("链表不空!\n");
*/
	return 0;
}

PNODE create_list(void)
{
	int len;  //用来存放有效节点的个数
	int i;
	int val; //用来临时存放用户输入的结点的值

	//分配了一个不存放有效数据的头结点
	PNODE pHead = (PNODE)malloc(sizeof(NODE));
	if (NULL == pHead)
	{
		printf("分配失败, 程序终止!\n");
		exit(-1);
	}
	PNODE pTail = pHead;
	pTail->pNext = NULL;

	printf("请输入您需要生成的链表节点的个数: len = ");
	scanf("%d", &len);
	
	for (i=0; i<len; ++i)
	{
		printf("请输入第%d个节点的值: ", i+1);
		scanf("%d", &val);
		
		PNODE pNew = (PNODE)malloc(sizeof(NODE));
		if (NULL == pNew)
		{
			printf("分配失败, 程序终止!\n");
			exit(-1);
		}
		pNew->data = val;
		pTail->pNext = pNew;
		pNew->pNext = NULL;
		pTail = pNew;
	}
	
	return pHead;
}

void traverse_list(PNODE pHead)
{
	PNODE p = pHead->pNext;

	while (NULL != p)
	{
		printf("%d  ", 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)
{
	PNODE p = pHead->pNext;
	int len = 0;

	while (NULL != p)
	{
		++len;
		p = p->pNext;
	}

	return len;
}

void sort_list(PNODE pHead)
{
	int i, j, t;
	int len = length_list(pHead);
	PNODE p, q;
	
	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)  //类似于数组中的:  a[i] > a[j]
			{
				t = p->data;//类似于数组中的:  t = a[i];
				p->data = q->data; //类似于数组中的:  a[i] = a[j];
				q->data = t; //类似于数组中的:  a[j] = t;
			}
		}
	}

	return;
}

//在pHead所指向链表的第pos个节点的前面插入一个新的结点，该节点的值是val， 并且pos的值是从1开始
bool insert_list(PNODE pHead, int pos, int val)
{
	int i = 0;
	PNODE p = pHead;

	while (NULL!=p && i<pos-1)
	{
		p = p->pNext;
		++i;
	}

	if (i>pos-1 || NULL==p)
		return false;

	//如果程序能执行到这一行说明p已经指向了第pos-1个结点,但第pos-1个节点是否存在无所谓
	//分配新的结点
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	if (NULL == pNew)
	{
		printf("动态分配内存失败!\n");
		exit(-1);
	}
	pNew->data = val;
	
	//将新的结点存入p节点的后面
	PNODE q = p->pNext;
	p->pNext = pNew;
	pNew->pNext = q;

	return true;
}


bool delete_list(PNODE pHead, int pos, int * pVal)
{
	int i = 0;
	PNODE p = pHead;

	while (NULL!=p->pNext && i<pos-1)
	{
		p = p->pNext;
		++i;
	}

	if (i>pos-1 || NULL==p->pNext)
		return false;
	
	//如果程序能执行到这一行说明p已经指向了第pos-1个结点，并且第pos个节点是存在的
	PNODE q = p->pNext;  //q指向待删除的结点
	*pVal = q->data;  

	//删除p节点后面的结点
	p->pNext = p->pNext->pNext;
	
	//释放q所指向的节点所占的内存
	free(q);
	q = NULL;
	
	return true;

}

链表的优缺点

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

动态分配的内存在堆中，静态分配的内存在栈中

定义

定义：一种可以实现“先进后出”的存储结构。栈类似于纸箱

分类：静态栈（以数组为底层）

​ 动态栈（以链表为底层）

算法：出栈

压栈（进栈）

image-20221004202118515

算法：狭义的算法是与数据的存储方式密切相关的

​ 广义的算法是与数据的存储方式无关的

泛型：利用某种技术达到的效果是：不同的存储方式，执行的操作是一样的。

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

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

typedef struct Stack
{
	PNODE pTop;
	PNODE pBottom;
}STACK,* PSTACK;

void init(PSTACK);//初始化栈
void push(PSTACK pS, int val);
void pushs(PSTACK);
void traverse(PSTACK);
bool pop(PSTACK, int *);
void clear(PSTACK pS);
bool empty(PSTACK pS);

int main(int argc, char const *argv[])
{
	STACK S;
	int val;

	init(&S);
	pushs(&S);
	traverse(&S);
	if(pop(&S,&val))
	{
		printf("出栈成功，出栈的元素为：%d\n\n",val);
	}
	else
	{
		printf("栈为空！");
	}
	traverse(&S);

	clear(&S);
	traverse(&S);
	
	
	return 0;
}

void init(PSTACK pS)
{
	pS->pTop = (PNODE)malloc(sizeof(NODE));
	if (NULL == pS->pTop)
	{
		printf("分配失败，退出程序");
		exit(-1);
	}
	else
	{
		pS->pBottom = pS->pTop;
		pS->pTop->pNext = NULL;
	}
	printf("栈初始化成功！\n\n");
}

//多次压栈
void pushs(PSTACK pS)
{
	int x,y,val;
	printf("请输入您要压栈的次数：");
	scanf("%d",&x);

	for (int i = 0; i < x; i++)
	{
		printf("第%d次压栈的数值为：",i+1);
		scanf("%d",&val);

		PNODE pNew = (PNODE)malloc(sizeof(NODE));

		pNew->data = val;
		pNew->pNext = pS->pTop;
		pS->pTop = pNew;
	}
	printf("已经全部压栈成功\n\n");
	return;
}

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

	pNew->data = val;
	pNew->pNext = pS->pTop;
	pS->pTop = pNew;

	return;
}

//输出与压栈的顺序相反，刚好表明先进后出
void traverse(PSTACK pS)
{
	if (empty(pS))
	{
		printf("栈为空");
	}
	else
	{
		PNODE p = pS->pTop;

		printf("栈中元素为：");
		while (p != pS->pBottom)
		{
			printf("%d	",p->data);
			p = p->pNext;
		}
		printf("\n\n");
	}
	return;
}

bool empty(PSTACK pS)
{
	if(pS->pBottom == pS->pTop)
		return true;
	else
		return false;
}

bool pop(PSTACK pS, int * pVal)
{
	if(empty(pS))
		return false;
	else
	{
		PNODE r = pS->pTop;
		*pVal = r->data;
		pS->pTop = r->pNext;
		free(r);
		r = NULL;

		return true;		
	}
}

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

		while (p != pS->pBottom)
		{
			q = p->pNext;
			free(p);
			p = q;
		}
		pS->pTop = pS->pBottom;
	}
	printf("已清空栈");
}

应用

函数调用

中断

表达式求值

内存分配

缓冲处理

迷宫

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

定义

一种可以实现“先进先出”的存储结构

队头（删）：front，队尾（增）：rear

分类

链式队列 —— 用链表实现

静态队列 —— 用数组实现

静态队列

静态队列通常都必须是循环队列

循环队列的讲解

  1. 静态队列为什么必须是循环队列
    队头和队尾都只能加，浪费内存，不合理

  2. 循环队列需要几个参数来确定
    两个参数：front，rear

  3. 循环队列各个参数的含义

    两个参数不同场合有不同的含义
    建议初学者先记住，慢慢体会
    1、队列初始化
    front和rear的值都是0

    ​ 2、队列非空

    ​ front代表的是队列的第一个元素

    ​ rear代表的是队列的最后一个有效元素的下一个元素

    ​ 3、队列空
    ​ front和rear的值相等，但不一定是零

  4. 循环队列入队伪算法讲解
    Snipaste_2022-11-08_20-29-10

  5. 循环队列出队伪算法讲解
    front= (front+1)%数组的长度

  6. 如何判断循环队列是否为空
    front = rear

  7. 如何判断循环队列是否已满
    预备知识：
    front的值可能比rant大，也可能比rear小，当然也可能两者相等
    两种方式：
    1、多增加一个标识参数
    2、少用一个元素【通常用第二种】
    Snipaste_2022-11-08_21-03-37

队列算法

入队

出队

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

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

void init(QUEUE *);
bool en_queue(QUEUE *,int);
bool full_queue(QUEUE * pQ);
bool empty(QUEUE * pQ);
void traverse_queue(QUEUE * pQ);
bool out_queue(QUEUE * pQ,int * pVal);

int main(int argc, char const *argv[])
{
    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);

    traverse_queue(&Q);

    if (out_queue(&Q,&val))
    {
        printf("出队成功，被删除的元素为：%d\n",val);
    }
    else
        printf("出队失败");

    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))
   {
        printf("队已满，无法添加\n");
        return false;
   }
   else
   {
        pQ->pBase[pQ->rear] = val;
        pQ->rear = (pQ->rear + 1) % 6;

        printf("添加成功！\n");

        return true;
   }
}

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

    printf("队内元素为：");

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

    printf("\n");

    return;    
}

bool empty(QUEUE * pQ)
{
    if (pQ->front == pQ->rear)
    {
        return true;
    }
    else 
    {   
        return false;
    }

}

bool out_queue(QUEUE * pQ,int * pVal)
{
    if (empty(pQ))
    {
        printf("队列为空！\n");
        return false;
    }
    else
    {
        *pVal = pQ->pBase[pQ->front];
        pQ->front = (pQ->front+1)%6;  

        return true;
    }
}

队列的具体应用

所有和时间有关的操作都有队列的影子

专题：递归

定义

一个函数自己直接或者间接调用自己

image-20221112170158231

递归满足三个条件

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

循环和递归

递归：

易于理解

数度慢

存储空间大

循环

不易理解

速度快

存储空间小

递归案例

1.1+2+3+4+…+100

# include <stdio.h>

long sum(int n)
{
    if(1 == n)
        return 1;
    else
        return n + sum(n - 1);
}

int main(int argc, char const *argv[])
{
    printf("%ld\n",sum(100));
    return 0;
}

2.求阶乘

# include <stdio.h>

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

int main(void)
{
	printf("%ld\n", f(20));

	return 0;
}

3.汉诺塔

# include <stdio.h>

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

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

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

	hannuota(n, 'A', 'B', 'C');


	return 0;
}

4.走迷宫

递归的应用

树和森林就是以递归的方式定义的

树和图的很多算法都是以递归来实现的

很多数学公式就是以递归的方式定义的

​ 斐波拉契序列

​ 1 2 3 5 8 13 21 34 55 89 144 233

模块二：非线性结构

树

定义

专业定义：

  1. 有且只有一个称为跟的节点
  2. 有若干个互不相交的子树，这些子树本身也是一棵树

通俗定义

  1. 树是由节点和边组成
  2. 每个节点只有一个父节点但可以有多个子节点
  3. 但有一个节点例外，该节点没有父节点，此节点称为跟节点

专业术语

节点：圈

父节点

子节点

子孙

堂兄弟

深度：从根节点到最底层节点的层数称之为深度，根节点是第一层。

叶子节点：没有子节点的节点

非终端节点：实际上就是非叶子节点

度：子节点的个数称为度（看该节点有几个孩子）

​ 树的度：一个树中最大的度

分类

一般树

任意一个节点的子节点的个数都不受限制

二叉树（有序树）

任意一个节点的子节点的个数最多两个。且子节点的位置不可更改（左边的叫左子树，右边的叫右子树）

分类

一般二叉树

满二叉树：在不增加树的层数的前提下，无法再多添加一个节点的二叉树就是满二叉树

完全二叉树：如果只是删除了满二叉树做底层最右边的连续若干个节点，这样形成的二叉树叫完全二叉树。

森林

n个互不相交的树的集合

树的存储【重点】

二叉树的存储【重点】

连续存储 [完全二叉树]【重点】

优点：查找某个节点的父节点和子节点（也包括判断有没有子节点）数组很快

缺点：耗用内存过大

链式存储image-20221113154137513

一般树的存储

双亲表示法image-20221113154700843

孩子表示法

image-20221113154853352

双亲孩子表示法image-20221113155252090

二叉树表示法【也叫孩子兄弟链表表示法】

先把一般树转化为二叉树，在存储二叉树

一般树转化为二叉树的方法是：

​ 设法保证任意一个节点的

​ 左指针域指向他的第一个孩子

​ 右指针域指向他的下一个兄弟

​ 只要满足此条件，就可以把一个普通树转化为二叉树来存储

image-20221113160104677

森林的存储

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

image-20221113161315078

二叉树操作

先序遍历[先访问根节点]

先访问根节点

再先序访问左子树

再先序访问右子树

image-20221113195822507

中：DBAECGF

后：DBEGFCA

image-20221113200009893

先： ABCDEFLQMNS

中：CDFELBAMSNQ

后：FLEDCBSNMQA

image-20221113200449662

先：ABQLCDGEF

中：QBLAGDCEF

后：QLBGDFECA

中序遍历[中间访问根节点]

中序遍历左子树

再访问根节点

再中序遍历右子树

image-20221113201400485

先：ABCDEFLMNQ

中：BDCEALFNQM

后：DECBLQNMFA

image-20221113202316806

先：ABCDEMQLN

中：BDCAMQELN

后：DCBQMNLEA

后续遍历[最后访问根节点]

先中序遍历左子树

再中序遍历右子树

再访问根节点

image-20221113203054980

先：ABCDEFML

中：BADCMFEL

image-20221113203802963

先：MNQSTWLPF

中：NMWTSQLPF

后：NWTSFPLQM

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

typedef struct BTNode
{
    char data;
    struct BTNode * pLchild;
    struct BTNode * pRchild;
}BTNODE,* PBTNODE;

void PostTraverseBTree(PBTNODE pT);
void InTraverseBTree(PBTNODE pT);
void PreTraverseBTree(PBTNODE pT);
PBTNODE CreateBTree();


int main(int argc, char const *argv[])
{
    PBTNODE pT = CreateBTree();

    // PreTraverseBTree(pT);
    // InTraverseBTree(pT);
    PostTraverseBTree(pT);

    return 0;
}

PBTNODE CreateBTree()
{
    PBTNODE pA = (PBTNODE)malloc(sizeof(BTNODE));
    PBTNODE pB = (PBTNODE)malloc(sizeof(BTNODE));
    PBTNODE pC = (PBTNODE)malloc(sizeof(BTNODE));
    PBTNODE pD = (PBTNODE)malloc(sizeof(BTNODE));
    PBTNODE pE = (PBTNODE)malloc(sizeof(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 = pE;
    pD->pRchild = NULL;
    pE->pLchild = pE->pRchild = NULL;

    return pA;
}

void PreTraverseBTree(struct BTNode * pT)
{
	if (NULL != pT)
	{
		printf("%c\n", pT->data);
	
		if (NULL != pT->pLchild)
		{
			PreTraverseBTree(pT->pLchild);
		}
		
		if (NULL != pT->pRchild)
		{
				PreTraverseBTree(pT->pRchild);
			//pT->pLchild可以代表整个左子树
		}	
	}	

/*
	伪算法
	先访问根节点
	再先序访问左子树
	再先序访问右子树
*/
}

void InTraverseBTree(PBTNODE pT)
{
    if(NULL != pT)
    {
        if (NULL != pT->pLchild)
        {
            InTraverseBTree(pT->pLchild);
        }

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

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

void PostTraverseBTree(PBTNODE pT)
{
    if(NULL != pT)
    {
        if (NULL != pT->pLchild)
        {
            PostTraverseBTree(pT->pLchild);
        }

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

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

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

通过先序和中序 或者 中序和后续 我们可以还原出原始的二叉树

但是通过先序和后续是无法还原出原始的二叉树的

换种说法：只有通过先序和中序，或者中序和后续 ，我们才可以唯一的确定一个二叉树

思路：不断的去根据先序和后续确定每一个根节点，然后根据中序判断左右节点的分布。

先 中：

image-20221113220232753

image-20221113221301341

中 后：

image-20221113222334639

image-20221114151150612

先：A B C D E F G L H

中：C D B A F L G E H

后：D C B L G F H E A

image-20221114152944328

图

模块三：查找和排序

折半查找

排序：

冒泡

插入

选择

快速排序

# include <stdio.h>

int FindPos(int * a,int low,int high);
void QuickSort(int * a,int low,int high);

int main(int argc, char const *argv[])
{
    int a[6] = {4,7,-2,8,1,5};
    int i;

    QuickSort(a,0,5);

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

    return 0;
}

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[high] <= val)
        {
            ++low;
        }
        a[high] = a[low];
    }

    a[low] = val; 

    return low;
}

归并排序

Java中容器和数据结构相关知识

Iterator接口

Map

哈希表

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布