本文最后更新于 204 天前，其中的信息可能已经有所发展或改变。
既然决定跨考至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;
}
}//重构链表
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);
}//递归求WPL3.计算结点最远距离
假定二叉树中两个结点的距离为两个结点之间边的条数（二叉树的边是无向边）。
编写一个函数求一棵二叉树中相距最远的两个结点之间的距离
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;
}
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;
}
}//二叉树转换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++; // 增加图的边数
}
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]++
}
}
}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;
}
