c语言实验二 单链表操作
实验内容
以单链表实现寝室同学的床号排序，每个同学的信息包含学号、姓名、年龄和床号
// 链表
const LinkList = function() {
this.head = null;
this.length = 0;
// 辅助类,创建节点
const Node = function(element) {
this.element = element;
this.next = null; //因为next用来存放对象，null是一个空的对象，因此这里使用空很合适
};
//在链表末尾添加元素
this.__proto__.append = function(element) {
const node = new Node(element);
if (this.head === null) {
this.head = node;
} else {
// 拿一个变量接收找到的最后一个节点,将添加的元素添加到最后一个节点的next属性
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = node;
}
this.length++;
};
// 获取链表的头
this.__proto__.getHead = function() {
return this.head;
};
//得到链表的长度
this.__proto__.size = function() {
return this.length;
};
// 往链表指定位置插入元素(下标位置position从0开始)
this.__proto__.insert = function(position, element) {
let node = new Node(element);
// 插入位置不能越界
if (position > -1 && position <= this.length) {
// 在开头插入元素,相当于交换(插入的node和head两个数)
if (position == 0) {
let current = this.head;
this.head = node;
this.head.next = current;
} else if (position == this.length) {
//在末尾的位置插入
this.append(element);
// 在append方法中新建了一个node,所以将这个作用域中的node赋值为null,释放内存
node = null;
// append方法中执行了this.length++
this.length--;
} else {
// previous插入坐标前一个节点 current当前插入坐标的节点
let previous = null;
let current = this.head;
let index = 0;
while (index < position) {
previous = current;
current = current.next;
index++;
}
previous.next = node;
node.next = current;
}
this.length++;
return true;
} else {
// return new Error("插入的下标位置越界了，不能这样");
return false;
}
};
//检查链表是否为空
this.__proto__.isEmpty = function() {
return this.length === 0;
};
//传入要删除某个位置下标的元素
this.__proto__.removeAt = function(position) {
// 越界问题
if (position > -1 && position < this.length) {
let current = this.head;
//删除链表第一个元素
if (position === 0) {
this.head = current.next;
} else {
//while循环退出条件是，查找到链表的index下标位置为position时，进行删除操作
let index = 0;
let previous = null;
// 查询
while (index < position) {
previous = current;
current = current.next;
index++;
}
// 当index == position时,删除
previous.next = current.next;
}
this.length--;
return current;
} else {
return false;
}
};
//获取指定element的下标position
this.__proto__.indexOf = function(element) {
let index = 0;
let current = this.head;
while (current) {
if (current.element == element) {
return index;
}
current = current.next;
index++;
}
return -1;
};
// 删除指定元素
this.__proto__.remove = function(element) {
return this.removeAt(this.indexOf(element));
};
// 更新指定position下标的节点
this.__proto__.update = function(position, element) {
if (this.get(position)) {
this.get(position).element = element;
return true;
}
return false;
};
// 获取指定position下标的节点
this.__proto__.get = function(position) {
// 越界判断
if (position > -1 && position < this.length) {
let current = this.head;
let index = 0;
while (index < position) {
current = current.next;
index++;
}
return current;
} else {
return false;
}
};
// 删除链表最后一个节点
this.__proto__.delete = function() {
this.removeAt(this.length - 1);
};
// 以数组的形式输出链表所有的值
this.__proto__.toArray = function() {
return (function reversePrint(head) {
if (head) {
if (head.next) {
return [...reversePrint(head.next), head.element]
}
return [head.element]
}
return []
})(this.head);
}
};
// 快排
Array.prototype.quickSort = function() {
// 交叉替换辅助函数
const swap = function(array, index1, index2) {
let arrCopy = array[index2];
array[index2] = array[index1];
array[index1] = arrCopy;
};
// 递归辅助函数
function quickSortRec(array) {
if (array.length === 1) {
return array;
}
const mid = array[Math.floor(array.length / 2)];
let leftIndex = 0;
let rightIndex = array.length - 1;
while (leftIndex < rightIndex) {
while (array[leftIndex].score < mid.score && leftIndex < rightIndex) {
leftIndex++;
}
while (array[rightIndex].score > mid.score && leftIndex < rightIndex) {
rightIndex--;
}
swap(array, leftIndex, rightIndex);
leftIndex++;
rightIndex--;
}
return quickSortRec(array.slice(0, Math.floor(array.length / 2))).concat(
quickSortRec(array.slice(Math.floor(array.length / 2), array.length))
);
}
return quickSortRec(this);
};
// 学生类
class Student {
constructor(name, sex, studentId, score) {
this.name = name;
this.sex = sex;
this.studentId = studentId;
this.score = score;
}
}
class Main {
constructor() {
// 男生组链表
this.maleLinkList = new LinkList();
// 女生组链表
this.femaleLinkList = new LinkList();
}
// 录入学生
entry(student) {
student.sex === 'male' ? this.maleLinkList.append(student) : this.femaleLinkList.append(student);
}
result() {
console.log(this.maleLinkList.toArray().quickSort());
console.log(this.femaleLinkList.toArray().quickSort());
}
}
const main = new Main();
let i = 0;
while (i < 10) {
main.entry(new Student(i, i % 2 === 0 ? "male" : "female", i, i));
i++;
}
main.result();
/*
输出结果
[
Student { name: 0, sex: 'male', studentId: 0, score: 0 },
Student { name: 2, sex: 'male', studentId: 2, score: 2 },
Student { name: 4, sex: 'male', studentId: 4, score: 4 },
Student { name: 6, sex: 'male', studentId: 6, score: 6 },
Student { name: 8, sex: 'male', studentId: 8, score: 8 }
]
[
Student { name: 1, sex: 'female', studentId: 1, score: 1 },
Student { name: 3, sex: 'female', studentId: 3, score: 3 },
Student { name: 5, sex: 'female', studentId: 5, score: 5 },
Student { name: 7, sex: 'female', studentId: 7, score: 7 },
Student { name: 9, sex: 'female', studentId: 9, score: 9 }
]
*/