| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 12568 | Reverse Linked List ver 2 |
|
| 13410 | Blockchain |
|
Description
Given several operations, push x, pop, print, reverse, create a linked list dynamicly.
- push x: Add one Node (with data = x) at the front of linked list.
- pop: Delete the Node at the front of linked list.
- reverse: reverse the current linked list
- print: output the linked list in given format.
You have to implement 3 functions:
1. void Push(Node** ptr_head,int x)
2. void Pop(Node** ptr_head)
3. void Reverse_List(Node** ptr_head)
Note: Modify the Node* head by Node** ptr_head
Input
There’re operations on several lines.
All operations are one of push x, pop, print, reverse.
It’s guaranteed that:
- Number of operations is less than 5,000,000
- Integer x is in [−1000,1000]
- The maximum length of linked list is less than 10,000.
Output
Output the linked list for every print.
Sample Input Download
Sample Output Download
Partial Judge Code
12568.cPartial Judge Header
12568.hTags
Discuss
Description
Blockchain is a widely used data structure in the cryptocurrency field such as Bitcoin. Its structure is similar to a linked list. One major difference between them is that while the links of the linked list points to next node’s address, links of a blockchain points backward to its previous block’s “hash” value. For example:
Linked list: 
Blockchain: 
The links of blockchains points backward because it is designed to be an “append-only” data structure.
Now, let’s dig into more detail about a blockchain with a simple example of accounting book. The block data stores a collection of transaction records among Alice, Bob and Chris. The notation (A, B, X) means "A gives X dollars to B.” In this question, each block will store 2 records and we define the hash function
H(B) = (((sum(all transaction money in block B))2 ⊕ link(B)) + link(B)2) % 1000 + 1
, where link(B) is the hash value of B’s previous block. Note that ⊕ means the XOR operation.
The genesis block, or the first block has link(B)=NULL=0. With a series of transactions (stored in blockchain) and the initial savings (given in the test cases), we are able to calculate someone’s balance.
In this problem, you are asked to implement 3 functions:
- create a block
- query someone’s balance (Alice or Bob or Chris)
- the hash function
The following is "function.h". There're three structures. Transaction structure stores a single transaction (A, B, X). Block structure is a node presenting in the blockchain. Last, the block_chain structure means a block chain, such as bitcoin.
typedef struct {
char from[10];
char to[10];
int val;
}transaction;
typedef struct {
transaction t[2];
int link;
}block;
typedef struct {
block* block_data[1010];
int tail;
}block_chain;
// TODO: return the hash value of the given block
int hash(block* b);
// TODO: create a block with the given information and return its address
block* create_block(int currentTail, transaction t[2]);
// TODO: query someone's balance
int query(block_chain *bc, char name[10], int initial_saving);
The following is the block chain presents in the sample test case.
This problem is adapted from the midterm exam of Professor Ren-Song Tsay’s data structure course.
Input
The first line is a integer n which means there're n operations to do. (0 < n < 10)
For each operation, the command c is given first. c is either 0 or 1 or 2.
c = 0: Print the block chain, this function is provided in main.c.
c = 1: Create a new block. The two transactions are provided in the next two lines. The value of transaction is less than 100. You need to implement the create_block and hash function in this mode.
c = 2: Query somebody's balance. The name and his/her initial saving is provided in the next line. You need to implement the query function in this mode.
Output
If the command is 0, print the block chain.
If the command is 2, print the balance.
Chack the sample input and main.c for more details.