devbox
笔触狂放9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构（C语言版）_数据结构c语言版

作者：笔触狂放9 | 2024-04-09 09:22:54

赞

踩

数据结构c语言版

一、数据结构与概述

1.1 数据结构的基本概念

  • 数据：所有能输入计算机中，并被计算机程序处理的符号的集合。

  • 数据元素：数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。可以由1个或n个数据项构成，也简称为元素、记录、结点、顶点。

  • 数据项：组成数据元素的、有独立含义的、不可分割的最小单位。

  • 数据对象：性质相同的数据元素的集合，是数据的一个子集。

  • 数据结构：相互之间存在一种或多种特定关系的数据元素的集合。

说明：
（1）数据元素与数据：集合的个体，数据对象与数据：集合的子集
（2）数据 >= 数据对象 > 数据元素 > 数据项

1.2 数据结构：逻辑结构、存储结构

  • 逻辑结构：指数据元素之间的逻辑关系，与数据的存储无关，独立于计算机。

（1） 集合结构：数据元素之间除了“属于同一集合”的关系外，别无其它关系。

在这里插入图片描述

（2） 线性结构：数据元素之间存在一对一的关系。

在这里插入图片描述

（3） 树结构：数据元素之间存在一对多的关系。

在这里插入图片描述

(4) 图结构或网状结构：数据元素之间存在多对多的关系。

在这里插入图片描述
• 逻辑结构可以用一个层次图来描述：
在这里插入图片描述

  • 存储结构：数据元素及其关系在计算机中的存储表示

(1)顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示

例如：C语言中的数组
在这里插入图片描述

(2)链式存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示

在这里插入图片描述

(3)索引存储结构：在存储结点信息的同时，还建立附加的索引表

例如，手机中的通讯录的索引表

(4)散列存储结构：根据结点的关键字直接计算出该结点的的存储地址

1.3 数据类型与抽象数据类型

1.3.1 数据类型

数据类型是一个值的集合和定义在这个值集上的一组操作的总称
数据类型 = 值的集合 + 值集上的一组操作

数据类型明显地或隐含地规定了数据的取值范围、存储方式以及允许进行的运算

可以明显看出，数据类型的作用：
（1）约束变量或常量的取值范围
（2）约束变量或常量的操作

  • 一些基本的数据结构可以用已经定义好的数据类型来实现，如数组、字符串等
  • 而一些复杂的数据结构，如树、图等不能用已经定义好的数据类型来实现，需要使用抽象数据类型

1.3.2 抽象数据类型

抽象数据类型：一个数学模型以及定义在此数学模型上的一组操作
具体包括3个部分：数据对象、数据关系、基本操作

一般形式：
ADT 抽象数据类型名
{
	数据对象：<数据对象的定义>
	数据关系：<数据关系的定义>
	基本操作：<基本操作的定义>
}ADT 抽象数据类型名

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 其中，数据对象和数据关系的定义用数学符号和自然语言描述

例如，圆的抽象数据类型的定义

ADT Circle
{
	数据对象：D={r,x,y|r,x,y均为实数}
	数据关系：R={<r,x,y>|r是半径，<x,y>是圆心}
	基本操作：
			Circle(&C,r,x,y)
				操作结果：构造一个圆
			double Area(r)
				初始条件：圆已存在
				操作结果：计算面积
			.......		
}ADT Circle

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

1.3.3 抽象数据类型的具体实现

用已有的数据类型定义描述它的存储结构，用函数定义描述它的操作

#define PI 3.14

//定义圆的抽象类型 
typedef struct
{
	float r;  //圆的半径 
	float x;  //圆点的横向坐标 
	float y;  //圆点的纵向坐标 
}Circle;

//构造一个圆
void assign(Circle* A,float r,float x,float y)
{
	A->r = r;
	A->x = x;
	A->y = y;
} 

//求圆的周长
double circum(Circle* A)
{
	return (2*PI*(A->r));	
}

//求圆的面积
double area(Circle* A)
{
	return (PI*(A->r)*(A->r));	
} 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

1.4 算法与算法的分析

算法：为了解决某类问题而规定的一个有限长的操作序列

  1. 算法的五个特性：有穷性、确定性、可行性、输入（0或多个）、输出（一个或多个）。

注：确定性：对于每种情况下所应执行的操作，在算法中都有确切的规定，不会产生二义性。
注：可行性：算法中的所有操作都可以通过将已经实现的基本操作运算执行有限次来实现。

  1. 时间复杂度（事前估算分析法）：算法的执行时间是问题规模n的函数。
  • 算法的执行时间 = 基本操作所需的时间(均设为单位时间)X 其运算次数

由于一条语句的重复执行次数称作语句频度
算法的执行时间 = ∑（每条语句频度X该语句执行一次所需的时间）
假设执行每条语句所需时间均为单位时间，则算法执行时间 = 语句频度之和

算法时间复杂度：基本语句重复执行次数是问题规模n的某个函数f(n)

  • 基本语句：对算法的运行时间贡献最大，执行次数最多
  • 问题规模n：n越大算法的执行时间越长

计算时间复杂度的基本方法:
1、找出语句频度最大的那条语句作为基本语句
2、计算基本语句的频度得到问题规模n的函数f(n)
3、取其数量级用符号“O”表示

注：
（1）一般情况下，不必计算所有操作的执行次数，而只考虑算法中基本操作执行的次数
（2）只求出最高阶即可，忽略其低阶项和常系数

例如：
1、
算法的执行时间与问题规模n无关的常数，所以时间复杂度T(n) = O(1)，为常量阶·

	++x;     语句频度为1，时间复杂度为O(1)
	s=0;     常量阶

  • 1
  • 2

2、
如果算法的执行时间与问题规模n无关的常数，即使常数很大，时间复杂度仍为O(1)

	for(j=1;j<=10000;++j)     语句频度为10000，时间复杂度为O(1)
	{                         常量阶
		++x;
		s+=x;
	}

  • 1
  • 2
  • 3
  • 4
  • 5

3、

	s=0;
	for(j=1;j<=n;++j)      语句频度为n,时间复杂度为O(n)
	{                      线性阶
		s++;
	}

  • 1
  • 2
  • 3
  • 4
  • 5

4、

	s=0;                     j的值由1、2、4 … n,共执行x次，则有2^x=n
	for(j=1;j<=n;j=j*2)      语句频度为log₂n,时间复杂度为O(log₂n)
	{                        对数阶
		s++;
	}

  • 1
  • 2
  • 3
  • 4
  • 5

5、

	s=0;
	for(i=1;i<=n;++i)         语句频度为n²,时间复杂度为O(n²)
		for(j=1;j<=n;++j)     平方阶
		{
			s++;
		}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

6、

	s=0;
	for(i=1;i<=n;i*=2)         语句频度为nlog₂n,时间复杂度为O(nlog₂n)
		for(j=1;j<=n;++j)  
		{
			s++;
		}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

7、

	s=0;
	for(i=1;i<=n;++i)         语句频度为n*(n+1)/2,时间复杂度为O(n²)
		for(j=1;j<=i;++j)     平方阶
		{
			s++;
		}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

注：由于加注释符后字体暗淡，所以示例中的注释符均没加，大家写注释的时候一定要加注释符。

  1. 各种不同算法时间复杂度的比较关系：
    O(1)<O(log₂n)<O(n)<O(nlog₂n)<O(n²)<O(n³)<O(nk)<O(2^n)<O(n!)

3、空间复杂度：算法中需要的辅助(临时)变量所占用存储空间的大小
2. O(1)表示该算法执行所需辅助空间大小与问题规模n无关，称此算法为原地工作或就地工作算法。
在这里插入图片描述

  1. 算法分析的目的：分析算法的时空效率以便改进算法性能

1.5 类C语言有关操作说明

  1. 元素类型说明
typedef struct
{
	ElemType* data;
	int length;
}SqList;

  • 1
  • 2
  • 3
  • 4
  • 5
  • ElemType数据类型是为了描述统一而自定的，在实际应用中，可以自行更改；或者使用typedef重定义类型

如果数据元素是一个复杂类型，可以定义如下形式：

typedef struct
{
	float cofe;
	int expn;
}ElemType;

typedef struct
{
	ElemType* data;
	int length
}SqList;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

2.数组定义说明

数组静态分配：长度固定不可变

#define MaxSize 100

typedrf struct
{
	ElemType data[MaxSize];
	int length;
}SqList;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

数组动态分配：长度可变

#define MaxSize 10

typedrf struct
{
	ElemType* data;
	int length;
}SqList;

SqList L;
L.data =(ElemType*)malloc(sizeof(ElemType)*MaxSize);

//sizeof(ElemType)*MaxSize表示申请的字节数，一个元素所占字节数*元素个数

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  1. C++的动态存储分配

new 数据类型名L(初值列表)
功能：申请用于存储L类型对象的空间，并根据初值列表赋以初值
返回值：如果申请成功，则返回申请的空间地址；否则，返回NULL

delete§;
功能：释放指针p所指向的开辟内存

int* p = new int(10);

p中存放动态开辟的内存空间，空间中存放的是10

delete(p);

  • 1
  • 2
  • 3
  • 4
  • 5
  1. C++中引用类型作为参数
int i = 10;
int &j = i;

  • 1
  • 2
  • j的地址和值与i一模一样
  • 引用类型作为参数与指针作为参数效果一样，形参变化实参也发生变化
  • 引用类型作为参数并没有开辟新的空间，而是对实参直接操作

二、线性表

2.1 线性表的定义和特点

线性表：由n(n >= 0)个相同特性的数据元素a1、a2、…an构成的有限序列

  1. 数据元素的个数n定义表的长度
  2. 当n=0时称为空表
  3. 数据元素之间是线性关系

对于非空的线性表或线性结构，其特点是：

  1. 有且仅有一个起始结点a1，没有直接前驱，只有直接后继
  2. 有且仅有一个终端结点an，没有直接后继，只有直接前驱
  3. 其余内部节点ai(2≤i≤n-1)，有且仅有一个直接前驱和一个直接后继

2.2 线性表的表示和实现

线性表两种基本的存储结构：顺序存储结构和链式存储结构

2.2.1 线性表的顺序存储表示

顺序存储：用一组地址连续的存储单元把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构

假设每个元素占用k个字节，则第ai个元素的地址：Loc(ai) = Loc(a1) + (i - 1)*k
由此，可以得出：上述时间复杂度为O(1)，与n无关
只要确定了顺序表的起始位置，线性表中的任一元素都可以随机存取

顺序表具有地址连续、依次存放、随机存取、类型相同的特点，因此，可以用数组描述线性表的顺序存储结构
由于数组的大小不可动态定义，但线性表的表长需要动态变化，因此,增加一个变量表示顺序表的长度属性

（1）定义一个线性表类型

#define MAXSIZE 10

typedef struct
{
	ElemType* elem;    //存储时间的首地址
	int length;        //当前元素个数 
}SqList;


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

（2）初始化线性表：构造一个空的线性表

  1. 为顺序表动态分配一个·预定义大小的数组空间，使elem指向这段空间的首地址
  2. 将表的当前·长度设为0
Statue InitList_Sq(SqList* L)
{
	L->elem =(ElemType*)malloc(sizeof(ElemType)*MAXSIZE);
	if(!L->elem)
	{
		perror("error");
		exit (OVERFLOW);  //内存开辟失败，退出程序
	}
	L->length = 0;
	return OK;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

（3）销毁线性表：将线性表所占的空间内存释放掉

  1. 利用free()函数释放elem指向这段空间
void DestroyList_Sq(SqList* L)
{
	if(!L->elem)
	{
		free(L->elem);
	}
	L->elem = NULL; //虽然指向的空间释放了，但该指针变量仍然存放该空间的地址吗，应置空
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

（4）清空线性表：将线性表的元素清空

  1. 将线性表的长度置为0
void ClearList_Sq(SqList* L)
{
	L->length = 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5

（5）求线性表的长度：

int GetLength(const SqList* L)
{
	return (L->length);
}


  • 1
  • 2
  • 3
  • 4
  • 5

（6）判断线性表是否为空：

Statue IsEmpty(const SqList* L)
{
	if(0 == L->length)
	{
		return TRUE;
	}
	else
	{
		return FALSE;
	}
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

（7）取值：根据指定的位置序号i，获取顺序表中第二个元素的值

  1. 判断位置序号i是否合理(1≤i≤L.length)。若不合理，则返回ERROR
  2. 若合理，则将第i个数据元素赋值给e，通过e返回第i个数据元素
Statue GetElem(const SqList* L,int i,ElemType* e)
{
	if((i < 1) || (i > L->length))
	{
		return ERROR;
	}
	else
	{
		*e = L->elem[i-1];
		return OK;
	}
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 显然，该算法的时间复杂度为O(1)

（8）查找：根据指定的元素值e，查找第一个值与e相等的元素

  1. 从第一个元素起，依次将值和e比较，若找到，则返回元素序号i+1
  2. 若没有找到，则查找失败，返回0
int LocateElem(const SqList* L,const ElemType* e)
{
	int i = 0;
	for(i = 0;i < L->length;i++)
	{
		if(L->elem[i] == *e)
		{
			return (i+1);
		}
	}
	return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 查找次数取决于所查元素在表中的位置，根据平均期望得：
    平均查找次数：pi∑i = (n + 1) / 2
    在这里插入图片描述
  • 显然，该算法的平均时间复杂度为O(n)

（9）插入：根据线性表的第i个位置插入一个新的数据元素e

  1. 判断插入位置i是否合法(1≤i≤n+1)。若不合法，则返回ERROR
  2. 判断顺序表的存储空间是否已满。若满，则继续开辟新空间，如果开辟失败则返回ERROR
  3. 将第n个至第i个位置的元素依次向后移动一个位置，空出第i个位置（i = i +1时无需移动）
  4. 将要插入的新元素e放入第i个位置
  5. 表长加1
Statue ListInsert(SqList* L,int i,ElemType* e)
{
	//第一步：判断插入是否合法
	if((i < 1) || (i > L->length + 1))
	{
		return ERROR;
	}
	
	//第二步：开辟新空间	
	if(L->length == MAXSIZE)
	{
		ElemType* p = (ElemType*)realloc(L->elem,sizeof(ElemType)*(MAXSIZE + 1));
		if(p)
		{
			L->elem = p;
			p = NULL;
		}
		else
		{
			perror("error");
			return ERROR;
		}
	}
	
	//第三步：移动
	int j = 0;
	for(j = L->length - 1;j >= (i - 1);j--)
	{
		L->elem[j + 1] = L->elem[j];
	}
	//第四步：插入
	L->elem[i - 1] = *e;
	
	//第五步：表长加1
	L->length++;
	return OK;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 平均移动次数：
    在这里插入图片描述
  • 显然，该算法的平均时间复杂度为O(n)
  • 显然，该算法的空间复杂度为O(1)

（10）删除：将线性表的第i个数据元素删除

  1. 判断删除位置i是否合法(1≤i≤n)。若不合法，则返回ERROR
  2. 将第n个至第i+1个位置的元素依次向前移动一个位置，空出第i个位置（i = i +1时无需移动）
  3. 表长减1
Statue ListDelete(SqList* L,int i)
{
	//第一步：判断插入是否合法
	if((i < 1) || (i > L->length + 1))
	{
		return ERROR;
	}
	
	//第二步：移动
	int j = 0;
	for(j = i;j <= L->length - 1;j++)
	{
		L->elem[j - 1] = L->elem[j];
	}
	
	//第三步：表长减1
	L->length--;
	return OK;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 平均移动次数：
    在这里插入图片描述
  • 显然，该算法的平均时间复杂度为O(n)
  • 显然，该算法的空间复杂度为O(1)

2.2.2 线性表的顺序存储表示的完整实现及优、缺点

  • 完整代码：
#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 10
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status; 
typedef int ElemType;

//定义线性表类型 
typedef struct
{
	ElemType* elem;    //存储时间的首地址
	int length;        //当前元素个数 
}SqList;

//初始化线性表 
Status InitList_Sq(SqList* L)
{
	L->elem =(ElemType*)malloc(sizeof(ElemType)*MAXSIZE);
	if(!L->elem)
	{
		perror("error");
		exit (OVERFLOW);  //内存开辟失败，退出程序
	}
	L->length = 0;
	return OK;
}

//销毁线性表 
void DestroyList_Sq(SqList* L)
{
	if(!L->elem)
	{
		free(L->elem);
	}
	L->elem = NULL; //虽然指向的空间释放了，但该指针变量仍然存放该空间的地址吗，应置空
}

//清空线性表 
void ClearList_Sq(SqList* L)
{
	L->length = 0;
}

//求线性表长度 
int GetLength(const SqList* L)
{
	return (L->length);
}

//判断线性表是否为空 
Status IsEmpty(const SqList* L)
{
	if(0 == L->length)
	{
		return TRUE;
	}
	else
	{
		return FALSE;
	}
}


//取值 
Status GetElem(const SqList* L,int i,ElemType* e)
{
	if((i < 1) || (i > L->length))
	{
		return ERROR;
	}
	else
	{
		*e = L->elem[i-1];
		return OK;
	}
}

//查找元素 
int LocateElem(const SqList* L,const ElemType* e)
{
	int i = 0;
	for(i = 0;i < L->length;i++)
	{
		if(L->elem[i] == *e)
		{
			return (i+1);
		}
	}
	return 0;
}

//插入元素 
Status ListInsert(SqList* L,int i,ElemType* e)
{
	//第一步：判断插入是否合法
	if((i < 1) || (i > L->length + 1))
	{
		return ERROR;
	}
	
	//第二步：开辟新空间	
	if(L->length == MAXSIZE)
	{
		ElemType* p = (ElemType*)realloc(L->elem,sizeof(ElemType)*(MAXSIZE + 1));
		if(p)
		{
			L->elem = p;
			p = NULL;
		}
		else
		{
			perror("error");
			return ERROR;
		}
	}
	
	//第三步：移动
	int j = 0;
	for(j = L->length - 1;j >= (i - 1);j--)
	{
		L->elem[j + 1] = L->elem[j];
	}
	//第四步：插入
	L->elem[i - 1] = *e;
	
	//第五步：表长加1
	L->length++;
	return OK;
}

//删除元素 
Status ListDelete(SqList* L,int i)
{
	//第一步：判断插入是否合法
	if((i < 1) || (i > L->length + 1))
	{
		return ERROR;
	}
	
	//第二步：移动
	int j = 0;
	for(j = i;j <= L->length - 1;j++)
	{
		L->elem[j - 1] = L->elem[j];
	}
	
	//第三步：表长减1
	L->length--;
	return OK;
}


int main()
{
	SqList L;
	ElemType e;
	
	//初始化线性表 
	InitList_Sq(&L);
	
	int i = 0;
	for(i = 1;i <= 10;i++)
	{
		//插入元素 
		ListInsert(&L,i,&i);
	}
	
	printf("赋值之后的线性表：\n");
	for(i = 0;i < L.length;i++)
	{
		printf("%d ",L.elem[i]);
	}
	printf("\n");
	printf("当前元素个数：%d\n",GetLength(&L));
	printf("--------------\n"); 
	
	//插入一个元素 
	printf("请输入要插入的元素序号：");
	scanf("%d",&i);
	ListInsert(&L,i,&i);
	for(i = 0;i < L.length;i++)
	{
		printf("%d ",L.elem[i]);
	}
	printf("\n");
	printf("当前元素个数：%d\n",GetLength(&L));	
	printf("--------------\n"); 
	
	//删除一个元素 
	printf("请输入要删除的元素序号：");
	scanf("%d",&i); 
	ListDelete(&L,i); 
	
	printf("删除之后的线性表：\n"); 
	for(i = 0;i < L.length;i++)
	{
		printf("%d ",L.elem[i]);
	}
	printf("\n");
	printf("当前元素个数：%d\n",GetLength(&L));
	
	//销毁线性表 
	DestroyList_Sq(&L); 
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212

优点·：

  1. 存储密度大(结点本身所占存储量 / 结点结构所占存储量)
  2. 可以随机存取表中任一元素
    缺点·：
  3. 在插入、删除某一元素时，需要移动大量元素
  4. 浪费存储空间

2.2.3 线性表的链式存储表示及实现

链式存储：用一组任意的存储单元存储线性表的数据元素

  1. 这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上
  2. 逻辑次序和物理次序不一定相同

为了表示数据元素之间的逻辑关系，对于一个数据元素而言，除了存储其本身的数据元素外，还需要存储直接后继的地址。这两部分信息组成数据元素ai的存储映像，叫做结点(node)。
结点的数据域：存储数据元素信息的域
结点的指针域：存储直接后继地址的域

在这里插入图片描述

2.2.3.1 单链表的表示及实现

单链表：此链表的每个节点中只包含一个指针域

单链表的存取必须从头指针开始进行，头指针指向链表中第一个结点（第一个数据元素的存储映像，也称首元结点）。同时，最后一个数据元素没有直接后继，所以最后一个结点的指针为空(NULL)

数据元素之间的逻辑关系是由结点中的指针指示的，也就是说，指针为数据元素之间的逻辑关系映像

单链表还分为是否带头节点两种情况：
（1）不带头节点
在这里插入图片描述
注：示意图仅仅是数据元素之间的逻辑顺序，而不是每个数据元素在内存中的实际位置
（2）带头节点
在这里插入图片描述
说明：
（1）首元结点：指链表中存储第一个数据元素a1的结点
（2）头结点：在逻辑关系上位于首元结点之前，其指针域指向首元结点；数据域可以为空，也可以存储表长等附加信息，但此节点不计入链表长度值
（3）头指针：指向链表中第一个结点的指针

头结点的作用：

  1. 便于首元结点的处理
    首元结点的地址保存在头结点的指针域，对链表中的第一个数据元素操作和其他数据元素的操作相同
  2. 便于空表和非空表的统一处理
    无论链表是否为空，头指针都是非空指针。是否为空表，只需判断 L->next是否为NULL

链表的特点：

  1. 各个元素的存储位置都是任意的
  2. 单链表是顺序存取的存储结构。每个元素的存储位置都包含在其直接前驱结点的指针域中。访问时只能通过头指针进入链表，通过每个结点的指针域，依次访问剩余结点

（1）单链表的类型定义

typedef struct LNode
{
	ELemType data;        //数据域
	struct LNode* next;   //指针域
}LNode,*LinkList;         //LinkList为指向结构体LNode的指针类型

  • 1
  • 2
  • 3
  • 4
  • 5
  • 上述声明，定义了一个结构体LNode，给struct LNode取个别名为LNode，给struct LNode*取个别名为LinkList
  • 通常，用LinkList定义链表，即作为头指针；用LNode* 定义结点指针

（2）单链表的初始化

  1. 生成新节点作为头节点，用头指针L指向头节点
  2. 头结点的指针域置空
Status InitList(LinkList* L)
{
	*L = (LinkList)malloc(sizeof(LNode));
	if(NULL == *L)
	{
		perror("error");
		exit (OVERFLOW);  //内存开辟失败，退出程序
	} 
	(*L)->next = NULL;
	return OK;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

（3）判断单链表是否为空（链表中无元素，头指针与头结点依然存在）

  1. 判断头结点的指针域是否为空
  2. 若为空指针，则是空表；反之，为非空表
int IsEmptyLinkList(const LinkList L)
{
	if((L->next) == NULL)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

（4）销毁单链表

  1. 创建一个结点指针变量，用来指向即将删除的结点
  2. 头指针指向下一个结点
  3. 如果头指针为非空，则重复（1）、（2），否则结束

传值：

Status DestoryLinkList(LinkList L)
{
	LNode* p;
	while(L)
	{
		p = L;   //即将销毁的结点
		L = L->next;  //指向下一个结点
		free(p);
	}
	//L = NULL;  要对链表指针置空，表示不存在
	//但是这句在这里无效，因为这是传值操作 
	//要在调用该函数之后，附加该语句
	return OK;
} 


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

传址：

Status DestoryLinkList(LinkList* L)
{
	LNode* p;
	while(*L)   //当循环跳出时，则 *L=NULL ，已经将链表指针置空
	{
		p = *L;  //记录要删除的结点地址
		*L = (*L)->next;  //头指针指向下一个节点 
		free(p);
	}
	return OK;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

（4）清空单链表（无数据元素，但头指针和头结点依然存在）

  1. 创建两个结点指针变量，一个用来指向即将删除的结点，一个用来指向下一个结点
  2. 如果指向下一个结点的指针域为非空，则重复（1）、（2），否则结束
  3. 将头结点的指针域置空
Status ClearLinkList(LinkList L)
{
	LNode* p,* q;
	q = L->next;  //首元地址赋给指针q 
	while(q)   
	{
		p = q;  //记录要删除的结点地址 
		q = p->next;  //指向下一个节点 
		free(p);
	}
	L->next = NULL;  //将头结点的指针域置空 
	return OK;
} 


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

（5）求单链表的表长

  1. 从首元结点开始，依次计数所有结点
  2. 如果遇到结点的指针域为空，则停止计数
int LenLinkList(const LinkList L)
{
	int length = 0;
	LNode* p;
	p = L->next;  //首元地址赋给结点指针p 
	while(p)   
	{
		length++;
		p = p->next;  //记录下一结点的地址 
	}
	return length;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

（6）单链表的取值

  1. 用结点指针p指向首元节点，用计数器记录结点的个数
  2. 只要当前结点的指针p不为空，且没有达到序号i的结点，一直循环以下操作：
    p指向下一个结点
    计数器加1
  3. 结束循环后，要判断指针p为空和计数器是否合法，则取值失败，返回ERROR；否则取值成功，p所指向的结点就是要找的第i个结点
Status GetElemLinkList(const LinkList L,int i,ElemType* e)
{
	LNode* p = L;
	int count = 1;
	while(p && (count < i))   //取第i个元素，实质是找到第i-1个结点的指针域 
	{
		p = p->next;
		count++; 
	}
	if(!p || (count > i))   //第i-1个结点的指针域不可能为空;第i个元素不存在 
	{
		return ERROR;
	}
	else
	{
		*e = p->data;
		return OK;
	}
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

（7）单链表的查找

  1. 用结点指针p指向第i-1个结点
  2. 只要当前结点的指针p不为空，且指针所指向的数据域不等于给定值，一直循环以下操作：
    p指向下一个结点
  3. 结束循环后，返回p。若查找成功，则返回该结点的地址；否则，返回NULL
LNode* LocElemLinkList(const LinkList L,const ElemType* e)
{
	LNode* p = L->next;
	while(p && (p->data != (*e)))   
	{
		p = p->next;
	}
	return p;
} 


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

在这里插入图片描述

（8）单链表的插入，插入第ai-1和ai之间

  1. 查找结点ai-1，用结点指针p指向该结点
  2. 开辟新空间，生成新节点s
  3. 将结点s的数据域置为e；结点s的指针域指向ai；ai-1结点的指针域指向新结点s

在这里插入图片描述

Status LinkListInsert(LinkList L,int i,const ElemType* e)
{
	LNode* p = L;
	int j = 0;
	while(p && (j < (i-1)))     //找到第i-1个结点的位置 
	{							//如果i是非正数，则输入值不合法 
		p = p->next;
		j++;
	}
	if(!p || j >(i - 1))
	{
		return ERROR;
	}
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if(!s)
	{
		perror("error");
		exit (OVERFLOW);  //内存开辟失败，退出程序
	} 
	s->data = *e;       
	s->next = p->next;  //将后继结点地址存储在新结点的数据域中 
	p->next = s;		//将新结点地址存储在前继结点的数据域中 
	return OK;
} 


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

（9）单链表的删除

  1. 查找结点ai-1，用结点指针p指向该结点
  2. 新建临时结点指针变量，用于存放被删除结点的地址
  3. 将结点*p的指针域指向被删除的后继结点
  4. 释放被删除的节点空间
Status LinkListDelete(LinkList L,int i)
{
	LNode* p = L,* q;
	int j = 0;
	while((p->next) && (j < (i-1)))     //找到第i-1个结点的位置 
	{							//如果i是非正数，则输入值不合法 
		p = p->next;
		j++;
	}
	if(!(p->next) || j >(i - 1)) //如果i超过表长，则p->next=NULL
	{							 //如果i<1，则也不合法
		return ERROR;
	}
	
	q = p->next;  //保存被删除结点的地址
	p->next = q->next;  //被删除的结点的直接前继的指针域发生改变 
	free(p);
	p = NULL; 
	return OK;
} 


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

在这里插入图片描述

  • 线性表的建立：

（1）前插法

  1. 创建一个只有头结点的空链表
  2. 根据创建链表的元素个数n，循环n次以下操作：
    ①生成一个新节点*p
    ②输入元素值赋值给新结点的数据域
    ③将新结点插入头结点之后
  • 每次插入的元素都在链表的头部，所以应该逆序输入数据
    在这里插入图片描述
void HeadInsert(LinkList* L,int n)
{
	*L = (LinkList)malloc(sizeof(LNode));
	if(NULL == *L)
	{
		perror("error");
		exit (OVERFLOW);  //内存开辟失败，退出程序
	} 
	(*L)->next = NULL;
	int i = 0,k = 0;
	for(i = 0;i < n;i++)
	{
		LNode* p = (LNode*)malloc(sizeof(LNode));
		if(!p)
		{
			perror("error");
			exit (OVERFLOW);  //内存开辟失败，退出程序
		}
		scanf("%d",&k);
		p->data = k;
		p->next = (*L)->next;
		(*L)->next = p; 
	}
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 显然，该算法的时间复杂度为O(n)
    （2）尾插法
  1. 创建一个只有头结点的空链表
  2. 尾指针r初始化，指向头结点
  3. 根据创建链表的元素个数n，循环n次以下操作：
    ①生成一个新节点*p
    ②输入元素值赋值给新结点的数据域
    ③将新结点插入尾结点之后
    ④r指向新的尾结点
  • 每次插入的元素都在链表的尾部，所以应该正序输入数据
void TailInsert(LinkList* L,int n)
{
	*L = (LinkList)malloc(sizeof(LNode));
	if(NULL == *L)
	{
		perror("error");
		exit (OVERFLOW);  //内存开辟失败，退出程序
	} 
	(*L)->next = NULL;
	LNode* r = L;
	int i = 0,k = 0;
	for(i = 0;i < n;i++)
	{
		LNode* p = (LNode*)malloc(sizeof(LNode));
		if(!p)
		{
			perror("error");
			exit (OVERFLOW);  //内存开辟失败，退出程序
		}
		scanf("%d",&k);
		p->data = k;
		p->next = NULL;
		r->next = p;
		r = p;
	}
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 显然，该算法的时间复杂度为O(n)

单链表的完整代码实现：

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

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status; 
typedef int ElemType;

//定义一个链表类型
typedef struct LNode
{
	ElemType data;
	struct LNode* next;
}LNode,*LinkList; 

//单链表的初始化
Status InitList(LinkList* L)
{
	*L = (LinkList)malloc(sizeof(LNode));
	if(NULL == *L)
	{
		perror("error");
		exit (OVERFLOW);  //内存开辟失败，退出程序
	} 
	(*L)->next = NULL;
	return OK;
}

//判断链表为空 
int IsEmptyLinkList(const LinkList L)
{
	if((L->next) == NULL)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

//销毁单链表
/*
Status DestoryLinkList(LinkList L)
{
	LNode* p;
	while(L)
	{
		p = L;
		L = L->next;
		free(p);
	}
	//L = NULL;  要对链表指针置空，表示不存在，但是这句在这里无效，因为这是传值操作 
	return OK;
} 
*/
Status DestoryLinkList(LinkList* L)
{
	LNode* p;
	while(*L)   //当循环跳出时，则 *L=NULL ，已经将链表指针置空 
	{
		p = *L;  //记录要删除的结点地址 
		*L = (*L)->next;  //头指针指向下一个节点 
		free(p);
	}
	return OK;
} 

//清空单链表
Status ClearLinkList(LinkList L)
{
	LNode* p,* q;
	q = L->next;  //首元地址赋给指针q 
	while(q)   
	{
		p = q;  //记录要删除的结点地址 
		q = p->next;  //指向下一个节点 
		free(p);
	}
	L->next = NULL;  //将头结点的指针域置空 
	return OK;
} 

//求单链表的表长
int LenLinkList(const LinkList L)
{
	int length = 0;
	LNode* p;
	p = L->next;  //首元地址赋给指针p 
	while(p)   
	{
		length++;
		p = p->next;  //记录下一结点的地址 
	}
	return length;
} 

//单链表的取值
Status GetElemLinkList(const LinkList L,int i,ElemType* e)
{
	LNode* p = L->next;
	int count = 1;
	while(p && (count < i))   //取第i个元素，实质是找到第i-1个结点的指针域 
	{
		p = p->next;
		count++; 
	}
	if(!p || (count > i))   //第i-1个结点的指针域不可能为空
	{						//如果i是非正数，则输入值不合法 
		return ERROR;
	}
	else
	{
		*e = p->data;
		return OK;
	}
} 

//单链表的查找
LNode* LocElemLinkList(const LinkList L,const ElemType* e)
{
	LNode* p = L->next;
	while(p && (p->data != (*e)))   
	{
		p = p->next;
	}
	return p;
} 

//单链表的插入：在第i个元素前插入 
Status LinkListInsert(LinkList L,int i,const ElemType* e)
{
	LNode* p = L;
	int j = 0;
	while(p && (j < (i-1)))     //找到第i-1个结点的位置 
	{							//如果i是非正数，则输入值不合法 
		p = p->next;
		j++;
	}
	if(!p || j >(i - 1))
	{
		return ERROR;
	}
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if(!s)
	{
		perror("error");
		exit (OVERFLOW);  //内存开辟失败，退出程序
	} 
	s->data = *e;       
	s->next = p->next;  //将后继结点地址存储在新结点的数据域中 
	p->next = s;		//将新结点地址存储在前继结点的数据域中 
	return OK;
}  

//删除结点
Status LinkListDelete(LinkList L,int i)
{
	LNode* p = L,* q;
	int j = 0;
	while((p->next) && (j < (i-1)))     //找到第i-1个结点的位置 
	{							//如果i是非正数，则输入值不合法 
		p = p->next;
		j++;
	}
	if(!(p->next) || j >(i - 1))
	{
		return ERROR;
	}
	
	q = p->next;  //保存被删除结点的地址
	p->next = q->next;  //被删除的结点的直接前继的指针域发生改变 
	free(p);
	p = NULL; 
	return OK;
}

//前插法创建单链表
void HeadInsert(LinkList* L,int n)
{
	*L = (LinkList)malloc(sizeof(LNode));
	if(NULL == *L)
	{
		perror("error");
		exit (OVERFLOW);  //内存开辟失败，退出程序
	} 
	(*L)->next = NULL;
	int i = 0,k = 0;
	for(i = 0;i < n;i++)
	{
		LNode* p = (LNode*)malloc(sizeof(LNode));
		if(!p)
		{
			perror("error");
			exit (OVERFLOW);  //内存开辟失败，退出程序
		}
		scanf("%d",&k);
		p->data = k;
		p->next = (*L)->next;
		(*L)->next = p; 
	}
}

//尾插法创建单链表
void TailInsert(LinkList* L,int n)
{
	*L = (LinkList)malloc(sizeof(LNode));
	if(NULL == *L)
	{
		perror("error");
		exit (OVERFLOW);  //内存开辟失败，退出程序
	} 
	(*L)->next = NULL;
	LNode* r = *L;
	int i = 0,k = 0;
	for(i = 0;i < n;i++)
	{
		LNode* p = (LNode*)malloc(sizeof(LNode));
		if(!p)
		{
			perror("error");
			exit (OVERFLOW);  //内存开辟失败，退出程序
		}
		scanf("%d",&k);
		p->data = k;
		p->next = NULL;
		r->next = p;
		r = p;
	}
}

void PrintLinkList(const LinkList L)
{
	LNode* p = L->next;  //首元节点的地址
	if(!p)
	{
		printf("该链表为空\n");
	}
	while(p)
	{
		printf("%d ",p->data);
		p = p->next;	
	}
	printf("\n");	
} 

int main()
{
	int i = 0;
	//定义一个链表，即为头指针
	LinkList L;
	
	//初始化单链表
	//InitList(&L);
	
	printf("请输入数据："); 
	//创建新链表 
	TailInsert(&L,10); 
	
	printf("目前该链表中所有元素的值：");
	PrintLinkList(L);
	
	printf("请输入要插入的元素序号：");
	scanf("%d",&i);
	LinkListInsert(L,i,&i);
	
	printf("目前该链表中所有元素的值：");
	PrintLinkList(L);
	
	DestoryLinkList(&L);
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236
  • 237
  • 238
  • 239
  • 240
  • 241
  • 242
  • 243
  • 244
  • 245
  • 246
  • 247
  • 248
  • 249
  • 250
  • 251
  • 252
  • 253
  • 254
  • 255
  • 256
  • 257
  • 258
  • 259
  • 260
  • 261
  • 262
  • 263
  • 264
  • 265
  • 266
  • 267
  • 268
  • 269
  • 270
  • 271
  • 272
  • 273
  • 274
  • 275
  • 276
  • 277
2.2.3.2 循环链表

循环链表：是一种头尾相接地链表，表中最后一个节点的指针域指向头结点，整个链表形成形成一个环
优点：从表中任一结点出发均可找到表中其他结点

在这里插入图片描述

  • 循环单链表的操作和单链表基本一致，差别仅在于：当涉及遍历操作时，循环中止的条件为：尾元素的指针域是否等于头指针

对于循环链表而言，使用尾指针更加便捷

在这里插入图片描述
尾指针不仅使寻找an的时间复杂度大大降低，还可以使一些操作简化，例如：将两个循环线性表合成一个表时：
①保存Ta表的头结点
②将Ta的表尾连接到Tb的首元结点
③释放Tb的头结点
④将Tb的表尾元素中的指针域修改为Ta头结点的地址
在这里插入图片描述

2.2.3.3 双向链表

双向链表：在节点中有两个指针域，一个指向直接前驱，一个指向直接后继
在这里插入图片描述

双向链表的结构定义

typedef struct DuLNode
{
	ElemType data;            //数据域
	struct DuLNode *prior;    //指向直接前驱
	struct DuLNode *next;     //指向直接后继
}DuLNode,* DuLinkList;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

在这里插入图片描述

  • 双向循环链表中具有对称性，如果d为某结点的指针，则有
    d->next->prior = d =d->prior->next ;
    在这里插入图片描述
    在双向链表中，求表长、查找某个元素等仅需涉及一个方向的指针，则他们的算法描述与线性链表相同，但在插入和删除却有很大的不同

双向链表的插入：

在这里插入图片描述
在这里插入图片描述

  • 显然，该算法的时间复杂度为O(n)

双向链表的删除：

在这里插入图片描述
在这里插入图片描述

  • 显然，该算法的时间复杂度为O(n)
2.2.3.4 单链表、循环链表、双向链表的时间复杂度比较

依次比较寻找头结点(首元结点)、表尾结点、查找结点*p的直接前驱的时间复杂度：
在这里插入图片描述

2.2.3.5 链式存储的优缺点

在这里插入图片描述

2.2.4 顺序表与链表的比较

在这里插入图片描述

三、栈和队列

栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是操作受限的线性表

3.1 栈的定义和特点

  • 栈（stack）是限定仅在表尾进行插入或删除操作的线性表。对栈而言，表尾称为栈顶（Top），表头称为栈底（base），不含元素的空表称为空栈。因此，栈又称为后进先出（last-in-first-out）的线性表（简称LIFO）。插入元素到栈顶称为入栈（Push），从栈顶删除一个元素称为出栈（Pop）。
  • 对于单链表的头插法创建，就相当于一个栈
  • 栈与线性表的区别：
    在这里插入图片描述
  • 栈的部分应用场景：
    在这里插入图片描述

3.2 栈的表示和实现

栈作为一种操作受限制的线性表，存储结构与线性表示相同，有顺序栈和和链栈

  1. 顺序栈的表示及实现
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

使用数组作为顺序栈存储方式的特点：简单、方便、但易产生溢出

  • 上溢（overflow）：栈已经满，仍要压入元素
  • 下溢（underflow）：栈已经空，仍要弹出元素

注：上溢是一种错误，使问题的处理无法进行；而下溢一般认为是一种结束条件，即问题处理结束

(1)顺序栈的存储结构

#define MAXSIZE 10

typedef struct
{
	SElemType *base;  //栈底指针 
	SElemType *top;   //栈顶指针 
	int stacksize;    //栈的最大容量
}SqStack;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

(2)初始化：

  1. 为顺序栈分配一个容量为MAXSIZE大小的数组空间，使base指向这段空间的基地址，即栈底
  2. 栈顶指针top指向base，表示栈为空
  3. stacksize置为栈的最大容量MAXSIZE
Status InitStack(SqStack *S)
{
	//为顺序栈申请空间，栈底指针指向此空间的首地址 
	S->base = (SElemType*)malloc(sizeof(SElemType)*MAXSIZE);
	if(!S->base)
	{
		perror("error");
		exit(OVERFLOW);
	} 
	
	//栈顶指针=栈底指针，表示空栈 
	S->top =  S->base;
	
	//stacksize置为栈的最大容量MAXSIZE
	S->stacksize = MAXSIZE; 
	return OK;
} 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

(3)判断栈是否为空：

  1. 栈顶指针top是否等于栈底指针base
  2. 如果相等则为空，反之则非空
Status StackEmpty(const SqStack S)
{
	if(S.base == S.top) 
	{
		return TRUE;
	}
	else
	{
		return FALSE;
	}
} 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

(4)求栈的长度：

  1. 栈顶指针 - 栈底指针所得值，为元素个数，就是栈的长度
int StackLength(const SqStack S) 
{
	return (S.top-S.base);
}

  • 1
  • 2
  • 3
  • 4

(5)清空顺序栈 ：

  1. 将栈顶指针指向栈底指针所指的空间
Status ClearStack(SqStack *S) 
{
	//如果栈存在 
	if(S->base)
	{
		S->top = S->base;		
	}
	return OK;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

(6)销毁顺序栈 ：

  1. 将栈底指针所指的空间释放
  2. 栈顶指针、栈底指针均置空
  3. stacksize置为0
Status DestoryStack(SqStack *S)
{
	if(S->base)
	{
		free(S->base);
		S->base = NULL;
		S->top = NULL;
		S->stacksize = 0;
	}
	return OK;
} 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

(7)入栈 ：

  1. 判断栈是否满，如果满则错误
  2. 将新元素压入栈顶
  3. 栈顶指针加1
Status Push(SqStack *S,const SElemType *e)
{
	//栈满，若要压栈，则会产生栈上溢出 
	if(S->top-S->base == S->stacksize)
	{
		return ERROR; 
	}
	*(S->top) = *e;
	S->top++;
	return OK;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

(8)出栈 ：

  1. 判断栈是否空，如果空则错误
  2. 栈顶指针减1
  3. 将栈顶指针所指元素出栈
Status Push(SqStack *S,SElemType *e)
{
	//栈空，若要出栈，则会产生栈下溢出 
	if(S->top == S->base)
	{
		return ERROR; 
	}
	S->top--;
	*e = *(S->top);
	return OK;
}
 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 顺序栈的完整代码：
#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 10
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status; 
typedef int SElemType;

//定义顺序栈的存储结构 
typedef struct
{
	SElemType *base;  //栈底指针 
	SElemType *top;   //栈顶指针 
	int stacksize;    //栈的最大容量
}SqStack;

//初始化
Status InitStack(SqStack *S)
{
	//为顺序栈申请空间，栈底指针指向此空间的首地址 
	S->base = (SElemType*)malloc(sizeof(SElemType)*MAXSIZE);
	if(!S->base)
	{
		perror("error");
		exit(OVERFLOW);
	} 
	
	//栈顶指针=栈底指针，表示空栈 
	S->top =  S->base;
	
	//stacksize置为栈的最大容量MAXSIZE
	S->stacksize = MAXSIZE; 
	return OK;
} 

//判断栈是否为空
Status StackEmpty(const SqStack S)
{
	if(S.base == S.top) 
	{
		return TRUE;
	}
	else
	{
		return FALSE;
	}
}

//求栈的元素个数 
int StackLength(const SqStack S) 
{
	return (S.top-S.base);
}

//清空顺序栈 
Status ClearStack(SqStack *S) 
{
	//如果栈存在 
	if(S->base)
	{
		S->top = S->base;		
	}
	return OK;
}

//销毁顺序栈
Status DestoryStack(SqStack *S)
{
	if(S->base)
	{
		free(S->base);
		S->base = NULL;
		S->top = NULL;
		S->stacksize = 0;
	}
	return OK;
} 

//入栈
Status Push(SqStack *S,const SElemType *e)
{
	//栈满，若要压栈，则会产生栈上溢出 
	if(S->top-S->base == S->stacksize)
	{
		return ERROR; 
	}
	*(S->top) = *e;
	S->top++;
	return OK;
}

//出栈
Status Pop(SqStack *S,SElemType *e)
{
	//栈空，若要出栈，则会产生栈下溢出 
	if(S->top == S->base)
	{
		return ERROR; 
	}
	S->top--;
	*e = *(S->top);
	return OK;
}
 
 int main()
 {
 	//定义顺序栈S 
 	SqStack S;
 	
 	//初始化顺序栈 
	InitStack(&S);
	
	//销毁顺序栈 
	DestoryStack(&S); 
 	return 0;
 }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  1. 链栈的表示及实现

链栈是运算受限的单链表，只能在链表头部进行操作

![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/2e88b6b45b714f8abb67bc4806f8ea08.png#pic_center

  • 和链表的头插法实现相同

(1)链栈的存储结构

typedef struct StackNode
{
	SElemType data;
	struct StackNode *next;
}StackNode,*LinkStack;      //这里的LinkStack是struct StackNode *类型 

  • 1
  • 2
  • 3
  • 4
  • 5

(2)链栈的初始化

  1. 构造一个空栈，将栈顶指针置空
Status InitStack(LinkStack *S)
{
	*S = NULL;
	return OK;	
} 

  • 1
  • 2
  • 3
  • 4
  • 5

(3)判断链栈是否为空

  1. 判断栈顶指针是否等于NULL
Status StackEmpty(const LinkStack S)
{
	if(S == NULL)
	{
		return TRUE;
	}
	return FALSE;
} 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

(4)入栈

  1. 为入栈元素分配空间，用指针p指向该空间
  2. 将新结点的数据域置为e
  3. 将新节点的插入栈顶
  4. 修改栈顶指针为p
Status Push(LinkStack *S,SElemType *e)
{
	//为入栈元素分配空间
	StackNode *p = (StackNode *)malloc(sizeof(StackNode));
	if(!p)
	{
		perror("error");
		exit(OVERFLOW);	
	}
	p->data = *e;
	p->next = *S;
	*S = p;
	p = NULL; 
	return OK;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

(5)出栈

  1. 判断栈是否为空，若为空，则返回ERROR
  2. 用指针变量p记录出栈元素所在的结点地址
  3. 栈顶指针指向下一个位置
  4. 释放原栈顶元素的空间
Status Pop(LinkStack *S)
{
	//判断栈是否为空
	if((*S == NULL))
	{
		return ERROR;
	}
	
	//记录出栈元素所在的结点地址
	StackNode *p = *S;
	
	//栈顶指针指向下一个位置
	*S = (*S)->next;
	
	//删除结点
	free(p);
	p = NULL; 
	return OK;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

(6)获得栈顶元素

  1. 判断栈是否为空，若为空，则返回ERROR
  2. 不为空，则返回当前栈顶元素
SElemType GetTop(const LinkStack S) 
{
	if(S)
	{
		return S->data;
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 链表的完整代码实现：
#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status; 
typedef int SElemType;

//链栈的存储结构
typedef struct StackNode
{
	SElemType data;
	struct StackNode *next;
}StackNode,*LinkStack;      //这里的LinkStack是struct StackNode *类型 

//链栈的初始化
Status InitStack(LinkStack *S)
{
	*S = NULL;
	return OK;	
} 

//判断链栈是否为空
Status StackEmpty(const LinkStack S)
{
	if(S == NULL)
	{
		return TRUE;
	}
	return FALSE;
} 

//入栈
Status Push(LinkStack *S,SElemType *e)
{
	//为入栈元素分配空间
	StackNode *p = (StackNode *)malloc(sizeof(StackNode));
	if(!p)
	{
		perror("error");
		exit(OVERFLOW);	
	}
	p->data = *e;
	p->next = *S;
	*S = p;
	p = NULL; 
	return OK;
}

//出栈 
Status Pop(LinkStack *S)
{
	//判断栈是否为空
	if((*S == NULL))
	{
		return ERROR;
	}
	
	//记录出栈元素所在的结点地址
	StackNode *p = *S;
	
	//栈顶指针指向下一个位置
	*S = (*S)->next;
	
	//删除结点
	free(p);
	p = NULL; 
	return OK;
}

//取栈顶元素
SElemType GetTop(const LinkStack S) 
{
	if(S)
	{
		return S->data;
	}
}

int main()
{
	
	return 0;
} 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89

3.3 栈与递归

递归、递归定义：在一个函数、过程或者数据结构定义的内部又直接（或间接）出现定义本身的应用

以下三种情况常常用到递归情况：

  1. 递归定义的数学函数
    在这里插入图片描述

分治法：对于一些复杂的问题，若将其分解成几个相对简单且解法相同或类似的子问题来求解

利用“分治法”进行求解递归的问题，常常满足以下3个条件：
①能将一个问题转变成一个新问题，而新问题与原问题的解法相同或类似，不同的是处理的对象，并且其处理的对象更小且变化有规律（每次调用越来越接近递归终止条件）
②可以通过上述转化使问题简化
③必须有一个明确的递归出口或递归边界

  • 一般形式
void p(参数表)
{
	if(递归结束条件成立)      //递归终止条件
		可直接求解；
	else
		p(较小的参数);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  1. 具有递归特性的数据结构
  • 比如，链表、二叉树、广义表等，都是递归的数据结构

遍历输出链表中各个结点的递归算法

void TraverseList(LinkList p)
{
	if(p == NULL)     递归终止条件
				;
	else
	{
		printf("%d ",p->data);
		TraverseList(p->next);
	}
		
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  1. 可递归求解的问题
    虽然问题本身没有明显的递归结构，但是用递归求解比迭代求解更简单，比如：Hanoi(汉诺)塔问题、八皇后问题、迷宫问题

-递归过程与递归工作栈
在这里插入图片描述
当多个函数构成嵌套调用时，按照“后调用先返回”的原则，就需要用栈来实现
在这里插入图片描述
在这里插入图片描述

  • 使用递归的优缺点：
    在这里插入图片描述
  • 递归转化为非递归的方法：
    在这里插入图片描述
    （1）方法1的示例
    在这里插入图片描述
    （2）借助栈改写递归的步骤
    在这里插入图片描述

3.4 队列的定义和特点

  • 队列（queue）是一种先进先出（first-in-first-out，FIFO）的线性表，它只允许在表的一端进行插入，在表的另一端进行删除元素（头删尾插）。在队列中，允许插入的一端叫做队尾（Rear），允许删除的一端叫做队头（Front）。插入操作称为入队，删除操作称为出队。
  • 队列的部分应用场景：
    在这里插入图片描述

3.5 队列的表示和实现

队列作为一种操作受限制的线性表，有顺序队列和和链式队列

  1. 顺序队列的表示及实现

（1）队列的顺序存储结构

typedef struct
{
	QElemType *base;  //存储空间的首地址
	int front;        //队头元素所在的下标 
	int rear; 		  //队尾元素所在的下标 
}SqQueue; 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

在这里插入图片描述
当队列中Q.rear = MAXSIZE时，且0≤Q.front≤ MAXSIZE - 1，当新元素入队时，则会产生溢出，事实上，队列的空间并未占满，称为“假溢出”

  • 解决假溢出的方法：
    假溢出
  • 循环队列的实现方法：
    在这里插入图片描述

但是会出现以下问题：无法判断栈空和栈满
在这里插入图片描述

解决方法

  1. 少用一个元素空间
    在这里插入图片描述
    循环队列的实现：

（1）队列的初始化

  1. 为队列分配一个MAXSIZE大小的数据空间，base指向数组空间的首地址
  2. 将头指针和尾指针都置0，表示队列为空
Status InitQueue(SqQueue *Q) 
{
	//申请空间 
	Q->base = (QElemType *)malloc(sizeof(QElemType)*MAXSIZE);
	if(Q->base == NULL)
	{
		perror("error");
		exit(OVERFLOW);
	}
	
	//将队置空 
	Q->front = 0;
	Q->rear = 0;
	return OK;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

（2）求队列的长度

  1. 对于非循环队列，Q.rear - Q.front就是队列长度，为正数
  2. 对于循环队列Q.rear、Q.front范围[0~5] ，可正可负，若为负数，则差值为剩余空间，加上MAXSIZE就是队列长度
  3. 对于图中第一种情况，在为正数的情况下加上MAXSIZE就超出了队列的最大长度，要对MAXSIZE取余才能得出正确结果；在为负数的情况下，取余或不取余都不影响正确结果
int QueueLength(SqQueue Q)
{
	//Q.rear、Q.front范围[0~5] ，若为负数，则差值为剩余空间，加上MAXSIZE，对MAXSIZE取余就是队列长度 
	return (Q.rear - Q.front + MAXSIZE)%MAXSIZE;	
} 

  • 1
  • 2
  • 3
  • 4
  • 5

在这里插入图片描述

（3）入队

  1. 判断队列是否满，若满则返回ERROR
  2. 将新元素插入队尾
  3. 队尾指针加1
Status EnQueue(SqQueue *Q,QElemType *e)
{
	//队满，返回ERROR 
	if((Q->rear + 1)%MAXSIZE == Q->front)
	{
		return ERROR;
	}
	
	//新数据元素入队
	Q->base[Q->rear] = 	*e;
	
	//尾指针加1
	Q->rear = (Q->rear + 1) % MAXSIZE;
	return OK;
} 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

（4）出队

  1. 判断队列是否空，若空则返回ERROR
  2. 将元素从队头出队
  3. 队头指针加1
Status DeQueue(SqQueue *Q,QElemType *e)
{
	//队空，返回ERROR 
	if(Q->rear == Q->front)
	{
		return ERROR;
	}
	
	//数据元素出队
	*e = Q->base[Q->front];
	
	//头指针加1
	Q->front = (Q->front + 1) % MAXSIZE;
	return OK;
} 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

（5）取队头元素

  1. 判断队列是否空
  2. 若不为空，将队头元素返回
Status GetHead(SqQueue Q)
{
	if(Q.rear != Q.front)
	{
		return Q.base[Q.front];
	}
} 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  1. 链式队列的表示及实现
  • 一个链队需要头指针和尾指针分别指向队头、队尾，才能唯一确定。为方便操作，给链队队列添加一个头结点，并令头指针始终指向头结点

在这里插入图片描述

（1）链式队列的类型定义

typedef struct QNode
{
	QElemType data;
	struct QNode *next;
}QNode,*QueuePtr;

typedef strcut
{
	QueuePtr front;  //头指针
	QueuePtr rear;   //尾指针 
}LinkQueue; 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

在这里插入图片描述

（2）链式队列的初始化

  1. 生成新节点作为头结点，头指针和尾指针指向此节点，构造空队列
  2. 头节点的指针域置空
Status InitQueue(LinkQueue *Q)
{
	//构造空队列 
	Q->front = (QueuePtr)malloc(sizeof(QNode));
	if(Q->front == NULL)
	{
		perror("error");
		exit(OVERFLOW);	
	} 
	Q->rear = Q->front;

	//将头结点的指针域置空 
	Q->rear->next = NULL; 

}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

（3）链式队列的销毁

  1. 判断头指针是否为空，若为空直接返回
  2. 若不为空，设置临时指针变量p对下一个结点的地址临时保存
  3. 释放头指针所指向的结点空间
  4. 将临时指针变量p赋值给头指针
Status DestroyQueue(LinkQueue *Q)
{
	//头指针指向不为空 
	while(Q->front)
	{
		//将下一个结点的地址临时保存 
		QNode *p = Q->front->next;
		
		//释放当前结点 
		free(Q->front);
		 
		Q->front = p;	
	} 
	return OK; 
} 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 当然，也可以用尾指针代替临时指针变量p，同位置上的替换即可

（4）入队

  1. 将入队元素分配结点空间，用指针p指向该空间
  2. 将新结点的数据域置为e，指针域置空
  3. 将新节点插入到队尾
  4. 修改队尾的指针为p
Status EnQueue(LinkQueue *Q,QElemType *e)
{
	//为新元素入队，申请新空间 
	QNode *p = (QueuePtr)malloc(sizeof(QNode));
	if(p == NULL)
	{
		perror("error");
		exit(OVERFLOW);	
	}
	
	//将新元素e写入结点的数据域中，指针域置空 
	p->data = *e;
	p->next = NULL;
	
	//将结点插入到队尾
	Q->rear->next =  p; 
	
	Q->rear = p; 
	return OK;	 
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

（5）出队

  1. 判断队列是否空，若空则返回ERROR
  2. 若不为空，记录下一个元素的地址
  3. 判断删除的是否为最后一个元素，若是则需要修改尾指针
  4. 释放首元结点
  5. 修改头结点的指针域为p
Status DeQueue(LinkQueue *Q,QElemType *e)
{
	//如果队是否为空
	if(Q->front == Q->rear)
	{
		return ERROR; 
	} 
	//记录下一个元素的地址
	QNode *p = Q->front->next->next;
	
	//判断删除的是否为最后一个元素 
	if(p == NULL)
	{
		//尾指针指向头结点 
		Q->rear = Q->front; 
	}
	//释放首元结点 
	free(Q->front->next);
	 
	//修改头结点的指针域为p
	Q->front->next = p;
	
	return OK;	 
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

（6）取队头元素

  1. 判断队列是否空
  2. 若不为空，将队头元素返回
QElemType GetHead(LinkQueue *Q)
{
	//如果队不为空
	if(Q->front == Q->rear)
	{
		return Q->front->next->data; 
	} 
	return ERROR; 
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

四、串、数组、广义表

4.1 串的定义

  • 串是一种内容受限的线性表，数据元素只能是字符
  • 串（string）（或字符串）是由零个或多个字符组成的有限序列，一般记为
    s = “a1a2…an” (n≥0)

其中，s 是串的名，用双引号括起来的字符序列是串的值；ai( 1 ≤ i ≤ n ) 可以是字母、数字或其他字符；
串的长度：串中字符的数目n称为串的长度。零个字符的串称为空串（null string）。
子串：串中任意个连续的字符组成的子序列称为该串的子串，包含空串和本身。但真子串不包含本身。
主串：包含子串的串相应的称为主串。
字符位置：通常称字符在序列中的序号为该字符在串中的位置。子串的位置是子串的第一个字符在主串中的位置。
空格串：由一个或多个空格组成的串，与空串不同
串相等：当且仅当两个串的长度相等，并且各个对应位置上的字符都相同，才认为两串相等

4.2 串的存储结构

  • 作为一种内容受限的线性表，其存储结构也有两种：顺序存储和链式存储

串的顺序存储结构

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 注：为方便算法的描述，字符串从下标为1的位置开始存储，下标为0的位置闲置

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

在这里插入图片描述

#define MAXSIZE 5

typedef struct Chunk
{
	char ch[MAXSIZE];
	struct Chunk *next;
}Chunk;

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

4.3 串的模式匹配算法

在这里插入图片描述

4.3.1 BF算法

  • BF算法（Brute-Force），也称简单匹配算法。采用穷举法的思路
  • 算法思路：从主串（正文串）的每一个字符开始依次与子串（模式）的字符进行匹配

算法步骤：

  1. 分别利用计数指针i和j指向主串和模式中当前正在比较的字符，i的初值为pos，j的初值为1
  2. 如果两串均未比较到串尾，则循环以下操作：
  • 若当前位置的字符相等，则i和j分别指向串中下一个位置，比较后续字符
  • 若不相等，指针进行回溯，主串指向下一字符（i = i - j + 2），再重新和模式的第一个字符（j = 1）比较
  1. 如果j > L.length，说明匹配成功，返回模式在主串出现的位置（i - L.length），否则匹配不成功，返回0

i = i - j + 2：由于字符串是在下标为1处开始存储，i - j + 1表示回到初始位置，i - j + 1 + 表示回到初始位置的下一字符

  • 注：算法是基于字符串从下标为1的位置开始存储，下标为0的位置闲置
    在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

  • （1）下面以顺序存储结构来实现该算法（从下标1开始存储）
int Index_BF(SString *S,SString *T)
{
	int i = 1,j = 1;
	while((i <= S->length) && (j <= T->length))
	{
		if(S->ch[i] == T->ch[j])
		{
			i++;
			j++;	
		}
		else
		{
			i = i - j + 2;
			j = 1;	
		}	
	}
	if(j > T->length)
	{
		return (i - T->length);	
	}
	else
	{
		return -1;
	}	
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

完整代码：

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

# define MAXSIZE 10         //串的最大长度

typedef struct
{
	char ch[MAXSIZE];  //存储串的一维数组
	int length;            //串的当前长度
}SString;


int Index_BF(SString *S,SString *T)
{
	int i = 1,j = 1;
	while((i <= S->length) && (j <= T->length))
	{
		if(S->ch[i] == T->ch[j])
		{
			i++;
			j++;	
		}
		else
		{
			i = i - j + 2;
			j = 1;	
		}	
	}
	if(j > T->length)
	{
		return (i - T->length);	
	}
	else
	{
		return -1;
	}	
}

//串的赋值
int StrAssign(SString *S,char *str)
{

	if((strlen(str) + 1) > MAXSIZE - 1)
	{
		return 0;		
	}
	int i = 0;
	for(i = 1;str[i-1] != '\0';i++)
	{
		S->ch[i] = str[i-1];
	}
	S->ch[i + 1] = '\0';
	S->length = strlen(str);
	return S->length; 
}

int main()
{
	SString S,T;
	StrAssign(&S,"Hello");
	StrAssign(&T,"ell");
	int i;
	i = Index_BF(&S,&T);
	printf("%d\n",i);
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • （2）BF算法（从下标为0开始存储）
//模式匹配 ——BF 
int Index_BF(SString *S,SString *T)
{
	int i = 0,j = 0;
	while((i < S->length) && (j < T->length))
	{
		if(S->ch[i] == T->ch[j])
		{
			i++;
			j++;	
		}
		else
		{
			i = i - j + 1;
			j = 0;	
		}	
	}
	if(j > T->length - 1)
	{
		return (i - T->length + 1);	
	}
	else
	{
		return -1;
	}	
} 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

完整代码：

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

# define MAXSIZE 10         //串的最大长度

typedef struct
{
	char ch[MAXSIZE];  //存储串的一维数组
	int length;            //串的当前长度
}SString;

int Index_BF(SString *S,SString *T)
{
	int i = 0,j = 0;
	while((i < S->length) && (j < T->length))
	{
		if(S->ch[i] == T->ch[j])
		{
			i++;
			j++;	
		}
		else
		{
			i = i - j + 1;
			j = 0;	
		}	
	}
	if(j > T->length - 1)
	{
		return (i - T->length + 1);	
	}
	else
	{
		return -1;
	}	
} 

//串的赋值
int StrAssign(SString *S,char *str)
{

	if((strlen(str) + 1) > MAXSIZE)
	{
		return 0;		
	}
	int i = 0;
	for(i = 0;str[i] != '\0';i++)
	{
		S->ch[i] = str[i];
	}
	S->ch[i] = '\0';
	S->length = i;
	return i; 
} 

int main()
{
	SString S,T;
	StrAssign(&S,"Hello");
	StrAssign(&T,"ell");
	int i;
	i = Index_BF(&S,&T);
	printf("%d\n",i);
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
4.3.1.1 BF算法的平均时间复杂度

最坏的情况：
在这里插入图片描述
最好的情况是第一次匹配就成功，设子串的长度为m，主串的长度为n，那么最优的时间复杂度为O ( m )；

4.4 数组

  • 数组是由类型相同的数据元素构成的有序集合，每个元素受n（n ≥ 1）各线性关系约束
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

五、树和二叉树

5.1 树的定义

  • 树（Tree）是n个（n≥0）个节点的有限集，结点数为0的树称为空树。结点不为0的树称为非空树。

  • 非空树的特性：
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

  • 树是一种递归定义的数据结构

  • 树中各元素的关系是1对多的关系，则除根节点外，每个结点有且仅有一个直接前驱

基本术语：

  1. 结点：树中的一个独立单元。
  2. 结点的度：结点拥有的子树个数。例如：A的度为3，B的度为2
  3. 树的度：树的度是树内各结点度的最大值。例如，上边的树的度为3
  4. 叶子结点（终端结点）：度为0的结点。例如：结点K、L
  5. 非终端结点（分支结点）：度不为0的结点。除根结点之外，非终端结点也称为内部结点
  6. 孩子结点：结点的子树的根。同时，该结点称为孩子的双亲（父结点）。例如，结点B的双亲为A，孩子有E、F
  7. 兄弟节点：同一个双亲的孩子之间互称兄弟。例如，结点K、L
  8. 祖先结点：从根到该结点所经分支上的所有结点。例如：G的祖先结点为：A、C
  9. 子孙结点：以某结点为根的子树中的任一结点都称为该结点的子孙结点。例如，结点B的子孙结点有：E、K、L、F
  10. 堂兄弟结点：在同一层次中，除兄弟结点外，其余结点都是堂兄弟结点。例如，结点E的堂兄弟结点有：G、H、I、J
  11. 层次：结点的层次从根开始定义，根为第一层，根的孩子为第二层，以此类推
  12. 树的深度（高度）：树中的最大层次数。例如，上边的树的深度为4
  13. 有序树和无序树：树中结点的各子树看成从左至右有次序的（不能互换），称为有序树，否则称为无序树。在有序树中，最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子
  14. 森林：m（m≥0）棵互不相交的树的集合。对于树而言，子树的集合就是森林
    森林与树之间的相互转化：在这里插入图片描述

注：

  • 两个结点的路径：只能从上往下，即为单向
  • 路径的长度：经过几条边
  • 结点的层次（深度）：从上往下数
  • 结点的高度：从下往上数

树的部分应用场景：

5.2 二叉树的定义

为什么要学习二叉树？

  1. 二叉树结构最简单，规律性最强
  2. 多叉树运算较难实现，而多叉树可以与二叉树相互转换
  • 二叉树（Binary Tree），是n ( n ≥ 0 ) 个结点的有限集，或者它是空树( n = 0 ) ，除根节点外的其余结点可分为两个互不相交的子集T1、T2，分别称左子树和右子树。且T1、T2本身又是二叉树
  • 二叉树的特点：
  1. 每个结点最多有两棵子树（结点的度不大于2）
  2. 子树有左右之分，其次序不能颠倒
  3. 二叉树也是一种递归定义的数据结构，二叉树可以是空集合，根可以有空的左子树或空的右子树。
  • ​ 二叉树和树的区别：二叉树不是树的特殊情况，是两个不同的概念
    二叉树的结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分；树只有一个结点时，就无需区分它是左还是右的次序，因此二者是不同的。这就是二叉树和树的主要区别。

二叉树的物五种基本形态：

在这里插入图片描述

5.3 二叉树的性质和存储结构

5.3.1 二叉树的性质

  1. 在二叉树的第 i 层上至多有2i-1（i≥1）个节点
    在这里插入图片描述
    第 i 层上至少有1个结点
  2. ==深度为 k ==的二叉树至多有2k-1个结点（k≥1）
    在这里插入图片描述
    深度为 k 的二叉树至少有k个结点（k≥1）
  3. 对于任何一棵二叉树T，其叶子（终端）结点数为n0，度为2的结点数为n2，则n0 = n2 + 1
    在这里插入图片描述
    其中，n：总结点数，n0：度为0，即叶子结点数，n1：度为1的结点数，n2：度为2的结点数

  • 本性质的分析过程尤为重要，首先从下往上分析二叉树的边数；之后，又从上往下分析二叉树的边数

  • 满二叉树：

满二叉树：深度为k且含有2k-1个结点的二叉树（达到最大值）
在这里插入图片描述
在这里插入图片描述

对满二叉树进行编号，从跟根节点开始，自上而下，自左至右，如下图所示
在这里插入图片描述

  • 完全二叉树：

完全二叉树：深度为k的、有n个结点的二叉树，当且仅当其每个结点都与深度为k的满二叉树中的编号从1至n的结点一一对应
在这里插入图片描述
在这里插入图片描述

  • 完全二叉树就是满二叉树编号后，从后向前有顺序的删除元素或不删除元素
    在这里插入图片描述
    满二叉树与完全二叉树的联系：
    在这里插入图片描述
    完全二叉树的性质：
  1. 具有n个结点的完全二叉树的深度为==⌊log2n⌋ + 1(⌊log2n⌋ 要向下取整)==
    该性质表明了完全二叉树结点数n与深度k之间的关系
  2. 具有n个结点的完全二叉树的深度为⌊log2n⌋ + 1 的结点按层序编号（从上到下，从左往右），则对任一结点i ( 1 ≤ i ≤ n )有：
    （1）如果i = 1，则结点i是二叉树的根，无双亲；如果i >1 ，则其双亲结点⌊ i / 2 ⌋
    （2）如果2 i > n ，则结点i为叶子结点，无左孩子；否则，其左孩子结点是2 i
    （3）如果2 i + 1 > n，则结点i无右孩子；否则，其右孩子是结点2 i + 1
    该性质表明了完全二叉树双亲结点编号与孩子结点编号之间的关系
    在这里插入图片描述

5.3.2 二叉树的存储结构

二叉树的存储结构可采用顺序存储和链式存储
在这里插入图片描述

顺序存储结构

用一组地址连续的存储单元来存储数据元素

  • 对于完全二叉树，依次自上而下、自左到右存储节点元素，即将完全二叉树上编号为i的结点元素存储在一维数组中下标为i-1的分量中
    在这里插入图片描述
    二叉树的顺序存储表示：
#define MAXSIZE 10
typedef TElemType SqBiTree[MAXSIZE];
SqBiTree bt;

  • 1
  • 2
  • 3

将SqBiTree[MAXSIZE]定义成了一种类型，类型的名字就是数组的名字
之后，用重定义类型SqBiTree bt，定义了一个数组bt，可存放MAXSIZE个元素

  • 对于一般二叉树，每个结点的编号与完全二叉树相对照，不存在的用0表示，或不存储
    在这里插入图片描述
    在这里插入图片描述
链式存储结构
  1. 二叉链表
    在这里插入图片描述

二叉链表的存储表示

typedef struct BiTNode
{
	TElemType data;
	struct BiTNode *lchild,*rchild;  // 左右孩子指针
}BiTNode,*BiTree;

  • 1
  • 2
  • 3
  • 4
  • 5

在这里插入图片描述

  • 在n个结点的二叉链表中，有n + 1个空指针域在这里插入图片描述
  1. 三叉链表
    在这里插入图片描述

三叉链表的存储表示

typedef struct TriTNode
{
	TElemType data;
	struct TriTNode *lchild,*parent,*rchild;  // 左右孩子指针,双亲指针
}TriTNode,*TriTree;

  • 1
  • 2
  • 3
  • 4
  • 5

5.4 遍历二叉树和线索二叉树

5.4.1遍历二叉树

  • 遍历二叉树：按照某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次
    在这里插入图片描述
    在这里插入图片描述
    二叉树是递归定义的数据结构，因此只需要遍历根结点、左子树和右子树这三部分即可
    遍历二叉树的方案：DLR、LDR、LRD、DRL、RDL、RLD
    在这里插入图片描述
DLR——先序遍历

如果二叉树为空则空操作，否则
在这里插入图片描述

由二叉链表实现先序遍历：

Status PreOrderTraverse(BiTree T)
{
	if(T == NULL)
	{
		return OK;
	}
	else
	{
		printf("%d\n",T->data);    //访问根节点
		PreOrderTraverse(T->lchild);   //先序遍历左子树
		PreOrderTraverse(T->rchild);   //先序遍历右子树
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

在这里插入图片描述

  • 先序遍历的执行过程：

在这里插入图片描述

LDR——中序遍历

如果二叉树为空则空操作，否则
在这里插入图片描述
在这里插入图片描述
由二叉链表实现中序遍历：

Status InOrderTraverse(BiTree T)
{
	if(T == NULL)
	{
		return OK;
	}
	else
	{
		InOrderTraverse(T->lchild);   //中序遍历左子树
		printf("%d\n",T->data);    //访问根节点
		InOrderTraverse(T->rchild);   //中序遍历右子树
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
LRD——后序遍历

如果二叉树为空则空操作，否则
在这里插入图片描述
由二叉链表实现后序遍历：

Status PostOrderTraverse(BiTree T)
{
	if(T == NULL)
	{
		return OK;
	}
	else
	{
		PostOrderTraverse(T->lchild);   //后序遍历左子树
		PostOrderTraverse(T->rchild);   //后序遍历右子树
		printf("%d\n",T->data);    //访问根节点
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

二叉树遍历的应用：
在这里插入图片描述

  • 根据二叉树的先序序列和中序序列或中序序列和后序序列可以确定唯一的二叉树

三种遍历算法的相同点：

在这里插入图片描述
算法的时间复杂度为：O(n)，空间复杂度：O(n)
在这里插入图片描述

利用栈将递归算法转化为非递归算法：

  1. 初始化一个空栈，指针p指向根节点
  2. 申请一个结点空间q，用来存放栈顶弹出的元素
  3. 当p非空或者栈非空，则循环以下操作：
    （1）如果p非空，使p进栈，p指向该结点的左孩子
    （2）如果p为空，使p出栈并访问根结点，p指向该结点的右孩子
Status InOrderTraversr(BiTree *T)
{
	//初始化栈
	InitStack(&S);
	
	//指针p指向根节点，指针q存出栈顶弹出的元素 
	BiTree p = *T;
	BiTree q;
	
	while(p || StackElmpty(S))
	{
		//根节点的地址不为空 
		if(p)
		{
			//将根节点的地址入栈 
			Push(*S,&p);
			//p指向根节点的左孩子 
			p = p->lchild; 
		}
		else
		{
			//出栈，用q保存栈顶信息 
			Pop(*S,&q);
			//访问根节点 
			printf("%d \n",q->data);
			//指向根节点的右孩子 
			p = q->rchild; 
		}
	}
	 return OK;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
层次遍历

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

  • 二叉树遍历的应用：

二叉树的“遍历”是各种操作的基础，访问，不仅仅局限于输出结点的数据，而是延伸到对结点的判别、计数等其他操作

  1. 创建二叉树的存储结构——二叉链表
    为简化问题，以二叉树中每个结点的数据元素为单个字符为例：
    算法步骤：
    ①输入字符序列ch
    ②如果ch是一个’#'，则表明该二叉树为空树；否则进行循环：
    (1)申请一个结点空间
    (2)将ch赋值给T->data
    (3)递归创建左子树
    (4)递归创建右子树
void CreatBiTree(BiTree *T)
{
    ch = getchar();               //按照先序序列输入二叉树的值
	if(ch == '#')
	{
		*T = NULL;
	}
	else
	{
		*T = (BiTree)malloc(sizeof(BiTNode));    //生成根节点
		if(!(*T))
		{
			perror("error");
			exit(OVERFLOW);
		}
		(*T)->data = ch;
		CreatBiTree(T->lchild);   //递归创建左子树
		CreatBiTree(T->rchild);   //递归创建右子树
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

在这里插入图片描述

  1. 复制二叉树
    算法步骤：
    ①如果是空树，递归结束，否则进行循环：
    (1)申请一个结点空间
    (2)复制根节点
    (3)递归复制左子树
    (4)递归复制右子树
void Copy(BiTree *T,BiTree *NewT)
{
	if(*T == NULL)
	{
		(*NewT) = NULL;
	}
	else
	{
		(*NewT) = (BiTree)malloc(sizeof(BiTNode));    //生成根节点
		if(!(*NewT))
		{
			perror("error");
			exit(OVERFLOW);
		}
		(*NewT)->data = (*T)->data;     //复制根结点
		Copy(T->lchild,NewT->lchild);   //递归复制左子树
		Copy(T->rchild,NewT->rchild);   //递归复制建右子树
	}
	return T;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  1. 计算二叉树的深度
    算法步骤：
    ①如果是空树，递归结束，深度为0，否则进行循环：
    (1)递归计算左子树的深度为m
    (2)递归计算右子树的深度为m
    (3)如果m>n，二叉树的深度为m+1，否则为n+1
int Depth(BiTree *T)
{
	if(*T == NULL)
	{
		return 0;;
	}
	else
	{
		m = Depth(T->lchild);   //递归计算左子树的深度
		n = Depth(T->rchild);   //递归计算右子树的深度
		if(m>n)
		{
			return (m+1);
		}
		else
		{
			return (n+1);
		}
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  1. 计算二叉树的结点总数
    算法步骤：
    ①如果是空树，递归结束，结点个数为0，否则进行：
    (1)递归计算左子树的结点个数
    (2)递归计算右子树的结点个数
    (3)返回，左子树的结点个数+右子树的结点个数+1
int NodeCount(BiTree *T)
{
	if(*T == NULL)
	{
		return 0;;
	}
	else
	{
		return NodeCount((*T)->lchild)+NodeCount((*T)->rchild)+1;
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  1. 计算二叉树的叶子结点总数
    算法步骤：
    ①如果是空树，递归结束，叶子结点个数为0，否则进行：
    (1)递归计算左子树的叶子结点个数
    (2)递归计算右子树的叶子结点个数
    (3)如果根节点的左孩子和右孩子都为空，则返回1
    (3)返回，左子树的结点个数+右子树的结点个数
int LeafCount(BiTree *T)
{
	if(*T == NULL)
	{
		return 0;;
	}
	if((*T)->lchild == NULL && (*T)->rchild == NULL)  //叶子结点
	{
		return 1;
	}
	else
	{
		return LeafCount((*T)->lchild)+LeafCount((*T)->rchild);
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

5.4.2 线索二叉树

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
为了区分lchild和rchild两指针指向的是孩子的指针，还是前驱和后继的指针。对二叉链表设立两个标志位ltag和rtag：

  1. ltag = 0，lchild指向左孩子
  2. ltag = 1，lchild指向前驱
  3. rtag = 0，rchild指向右孩子
  4. rtag = 1，rchild指向后继

线索二叉树的存储类型定义：

typedef struct BiThrNode
{
	int data;
	int ltag,rtag;
	BiThrNode *lchild,*rchild;
}BiThrNode,*BiThrTree;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

在这里插入图片描述
在这里插入图片描述

5.5 树和森林

5.5.1 树的存储结构

  1. 双亲表示法
    在这里插入图片描述
    在这里插入图片描述
  2. 孩子链表法
    在这里插入图片描述

在这里插入图片描述
对方法1与方法2结合可得：
在这里插入图片描述

  1. 孩子兄弟表示法
    在这里插入图片描述
    在这里插入图片描述

5.5.2 树和二叉树的转化

由孩子兄弟表示法可知，任何一个树都可以用二叉链表表示，都有唯一对应的二叉树

在这里插入图片描述

  • 树转化为二叉树
    在这里插入图片描述
    在这里插入图片描述

  • 二叉树转化为树
    在这里插入图片描述
    在这里插入图片描述

5.5.3 森林和二叉树的转化

  • 森林转化为二叉树：
    在这里插入图片描述
    在这里插入图片描述
  • 二叉树转化为森林：
    在这里插入图片描述
    在这里插入图片描述

5.5.4 树和森林的遍历

  1. 树的遍历
    在这里插入图片描述
  2. 森林的遍历
    在这里插入图片描述
    （1）先序遍历
    在这里插入图片描述
  • 依次左右对森林里的每一棵树进行先根遍历

（2）中序遍历在这里插入图片描述

  • 依次左右对森林里的每一棵树进行后根遍历

六、图

6.1 图的定义和基本术语

图G（Graph）由两个集合V和E组成，G=（V,E）
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
注：
（vi,vj）表示两者直间有关系，但不分先后顺序
<vi,vj>表示两者直间有关系，分先后顺序，vi在前vj在后
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
权与网：
在这里插入图片描述

子图：
在这里插入图片描述
连通分量（强连通分量）：
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

6.2 图的存储结构

图没有顺序存储结构，但可以借助二维数组来表示元素之间的关系，即采用邻接矩阵表示法；此外，也可以用链式存储表示图

6.2.1 邻接矩阵

在这里插入图片描述

  • 对于无向图而言，其邻接矩阵表示法：
    在这里插入图片描述
  • 对于有向图而言，其邻接矩阵表示法：
    在这里插入图片描述
    在这里插入图片描述

注：完全图的邻接矩阵，对角元素为0，其余元素都为1

  • 对于网（有权图）而言，其邻接矩阵表示法：
    在这里插入图片描述

邻接矩阵的存储表示：

#define MaxInt 32767      //表示极大值
#define MVNum 10          //最大顶点数
typedef char VerTexType;  //假设顶点的数据类型为字符型
typedef int ArcType;      //假设边的权值类型为字符型

typedef struct
{
	VerTexType vexs[MVNum]; //顶点表
	ArcType arcs[MVNum][MVNum];  //邻接矩阵
	int vexnum,arcnum;      //记录当前顶点数和边数
}AMGraph;    //Adjacency Matrix Graph

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在图中查找顶点的算法：
在这里插入图片描述

  • 算法的时间复杂度为O(n2)

无向网转化为其他形式的方法：
在这里插入图片描述

  • 邻接矩阵的优点：
    在这里插入图片描述
  • 邻接矩阵的缺点：

在这里插入图片描述

6.2.2 邻接表

在这里插入图片描述

  • 无向图的邻接表：

在这里插入图片描述

邻接表不唯一是表结点位置可以互换

对于网而言，表结点海选哟增加一项用来存储权值

  • 有向图的邻接表：（左：邻接表，右：逆邻接表）

在这里插入图片描述

邻接表的存储表示：

表头结点：

#define MVNum 10

typedef struct VNode
{
	VerTexType data;     //顶点信息
	AecNode *firstarc;   //指向第一条依附该顶点的边的指针
}VNode，AdjList[MVNum];   //定义了一个结构体数组，可以存放MVNum个元素，类型名字为AdjList

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • AdjList v等价于VNode v[MVNum]

边结点：

typedef struct ArcNode
{
	int adjvex;    //该边所指向的顶点位置
	struct ArcNode *nextarc;   //指向下一条边的指针
	OtherInfo info;   //和边相关的信息
}ArcNode;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

图的结构定义：

typedef struct
{
	AdjList vertices;   //顶点结构体数组
	int vexnum,arcnum;  //当前顶点数和边数
}ALGraph;

  • 1
  • 2
  • 3
  • 4
  • 5

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

  • 邻接矩阵和邻接表的区别和联系：

在这里插入图片描述
在这里插入图片描述

6.2.3 十字链表

十字链表：为解决用邻接表存储有向图求顶点的度困难，而设计的方法
在这里插入图片描述

6.2.4 邻接多重表

邻接多重表：为解决用邻接表存储无向图每条边要存储两次，而设计的方法
在这里插入图片描述

6.3 图的遍历

在这里插入图片描述
遍历的实质：找到每个顶点的邻接点的过程
在这里插入图片描述

6.3.1 深度优先遍历（Depth_First Search——DFS）

在这里插入图片描述
连通图的深度优先遍历类似于树的先根遍历
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

6.3.1 广度优先遍历（Breadth_First Search——DFS）

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
DFS和BFS算法效率的比较：
在这里插入图片描述
在这里插入图片描述

七、查找

7.1 线性表的查找

7.1.1 顺序查找

  • 顺序查找：从表的一端开始，依次将关键字与给定值进行比较，如果相等，则查找成功；反之，查找整个表后没有找到，则查找失败
  • 适用于：顺序表、链表

数据元素定义：

typedef struct
{
	KeyType key;         //关键字域
	InfoType otherinfo;  //其他域
}ElemType;

  • 1
  • 2
  • 3
  • 4
  • 5

顺序表的定义：

typedef struct
{
	ElemType *R;         //存储空间基地址
	int length;          //当前长度
}SSTable;                //查找表                  

  • 1
  • 2
  • 3
  • 4
  • 5

假设，下标为0的位置不存储数据元素，从下标为1的位置存储数据元素
在这里插入图片描述

顺序查找的算法实现：

int Search_Seq(SSTable *T,KeyType *key)
{
    //从表的一端开始，逐个查找。如果找到，返回其下标；否则，返回0
    int i = 0;
    for(i = T->length;i >= 1;i--)
    {
        if((T->R + i)->key == *key)
        {
            return i;
        }

    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

算法分析：每次循环都要进行两次比较，一次判断整个表是否查找完成，一次判断关键字与给定值是否相等，下面对该算法稍作改进

改进方法：设置检查哨，把待查找的关键字存入表头，从后向前查找，可以免去每次判断整个表是否查找完成的步骤
在这里插入图片描述

int Search_Seq(SSTable *T,KeyType *key)
{
    //将带查找关键字放入表头，作为哨兵
    (T->R->key) = *key;
    //从表尾开始，逐个查找。如果找到，返回其下标；否则，返回0
    int i = 0;
    for(i = T->length;(T->R + i)->key != key;i--);

    return i;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

在这里插入图片描述
算法分析：时间复杂度：O(n)，空间复杂度：O(1)

  • 顺序查找的优缺点：

在这里插入图片描述

7.1.2 折半查找（二分查找）

  • 折半查找：分别用两变量表示当前查找区间的上下界，从区间的中间位置开始与关键字进行比较，如果相等，则比较成功；如果关键字大于中间位置的关键字，则在表中大于中间位置的区间进行查找；如果关键字小于中间位置的关键字，则在表中小于中间位置的区间进行查找。重复以上操作，直到查找成功或者查找区间为空，代表查找失败。
  • 要求线性表必须采用顺序存储结构，而且表中元素关键字有序排列

在这里插入图片描述
算法过程：
在这里插入图片描述
非递归解法：

int Search_Bin(SSTable *T,KeyType *key)
{
    //初始化，low、high分别指向查找区间的上下界
    int low = 1,high = T->length;


    while (low <= high)
    {
        //int mid = (low + high) / 2;    容易发生溢出
        int mid = low + (high - low) / 2;

        if((T->R + mid)->key == *key)
        {
            return mid;
        }
        else if((T->R + mid)->key > *key)  //在后半区查找
        {
            low = mid + 1;

        }
        else                                //在前半区查找                     
        {
            high = mid - 1;
        }
    }
    return 0;  //不存在该关键字
    
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

递归解法：

int Search_Bin(SSTable *T,KeyType *key,int low,int high)
{
    //递归结束条件
    if(high < low)
    {
        return 0;
    }

    //int mid = (low + high) / 2;    容易发生溢出
    int mid = low + (high - low) / 2;

    if((T->R + mid)->key == *key)
    {
        return mid;
    }
    else if((T->R + mid)->key > *key)
    {
        Search_Bin(&T,&key,mid + 1,high);
    }
    else
    {
        Search_Bin(&T,&key,low,mid - 1);
    }
    
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

算法分析：时间复杂度：O(log2n)，空间复杂度：O(1)

  • 顺序查找的优缺点：
    优点：比较次数少，查找效率高
    缺点：只适用于有序表，且限于顺序存储结构

7.1.3 分块查找

  • 条件：
  1. 将表分成几块，且表或者有序，或者分块有序
    分块有序：i<j，则第j块中所有记录的关键字均大于第i块中所记录的最大关键字
  2. 建立“索引表”：每个结点含有最大关键字域和指向本块第一个结点的指针，且最大关键字有序
  • 分块查找：先确定待查关键字所在块（顺序和折半查找），再在块内查找（顺序查找）
    在这里插入图片描述
  • 算法效率分析：
    在这里插入图片描述
  • 分块查找的优缺点：
    优点：由于块内无序，插入和删除比较容易，无需进行大量移动
    缺点：需要增加一个索引表的存储空间并对初始索引表进行排序运算
  • 分块查找的适用情况：线性表既要经常动态变化，又需对其进行快速查找

在这里插入图片描述
线性表的查找更适用于静态查找表

7.2 树表的查找

7.2.1 二叉排序树

  • 二叉排序树的定义：
    在这里插入图片描述
    由此可见。二叉排序树是递归定义的，由此得出一个重要性质：中序遍历一棵二叉排序树可以得到一个结点递增的有序序列

数据元素定义：

typedef struct
{
	KeyType key;         //关键字域
	InfoType otherinfo;  //其他域
}ElemType;

  • 1
  • 2
  • 3
  • 4
  • 5

二叉排序数的结构定义：

typedef struct BSTNode                   //二叉排序树
{
	ElemType data;                       //数据域
	struct BSTNode *lchild,*rchild;      //左右孩子结点
}SBSTNode,*BSTree;                    

  • 1
  • 2
  • 3
  • 4
  • 5

在这里插入图片描述

BSTree SearchBST(BSTree T,KeyType *key)
{
    if((!T) || T->data.key == *key)
    {
        return T;
    }
    else if (T->data.key > *key)     //根结点的关键字大于给定值，则取左子树查找
    {
        return SearchBST(T->lchild,*key);
    }
    else                             //根结点的关键字小于给定值，则取右子树查找
    {
        return SearchBST(T->rchild,*key);
    }
    
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/391759
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号