西工大数据结构实验NOJ参考代码和分析合集

这篇具有很好参考价值的文章主要介绍了西工大数据结构实验NOJ参考代码和分析合集。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

实验1.1 合并有序数组

西工大数据结构实验NOJ参考代码和分析合集

//001合并有序数组
#include <bits/stdc++.h>
#define MAXSIZE 20 //数组的最大长度为20
typedef struct	   //定义线性表的顺序存储结构
{
	int elem[MAXSIZE];
	int last = -1;
} SeqList;

void inputList(SeqList *la, SeqList *lb) //输入两个线性表
{
	int n, m;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &la->elem[i]);
		la->last++;
	}
	scanf("%d", &m);
	for (int i = 0; i < m; i++)
	{
		scanf("%d", &lb->elem[i]);
		lb->last++;
	}
}

void mergeList(SeqList *la, SeqList *lb, SeqList *lc) //合并数组
{
	int ia, ib, ic; //三个数分别指向三个线性表中正在进行数据处理的位置
	ia = 0;
	ib = 0;
	ic = 0;									 //从头开始处理
	while (ia <= la->last && ib <= lb->last) //两个数组都没有处理完数据时
	{
		if (la->elem[ia] <= lb->elem[ib]) //比较当前的两个数,将较小数放入lc中
		{
			lc->elem[ic] = la->elem[ia];
			ia++;
			ic++;
		}
		else
		{
			lc->elem[ic] = lb->elem[ib];
			ib++;
			ic++;
		}
	}
	while (ia <= la->last) //当有一个或两个数组完成了对所有数据的处理,则将没有完成数据处理的数组中剩余的元素依次放入lc中
	{
		lc->elem[ic] = la->elem[ia];
		ia++;
		ic++;
	}
	while (ib <= lb->last)
	{
		lc->elem[ic] = lb->elem[ib];
		ib++;
		ic++;
	}
	lc->last = la->last + lb->last + 1;
}

void printList(int length, SeqList *L) //打印线性表
{
	for (int i = 0; i < length; i++)
		printf("%d\n", L->elem[i]);
}

int main()
{
	SeqList la, lb, lc;
	inputList(&la, &lb);
	mergeList(&la, &lb, &lc);
	printList(la.last + lb.last + 2, &lc);
	return 0;
}

实验1.2 高精度计算PI值

西工大数据结构实验NOJ参考代码和分析合集

//002高精度计算PI值
#include <bits/stdc++.h>

typedef struct list //定义双向链表
{
    int data;
    struct list *next;
    struct list *prior;
} list;

list *Initlist() //初始化双向链表
{
    list *head;
    head = (list *)malloc(sizeof(list));
    head->next = head->prior = head;
    return head;
}
list *Creatlist(list *head) //建立链表
{
    int i;
    list *p;
    p = head;
    for (i = 0; i < 1000; i++)
    {
        list *q = (list *)malloc(sizeof(list));
        q->data = 0;
        q->prior = p;
        p->next = q;
        q->next = head; //第一次循环时此时的head和p是一个东西,目的为把链表画成一个圈
        head->prior = q;
        p = p->next;
    }
    return head;
}
int main()
{
    int n, i, a, b;
    scanf("%d", &n);
    list *number, *sum;
    list *p, *q, *x;
    number = Initlist();
    sum = Initlist();
    number = Creatlist(number);
    sum = Creatlist(sum);
    number->next->data = 2;    //第一位储存2,即2*R(1)=2
    sum->next->data = 2;       //与上同理
    a = 0, b = 0;              //分别是用来暂时存储进位和余数
    for (i = 1; i < 2500; i++) //循环两千次,确保精确度
    {
        p = number->prior;  //做大数乘法时从链表的后方开始
        while (p != number) //大于10则把10位的数字给b,个位数字放入data域中。
        {
            a = p->data * i + b;
            p->data = a % 10;
            b = a / 10;
            p = p->prior;
        }
        b = 0;              //清空b,为除法做准备
        p = p->next;        //大数除法从链表的前方开始
        while (p != number) //若计算出的数字为自然数,则直接放入data域;若等于0,或为小数,则要计算余数并给b。
        {
            a = p->data + b * 10;
            p->data = a / (2 * i + 1);
            b = a % (2 * i + 1);
            p = p->next;
        }
        b = 0;             //清零
        p = number->prior; //大数加法均从末尾开始
        q = sum->prior;
        while (p != number) //大于10进位,并储存个位数,进位数字赋给b。
        {
            a = p->data + q->data + b;
            q->data = a % 10;
            b = a / 10;
            p = p->prior;
            q = q->prior;
        }
    }
    printf("3.");
    x = sum->next->next; //从小数开始输出。
    for (i = 0; i < n; i++)
    {
        printf("%d", x->data);
        x = x->next;
    }
    return 0;
}

实验2.1 稀疏矩阵转置

西工大数据结构实验NOJ参考代码和分析合集

//003稀疏矩阵转置:一次定位快速转置法
#include <bits/stdc++.h>
#define MAXSIZE 2000

typedef struct triple
{				 //定义三元组
	int r, c, e; //三元组的坐标和元素值
} triple;

typedef struct matrix
{						  //定义稀疏矩阵
	int m, n, t;		  //稀疏矩阵的行列数和非零元素个数
	triple data[MAXSIZE]; //该稀疏矩阵中的三元组信息  从下标1开始
} matrix;

void initMatrixA(matrix *M) //初始化矩阵A
{
	scanf("%d%d", &M->m, &M->n); //输入矩阵信息
	M->t = 0;
	int temp_r, temp_c, temp_e;
	while (true) //输入三元组信息
	{
		scanf("%d", &temp_r);
		getchar();
		scanf("%d", &temp_c);
		getchar();
		scanf("%d", &temp_e);
		getchar();
		if (temp_r == 0 && temp_c == 0 && temp_e == 0)
		{
			break;
		}
		M->t++;
		M->data[M->t].r = temp_r;
		M->data[M->t].c = temp_c;
		M->data[M->t].e = temp_e;
	}
}

void initMatrixB(matrix *M, int m, int n, int t) //初始化B矩阵
{
	M->m = n;
	M->n = m;
	M->t = t;
}

void transposeMatrix(matrix A, matrix *B) //转置函数
{
	int num[MAXSIZE], pos[MAXSIZE]; //num存储A中每一列非零元素个数,pos记录不同列号对应的开始位置
	for (int col = 0; col < A.n; col++)
	{
		num[col] = 0;
	}
	for (int t = 1; t <= A.t; t++) //统计每一个列号对应的三元组个数
	{
		num[A.data[t].c]++;
	}
	pos[0] = 1;
	for (int col = 1; col < A.n; col++) //计算不同列号对应的开始位置
	{
		pos[col] = pos[col - 1] + num[col - 1];
	}
	for (int p = 1; p <= A.t; p++) //完成转置
	{
		int col = A.data[p].c;
		int q = pos[col];
		B->data[q].r = A.data[p].c;
		B->data[q].c = A.data[p].r;
		B->data[q].e = A.data[p].e;
		pos[col]++;
	}
}

void printResult(matrix M) //输出矩阵三元组
{
	for (int i = 1; i <= M.t; i++)
	{
		printf("%d %d %d\n", M.data[i].r, M.data[i].c, M.data[i].e);
	}
}

int main()
{
	matrix A, B; //定义待转置矩阵A和输出矩阵B
	initMatrixA(&A);
	initMatrixB(&B, A.m, A.n, A.t);
	transposeMatrix(A, &B);
	printResult(B);
	return 0;
}

实验2.2 稀疏矩阵加法,实现C=A+B

西工大数据结构实验NOJ参考代码和分析合集

//004 稀疏矩阵加法
#include <bits/stdc++.h>
#define MAXSIZE 20000
using namespace std;

typedef struct triple
{
	int x, y; //非零元素的坐标
	int e;	  //非零元素的值
} triple;

typedef struct matrix
{
	int row, col, t;	  //定义矩阵的长宽和非零元素个数
	triple data[MAXSIZE]; //存储矩阵的三元组
} matrix;

void inputTriple(matrix *A, matrix *B) //输入矩阵三元组
{
	for (int i = 0; i < A->t; i++)
	{
		scanf("%d%d%d", &A->data[i].x, &A->data[i].y, &A->data[i].e);
	}
	for (int i = 0; i < B->t; i++)
	{
		scanf("%d%d%d", &B->data[i].x, &B->data[i].y, &B->data[i].e);
	}
}

void addMatrix(matrix *A, matrix *B) //矩阵相加
{
	for (int i = 0; i < B->t; i++)
	{
		for (int j = 0; j < A->t; j++)
		{
			if (A->data[j].x == B->data[i].x && A->data[j].y == B->data[i].y) //相同位置有非零元素
			{
				A->data[j].e += B->data[i].e;
				B->data[i].x = -1; //标记已经用过的三元组
			}
			if (A->data[j].e == 0) //排除相加后为0的三元组
			{
				A->data[j].x = -1;
			}
		}
	}
	for (int i = 0; i < B->t; i++) //对于B中没有用过的三元组进行遍历
	{
		if (B->data[i].x == -1)
			continue;
		A->data[A->t].x = B->data[i].x;
		A->data[A->t].y = B->data[i].y;
		A->data[A->t].e = B->data[i].e; //新建A的三元组
		A->t++;
	}
}

void sortTriple(matrix *A) //对A中三元组按照行递增和行内列递增的顺序进行排列
{
	for (int i = 0; i < A->t; i++) //行列递增排序
	{
		for (int j = 0; j < A->t - i - 1; j++)
		{
			if (A->data[j].x > A->data[j + 1].x || (A->data[j].x == A->data[j + 1].x && A->data[j].y > A->data[j + 1].y))
			{
				triple t = A->data[j];
				A->data[j] = A->data[j + 1];
				A->data[j + 1] = t;
			}
		}
	}
}

void printMatrix(matrix A)
{
	for (int i = 0; i < A.t; i++)
	{
		if (A.data[i].x == -1)
			continue;
		printf("%d %d %d\n", A.data[i].x, A.data[i].y, A.data[i].e);
	}
}

int main()
{
	matrix A, B;
	scanf("%d%d%d%d", &A.row, &A.col, &A.t, &B.t);
	B.row = A.row;
	B.col = A.col;
	inputTriple(&A, &B);
	addMatrix(&A, &B);
	sortTriple(&A);
	printMatrix(A);
	return 0;
}

实验2.3 稀疏矩阵加法,用十字链表实现C=A+B

西工大数据结构实验NOJ参考代码和分析合集

//005 以十字链表为存储结构实现矩阵相加
#include <bits/stdc++.h>

typedef struct Node
{
    int x, y, e;
    Node *right, *down;
} Node;

typedef struct Matrix
{
    Node **rhead, **chead;
    int m, n, t;
} Matrix;

void initMatrix(Matrix *A, Matrix *B)
{
    scanf("%d%d%d%d", &A->m, &A->n, &A->t, &B->t);
    B->m = A->m;
    B->n = A->n;
}

void insertNode(Matrix *L, Node *P) //插入节点
{
    Node *temp, *N;
    N = (Node *)malloc(sizeof(Node)); //新建待插入节点
    N->y = P->y;
    N->x = P->x;
    N->e = P->e;                                            //装载节点信息
                                                            //插入行指针
    if (L->rhead[N->x] == NULL || L->rhead[N->x]->y > N->y) //需要插在头结点的情况
    {
        N->right = L->rhead[N->x];
        L->rhead[N->x] = N;
    }
    else
    {
        for (temp = L->rhead[N->x]; temp->right && temp->right->y < N->y; temp = temp->right)
            ; //不断向右遍历找到正确插入位置
        N->right = temp->right;
        temp->right = N;
    }
    //插入列指针
    if (L->chead[N->y] == NULL || L->chead[N->y]->x > N->x)
    {
        N->down = L->chead[N->y];
        L->chead[N->y] = N;
    }
    else
    {
        for (temp = L->chead[N->y]; temp->down && temp->down->x < N->x; temp = temp->down)
            ;
        N->down = temp->down;
        temp->down = N;
    }
}

void createMatrix(Matrix *M)
{
    Node *p, q;
    M->rhead = (Node **)malloc((M->m + 1) * sizeof(Node));
    M->chead = (Node **)malloc((M->n + 1) * sizeof(Node)); //创建行列指针表
    for (int i = 1; i <= M->m; i++)                        //初始化行列指针
        M->rhead[i] = NULL;
    for (int i = 1; i <= M->n; i++)
        M->chead[i] = NULL;
    for (int i = 1; i <= M->t; i++) //开辟节点并装在数据域和插入十字链表
    {
        p = (Node *)malloc(sizeof(Node));
        scanf("%d%d%d", &p->x, &p->y, &p->e);
        insertNode(M, p);
    }
}

void addMatrix(Matrix *A, Matrix *B)
{
    Node *p, *temp1, *temp2;
    for (int i = 1; i <= B->m; i++) //枚举每一行的头指针
    {
        if (B->rhead[i] == NULL) //如果B矩阵的该行没有元素,直接跳过,不需要执行加法
            continue;
        else
        {
            if (A->rhead[i] == NULL) //如果B该行不空,但A空,问题转化为将B中节点插入A中
            {
                temp2 = B->rhead[i];
                while (temp2)
                {
                    insertNode(A, temp2);
                    temp2 = temp2->right;
                }
            }
            else //如果A该行和B该行都不空
            {
                for (temp2 = B->rhead[i];; temp2 = temp2->right)
                {
                    for (temp1 = A->rhead[i];; temp1 = temp1->right) //对于该行某个B节点,枚举所有A节点
                    {
                        if (temp2->y == temp1->y) //如果两个节点位置重合,直接相加
                        {
                            temp1->e += temp2->e;
                            break;
                        }
                        //如果位置不重合
                        else if ((temp2->y < temp1->y) || temp1->right == NULL) //如果temp2的列已经大于temp1的列,说明temp2没有遇到相同列数的temp1
                        {                                                       //又或者已经遍历到尽头都没有相同列数
                            insertNode(A, temp2);                               //说明该列不可能存在相同位置了,直接插入
                            break;
                        }
                        else if (temp2->y > temp1->y && temp2->y < temp1->right->y) //如果temp2正好介于两者之间
                        {
                            insertNode(A, temp2);
                            break;
                        }
                    }
                    if (temp2->right == NULL)
                        break;
                }
            }
        }
    }
}

void printMatrix(Matrix *L)
{
    int i;
    Node *p;
    for (i = 1; i <= L->m; i++)
    {
        p = L->rhead[i];
        while (p != NULL)
        {
            if (p->e != 0)
                printf("%d %d %d\n", p->x, p->y, p->e);
            p = p->right;
        }
    }
}

int main()
{
    Matrix A, B;
    initMatrix(&A, &B);
    createMatrix(&A);
    createMatrix(&B);
    addMatrix(&A, &B);
    printMatrix(&A);
    return 0;
}
/*
3 4 3 2
1 1 1
1 3 1
2 2 2
1 2 1
2 2 3
*/

实验2.4 稀疏矩阵的乘法 

西工大数据结构实验NOJ参考代码和分析合集

//006 稀疏矩阵的乘法
#include <bits/stdc++.h>
#define MAXSIZE 2000

typedef struct triple
{				 //定义三元组
	int r, c, e; //三元组的坐标和元素值
} triple;

typedef struct matrix
{						  //定义稀疏矩阵
	int m, n, t;		  //稀疏矩阵的行列数和非零元素个数
	triple data[MAXSIZE]; //该稀疏矩阵中的三元组信息  从下标1开始
} matrix;

void initMatrix(matrix *M) //初始化稀疏矩阵
{
	scanf("%d", &M->m);
	getchar();
	scanf("%d", &M->n);
	while (true)
	{
		triple *p = (triple *)malloc(sizeof(triple));
		scanf("%d", &p->r);
		getchar();
		scanf("%d", &p->c);
		getchar();
		scanf("%d", &p->e);
		if (!p->c)
			break;
		M->t++;
		M->data[M->t].r = p->r;
		M->data[M->t].c = p->c;
		M->data[M->t].e = p->e;
	}
}

void multiplyMatrix(matrix A, matrix B, matrix *C)
{
	int temp = 0; //temp用于累加当前行列相乘所得到的结果
	for (int i = 1; i <= A.m; i++)
	{
		for (int j = 1; j <= B.n; j++) //外两层循环是分别遍历第一个矩阵的行号和第二个矩阵的列号,排列组合
		{
			for (int p = 1; p <= A.t; p++)
			{
				for (int q = 1; q <= B.t; q++) //内两层循环是遍历所有元素,找到能进行乘法的元素数对
				{
					if (A.data[p].r == i && B.data[q].c == j && A.data[p].c == B.data[q].r)
					{
						temp += A.data[p].e * B.data[q].e;
					}
				}
			}
			if (!temp)
				continue;
			else
			{
				C->t++;
				C->data[C->t].r = i;
				C->data[C->t].c = j;
				C->data[C->t].e = temp;
				temp = 0;
			}
		}
	}
}

void printMatrix(matrix M) //输出矩阵三元组
{
	for (int i = 1; i <= M.t; i++)
	{
		printf("%d %d %d\n", M.data[i].r, M.data[i].c, M.data[i].e);
	}
}

int main()
{
	matrix A, B, C;
	initMatrix(&A);
	initMatrix(&B);
	C.m = A.m;
	C.n = B.n;
	multiplyMatrix(A, B, &C);
	printMatrix(C);
	return 0;
}

实验3.1 哈夫曼编/译器 

西工大数据结构实验NOJ参考代码和分析合集

//007 哈夫曼编/译码器
#include <bits/stdc++.h>
#define N 100		//叶子结点最大数量
#define M 2 * N - 1 //所有结点最大数量

typedef struct HTNode //结点
{
	int weight;					//权重
	int parent, lchild, rchild; //双亲、左右孩子结点
	char data;					//字符
} HTNode, HT[M + 1];
HT ht;

typedef struct HCNode
{
	int bit[200]; //编码
	int start;	  //该编码的末尾位置
} HCNode, HC[100];
HC hc;

int str[1000] = {0};
int len = 0;

void select(int pos, int *x1, int *x2)
{
	int min = 100000;
	for (int i = 1; i <= pos; i++)
	{
		if (ht[i].weight < min && ht[i].parent == 0) //注意判断该节点必须没有双亲节点
		{
			min = ht[i].weight;
			*x1 = i;
		}
	}
	min = 100000;
	for (int i = 1; i <= pos; i++)
	{
		if (i == *x1)
			continue;
		if (ht[i].weight < min && ht[i].parent == 0) //注意判断该节点必须没有双亲节点
		{
			min = ht[i].weight;
			*x2 = i;
		}
	}
}

void initTree(int n)
{
	int x1, x2;
	for (int i = 1; i <= 2 * n - 1; i++) //对所有结点初始化
	{
		ht[i].weight = 0;
		ht[i].parent = 0;
		ht[i].lchild = 0;
		ht[i].rchild = 0;
	}
	for (int i = 1; i <= n; i++) //叶子结点的data域
	{
		getchar();
		scanf("%c", &ht[i].data);
	}
	for (int i = 1; i <= n; i++) //叶子结点的weight域
	{
		scanf("%d", &ht[i].weight);
	}
	for (int i = n; i < 2 * n - 1; i++)
	{
		select(i, &x1, &x2); //找到序号为i的结点之前的两个最小权重结点
		//两个最小权重结点组成一棵树,以i处的结点为根节点,直至循环结束所有结点组成一棵树
		ht[i + 1].weight = ht[x1].weight + ht[x2].weight;
		ht[x1].parent = i + 1;
		ht[x2].parent = i + 1;
		ht[i + 1].lchild = x1;
		ht[i + 1].rchild = x2;
	}
}

void encode(int n)
{
	for (int i = 1; i <= n; i++)
	{
		hc[i].start = n;	  //编码长度最多为n
		int c = i;			  //当前叶子结点序号
		int p = ht[c].parent; //叶子结点双亲序号
		while (p)
		{
			if (ht[p].lchild == c)
				hc[i].bit[hc[i].start] = 0;
			else
				hc[i].bit[hc[i].start] = 1;
			hc[i].start--;	  //准备录入下一位编码
			c = p;			  //上溯
			p = ht[c].parent; //上溯,直到while循环结束
		}
		hc[i].start++; //while循环中,start多退了一位。
	}
}

void printCode(int n)
{
	len = 0;
	char code[1000];
	scanf("%s", code);
	for (int i = 0; i < strlen(code); i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (code[i] == ht[j].data)
			{
				for (int k = hc[j].start; k <= n; k++)
				{
					printf("%d", hc[j].bit[k]);
					str[len] = hc[j].bit[k]; //存储待破解编码
					len++;
				}
			}
		}
	}
	printf("\n");
}

void decode(int n) //译码并输出
{
	int t;
	for (int i = 0; i < len;)
	{
		t = 2 * n - 1;								   //根节点
		while (ht[t].lchild != 0 && ht[t].rchild != 0) //当找到叶子节点时,退出循环
		{
			if (str[i] == 0)
				t = ht[t].lchild;
			else
				t = ht[t].rchild;
			i++;
		}
		printf("%c", ht[t].data);
	}
}

int main()
{
	int n;
	scanf("%d", &n);
	initTree(n);
	encode(n);
	printCode(n);
	decode(n);
	return 0;
}

实验4.1 求赋权图中一个结点到所有结点的最短路径的长度 

西工大数据结构实验NOJ参考代码和分析合集

//求赋权图中一个结点到所有结点的最短路径长度
#include <bits/stdc++.h>
#define MAXSIZE 105
#define INF 10000

int ans[MAXSIZE] = {0};

typedef struct Graph
{
	int data[MAXSIZE];
	int arc[MAXSIZE][MAXSIZE];
	int Vnum, Anum;
} Graph;

typedef struct dijkstra
{
	bool visited[MAXSIZE];
	int length[MAXSIZE];
} Dij;

void initGraph(Graph *G)
{
	scanf("%d", &G->Vnum);
	for (int i = 0; i < G->Vnum; i++)
	{
		for (int j = 0; j < G->Vnum; j++)
		{
			scanf("%d", &G->arc[i][j]);
		}
	}
}

void initDij(Graph *G, Dij *D)
{
	for (int i = 0; i < G->Vnum; i++)
	{
		D->visited[i] = 0;
		D->length[i] = INF;
	}
	D->visited[0] = 1;
	D->length[0] = 0;
	for (int i = 0; i < G->Vnum; i++)
	{
		if (G->arc[0][i] != 10000)
		{
			D->length[i] = G->arc[0][i];
		}
	}
}

int searchMinLengthV(Graph *G, Dij *D)
{
	int min = 10000;
	int r;
	for (int i = 0; i < G->Vnum; i++)
	{
		if (!D->visited[i] && D->length[i] < min)
		{
			min = D->length[i];
			r = i;
		}
	}
	D->visited[r] = true;
	return r;
}

bool judgeFinished(Graph *G, Dij *D)
{
	for (int i = 0; i < G->Vnum; i++)
	{
		if (!D->visited[i])
			return false;
	}
	return true;
}

int min(int a, int b)
{
	return a > b ? b : a;
}

void updateArcV(int V0, Graph *G, Dij *D)
{
	for (int i = 0; i < G->Vnum; i++)
	{
		if (G->arc[V0][i] != 10000 && !D->visited[i])
		{
			D->length[i] = min(D->length[i], D->length[V0] + G->arc[V0][i]);
		}
	}
}

void findMinPath(Graph *G, Dij *D)
{
	initDij(G, D);
	for (int i = 0; i < G->Vnum - 1; i++)
	{
		int t = searchMinLengthV(G, D);
		if (judgeFinished(G, D))
			return;
		updateArcV(t, G, D);
	}
}

void printPath(Graph *G, Dij *D)
{
	for (int i = 0; i < G->Vnum; i++)
	{
		printf("%d\n", D->length[i]);
	}
}

int main()
{
	Graph G;
	Dij D;
	initGraph(&G);
	int ans[MAXSIZE] = {0};
	findMinPath(&G, &D);
	printPath(&G, &D);
	return 0;
}
/*
6
0 1 4 10000 10000 10000
1 0 2 7 5 10000
4 2 0 10000 1 10000
10000 7 10000 0 3 2
10000 5 1 3 0 6
10000 10000 10000 2 6 0
*/

实验4.2 用迪杰斯特拉算法求赋权图中的最短路径 

西工大数据结构实验NOJ参考代码和分析合集

/*实验4.2:用迪杰斯特拉算法求赋权图中的最短路径
核心:
1.与上一题一样更新完成最短路径图
2.从目标结点向前寻找最短路径:按照结点的length递减的顺序;验证length-边长?=上一个结点length
*/
#include <bits/stdc++.h>
using namespace std;
#define MAXSIZE 105

typedef struct Graph
{
    int Vnum;
    int arc[MAXSIZE][MAXSIZE];
} Graph;

typedef struct Dij
{
    bool visited[MAXSIZE];
    int length[MAXSIZE];
} Dij;

typedef struct Stack
{
    int top;
    int data[MAXSIZE];
} Stack;

void push_stack(Stack *S, int e)
{
    S->top++;
    S->data[S->top] = e;
}

int pop_stack(Stack *S)
{
    S->top--;
    return S->data[S->top + 1];
}

void init(Graph *G, Dij *D, Stack *S)
{
    scanf("%d", &G->Vnum);
    for (int i = 0; i < G->Vnum; i++)
    {
        for (int j = 0; j < G->Vnum; j++)
        {
            scanf("%d", &G->arc[i][j]);
        }
    }
    for (int i = 0; i < G->Vnum; i++)
    {
        D->visited[i] = 0;
        D->length[i] = G->arc[0][i];
    }
    D->visited[0] = 1;
    S->top = -1;
}

bool is_finished(Graph *G, Dij *D)
{
    for (int i = 0; i < G->Vnum; i++)
    {
        if (!D->visited[i])
        {
            return false;
        }
    }
    return true;
}

int find_minlength_V(Graph *G, Dij *D)
{
    int min = 10005;
    int min_V;
    for (int i = 0; i < G->Vnum; i++)
    {
        if (!D->visited[i] && D->length[i] < min)
        {
            min = D->length[i];
            min_V = i;
        }
    }
    return min_V;
}

void update_arc_V(Graph *G, Dij *D, int v)
{
    D->visited[v] = true;
    for (int i = 0; i < G->Vnum; i++)
    {
        if (!D->visited[i] && D->length[v] + G->arc[i][v] < D->length[i])
        {
            D->length[i] = D->length[v] + G->arc[i][v];
        }
    }
}

void caculate_minlength_for_each_V(Graph *G, Dij *D)
{
    for (int i = 0; i < G->Vnum; i++)
    {
        if (is_finished(G, D))
        {
            return;
        }
        int v = find_minlength_V(G, D);
        update_arc_V(G, D, v);
    }
}

void find_path(Graph *G, Dij *D, Stack *S)
{
    int start, end;
    scanf("%d%d", &start, &end);
    push_stack(S, end);
    while (end != start)
    {
        for (int i = 0; i < G->Vnum; i++)
        {
            if (G->arc[i][end] != 10000 && D->length[i] < D->length[end] && D->length[i] + G->arc[i][end] == D->length[end])
            {
                push_stack(S, i);
                end = i;
            }
        }
    }
}

void print_path(Stack *S)
{
    while (S->top > -1)
    {
        printf("%d\n", pop_stack(S));
    }
}

int main()
{
    Graph G;
    Dij D;
    Stack S;
    init(&G, &D, &S);
    caculate_minlength_for_each_V(&G, &D);
    int path[MAXSIZE];
    find_path(&G, &D, &S);
    print_path(&S);
    return 0;
}

/*
4
0 2 10 10000
2 0 7 3
10 7 0 6
10000 3 6 0
0 2
*/

实验4.3 用弗洛伊德算法求赋权图的两点间的最短路径的长度

西工大数据结构实验NOJ参考代码和分析合集

//010用弗洛伊德算法求赋权图的两点间的最短路径长度
#include <bits/stdc++.h>
#define MAXSIZE 105
#define INF 10000
using namespace std;

typedef struct Graph
{
    int vnum;
    int arc[MAXSIZE][MAXSIZE];
    int path[MAXSIZE][MAXSIZE];
} Graph;

void init_Graph(Graph *G)
{
    scanf("%d", &G->vnum);
    for (int i = 0; i < G->vnum; i++)
    {
        for (int j = 0; j < G->vnum; j++)
        {
            scanf("%d", &G->arc[i][j]);
            G->path[i][j] = -1;
        }
    }
}

void floyd(Graph *G)
{
    for (int m = 0; m < G->vnum; m++)
        for (int a = 0; a < G->vnum; a++)
            for (int b = 0; b < G->vnum; b++)
            {
                if (G->arc[a][b] > G->arc[a][m] + G->arc[m][b])
                {
                    G->arc[a][b] = G->arc[a][m] + G->arc[m][b];
                    G->path[a][b] = m;
                }
            }
}

void print_result(Graph *G)
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", G->arc[a][b]);
    }
}

int main()
{
    Graph G;
    init_Graph(&G);
    floyd(&G);
    print_result(&G);
    return 0;
}

/*
4
0 2 10 10000
2 0 7 3
10 7 0 6
10000 3 6 0
2
0 2
3 0
*/

实验4.4 用弗洛伊德算法求赋权图中任意两点间的最短路径 

西工大数据结构实验NOJ参考代码和分析合集文章来源地址https://www.toymoban.com/news/detail-405112.html

//011用弗洛伊德算法求赋权图任意两点间的最短路径
#include <bits/stdc++.h>
#define MAXSIZE 105
#define INF 10000
using namespace std;

typedef struct Graph
{
    int vnum;
    int arc[MAXSIZE][MAXSIZE];
    int path[MAXSIZE][MAXSIZE];
} Graph;

typedef struct Stack
{
    int top;
    int data[MAXSIZE];
} Stack;

void init_Stack(Stack *S)
{
    S->top = -1;
}

void push_Stack(Stack *S, int e)
{
    S->top++;
    S->data[S->top] = e;
}

int pop_Stack(Stack *S)
{
    S->top--;
    return S->data[S->top + 1];
}

void init_Graph(Graph *G)
{
    scanf("%d", &G->vnum);
    for (int i = 0; i < G->vnum; i++)
    {
        for (int j = 0; j < G->vnum; j++)
        {
            scanf("%d", &G->arc[i][j]);
            G->path[i][j] = -1;
        }
    }
}

void floyd(Graph *G)
{
    for (int m = 0; m < G->vnum; m++)
        for (int a = 0; a < G->vnum; a++)
            for (int b = 0; b < G->vnum; b++)
            {
                if (G->arc[a][b] > G->arc[a][m] + G->arc[m][b])
                {
                    G->arc[a][b] = G->arc[a][m] + G->arc[m][b];
                    G->path[a][b] = m;
                }
            }
}

void find_path(Graph *G, Stack *S, int a, int b)
{
    push_Stack(S, b);
    if (G->path[a][b] == -1)
    {
        push_Stack(S, a);
        return;
    }
    else
    {
        find_path(G, S, a, G->path[a][b]);
    }
}

void print_result(Graph *G, Stack *S)
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        init_Stack(S);
        find_path(G, S, a, b);
        while (S->top > -1)
        {
            printf("%d\n", pop_Stack(S));
        }
    }
}

int main()
{
    Graph G;
    Stack S;
    init_Graph(&G);
    floyd(&G);
    print_result(&G, &S);
    return 0;
}

/*
4
0 2 10 10000
2 0 7 3
10 7 0 6
10000 3 6 0
2
0 2
3 0
*/

到了这里,关于西工大数据结构实验NOJ参考代码和分析合集的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 西工大--人工智能程序设计noj--前60道

    前言 截止到2022.12.10,本课程的noj61——90道,由于需要用到numpy、pandas、scipy等库,系统暂时没有这些库,无法评判,所以暂且分享一下前60道。前60道都已经AC(AC的截图我放在最后了)。有些题我小题大做了,程序写的很复杂,比如前10道;另外有些题的代码写的不太好,最

    2024年01月16日
    浏览(46)
  • 西工大 ASLP 实验室在 WeNet 中开源基于 CPPN 的神经网络热词增强语音识别方案

    语境偏置 (Contextual biasing)旨在将语境知识集成到语音识别(ASR)系统中,以提高在相关领域词汇(俗称“ 热词 ”)上的识别准确率。在许多ASR场景中,待识别语音中可能会包含训练数据中数量很少或完全没出现的短语,例如一些领域专有名词、用户通讯录中的人名等,这

    2024年02月07日
    浏览(35)
  • 数据结构实验——实验三--栈实验

    一、 实验任务 1.1 顺序栈实验任务 (1)利用顺序栈实现将10进制数转换为x进制数,2=x=36,除了阿拉伯数字字符,不够字符使用大写英文字符。要求键盘输入10进制数和转换的目标进制数。比如:37转换为20进制数为1H。 第一组数据:4 第二组数据:311 第三组数据:7254 第四组数据

    2023年04月09日
    浏览(31)
  • 数据结构实验———图实验

    一、实验内容 1.打印出图(网)的两种遍历序。 实验测试数据基本要求: 第一组数据: udg8.grp 第二组数据: udg115.grp 第三组数据: dg6.grp 第四组数据: f14.grp 2.求给定图中的边(或弧)的数目。    实验测试数据基本要求:第一组数据: udg8.grp 第二组数据: udg115.grp 第

    2024年02月08日
    浏览(43)
  • 【数据结构】实验六:图论

    采用邻接矩阵表示法创建无向图G ,依次输出各顶点的度。 输入格式: 输入第一行中给出2个整数i(0i≤10),j(j≥0),分别为图G的顶点数和边数。 输入第二行为顶点的信息,每个顶点只能用一个字符表示。 依次输入j行,每行输入一条边依附的顶点。 输出格式: 依次输出各顶点的

    2024年02月05日
    浏览(45)
  • 【数据结构】实验三:链表

    实验三链表 一、实验目的与要求 1 )熟悉链表的类型定义; 2 ) 熟悉链表的基本操作; 3 ) 灵活应用链表解决具体应用问题。 二、实验内容 1 ) 请设计一个单链表的存储结构,并实现单链表中基本运算算法。 编写程序 linklist.cpp 实现单链表的各种基本运算(假设单链表元

    2024年02月05日
    浏览(60)
  • 折半查找实验 (数据结构)

    一、实验目的 掌握折半查找算法的基本思想 掌握折半查找算法的实现方法 掌握折半查找的时间性能 掌握折半查找类的定义和使用 二、实验要求 熟悉C++语言编程 了解折半查找的原理 了解折半查找类的定义、应用 三、实验内容 1、问题描述 在一个有序序列中,折半查找一个

    2024年02月08日
    浏览(84)
  • 【数据结构】实验一:绪论

    实验一  绪论 一、实验目的与要求 1)熟悉C/C++语言(或其他编程语言)的集成开发环境; 2)通过本实验加深对算法时间复杂度的理解; 3)结合具体的问题分析算法时间复杂度。 二、实验内容 设计程序实现统计一个班的学生成绩(学生的人数可以设置3000、5000、8000、1000

    2024年02月15日
    浏览(38)
  • 数据结构 实验 家族族谱项目

    1.设计制作自己的家族族谱,确认问题;  家谱记载了一个家族的世系繁衍及重要人物事迹。使用树型结构对家谱进行管理,实现查看祖先和子孙个人信息,插入家族成员,删除家族成员的功能 2.分解问题,写出问题陈述,即把问题分解为各个比较小的问题,区分出紧急、严

    2024年02月04日
    浏览(47)
  • 《数据结构》实验报告七:查找

    1、掌握 查找表 、 动态查找表 、 静态查找表 和 平均查找长度 的概念。 2、掌握线性表中 顺序查找 和 折半查找 的方法。 3、学会 哈希函数 的构造方法, 处理冲突 的机制以及 哈希表的查找 。 说明以下概念 1、顺序查找:         顺序查找又叫 线性查找 ,是最基本的查

    2024年02月06日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包