Data Structure Platform 5
DS5
Problem A.a
Find the shortest path from A to all other vertices for the graph in Figure 9.80.
通过邻接矩阵定义加权图
1234567891011121314151617181920212223//index-char array char id[7] = {'A', 'B', 'C', 'D', 'E', 'F', 'G',}; //generate the graph int G[7][7]; //init = 0 for (int i = 0; i < 7; i++) { for (int j = 0; j < 7; j++) { G[i][j] = INF; } } //ad ...
Data Structure Platform 4
DS4
Problem A
向空AVL树插入 3,1,4,6,9,2,5,7
在插入9前，与BST相同
图示：
按BST插入方法插入9
图示：
此时，0003节点左右子树高度差超过1，执行旋转树操作。
图示：
后续插入同BST
图示：
Problem B
单旋转代码：
12345678910111213141516171819202122232425PTNode rightRotate(PTNode y) { PTNode x = y->LChild; PTNode xr = x->RChild; x->RChild = y; y->LChild = xr; x->height = height(x); y->height = height(y); return x;}PTNode leftRotate(PTNode y) { PTNode x = y->RChild; PTNode xl = x->LChild; x->LChi ...
Data Structure Platform 3
DataStructureHomework3
题目
假设以块链结构（blocked linked）表示串，试编写将串 s 插入到串 t 中某个字符之后的算法，若该字符不存在，则将串 s 联接在串 t 之后。
分析
定义结构
12345typedef struct block *PTNode;struct block { char character[SIZE]; PTNode next;};
其中，本例常量定义为
1#define SIZE 5
图示如下
写入
采用两个函数 WriteInList 和 WriteInBlock, 用flag来表示块是否写满
12345678910void WriteInList(PTNode pHead) { int flag = 1; while (flag) { PTNode pLast = pHead; while (pLast->next != NULL) { pLast = pLast->next; ...
Data Structure Platform 2
DS2
3.21 Write routines to implement two stacks using only one arrayYour stack routines should not declare an overflow unless everyslot in the array is used
3.21 编写例程以仅使用一个数组实现两个堆栈除非使用了数组中的每个插槽，否则堆栈例程不应声明溢出
考虑使用如下逻辑结构：
source code
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include <stdio.h>#include <stdlib.h>typedef int Array;Array arr[10];int l_top, r_top;//init arr -1void init() { for (int i = 0; i < 10; i++) ...
Data Structure Platform 1
2.11
Give an efficient algorithm to determine if there exists an integer i such that Ai = i in an array of integers A1 < A2 < A3 < … < AN. What is the running time of your algorithm?
source code
1234567891011121314151617181920212223242526272829303132333435363738#include <stdio.h>//2.11//By using Binary Searchint SearchArry(int head, int tail, int *arr, int key) { int mid = (head + tail) / 2; if (head > tail) { return -1; } if (arr[mid] == ...
