学习通的作业
学习通的作业已存放在网盘(点击进入)
最好还是不要让太多人知道了，好东西独自享受喵。
实验
实验1 顺序表的基本操作
一、实验内容与要求
https://acm.zjnu.edu.cn/problem/3070/view
二、算法思路与流程
三、程序代码及运行结果
#include <bits/stdc++.h>
using namespace std;
#define OK 1
#define ERROR 0
#define LIST_SIZE 100
#define LISTINCREMENT 10
#define OVERFLOW -2
typedef int ElemType;
typedef int Status;
typedef struct{
ElemType *elem;
int length;
int listsize;
}Sqlist;
Status Initlist_sq(Sqlist &L){
L.elem = (ElemType *)malloc(LIST_SIZE*sizeof(ElemType));
if(!L.elem) return OVERFLOW;
L.length = 0;
L.listsize = LIST_SIZE;
return OK;
}
Status ClearList_sq(Sqlist &L){
if(L.length==0) return ERROR;
L.length = 0;
return OK;
}
int LocateElem_sq(Sqlist L, ElemType e){
int i =1;
int *p = L.elem;
while(i<=L.length && *p++!=e) ++i;
if(i<=L.length) return i;
else return 0;
}
ElemType LocateIndex_sq(Sqlist L, int i){
if(i<1||i>L.length) return ERROR;
return L.elem[i-1];
}
Status ListInsert_sq(Sqlist &L, int i, ElemType e){
if(i<1|| i>L.length+1) return ERROR;
if(L.length+1>L.listsize){
ElemType *newlist = (ElemType *)realloc(L.elem,(L.listsize +1) * sizeof(ElemType));
L.elem = newlist;
L.listsize++;
}
ElemType *q = &(L.elem[i-1]);
for(ElemType *p = &(L.elem[L.length-1]);p>=q;--p) *(p+1) = *p;
*q = e;
++L.length;
return OK;
}
Status ListDelete_sq(Sqlist &L, int i, ElemType &e){
if(i<1||i> L.length) return ERROR;
ElemType *p = &(L.elem[i-1]);
e = *p;
for(ElemType *q = p+1;q<=&(L.elem[L.length-1]);++q) *(p++) = *q;
--L.length;
return OK;
}
int main(){
Sqlist L;
Initlist_sq(L);
int n, m, index;
ElemType e, a, b;
cin >> n >> m;
for (int i=1;i<=n;i++){
cin >> e;
ListInsert_sq(L, i, e);
}
string s;
for (int i=1;i<=m;i++){
cin >> s;
if (s[0]=='I'){
cin >> a >> b;
ListInsert_sq(L, a, b);
}
else if (s[0]=='D'){
cin >> index;
ListDelete_sq(L, index, b);
cout << b << endl;
}
else if (s[0]=='G'){
cin >> index;
cout << LocateIndex_sq(L, index) << endl;
}
else if (s[0]=='L'){
cin >> b;
index = LocateElem_sq(L, b);
cout << index << endl;
}
else {
ClearList_sq(L);
}
}
return 0;
}
四、收获总结
实验2 链表及其多项式相加
一、实验内容与要求
https://acm.zjnu.edu.cn/problem/3049/view
二、算法思路与流程
三、程序代码及运行结果
/* 链表及其多项式相加 */
#include<stdio.h>
#include<stdlib.h>
#define OVERFLOW -2
#define OK 1
typedef int status;
typedef struct Lnode {
int exp, data;
struct Lnode* next;
} Lnode, * Linklist;
//链表建立函数：建立一个长度为n的链表
status listcreate_L(Linklist L, int n) {
Lnode* p = L;
for (int i = 0; i < n; i++) {
int val = 0, exp = 0;
Lnode* n = (Lnode*)malloc(sizeof(Lnode));
scanf("%d %d", &val, &exp);
n->data = val;
n->exp = exp;
n->next = NULL;
p->next = n;
p = p->next;
}
return 0;
}
//表达式相加函数：将La指向的表达式与Lb指向的表达式相加，赋给Lc
Linklist listadd_L(Linklist l1, Linklist l2) {
Linklist lc = (Linklist)malloc(sizeof(Lnode)); //创建头指针
lc->next = NULL;
Lnode *la = l1->next, * lb = l2->next, * ld, * le; //ld表示新链表中的节点，le表示创建的新节点
ld = lc;
while (la && lb) {
if (la->exp < lb->exp) {
ld->next = la; //la赋值给新节点
la = la->next;
ld = ld->next;
}
else if (la->exp > lb->exp) {
ld->next = lb; //lb赋值给新节点
lb = lb->next;
ld = ld->next;
}
else {
int sum = la->data + lb->data;
if (!sum) { la = la->next; lb = lb->next; continue; } //如果相加为0，跳过
le = (Linklist)malloc(sizeof(Lnode)); //相加不为0创建一个新节点，把值赋值给新节点，并指向新节点
le->next = NULL;
le->exp = la->exp;
le->data = sum;
ld->next = le;
la = la->next;
lb = lb->next;
ld = ld->next;
}
}
ld->next = la ? la : lb; //处理剩下的节点
return lc;
}
//输出链表
status listouput_L(Linklist L) {
Lnode* p = L->next;
int sum = 0, t = 1;
while (p != NULL) {
printf("%d %d\n", p->data, p->exp);
p = p->next;
}
return OK;
}
int main() {
Lnode* A = (Lnode*)malloc(sizeof(Lnode));
A->next = NULL;
int n = 0;
scanf("%d", &n);
listcreate_L(A, n);
Lnode* B = (Lnode*)malloc(sizeof(Lnode));
B->next = NULL;
int m = 0;
scanf("%d", &m);
listcreate_L(B, m);
Lnode* C = listadd_L(A, B);
listouput_L(C);
return 0;
return 0;
}
四、收获总结
实验3 实践栈结构-括号匹配算法
一、实验内容与要求
https://acm.zjnu.edu.cn/problem/3050/view
二、算法思路与流程
#include <bits/stdc++.h>
using namespace std;
#define OVERFLOW -2
#define UNDERFLOW -1
#define OK 1
typedef char DataType;
typedef struct snode{
DataType data;
struct snode *next;
}StackNode;
typedef struct {
StackNode *top;
}LinkStack;
void InitStack(LinkStack &S){
S.top = NULL;
}
bool StackEmpty(LinkStack &S){
return S.top == NULL;
}
void Push(LinkStack &S, DataType x){
StackNode * a=(StackNode*)malloc(sizeof(StackNode));
if(a==NULL) exit(OVERFLOW);
a->data=x;
a->next=S.top;
S.top = a;
}
DataType Pop(LinkStack &S){
if(S.top==NULL) return UNDERFLOW;
DataType p;
snode * q = S.top;
p = S.top->data;
q = S.top;
S.top = S.top->next;
free(q);
return p;
}
DataType GetTop(LinkStack &S){
if(S.top == NULL) return UNDERFLOW;
return S.top->data;
}
int Length(string s){
return s.length();
}
bool match(char a, char b){
if((a=='('&&b==')')||(a=='['&&b==']')){
return 1;
}
else return 0;
}
bool matching(string exp){
LinkStack S;
InitStack(S);
int state=1,i=0;
while(i<Length(exp) && state){
switch (exp[i])
{
case '(':
case '[':
Push(S,exp[i]);
i++;
break;
case ']':
case ')':
if(!StackEmpty(S) && match(GetTop(S), exp[i])) {
Pop(S);
i++;
}
else state =0;
break;
}
}
if(state==1 && StackEmpty(S))return OK;
else return 0;
}
int main(){
string exp;
cin >> exp;
if (matching(exp)) printf("yes\n");
else printf("no\n");
return 0;
}
三、程序代码及运行结果
四、收获总结
实验4 实践栈结构-编译器中的表达式求值问题
一、实验内容与要求
https://acm.zjnu.edu.cn/problem/3052/view
二、算法思路与流程
#include <cstdio>
#include <iostream>
#include <cstring>
#define OVERFLOW -2
#define UNDERFLOW -1
#define OK 1
using namespace std;
typedef char Dataoptr;
typedef int Dataopnd;
typedef struct stdacknode_optr{
Dataoptr data;
struct stdacknode_optr*next;
} Stacknode_optr;
typedef struct {
Stacknode_optr *top;
Stacknode_optr *base;
} Stack_optr;
typedef struct stdacknode_opnd{
Dataopnd data;
struct stdacknode_opnd*next;
} Stacknode_opnd;
typedef struct {
Stacknode_opnd *top;
Stacknode_opnd *base;
} Stack_opnd;
void InitStack_optr(Stack_optr &S) {
S.top == NULL;
}
void Push_optr(Stack_optr &S, Dataoptr x) {
Stacknode_optr *p = (Stacknode_optr *)malloc(sizeof(Stacknode_optr));
p->data = x;
p->next = S.top;
S.top = p;
}
Dataoptr Pop_optr(Stack_optr &S) {
if (S.top == NULL) {
return UNDERFLOW;
}
Dataoptr x;
Stacknode_optr *p = S.top;
x = p->data;
S.top = p->next;
free(p);
return x;
}
Dataoptr GetTopnode_optr(Stack_optr &S){
return S.top->data;
}
Dataopnd GetTopnode_opnd(Stack_opnd &S){
return S.top->data;
}
void InitStack_opnd(Stack_opnd &S) {
S.top == NULL;
}
void Push_opnd(Stack_opnd &S, Dataopnd x) {
Stacknode_opnd *p = (Stacknode_opnd *)malloc(sizeof(Stacknode_opnd));
p->data = x;
p->next = S.top;
S.top = p;
}
Dataopnd Pop_opnd(Stack_opnd &S) {
if (S.top == NULL) {
return UNDERFLOW;
}
Dataopnd x;
Stacknode_opnd *p = S.top;
x = p->data;
S.top = p->next;
free(p);
return x;
}
bool in (char c) {
return c<='9'&&c>='0';
}
Dataopnd Operate(Dataopnd a,Dataoptr op, Dataopnd b) {
switch (op) {
case '+':return a+b;
case '-':return a-b;
case '*':return a*b;
case '/':return a/b;
}
return 0;
}
char Precede(char x1, char x2)
{
if((x1=='('&&x2==')')|| x1=='#'&&x2=='#') return '=';
else if((x1=='('||x1=='#'||x2=='(')||(x1=='+'||x1=='-')&&(x2=='*'||x2=='/')) return '<';
else return '>';
}
int EvaluateExpression(char *s)
{
Stack_optr OPTR;
Stack_opnd OPND;
int idx = 0;
int a, b;
char op;
InitStack_optr(OPTR);
InitStack_opnd(OPND);
Push_optr(OPTR, '#');
while (s[idx] != '#' || GetTopnode_optr(OPTR) != '#')
{
if (in(s[idx]))
{
Push_opnd(OPND, s[idx] - '0');
printf("%d ", s[idx] - '0');
idx++;
}
else
{
switch (Precede(GetTopnode_optr(OPTR), s[idx]))
{
case '>':
op = Pop_optr(OPTR);
b = Pop_opnd(OPND);
a = Pop_opnd(OPND);
printf("%c ", op);
Push_opnd(OPND, Operate(a, op ,b));
break;
case '=':
Pop_optr(OPTR);
idx++;
break;
case '<':
Push_optr(OPTR, s[idx++]);
}
}
}
return GetTopnode_opnd(OPND);
}
int main() {
char str[2000] = {0};
scanf("%s", str);
int num;
str[strlen(str)] = '#';
num = EvaluateExpression(str);
printf("\n%d\n", num);
return 0;
}
三、程序代码及运行结果
四、收获总结
实验5 字符串的模式匹配(KMP)
一、实验内容与要求
https://acm.zjnu.edu.cn/problem/3053/view
二、算法思路与流程
#include <stdio.h>
#include <string.h>
char s[100005];
char t[100005];
int next[100005];
void get_next(char *t)
{
int i = 0, j = -1;
next[0] = -1;
int tlen = strlen(t);
while (i < tlen)
{
if (j == -1 || t[i] == t[j]){
++i;
++j;
next[i] = j;
}
else j = next[j];
}
}
int kmp(char *s, char *t)
{
int i = 0, j = 0;
int slen = strlen(s);
int tlen = strlen(t);
while (i < slen && j < tlen)
{
if (j == -1 || s[i] == t[j])
{
++i;
++j;
}
else j = next[j];
}
if (j >= tlen) return 1;
else return 0;
}
int main(){
gets(s);
int count=0;
scanf("%d",&count);
getchar(); //读取后面的换行符防止下次对gets读取造成干扰
for(int i =0;i<count;i++){
gets(t);
get_next(t);
int flag = kmp(s,t);
if(flag==1) printf("yes\n");
else printf("no\n");
}
return 0;
}
三、程序代码及运行结果
四、收获总结
实验6 稀疏矩阵的建立与转置
一、实验内容与要求
https://acm.zjnu.edu.cn/problem/3054/view
二、算法思路与流程
#include <cstdio>
using namespace std;
#define MAXSIZE 12500
#define OK 1
typedef int ElemType;
typedef int Status;
typedef struct {
int i,j;
ElemType e;
} Triple;
typedef struct {
Triple data[MAXSIZE+1];
int mu,nu,tu;
} TSMatrix;
Status TransposeSMatrix(TSMatrix M, TSMatrix &T){
int p, q, col;
T.mu = M.nu; T.nu = M.mu; T.tu = M.tu;
if(T.tu){
q = 1;
for (col = 0;col<=M.nu;col++){ // 这里col从0开始
for (p = 1;p<=M.tu;p++){
if(M.data[p].j == col){
T.data[q].i = M.data[p].j;
T.data[q].j = M.data[p].i;
T.data[q].e = M.data[p].e;
q++;
}
}
}
}
return OK;
}
void printMatrix(TSMatrix M){
int count = 1;
for (int i =0;i<M.mu;i++){
for (int j=0;j<M.nu;j++){
if(M.data[count].i ==i&&M.data[count].j==j){
printf("%5d", M.data[count].e);
count++;
}
else{
printf("%5d", 0);
}
}
printf("\n");
}
}
int main(){
TSMatrix A;
TSMatrix B;
scanf("%d %d %d", &A.mu, &A.nu, &A.tu);
for (int i =1;i<=A.tu;i++){
scanf("%d %d %d", &A.data[i].i, &A.data[i].j, &A.data[i].e);
}
TransposeSMatrix(A, B);
printMatrix(A);
printf("\n");
printMatrix(B);
return 0;
}
三、程序代码及运行结果
四、收获总结
实验7 二叉树的创建及遍历
一、实验内容与要求
https://acm.zjnu.edu.cn/problem/3055/view
二、算法思路与流程
#include <cstdlib>
#include <cstdio>
using namespace std;
#define ERROR 0
#define OK 1
#define OVERFLOW -2
#define MAX 100000000
typedef int status;
typedef struct Binode {
char data;
int deep;
Binode* lchild;
Binode* rchild;
}Binode, * BiTree;
status depthbitree(BiTree& T);
status prebitree(BiTree T) {
if (T) {
depthbitree(T);
printf("%c(%d)", T->data, T->deep);
prebitree(T->lchild);
prebitree(T->rchild);
}
return OK;
}
status depthbitree(BiTree& T) {
if(T)
{
if (T->lchild != NULL) T->lchild->deep = T->deep +1;
if (T->rchild != NULL) T->rchild->deep = T->deep +1;
depthbitree(T->lchild);
depthbitree(T->rchild);
}
return OK;
}
status creabitree(BiTree& T) {
char get;
scanf("%c", &get);
if (get == '#' || get == '\n') T = NULL;
else {
if (!(T = (Binode*)malloc(sizeof(Binode)))) exit(OVERFLOW);
T->data = get;
T->deep = 1;
creabitree(T->lchild);
creabitree(T->rchild);
}
return OK;
}
int main() {
BiTree T;
creabitree(T);
depthbitree(T);
prebitree(T);
return 0;
}
三、程序代码及运行结果
四、收获总结
实验8 树的建立与遍历
一、实验内容与要求
https://acm.zjnu.edu.cn/problem/3093/view
二、算法思路与流程
#include<stdio.h>
#include <stdlib.h>
#include<string>
#define ERROR 0
#define OK 1
#define OVERFLOW -2
typedef int Elem;
typedef struct CSNode {
Elem data;
struct CSNode* firstchild, * nextsibling;
} CSNode, * CSTree;
typedef CSNode Qelemtype;
typedef int status;
typedef struct QNode {
Qelemtype* Qdata;
struct QNode* next;
}Qnode, * QueuePtr;
typedef struct {
QueuePtr front;
QueuePtr rear;
} LinkQueue;
status InitQueue(LinkQueue& Q) {
Q.front = Q.rear = (QueuePtr)malloc(sizeof(Qnode));
if (!Q.front) exit(EOVERFLOW);
Q.front->next = NULL;
return OK;
}
status EnQueue(LinkQueue& Q, Qelemtype *e)
{
QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
if (!p) exit(EOVERFLOW);
p->Qdata = e; p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}
Qelemtype* DeQueue(LinkQueue& Q) {
Qelemtype* e;
if (Q.front == Q.rear) return(ERROR);
QueuePtr p = Q.front->next;
e = p->Qdata;
Q.front->next = p->next;
if (Q.rear == p) Q.rear = Q.front;
free(p);
return e;
}
Qelemtype* GetHead(LinkQueue& Q) {
Qelemtype* e;
if (Q.front == Q.rear) return ERROR;
e = Q.front->next->Qdata;
return e;
}
CSTree GetTreeNode(char ch){
CSTree p = (CSTree)malloc(sizeof(CSNode));
p->data = ch;
p->firstchild = NULL;
p->nextsibling = NULL;
return p;
}
void CreatTree(CSTree& T){
T = NULL;
CSTree r =NULL;
char ch = NULL, fa = NULL;
int i = 0;
LinkQueue Q;
InitQueue(Q);
scanf("%d", &i); getchar();
for (int j =0; j<i; j++)
{
CSTree s = NULL, p;
scanf("%c %c", & fa, &ch); getchar();
p = GetTreeNode(ch);
EnQueue(Q, p);
if (fa == '#') T = p;
else {
s = GetHead(Q);
while (s->data != fa) {
s = DeQueue(Q); s =GetHead(Q);
}
if (!(s->firstchild)){
s->firstchild = p; r = p;
}
else { r->nextsibling = p; r = p; }
}
}
}
int TreeDepth(CSTree T) {
int h1, h2;
if (!T) return 0;
else {
h1 = TreeDepth(T->firstchild);
h2 = TreeDepth(T->nextsibling);
return(h1 + 1 > h2 ? h1 + 1 : h2);
}
}
void getin(CSNode* p,int &count){
if (p){
if (!p->firstchild) count++;
getin(p->firstchild,count);
getin(p->nextsibling,count);
}
}
status pretraverse(CSTree T) {
if (T) {
printf("%c ", T->data);
pretraverse(T->firstchild);
pretraverse(T->nextsibling);
}
return OK;
}
status intraverse(CSTree T) {
if (T) {
intraverse(T->firstchild);
printf("%c ", T->data);
intraverse(T->nextsibling);
}
return OK;
}
int main() {
CSTree T;
CreatTree(T);
printf("PreOrder: ");
pretraverse(T);
printf("\n");
printf("PostOrder: ");
intraverse(T);
printf("\n");
printf("Depth: %d\n", TreeDepth(T));
int count = 0;
getin(T, count);
printf("Number of leaves: %d\n", count);
return 0;
}
三、程序代码及运行结果
四、收获总结
实验9 图的建立与遍历（多城市间遍历）
一、实验内容与要求
https://acm.zjnu.edu.cn/problem/1416/view
二、算法思路与流程
三、程序代码及运行结果
#include <stdio.h>
#include <stdlib.h>
#define ERROR 0
#define OK 1
#define OVERFLOW -2
#define MAX_VERTEX_N 80
typedef int VRType;
typedef int InfoType;
typedef int VerterType;
typedef struct ArcCell {
VRType adj;
}ArcCell, AdjMatrix[MAX_VERTEX_N][MAX_VERTEX_N];
typedef struct Qnode {
VerterType data;
struct Qnode* next;
};
typedef struct Queue{
Qnode* front;
Qnode* rear;
} Queue;
typedef struct {
VerterType vexs[MAX_VERTEX_N];
AdjMatrix arcx;
int vexnum, arcnum;
}MGraph;
bool visited[MAX_VERTEX_N] = {false};
int InitQueue(Queue& Q) {
Q.front = Q.rear = (Qnode*)malloc(sizeof(Qnode));
if (!Q.front) exit(OVERFLOW);
Q.front->next = NULL;
return OK;
}
int InQueue(Queue& Q, VerterType a) {
Qnode* p = (Qnode*)malloc(sizeof(Qnode));
if (!p) exit(OVERFLOW);
p->data = a;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}
bool QueueEmpty(Queue& Q) {
return Q.front == Q.rear;
}
int DeQueue(Queue& Q, VerterType& a) {
if (Q.front == Q.rear) return ERROR;
Qnode* p = Q.front->next;
a = p->data;
Q.front->next = p->next;
if (Q.rear == p) Q.rear = Q.front;
free(p);
return OK;
}
int InitGraph(MGraph &M) {
scanf("%d %d", &M.vexnum, &M.arcnum); getchar();
if (M.vexnum) {
for (int i = 0; i < M.vexnum; i++) {
M.vexs[i] = i;
}
}
for(int i =0;i<MAX_VERTEX_N;i++){
for(int j =0;j<MAX_VERTEX_N;j++){
M.arcx[i][j].adj = 0;
}
}
if (M.arcnum) {
for (int i = 0; i < M.arcnum; i++) {
int a, b;
scanf("%d %d", &a, &b); getchar();
M.arcx[a][b].adj = 1;
M.arcx[b][a].adj = 1;
}
}
return OK;
}
void DFS(MGraph M, int v) {
visited[v] = true;
printf("%d ", M.vexs[v]);
for (int i = 0; i < M.vexnum; i++) {
if (M.arcx[v][i].adj == 1 && !visited[i]) {
DFS(M, i);
}
}
}
void DFSTraverse(MGraph M){
for(int i =0;i<MAX_VERTEX_N;i++) visited[i] = false;
for (int i = 0; i < M.vexnum; i++) {
if (!visited[i]) {
DFS(M, i);
}
}
}
void BFS(MGraph M, Queue& Q) {
for (int i = 0; i < M.vexnum; i++) {
if (!visited[i]) {
visited[i] = true;
printf("%d ", M.vexs[i]);
InQueue(Q, i);
while (!QueueEmpty(Q)) {
VerterType u;
DeQueue(Q, u);
for (int j = 0; j < M.vexnum; j++) {
if (M.arcx[u][j].adj && !visited[j]) {
visited[j] = true;
printf("%d ", M.vexs[j]);
InQueue(Q, j);
}
}
}
}
}
}
void BFSTraverse(MGraph M){
Queue Q;
InitQueue(Q);
for(int i =0;i<MAX_VERTEX_N;i++) visited[i] = false;
BFS(M,Q);
}
int main() {
MGraph M;
InitGraph(M);
DFSTraverse(M);
printf("\n");
BFSTraverse(M);
return 0;
}
四、收获总结
实验10 最小生成树prim算法
一、实验内容与要求
https://acm.zjnu.edu.cn/problem/1408/view
二、算法思路与流程
三、程序代码及运行结果
#include <stdio.h>
using namespace std;
#define MAX_VERTEX_N 105
#define INF 1000000007
typedef int VRType;
typedef int VertexType;
typedef int status;
typedef struct ArcCell {
VRType adj;
} ArcCell, AdjMatrix[MAX_VERTEX_N][MAX_VERTEX_N];
typedef struct MGraph {
VertexType vexs[MAX_VERTEX_N];
AdjMatrix arcs;
int vexnum, arcnum;
} MGraph;
struct Closedge {
VertexType adjvex;
VRType lowcost;
} closedge[MAX_VERTEX_N];
void CreatGraph(MGraph& G) {
scanf("%d", &G.vexnum);
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
scanf("%d", &G.arcs[i][j].adj);
}
}
}
int minimum(Closedge closedge[], MGraph G) {
int u = 0, min = INF;
for (int i = 0; i < G.vexnum; i++) {
if (closedge[i].lowcost != -1 && min > closedge[i].lowcost) {
min = closedge[i].lowcost;
u = i;
}
}
return u;
}
int Prim(MGraph G) {
int u = 0, res = 0;
for (int i = 0; i < G.vexnum; i++) closedge[i].lowcost = G.arcs[u][i].adj;
closedge[u].lowcost = -1;
for (int i = 1; i < G.vexnum; i++) {
u = minimum(closedge, G);
res += closedge[u].lowcost;
closedge[u].lowcost = -1;
for (int j = 0; j < G.vexnum; j++) {
if (closedge[j].lowcost > G.arcs[u][j].adj)
closedge[j].lowcost = G.arcs[u][j].adj;
}
}
return res;
}
int main() {
MGraph G;
CreatGraph(G);
printf("%d\n", Prim(G));
return 0;
}
四、收获总结
实验11 城市畅通工程的问题
一、实验内容与要求
https://acm.zjnu.edu.cn/problem/1414/view
二、算法思路与流程
三、程序代码及运行结果
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct edge
{
int u, v, w;
} edge[4005];
int father[4005];
int Find(int l)
{
if (father[l] != l){
return father[l] = Find(father[l]);
}
return l;
}
void Union(int p, int q)
{
father[q] = p;
}
void swap(int &a, int &b)
{
int t = a;
a = b;
b = t;
}
void Sort(struct edge edge[], int m)
{
for (int i = m - 1; i > 0; i--){
for (int j = 0; j < i; j++){
if (edge[j].w > edge[j + 1].w){
swap(edge[j].u, edge[j + 1].u);
swap(edge[j].v, edge[j + 1].v);
swap(edge[j].w, edge[j + 1].w);
}
}
}
}
void Initialize(int n){
for (int i = 1; i <= n; i++){
father[i] = i;
}
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++){
scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
}
Initialize(n);
Sort(edge, m);
int sum = 0, j = 0, k = 0;
while (k < n - 1){
int p = Find(edge[j].u);
int q = Find(edge[j].v);
if (p != q){
Union(p, q);
sum += edge[j].w;
k++;
}
j++;
}
printf("%d\n", sum);
return 0;
}
四、收获总结
实验12 单源最短路径
一、实验内容与要求
https://acm.zjnu.edu.cn/problem/3933/view
二、算法思路与流程
三、程序代码及运行结果
#include <iostream>
using namespace std;
#define MAX_VERTEX_N 3005
#define MAX_EDGE_M 10005
#define INF 1000000007
typedef int VRType;
typedef int VertexType;
typedef int status;
int s, t;
int dist[MAX_VERTEX_N];
bool visited[MAX_VERTEX_N];
typedef struct ArcCell {
VRType adj;
} ArcCell, AdjMatrix[MAX_VERTEX_N][MAX_VERTEX_N];
typedef struct MGraph {
VertexType vexs[MAX_VERTEX_N];
AdjMatrix arcs;
int vexnum, arcnum;
} MGraph;
MGraph G;
void CreatGraph() {
int u, v, x;
cin >> G.vexnum >> G.arcnum >> s >> t;
for (int i = 0; i < G.vexnum; i++) {
G.vexs[i] = i;
}
for (int i = 0; i <= G.vexnum; i++) {
for (int j = 0; j <= G.vexnum; j++) {
G.arcs[i][j].adj = INF;
}
}
for (int i = 0; i < G.arcnum; i++) {
cin >> u >> v >> x;
if (G.arcs[u][v].adj > x) {
G.arcs[v][u].adj = G.arcs[u][v].adj = x;
}
}
}
void Dijkstra() {
for (int i = 1; i <= G.vexnum; i++) {
dist[i] = G.arcs[s][i].adj;
visited[i] = false;
}
for (int i = 0; i <= G.vexnum; i++) {
int min = INF, u=0, j;
for (j = 1; j <= G.vexnum; j++) {
if (!visited[j] && dist[j] < min) {
min = dist[j];
u = j;
}
}
visited[u] = true;
for (int j = 1; j <= G.vexnum; j++) {
if (!visited[j] && dist[u] + G.arcs[u][j].adj < dist[j]) {
dist[j] = dist[u] + G.arcs[u][j].adj;
}
}
}
cout << dist[t] << endl;
}
int main() {
CreatGraph();
Dijkstra();
return 0;
}
四、收获总结
实验13 拓扑排序
一、实验内容与要求
https://acm.zjnu.edu.cn/problem/1413/view
二、算法思路与流程
三、程序代码及运行结果
#include <stdio.h>
#include <string.h>
#define maxex 200
// 定义图的结构体
typedef struct {
int vexnum, arcnum;
int arcs[maxex][maxex];
} MGraph;
MGraph g;
int in[maxex], visit[maxex];
// 统计入度
void countIndegree() {
memset(in, 0, sizeof(in));
for (int i = 1; i <= g.vexnum; i++) {
for (int j = 1; j <= g.vexnum; j++) {
if (g.arcs[j][i])
in[i]++;
}
}
}
// 拓扑排序
bool topoSort() {
int base = 0, top = 0;
int stack[maxex];
countIndegree();
// 入度为 0 的顶点入栈（倒序）
for (int i = g.vexnum; i >= 1; i--) {
if (!in[i])
stack[top++] = i;
}
int count = 0;
while (top != base) {
int v = stack[--top];
visit[count++] = v;
for (int u = 1; u <= g.vexnum; u++) {
if (g.arcs[v][u]) {
in[u]--;
if (!in[u])
stack[top++] = u;
}
}
// 对栈中元素进行降序排序（每次调整）
for (int i = 0; i < top; i++) {
int k = i;
for (int j = i + 1; j < top; j++) {
if (stack[k] < stack[j])
k = j;
}
if (k != i) {
int t = stack[i];
stack[i] = stack[k];
stack[k] = t;
}
}
}
// 检查是否存在环
if (count == g.vexnum) {
printf("%d", visit[0]);
for (int i = 1; i < g.vexnum; i++)
printf(" %d", visit[i]);
}
else {
printf("no");
}
return true;
}
int main() {
// 读入顶点数和边数
scanf("%d%d", &g.vexnum, &g.arcnum);
// 初始化邻接矩阵
for (int i = 1; i <= g.vexnum; i++) {
for (int j = 1; j <= g.vexnum; j++) {
g.arcs[i][j] = 0;
}
}
// 读入边的信息，并构建邻接矩阵
for (int i = 1; i <= g.arcnum; i++) {
int u, v;
scanf("%d%d", &u, &v);
g.arcs[u][v] = 1;
}
// 进行拓扑排序
topoSort();
return 0;
}
四、收获总结
实验14 二叉搜索树的构建与应用
一、实验内容与要求
https://acm.zjnu.edu.cn/problem/3065/view
二、算法思路与流程
三、程序代码及运行结果
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define TRUE 1
#define FALSE 0
typedef struct BiTNode{
int data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
int SearchBST(BiTree T, int e, BiTree f, BiTree &p){
if(T){
if(e==T->data) {
p = T;
return TRUE;
}
else if(e>T->data) return SearchBST(T->rchild,e,T,p);
else return SearchBST(T->lchild,e,T,p);
}
else{
p=f;
return FALSE;
}
}
int InsertBST(BiTree &T, int e){
BiTree f=NULL,p=NULL;
if(!SearchBST(T,e,f,p)){
BiTree s = new BiTNode;
s->data = e;
s->lchild = s->rchild =NULL;
if(!p){
T=s;
}
else{
if(e > p->data) p->rchild = s;
else p->lchild =s;
}
return TRUE;
}
return FALSE;
}
int CreateBST(BiTree &T){
int n, x, cnt=0;
scanf("%d", &n);
for (int i=0;i<n;i++){
scanf("%d", &x);
if (InsertBST(T, x)) cnt++;
}
return cnt;
}
void PreOrder(BiTree T){
if(T){
cout << T->data << " ";
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
int main(){
BiTree T = NULL;
cout << CreateBST(T) <<endl;
PreOrder(T);
}
四、收获总结
实验15 对大量数据快速排序
一、实验内容与要求
https://acm.zjnu.edu.cn/problem/1479/view
二、算法思路与流程
三、程序代码及运行结果
四、收获总结
实验16 堆的建立和维护
一、实验内容与要求
https://acm.zjnu.edu.cn/problem/3067/view
二、算法思路与流程
三、程序代码及运行结果
四、收获总结
作业
两个有序链表的合并
#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef struct Lnode
{
ElemType data;
struct Lnode* next;
} Lnode, * linkLnode;
int h_insert_Lnode(Lnode* H, ElemType m) {
Lnode* p = H;
for (int i = 0; i < m; i++) {
ElemType val = 0;
Lnode* n = (Lnode*)malloc(sizeof(Lnode));
scanf("%d", &val);
n->data = val;
n->next = NULL;
p->next = n;
p = p->next;
}
return 0;
}
void print_Lnode(Lnode* h) {
Lnode* p = h->next;
int sum = 0, t = 1;
while (p != NULL) {
printf("%d ", p->data);
if (t % 2 == 1)sum += p->data;
t++;
p = p->next;
}
printf("\n");
printf("%d\n", sum);
}
struct Lnode* mergeTwoLists(struct Lnode* l1, struct Lnode* l2) {
Lnode* la = l1->next, * lb = l2->next, * lc, * ld;
lc = (Lnode*)malloc(sizeof(Lnode));
ld = lc;
while (la&& lb) {
if (la->data <= lb->data) {
lc->next = la;
la = la->next;
}
else {
lc->next = lb;
lb = lb->next;
}
lc = lc->next;
}
lc->next = la ? la : lb;
return ld;
}
int main() {
Lnode* A = (Lnode*)malloc(sizeof(Lnode));
A->next = NULL;
Lnode* B = (Lnode*)malloc(sizeof(Lnode));
B->next = NULL;
int n = 0;
int m = 0;
scanf("%d %d", &n, &m);
h_insert_Lnode(A, n);
h_insert_Lnode(B, m);
Lnode* C = mergeTwoLists(A, B);
print_Lnode(C);
return 0;
}
链表的删除
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define LIST_SIZE 100
#define LISTINCREMENT 10
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
typedef struct Lnode
{
ElemType data;
struct Lnode* next;
} Lnode, * LinkList;
int ListLength(LinkList L) {
Lnode* p = L;
int k = 0;
while (p->next) {
p = p->next;
k++;
}
return k;
}
Status GetElem(Lnode* L, int i, ElemType &e) {
Lnode* p = L->next;
int j = 1;
while (p && j < i) {
p = p->next;
j++;
}
if (!p || j > i) return ERROR;
e = p->data;
return OK;
}
Status ListInsert_L(LinkList L, int i, ElemType& e) {
Lnode* p = L,*s;
int j = 0;
while (!p || j < i - 1) { p = p->next; j++;}
if (!p || j > i - 1) return ERROR;
s = (Lnode*)malloc(sizeof(Lnode));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
Status ListDelete_L(LinkList L, int i, ElemType *e) {
Lnode* p = L, * s;
int j = 0;
while (p->next && j < i-1) { p = p->next; j++; }
if (!p->next || j > i-1) return ERROR;
s = p->next;
*e = s->data;
p->next = s->next;
free(s);
return OK;
}
Status CreateList_L(LinkList L, int n) {
Lnode* p,*m;
ElemType q;
m = L;
for (int i = 0; i < n; i++) {
p = (LinkList)malloc(sizeof(Lnode));
p->next = NULL;
scanf("%d ", &q);
p->data = q;
m->next = p;
m = m->next;
}
return OK;
}
void ClearList(LinkList& L) {
Lnode* p;
while (L->next) {
p = L->next;
L->next = p->next;
free(p);
}
}
struct Lnode* mergeTwoLists(struct Lnode* l1, struct Lnode* l2) {
Lnode* la = l1->next, * lb = l2->next, * lc, * ld;
lc = (Lnode*)malloc(sizeof(Lnode));
ld = lc;
while (la && lb) {
if (la->data <= lb->data) {
lc->next = la;
la = la->next;
}
else {
lc->next = lb;
lb = lb->next;
}
lc = lc->next;
}
lc->next = la ? la : lb;
return ld;
}
int main() {
int n,count,q;
ElemType e;
Lnode *h = NULL;
h = (LinkList)malloc(sizeof(Lnode));
h->next = NULL;
scanf("%d", &n);
CreateList_L(h,n);
scanf("%d", &count);
for (int i = 0; i < count; i++) {
scanf("%d", &q);
if (!ListDelete_L(h, q, &e)) printf("-1\n");
else printf("%d\n", e);
}
return 0;
}
链表的操作
//还包括总结的一些其他操作
#include <bits/stdc++.h>
using namespace std;
#define OK 1
#define ERROR 0
#define LIST_SIZE 100
#define LISTINCREMENT 10
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
typedef struct Lnode
{
ElemType data;
struct Lnode* next;
} Lnode, * LinkList;
Status Reverse(LinkList L) {
Lnode* p = L->next, * q, * s;
q = p->next;
if (!q->next) {
L->next = q;
q->next = p;
p->next = NULL;
return OK;
}
p->next = NULL;
s = q->next;
do {
q->next = p;
p = q;
q = s;
s = s->next;
} while (s);
q->next = p;
L->next = q;
return OK;
}
ElemType add_L(LinkList L) {
Lnode* p = L->next;
int sum = 0;
while (p) { sum += p->data; p = p->next; }
return sum;
}
Status GetElem(Lnode* L, int i, ElemType& e) {
Lnode* p = L->next;
int j = 1;
while (p && j < i) {
p = p->next;
j++;
}
if (!p || j > i) return ERROR;
e = p->data;
return OK;
}
ElemType LocateElem_L(LinkList L, ElemType *q) {
Lnode* p = L->next;
int k = 1;
while (p) {
if (*q == p->data) return k;
k++;
p = p->next;
}
return ERROR;
}
Status ListInsert_L(LinkList L, int i, ElemType& e) {
Lnode* p = L, * s;
int j = 0;
while (!p || j < i - 1) { p = p->next; j++; }
if (!p || j > i - 1) return ERROR;
s = (Lnode*)malloc(sizeof(Lnode));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
Status ListDelete_L(LinkList L, int i, ElemType* e) {
Lnode* p = L, * s;
int j = 0;
while (p->next && j < i - 1) { p = p->next; j++; }
if (!p->next || j > i - 1) return ERROR;
s = p->next;
*e = s->data;
p->next = s->next;
free(s);
return OK;
}
Status CreateList_L(LinkList L, int n) {
Lnode* p, * m;
ElemType q;
m = L;
for (int i = 0; i < n; i++) {
p = (LinkList)malloc(sizeof(Lnode));
p->next = NULL;
scanf("%d ", &q);
p->data = q;
m->next = p;
m = m->next;
}
return OK;
}
void ClearList(LinkList& L) {
Lnode* p;
while (L->next) {
p = L->next;
L->next = p->next;
free(p);
}
}
struct Lnode* mergeTwoLists(struct Lnode* l1, struct Lnode* l2) {
Lnode* la = l1->next, * lb = l2->next, * lc, * ld;
lc = (Lnode*)malloc(sizeof(Lnode));
ld = lc;
while (la && lb) {
if (la->data <= lb->data) {
lc->next = la;
la = la->next;
}
else {
lc->next = lb;
lb = lb->next;
}
lc = lc->next;
}
lc->next = la ? la : lb;
return ld;
}
Status print_L(LinkList L) {
Lnode* p = L->next;
while (p) { printf("%d ",p->data); p = p->next; }
return 0;
}
int main() {
Lnode* h = (LinkList)malloc(sizeof(Lnode));
h->next = NULL;
int n, m, index;
ElemType e, a, b;
cin >> n >> m;
CreateList_L(h, n);
string s;
for (int i = 1; i <= m; i++) {
cin >> s;
if (s[0] == 'I') {
cin >> a >> b;
ListInsert_L(h, a, b);
}
else if (s[0] == 'D') {
cin >> index;
ListDelete_L(h, index, &b);
cout << b << endl;
}
else if (s[0] == 'G') {
cin >> index;
GetElem(h, index, e);
cout << e << endl;
}
else if (s[0] == 'L') {
cin >> b;
index = LocateElem_L(h, &b);
cout << index << endl;
}
else {
ClearList(h);
}
}
return 0;
}
单链表的逆转求和
#include <bits/stdc++.h>
using namespace std;
#define OK 1
#define ERROR 0
#define LIST_SIZE 100
#define LISTINCREMENT 10
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
typedef struct Lnode
{
ElemType data;
struct Lnode* next;
} Lnode, * LinkList;
Status CreateList_L(LinkList L, int n) {
Lnode* p, * m;
ElemType q;
m = L;
for (int i = 0; i < n; i++) {
p = (LinkList)malloc(sizeof(Lnode));
p->next = NULL;
cin >> q;
p->data = q;
m->next = p;
m = m->next;
}
return OK;
}
Status Reverse(LinkList L) {
Lnode* p = L->next, * q, * s;
q = p->next;
if (!q->next) { //只有两个元素时直接交换
L->next = q;
q->next = p;
p->next = NULL;
return OK;
}
p->next = NULL;
s = q->next;
do {
q->next = p;
p = q;
q = s;
s = s->next;
} while (s);
q->next = p;
L->next = q;
return OK;
}
ElemType add_L(LinkList L) {
Lnode* p = L->next;
int sum = 0;
while (p) { sum += p->data; p = p->next; }
return sum;
}
Status print_L(LinkList L) {
Lnode* p = L->next;
while (p) { printf("%d ",p->data); p = p->next; }
return OK;
}
int main() {
Lnode* h = (LinkList)malloc(sizeof(Lnode));
h->next = NULL;
int n;
cin >> n;
CreateList_L(h, n);
if(n>1) Reverse(h); //考虑n=1或n=2的情况
print_L(h);
printf("\n");
printf("%d",add_L(h));
return 0;
}
汉诺塔问题
#include <stdio.h>
void move(char A,int n,char C){
printf("%c->%d->%c\n",A,n,C);
}
void hanoi (int n,char A,char B,char C){
if(n==1){
move(A,1,C);
}
else {
hanoi(n-1,A,C,B);
move(A,n,C);
hanoi(n-1,B,A,C);
}
}
int main(){
int n;
char a,b,c;
scanf("%d %c %c %c",&n,&a,&c,&b);
hanoi(n,a,b,c);
}
循环队列插入与删除操作
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define QUEUE_INIT_SIZE 31000
#define OK 1
#define OVERFLOW -2
#define error -1
typedef int DataType;
typedef int Status;
typedef struct duilie{
int f;
int r;
DataType *base;
}queue;
int dlength(&s){
return (s.r - s.f + QUEUE_INIT_SIZE) % QUEUE_INIT_SIZE;
}
Status init(queue &s){
s.base = (DataType*)malloc(QUEUE_INIT_SIZE*sizeof(DataType));
if(s.f==NULL)return -1;
s.f = s.r = 0;
return OK;
}
Status in(queue &s,DataType e){
if(s.f == (s.r +1)%QUEUE_INIT_SIZE) exit(OVERFLOW);
s.base[s.r]=e;
s.r = (s.r +1)%QUEUE_INIT_SIZE;
return OK;
}
int del(queue &s){
if(s.f ==s.r) return -1;
DataType q = s.base[s.f];
s.f =(s.f+1) %QUEUE_INIT_SIZE;
return q;
}
int main(){
queue d;
init(d);
int n,i;
scanf("%d",&n);getchar();
for(i=0;i<n;i++){
char a[100];
int x,t;
scanf("%s", a);
if(strcmp(a,"enqueue")==0){
scanf("%d",&x);
in(d,x);
}
if(strcmp(a,"dequeue")==0){
t=del(d);
printf("%d\n",t);
}
}
return 0;
}
二叉树
由先序遍历和中序遍历序列建立二叉树
#include <stdio.h>
#include <cstdlib>
#include <cstring>
using namespace std;
#define ERROR 0
#define OK 1
#define OVERFLOW -2
typedef int status;
typedef struct Binode {
char data;
Binode* lchild;
Binode* rchild;
}Binode, * BiTree;
int getindex(char* inod, char data,int iright) {
for (int i = 0; i <= iright; i++) {
if (inod[i] == data) {
return i;
}
}
return -1;
}
void PreInOd(char preod[], int pleft, int pright, char inod[], int ileft, int iright, BiTree& t)
{
if (pleft > pright) {
t = NULL;
return;
}
t = (Binode*)malloc(sizeof(Binode));
if (!t) exit(OVERFLOW);
t->data = preod[pleft];
int mid = getindex(inod, t->data, iright);
if (mid == ileft) t->lchild = NULL;
else PreInOd(preod, pleft + 1, pleft + mid - ileft, inod, ileft, mid - 1, t->lchild);
if (mid == iright) t->rchild = NULL;
else PreInOd(preod, pleft + mid - ileft + 1, pright, inod, mid + 1, iright, t->rchild);
}
int PostOrderTraversal(BiTree T)
{
if (T)
{
PostOrderTraversal(T->lchild);
PostOrderTraversal(T->rchild);
printf("%c",T->data);
}
return OK;
}
int main() {
char preod[100];
char inod[100];
BiTree t;
scanf("%s", preod);
scanf("%s", inod);
int n1 = strlen(preod);
int n2 = strlen(inod);
PreInOd(preod, 0, n1-1, inod, 0, n2-1, t);
PostOrderTraversal(t);
printf("\n");
return 0;
}
二叉树建立、中序遍历、叶子结点及深度
#include <cstdlib>
#include <cstdio>
using namespace std;
#define ERROR 0
#define OK 1
#define OVERFLOW -2
typedef int status;
typedef struct Binode {
char data;
int deep;
Binode* lchild;
Binode* rchild;
}Binode, * BiTree;
status exchange(BiTree& T) {
if (T) {
BiTree temp = T->lchild;
T->lchild = T->rchild;
T->rchild = temp;
exchange(T->lchild);
exchange(T->rchild);
}
return OK;
}
void CountLeaf(BiTree T, int& count) {
if (T) {
if ((!T->lchild) && (!T->rchild))
count++;
CountLeaf(T->lchild, count);
CountLeaf(T->rchild, count);
}
}
status InTraversal(BiTree T) {
if (T) {
InTraversal(T->lchild);
printf("%c ", T->data);
InTraversal(T->rchild);
}
return OK;
}
int BitreeDepth(BiTree T)
{
int depth = 0;
if (T == NULL) depth = 0;
else {
int ldepth = BitreeDepth(T->lchild);
int rdepth = BitreeDepth(T->rchild);
depth = 1 + (ldepth > rdepth ? ldepth : rdepth);
}
return depth;
}
status creabitree(BiTree& T) {
char get;
scanf("%c", &get);
if (get == '#' || get == '\n') T = NULL;
else {
if (!(T = (Binode*)malloc(sizeof(Binode)))) exit(OVERFLOW);
T->data = get;
T->deep = 1;
creabitree(T->lchild);
creabitree(T->rchild);
}
return OK;
}
int main() {
int count = 0,deep=0;
BiTree T;
creabitree(T);
exchange(T);
InTraversal(T);
printf("\n");
CountLeaf(T, count);
printf("%d\n", count);
printf("%d\n", BitreeDepth(T) );
return 0;
}
建二叉树并输出所找结点的祖先
注意这里的代码建议使用pop和push合用的形式，使用我下面的这个代码在过大情况下会导致内存超出的错误。不过因为oj测试数据范围较小，下面的代码也可以通过。（懒得改了）
#include <cstdlib>
#include <cstdio>
using namespace std;
#define ERROR 0
#define OK 1
#define OVERFLOW -2
typedef struct Stacknode{
int data;
struct Stacknode* next;
}Stacknode;
typedef struct stack {
Stacknode* top;
}stack;
typedef int status;
typedef struct Binode {
int data;
Binode* lchild;
Binode* rchild;
}Binode, * BiTree;
status push(stack& t,int data) {
Stacknode* p = (Stacknode*)malloc(sizeof(Stacknode));
if (p == NULL) exit(OVERFLOW);
p->data = data;
p->next = t.top;
t.top = p;
return OK;
}
status initstack(stack& t) {
t.top = NULL;
return OK;
}
status printstack(stack t) {
Stacknode* p = t.top;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
return OK;
}
status getfather(BiTree& T, int node,stack t) {
if (T) {
push(t, T->data);
if (T->data == node) printstack(t);
getfather(T->lchild, node,t);
getfather(T->rchild, node, t);
}
return OK;
}
status creabitree(BiTree& T) {
int get;
scanf("%d", &get);
if (get == 0) T = NULL;
else {
if (!(T = (Binode*)malloc(sizeof(Binode)))) exit(OVERFLOW);
T->data = get;
creabitree(T->lchild);
creabitree(T->rchild);
}
return OK;
}
int main() {
int count = 0,deep=0;
BiTree T;
creabitree(T);
scanf("%d", &count);
for (int i = 0; i < count; i++) {
int node;
scanf("%d", &node);
stack t;
initstack(t);
getfather(T, node, t);
printf("\n");
}
return 0;
}
树
二元组建树并求其叶子结点和深度
#include<stdio.h>
#include <stdlib.h>
#define ERROR 0
#define OK 1
#define OVERFLOW -2
typedef int Elem;
typedef struct CSNode {
Elem data;
struct CSNode* firstchild, * nextsibling;
} CSNode, * CSTree;
typedef CSNode Qelemtype;
typedef int status;
typedef struct QNode {
Qelemtype* Qdata;
struct QNode* next;
}Qnode, * QueuePtr;
typedef struct {
QueuePtr front;
QueuePtr rear;
} LinkQueue;
status InitQueue(LinkQueue& Q) {
Q.front = Q.rear = (QueuePtr)malloc(sizeof(Qnode));
if (!Q.front) exit(OVERFLOW);
Q.front->next = NULL;
return OK;
}
status EnQueue(LinkQueue& Q, Qelemtype *e)
{
QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
if (!p) exit(OVERFLOW);
p->Qdata = e; p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}
Qelemtype* DeQueue(LinkQueue& Q) {
Qelemtype* e;
if (Q.front == Q.rear) return(ERROR);
QueuePtr p = Q.front->next;
e = p->Qdata;
Q.front->next = p->next;
if (Q.rear == p) Q.rear = Q.front;
free(p);
return e;
}
Qelemtype* GetHead(LinkQueue& Q) {
Qelemtype* e;
if (Q.front == Q.rear) return ERROR;
e = Q.front->next->Qdata;
return e;
}
CSTree GetTreeNode(int ch){
CSTree p = (CSTree)malloc(sizeof(CSNode));
p->data = ch;
p->firstchild = NULL;
p->nextsibling = NULL;
return p;
}
void CreatTree(CSTree& T){
T = NULL;
CSTree r =NULL;
int ch = NULL, fa = NULL;
int i = 0;
LinkQueue Q;
InitQueue(Q);
scanf("%d", &i); getchar();
for (int j =0; j<i; j++)
{
CSTree s = NULL, p;
scanf("%d %d", & fa, &ch); getchar();
p = GetTreeNode(ch);
EnQueue(Q, p);
if (fa == -1) T = p;
else {
s = GetHead(Q);
while (s->data != fa) {
s = DeQueue(Q); s =GetHead(Q);
}
if (!(s->firstchild)){
s->firstchild = p; r = p;
}
else { r->nextsibling = p; r = p; }
}
}
}
int TreeDepth(CSTree T) {
int h1, h2;
if (!T) return 0;
else {
h1 = TreeDepth(T->firstchild);
h2 = TreeDepth(T->nextsibling);
return(h1 + 1 > h2 ? h1 + 1 : h2);
}
}
status pretraverse(CSTree T) {
if (T) {
if(!T->firstchild) printf("%d ",T->data);
pretraverse(T->firstchild);
pretraverse(T->nextsibling);
}
return OK;
}
int main() {
CSTree T;
CreatTree(T);
pretraverse(T);
printf("\n");
printf("%d",TreeDepth(T));
return 0;
}
数据压缩中的编码问题
不会，用ai辅助写的。。。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_CHAR 127
typedef struct Node {
int freq;
struct Node* next;
} Node;
void insertSorted(Node** head, int freq) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->freq = freq;
newNode->next = NULL;
if (*head == NULL || (*head)->freq >= freq) {
newNode->next = *head;
*head = newNode;
}
else {
Node* curr = *head;
while (curr->next != NULL && curr->next->freq < freq) {
curr = curr->next;
}
newNode->next = curr->next;
curr->next = newNode;
}
}
int popMin(Node** head) {
if (*head == NULL) return 0;
Node* temp = *head;
int val = temp->freq;
*head = (*head)->next;
free(temp);
return val;
}
int huffmanEncodedLength(const char* str) {
int freq[MAX_CHAR] = { 0 };
for (int i = 0; str[i]; i++) {
freq[(unsigned char)str[i]]++;
}
Node* head = NULL;
for (int i = 0; i < MAX_CHAR; i++) {
if (freq[i] > 0) {
insertSorted(&head, freq[i]);
}
}
int totalLength = 0;
while (head && head->next) {
int f1 = popMin(&head);
int f2 = popMin(&head);
int merged = f1 + f2;
totalLength += merged;
insertSorted(&head, merged);
}
return totalLength;
}
int main() {
char input[101];
int count = 0;
scanf("%d", &count); getchar();
for (int i = 0; i < count; i++) {
fgets(input, 101, stdin);
input[strcspn(input, "\n")] = '\0';
int encodedLength = huffmanEncodedLength(input);
printf("%d\n", encodedLength);
}
return 0;
}
任两点间最短路径Floyd算法
#include <iostream>
using namespace std;
#define MAX_VERTEX_N 105
#define MAX_EDGE_M 10005
#define INF 1000000007
typedef int VRType;
typedef int VertexType;
typedef int status;
typedef struct ArcCell {
VRType adj;
} ArcCell, AdjMatrix[MAX_VERTEX_N][MAX_VERTEX_N];
typedef struct MGraph {
VertexType vexs[MAX_VERTEX_N];
AdjMatrix arcs;
int vexnum, arcnum;
} MGraph;
int m;
int dist[MAX_VERTEX_N][MAX_VERTEX_N];
void CreatGraph(MGraph& G) {
int u, v, t;
cin >> G.vexnum >> m;
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
G.arcs[i][j].adj = INF;
}
}
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
cin >> G.arcs[i][j].adj;
}
}
}
void Floyd(MGraph G) {
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
dist[i][j] = G.arcs[i][j].adj;
}
}
for (int k = 0; k < G.vexnum; k++) {
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
if(dist[i][j] > dist[i][k]+dist[k][j]){
dist[i][j] = dist[i][k]+dist[k][j];
}
}
}
}
int u,v;
for(int i =0;i<m;i++){
cin >> u >>v;
cout << dist[u][v] <<endl;
}
}
int main() {
MGraph G;
CreatGraph(G);
Floyd(G);
return 0;
}
关键路径
#include <bits/stdc++.h>
using namespace std;
#define MAX_VERTEX_N 250
#define MAX_EDGE_M 10005
#define INF 1000000007
typedef int VRType;
typedef int VertexType;
typedef int status;
typedef struct ArcNode {
int adjvex;
VRType cost;
struct ArcNode *nextarc;
} ArcNode;
typedef struct VNode {
VertexType data;
ArcNode *firstarc;
} VNode, AdjList[MAX_VERTEX_N];
typedef struct {
AdjList vertices;
int vexnum, arcnum;
} ALGraph;
typedef struct Queue{
int data[MAX_VERTEX_N];
int rear, front;
} Queue;
typedef struct Edge {
int v, w;
} Edge;
bool cmp(Edge a, Edge b) {
return a.v == b.v? a.w < b.w :a.v < b.v;
}
void InitQueue(Queue &Q){
Q.rear = Q.front = 0;
}
int EmptyQueue(Queue Q){
return Q.rear == Q.front;
}
void Push(Queue &Q, int x){
Q.data[Q.rear++] = x;
}
void Pop(Queue &Q, int &x){
int minn = Q.data[Q.front], j = Q.front;
for (int i=Q.front;i<Q.rear;i++)
if (Q.data[i] < minn) minn = Q.data[i], j=i;
int temp = Q.data[j];
Q.data[j] = Q.data[Q.front];
Q.data[Q.front] = temp;
x = Q.data[Q.front++];
}
void CreatGraph(ALGraph &G){
int v, w, x;
scanf("%d%d", &G.vexnum, &G.arcnum);
for (int i=1;i<=G.vexnum;i++) {
G.vertices[i].data = i;
G.vertices[i].firstarc = NULL;
}
for (int i=1;i<=G.arcnum;i++){
scanf("%d%d%d", &v, &w, &x);
ArcNode *p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = w; p->cost = x; p->nextarc = G.vertices[v].firstarc;
G.vertices[v].firstarc = p;
}
}
void CountInDegree(ALGraph G, int indegree[]){
for (int v=1;v<=G.vexnum;v++) indegree[v] = 0;
for (int v=1;v<=G.vexnum;v++){
for (ArcNode* w=G.vertices[v].firstarc; w; w=w->nextarc)
indegree[w->adjvex]++;
}
}
void TopoLogicalSort(ALGraph G){
//拓扑排序
Queue Q;
int v, indegree[MAX_VERTEX_N];
int topo[MAX_VERTEX_N], ve[MAX_VERTEX_N], vl[MAX_VERTEX_N];
CountInDegree(G,indegree);
InitQueue(Q);
for (int v=1;v<=G.vexnum;v++)
if (!indegree[v]) {
Push(Q, v); indegree[v] = INF;
}
while (!EmptyQueue(Q)) {
Pop(Q, v);
for (ArcNode* w=G.vertices[v].firstarc; w; w=w->nextarc) {
indegree[w->adjvex]--;
if (!indegree[w->adjvex]) {
Push(Q, w->adjvex); indegree[w->adjvex] = INF;
}
}
}
if (Q.rear<G.vexnum) {
printf("unworkable project\n");
return ;
}
for (int i=1;i<=G.vexnum;i++) topo[i] = Q.data[i-1];
int max =0;
for(int i=1;i<=G.vexnum;i++)ve[i] =0;
for(int i=1;i<=G.vexnum;i++){
int v =topo[i];
if(ve[v]>max)max=ve[v];
for(ArcNode * p=G.vertices[v].firstarc;p;p=p->nextarc){
if(ve[p->adjvex]<ve[v] + p->cost) ve[p->adjvex] = ve[v] + p->cost;
}
}
printf("%d\n", max);
for(int i =1;i<=G.vexnum;i++) vl[i] =max;
for(int i =G.vexnum;i>0;i--){
int v = topo[i];
for(ArcNode * p=G.vertices[v].firstarc;p;p=p->nextarc){
if(vl[v] > vl[p->adjvex]- p->cost) vl[v] = vl[p->adjvex] - p->cost;
}
}
int t =0;
Edge edge[MAX_EDGE_M];
for(int v=1;v<=G.vexnum;v++){
for(ArcNode * p=G.vertices[v].firstarc;p;p=p->nextarc){
int e =ve[v];
int l =vl[p->adjvex] - p->cost;
if(e==l){
edge[t].v = v;
edge[t++].w =p->adjvex;
}
}
}
sort(edge, edge+t, cmp);
for (int i=0;i<t;i++) printf("%d->%d\n", edge[i].v, edge[i].w);
}
int main() {
ALGraph G;
CreatGraph(G);
TopoLogicalSort(G);
return 0;
}