#include <iostream> #include <cstdlib> #include <time.h> using namespace std; //#define LARGE_AMOUNT #ifdef LARGE_AMOUNT #define LOOP_COUNT 40000 #else #define LOOP_COUNT 40 #endif struct Student { int id; bool sex; char name[64]; Student* next; }; Student* head = nullptr; void addStudentToList(Student* s) { if (head == nullptr) { head = s; s->next = nullptr; } else if (s->id <= head->id) { s->next = head; head = s; } else { Student* f1 = head->next, * f2 = head; } //请填写程序 //以上两个分支都不成立,说明head指向某个元素,且s的id大于头元素id //现有数组已排好序,s应该插入到什么位置,才能维持顺序? //f1和f2分别指向链表中两个相邻的元素,这对于“插入”操作有什么帮助? } } int main() { clock_t startTime, endTime; startTime = clock(); for (int i = 0; i < LOOP_COUNT; i++) { Student* s = new Student; s->id = rand(); addStudentToList(s); } endTime = clock(); #ifndef LARGE_AMOUNT for (Student* p = head; p != nullptr; p = p->next) cout << p->id << " --> "; cout << endl; #endif Student* q, * p = head; while (p != nullptr) { q = p; p = p->next; delete q; } cout << "Time cost: " << endTime - startTime << endl; return 0; }
时间: 2024-01-29 18:02:03 浏览: 19
这段程序的功能是生成一个包含随机学号的链表,然后按照学号顺序插入节点。这里提供一份完整的代码,并解释其中的细节:
```c++
#include <iostream>
#include <cstdlib>
#include <time.h>
using namespace std;
#define LOOP_COUNT 40
struct Student {
int id;
bool sex;
char name[64];
Student* next;
};
Student* head = nullptr;
void addStudentToList(Student* s) {
if (head == nullptr) {
head = s;
s->next = nullptr;
}
else if (s->id <= head->id) {
s->next = head;
head = s;
}
else {
Student* f1 = head->next, * f2 = head;
while (f1 != nullptr && f1->id <= s->id) {
f2 = f1;
f1 = f1->next;
}
// 在f2和f1之间插入新节点
f2->next = s;
s->next = f1;
}
}
int main() {
srand(time(nullptr)); // 初始化随机数种子
clock_t startTime, endTime;
startTime = clock();
for (int i = 0; i < LOOP_COUNT; i++) {
Student* s = new Student;
s->id = rand();
addStudentToList(s);
}
endTime = clock();
// 遍历链表输出结果
for (Student* p = head; p != nullptr; p = p->next) {
cout << p->id << " --> ";
}
cout << endl;
// 释放链表内存空间
Student* q, * p = head;
while (p != nullptr) {
q = p;
p = p->next;
delete q;
}
cout << "Time cost: " << endTime - startTime << endl;
return 0;
}
```
在这个示例代码中,我们首先定义了一个 `Student` 结构体,包含学号、性别和姓名等信息,并且定义了一个 `addStudentToList` 函数,将新节点插入到链表中。在插入函数中,我们使用了三个指针:`head`、`f1` 和 `f2`,其中 `head` 指向链表头节点,`f1` 和 `f2` 分别指向链表中两个相邻的元素,这对于“插入”操作有很大的帮助。
在主函数中,我们使用 `srand` 函数初始化了随机数种子,然后循环生成 40 个随机学号的节点,并将它们插入到链表中。最后,我们遍历链表输出每个节点的学号,并释放了链表的内存空间,避免内存泄漏。
需要注意的是,在插入函数中,我们使用了一个 while 循环遍历链表,找到新节点需要插入的位置。如果插入位置在链表的头部或者链表为空,我们直接将新节点插入到头部;否则,我们需要在链表的中间插入节点。具体来说,我们使用两个指针 `f1` 和 `f2` 分别指向链表中两个相邻的元素,然后遍历链表,找到新节点需要插入的位置。最后,我们在 `f2` 和 `f1` 之间插入新节点。
最后,我们需要注意释放链表内存空间的操作,需要使用一个指针 `q` 暂存当前节点的指针,然后再将当前节点的指针指向下一个节点,最后释放 `q` 所指向的内存空间。