首页 > 其他分享 >数据结构

数据结构

时间：2023-05-17 20:13:10浏览次数：42  
标签：结点 遍历 int NULL --- -- 数据结构

数据结构

1 线性表

1.1 顺序表

1.1.1 比较数组大小

题目：

设A= (a1, a2, am)和B= (b1, b2, ... , bn)均为顺序表，A'和B'分别是除去最大公共前缀后的子表。例如，A= (b, e, i, j, i, n, g)，B= (b, e, i, f, a, n, g), 则两者的最大公共前缀为b、e、i，在两个顺序表中除去最大公共前缀后的子表分别为A'=(j, i, n, g), B'= (f, a, n, g)。若A'=B'=空表，则A=B。若A'=空表且B'≠空表，或两者均不为空且A'的第一个元素值小于B'的第一个元素值，则A<B,否则A>B。试编写一个函数，根据上述方法比较A和B的大小，A和B中的元素为float型。

思路：

编写一个int类型函数，A=B返回0，A<B返回-1，A>B返回1。传入参数为A,B数组及A,B数组长度：An，Bn。

先遍历两个数组，直至出现两数组元素不等，或某一为空，再将i与数组长度比较，An == Bn == 0，则两数组相等，若A'=空表且B'≠空表，或两者均不为空且A'的第一个元素值小于B'的第一个元素值，则A<B,否则A>B。

1.2 链表

1.2.1 单向链表

结点结构体：

struct LNode
{
	int data;  // 数据 
	LNode* next;  // 下一个结点的指针 
};

尾插法建表（用户输入方式建表）

// 尾插法，用户输入方式建表 
void createLinkListR(LNode *&head)
{
	// 头节点
	head = (LNode*)malloc(sizeof(LNode));
	head->next = NULL;
	
	// p：用于指向新结点，r：指向最后一个结点 
	LNode *p = NULL, *r = head;
	
	// n：输入数据个数 
	int n;
	cin >> n;
	
	// 输入新结点 
	for (int i = 0; i < n; i++)
	{
		// 创建新结点 
		p = (LNode*)malloc(sizeof(LNode));
		p->next = NULL;
		
		// 输入数据 
		cin >> p->data;
		
		// 两个结点插入新结点的方法 
		p->next = r->next;
		r->next = p;
		r = p;
	}
}

尾插法建表（数组方式建表）

// 尾插法，数组方式建表 
void createList(LNode *&head, int arr[], int n)
{
	// 头节点
	head = (LNode*)malloc(sizeof(LNode));
	head->next = NULL;
	
	// p：用于指向新结点，r：指向最后一个结点 
	LNode * p = NULL, *r = head;
	
	// 输入新结点 
	for (int i = 0; i < n; i++)
	{
		// 创建新结点 
		p = (LNode*)malloc(sizeof(LNode));
		p->next = NULL;
		
		// 输入数据 
		p->data = arr[i];
		
		// 两个结点插入新结点的方法 
		p->next = r->next;
		r->next = p;
		r = p;
	}
}

头插法建表（用户输入方式建表）

// 头插法，用户输入方式建表 
void createLinkListH(LNode *&head)
{
	// 头节点
	head = (LNode*)malloc(sizeof(LNode));
	head->next = NULL;
	
	// p：用于指向新结点 
	LNode * p = NULL;
	
	// n：输入数据个数 
	int n;
	cin >> n;
	
	// 输入新结点 
	for (int i = 0; i < n; i++)
	{
		// 创建新结点 
		p = (LNode*)malloc(sizeof(LNode));
		p->next = NULL;
		
		// 输入数据 
		cin >> p->data;
		
		// 新结点插在头结点后 
		p->next = head->next;
		head->next = p;
	}
}

打印链表

void printList(LNode * L)
{
	LNode * p;
	p = L->next;
	while (p != NULL)
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}

1.2.2 双向链表

结点结构体：

struct LNode
{
	int data;  // 数据 
    LNode * prior; // 上一个结点的指针
	LNode * next;  // 下一个结点的指针 
};

建表

// 尾插法，用户输入方式建表 
void createLinkListR(LNode *&head)
{
	// 头节点
	head = (LNode*)malloc(sizeof(LNode));
	head->next = NULL;
	
	// p：用于指向新结点，r：指向最后一个结点 
	LNode * p = NULL, * r = head;
	
	// n：输入数据个数 
	int n;
	cin >> n;
	
	// 输入新结点 
	for (int i = 0; i < n; i++)
	{
		// 创建新结点 
		p = (LNode*)malloc(sizeof(LNode));
		p->next = NULL;
        p->prior = NULL;
		
		// 输入数据 
		cin >> p->data;
		
		// 两个结点插入新结点的方法 
		p->next = r->next;
        p->prior = r;
		r->next = p;
        p->next->prior = p;
		r = p;
	}
}

1.2.3 表逆置

顺序表

思路：创建两个变量i，j，i从左向右遍历，j从右向左遍历，直至 i >= j，即i、j相遇，每次遍历交换i、j所在下标的值。

void reverse(int arr[], int n)
{
	int temp;
	for (int i = 0, j = n - 1; i < j; i++, j--)
	{
		temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}

1.2.4 STL-list（双向列表）

建表

void createList(list<int>& L, int arr[], int n)
{
	for (int i = 0; i < n; i++)
	{
		L.push_back(arr[i]);
	}
}

打印链表

void printList(const list<int>& L) {

	for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

代码：

#include <iostream>
#include <cmath>
using namespace std;

#define min 0.0001
#define MaxSize 1000


int compare(float A[], int An, float B[], int Bn)
// 传入参数为A,B数组及A,B数组长度：An，Bn。
{
    int i = 0;
    while (i < An && i < Bn)
    {
        if (fabs(A[i] - B[i]) < min)  // 浮点型很难完全相等，fabs()是取绝对值函数
        {
            ++i;
        }
        else
        {
            break;
        }
    }
    // 出循环时i，即为两数组公共部分的长度

    if (i == An && i == Bn)  // 若i等于两数组长度
    {
        return 0;
    }
    else if (i == An && i < Bn || A[i] < B[i])
    // 若A'=空表且B'≠空表，或两者均不为空且A'的第一个元素值小于B'的第一个元素值
    {
        return -1;
    }
    else
    {
        return 1;
    }
}

int main()
{
    float A[MaxSize] = {1,2,3,4};
    float B[MaxSize] = {1,2,3,4,5};
    int len_A = sizeof(A)/sizeof(A[0]);
    int len_B = sizeof(B)/sizeof(B[0]);
    int ret = compare(A, len_A, B, len_B);

    if (ret == 0)
    {
        cout << "A = B" << endl;
    }

    if (ret == -1)
    {
        cout << "A < B" << endl;
    }

    if (ret == 1)
    {
        cout << "A > B" << endl;
    }

    system("pause");

    return 0;
}

2 二叉树

2.1 二叉树分类：

2.1.1 满二叉树

  • 满二叉树：除最后一层无任何子结点外，每一层上的所有结点都有两个子结点的二叉树。
graph TD 1((A1)) --- 2((A2)) --- 4((A5)) 2 --- 5((A6)) 1 --- 3((A3)) --- 6((A7)) 3 --- 7((A8))
满二叉树

2.1.2 完全二叉树

  • 完全二叉树：除了最后一层，其他层都是满的，最后一层从左向右是连续的，可以满，也可以不满，但是必须连续。也可以理解为，完全二叉树是由满二叉树将最底层从右向左删除结点得到。
graph TD 1((A1)) --- 2((A2)) --- 4((A5)) 2 --- 5((A6)) 1 --- 3((A3)) --- 6((A7))
完全二叉树

eg：满二叉树是一种特殊的完全二叉树

  • 求完全二叉树高度：

\[h=\lfloor \log_2n \rfloor + 1 \]

\[h=\lceil \log_2(n+1) \rceil \]

eg：\(\lceil x \rceil\)：向上取整，\(\lfloor x \rfloor\)：向下取整

2.2 存储结构

2.2.1 顺序存储结构

  • 只可对完全二叉树使用

![Sequential Storage Structure](image/Sequential Storage Structure.png)

2.2.2 链式存储结构

  • 二叉树结点结构体代码：
struct BTBode {
    int data;  // 数据
    BTBode* lChild;  // 左孩子
    BTBode* rChild;  // 右孩子
};
  • 树的孩子兄弟的存储结构：将树转化为二叉树的方法
struct BTBode {
    int data;  // 数据
    BTBode* child;  // 孩子结点
    BTBode* sibling;  // 兄弟结点
};

2.3 遍历

2.3.1 广度优先遍历（BFS）

树的广度优先遍历动图如下，每个节点的值即为它们的遍历顺序。所以广度优先遍历也叫层序遍历，先遍历第一层(节点 1)，再遍历第二层(节点 2，3，4)，第三层(5，6，7，8)，第四层(9，10)。

  • 数字顺序即遍历顺序
graph TD 1((1)) --- 2((2)) --- 5((5)) --- 9((9)) 1 --- 3((3)) --- 6((6)) --- 10((10)) 3 --- 7((7)) 1 --- 4((4)) --- 8((8))
广度优先遍历
/*
算法设计思路：
1.将根结点入队
2.队列不为空时循环，从队列中出列一个元素，访问它，并作以下步骤：
    2.1 如果该元素的左孩子不为空，让该元素的左孩子入队
    2.2 如果该元素的右孩子不为空，让该元素的右孩子入队
*/
void level(BTNode* bt) {
    if (bt != NULL) {
        // 创建一个队列，用于存储结点
        int front, rear;
        BTNode* que[maxSize];
        front = rear = 0;
        // 用于遍历的指针
        BTNode* p;
        
        rear = (rear + 1) % maxSize;
        que[rear] = bt;  // 根节点入队
        // 队不空的情况下循环
        while (front != rear) {
            // 出队元素并对其访问
            front = (front + 1) % maxSize;
            p = que[rear];
            Visit(p);
            // 左右孩子是否存在，存在就入队，先左后右
            if (p->lChild != NULL) {
                rear = (rear + 1) % maxSize;
                que[rear] = p->lChild;
            }
            if (p->rChild != NULL) {
                rear = (rear + 1) % maxSize;
                que[rear] = p->rChild;
            }
        }
    }
}

2.3.2 深度优先遍历（DFS）

  • 前序遍历：先访问根，在访问左子树，最后访问右子树，总结就是“中左右”；
  • 中序遍历：先访问左子树，再访问根，最后访问右子树，总结就是“左中右”；
  • 后序遍历：先访问左子树，再访问右子树，最后访问根，总结就是“左右中”；

eg：记忆方法：“中”的位置即是什么序遍历，例如：前序遍历“中左右”，“中”就是前面

  • 前序遍历：
graph TD 1((1)) --- 2((2)) --- 3((3)) 2 --- 4((4)) 1 --- 5((5)) --- 6((6)) 5 --- 7((7))
前序遍历

代码（递归）：

void r(BTBode* p) {
    if (p != NULL) {
        // 访问根结点
        visit(p);
        // 递归遍历左孩子
        r(p->lChild);
        // 递归遍历右孩子
        r(p->rChild);
    }
}

代码（非递归）：

void preorderNonrecursion(BTNode* bt) {
    if (bt != NULL) {
        // 创建一个栈，用于存储结点
        BTNode* Stack[maxsize];
        int top = -1;
        // 创建一个指针
        BTNode *p = NULL;
        // 根节点入栈
        Stack[++top] = bt;
        // 栈不空的前提下循环
        while (top != -1) {
            // 出栈一个元素
            p = Stack[top--];
            Visit(p);
            // 检测左右孩子，存在就入栈，先右后左
            if (p->rChild != NULL)
            	Stack[++top] = p->rChild;
            if (p->lChild != NULL)
            	Stack[++top] = p->1Child;
        }
    }
}
  • 中序遍历：
graph TD 1((4)) --- 2((2)) --- 4((1)) 2 --- 5((3)) 1 --- 3((6)) --- 6((5)) 3 --- 7((7))
中序遍历

代码（递归）：

void r(BTBode* p) {
    if (p != NULL) {
        // 递归遍历左孩子
        r(p->lChild);
        // 访问根结点
        visit(p);
        // 递归遍历右孩子
        r(p->rChild);
    }
}

void inorderNonrecursion(BTNode* bt) {
    if (bt != NULL) {
        // 创建一个栈，用于存储结点
        BTNode* Stack[maxsize];
        int top = -1;
        // 创建一个指针
        BTNode *p = NULL;
        p = bt;
        // 栈不空且p不空的前提下循环
        while (top != -1 || p != NULL) {
            while (p != NULL) {
                // 一直遍历左孩子，途经的结点入栈
                Stack[++top] = p;
                p = p->lChild;
            }
            if (top != -1) {
                // 出栈并访问结点
                p = Stack[top--];
                Visit(p);
                // 往右走一步
                p = p->rChild;
            }
        }
    }
}
  • 后序遍历：
graph TD 1((7)) --- 2((3)) --- 4((1)) 2 --- 5((2)) 1 --- 3((6)) --- 6((4)) 3 --- 7((5))
后序遍历

代码（递归）：

void r(BTBode* p) {
    if (p != NULL) {
        // 递归遍历左孩子
        r(p->lChild);
        // 递归遍历右孩子
        r(p->rChild);
        // 访问根结点
        visit(p);
    }
}

代码（非递归）：（在前序遍历基础上，增加一个用于逆序的栈，左右孩子访问顺序相反）

void postorderNonrecursion(BTNode* bt) {
    if (bt != NULL) {
        // 创建一个栈1，用于存储结点
        BTNode* Stack1[maxsize]; int top1 = -1;
        // 创建一个栈2，用于逆序遍历结果
        BTNode* Stack2[maxsize]; int top2 = -1;
        // 创建一个指针
        BTNode *p = NULL;
        // 根节点入栈
        Stack[++top1] = bt;
        // 栈不空的前提下循环
        while (top != -1) {
            // 出栈一个元素
            p = Stack1[top1--];
            Stack2[++top2] = p;
            // 检测左右孩子，存在就入栈，先左后右，和前序遍历相反
            if (p->lChild != NULL)
            	Stack1[++top1] = p->lChild;
            if (p->rChild != NULL)
            	Stack1[++top1] = p->rChild;
        }
        while (top2 != -1) {
            // 挨个出栈，并访问
            p = Stack2[top2--];
            Visit(p);
        }
    }
}

2.3.3 二叉树遍历例题

递归法：

步骤：

  1. 确定递归函数的参数和返回值：
    确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
  2. 确定终止条件：
    写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
  3. 确定单层递归的逻辑：
    确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

代码（前序遍历）：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 递归函数
    void traversal(TreeNode* cur, vector<int>& vec) {
        // 遇到空结点返回
        if (cur == NULL) return;
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
    }

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        traversal(root, res);
        return res;
    }
};

3 图

3.1 图存储结构

3.1.1 邻接矩阵

使用二维数组存储：图的指向对应边数组为行数指向列数，数值为权值。

例如：1 --> 2，权值为3，则在边数组中a[1][2] = 3，其余位置填0。

如果不带权值的图，1 --> 2，则在边数组中a[1][2] = 1，其余位置填0。

graph TD 1((1)) --9--> 0((0)) --6--> 4((4)) 1((1)) --3--> 2((2)) --5--> 3((3)) --1--> 4((4)) 2((2)) --2--> 0((0))

\[ \left[ \begin{matrix} 0 & 0 & 0 & 0 & 6 \\ 9 & 0 & 3 & 0 & 0 \\ 2 & 0 & 0 & 5 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ \end{matrix} \right] \tag{边数组} \]

优点：适合稠密图的存储；码量少；对边的存储、查询、更新等操作快而简单；只需要一步即可访问和修改

缺点：空间复杂度太高，存储结点比较多的图会MLE（爆内存），存储稀疏图时空间浪费太大；一般情况下无法存储重边

3.1.2 邻接表

使用动态二维数组存储：

\[ \left[ \begin{matrix} 4 \\ 0 & 2 \\ 0 & 3 \\ 4 \\ \\ \end{matrix} \right] \]

代码：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<vector<int> > v(5, vector<int>());
    v[0].push_back(4);
    
    v[1].push_back(0);
    v[1].push_back(2);
    
    v[2].push_back(0);
    v[2].push_back(3);
    
    v[3].push_back(4);
    
    return 0;
}

带权值的代码：写一个结构体，push结构体到动态数组

struct Node {
    int v, len  // v：记录连接的点，len：权值
    Node(int v, int len) {
        this->v = v;
        this->len = len;
    }
};

优点：存储效率非常高；空间复杂度优；可以存储重边

缺点：码量较大；访问和修改会变慢

3.2 最短路径

算法比较：

floyd （弗洛伊德算法） Dijkstra（迪杰斯特拉算法） bellman-ford（贝尔曼夫德算法） spfa
空间复杂度 O(N²) O(M) O(M) O(M)
时间复杂度 O(N³) O( (m+n) log N ) O(MN) 最坏也是O(MN)
适用情况 稠密图和顶点关系密切 稠密图和顶点关系密切 稀疏图和边关系密切 稀疏图和边关系密切
负权 可以 不能 可以 可以
有负权边时可否处理 可以 不能 可以 可以
判断是否存在负权回路 不能 不能 可以 可以

  • Floyd 算法虽然总体上时间复杂度较高，但可以处理带负权边的图（但不能有负权回路），并且均摊到每一点对上，在所有的算法中还是属于比较优秀的算法。另外，floyd算法较小的编码复杂度也是一大优势，所以，如果要求的是所有点对间的最短路径，或者如果数据范围较小，则floyd算法比较合适。

  • Dijkstra算法最大的弊端就是他无法处理带有负权边以及负权回路的图，但是Dijkstra算法具有良好的可扩展性，扩展后可以适应很多问题。另外用堆优化的Dijkstra算法的时间复杂度可以达到O（M log N）。当边有负权，甚至存在负权回路时，需要使用Bellman-ford 算法或者队列优化的Bellman-ford算法，因此我们选择最短路径法时，根据实际的需求和每一种算法的特性，选择合适的算法来使用。

3.2.1 Dijkstra（迪杰斯特拉算法）

视频讲解：dijstra算法 - bilibili

路径图：

graph TD 0((0)) --10--> 2((2)) --5--> 1((1)) 0((0)) --30--> 4((4)) --20--> 3((3)) --10--> 5((5)) 2((2)) --50--> 3((3)) 0((0)) --100--> 5((5)) 4((4)) --60--> 5((5))

代码：（邻接矩阵）

#include <iostream>
using namespace std;

// 邻接矩阵 
int mp[6][6] = {{1000000, 1000000, 10,      100000,  30,      100},
				{1000000, 1000000, 1000000, 1000000, 1000000, 1000000},
				{1000000, 5, 	   1000000, 50,      1000000, 1000000},
				{1000000, 1000000, 1000000, 1000000, 1000000, 10},
				{1000000, 1000000, 1000000, 20,      1000000, 60},
				{1000000, 1000000, 1000000, 1000000, 1000000, 1000000}
				};
bool vis[10] = {false};  // 是否已确定最短路径，
int dis[10];  // 最短路径长度 
			
void shortestPath(int s) {  // 起点s到其他点的最短路径 
	dis[s] = 0;  // 起点设置为0
	vis[s] = true;
	// 用起点指向的结点，更新dis
	for (int i = 0; i <= 5; i++) {
		if (mp[s][i] < dis[i]) {
			dis[i] = mp[s][i];
		}
	}
	
	while (true) {
		// dis中找出未确定最短路径的最小的点
		int min_i = 0, min_v = 1000000;
		for (int i = 0; i <= 5; i++) {
			if (!vis[i] && min_v > dis[i]) {
				min_i = i;
				min_v = dis[i];
			}
		}
		// vis全为true，最短路径全部找出 
		if (min_i == 0) {
			break;
		}
		vis[min_i] = true;
        // 更新min_i结点所指向的结点的最短路径数组，即dis
		for (int i = 0; i <= 5; i++) {
			if (!vis[i] && dis[i] > dis[min_i] + mp[min_i][i]) {
				dis[i] = dis[min_i] + mp[min_i][i];
			}
		}
	} 
} 

int main() {
  	// 初始化为无穷大 
	for (int i = 0; i <= 5; i++) {
		dis[i] = 1000000; 
	}
	shortestPath(0);
	
	for (int i = 0; i <= 5; i++) {
		cout << dis[i] << " ";
	}
	cout << endl;
	  
  	return 0;
}

代码：（邻接表）

#include <iostream>
#include <vector>
using namespace std;


struct Node {
	int v, len;
	Node(int v, int len) {
		this->v = v;
		this->len = len;
	}
};

// 邻接表 
vector<vector<Node> > mp(6, vector<Node>());

bool vis[10] = {false};  // 是否已确定最短路径，
int dis[10];  // 最短路径长度 

// 邻接表初始化 
void init_v() {
	mp[0].push_back(Node(2, 10));
	mp[0].push_back(Node(4, 30));
	mp[0].push_back(Node(5, 100));
	mp[2].push_back(Node(1, 5));
	mp[2].push_back(Node(3, 50));
	mp[3].push_back(Node(5, 10));
	mp[4].push_back(Node(3, 20));
	mp[4].push_back(Node(5, 60));
}
		
void shortestPath(int s) {  // 起点s到其他点的最短路径 
	dis[s] = 0;  // 起点设置为0
	vis[s] = true;
	
	for (int i = 0; i < mp[s].size(); i++) {
		if (mp[s][i].len < dis[mp[s][i].v]) {
			dis[mp[s][i].v] = mp[s][i].len;
		}
	}
	
	while (true) {
		// dis中找出未确定最短路径的最小的点
		int min_i = 0, min_v = 1000000;
		for (int i = 0; i <= 5; i++) {
			if (!vis[i] && min_v > dis[i]) {
				min_i = i;
				min_v = dis[i];
			}
		}
		// vis全为true，最短路径全部找出 
		if (min_i == 0) {
			break;
		}
		vis[min_i] = true;
        // 更新min_i结点所指向的结点的最短路径数组，即dis
		for (int i = 0; i < mp[min_i].size(); i++) {
			if (!vis[mp[min_i][i].v] && dis[mp[min_i][i].v] > dis[min_i] + mp[min_i][i].len) {
				dis[mp[min_i][i].v] = dis[min_i] + mp[min_i][i].len;
			}
		}
	} 
} 

int main() {
  	// 初始化为无穷大 
	for (int i = 0; i <= 5; i++) {
		dis[i] = 1000000; 
	}
	// 邻接表初始化 
	init_v();
	
	shortestPath(0);
	
	for (int i = 0; i <= 5; i++) {
		cout << dis[i] << " ";
	}
	cout << endl;
	for (int i = 0; i <= 5; i++) {
		cout << vis[i] << " ";
	}
	cout << endl;
	
  	return 0;
}

3.2.2 floyd（弗洛伊德算法）

路径图：

graph TD 0((0)) --10--> 2((2)) --5--> 1((1)) 0((0)) --30--> 4((4)) --20--> 3((3)) --10--> 5((5)) 2((2)) --50--> 3((3)) 0((0)) --100--> 5((5)) 4((4)) --60--> 5((5))

邻接矩阵：

\[\left[ \begin{matrix} 0 & ∞ & 10 & ∞ & 30 & 100 \\ ∞ & 0 & ∞ & ∞ & ∞ & ∞ \\ ∞ & 5 & 0 & 50 & ∞ & ∞ \\ ∞ & ∞ & ∞ & 0 & ∞ & 10 \\ ∞ & ∞ & ∞ & 20 & 0 & 60 \\ ∞ & ∞ & ∞ & ∞ & ∞ & 0 \\ \end{matrix} \right] \]

输出结果：

\[\left[ \begin{matrix} 0 & 15 & 10 & 50 & 30 & 60 \\ ∞ & 0 & ∞ & ∞ & ∞ & ∞ \\ ∞ & 5 & 0 & 50 & ∞ & 60 \\ ∞ & ∞ & ∞ & 0 & ∞ & 10 \\ ∞ & ∞ & ∞ & 20 & 0 & 30 \\ ∞ & ∞ & ∞ & ∞ & ∞ & 0 \\ \end{matrix} \right] \]

代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 205;
const int INF = 0x3f3f3f3f;

int dis[N][N];

void floyd() {
    for (int k = 0; k <= 5; k++)
        for (int i = 0; i <= 5; i++)
            for (int j = 0; j <= 5; j++)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}


int main() {
    // 输入数组 
	for (int i = 0; i <= 5; i++) {
    	for (int j = 0; j <= 5; j++) {
    		dis[i][j] = INF;
		}
	}
	for (int i = 0; i <= 5; i++) {
		dis[i][i] = 0;
	}
	dis[0][2] = 10;
	dis[0][4] = 30;
	dis[0][5] = 100;
	dis[2][1] = 5;
	dis[2][3] = 50;
	dis[3][5] = 10;
    dis[4][3] = 20;
    dis[4][5] = 60;
    // 输出数组 
    for (int i = 0; i <= 5; i++) {
        for (int j = 0; j <= 5; j++) {
            if (dis[i][j] == INF) cout << "INF" << "\t";
            else cout << dis[i][j] << "\t";
        }
        cout << endl;
    }
    cout << "============================================" << endl;
    // 更新最短路径 
    floyd();
    // 输出最终结果 
    for (int i = 0; i <= 5; i++) {
        for (int j = 0; j <= 5; j++) {
            if (dis[i][j] == INF) cout << "INF" << "\t";
            else cout << dis[i][j] << "\t";
        }
        cout << endl;
    }
    return 0;
}

标签：结点,遍历,int,NULL,---,--,数据结构
From： https://www.cnblogs.com/xiufanivan/p/17409997.html

相关文章

  • 数据结构
    数据结构堆1.插入一个元素：h[++size]=x；up(size)；2.求集合中当前最小值：h[1]；3.删除最小值：h[1]=h[size];size--;down(1);4.删除任意一个元素：h[k]=h[size];size--;up(k)ordown(k);5.修改任意一个元素：h[k]=x;up(k)ordown(k);[NOIP2004提高组]合并果子/[USA......
  • 优秀课件笔记之什么是数据结构
    1、本文所以内容来自著名高校课件和学生笔记（校园里面经常见到有人高价买笔记）2、任课教师不会提供参考文献，所以只能对作者表示感谢，如果引用了您的作品，可以用回复方式补充参考文献。3、我不对文章无关问题进行解答，文章内容也比较难，我也很难解答您遇到的问题，如果发现BUG可以用回复方......
  • 数据结构之栈
    Stack类型定义栈是限定仅在表尾进行插入和删除操作的线性表，又称为后进先出(lastinfirstout)的线性表(LIFO结构)，表尾称为栈顶，表头称为栈底，不含元素则称为空栈；抽象数据类型:InitStack(&S)//构造空栈SDestoryStack(&S)//销毁栈SClearStack(&S)......
  • Redis数据结构二之SDS和双向链表
    本文首发于公众号：Hunter后端原文链接：Redis数据结构二之SDS和双向链表这一篇笔记介绍一下SDS（simpledynamicstring）和双向链表。以下是本篇笔记目录：SDS常数复杂度获取字符串长度杜绝缓冲区溢出减少修改字符串带来的内存重分配次数二进制安全兼容C字符串函数双向链......
  • 架构师日记-从数据库发展历程到数据结构设计探析
    作者：京东零售刘慧卿一数据库发展史起初，数据的管理方式是文件系统，数据存储在文件中，数据管理和维护都由程序员完成。后来发展出树形结构和网状结构的数据库，但都存在着难以扩展和维护的问题。直到七十年代，关系数据库理论的提出，以表格形式组织数据，数据之间存在关联关系，具有了良好......
  • Redis数据结构一之对象的介绍及各版本对应实现
    本文首发于公众号：Hunter后端原文链接：Redis数据结构一之对象的介绍及各版本对应实现本篇笔记开始介绍Redis数据结构的底层实现。当我们被问到Redis中有什么数据结构，或者说数据类型，我们可能会说有字符串、列表、哈希、集合、有序集合。其实这几种数据类型在Redis中都由......
  • 数据结构与算法之一道题感受算法（算法入门）
    题目：给定N个整数的序列{A1,A2,....An}，求函数F（i，j）=Max{Ai+.....Aj }题目要求：这道题的目的是要求给定的一个整数序列中，它所含的连续子序列的最大值，比如现在我有一个整数序列{-3，2，3，-3，1}它的最大子序列很显然是 {2，3}第一种方法蛮力法（强制枚举）：我们从第一个整数开始遍历，依......
  • 个人推荐讲的非常好的数据结构免费[速成 速成 速成]视频了
    适用人群期末突击,二级+期末+考研+学习数据结构打基础,考前复习数据结构,巩固数据结构基础学习步骤：每一章，都会先讲基础，然后下一节就是配套习题讲解，坚持学完全部章即可拿捏期末,同时在课程最后提供一个新的整套题的讲解，进行巩固拔高好评截图：  几个小时就带你过了一边基础，讲了直......
  • 数据结构-二维数组内存结构
    二维数组内存结构  逻辑上是二维的,再分配内存的时候,也是给他分配一维的内存行优先存储 行优先存储，M行N列的b[i][j]的存储地址=基地址+(i*N+j)*sizeof(ElemType)列优先存储 M行N列b[i][j]的存储地址=基地址+(j*M+i)*sizeof(ElemType)......
  • chapter2-R的数据结构
    chapter2-R的数据结构R语言的数据结构分为5种类型：标量，向量，矩阵，列表，数据框向量-c()c()构建成的仅包含数值型、字符型、逻辑型数据的一维数组a<-c(1,2,3,4,5) ###数值型的向量b<-c('one','two','three')  ###字符型数据c<-c(T,F) ##逻辑型数据向量中元素的......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99