The background,
Just a few days ago, our data structure teacher posted a course design:
Problem description: establish id card information management system, can carry out id card information input, search, save, consider the search efficiency, use binary sorting tree storage information. Specific functions are:
(1) Able to input ID number and related information, including name, address and mobile phone number;
(2) Can quickly query the ID number, and output related information;
(3) You can modify other information corresponding to the ID card number, such as name and address;
(4) The id card information can be deleted.
(5) The information is saved in the data file.
But I a deep thought, MY C language almost a semester useless, this should not cool cool.
When I got back to my dormitory, I began to register
Seeing the familiar TS syntax, IT occurred to me that this could be written in C, so why not in TS.
Two, the road twists and turns, a long story
/ / # BST. Ts file
import { IDData, BNode } from "./dataType";
class BST {
public root: BNode = null;
public BNode = class implements BNode {
data: IDData;
left: BNode = null;
right: BNode = null;
constructor(data: IDData) {
this.data = data; }}// Insert a node into the tree
insert(data: IDData): void {
const newNode = new this.BNode(data);
if (this.root == null) {
this.root = newNode;
} else {
this.insertNode(this.root, newNode)
}
}
// Find the insert node
private insertNode(root: BNode, node: BNode) {
// look left
if (Number(node.data.id) < Number(root.data.id)) {
// If the left subtree empty is inserted directly
if (root.left == null) {
root.left = node
} else {
// Continue recursively if not empty
this.insertNode(root.left, node)
}
} else {
if (root.right == null) {
root.right = node
} else {
this.insertNode(root.right, node)
}
}
}
// Run the following command through the data:
inorderTraversal(): IDData[] {
const result: IDData[] = [];
this.preorderTraversalNode(this.root, result);
return result;
}
private preorderTraversalNode(node: BNode, result: IDData[]) {
if (node == null) return result;
this.preorderTraversalNode(node.left, result)
result.push(node.data)
this.preorderTraversalNode(node.right, result)
}
/ / to find
search(id: IDData['id']): IDData {
let node: BNode = this.root;
while (node) {
if (Number(id) < Number(node.data.id)) {
node = node.left
} else if (Number(id) > Number(node.data.id)) {
node = node.right
} else {
return node.data
}
}
}
/ / delete
delete(id: IDData['id']): IDData {
let currentNode: BNode = this.root;
let parentNode: BNode = null;
let isLeftChild: boolean = true;
//循环查找要删除的节点 currentNode，已及它的parrentNode,isLeftChild
while(currentNode.data.id ! = id) { parentNode = currentNode;if (Number(id) < Number(currentNode.data.id)) {
isLeftChild = true;
currentNode = currentNode.left;
} else {
isLeftChild = false;
currentNode = currentNode.right;
}
// Return null
if (currentNode == null) {
return null; }}//1. Delete leaf node
if (currentNode.left == null && currentNode.right == null) {
if (currentNode == this.root) {
this.root == null;
} else if (isLeftChild) {
parentNode.left = null;
} else {
parentNode.right = null;
}
//2. Delete the node with only one child node
} else if (currentNode.right == null) {//currentNode only has left nodes
// Check whether it is the root node
if (currentNode == this.root) {
this.root = currentNode.left;
// Check whether currentNode is the left cotyledon of the parent node
} else if (isLeftChild) {
// Rejoin the left cotyledon of the parent node to the cotyledon that is currentNode
parentNode.left = currentNode.left
} else {
parentNode.right = currentNode.left
}
} else if (currentNode.left == null) {//currentNode has only slave nodes
// Check whether it is the root node
if (currentNode == this.root) {
this.root = currentNode.right
// Check whether currentNode is the left cotyledon of the parent node
} else if (isLeftChild) {
// Rejoin the left cotyledon of the parent node to the cotyledon that is currentNode
parentNode.left = currentNode.right
} else {
parentNode.right = currentNode.right
}
//3. Delete two child nodes
}else{
//1. Find subsequent nodes
let successor=this.getSuccessor(currentNode);
//2. Check whether the node is the root node
if(currentNode==this.root){
this.root=successor;
}else if(isLeftChild){
parentNode.left=successor;
}else{
parentNode.right=successor;
}
//3. Change the subsequent left node to the deleted left node
successor.left=currentNode.left;
}
return currentNode.data;
}
private getSuccessor(delNode:BNode):BNode{
// Save the follow-up to find
let successor:BNode=delNode;
let current:BNode=delNode.right;
let successorParent:BNode=delNode;
while(current! =null){
successorParent=successor;
successor=current;
current=current.left;
}
// Determine whether the next node to be searched is directly the right of the node to be deleted
if(successor! =delNode.right){ successorParent.left=successor.right; successor.right=delNode.right }return successor
}
}
export default BST
Copy the codeDeclaration file
/ / # dataType. Which s file
export declare enum Sex{
male="Male",
female="Female"
}
export declare interface IDData{
id:string.name:string.telephone:string.address:string.sex:Sex,
age:number
}
export declare interface BNode{
data:IDData,
left:BNode,
right:BNode
}
Copy the codeAbove is the complete binary sorting tree code, because I just started to contact with data structures and algorithms are not very familiar with,
This is a reference
JavaScript data structures and algorithms
The core binary tree is written, followed by the following questions:
1. Where does it run?
2. How do I receive command line parameters?
3. In what format is the data file stored?
4. How to store it in data files?
5. How to improve user experience?
2. Identify problems and solve them
1. Where does it run?
No doubt running in the Node environment, just some time ago also self-taught a little process, thread, NET module.
I simply for practice, this course design as a test paper to test the knowledge learned before.
2. How do I receive command line parameters?
The readLine module is shown in the Node tutorial and is a good way to do this. I use inquirer.
3. In what format is the data file stored?
At that time, my roommate was on the way back to my dormitory with me. My roommate learned Java. I asked him what format of file do you plan to use to save data.
But then I thought, TXT text seems to have no format at all, if you can put Excel spreadsheet good.
When I went back to VS Code and saw the package description file package.json, I thought I could save it with JSON data. Json data is full of key-value pairs, objects and arrays, so I can put each piece of identity information into an object and store it in an array.
4. How to store it in data files?
Here I use the FS module to read and write all at once.
5. How to improve user experience?
Write a server that combines vue with the entire web page? On second thought, there are still 20 days left for the final exam. Do you have time to review after writing this?
Then I still choose the console to print. In practice, I found that it was impossible to print JSON string data when the amount of data was too much. Can I print a table? After some searching, I found the package word-table. I decided to use Chalk to try my own CLI. Those of you who know chalk also have a commander, but I’m not going to use that.
The following goes directly to the code
//# src/CommandeLine/index.ts
import inquirer from "inquirer";
import chalk from "chalk";
enum Sex{
male="Male",
female="Female"
}
export async function init(){
return await inquirer.prompt([
{
type:'list'.name:'serve'.message:chalk.yellow('Please select service:'),
choices: ['Input identity information'.'Query Identity information'.'View all data'.'Delete specified information'.'Modify specified information'.'save'.'exit']})}export async function input(){
return await inquirer.prompt([
{
type:'input'.name:'name'.message:'Please enter your name'.default:"Zhang"
},
{
type:'input'.name:'age'.message:'Please enter age'.default:'18'
},
{
type:'confirm'.name:'sex'.message:'What's your gender? '.default:'male'
},
{
type:'input'.name:'id'.message:chalk.greenBright('Please enter your ID number'),
validate(value){
return! value.length ?new Error(chalk.red('ID number cannot be empty')) : true}}, {type:'input'.name:'address'.message:'Please enter your address'.default:'unknown'
},
{
type:'input'.name:'telephone'.message:'Please enter your phone number'})}export async function confirm(){
return await inquirer.prompt([{
type:"confirm".name:"continueOperation".message:chalk.blue('Continue? '),
default:true})}export async function search(){
return await inquirer.prompt([
{
type:"input".name:'id'.message:chalk.greenBright('Please enter id number for enquiry:'),
validate(value){
return! value.length ?new Error(chalk.red('ID number cannot be empty')) : true}})}export async function modify(){
return await inquirer.prompt([
{
type:'input'.name:'name'.message:'Please enter your name'.default:"Zhang"
},
{
type:'input'.name:'age'.message:'Please enter age'.default:'18'
},
{
type:'confirm'.name:'sex'.message:'What's your gender? '}, {type:'input'.name:'address'.message:'Please enter your address'.default:'unknown'
},
{
type:'input'.name:'telephone'.message:'Please enter your phone number'})}export async function signout(){
return await inquirer.prompt([
{
type:'confirm'.message:chalk.green('Exit or not'),
name:'logout'})}Copy the codeWhen MODULarization was carried out in the process of writing, direct export was used at the beginning, instead of async and await, resulting in inconsistent with the expected command line prompt questions. Later, I tried callback method, but it was easy to create callback hell when writing. Since Inquirer directly supports promise, I wrote this way.
A quick explanation:
In main.ts, I created subprocesses for operation.ts and index.ts. Operation. ts is used for binary tree operations and index.ts is used for table printing. I also started another child process, readwrite.ts, in operation.
This is also the first attempt to open a child within a child. The readwrite. ts process mainly reads and writes data. Json files.
Here’s the code:
// # src/child_process/operation.ts
import BST from '.. /BST'
import net from 'net'
import ChildProcess from 'child_process'
import path from 'path'
// Create a binary tree
const bst = new BST()
// Must use absolute path (in child process the current working file changed all relative path cannot find file)
const child=ChildProcess.fork(path.join(__dirname,'readWrite'))
// Establish TCP communication (client)
const client = net.createConnection({
port: 8000.host: 'localhost'
})
client.on('connect'.() = > {
// After the connection is established, the data is being manipulated
child.on('message'.(data:any) = >{
// Parse json strings into arrays
data=JSON.parse(data)
// Iterate over the array and insert each item into the tree
data.forEach(i= > {
bst.insert(i)
});
})
process.on('message'.(msg: any) = > {
if (msg.type == 'query') {
//console.log(msg.data)
const res1 = bst.search(msg.data)
let res = [];
res.push(res1)
client.write(JSON.stringify(res))
} else if (msg.type == 'Query all') {
// Save the sequential traversal data
const res = bst.inorderTraversal()
// Sends the data print table to child process 2
client.write(JSON.stringify(res))
} else if (msg.type == 'entry') {
// Perform an insert into the binary tree
msg.data.forEach(i= > {
bst.insert(i)
});
} else if (msg.type == 'delete') {
bst.delete(msg.data)
}else if (msg.type == 'change') {
/ / delete first
bst.delete(msg.data)
// Write again
/ / insert id
msg.IdData.id=msg.data
bst.insert(msg.IdData)
}else if (msg.type == 'save') {
// Sends a write file signal to the child process
let res:any=bst.inorderTraversal()
res=JSON.stringify(res,null.'\t')
child.send(res)
}
})
})
client.on('data'.(data) = > {
console.log(data.toString())
})
Copy the code// # src/child_process/readWrite.ts
import fs from 'fs'
import util from 'util'
import path from 'path'
const read=util.promisify(fs.readFile);
const write=util.promisify(fs.writeFile);
async function readFile(path:string){
return await read(path);
}
async function writeFile(path:string,data:any){
return await write(path,data);
}
let main=async() = > {let res=await readFile(path.join(__dirname,'.. /data.json'))
process.send(res.toString())
process.on('message'.async(msg:string) = > {await write(path.join(__dirname,'.. /data.json'),msg)
})
}
main()
Copy the code// # src/child_process/index.ts
import WordTable from 'word-table';
import chalk from 'chalk';
import net from 'net'
let header = [
"id"."name"."age"."sex"."telephone"."address"
]
let body = [];
// Establish TCP communication (server)
const server = net.createServer()
// Listen on port 8000
server.listen(8000)
server.on('connection'.socket= > {
// Receive data to print the table
socket.on('data'.(data) = > {
let msg = JSON.parse(data.toString())
msg.forEach(e= > {
let arr = [];
arr.push(e.id)
arr.push(e.name)
arr.push(e.age)
arr.push(e.sex)
arr.push(e.telephone)
arr.push(e.address)
body.push(arr)
});
const wt = new WordTable(header, body)
//console.log(chalk. Green (' Insert data successfully: '))
console.log(chalk.bgGray.yellow(wt.string()))
// Reset the body for the next print
body=[]
})
})
Copy the codeOperation effect:
The effect may be general, but I think the value, at least is their liver for two days to write good.
Third, summary
In this way, I spent two days to complete my course design, during which I found problems and solved them, which was both painful and joyful. I also found some problems of my own:
Typescript isn’t written well enough, so use AnyScript when using node’s built-in modules
Second, the data structure needs to be improved
There is much more to learn about Node execution and underlying Node
In this winter holiday, I will try my best to improve myself, and I hope to make some contributions to the community in the future.
If one day, when your efforts are worthy of your dreams, then your dreams will definitely not live up to your efforts. Make yourself as good as possible, when you work hard for one thing, the world will help you!
The author github:github.com/yexiyue