数据结构复习

//有一个顺序表以一个元素为基准，将所有小于他的数放在他的右边大于他的数放在他的左边。
#include<iostream>
using namespace std;
struct sqlist
{
	int data[10] = {0};
	int length=0;
};
int swap(sqlist *&l,int i,int j) {
	int temp;
	temp = l->data[i];
	l->data[i] = l->data[j];
	l->data[j] = temp;
	return 0;
}
bool listinsert(sqlist *&l, int k, int j) {
	for (int i = l->length; i>k; i--) {
		l->data[i] = l->data[i-1];
	}
	l->data[k] = j;
	l->length++;
	return true;
}
int partional(sqlist *&l,int j) {
	int k = 0;
	int k1 = 0;
	int i = 0;
	int flag = j;
	sqlist *z;
	z = (sqlist*)malloc(sizeof(sqlist));
	z->data[0] = flag;
	z->length = 1;
	while (i<=l->length)
	{
		if (l->data[i] < flag) {
			//printf("%d#", l->data[i]);
			listinsert(z, 0,l->data[i]);
			k1++;
		}
		else {
			//printf("%d!", l->data[i]);
			z->data[k1 + 1] = l->data[i];
			z->length++;
			k1++;
		}

		i++;

	}
	l = z;
	return 0;
}
int main() {
	sqlist *list;
	list=(sqlist*)malloc(sizeof(sqlist));
	int a[10] = { 4,5,6,2,3,7,8, 10};
	for (int i = 0; i < 10; i++) {
		list->data[i] = a[i];
	}
	list->length = 10;
	partional(list, 5);
	for (int j =0; j < list->length; j++) {
		printf("%d ", list->data[j]);
	}
}

将一个顺序表中的元素从大到小排序，将所有的奇数移动到偶数前面

int movel(sqlist *&l,int k) {
	int i = 0, j = l->length;
	int priv = l->data[0];
	while (i<j)
	{
		while (i < j&&l->data[j] % 2 == 0)
			j--;
		l->data[i] = l->data[j];
		while (i < j&&l->data[i] % 2 == 1)
			i++;
		l->data[j] = l->data[i];
		
	}
	l->data[i] = priv;
	return 0;
}
int main() {
	sqlist *list;
	list=(sqlist*)malloc(sizeof(sqlist));
	int a[10] = { 4,5,6,2,3,7,8, 10};
	for (int i = 0; i < 10; i++) {
		list->data[i] = a[i];
	}
	list->length = 10;
	movel(list, 2);
	for (int j =0; j < list->length; j++) {
		printf("%d ", list->data[j]);
	}
}

单链表

单链表采用头节点：

1>单链表中首节点的插入和删除操作与其他节点一致，无需进行特殊处理。

2>无论单链表是否为空都有一个头节点，因此统一了空表和非空表的处理过程。

typedef struct LNode{
    elemtype data;
    struct *lnode_next;
}Llinknode;

建立单链表

尾插法

Llinknode *createlist(int a[],int n) {
	Llinknode *l;
	Llinknode *s;
	Llinknode *temp;
	l = (Llinknode*)malloc(sizeof(Llinknode));
	temp = l;
	for (int i = 0; i < n; i++) {
		s=(Llinknode*)malloc(sizeof(Llinknode));
		s->data = a[i];
		temp->lnode_next = s;
		temp = s;
	}
	temp->lnode_next = NULL;
	return l;
}

头插法

Llinknode *createlist1(int a[], int n) {
	Llinknode *l;
	Llinknode *s;
	l = (Llinknode*)malloc(sizeof(Llinknode));
	l->lnode_next = NULL;
	for (int i = 0; i < n; i++) {
		s = (Llinknode*)malloc(sizeof(Llinknode));
		s->data = a[i];
		s->lnode_next = l->lnode_next;
		l->lnode_next = s;

	}

	return l;
}
int main() {
	//sqlist *list;
	//list=(sqlist*)malloc(sizeof(sqlist));
	//int a[10] = { 4,5,6,2,3,7,8, 10};
	//for (int i = 0; i < 10; i++) {
	//	list->data[i] = a[i];
	//}
	//list->length = 10;
	//movel(list, 2);
	//for (int j =0; j < list->length; j++) {
	//	printf("%d ", list->data[j]);
	//}
	Llinknode *l,*s;
	int a[5] = { 1,2,3,4,5 };
	l = createlist1(a, 5);
	s = l;
	while (s->lnode_next!= NULL) {
		s = s->lnode_next;
		printf("%d ", s->data);
		
	}

}

初始化单链表

void Initlist(Llinknode *&l) {
	l = (Llinknode*)malloc(sizeof(Llinknode));
	l->lnode_next = NULL;
}

销毁单链表#####

void Destorylist(Llinknode *&l) {
	Llinknode *temp = l,*p=l->lnode_next;
	while (p!=NULL)
	{
		free(temp);
		temp = p;
		p = p->lnode_next;
	}
	free(p);
}

判断单链表是否为空表

void Listempty(Llinknode *&p){
    return (p->lnode_next==NUll);
}

返回单链表长度

int listlength(Llinkenode *p){
    Llinknode *l=p;
    int p1=0;
while(l->next!=NUll){
    p1++;
    p=p->next;
}
    return p1;
}

输出单链表

int dislist(Llinkenode *p){
    Llinknode *l=p;
while(l->next!=NUll){
    p=p->next;
    printf("%d",l->data);
}
    return 0;
}

求线性表中的某个数据元素

#按照值
Llinkenode *Locatelist(Llinkenode *p,int flag){
    Llinknode *l=p;
    int p1=0;
while(l->next!=NUll&&l->data!=flag){
    p1++;
    l=l->next;
}
    if(l->next!=NULL){
         return l,p1/*p1为他在表里的逻辑顺序*/);
    }
   else{
       return false;
   }
}
#按照逻辑顺序
Llinkenode *Locatelist(Llinkenode *p,int flag){
    Llinknode *l=p;
    int p1=0;
while(l->next!=NUll&&p1==flag){
    p1++;
    l=l->next;
}
    if(l->next!=NULL){
         return l,p1/*p1为他在表里的逻辑顺序*/);
    }
   else{
       return false;
   }
}

插入数据算法

bool listinsert(Llinknode *&l,int i,int j) {
	if (i <= 0) {
		return false;
	}
	Llinknode *p = l,*s;
	while (j<i-1&&p!=NULL)
	{
		j++;
		p = p->lnode_next;
	}
	if (p == NULL) {
		return false;
	}
	else {
		s = (Llinknode*)malloc(sizeof(Llinknode));
		s->data = j;
		s->lnode_next = p->lnode_next;
		p->lnode_next = s;
		return true;
	}
}

删除数据元素

bool Listdelete(Llinknode *&l, int i) {
	int z = 0;
	Llinknode *p1 = l,*q,*o;
	while (z < i - 1 && p1->lnode_next!=NULL) {
		z++;
		p1 = p1->lnode_next;
	}
	if (p1 == NULL) {
		return false;
	}
	else {
	   q = p1->lnode_next;
	   if (q == NULL) {
		   return false;
	   };
	   p1->lnode_next = q->lnode_next;
	   free(q);
	   return true;
	}
}

一个单链表中将其分为两个单链表

int split(Llinknode *&p,Llinknode *&qA,Llinknode *&qB) {
	Llinknode *q = p,*q1,*q2,*q4,*q5;
	int i = 0;
	q1 = qA;
	q2 = qB;
	while (q->lnode_next!=NULL) {
		q = q->lnode_next;
		if (i % 2 == 0) {
			cout << q->data << "*";
			q4 = (Llinknode*)malloc(sizeof(Llinknode));
			q4->data = q->data;
			q4->lnode_next = q1->lnode_next;
			q1->lnode_next = q4;
			q1=q1->lnode_next;
		}
		else {
			cout << q->data << "#";
			q5 = (Llinknode*)malloc(sizeof(Llinknode));
			q5->lnode_next = NULL;
			q5->data = q->data;
			q5->lnode_next = q2->lnode_next;
			q2->lnode_next = q5;
			q2= q2->lnode_next;
		}
		cout << i<<"\n";
		i++;
	}
	/*q1->lnode_next = NULL;
	q2->lnode_next = NULL;*/
	return 0;
}
int main() {
	//sqlist *list;
	//list=(sqlist*)malloc(sizeof(sqlist));
	//int a[10] = { 4,5,6,2,3,7,8, 10};
	//for (int i = 0; i < 10; i++) {
	//	list->data[i] = a[i];
	//}
	//list->length = 10;
	//movel(list, 2);
	//for (int j =0; j < list->length; j++) {
	//	printf("%d ", list->data[j]);
	//}
	Llinknode *l,*s,*q6,*q7,*s1;
	q6 = (Llinknode*)(malloc)(sizeof(Llinknode));
	q7 = (Llinknode*)(malloc)(sizeof(Llinknode));
	q6->lnode_next = NULL;
	q7->lnode_next = NULL;
	int a[5] = { 1,2,3,4,5 };
	l = createlist(a, 5);
	split(l, q6, q7);
	s = q6;
	s1 = q7;
	while (s->lnode_next!= NULL) {
		s = s->lnode_next;
		printf("%d ", s->data);
		
		
	}
	printf("\n");
	while (s1->lnode_next != NULL) {
		s1 = s1->lnode_next;
		printf("%d ", s1->data);
		
	}

}

删除单链表中元素值最大的节点

int max_my(Llinknode *p) {
	Llinknode *q = p;
	int max = q->data;
	int i = 0;
	while (q->lnode_next!= NULL) {
		q = q->lnode_next;
		if (max < q->lnode_next->data) {
			max = q->lnode_next->data;
			
		}
		cout << max << i<<"##\n";
	}
	cout << "xasxsax";
	return max;
}
int main() {
	Llinknode *l,*s,*q6,*q7,*s1;
	q6 = (Llinknode*)(malloc)(sizeof(Llinknode));
	q7 = (Llinknode*)(malloc)(sizeof(Llinknode));
	q6->lnode_next = NULL;
	q7->lnode_next = NULL;
	int a[5] = { 1,2,3,4,5 };
	l = createlist(a, 5);
	printf("%d", max_my(l));
}

双链表

typedef struct DNode{
    int data;
    struct DNode *p1;
    struct DNode *p2;
}DLinkNode;

建立双链表

void createinf(DLinkNode *&l,int a[],int n){
    DLinkNode *s;
    l=(DLinkNode*)malloc(sizeof(DLinkNode));
    l->p1=NULL;
    l->p2=NULL;
    for(int i=0;i<n;i++){
        s=(DLinkNode*)malloc(sizeof(DLinkNode));
        s->data=a[i];
        s->p1=l;
        s->p2=l->p2;
        l->p2=s;
        l=s;
    }
}

尾插法建立双链表

void createinf(DLinkNode *&l,int a[],int n){
    DLinkNode *s;
    l=(DLinkNode*)malloc(sizeof(DLinkNode));
    l->p1=NULL;
    l->p2=NULL;
    for(int i=0;i<n;i++){
        s=(DLinkNode*)malloc(sizeof(DLinkNode));
        s->data=a[i];
        l->p2=s;
        s->p1=l;
        s->p2=NULL;
        l=s;
    }
}

插入算法实现

bool ListInsert(DLinknode *&l,int i,int j){
    DLinknode *q=l,*s;
    int k=0;
while(q->p2!=NULL&&k<i-1){
    q=q->p2;
    k++;
}
    if(p==NULL)
        return false;
    s=(DLinknode*)malloc(sizeof(DLinknode));
    s->p1=q;
    s->p2=q->p2;    
    q->p2=s;
    s->data=j;
    
}

删除算法

bool Listdelete(DLinknode *&l,int i){
    DLinknode *q=l,*s;
    int k=0;
while(q->p2!=NULL&&k<i-1){
    q=q->p2;
    k++;
}
    if(p==NULL)
        return false;
   q->p2=q->p2->p2;
    q->p2->p2->p1=q;
    free(q->next);
    
}

逆置算法实现

void reverse(LNode *l){
    LNode *p=l->next,*p1，*p2;
    p1=(LNode*)malloc(sizeof(LNode));
    p1->next=NULL;
    p1->priv=NULL;
    while(p1->next!=NULL){
	p=p->next;
    }
    while(p->priv!=NULL){
        p2=(LNode*)malloc(sizeof(LNode));
        p2->priv=p1;
        p2->data=p->data;
        p2->next=p->next;
        p=p->priv;
    }
}

排序算法

void sort(LNode *&l){
    LNode *l1=l,*l2;
    p=L->next->next;
    l2=(LNode*)malloc(sizeof(LNode));
    l2->next=NULL;
    l2->prior=NULL;
    while(p!=NULL){
        q=p->next;
        pre=L2;
        while(pre->next!=NULL&&pre->next->data<p->data){
            pre=pre->next;
            p->next=pre->next;
            if(pre->next!=NULL){
				pre->Next->prior=p;
            }
            pre->next=p;
            p->prior=pre;
            p=q;
        }
    }
}

循环链表

把单链表改为循环链表的过程是将他的尾节点next指向首节点，整个单链表形成一个循环。

把双链表改为循环链表的过程是将他的尾节点的next指向首节点，将首节点的privo指向尾节点。

循环链表和非循环链表的实现基本一致，不一致的地方是判断循环结束的条件是p->next==L.，另外在双链表中可以通过L->prior快速找到尾节点。

有序表

有序表是指其中所有元素以递减或者递增的方式有序排列。

栈和队列

栈

栈的 抽象数据类型

struct stack
{
	int data[20];
	int Initstack(&s); //初始化栈
	int Destroystack(&s);  //销毁一个栈
	int Stackempty(&s);   //销毁一个栈
	int push(&s,e);          //进栈
	int pop(&s, &e);      //出栈
	int gettop(s, &e);   //取栈顶元素
}stack;

n个不同的元素通过一个栈产生的出栈序列的个数为1 n + 1 C 2 n n {\frac{1}{n+1}C_{2n}^{n}}n+11​C2nn​个。

顺序栈类型

typedef struct{
 int DATA[maxsize];
 int top;
}sqstack;

栈空的判断的条件：x->top=-1

栈满的判断的条件：x->top=maxsize-1

元素进栈的操作，x->top++;x->data[top]=e;

出栈操作 x->data[top]=0;:x->top–;

初始化栈的操作

void initstack(sqstack *&l){
    l=(sqstack*)malloc(sizeof(sqstack));
    l->data={0};
	l->top=-1;
}

销毁栈

void DesktoryStack(sqstack *&s){
    free(s);
}

判断栈是否为空

bool isempty(sqstack *&s){
    return (s->top==-1);
}

进栈

void push(sqstack *&e,int i){
	e->top++;
    e->data[e->top]=i;
}

出栈

void pop(sqstack *&e,int &da){
    if(e->top==-1){
        return false;
    }
    da=e->data[e->top];
    e->data[e->top]=0;
    e->top--;
}

取栈顶元素

bool gettop(sqstack *&e,int &da){
     if(e->top==-1){
        return false;
    }
    da=e->data[e->top];
    return true;
}

判断对称串

struct sqstack {
	int data[100] = {0};
	int top;
};
void push(sqstack *&e, int i) {
	e->top++;
	e->data[e->top] = i;
}
bool pop(sqstack *&e, int &da) {
	if (e->top == -1) {
		return false;
	}
	da = e->data[e->top];
	e->data[e->top] = 0;
	e->top--;
}
void initstack(sqstack *&l) {
	l = (sqstack*)malloc(sizeof(sqstack));
	l->top = -1;
}
int main() {
	sqstack *s;
	initstack(s);
	int a[9] = { 1,2,3,4,5,4,3,2,1 };
	int b[9];
	int count,k=0;
	for (int i = 0; i < 9; i++) {
		push(s, a[i]);
	}
	while (s->top != -1) {
		pop(s, count);
		b[k] = count;
		k++;
	}
	for (int i = 0; i < 9; i++) {
		cout << b[i] << " ";
	}
}

栈的链式存储

struct linknode{
int data;
linknode *next;
}

栈空的条件：s->next==NULL;

初始化栈

void initstack(linknode *&l){
	l=(linkenode*)malloc(sizeof(linknode));
    l->next=NULL;
}

销毁栈

void Destorystack(linknode *&l){
    linknode *s;
    s=l;
    while(l->next!=NULL){
        free(l);
        s=s->next;
        l=s;
    }
    free(l);
    free(s);
}

判断栈是否为空

bool stackempty(Linknode *&l){
    return (l->next==NULL);
}

进栈

void push(Linknode *&l,int e){
    Linknode *q;
    q=(Linknode*)malloc(sizeof(Linknode));
    q->next=l->next;
    q->data=e;
    l->next=q;
}

出栈

void pop(Linknode *&l,int &e){
   if(s->next==NULL)
       return false;
  e=l->next->data;
  linknode *q=l->next;
  free(l->next);
  l->next=q->next;
   free(q);
}

取出栈顶元素

void gettop(Linknode *&l,int &e){
    if(s->next==NULL)
       return false;
    e=->l->next->data;
}

队列

typedef struct{
    int data[max];
    int front,rear;
}sqqueue;

初始化队列

void initsqueue(sqQueue 8&q){
	q=(SqQueue*)malloc(sizeof(sqQueue));
    q->font=q->rear=-1;
}

销毁队列

void DestoryQueue(SqQueue *&q){
    free(q);
}

判断队列是否为真

bool QueueEmpty(SqQueue *q){
    return (q->font==q->rear);
}

进入队列

void enQueue(SqQueue *&q,int e){
    if(q->near==MaxSize-1)
        return false;
    q->rear++;
    q->data[q->rear]=e;
}

出队列

void deQueue(SqQueue *&q,int &e){
	 if(q->near==q->front)
        return false;
    q->front++:
    e=q->data[q->front];
}

环形队列

初始化环型队列

队头指针front循环增1：front=(front+1)%maxsize

对尾指针rear循环增1：rear=(rear+1)%maxsize

队空条件：q->rear==q->front

队满条件 ：(q->rear+1)%maxsize==q->front

void InitQueue(SqQueue *&q){
	q=(Squeue*)malloc(sizeof(Squeue));
    q->font=q->rear=0;
}

队空判断

bool QueueEmpty(SqQueue *q){
    return (q->front==q->near);
}

进队列

bool enQueue(SqQueue *&q,int e){
    if(q->rear+1)%maxsize==q->front){
        return false;
    }
    q->front=(q->front+1)%maxsize;
    e=q->data[q->front];
    
}

出队列

bool deQueue(SqQueue *&q,int &e){
    if(q->rear==q->front)
        return false;
    q->front=(q->front+1)%maxsize;
    e=q->data[q->front];
}

队列的链式存储方式

struct datanode{
    int data;
    struct datanode *next;
}
struct Linkqueue{
    datanode *next;
   datanode *priv;
}

初始化链式队列

void initlinkqueue(Linkqueue *&q){
	q=(Linkqueue*)malloc(sizeof(Linkqueue));
    q->next=q->priv=NULL;
}

销毁队列

void destoryLinkqueue(Linkqueue *&l){
   datanode *d=l->priv,*p;
    p=d;
  while(p->next!=NULL){
		free(d);
      	p=d->next;
      d=d->next;
  }
    free(d);
    free(q);
}

判断队列是否为空

void Linkqueueempty(Linkqueue *&l){
    return (q->next==NULL);
or    return ( q->next==q->priv);
}

进队列

void enqueue(LinKqueue *&l,int e){
    datanode *p=l->next，*q;
    q=(datanode*)malloc(sizeof(datanode));
    q->data=e;
    q->next=NULL;
    p->next=q;
    l->next=q;
}

出队列

bool dequeue(Linkqueue *&l,int &e){
    datanode *p=l->priv;
    l->priv=p->next;
   e=p->data;
    free(p);
}

树

树中的某个节点的子树的个数称为该节点的度。

树中的所有节点的度最大值为树的度，通常把度为m的树称为m次树。

单分支节点为1，双分支节点为2，度为0的节点为叶子节点。

树的性质：

1.树中的节点数等于所有节点的度数和加1.

2.度为m的树中第i层上最多有m i − 1 {m^{i-1}}mi−1个节点（i>=1）。

推广：当一棵m次树的第i层上有m i − 1 {m^{i-1}}mi−1个节点的时候，称为这个树是满的，若一颗m次数所有叶节点在同一层，且每一层都满，增称为其为满m次数。

3.高度为h的m次树最多有m h − 1 m − 1 {\frac{m^{h}-1}{m-1}}m−1mh−1​个节点。

4.具有n个节点的m次树的最高度为对3式子求解m h − 1 m − 1 = n {\frac{m^{h}-1}{m-1}=n}m−1mh−1​=n

树的遍历

先根遍历

1>访问根节点

2>按照从左往右的顺序进行先根遍历根节点得到每一棵树。

后跟遍历

1>按照从左往右的顺序进行先根遍历根节点得到每一棵树。

2>访问根节点

层序遍历

从根节点开始按照从上往下的方式，从左往右的方式访问树中的每一个节点。

树的存储结构

双亲存储结构

#根节点设置为-1

孩子链存储结构

#可以便捷的找到孩子节点

孩子兄弟链存储结构

#可以便捷的转换为二叉树

二叉树

二叉树的性质

1>非空二叉树上的叶子节点数等于双分支节点数加1。

2>非空二叉树的第i层最多有2 i − 1 {2^{i-1}}2i−1个节点。

3>高度为h的二叉树最多有2 h − 1 {2^{h-1}}2h−1个节点

4>具有n个节点的二叉树的完全二叉树的高度为l o g 2 ( n + 1 ) {log_{2}(n+1)}log2​(n+1)

将一棵树转换为二叉树的方法：
1.记住左边的树表示父子关系，右边表示兄弟关系。从左往右看。

二叉树的顺序存储方式：

简单来说就是将一个二叉树转换位一个完全的二叉树，完全二叉树中对应二叉树值不存在的地方设为“#”，反之设为该值。

二叉树链式存储方式：

struct node{
    struct *left;
    struct *right;
    int data;
    struct *parrents; //有时加有时不加
}

二叉树的创建方式

二叉树的销毁

void Destory(BTNode *&b){
    if(b!=NULL){
    Destory(b->lchild);
    Destory(b->rchild);
    free(b);}
}

二叉树的查找

BTNode *FindNode(BTNode *b,int x){
	BTNode *p;
    if(b==NULL)
        return NULL;
    else if(b->data==x)
        return b;
    else{
        p=FindNode(b->lchild,x);
        if(p!=NULL)
            return p;
        else{
            return FindNode(p->rchild,x);
        }
    }
}

找孩子节点

求高度

int BTheight(BTNode *b){
    int lchild,rchild;
    if(b==NULL) return 0;
    else{
        lchild=BTheight(b->lchild);
        rchild=BTheight(b->rchild);
        return (lchildh>rchildh)?(lchildh+1):(rchildh+1);
    }
}

二叉树的遍历

先序遍历

1>先访问根节点.

2>先序遍历左子树

3>先序遍历右子树

中序遍历

1>中序遍历左子树

2>访问根节点

3>中序遍历右子树

后序遍历

1>后序遍历左子树

2>后序遍历右子树

3>访问根节点

void PreOrder(BTNode *p){
    if(b!=NULL){
        printf("%c",p->data);
        PreOrder(b->lchild);
        PreOrder(b->rchild);
    }
}
void Inorder(BTNode *p){
    if(b!=NULL){
         
        InOrder(b->lchild);
         printf("%c",p->data);
        InOrder(b->rchild);
    }
}
void postorder(BTNode *p){
    if(b!=NULL){
         
        postOrder(b->lchild);   
        postOrder(b->rchild);
         printf("%c",p->data);
    }
}
层序遍历用队列的形式实现

哈夫曼树

哈夫曼树的构造

对于具有n0个叶子节点的哈夫曼树，共有2n-1个节点

哈夫曼编码

哈夫曼编码的平均长度:∑ i = 1 n 0 d i ∗ w i {\sum_{i=1}^{n0}di*wi}∑i=1n0​di∗wi

看一下p240例子：7.20

图

图由两个部分组成，V和G，V代表角的集合，G表示边的集合。

度：在无向图中，一个顶点关联的数目称为该顶点的度。在有向图中，顶点的度分为入度和出度，一个顶点的入度和出度之和称为该顶点的度。

一个图中有n个顶点和e条边，每个顶点的度为d i ( 0 < = i < = n − 1 ) {d_{i}(0<=i<=n-1)}di​(0<=i<=n−1)则有:e = 1 2 ∑ i = 0 n − 1 d i {e=\frac{1}{2}\sum_{i=0}^{n-1}d_{i}}e=21​∑i=0n−1​di​

也就是说一个图中所有顶点的度之和为边数的两倍。

完全图

若无向图中的每两个顶点之间都存在一个边，有向图中的每两个顶点之间都存在方向相反的两条边。有向图包含n(n-1)条边。无向图有n（n-1）/2条边。

若图中的任意两点都联通则称强连通图。

强连通图中边数等于顶点。

图的存储结构

图的邻接矩阵

图的邻接矩阵的声明

typedef struct
{
    int no;
    InfoType info;
}VertexType;
typedef struct
{
	int edges[MAXV][MAXV];
    int n,e;
    VertexType vexs[MAXY];
}matGraph;

图的邻接表的形式

struct ANode{
    int adjvex;
    struct ANode *nextarc;
    int weight;
}
struct Vnode{
    int inf;
    ANode *firstarc;
}

创建图

void CreateADj(ADjGraph *&G,int A[MAXV][MAXV],int n,int e){
    int i,j;
    ArcNode *p;
   G=(AdjGraph*)malloc(sizeof(AdjGraph));
    for(int i=0;i<n;i++){
        G->adjlist[i].firstarc=NULL;
    }
    for(int i=0;i<n;i++){
        for(int j=n-1;j>0;j--){
            if(A[i][j]!=0&&A[i][j]!=INF)
            {
                p=(ArcNode*)malloc(sizeof(ArcNode));
                p->adjvex=j;
                p->weight=A[i][j];
                p->nextarc=G->adjlist[i].firstarc;
                G->adjlist[i].firstarc=p;
            }
            G->n=n;
            G->e=n;
        }
    }
}

输出图

void DisAdj(AdjGraph *G){
    int i,ArcNode *p;
    for(int i=0;i<G->n;i++){
        p=G->adjlist[i].firstarc;
        printf("%3d",i);
        while(p!=NULL){
            printf("%3d[%d]->",p->adjvex,p->weight);
            p=p->nextarc;
        }
        printf("^\n");
    }
}

销毁图

void DestoryAdj(AdjGraph *&G){
    int i;
    ArcNode *pre,*p;
    for(int i=0;i<G->n;i++){
if(pre!=NULL){
    p=pre->nextarc;
    while(p!=NULL){
free(pre);
    pre=p;
        p=p->nexarc;
    }
    free(pre);
}}
    free(G);S
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-C2gByd7f-1640692515375)(C:\Users\mzy\AppData\Roaming\Typora\typora-user-images\image-20211227223046730.png)]

深度优先遍历

int visited[Max]={0};
void DFS(AdjGraph *G,int v){
    ArcNode *p;
    visited[v]=1;
    printf("%d",v);
    p=G->adjlist[v].firstarc;
    while(p!=NULL){
if(visited[p->adjvex]==0)
    DFS(g,P->ADJVEX);
    p=p->nextarc;}
    
}

广度优先遍历

void BFS(AdjGraph *G,int v){
    int w,i;
    ArcNode *p;
    SqQueue *qu;
    InitQueue(qu);
    int visited[MAXV]={0};
    printf("%d",v);
    visited[v]=1;
    enQueue(qu,v);
    while(QueueEmpty(qu)){
        deQueue(qu,w);
        p=G->adjlist[w].firstarc;
        while(p!=NULL){
            if(visited[p->adjvex]==0){
                printf("%d",p->adjvex);
                visited[p->adjvex]=1;
                enQueue(qu,p->adjvex);
            }
            p=p->nextarc;
        }
    }
    printf("\n");
}

Prim算法

Kruskal算法

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-A56UaGOR-1640692515376)(C:\Users\mzy\AppData\Roaming\Typora\typora-user-images\image-20211227233945665.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kHDa8W4f-1640692515377)(C:\Users\mzy\AppData\Roaming\Typora\typora-user-images\image-20211227234023565.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XOEZlb0z-1640692515378)(C:\Users\mzy\AppData\Roaming\Typora\typora-user-images\image-20211227234142537.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZIzMKZ6K-1640692515379)(C:\Users\mzy\AppData\Roaming\Typora\typora-user-images\image-20211228001509672.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tjg60mAG-1640692515380)(C:\Users\mzy\AppData\Roaming\Typora\typora-user-images\image-20211228025209305.png)]
j(AdjGraph *&G){
int i;
ArcNode *pre,*p;
for(int i=0;in;i++){
if(pre!=NULL){
p=pre->nextarc;
while(p!=NULL){
free(pre);
pre=p;
p=p->nexarc;
}
free(pre);
}}
free(G);S
}


[外链图片转存中...(img-C2gByd7f-1640692515375)]

深度优先遍历

```c++
int visited[Max]={0};
void DFS(AdjGraph *G,int v){
    ArcNode *p;
    visited[v]=1;
    printf("%d",v);
    p=G->adjlist[v].firstarc;
    while(p!=NULL){
if(visited[p->adjvex]==0)
    DFS(g,P->ADJVEX);
    p=p->nextarc;}
    
}

广度优先遍历

void BFS(AdjGraph *G,int v){
    int w,i;
    ArcNode *p;
    SqQueue *qu;
    InitQueue(qu);
    int visited[MAXV]={0};
    printf("%d",v);
    visited[v]=1;
    enQueue(qu,v);
    while(QueueEmpty(qu)){
        deQueue(qu,w);
        p=G->adjlist[w].firstarc;
        while(p!=NULL){
            if(visited[p->adjvex]==0){
                printf("%d",p->adjvex);
                visited[p->adjvex]=1;
                enQueue(qu,p->adjvex);
            }
            p=p->nextarc;
        }
    }
    printf("\n");
}

Prim算法

Kruskal算法

版权声明：本文为qq_51324662原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。