全部 / 技术交流 · 2023年10月7日 0

866数据结构与算法练习记录

本文最后更新于 251 天前,其中的信息可能已经有所发展或改变。

既然决定跨考至HNU软件工程,这篇文章就用以记录刷过的数据结构算法题~

1.重构链表

void reverseLinklist(Linklist &L) {
    Lnode *p = NULL, *q = L, *temp;

    while (q != NULL) {
        temp = q->next;
        q->next = p;
        p = q;
        q = temp;
    }
    L = p; // 更新L的位置为反转后的链表的头部
}//头插法原地逆置

Lnode *findmiddle(Linklist L){
  Lnode *slow=L,*quick=L;
  while(quick!=NULL){
    slow=slow->next;
    quick=quick->next;
    if(quick!=NULL)quick=quick->next;
  }
  return slow;
}//快慢指针寻找中间节点


void reconstruct(Linklist &L){
  Lnode *mid=findmiddle(L);
  reverseLinklist(mid);
  Lnode *p=L,*q=mid,*temp1,*temp2;
  while(p!=mid&&q!=NULL){
    temp1=p->next;
    p->next=q;
    temp2=q->next;
    q->next=temp1;
    p=temp1;
    q=temp2;
  }
}//重构链表
C

2.求二叉树带权路径长度WPL

int WPL(Bitree T){
    if(T==NULL)return-1;
    InitQueue(Q);
    Bitnode *p=T;
    int level=0,wpl=0;
    EnQueue(Q,p);
    while(!isEmpty(Q)){
        int levelsize=QueueSize(Q);
        level++;
        for(int i=0;i<levelsize;i++){
            DeQueue(Q,p);
            if(p->lchild)EnQueue(Q,p->lchild);
            if(p->rchild)EnQueue(Q,p->rchild);
            if(isleaf(p))wpl=wpl+p->weight*level;
        }
    }
    return wpl;
}//求WPL

int WPL2(Bitree T,int length){
    if(T==NULL)return 0;
    if(isleaf(T)){
        return T->weight*length;
    }
    int leftwpl=WPL2(T->lchild,length+1);
    int rightwpl=WPL2(T->rchild,length+1);
    return leftwp + rightwpl;
}

int wplcaculator(Bitree T){
    return WPL2(T,0);
}//递归求WPL
C

3.计算结点最远距离

假定二叉树中两个结点的距离为两个结点之间边的条数(二叉树的边是无向边)。
编写一个函数求一棵二叉树中相距最远的两个结点之间的距离

struct TreeNode {
    struct TreeNode* left;
    struct TreeNode* right;
    int data;  // 此处为了完整性添加,实际算法中不会用到此data
};

int maxDistance = 0;

int depth(struct TreeNode* node) {
    if (node == NULL) {
        return 0;
    }

    // 递归计算左子树和右子树的深度
    int leftDepth = depth(node->left);
    int rightDepth = depth(node->right);

    // 更新最大距离
    if (leftDepth + rightDepth > maxDistance) {
        maxDistance = leftDepth + rightDepth;
    }

    // 返回当前节点的深度
    return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}

int findMaxDistance(struct TreeNode* root) {
    maxDistance = 0;
    depth(root);
    return maxDistance;
}
C

4.中序遍历的应用

void reform(Bitree T, int deep){
    if(T){
        if(isleaf(T)) {
        printf('%s',T->data);
        }else{
        if(deep>1)printf('(');
        reform(T->lchild,deep+1);
        printf('%s',T->data);
        reform(T->rchild,deep+1);
        if(deep>1)printf(')');
        }
    }else{
    return;
    }
}//二叉树转换
C

5.基于邻接多重表存储结构的图增加边(setEdge) 操作

// 边表节点
typedef struct ENode {
    int ivex, jvex; // 该边所依附的两个顶点的位置
    struct ENode *ilink, *jlink; // 分别指向依附于顶点ivex和jvex的下一条边
} ENode;

// 顶点表节点
typedef struct VNode {
    char data;  // 顶点信息
    ENode *firstedge;  // 指向第一条依附于该顶点的边
} VNode;

// 图
typedef struct {
    VNode adjmulist[MAX_VERTEX_NUM];  // 顶点数组
    int vexnum, edgenum;  // 图的当前顶点数和边数
} AMLGraph;

void setEdge(AMLGraph *G, int i, int j) {
    if (i == j) {
        printf("Self loops are not allowed.\n");
        return;
    }

    ENode *newEdge = (ENode *)malloc(sizeof(ENode));
    if (!newEdge) {
        printf("Memory allocation failed.\n");
        return;
    }

    // 设置边的信息
    newEdge->ivex = i;
    newEdge->jvex = j;

    // 将新边插入i的边表
    newEdge->ilink = G->adjmulist[i].firstedge;
    G->adjmulist[i].firstedge = newEdge;

    // 将新边插入j的边表
    newEdge->jlink = G->adjmulist[j].firstedge;
    G->adjmulist[j].firstedge = newEdge;

    G->edgenum++;  // 增加图的边数
}
C

6.基于ADT统计顶点出度与入度

void GraphDegree(Graph* G, int* indegree, int* outdegree{
  for(v=0;v<G->n();v++){
    for(w=G->First(v);w<G->n();w=G->Next(v,w){
      outdegree[v]++
      indegree[w]++
      }
    }
  }
C

7.Dijkstra算法的应用

// 使用Dijkstra算法计算从C市到所有其他城镇的最短距离
int* dijkstra(int graph[n][n], int src) {
    int dist[n]; // 存储从C市到每个城镇的最短距离
    bool visited[n]; // 标记城镇是否被访问
    for (int i = 0; i < n; i++) {
        dist[i] = INT_MAX;
        visited[i] = false;
    }
    dist[src] = 0;
    for (int count = 0; count < n - 1; count++) {
        int u = findMinimumDistance(dist, visited); // 寻找当前未访问的最短距离的城镇
        visited[u] = true;
        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
    return dist;
}

int computeShortestDistanceSum(int graph[n][n], int src, int K) {
    int* dist = dijkstra(graph, src);
    sort(dist + 1, dist + n); // 排除C市,然后排序
    int sum = 0;
    for (int i = 1; i <= K; i++) {
        sum += dist[i];
    }
    return sum;
}
C