Jiangsu University of Science and Technology
Laboratory report on Data Structures
(1st semester of the academic year 2024/2025)
Student Name:
Student's school number:
Faculty: School of Computer Science
Specialization:
Appraisal Score:
December 2024
Experiment 1 Linear Table Operations
I. Purpose of the experiment
Master the implementation of the basic operations of linear tables on storage structures, with an emphasis on the operations of single linked tables.
II. Experimental topics
1. bysingle linked tableas a storage structure to realize in-place inversion of linear tables.
2. Create aNon-decreasing order (with repeating values) of a single linked table, which implements the deletion of redundant nodes with the same value.
III. core algorithm pseudo-code for experimental preliminaries
- Invert single-chained tables in place
reverseList(head):
prev = NULL
curr = head
while curr != NULL:
next =
= prev
prev = curr
curr = next
head = prev
Remove duplicate nodes
removeDuplicates(head):
current = head
while current != NULL:
runner = current
while != NULL:
if == :
=
else:
runner =
current =
IV. Experimental source program
invert a single linked table
#include
using namespace std;
struct Node {
int data;
Node* next;
Node(int value) : data(value), next(nullptr) {}
};
// Invert a single linked table
void reverseList(Node*& head) {
Node* prev = nullptr;
Node* curr = head;
Node* next = nullptr;
while (curr != nullptr) {
next = curr->next; // save the next node of the current node
curr->next = prev; // reverse the pointer to the current node
prev = curr; // prev moves forward
curr = next; // curr moves forward
}
head = prev; // update head pointer
}
// Print the linked list
void printList(Node* head) {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
int main() {
// Create a simple chained table: 1 -> 2 -> 3 -> 4
Node* head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(3);
head->next->next->next = new Node(4);
cout << "Original list: ";
printList(head);
reverseList(head);
cout << "Reversed list: ";
printList(head);
return 0;
}
Remove duplicate nodes
#include
using namespace std;
struct Node {
int data;
Node* next;
Node(int value) : data(value), next(nullptr) {}
};
// Remove duplicate nodes
void removeDuplicates(Node* head) {
Node* current = head;
while (current != nullptr) {
Node* runner = current;
while (runner->next != nullptr) {
if (runner->next->data == current->data) {
// Remove duplicate nodes
Node* temp = runner->next;
runner->next = runner->next->next;
delete temp;
} else {
runner = runner->next;
}
}
current = current->next;
}
}
// Print the linked list
void printList(Node* head) {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
int main() {
// Create a chained table with duplicate values: 1 -> 1 -> 2 -> 2 -> 3
Node* head = new Node(1);
head->next = new Node(1);
head->next->next = new Node(2);
head->next->next->next = new Node(2);
head->next->next->next->next = new Node(3);
cout << "Original list: ";
printList(head);
removeDuplicates(head);
cout << "List after removing duplicates: ";
printList(head);
return 0;
}
V. Experimental results and analysis (analysis of the causes of errors and debugging process, etc.)
-
Single linked table inversion:
- The final reversal of the order of a linked table is accomplished by traversing the table and inverting the pointers to each node. Careful pointer updating is required during the inversion operation to ensure that each node is correctly pointing to its predecessor.
- If the pointers are manipulated improperly (e.g., incorrectly updating prev, curr, or next), the chain table may break or the program may crash.
-
Remove duplicate nodes:
- Use double pointer method, current pointer is used to traverse the chain table and runner pointer is used to check if there is any duplicate node. If there is a duplicate element, the node is deleted directly.
- When deleting nodes, be careful to update the pointers, otherwise the chain table may break.
Sixth, the experimental experience (personalized summary of the experimental harvest, here avoid sets or reference, really do not think there is no gain, can not write; In addition, students with spare capacity to learn, in the part can be given with the content of the experiments related to the independent development of the content and results.)
- Basics of chained table operations:
- This experiment helped me to deepen my understanding of single linked tables, especially how to change the structure of a linked table through pointer operations. Pointer swapping in the inverse placement operation and pointer updating in the deletion of duplicate nodes are key in chain table operations.
- Challenges of the commissioning process:
- During my experiments, I encountered problems where improper pointer manipulation resulted in errors in the structure of the chain table. For example, forgetting to update the pointer when deleting a node can cause the chain table to break and not be traversed properly.
- Autonomous Expansion:
- By learning the basic operations of a chained table, I realized the power of the chained table structure. In the future, I can further investigate how to optimize the operations of a chain table, such as using a hash table when removing duplicate nodes to reduce the time complexity of traversal.
- Understanding of data structures:
- Through this experiment, I have a better understanding of the dynamics of chained tables and the basic principles of chained table operations. In my future study, I will continue to delve deeper into other chain table related operations, such as merging chain tables, sorting chain tables, and so on.
Experiment 2: Manipulation of stacks and queues
I. Purpose of the experiment
Master the storage structure, operational characteristics and implementation of stacks and queues.
II. Experimental topics
1. Let a sequence of integers be entered from the keyboard: a1, a2, …，an, write programs to achieve: usingchain storehousestructure stores the input integer when ai At ≠-1, the aiinto the stack; when ai=-At = -1, output the top-of-stack integer and exit the stack. The algorithm responds to exceptions with appropriate messages.
2. Set up withCircular chain table without head nodeindicateformationand only one pointer to the end node of the queue.
But do not set the header pointer. Write the corresponding queue-in and queue-out programs.
III. core algorithm pseudo-code for experimental preliminaries
- chain stack operation
- Definition of stack:
struct Node {
int data;
Node* next;
};
- Into the stack operation (push)
arduino
Copy Code
push(stack, value):
create a new node
new_node.data = value
new_node.next =
= new_node
- Out-of-stack operation (pop)
pop(stack):
if stack is empty:
output "Stack underflow" and return
top_node =
=
delete top_node
- circular chained list queue operation
- Definition of queue:
arduino
Copy Code
struct Node {
int data;
Node* next;
};
- Enqueue operation (enqueue)
enqueue(queue, value):
create a new node
new_node.data = value
if queue is empty:
new_node.next = new_node
= new_node
else:
new_node.next =
= new_node
= new_node
- Out-of-queue operation (dequeue)
dequeue(queue):
if queue is empty:
output "Queue underflow" and return
front_node =
if == :
= NULL // last element
else:
= front_node.next
delete front_node
IV. Experimental source program
chain stack implementation
#include
using namespace std;
// Chain stack node definition
struct Node {
int data;
Node* next;
};
// Chain stack class
class Stack {
private:
Node* top;
public:
Stack() : top(nullptr) {}
// Stacking operations
void push(int value) {
Node* newNode = new Node();
newNode->data = value;
newNode->next = top;
top = newNode;
cout << value << " pushed to stack" << endl;
}
// Out-of-stack operations
void pop() {
if (top == nullptr) {
cout << "Stack underflow!" << endl;
return;
}
Node* temp = top;
cout << "Popped from stack: " << top->data << endl;
top = top->next;
delete temp;
}
// Print Stack
void print() {
Node* temp = top;
if (temp == nullptr) {
cout << "Stack is empty" << endl;
return;
}
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};
int main() {
Stack s;
int num;
// Input data
cout << "Enter integers to push to the stack. Enter -1 to pop." << endl;
while (true) {
cout << "Enter an integer: ";
cin >> num;
if (num == -1) {
();
} else {
(num);
}
}
return 0;
}Cyclic Chained Table Queue Implementation
#include
using namespace std;
// Queue node definition
struct Node {
int data;
Node* next;
};
// Queue class
class Queue {
private:
Node* tail;
public:
Queue() : tail(nullptr) {}
// Queuing operation
void enqueue(int value) {
Node* newNode = new Node();
newNode->data = value;
if (tail == nullptr) {
newNode->next = newNode; // points to itself, indicating that there is only one element in the queue
tail = newNode;
} else {
newNode->next = tail->next;
tail->next = newNode;
tail = newNode;
}
cout << value << " enqueued to queue" << endl;
}
// Out of queue operation
void dequeue() {
if (tail == nullptr) {
cout << "Queue underflow!" << endl;
return;
}
Node* frontNode = tail->next;
if (tail == frontNode) { // there is only one element
tail = nullptr;
} else {
tail->next = frontNode->next;
}
cout << "Dequeued from queue: " << frontNode->data << endl;
delete frontNode;
}
// Print queue
void print() {
if (tail == nullptr) {
cout << "Queue is empty" << endl;
return;
}
**
Node* temp = tail->next;
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != tail->next);
cout << endl;
}
};
int main() {
Queue q;
int num;
// Input data
cout << "Enter integers to enqueue to the queue. Enter -1 to dequeue." << endl;
while (true) {
cout << "Enter an integer: ";
cin >> num;
if (num == -1) {
();
} else {
(num);
}
}
return 0;
}
V. Experimental results and analysis
- Chain Stack:
- Stacks are implemented to store data through chained storage, where new elements are inserted into the top of the stack when entering the stack and the top element is deleted when exiting the stack.
- Exception Handling: When the stack is empty, executing an out-of-stack operation triggers the Stack underflow prompt.
- Circular Chained Table Queue:
- A queue is implemented using a circular chain table. tail points to the last element of the queue, which is the head element. The queue-in operation inserts a new element into the tail of the queue, and the queue-out operation removes the head element.
- Exception Handling: When the queue is empty, performing a queue out operation triggers the Queue underflow prompt.
VI. Experimental experience
· Understanding of stacks and queues:
- This experiment deepened my understanding of stacks and queues, especially how chained storage implements these two data structures. Chained stacks and circular linked table queues are very efficient dynamic storage structures.
· Advantages of chained storage structure:
- Compared to sequential storage, chained storage structures are more dynamic in that they do not require a fixed size of memory to be allocated in advance for stack and queue operations.
· Debugging experience:
- The debugging process has encountered some pointer operation errors (such as improper updating of the pointer at the end of the circular chain table), by carefully checking the modification of the pointers, and gradually eliminating the problem, and finally successfully realized the function.
· Extension and Practice:
- Learn how to implement the basic operations of chained stacks and circular linked list queues, and be able to extend the implementation of other functions, such as the size of the queue to monitor, the minimum value of the stack to find, and so on.
Experiment 3 Binary Tree
I. Purpose of the experiment
Familiarize yourself with the structure of binary trees and master the operations and implementation of binary trees.
II. Experimental topics
Write a program to implement the following functions:
1. Create a binary tree with all values as integers (using binary chained table storage);
2. Output the sequence of preorder, midorder, and postorder traversals of the binary tree;
3. Modify all nodes with negative values to positive values.
III. core algorithm pseudo-code for experimental preliminaries
- The basic structure of a binary tree
- Each node contains: data field (int type) and two pointers (left subtree pointer, right subtree pointer).
cpp
Copy Code
struct TreeNode {
int data;
TreeNode *left;
TreeNode *right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
- Pre-order Traversal Pseudocode:
scss
Copy Code
PreOrderTraversal(root):
if root is not null:
visit(root)
PreOrderTraversal()
PreOrderTraversal()
- In-order Traversal Pseudocode:
scss
Copy Code
InOrderTraversal(root):
if root is not null:
InOrderTraversal()
visit(root)
InOrderTraversal()
- Post-order Traversal Pseudocode:
scss
Copy Code
PostOrderTraversal(root):
if root is not null:
PostOrderTraversal()
PostOrderTraversal()
visit(root)
- Modify all negative nodes to be positive Pseudocode:
kotlin
Copy Code
ModifyNegativeNodes(root):
if root is not null:
if < 0:
= -
ModifyNegativeNodes()
ModifyNegativeNodes()
IV. Experimental source program
#include
using namespace std;
// Binary tree node structure
struct TreeNode {
int data;
TreeNode *left, *right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
// Pre-order traversal
void PreOrderTraversal(TreeNode* root) {
if (root != nullptr) {
cout << root->data << " ";
PreOrderTraversal(root->left);
PreOrderTraversal(root->right);
}
}
// Intermediate order traversal
void InOrderTraversal(TreeNode* root) {
if (root != nullptr) {
InOrderTraversal(root->left);
cout << root->data << " ";
InOrderTraversal(root->right);
}
}
// Back-order traversal
void PostOrderTraversal(TreeNode* root) {
if (root != nullptr) {
PostOrderTraversal(root->left);
PostOrderTraversal(root->right);
cout << root->data << " ";
}
}
// Change all negative nodes to positive.
void ModifyNegativeNodes(TreeNode* root) {
if (root != nullptr) {
if (root->data < 0) {
root->data = -root->data;
}
ModifyNegativeNodes(root->left);
ModifyNegativeNodes(root->right);
}
}
// Create a simple binary tree
TreeNode* CreateSampleTree() {
TreeNode* root = new TreeNode(-1);
root->left = new TreeNode(2);
root->right = new TreeNode(-3);
root->left->left = new TreeNode(-4);
root->left->right = new TreeNode(5);
root->right->right = new TreeNode(-6);
return root;
}
int main() {
// Create a binary tree
TreeNode* root = CreateSampleTree();
// Output the result of the traversal
cout << "Pre-order traversal: ";.
PreOrderTraversal(root);
cout << endl;
cout << "Middle order traversal: ";.
InOrderTraversal(root);
cout << endl;
cout << "Posterior order traversal: ";.
PostOrderTraversal(root);
cout << endl;
// Change a negative node to a positive one
ModifyNegativeNodes(root);
cout << "Modified, preorder traversal: ";.
PreOrderTraversal(root);
cout << endl;
return 0;
}
V. Experimental results and analysis
- After modifying the negative node, the original negative values (e.g. -1, -4, -3, -6) are changed to the corresponding positive numbers (e.g. 1, 4, 3, 6).
- The output order of the three traversals (preorder, midorder, and postorder) is as expected and correctly reflects the structure of the binary tree.
VI. Experimental experience
- This experiment deepens the understanding of binary tree structure and traversal methods.
- In the process of implementation, some problems were encountered, such as the details of traversal order comprehension, but by consulting the information and continuous debugging, we finally mastered how to correctly implement the preorder, middle order and postorder traversal.
- The operation of modifying a negative number of nodes to a positive number also gave me a better understanding of recursion, which is a common and effective method for working with tree structures.
Experiment 4 Fig.
I. Purpose of the experiment
Familiarize yourself with the storage structure of graphs and master graph traversal and implementation.
II. Experimental topics
Write a program to implement the following functions:
1. Create an undirected graph (stored as an adjacency matrix or adjacency table);
2. Output a depth-first traversal sequence and a breadth-first traversal sequence starting at node 0, respectively.
III. core algorithm pseudo-code for experimental preliminaries
// Initialize the adjacency matrix
function initializeGraph(numNodes):
matrix = [[0 for i in range(numNodes)] for j in range(numNodes)]
return matrix
function DFS(graph, node, visited):
mark node as visited
print(node)
for each neighbor in graph[node]:
if neighbor is not visited:
DFS(graph, neighbor, visited)
function BFS(graph, startNode):
create a queue
enqueue startNode
mark startNode as visited
while queue is not empty:
node = dequeue from queue
print(node)
for each neighbor in graph[node]:
if neighbor is not visited:
enqueue neighbor
mark neighbor as visited
IV. Experimental source program
#include
#include
#include
using namespace std;
const int NUM_NODES = 6;
// Initialize the adjacency matrix of the graph
void initializeGraph(vector<vector
graph[0][1] = 1; graph[1][0] = 1;
graph[0][2] = 1; graph[2][0] = 1;
graph[1][2] = 1; graph[2][1] = 1;
graph[1][3] = 1; graph[3][1] = 1;
graph[2][4] = 1; graph[4][2] = 1;
graph[3][4] = 1; graph[4][3] = 1;
graph[3][5] = 1; graph[5][3] = 1;
graph[0][5] = 1; graph[5][0] = 1;
}
// Depth-first traversal (DFS)
void DFS(const vector<vector
visited[node] = true;
cout << node << " ";
for (int i = 0; i < NUM_NODES; ++i) {
if (graph[node][i] == 1 && !visited[i]) {
DFS(graph, i, visited);
}
}
}
// Breadth-first traversal (BFS)
void BFS(const vector<vector
vector
queue
(startNode);
visited[startNode] = true;
while (!()) {
int node = ();
();
cout << node << " ";
for (int i = 0; i < NUM_NODES; ++i) {
if (graph[node][i] == 1 && !visited[i]) {
(i);
visited[i] = true;
}
}
}
}
int main() {
vector<vector
initializeGraph(graph);
// Output a depth-first traversal sequence starting at node 0.
cout << "DFS traversal sequence starting at node 0: ";.
vector
DFS(graph, 0, visited);
cout << endl;
// Output a breadth-first traversal sequence starting at node 0.
cout << "BFS traversal sequence starting at node 0: ";.
BFS(graph, 0);
cout << endl;
return 0;
}
V. Experimental results and analysis
- DFS traverses the sequence (starting at node 0):
The output sequence may be: 0 1 2 4 3 5
- BFS traversal sequence (starting at node 0)
The output sequence may be: `0 1 2 50 1 2 5 3 4
VI. Experimental experience
This experiment stores the undirected graph by means of adjacency matrix so that each edge of the graph has a corresponding position in the matrix. It is understood that the adjacency matrix has a fixed size in the storage of graphs, which is suitable for the case of dense graphs.
Experiment 5 Find
I. Purpose of the experiment
Familiarize yourself with the basic process of lookup and master the techniques of designing common lookup algorithms.
II. Experimental topics
1. design a sequential lookup algorithm for sequential tables that locates the sentinel at the high end of the subscript.
2. Construct a binary sorted tree and output the values of all nodes in the tree whose values are greater than x from smallest to largest.
III. core algorithm pseudo-code for experimental preliminaries
- Pseudocode for sequential lookup algorithm (with sentinels):
less
Copy Code
function SequentialSearchWithSentinel(arr, target):
n = len(arr)
arr[n] = target // set target value to sentinel at end of array
i = 0
while arr[i] != target:
i = i + 1
if i < n:
return i // find target, return index
else:
return -1 // no target found, return -1
Description: By placing the target value at the end of the array, it avoids determining whether the target is the last element in each loop and optimizes efficiency.
- Binary sorted tree to find node values greater than x pseudocode:
php
Copy Code
function BSTFindGreaterThanX(root, x):
if root == null:
return
if > x:
BSTFindGreaterThanX(, x)
print() // output the current node value
BSTFindGreaterThanX(, x)
else:
BSTFindGreaterThanX(, x)
Note: A binary sort tree is characterized by a left subtree with values less than the root node and a right subtree with values greater than the root node. Therefore, when finding a value greater than x, we only need to visit the right subtree and the node that matches the condition.
IV. Experimental source program
- Sequential lookup algorithm implementation:
python
Copy Code
def SequentialSearchWithSentinel(arr, target):
n = len(arr)
(target) # Add the target value to the end as a sentinel
i = 0
while arr[i] != target:
i += 1
if i < n:
return i # find target, return index
else:
return -1 # No target found, return -1
# Testing sequential lookups
arr = [10, 20, 30, 40, 50]
target = 30
result = SequentialSearchWithSentinel(arr, target)
print(f"Target {target} found at index: {result}")
- Construction of binary sorted tree with finding node values greater than x implementation:
python
Copy Code
class TreeNode:
def __init__(self, value):
= value
= None
= None
def insert(root, value):
if root is None:
return TreeNode(value)
elif value < :
= insert(, value)
else:
= insert(, value)
return root
def BSTFindGreaterThanX(root, x):
if root is None:
return
if > x:
BSTFindGreaterThanX(, x)
print() # Output the current node value
BSTFindGreaterThanX(, x)
else:
BSTFindGreaterThanX(, x)
# Construct a binary sort tree
root = None
values = [20, 10, 30, 5, 15, 25, 35]
for value in values:
root = insert(root, value)
# Find nodes greater than 15
print("Nodes with values greater than 15:")
BSTFindGreaterThanX(root, 15)
V. Experimental results and analysis
-
Sequential lookup results:
- Input array: [10, 20, 30, 40, 50]
- Targets to be found: 30
- Output: Target 30 found at index: 2
- The results show that the sequential lookup is able to find the index location of the target element correctly and the efficiency of the lookup is slightly improved due to the use of the sentinel technique.
-
Binary sorted tree lookup results:
- Input binary sorted tree: contain node values [20, 10, 30, 5, 15, 25, 35]
- Finds nodes greater than 15:
- The results show that the binary sorted tree correctly outputs all nodes greater than a given value of 15 and the output is in ascending order.
VI. Experimental experience
Through this experiment, I have gained a deeper understanding of the lookup algorithm. The sequential lookup algorithm reduces the number of conditional judgments by introducing the sentinel technique, which makes the lookup process more efficient. The binary sorted tree, on the other hand, performs the lookup in the tree structure through recursion, which is able to quickly locate nodes larger than a certain value and output them in ascending order.
- Optimization of sequential lookup: by introducing sentinels, the sequential lookup process can be made more concise and efficient, avoiding the overhead of determining whether it is the last element each time.
- Advantages of binary sorted trees: binary sorted trees are able to efficiently prune and reduce unnecessary traversal based on the structure of the tree when looking for nodes larger than a certain value.
Overall, through this experiment, I deepened my understanding of lookup algorithms and improved my programming and problem analysis skills by implementing these algorithms.
Experiment 6 Sorting
I. Purpose of the experiment
Master the basic concepts of sorting and compare the process of designing algorithms based on sorting under different storage structures.
II. Experimental topics
Write programs for Direct Insertion Sort and Simple Selection Sort on a sequence of records to be sorted using a single linked table as the storage structure.
III. core algorithm pseudo-code for experimental preliminaries
- Direct Insertion Sort (Insertion Sort) Pseudo-Code
The key to implementing direct insertion sort in a linked list is the need to handle pointer operations between nodes.
python
Copy Code
function InsertionSort(head):
if head is None or is None:
return head // No sorting if the list is empty or has only one element.
**
sorted_head = None // Sorted section
current = head
while current is not None:
next_node = // save the next node of the current node
if sorted_head is None or sorted_head.value >= :
= sorted_head
sorted_head = current
else:
sorted_ptr = sorted_head
while sorted_ptr.next is not None and sorted_ptr. < :
sorted_ptr = sorted_ptr.next
= sorted_ptr.next
sorted_ptr.next = current
current = next_node
return sorted_head
Description : Direct insertion sort inserts the nodes of a linked table one by one into the sorted part. The current node is inserted into the appropriate position by adjusting the pointer each time the chain table is traversed.
- Simple Selection Sort (Selection Sort) Pseudo-Code
To implement selective sorting in a linked table, we need to find the smallest element in the currently unsorted section and move it to the end of the sorted section.
python
Copy Code
function SelectionSort(head):
if head is None or is None:
return head // No sorting if the list is empty or has only one element.
**
current = head
while current is not None:
min_node = current
runner =
while runner is not None:
if < min_node.value:
min_node = runner
runner =
**
// Swap the values of the current node and the smallest node
if min_node != current:
, min_node.value = min_node.value,
**
current =
return head
Description : Simple selection sort is done by selecting the smallest (or largest) element in an unsorted section and then moving it to the end of the sorted section. The swap operation here is accomplished by directly swapping the values of the nodes without swapping the pointers to the nodes.
IV. Experimental source program
class ListNode:
def __init__(self, value=0, next=None):
= value
= next
# Direct insertion sort
def InsertionSort(head):
if head is None or is None:
return head # If the list is empty or has only one element, no sorting is needed.
**
sorted_head = None # Sorted section
current = head
while current is not None:
next_node = # save the next node of the current node
if sorted_head is None or sorted_head.value >= :
= sorted_head
sorted_head = current
else:
sorted_ptr = sorted_head
while sorted_ptr.next is not None and sorted_ptr. < :
sorted_ptr = sorted_ptr.next
= sorted_ptr.next
sorted_ptr.next = current
current = next_node
return sorted_head
# Simple selection sort
def SelectionSort(head):
if head is None or is None:
return head # If the list is empty or has only one element, no sorting is needed.
**
current = head
while current is not None:
min_node = current
runner =
while runner is not None:
if < min_node.value:
min_node = runner
runner =
**
# Exchange the values of the current node and the smallest node
if min_node != current:
, min_node.value = min_node.value,
**
current =
return head
# Auxiliary function: print a linked list
def print_list(head):
current = head
while current:
print(, end=" -> ")
current =
print("None")
# Auxiliary Functions: Creating a Chained Table
def create_linked_list(values):
head = None
for value in reversed(values):
head = ListNode(value, head)
return head
# Test code
values = [4, 2, 1, 5, 3]
head = create_linked_list(values)
# A pre-sorting chained table
print("Original list:")
print_list(head)
# Use direct insertion sort
sorted_head = InsertionSort(head)
print("List after Insertion Sort:")
print_list(sorted_head)
# Re-create the chained table and use simple selection sorting
head = create_linked_list(values)
sorted_head = SelectionSort(head)
print("List after Selection Sort:")
print_list(sorted_head)
V. Experimental results and analysis
-
Test data:
- Input chain table: [4, 2, 1, 5, 3]
-
Direct insertion of sorted results:
- Pre-sort: 4 -> 2 -> 1 -> 5 -> 3 -> None
- Sorted: 1 -> 2 -> 3 -> 4 -> 5 -> None
-
Simple selection of sorted results:
- Pre-sort: 4 -> 2 -> 1 -> 5 -> 3 -> None
- Sorted: 1 -> 2 -> 3 -> 4 -> 5 -> None
Analysis:
- Direct Insertion Sort: Direct Insertion Sort ensures that each inserted node is in the correct position in the sorted section by constantly adjusting the pointer. For chained lists, the insertion operation is relatively simple and does not require moving elements, only adjusting pointers.
- Simple Selection Sort: Selection sort finds the smallest node of the remainder each time and swaps its value with the current node. Compared to direct insertion sort, selection sort is simpler to swap in a chained table implementation, only swapping the values of the nodes instead of adjusting the pointers.
VI. Experimental experience
Through this experiment, I have further understood how sorting algorithms are implemented and optimized in a chained table. When implementing sorting in a linked table, special attention needs to be paid to pointer manipulation to avoid damage to the structure of the linked table.
- direct insertion sortThe implementation in a chained table is relatively simple, inserting nodes into the sorted section one at a time via pointer adjustment.
- Simple Selection SortAlthough similar to the implementation in arrays, due to the structural nature of a linked list, the node exchange operation is limited to exchanging the values of the nodes rather than the positions of the nodes, reducing the complexity.