数据结构与算法JavaScript描述练习------第3章列表
1. 增加一个向列表中插入元素的方法，该方法只在待插元素大于列表中的所有元素时才执 行插入操作。这里的大于有多重含义，对于数字，它是指数值上的大小；对于字母，它 是指在字母表中出现的先后顺序。
function isGreaterThan(a, b) {
if (typeof a === 'number' && typeof b === 'number') {
return a > b;
} else if (typeof a === 'string' && typeof b === 'string') {
return a.localeCompare(b) > 0;
} else {
throw new Error('Unsupported data type');
}
}
function insertIfGreaterThanAll(element) {
for (var i = 0; i < this.dataStore.length; i++) {
if (!isGreaterThan(element, this.dataStore[i])) {
return false;
}
}
this.append(element);
return true;
}2. 增加一个向列表中插入元素的方法，该方法只在待插元素小于列表中的所有元素时才执 行插入操作。
function isLessThan(a, b) {
if (typeof a === 'number' && typeof b === 'number') {
return a < b;
} else if (typeof a === 'string' && typeof b === 'string') {
return a.localeCompare(b) < 0;
} else {
throw new Error('Unsupported data type');
}
}
function insertIfLessThanAll(element) {
for (var i = 0; i < this.dataStore.length; i++) {
if (!isLessThan(element, this.dataStore[i])) {
return false;
}
}
this.append(element);
return true;
}3. 创建 Person 类，该类用于保存人的姓名和性别信息。创建一个至少包含 10 个 Person 对 象的列表。写一个函数显示列表中所有拥有相同性别的人。
function Person(name, gender) {
this.name = name;
this.gender = gender;
}
function displayPeopleByGender(peopleList, gender) {
for (peopleList.front(); peopleList.currPos() < peopleList.length(); peopleList.next()) {
if (peopleList.getElement().gender === gender) {
console.log(gender + "性：" + peopleList.getElement().name);
}
}
}
var list = new List();
list.append(new Person("张三", "男"));
list.append(new Person("李四", "女"));
list.append(new Person("王五", "男"));
list.append(new Person("赵六", "女"));
list.append(new Person("刘七", "男"));
list.append(new Person("陈八", "女"));
list.append(new Person("周九", "男"));
list.append(new Person("吴十", "女"));
list.append(new Person("郑十一", "男"));
list.append(new Person("孙十二", "女"));
displayPeopleByGender(list, "男");
displayPeopleByGender(list, "女");4. 修改本章的影碟租赁程序，当一部影片检出后，将其加入一个已租影片列表。每当有客 户检出一部影片，都显示该列表中的内容。
function checkOut(name, movie, filmList, customerList, rentList) {
if (filmList.contains(movie)) {
var c = new Customer(name, movie);
customerList.append(c);
rentList.append(movie);
filmList.remove(movie);
console.log("Rented movies: ");
displayList(rentList);
} else {
console.log(movie + " is not available.");
}
}5. 为影碟租赁程序创建一个 check-in() 函数，当客户归还一部影片时，将该影片从已租列 表中删除，同时添加到现有影片列表中。
function checkIn(name, movie, filmList, customerList, rentList) {
if (rentList.contains(movie)) {
rentList.remove(movie);
filmList.append(movie);
console.log(movie + " has been returned.\n");
console.log("rent movies: \n");
displayList(rentList);
for (customerList.front(); customerList.currPos() < customerList.length(); customerList.next()) {
if (customerList.getElement().movie == movie) {
customerList.remove(customerList.getElement());
}
}
console.log("\nCustomer Rentals: \n");
displayList(customers);
} else {
console.log(movie + " is not rented.\n");
}
}List不是JavaScript的内置类型，记录一下数组实现的List对象：
function List() {
this.listSize = 0;
this.pos = 0;
this.dataStore = [];
this.clear = clear;
this.find = find;
this.toString = toString;
this.insert = insert;
this.append = append;
this.remove = remove;
this.front = front;
this.end = end;
this.prev = prev;
this.next = next;
this.length = length;
this.currPos = currPos;
this.moveTo = moveTo;
this.getElement = getElement;
this.length = length;
this.contains = contains;
this.insertIfGreaterThanAll = insertIfGreaterThanAll;
this.insertIfLessThanAll = insertIfLessThanAll;
}
function append(element) {
this.dataStore[this.listSize++] = element;
}
function find(element) {
for (var i = 0; i < this.dataStore.length; ++i) {
if (this.dataStore[i] == element) {
return i;
}
}
return -1;
}
function remove(element) {
var foundAt = this.find(element);
if (foundAt > -1) {
this.dataStore.splice(foundAt,1);
--this.listSize;
return true;
}
return false;
}
function length() {
return this.listSize;
}
function toString() {
return this.dataStore;
}
function insert(element, after) {
var insertPos = this.find(after);
if (insertPos > -1) {
this.dataStore.splice(insertPos+1, 0, element);
++this.listSize;
return true;
}
return false;
}
function clear() {
delete this.dataStore;
this.dataStore = [];
this.listSize = this.pos = 0;
}
function contains(element) {
for (var i = 0; i < this.dataStore.length; ++i) {
if (this.dataStore[i] == element) {
//if (this.dataStore[i].indexOf(element) >= 0) {
return true;
}
}
return false;
}
function front() {
this.pos = 0;
}
function end() {
this.pos = this.listSize-1;
}
function prev() {
if (this.pos > 0) {
--this.pos;
}
}
function next() {
// if (this.pos < this.listSize-1) {
++this.pos;
// }
}
function currPos() {
return this.pos;
}
function moveTo(position) {
this.pos = position;
}
function getElement() {
return this.dataStore[this.pos];
}
function isGreaterThan(a, b) {
if (typeof a === 'number' && typeof b === 'number') {
return a > b;
} else if (typeof a === 'string' && typeof b === 'string') {
return a.localeCompare(b) > 0;
} else {
throw new Error('Unsupported data type');
}
}
function isLessThan(a, b) {
if (typeof a === 'number' && typeof b === 'number') {
return a < b;
} else if (typeof a === 'string' && typeof b === 'string') {
return a.localeCompare(b) < 0;
} else {
throw new Error('Unsupported data type');
}
}
function insertIfGreaterThanAll(element) {
for (var i = 0; i < this.dataStore.length; i++) {
if (!isGreaterThan(element, this.dataStore[i])) {
return false;
}
}
this.append(element);
return true;
}
function insertIfLessThanAll(element) {
for (var i = 0; i < this.dataStore.length; i++) {
if (!isLessThan(element, this.dataStore[i])) {
return false;
}
}
this.append(element);
return true;
}
var films = "The Shawshank Redemption（《肖申克的救赎》） \n\
The Godfather（《教父》） \n \
The Godfather: Part II（《教父 2》） \n\
Pulp Fiction（《低俗小说》） \n\
The Good, the Bad and the Ugly（《黄金三镖客》） \n\
12 Angry Men（《十二怒汉》 ） \n\
Schindler’s List（《辛德勒名单》） \n\
The Dark Knight（《黑暗骑士》） \n\
The Lord of the Rings: The Return of the King（《指环王：王者归来》） \n\
Fight Club（《搏击俱乐部》） \n\
Star Wars: Episode V - The Empire Strikes Back（《星球大战 5：帝国反击战》）\n\
One Flew Over the Cuckoo’s Nest（《飞越疯人院》） \n\
The Lord of the Rings: The Fellowship of the Ring（《指环王：护戒使者》） \n\
Inception（《盗梦空间》） \n\
Goodfellas（《好家伙》） \n\
Star Wars（《星球大战》） \n\
Seven Samurai（《七武士》） \n\
The Matrix（《黑客帝国》） \n\
Forrest Gump（《阿甘正传》） \n\
City of God（《上帝之城》） \n"
function createArr(file) {
var arr = file.split("\n");
for (var i = 0; i < arr.length; i++) {
arr[i] = arr[i].trim();
}
return arr;
}
function Customer(name, movie) {
this.name = name;
this.movie = movie;
}
function checkOut(name, movie, filmList, customerList, rentList) {
if (filmList.contains(movie)) {
var c = new Customer(name, movie);
customerList.append(c);
rentList.append(movie);
filmList.remove(movie);
console.log("Rented movies: ");
displayList(rentList);
} else {
console.log(movie + " is not available.");
}
}
function checkIn(name, movie, filmList, customerList, rentList) {
if (rentList.contains(movie)) {
rentList.remove(movie);
filmList.append(movie);
console.log(movie + " has been returned.\n");
console.log("rent movies: \n");
displayList(rentList);
for (customerList.front(); customerList.currPos() < customerList.length(); customerList.next()) {
if (customerList.getElement().movie == movie) {
customerList.remove(customerList.getElement());
}
}
console.log("\nCustomer Rentals: \n");
displayList(customers);
} else {
console.log(movie + " is not rented.\n");
}
}
function displayList(list) {
for (list.front(); list.currPos() < list.length(); list.next()) {
if (list.getElement() instanceof Customer) {
console.log(list.getElement()["name"] + ", " + list.getElement()["movie"]);
} else {
console.log(list.getElement());
}
}
}
var movies = createArr(films);
var movieList = new List();
var customers = new List();
var rentList = new List();
for (var i = 0; i < movies.length; i++) {
movieList.append(movies[i]);
}
console.log("Available movies: \n");
displayList(movieList);
checkOut("Jane Doe", "The Godfather（《教父》）", movieList, customers, rentList);
console.log("\nCustomer Rentals: \n");
displayList(customers);
console.log("\nAvailable movies: \n");
displayList(movieList);
console.log("\n-----------------------------------------------------\n");
checkIn("Jane Doe", "The Godfather（《教父》）", movieList, customers, rentList);
console.log("Available movies: \n");
displayList(movieList);