$ 1基本概念
1.1基础
1.1.1空间的使用
对于以下两个代码同时实现了打印小于等于N的所有数,但是当N在不同的值的时候结果会不同
/*循环调用*/
void printN(int N)
{
for(int i=0;i<N+1;i++)
cout<<i<<endl;
return
}
/*递归调用*/
void printN(int N)
{
if(N)
{
printN(N-1);
cout<<N;
}
return ;
}
在如上的两个代码中,在数字较小的时候结果相同,但是当数字较大的时候,递归调用就会占用很大的空间,从而无法打印出正确的结果
1.1.2.时间复杂度
/*判断时间的方法*/
#include <ctime>
#include <iostream>
using namespace std;
int main()
{
clock_t start,stop; //clock()返回的类型
start=clock();
myfunction(); //待测的函数
stop=clock();
double duration=((double)(stop-start))/CLK_TCK; //CLK_TCK为每个电脑的运行速度
return 0;
}
1.1.3.抽象数据类型
数据结构包含逻辑结构和储存结构
抽象数据类型:
数据类型:数据对象集,数据集相关的操作集(C++中的封装)
抽象:和机器,物理结构,编程语言无关
1.2算法(Algorithm)
- 有限的指令集
- 接收一些输入
- 产生输出
- 有限步骤后终止
1.2.1算法的优劣
- 空间复杂度S(N)
- 时间复杂度t(N)
1.2.2复杂度的渐进表示法
$$ T(n)=O(f(n)) ,表示存在C>0,n_0>0使得当n\geq n_0时有T(n) \leq C*f(n),上界 $$
$$ T_1(n)+T_2(n)=max(O(f_1(n)),O(f_2(n))) $$
$$ T_1(n)*T_2(n)=max(f_1(n)*f_2(n)) $$
$ 2、表
2.1引入:多项式的表述
$$ f(x)=a_0+a_1x+a_2x^2+...+a_nx^n $$
方法一:顺序存储结构直接表示(数组)
a[i]的值表示次数为i的项对应的系数
两个多项式相加就对应数组的相加
缺点:对于次数大的多项式,在储存和运算过程中的复杂度较大
方法二:顺序储存非零项(结构数组)
struct P{
int ai;
int i;
}
按照指数大小顺序存储运算符方便
(ai,i)
P1:(9,12),(15,8),(3,2)
P2:(26,19),(-4,8),(5,7)
P1+P2:顺序比较大小,如果相同则相加系数
方法三:链表
2.2线性表(List)
定义:由同类元素构成的有序线性结构
2.2.1抽象集表示
数据对象集:(a1,a2,a3,...,an)
操作集主要有:
List MakeEmpty(); //初始化一个空list ElementType FindKth(int k,List L); //返回L的第k个元素 int Find(ElementType x, List L); //返回元素x的位序 void insert(ElementType x ,List); //插入一个新的元素 void delete(int i,List L); //删除 int Length(List L); //返回长度
2.2.2顺序储存的实现
typedef struct LNode * List;
struct LNode{
ElementType Data[MaxSize];
int last; //用于存储最后的元素的下标
};
struct LNode L;
List Lptr;
/*返回对应的元素*/
L.Data[i];
Lptr->Data[i];
/*返回长度*/
length=L.last+1;
length=Lptr->last+1;
1.初始化 (MakeEmpty)
List MakeEmpty()
{
List PtrL;
PtrL = new LNode;
PtrL->last=-1;
return PtrL;
}
2.查找(find)
int Find(ElementType x,List PtrL)
{
int i=0;
while(i<=PtrL->last)
{
if(PtrL->Data[i]==x)
return i;
i++;
}
return -1;
}
3.插入(insert)
void insert(ElementType x,int i,List LPtr) //向第i位置中插入元素x
{
if(LPtr->last==Maxsize-1)
{
cout<<"表满无法插入"<<endl;
return;
}
if(i<1||i>LPtr->Last+2)
{
cout<<"非法位置"<<endl;
return;
}
for(int j=LPtr->last;j>=i-1;j--)
{
LPtr->Data[j+1]=LPtr->Data[j];
}
LPtr->Data[i-1]=x;
LPtr->last++;
return;
}
4.删除(delete)
void delete(int i,List Lptr)
{
if(i<1||i>Lptr->last+1)
{
cout<<"非法输入"<<endl;
return;
}
for(int j=i;j<Lptr->last+1;j++)
{
LPtr->Data[j-1]=Lptr->Data[j];
}
LPtr->Last--;
return;
}
2.2.3顺序储存的C++实现
#define Maxsize 100
#define LISTINCREMENT 10 //定义每次增加的长度,用于动态增加(类似vector)
typedef int Elemtype;
class Sqlist {
Elemtype *data;
int MaxSize;
int length;
public:
Sqlist(int size);
~Sqlist();
//void Sqlist_insert_head(int x); // 头插法
//void Sqlist_insert_rear(int x); //尾插法
void Sqlist_insert(int i, int x);
Elemtype Sqlist_delete(int i); //删除i处的元素并返回该值
int Locatex(int x); //定位x的下标
int Length();
};
#include "Sqlist.h"
/*构造函数*/
Sqlist::Sqlist(int size)
{
if (size < Maxsize)
{
data = new Elemtype[Maxsize];
MaxSize = Maxsize;
length = 0;
}
else
{
data = new Elemtype[size];
MaxSize = size;
length = 0;
}
}
/*析构函数*/
Sqlist::~Sqlist()
{
delete[]data;
MaxSize = length = 0;
}
/*第i个位置插入元素*/
void Sqlist::Sqlist_insert(int i, int x)
{
/*判断位置是否异常*/
if (i > length + 1 || i < 1)
return;
/*判断是否已满*/
if (length >= MaxSize)
{
/*重新定义空间*/
Elemtype *data_new = new Elemtype[MaxSize + LISTINCREMENT];
/*数据转移*/
for (int j = 0; j < length; j++)
data_new[j] = data[j];
delete[]data;
data = data_new;
MaxSize += LISTINCREMENT;
}
/*依次位移*/
for (int j = length-1; j > i-1; j--)
{
data[j + 1] = data[j];
}
data[i - 1] = x;
length++;
}
/*删除*/
Elemtype Sqlist::Sqlist_delete(int i)
{
/*判断位置是否异常*/
if (i < 1 || i >= length)
return -1; //注意这里需要设定一个不存在的值,或者使用引用的形式带出结果
/*判断是否为空*/
if (length == 0)
{
return -1;
}
int x = data[i - 1];
for (int j = i - 1; j < length - 1; j++)
data[j] = data[j + 1];
length--;
return x;
}
/*定位*/
int Sqlist::Locatex(int x)
{
for (int j = 0; j < length; j++)
{
if (data[j] == x)
return j + 1;
}
return -1;
}
/*返回长度*/
int Sqlist::Length()
{
return length;
}
2.2.4线性表的链表实现
a.存储
typedef struct LNode * List;
struct LNode{
ElementType Data;
List Next;
};
LNode L;
List PtrL;
b.主要操作
1.求表长
int Length(List PtrL)
{
List p = PtrL;
int i=0;
while(p)
{
p=p->Next;
i++;
}
return i;
}
2.查找
List FindKth(int K,List PtrL)
{
List p = PtrL;
int i=1;
while(p&&i<K)
{
p=p->Next;
i++;
}
if(i==K)
return p;
else
return NULL; //没有找到
}
List Find(ElementType X,List PtrL)
{
List p=PtrL;
while(p&&p->Data!=X)
{
p=p->Next;
}
return p;
}
3.插入
List insert(ElementType X,int i,List PtrL) //在第i的位置插入一个节点,返回表头指针
{
List p,s;
if(i==1) //插入位置在表头
{
s= new LNode;
s->Data=X;
s->Next = PtrL;
return s;
}
p=FindKth(i-1,PtrL);
if(p==NULL)
{
cout<<"非法位置"<<endl;
return PtrL;
}
else
{
s = new LNode;
s->Data=X;
s->Next=p->Next;
p->Next=s;
}
return PtrL;
}
4.删除
List Delete(int i, List PtrL) //删除第i个节点,并返回头结点
{
List p,s; //s指向要删除结点,p指向删除结点的前一个结点
/*删除位置在头结点*/
if(i==1)
{
s=PtrL;
/*判断表是否为空*/
if(PtrL!=NULL)
{
PtrL=PtrL->Next;
delete s;
}
else
return NULL;
return PtrL;
}
/*位置不在头结点*/
p=FindKth(i-1,PtrL);
if(p==NULL||p->Next==NULL)
{
cout<<"不存在该节点"<<endl;
return PtrL;
}
else
{
s=p->next;
p->next = s->next;
delete s;
return PtrL;
}
}
2.2.5链表的C++实现
1.单链表
typedef int ElemType;
struct Node
{
ElemType data;
Node *next;
};
class LinkList
{
Node *Head;
public:
LinkList();
~LinkList();
void List_insert_head(int x);
void List_insert_rear(int x);
void ListInsert(int i, int x);
ElemType ListDelete(int i);
ElemType GetElem(int i);
Node *LocateElem(ElemType e);
int Length();
};
Sqlist::Sqlist(int size)
{
if (size < Maxsize)
{
data = new Elemtype[Maxsize];
MaxSize = Maxsize;
length = 0;
}
else
{
data = new Elemtype[size];
MaxSize = size;
length = 0;
}
}
/*析构函数*/
Sqlist::~Sqlist()
{
delete[]data;
MaxSize = length = 0;
}
/*第i个位置插入元素*/
void Sqlist::Sqlist_insert(int i, int x)
{
/*判断位置是否异常*/
if (i > length + 1 || i < 1)
return;
/*判断是否已满*/
if (length >= MaxSize)
{
/*重新定义空间*/
Elemtype *data_new = new Elemtype[MaxSize + LISTINCREMENT];
/*数据转移*/
for (int j = 0; j < length; j++)
data_new[j] = data[j];
delete[]data;
data = data_new;
MaxSize += LISTINCREMENT;
}
/*依次位移*/
for (int j = length-1; j > i-1; j--)
{
data[j + 1] = data[j];
}
data[i - 1] = x;
length++;
}
/*删除*/
Elemtype Sqlist::Sqlist_delete(int i)
{
/*判断位置是否异常*/
if (i < 1 || i >= length)
return -1; //注意这里需要设定一个不存在的值,或者使用引用的形式带出结果
/*判断是否为空*/
if (length == 0)
{
return -1;
}
int x = data[i - 1];
for (int j = i - 1; j < length - 1; j++)
data[j] = data[j + 1];
length--;
return x;
}
/*定位*/
int Sqlist::Locatex(int x)
{
for (int j = 0; j < length; j++)
{
if (data[j] == x)
return j + 1;
}
return -1;
}
/*返回长度*/
int Sqlist::Length()
{
return length;
}
2.静态链表
采用数组的方式保存链表,以空的位置代表链表的链,有利于没有指针的语言使用链表,缺点在于空间的浪费非常大
#pragma once
#define MaxSize 1000
typedef int ElemType;
struct Node {
ElemType data;
int next; //用于保存下一个元素在数组中的位置
};
class StaticList
{
private:
Node StList[MaxSize];
int length;
public:
//相关操作函数
};
2.2.6链表的应用——一元多项式
在该问题里面,我们通常可以使用数组来保存每一个次数的系数,但是问题在于对于一个次数相当大的多项式中我们需要的空间变得非常大,所以我们希望利用链表来保存以此节约空间。
#pragma once
#define MaxSize 20
typedef struct polyArray {
float coef;
int exp;
}PolyArray[MaxSize];
struct PolyNode {
float coef; //保存系数
int exp; //保存次数
PolyNode *next;
};
class Poly
{
public:
PolyNode *Head;
Poly();
~Poly();
void CreatePoly(PolyArray a,int n); //创建多项式链表
void PolyDisplay();
void PolySort();
void insertPoly(PolyNode &a);
void PolyAdd(Poly &Lb);
void Polymultiple(Poly &Lb);
};
a.构造函数与析构函数
/*头结点不存放东西,否则无法判断是否为空*/
Poly::Poly()
{
Head = new PolyNode;
Head->next = nullptr; //如果Head->next为空,则链表为空
}
/*需要遍历每一个结点然后delete*/
Poly::~Poly()
{
while (Head->next!=nullptr)
{
PolyNode *p = Head;
Head = Head->next;
delete p;
}
delete Head;
}
b.建立多项式
void Poly::CreatePoly(PolyArray a, int n)
{
PolyNode *r = Head;
for (int i = 0; i < n; i++)
{
PolyNode *s = new PolyNode;
s->exp = a[i].exp;
s->coef = a[i].coef;
r->next = s;
r = r->next;
r->next = nullptr; //注意必须要置空,否则会导致最后一个节点的下一位不是空
}
}
c.打印多项式
void Poly::PolyDisplay()
{
PolyNode *cur = Head->next;
cout << "coef" << "\t" << "exp" << endl;
while (cur!=nullptr)
{
cout << cur->coef << "\t" << cur->exp<<endl;
cur = cur->next;
}
}
d.排序
/*
注意对于排序链表的时候,要么进行值交换,要么进行结点交换
若进行结点交换,那么需要考虑交换结点的前一个节点,以及交换结点之间的指针指向顺序
*/
/*该算法考虑使用值交换,不改变结点的顺序*/
void Poly::PolySort() //降序排序
{
for (PolyNode *p = Head->next; p != NULL; p = p->next)
{
for (PolyNode *q = p->next; q != nullptr; q=q->next)
{
if (p->exp < q->exp)
{
float temp1 = q->coef;
q->coef = p->coef;
p->coef = temp1;
int temp2 = p->exp;
p->exp = q->exp;
q->exp = temp2;
}
}
}
}
e.一元多项式的加法
/*插入算法,如果以包含相同的指数,那么系数相加,否则插入结点*/
void Poly::insertPoly(PolyNode &a)
{
PolyNode *s = new PolyNode;
PolyNode *p = Head;
s->exp = a.exp;
s->coef = a.coef;
s->next = nullptr;
while (p->next != NULL)
{
if (p->exp == s->exp)
{
p->coef += s->coef;
return;
}
p = p->next;
}
p->next = s;
}
/*对于b中的每一个结点进行处理,如果该节点的系数在*this中存在,那么系数相加,否则插入结点(即进行上述的insert处理)*/
void Poly::PolyAdd(Poly & Lb)
{
/*从Lb的第一个开始依次遍历,如果没有就插入,有就加入*/
for (PolyNode *p = Lb.Head; p->next != nullptr; p = p->next)
{
int flag = 0; //是否找到
for (PolyNode *q = Head; q->next != nullptr; q = q->next) //当前多项式
{
PolyNode *Np = p->next;
PolyNode *Nq = q->next;
if (Np->exp == Nq->exp)
{
//cout << Nq->coef<<"\t"<<Np->exp << endl;
flag = 1;
Nq->coef += Np->coef;
break;
}
}
if (flag == 0)
{
this->insertPoly(*(p->next));
}
}
this->PolySort();
}
f.一元多项式的乘法
/*新建一个一元多项式,对于每一个处理后的结点插入到*this中*/
void Poly::Polymultiple(Poly & Lb)
{
PolyNode *p = Head->next;
Head = new PolyNode;
Head->next = nullptr;
while (p)
{
PolyNode *q = Lb.Head->next;
while (q)
{
PolyNode *s = new PolyNode;
s->exp = p->exp+q->exp;
s->coef = p->coef*q->coef;
this->insertPoly(*s);
q = q->next;
}
p = p->next;
}
this->PolySort();
}
2.3 栈
2.3.1后缀表达式
对于一个表达式有优先级的问题,我们常使用的中缀表达式不利于计算机计算
例如:a+b*c-d/e这个中缀表达式,计算机无法判断优先级
所以我们使用后缀表达式:a b c * + d e / - (运算是最后两个的运算)
所需要的数据结构:能够顺序记录存储运算数,并且倒叙输出
2.3.2栈的顺序实现
只能在一段插入和删除
插入数据:入栈
删除数据:出栈
先入后出
1.抽象数据表述
Stack CreateStack(int MaxSize); //生成空的堆栈
int IsFull(Stack S,int MaxSize); //判断是否满
void Push(Stack S,ElementType item); //将元素压栈
int IsEmpty(Stack S); //判断是否为空
ElementType Pop(Stack S) //删除并弹出顶栈元素
2.基本操作
a.存储实现
typedef SNode * Stack;
struct SNode{
ElementType Data[MaxSize]; //用于保存内容
int Top; //栈顶位置的下标,Top=-1表示堆栈空
};
b.入栈
void push(ElementType X,Stack PtrS)
{
/*判断是否满*/
if(PtrS->top==MaxSize-1)
{
cout<<"堆栈已满"<<endl;
return;
}
else
{
PtrS->Data[++PtrS->top]=X;
return;
}
}
c.出栈
ElementType Pop(Stack PtrS)
{
/*判断是否为空*/
if(PtrS->top==-1)
{
cout<<"堆栈为空"<<endl;
return ERROR;
}
else
return (PtrS->Data[(PtrS->Top)--]);
}
3. C++实现
a.栈的实现
#pragma once
typedef int ElemType;
class SqStack
{
ElemType *base; //栈底指针
ElemType top; //栈顶下标
int stackSize;
public:
SqStack(int m); //创建m大小的栈
~SqStack();
void Push(int e); //入栈
ElemType Pop(); //弹栈
int GetTop(); //返回栈顶元素
void StackTranverse(); //显示所有元素
int StackEmpty(); //返回是否为空
};
#include "SqStack.h"
#include <iostream>
using namespace std;
SqStack::SqStack(int m)
{
base = new ElemType[m];
top = -1;
stackSize = m;
}
SqStack::~SqStack()
{
top = stackSize = 0;
delete[] base;
}
void SqStack::Push(int e)
{
/*判断是否为满*/
if (top == stackSize-1)
{
cout << "栈已满" << endl;
return;
}
base[++top] = e;
}
ElemType SqStack::Pop()
{
//判断是否为空
if (top == -1)
{
cout << "栈空,不可出栈" << endl;
return -1; //需要没有-1 的值
}
ElemType e = base[top];
top--;
return e;
}
int SqStack::GetTop()
{
/*判断是否为空*/
if (top == -1)
{
cout << "栈为空" << endl;
return -1;
}
return base[top];
}
void SqStack::StackTranverse()
{
/*判断是否为空*/
if (top == -1)
{
cout << "栈为空" << endl;
return;
}
for (int i = 0; i < top + 1; i++)
{
cout << base[i] << endl;
}
return;
}
int SqStack::StackEmpty()
{
if(top==-1)
return 1;
return 0;
}
b.数制转化
#include <iostream>
#include "LinkStack.h"
using namespace std;
int main()
{
LinkStack s;
int num, system;
cin >> num >> system;
while (num)
{
s.Push(num%system);
num /= system;
}
s.StackTranverse();
return 0;
}
c.括号匹配
#include <iostream>
#include "LinkStack.h"
using namespace std;
int main()
{
LinkStack s;
char a[100];
cin >> a;
for(int i=0;i<strlen(a);i++)
{
switch (a[i])
{
case '(':
{
s.Push(a[i]);
i++;
break;
}
case ')':
{
if (s.Empty())
{
cout << "不匹配!" << endl;
return 0;
}
else
{
s.Pop();
}
}
}
}
if (s.Empty())
{
cout << "匹配!" << endl;
}
else
{
cout << "不匹配" << endl;
}
return 0;
}
d.行编辑问题
#include <iostream>
#include "LinkStack.h"
using namespace std;
int main()
{
LinkStack s;
char a[100];
cin >> a;
for(int i=0;i<strlen(a);i++)
{
switch (a[i])
{
case '#':
{
s.Pop();
break;
}
case '@':
{
while (!s.Empty())
{
s.Pop();
}
break;
}
default:
s.Push(a[i]);
}
}
s.StackTranverse();
return 0;
}
e.迷宫寻路(回溯)
2.3.3栈的链式存储
1.存储实现
typedef struct SNode * Stack;
struct SNode {
ElementType Data;
SNode *Next;
};
2.建立空栈
//头结点没有任意一个元素
Stack CreateStack()
{
Stack S;
S=new SNode;
S->Next=NULL;
return S;
}
int IsEmpty(Stack S)
{
return (S->Next==NULL);
}
3.入栈
void Push(ElementType X,Stack S)
{
Stack temp=new SNode;
temp->Data=X;
temp->Next=S->Next;
S->Next=temp;
}
4.出栈
ElementType Pop(Stack S)
{
/*判断是否为空*/
if(IsEmpty(S))
{
cout<<"堆栈为空"<<endl;
return NULL;
}
else
{
Stack TopNode = S->Next;
ElementType Top=TopNode->Data;
S->Next=TopNode->Next;
delete TopNode;
return Top;
}
}
5. C++实现
#pragma once
typedef int ElemType;
struct Node {
ElemType Data;
Node *Next;
};
class LinkStack
{
Node *top;
public:
LinkStack() { top = nullptr; }
~LinkStack();
void Push(ElemType e);
ElemType Pop();
ElemType GetTop();
int Empty();
void StackTranverse();
};
#include "LinkStack.h"
#include <iostream>
using namespace std;
LinkStack::~LinkStack()
{
while (top)
{
Node *p = top->Next;
delete top;
top = p;
}
}
int LinkStack::Empty()
{
if(top==nullptr)
return 1;
return 0;
}
void LinkStack::Push(ElemType e)
{
Node *s = new Node;
s->Data = e;
s->Next = top;
top = s;
}
ElemType LinkStack::Pop()
{
//判断是否为空
if (top == nullptr)
{
cout << "栈为空" << endl;
return -1;
}
//注意这里有删除弹出结点的操作,顺序栈没有因为空间已经分配
Node *p = top->Next;
ElemType e = top->Data;
delete top;
top = p;
return e;
}
ElemType LinkStack::GetTop()
{
//判断为空
if (Empty())
{
cout << "栈为空";
return -1;
}
return top->Data;
}
void LinkStack::StackTranverse()
{
//判断为空
if (Empty())
{
cout << "栈为空" << endl;
return;
}
Node *p = top;
while (p)
{
cout << p->Data<<endl;
p = p->Next;
}
}
2.4 队列
数据插入:入队列
数据删除:出队列
先进先出,一段插入一段删除
2.4.1抽象数据类型
Queue CreateQueue(int MaxSize);
int IsFullQ(Queue Q,int MaxSize);
void AddQ(ElementType item,Queue Q);
int IsEmpty(Queue Q);
ElementType DeleteQ(Queue Q);
2.4.2 队列的顺序存储实现
a.定义实现
typedef QNode * Queue;
struct QNode{
ElementType Data[MaxSize];
int rear; // 队尾下标
int front; // 队头前一个元素下标
};
b.循环队列的插入
/*此处采用大小为n的循环队列只保存n-1个元素的方式*/
void AddQ(ElementType item,Queue PtrQ)
{
/*判断是否为满*/
if((PtrQ->rear+1)%MaxSize==PtrQ->top)
{
cout<<"队列已满"<<endl;
return;
}
else
{
PtrQ->rear=(Ptr->rear+1)%MaxSize;
PtrQ->Data[PtrQ->rear]=item;
}
}
c.循环队列的出队
ElementType DeleteQ(Queue PtrQ)
{
/*判断是否为空*/
if(PtrQ->front == PtrQ->rear)
{
cout<<"队列为空"<<endl;
return NULL;
}
else
{
PtrQ->front=(PtrQ->front+1)%MaxSize;
return PtrQ->Data[PtrQ->front];
}
}
d.C++实现
#pragma once
typedef int ElemType;
class CQueue
{
int *base;
int front; //头指针
int rear; //尾指针
int queuesize;
public:
CQueue(int m);
~CQueue();
void EnQueue(ElemType e); //入队
ElemType DeQueue();
void QueueDisplay();
int isEmpty();
int isFull();
};
#include "CQueue.h"
#include <iostream>
using namespace std;
CQueue::CQueue(int m)
{
base = new ElemType[m];
front = rear = 0;
queuesize = m;
}
int CQueue::isEmpty()
{
if (front == rear)
{
cout << "队列为空" << endl;
return 1;
}
return 0;
}
CQueue::~CQueue()
{
delete[] base;
}
int CQueue::isFull()
{
if ((rear + 1) % queuesize == front)
{
cout << "队列已满" << endl;
return 1;
}
return 0;
}
void CQueue::EnQueue(ElemType e)
{
/*判断是否为满*/
if (isFull())
{
return;
}
base[rear] = e;
rear = (rear + 1) % queuesize;
}
ElemType CQueue::DeQueue()
{
//判断是否为空
if (isEmpty())
{
return -1;
}
ElemType e = base[front];
front = (front + 1) % queuesize;
return e;
}
void CQueue::QueueDisplay()
{
//判断为空
if (isEmpty())
return;
int p = front;
while (p != rear)
{
cout << base[p] << endl;
p = (p + 1) % queuesize;
}
}
2.4.3队列的链式存储
a.定义实现
struct Node{
ElementType Data;
Node * Next;
};
struct QNode{
Node * rear;
Node * front;
};
typedef QNode * Queue;
Queue PtrQ;
b.队列初始化
Queue CreateQueue()
{
Queue PtrQ=new QNode;
PtrQ->rear=NULL;
PtrQ->front=Null;
}
b.入队操作
void Push(ElementType X,Queue PtrQ)
{
Node *temp=new Node;
temp->Data=x;
temp->Next=PtrQ->rear;
PtrQ->rear=temp;
}
c.出队操作
ElementType Pop(Queue PtrQ)
{
/*判断是否为空*/
if(PtrQ->front==Null)
{
cout<<"队列为空"<<endl;
return NULL;
}
else
{
Node *FrontNode = PtrQ->front;
/*若只有一个元素*/
if(PtrQ->front==PtrQ->rear)
{
PtrQ->rear=PtrQ->front=NULL; //删除后置空
}
else
{
PtrQ->front=FrontNode->Next;
}
ElementType FrontItem= FrontNode->Data;
delete FrontNode;
return FrontItem;
}
}
e.C++实现
#pragma once
typedef int ElemType;
struct Node {
ElemType data;
Node *next;
};
class LinkQueue
{
Node *front;
Node *rear;
public:
LinkQueue();
~LinkQueue();
void EnQueue(ElemType e);
ElemType DeQueue();
void QueueDisplay();
};
#include "LinkQueue.h"
#include <iostream>
using namespace std;
LinkQueue::LinkQueue()
{
front = new Node;
front->next = nullptr;
rear = front;
}
LinkQueue::~LinkQueue()
{
Node *p = front;
while (p)
{
p = p->next;
delete front;
front = p;
}
}
void LinkQueue::EnQueue(ElemType e)
{
Node *r = new Node;
r->data = e;
r->next = nullptr;
rear->next = r;
rear = r;
}
ElemType LinkQueue::DeQueue()
{
/*判断为空*/
if (rear == front)
{
cout << "队列为空!" << endl;
return -1;
}
Node *p = front->next;
ElemType e = p->data;
front->next = p->next;
/*注意,当到了最后即使是rear=null,front=null依然不等*/
if (p->next == nullptr)
rear=front;
delete p;
return e;
}
void LinkQueue::QueueDisplay()
{
/*判断队列是否为空*/
if (rear == front)
{
cout << "队列为空!" << endl;
return;
}
while (front->next != nullptr)
{
Node *p = front->next;
cout << p->data << endl;
front->next = p->next;
delete p;
}
}
f.链队列应用——事件驱动模拟(待完成)
2.5 串
2.5.1基本概念
空串:长度为0的串
空格串:只含有空格的串
子串:包含于主串中的字符串
抽象数据类型:
ADT String{
$$ 数据对象:D=\lbrace a_i|a_i\in 字符集合\rbrace $$
$$ 数据关系:R=\lbrace (a_i,a_{i+1})|a_i,a_{i+1}\in D\rbrace $$
基本操作:
Strassign(&s,st); //字符串分配 strempty(s); strcopy(&t,s); strncpy(&sub,p,pos,len); strcmp(s,t); strlength(s); strconcat(&t,s1,s2); //连接新串 substring(&sub,s,pos,len); //求子串 strindex(s,t,pos); //求位置
}
2.5.2 定长顺序存储
采用静态存储分配
#define MaxStrlen 256
typedef char sstring[MaxStrlen+1];
sstring s;
缺点:存储为定长
2.5.3 堆分配存储
typedef struct
{
char *ch;
int length;
}Hstring;
动态存储字符串,在每一初始化的时候在堆区开辟一个空间用于保存(注意在删除或者更改数据的时候需要重新分配空间)
2.5.4 链式存储
该方法利于插入和删除运算,但是空间利用率较小
2.5.5 模式匹配
a. BF 模式匹配
int index(string s,string t,int pos)//返回在s中t在pos之后的位置
{
int i=pos,j=1;
while(i<strlen(s)&&j<strlen(j))
{
if(s[i]==j[i])
{
i++;
j++;
}
else
{
i=i-j+1;
j=0;
}
}
if(j>=strlen(j))
return i-strlen(j);
else
return -1;
}
b. KMP 模式匹配(待完成)
2.6 数组与广义表(待完成)
2.6.1 矩阵的压缩
对于三角矩阵和对称矩阵,分别采用数组的方式保存有用的位置,同时利用公式求取其在矩阵中的坐标.
稀疏矩阵:若矩阵有s个非0元素,那么当s<<mn (t=s/(mn),t<<0.05时),称其为稀疏矩阵
对于稀疏矩阵的储存,首先要明确矩阵的行列数,然后要明确非0元素的个数和每个非0元素的数值。对于非0元素,我们需要明确其行列以及数值
2.6.2 广义表
$3、树与二叉树
3.1 树的基本概念
定义:树是n个结点的有限集T,T为空时为空数,否则满足下面两个条件
- 有且仅有一个根结点
- 其余的结点可以分为m个互不相交的子集T1,T2...(即可以划分为若干子集),且每个子集又为一棵树
树中的基本术语:
- 兄弟结点:拥有同一个父结点的若干结点互为兄弟结点
- 堂兄弟结点:结点在树中的层次相同但是双亲不同的结点
- 祖先结点:从根结点到X所有的结点都为X的祖先结点(注意要在同主路上)
- 子孙结点:结点X的孩子以及其孩子的子孙结点
- 树的深度:树中距离根最远的结点的层次数,只有根的树其深度为1
- 树的高度:与深度相反,叶子结点的高度为1,反向定义深度
- 有序树:指需要考虑到兄弟结点从左到右顺序的树
- 无序树:子树可以相互交换的树
- 森林:m个互不相交的树的集合
3.2 二叉树
3.2.1 定义
由n个结点组成的有限集合,满足如下条件中的任意一条:
- 该集合为空,为空树
- 该集合非空,由一个根结点及两棵互不相交的左右子树组成,且左右子树都是二叉树
注意:二叉树左子树和右子树不同,需要区分
3.2.2 性质
$$ 在二叉树的第i(i\geq1)层上最多有2^{i-1}个结点
$$ 2. $$ 深度为k(k\geq1)的二叉树最多有2^k-1个结点 $$
两种特殊的二叉树
- 满二叉树:满足性质二的最多情况的二叉树
- 完全二叉树:对于一个树其内部的排列皆为先左数,再右树的二叉树(即满足有n个结点,每个结点的序号和满二叉树相互对应)
$$ 具有n(n\geq1)个结点的完全二叉树的深度为[\log_2n]+1
$$ 5. 如果对一棵有n个结点的完全二叉树的结点按层序编号,则对任意结点i(1<=i<=n)有: 1. 如果i=1,则i为根结点;若i>1,则其双亲的编号为[i/2] 2. 如果2i>n,则无左孩子,否则其左孩子是结点2i 3. 若2i+1>n,则结点无右孩子,否则右孩子是结点2i+1 ### 3.2.3 存储结构 #### a.顺序存储 采用表形式,按照完全二叉树的编号方式对于二叉树进行储存,通过下标可以推断出二叉树的层以及每个位置的元素 #### b.链式存储
#pragma once
typedef int ElemType;
typedef struct BitNode {
ElemType data; //数据域
BitNode* lchild; //左子树的指针
BitNode* rchild; //右子树的指针
};
class BinaryTree {
BitNode *bt;
int RCreate(BitNode *p, int k, int end);
public:
BinaryTree() { bt = nullptr; }
void CreateBiTree(int *data); //end为输入结束的标志
/*递归算法*/
void PreTraverse(void(*p)(ElemType m),BitNode *q);
void InTraverse(void(*p)(ElemType m), BitNode *q);
void PostTraverse(void(*p)(ElemType m), BitNode *q);
/*非递归算法*/
void PreOrderTraverse(void (*p)(ElemType m));
void InOrderTraverse(void(*p)(ElemType m));
void PostOrderTraverse(void(*p)(ElemType m));
BitNode *GetRoot(); //返回根结点的指针
void BitTreeDisplay(BitNode *bt, int level = 1);//展示树形
};
3.3 遍历二叉树与线索二叉树
3.3.1 遍历二叉树
a. 先序遍历
也称前序遍历(根——左子树——右子树)
步骤(当二叉树为空):
- 访问根结点(D);
- 访问左子树(L);
- 访问右子树(R)。
递归算法
void BinaryTree::PreTraverse(void(p)(ElemType m),BitNode q)
{if (q != nullptr) { p(q->data); //调用特定的函数 PreTraverse(p, q->lchild); PreTraverse(p, q->rchild); }
}
非递归算法
- 从根结点开始,依次根——左——右遍历
- 对于已经遍历的根结点,保存到栈中
- 如果没有遍历到的结点为空,退回到栈所保存的结点,遍历其右结点
/* 相比于非递归,递归的方式不够高效,为了记录每一个已经遍历的结点的上一个结点我们采用栈来保存上一个结点的值 步骤:
void BinaryTree::PreOrderTraverse(void(*fun)(ElemType m))
{
BitNode *p = bt;
stack<BitNode*> s;
while (p || !s.empty()) //如果p不是空或者S不为空
{
if (p)
{
fun(p->data);
s.push(p);
p = p->lchild;
}
else
{
/*注意在STL中由于安全以及效率原因,pop的返回类型为void,需要使用top来返回*/
p = s.top();
s.pop();
p = p->rchild;
}
}
}
#### b. 中序遍历
步骤(当二叉树不为空):
1. 中序遍历左子树(L)
2. 访问根结点(D)
3. 访问右子树(R)
- 递归算法
- ```c++
void BinaryTree::InTraverse(void(*p)(ElemType m), BitNode * q)
{
if (p != NULL)
{
InTraverse(p,q->lchild);
p(q->data);
InTraverse(p, q->rchild);
}
}
非递归算法
{
stack<BitNode*> S; //用于保存根 BitNode *q = bt; while (q || !S.empty()) { if (q != NULL) { S.push(q); q = q->lchild; } else { q = S.top(); S.pop(); p(q->data); q = q->rchild; } }
}
#### c. 后序遍历 步骤(二叉树不为空):
- 后续遍历左子树(L)
- 后续遍历右子树(R)
- 访问根结点(D)
递归算法
{
if (p != NULL) { PostTraverse(p,q->lchild); PostTraverse(p, q->rchild); p(q->data); }
}
非递归算法
struct BitNode1 { BitNode* bt; int tag;
void BinaryTree::PostOrderTraverse(void(*p)(ElemType m))
{stack<BitNode1*> S; BitNode *q = bt; BitNode1 *temp; while (q || !S.empty()) { if (q != NULL) //第一次遍历左子树并且第一次压栈 { BitNode1 *t = new BitNode1; t->bt = q; t->tag = 1; S.push(t); q = q->lchild; } else //左子树遍历完成 { temp = S.top(); S.pop(); if (temp->tag == 1) //第一次出现在栈顶(不对其处理,相当于历遍过程) { temp->tag = 2; S.push(temp); q = temp->bt->rchild; } else //第二次出现在栈顶 { p(temp->bt->data); q = NULL; } } }
}
#### d. 层次遍历 原理:按照层次对于每一层依次左右遍历
- BinaryTree::LevelOrderTraverse(void(*p)(ElemType m))
{
queue<BitNode*> q;
BitNode* t;
if (bt) //确保该树不是空树
{
q.push(bt);
while (!q.empty()) //当q不为空的时候
{
t = q.front();
q.pop();
p(t->data);
if (t->lchild)
{
q.push(t->lchild);
}
if (t->rchild)
{
q.push(t->rchild);
}
}
}
}
### 3.3.2 线索二叉树
遍历二叉树的问题
- 遍历算法复杂,费时多
- 寻找某个结点的后继,必须从根开始找
为了解决上面的问题,可以将二叉树线索化,进而便于遍历。
线索化:将一个结点在某种遍历的前继结点和后继结点保存为一个整体
结构定义如下
typedef struct BithrNode{
ElemType data;
BithrNode *lchild,*rchild;
int LTag,RTag;
};
其中的LTag与RTag用于区分在lchild以及rchild中保存的是否左右子树,规定
$$
LTag/RTag=\begin{cases}0,&\text{指示结点的左/右孩子}\\
1,&\text{指示结点的前驱/后继}\end{cases}
$$
## 3.4树与森林
### 3.4.1 树与二叉数转化
对于一个无序树,其排序方式并不重要,而普通树不便于遍历,所以需要将其转化为二叉数的形式
步骤:
1. 加线:将树中相邻兄弟结点连接起来
2. 去线:对于每一个结点,只保留一条与孩子相连接的先
3. 旋转:将上述图像旋转得到二叉数
![](https://img2020.cnblogs.com/blog/1673558/202004/1673558-20200419195017427-9139829.png)
### 3.4.2 二叉数与森林转化
- 森林转化二叉树
1. 将森林中每棵树转化为二叉树
2. 第一个二叉树不动,从第二个二叉树开始,一次把二叉树的根结点作为前一个二叉树的右孩子
- 二叉树转化为森林
1. 若某结点是双亲的左孩子,则把该节点的右孩子,右孩子的右孩子....与双亲相连接。
2. 删去员二叉树中所有的双亲与右孩子的连线
3. 整理图形
## 3.5 赫夫曼树及其应用
### 3.5.1 哈夫曼树的概念
- 哈夫曼树:又称最优二叉树,只带权路径最小的二叉树
- 结点的权:对结点赋予的数值
- 结点的带权路径长度:从根开始到该结点之间的路径长度与该节点的权值乘积
- 叶子结点:树中度为0的结点(即没有子结点)
-
- 树的带权路径长度:树中所有叶子结点的带权路径长度之和
- $$
WPL=\sum_{k=1}^nW_kL_k
$$
### 3.5.2 哈夫曼树的构造
根据哈夫曼树的定义,要是上述的WPL最小,则需要让权值最大的结点靠近根,所以采用如下步骤进行够着哈夫曼树:
1. 根据所给的权值创建集合{w1,w2,...,wn},构造二叉树F={T1,T2,...,Tn},其中每棵二叉树只含有根结点
2. 在F中选取权值最小的树分别作为左右子树构造一棵新的二叉树,且将新的二叉树的根结点设定为其左右子树上根结点的权值和
3. 在F中删除作为左右子树的两棵二叉树,同时将新树加入F中
4. 重复2,3直到只有一棵树为止,该树为哈夫曼树
/头文件/
pragma once
struct HTNODE
{
int weight;
int parent;
int lchild;
int rchild;// 通过链的形式存储,分别指向其下标
};
class huffman_BT
{
int nn; //叶子结点个数
HTNODE *bt; //顺序存储首地址
char **hc;//动态分配数组存储哈夫曼编码表
public:
huffman_BT() { bt = nullptr; }
void creat_huffman_BT();
void select(HTNODE *p, int k, int *i, int *j);//在前k位搜索最小的两个节点,分别返回给i与j
void Huffman_display();
int HuffmanCoding();
};
include "huffman_BT.h"
include <iostream>
include <queue>
include <iomanip>
using namespace std;
void huffman_BT::select(HTNODE p, int k, int i, int * j)
{
int m; //表示最小的下标
/*寻找第一个根结点*/
for (m = 0; m < k; m++)
{
if ((p + m)->parent == -1)
break;
}
int min = (p+m)->weight; //表示最小的值
*i = m;
/*寻找最小*/
for (; m < k; m++)
{
HTNODE *w = p + m;
if (((p + m)->weight < min) && (p + m)->parent == -1) //要求为根结点,其父节点为空
{
*i = m;
min = (p + m)->weight;
}
}
/*寻找第二小*/
//首先进行初始化
/*寻找根结点*/
for (m = 0; m < k; m++)
{
if ((p + m)->parent == -1&&m!=*i) //除去i的根结点
break;
}
*j = m;
min = (p + m)->weight;
for (; m < k; m++)
{
if (((p + m)->weight) < min&&(m != (*i)) && (p + m)->parent == -1)
{
*j = m;
min = (p + m)->weight;
}
}
/*保证i<j,减少遍历次数*/
if (*i > *j)
{
m = *i;
*i = *j;
*j = m;
}
}
void huffman_BT::creat_huffman_BT()
{
HTNODE *p;
int i,j,m; //保存长度,临时变量i,j最小下标,总共的结点数
cout << "请输入结点的个数:";
cin >> nn;
m = nn * 2 - 1; //总共的结点数目
bt = new HTNODE[m]; //建立长度m的树结构
p = bt;
/*对该树进行初始化*/
for (int k = 0; k < m; k++)
{
p[k].weight = 0;
p[k].parent = p[k].rchild = p[k].lchild = -1; //初始化都为-1
}
/*对权值列表进行初始化*/
for (int k = 0; k < nn; k++)
{
cout << "请输入第" << k + 1 << "个权值:";
cin >> p[k].weight;
}
/*对树进行构造*/
HTNODE *w1, *w2;
for (int k = nn; k < m; k++)
{
select(p, k, &i, &j); //找寻最小的两个下标
w1 = p + i, w2 = p + j;
(p + i)->parent = k;
(p + j)->parent = k;
(p + k)->lchild = i;
(p + k)->rchild = j;
(p + k)->weight = (p + j)->weight + (p + i)->weight;
// cout << (p + k)->weight << endl;
}
}
/层次遍历输出结果/
void huffman_BT::Huffman_display()
{
queue<HTNODE*> q;
HTNODE* t;
t = bt;
/*寻找根结点*/
int i;
for (i = 0; i < 2 * nn - 1; i++)
{
if ((bt + i)->parent == -1)
break;
}
t = bt + i;
q.push(t);
while (!q.empty()) //当q不为空的时候
{
t = q.front();
q.pop();
cout << t->weight << "\t";
if (t->lchild!=-1)
{
q.push(bt+t->lchild);
}
if (t->rchild!=-1)
{
q.push(bt+t->rchild);
}
}
}
### 3.5.3 应用
- 最优判定
- | 等级 | E | D | C | B | A |
| ------------ | ---- | ----- | ----- | ----- | ------ |
| 分数段 | 0-59 | 60-70 | 70-80 | 80-90 | 90-100 |
| 比例(权值) | 0.05 | 0.15 | 0.40 | 0.30 | 0.10 |
对于上述的问题,在使用if-else语句时,如果需要判定的时间最短,那么我们希望把权值最大的分数段放在第一个进行判断,然后依次减小权值,其构成为一个哈夫曼树,权值大的分数段接近根
- 哈夫曼编码
- 在文本传输中,为了使传输的串尽可能的短,可以采用二叉树设计不定长的编码串
- 例如:
| A | B | C | D |
| ---- | ---- | ---- | ---- |
| 000 | 001 | 100 | 111 |
此时采用等长的编码形式,所以在传输长度为n的一个字符串时,需要传输3n的二进制串,为了在效率上面优化采用不定长的字符串
如:某通信系统中只存在a,b,c,d,e,f,g,h的字符,其频率*100分别为5,29,7,8,14,23,3,11.为了构造一个通信方式,使传输的二进制字符尽可能的少,那么我们采用哈夫曼树的形式构造结点。
![image-20220328100540048](C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20220328100540048.png)
所以对于输入的一个二进制串例如:0110101110,对应的在树中查找0110为a,10为b,1110为c所以为abc
# $ 4 图
## 4.1 基本概念
### 4.1.1 基本概念
- 顶点
- 无向图:顶点间没有方向
- 有向图:顶点间存在方向(<v,w>其中v称为弧头或者初始点,w称为弧尾或者终端点)
### 4.1.2 基本术语
这里不考虑自环和多重图
- 完全图:每个不同的顶点都有着相互的连接,无向图边数为n(n-1)/2,有向图为n(n-1)
- 权:边或者与弧上具有它相关的数据信息
- 邻接顶点:相邻的顶点,对于无向图两个顶点之间如果存在边,那么他们为邻接顶点,有向图中,例如<u,v>则称u邻接到v,v邻接自u
- 子图:一个图的部分图
- 度:一个顶点与其相互关联的边数,对于一个有向图,指出的边数成为出度,指入的边数称为入度
- 路径:从顶点u到达v所经历的顶点
- 路径长度:从顶点u到达v所经历的边数目
- 简单路径与回路:若路径上各个点相互间不重复,则称该路径为简单路径,若第一个顶点和最后一个顶点相互重合,则为一条回路
- 连通图与连通分量:当一个图中任意两个顶点是连通的,那么这个图为连通图,对于一个非连通图,其最大连通子图数为该图的连通分量。
- 强连通图和强连通分量:在有向图中,任意两个顶点v,u间都存在v到u的路径,则称该图为一个强连通图,对于非强连通图,其最大连通子图数为该图的连通分量
- 生成树:G的生成树为包含G中全部顶点的一个极小连通子图,
- 生成森林:非连通图的每一个连通分量都可以得到一个生成树,这些生成树组成生成森林
## 4.2 储存结构
### 4.2.1 图的顺序储存
#### a.矩阵存储方式
- 邻接矩阵(无权图):利用矩阵的形式来保存顶点间的关系(边),一个数组来表示图中顶点的信息
对于该矩阵而言,有如下定义:
$$
G.Edge[i][j]=\begin{cases} 1, & {(v_i,v_j)\in E或者<v_i,v_j>\in E} \\ 0, & {(v_i,v_j)\notin E或者<v_i,v_j>\notin E} \end{cases}
$$
对于上述的矩阵,如果需要求无向图的第i个顶点度,则仅需要求第i行或第i列的和
如果需要求有向图第i个顶点的出度,则只需要第i行的和,入度,第i列的和
- 加权临接矩阵:对于加权图,需要记录某一边的权值,我们采用如下方式对上面的邻接矩阵进行改写
$$
G.Edge[i][j]=\begin{cases} w_{i,j}, & {(v_i,v_j)\in E或者<v_i,v_j>\in E} \\ \infty, & {(v_i,v_j)\notin E或者<v_i,v_j>\notin E} \end{cases}
$$
对于上面的方法存在一个缺陷,在未加权的情况下时对称矩阵,这样有大部分的空间是浪费的,所以需要其他的方式对矩阵进行存储以实现空间的节约。可以利用一维数组存储,对于相应的元素需要设计相应的求下标的算法以此得到数组下标。
同时对于存稀疏图的时候,十分的浪费空间,以及在运算的过程中的时间(顶点多,但是边少),此时我们可以考虑链式的存储方法。
#### b.代码实现
/类的定义/
pragma once
include <limits.h>
include <string>
using namespace std;
define MAX_VERTEX_NUM 20 //最大的顶点数
typedef string ElemType;
const int infinity = INT_MAX;
struct ArcCell //用于保存图中的每一条边的信息
{
int adj; //对于无权图0,1表示是否相连,对于有权图表示权值
ElemType info; //记录每个边的信息
};
struct MGraph { //用于保存图的数据
ElemType vexs[MAX_VERTEX_NUM]; //记录图中每一个顶点的信息
ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //记录图中每一个边的信息
int vexnum; //记录顶点数目
int arcnum; //记录边的数目
int kind; //记录图的类型
};
class Graph
{
MGraph mgraph;
public:
void createGraph();
int LocateVex(ElemType u); //定位Vex并且返回该节点的位置
bool CreateDG(); //构造一个有向图
bool CreateUDG(); //构造一个无向图
bool CreateDN(); //构造一个有向网
bool CreateUDN(); //构造一个无向网
void DFS(int v); //深度优先搜索
void BFS(int v); //广度优先搜索
void Display(); //打印邻接矩阵
};
以创建一个无向图为例:
/该算法默认的是顶点中使用字符串存放信息,边上面没有信息/
bool Graph::CreateUDG()
{
int i, j;
cout << "请输入你的顶点数和边数:";
cin >> i >> j;
mgraph.vexnum = i;
mgraph.arcnum = j;
cout << "请输入各顶点的信息:";
for (int i = 0; i < mgraph.vexnum; i++)
{
cin >> mgraph.vexs[i];
}
for (int i = 0; i < mgraph.vexnum; i++)
{
for(int j=0;j<mgraph.vexnum;j++)
{
mgraph.arcs[i][j].adj = 0;
mgraph.arcs[i][j].info = "\0";
}
}
cout << "请输入相邻顶点的边:";
for (int i = 0; i < mgraph.arcnum; i++)
{
ElemType v1, v2;
cin >> v1 >> v2;
int m = LocateVex(v1);
int n = LocateVex(v2);
mgraph.arcs[m][n].adj = 1;
mgraph.arcs[n][m].adj = 1;
}
mgraph.kind = 2;
return true;
}
### 4.2.2 图的链式储存
#### a.邻接表
相比于临接矩阵的形式,对于稀疏矩阵将会十分浪费空间,那么我们可以采用临接表的形式,其原理为开辟一个数组用于保存每一个顶点,同时该顶点指向和自己临接的其他顶点。
![](https://img2020.cnblogs.com/blog/1020928/202005/1020928-20200516173259302-1491823032.png)
注意:只有当十分稀疏的情况下临接表才能有效的节约空间,否则其所占空间实际比临接矩阵更大
定义方式:
pragma once
define maxsize 20
include <string>
using namespace std;
typedef string Elem;
struct arcNode
{
int adjvex; //用于保存指向顶点的下标
Elem info; //用于保存该边的结点
arcNode *nextarc; //用于保存下一个指向的弧
};
struct VNode { //顶点
Elem data; //保存顶点的信息
arcNode *firstarc; //用于保存该顶点第一个指向
};
class LGraph
{
VNode vertices[maxsize];
int vexnum;
int arcnum;
int kind;
public:
void CreateGraph(int e,int m); //分别代表边数与顶点数
int LocateVex(Elem u);
void AlGraphDisplay();
void FindInDegree();
bool TopologicalSort(); //若图没有回路,则输出图顶点的一个拓扑排序,否则输出false
};
初始化
include <iostream>
using namespace std;
int LGraph::LocateVex(Elem u)
{
for (int i = 0; i < vexnum; i++)
{
if (u == vertices[i].data)
return i;
}
return -1;
}
void LGraph::CreateGraph(int e, int k)
{
vexnum = k;
arcnum = e;
for (int i = 0; i < vexnum; i++) //初始化顶点信息
{
cout << "请输入第" << i + 1 << "个顶点的信息:";
cin >> vertices[i].data;
vertices[i].firstarc = NULL;
}
for (int j = 0; j < arcnum; j++) // 初始化边的信息
{
cout << "请输入对应的弧的顶点,以及信息<v1,v2,w>:";
Elem v1, v2,w;
cin >> v1 >> v2 >> w;
int h = LocateVex(v1);
int t = LocateVex(v2);
arcNode *p = new arcNode;
p->adjvex = t;
p->info = w;
p->nextarc = vertices[h].firstarc;
vertices[h].firstarc = p;
}
}
#### b.十字链表
对于一个有向图而言,当他为稀疏图,采用邻接矩阵十分的浪费空间,但是采用邻接表(无论正邻接表还是逆邻接表)都只能在求出度(入度)的时候十分的简便,无法兼顾,所以我们需要一种结构可以在有向图求出度与入度时都十分简便。
十字链表结合了邻接表与逆邻接表,同时保存了弧结点的弧头和弧尾,同时每一个顶点同时保存了指向他以及指出的结点。
![](https://images2017.cnblogs.com/blog/1063500/201711/1063500-20171112223859497-1649164244.png)
## 4.3 图的遍历
### 4.3.1 深度优先搜索(DFS)
访问方式:从图的某个顶点出发,按照某种已定的顺序访问下一个结点,之后以下一个结点作为初始点,再次访问下一个未被访问的结点,当遇到无法访问时返回上一个结点并且重复上一个步骤直到回到开始点(由于需要回到上一个结点,可以使用栈的形式存放已经访问过的结点)
利用递归为栈的一种特殊形式,我们可以采用递归的形式对上述问题进行求解。对于每一个结点可以理解为上一个结点的相同情况,于是可以利用递归
邻接矩阵的DFS:
int visited_DFS[MAX_VERTEX_NUM];
void Graph::DFS(int v)
{
cout << vexs[v];
visited_DFS[v] = 1;
for (int j = 0; j < vexnum; j++)
{
if (arcs[v][j].adj == 1 && visited_DFS[j] == 0)
DFS(j);
}
}
非递归算法 :
void Graph::DFS_2(int v)
{
stack<int> S; //用于保存历遍过的顶点
Visited_DFS[v] = 1;
S.push(v);
cout << vex[v] << " ";
while (!S.empty())
{
v=S.top();
S.pop();
for (int i = 0; i < vexnum; i++)
{
if (arc[v][i].adj == 1 && Visited_DFS[i] == 0) //存在边且没有被访问过
{
Visited_DFS[i] = 1;
v = i;
S.push(v);
cout << vex[v] << " ";
i = 0;
}
}
}
}
邻接表的DFS:
其实质是找与某顶点相连接的顶点,对于邻接表只需要对于每一个顶点的firstarc中的顶点进行遍历就可以了。
### 4.3.2 广度优先搜索(BFS)
DFS十分依赖于我们选择的顺序,所以当所搜索的目标在很接近初始点但是在搜索的另外一个分支的时候,就会存在搜索时间很长的情况。
BFS类似于层次遍历,首先遍历离开始点较为接近的点,于是我们得到以下算法:
1. 访问结点v
2. 访问v相邻的结点w1,w2,w3...
3. 访问上述结点相邻的结点
如上面的过程,需要一个结构用于保存我们需要访问的结点的顺序,所以我们使用队列的形式来对结果进行保存,对于每次遍历的wi,使用队列保存于他相邻的结点,在开始之初出队用于访问结点。
代码如下
void Graph::BFS(int v)
{
queue<int> Q;
visited_BFS[v] = 1;
Q.push(v);
while (!Q.empty())
{
int v = Q.front();
Q.pop();
for (int j = 0; j < vexnum; j++)
{
if (arcs[v][j].adj == 1 && visited_BFS[j] == 0)
{
Q.push(j);
visited_BFS[v] = 1;
}
}
}
}
### 4.3.3 非连通图的遍历
对于非连通图而言,我们需要知道他的连通分量,并且同时对于每一个连通分量进行遍历,对于每一个连通分量而言使用BFS和DFS
解决方法为对于每个顶点V如果没有被访问过,那么对其调用DFS或者BFS,从而让其被访问
## 4.4 最小生成树
### 4.4.1 定义
生成树中边的权值之后最小的树
原则:
- 选取n-1条边的连通图
- 尽量选择边权重小的
其意义在于:例如有n个村子,他们任意两条之间都可以修一条路,现在需要选择一种修法,使n个村子每个之间都可以相互到达(可经过其他村子),且费用(花销/路数目)最小的问题(需要n-1条边)
### 4.4.2 构造算法
#### a. Kruskal算法
基本思路:对于含有n个顶点的图,首先建立一个不含边,仅仅含有这n个顶点的图,依次将权值小的边选择出来,如果该边的两个顶点处于已有图中的不同连通分量中,则将该边加入到图中,直到图中仅有一个连通分量。
/此处采用伪代码形式/
void Kruskal()
{
MST={};
while(MST中不到|V|-1条边&&E中还有边)
{
e(v,w)=E中权最小的边; //使用堆的形式按照权值保存
E=E-e(v,w);
if(e(v,w)不构成回路) //采用并查集的形式,也可以利用数组的形式进行处理
MST+=e(v,w);
else
continue;
}
}
![image-20220516100821317](https://cdn.jsdelivr.net/gh/Bacaf/Picture/img/image-20220516100821317.png)
#### b. Prim 算法
基本思路:将某个图的顶点作为集合V,创建另外一个集合U,初始状态下的U有u0(其中u0为任意V中的集合)重复如下步骤:在(V-U)中找一个点v1,U中找一个点u1,满足v1与u1的边的权最小,并且把这条边加入树的边集,v1加入到U中,直到V=U为止停止该过程。
该算法的思想有点类似与Dijkstra,需要每次选择结点之后计算对应的dist[i]
/*此处采用伪代码形式
注意判断最终的MST中的顶点是否等于V中顶点以此来判断是否为连通图
*/
void Prim()
{
MST={s}; //初始化一个节点,表示一个树
while(1)
{
v=未收录的节点中dist最小的; //这里的dist表示节点到树的距离
if(v不存在)
break;
MST+=V; //这里可以创建一个dist数组来表示权值与是否被收录,如果被收录dist[v]=0
/*对V相邻顶点的权值进行更新*/
while(v的邻接顶点w)
{
if(w未被收录)
{
if(dist[w]>E(v,w))
{
dist[w]=E(v,w);
}
}
}
}
}
![image-20220516101025736](https://cdn.jsdelivr.net/gh/Bacaf/Picture/img/image-20220516101025736.png)
## 4.5 有向无环图及其应用
## 4.6 最短路径
#### a. 单源最短路径
#### b. 任意两个顶点间的最短路径