Data Structure Platform 6
DS6
Problem A
If the key sequence of the initial record is with the key (49,38,65,97,76,13,27,50), give the results of shell sort with intervals d=4 and then with d=2;
创建数组及其他函数
1234int main() { int arr[8] = {49, 38, 65, 97, 76, 13, 27, 50}; return 0;}
交换函数，用来交换两个整数
12345void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp;}
打印函数，遍历输出数组
12345void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp;}
排序算法
123456789101 ...
Data Structure PTA-Sort
7-12 Insertion sort
插入排序
Implement the insertion sort algorithm in descending order.
输入格式:
Input,2 line.
First line means the number of keys (<=20)
The second line means the initial key sequence consisted of several integers divided by common
输出格式:
Output, Several lines.
Each line gives the every iteration of insertion sort. Add “\n” to the end of each line.
输入样例:
在这里给出一组输入。例如：
1237,3,1,
输出样例:
在这里给出相应的输出。例如：
123,7,1,1,3,7,
思想
向有序序列中插入元素
步骤
将第一个元素视为有序序列
对于有序列后的元素，比较与前一个元素值，不符合序列顺序则交换两元素。
步 ...
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] == ...
