24软专 数据结构

1、A[n]，k，将数组向右循环移动k位。要求时间复杂度O(n)，空间O(1)。

思路：采用三次反转数组的操作，可以实现时间复杂度为O(n)，空间复杂度为O(1)的算法。

void moveElem(int array[],int k,int length){//array是需要循环移动元素的数组，k是需要移动的位数，length是数组的长度int temp;//先将整个数组反转for(int i=0;i<=length/2;i++){temp=array[length-1-i];array[length-1-i]=array[i];array[i]=temp;}//再反转前K个元素，这样就使得原本在倒数k个位置的元素来到了数组前K个位置，相当于后k个元素都前进了k位for(int i=0;i<=k/2;i++){temp=array[k-1-i];array[k-1-i]=array[i];array[i]=temp;}//再反转下标为k到n-1的所有元素，相当于前n-k个元素后移了k位for(int i=k;i<=(length+k)/2-1;i++){temp=array[length+k-1-i];array[length+k-1-i]=array[i];array[i]=temp;}
}

2、给定一个无向无权图G，对所有顶点排序，按照每个顶点到顶点V的最短路径长度非增排序。要求时间复杂度O(n+e) n:顶点数 e:边数

bool visited[MaxVertexNum];               // 访问数组
char distSorted[MaxVertexNum];            // 保存排序信息
int len;                                  // 路径长度（或者理解为广度优先搜素层数）
void BFSTraverse(ALGraph G, int K, int v) // 邻接表存储图
{for (int i = 0; i < G.vernum; ++i){visited[i] = false; // 初始化访问数组dist[i] = -1;       // 初始化最短路径数组}Queue Q;InitQueue(Q); // 初始化队列；// 从顶点V开始搜索// 更新访问数组visited[v] = true;distSorted[0] = G.vertices[v].data;int i=0;// 将结点V入队EnQueue(Q, v);while (!IsEmpty(Q)){                  // 当队列不空时DeQueue(Q, v); // 队首顶点出队并用V保存该顶点for (ArcNode *p = G.vertices[v].firstarc; p; p->nextarc){                      // 检测所有V的邻接点int w = p->adjvex; // w即为邻接点if (visited[w] == false){ // 当前节点未访问// 更新访问数组visited[w] = true;distSorted[++i] = G.vertices[v].data;EnQueue(Q, w); // w入队}}}//给结点排序，由于广度优先搜索形成的结点是按照距离由小到大保存的，因此只要反转数组即可for(int i=0;i<=G.vernum/2;i++){char temp=distSorted[G.vernum-1-i];distSorted[G.vernum-1-i]=distSorted[i];distSorted[i]=temp;}
}

3、struct BinNode{

        int size;//以该结点为根的子树的总结点数

        BinNode *left,*right;

}

实现BinNode* rank(BinNode *t,int k)

功能为找到先根序列中第K个结点，返回其地址。要求：不使用先序遍历，且时间复杂度为0（depth(x)),depth(x)为结点x的深度。

BinNode *rank(BinNode *t, int k)
{if (!t)return nullptr; // 如果树为空，返回空// 如果第k个节点就是当前节点if (k == 1)return t;// 如果第k个节点在左子树中if (k <= t->left->size+1){return rank(t->left, k-1);}else{// 如果第k个节点在右子树中return rank(t->right, k - t->left->size - 1);}
}

按照先序遍历的规则，根节点是先序遍历中的第1个节点，然后先遍历完左子树才会遍历右子树，因此如果k小于左子树上节点的个数，那么说明第k个节点在其左子树上，因此继续往左寻找。而如果k大于左子树上的节点个数就说明k在右子树上，因此向右寻找。