数据结构与算法@列表练习题

发表于 | 分类于 | 评论数： | 阅读次数：

概述

数据结构列表相关练习题。

详述

练习一

增加一个向列表中插入元素的方法，该方法只在待插元素大于列表中的所有元素时才执行插入操作。这里的大于有多重含义，对于数字，它是数值上的大小；对于字母，它是在字母表中出现的先后顺序。（代码见练习二）

练习二

增加一个向列表中插入元素的方法，该方法只在待插元素小于列表中的所有元素时才执行插入操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
// 练习一和练习二
class List {
  constructor() {
    this.listSize = 0;
    this.pos = 0;
    this.dataStore = []; //初始化一个空数组来保存列表元素
  }
  append(element) {
    this.dataStore[this.listSize++] = element;
  }
  find(element) {
    for (let i = 0; i < this.dataStore.length; i++) {
      if (this.dataStore[i] === element) {
        return i;
      }
    }
    return -1;
  }
  remove(element) {
    let foundAt = this.find(element);
    if (foundAt > -1) {
      this.dataStore.splice(foundAt, 1);
      this.listSize--;
      return true;
    }
    return false;
  }
  lenth() {
    return this.listSize;
  }
  toString() {
    return this.dataStore;
  }
  insert(element, after) {
    let insertPos = this.find(after);
    if (insertPos > -1) {
      this.dataStore.splice(insertPos, 0, element);
      this.listSize++;
      return true;
    }
    return false;
  }
  insertMax(element, after) {
    let isMax = this.dataStore.every(value => {
      if (/^[a-zA-Z]+$/.test(element) && /^[a-zA-Z]+$/.test(value)) {
        return element.charCodeAt(0) > value.charCodeAt(0);
      } else {
        return element > value;
      }
    });
    if (!isMax) {
      return;
    }
    this.insert(element, after);
  }
  insertMin(element, after) {
    let isMin = this.dataStore.every(value => {
      if (/^[a-zA-Z]+$/.test(element)) {
        return element.charCodeAt(0) < value.charCodeAt(0);
      } else {
        return element < value;
      }
    });
    if (!isMin) {
      return;
    }
    this.insert(element, after);
  }
  clear() {
    delete this.dataStore;
    this.dataStore.length = 0;
    this.listSize = this.pos = 0;
  }
  contains(element) {
    for (let i = 0; i < this.dataStore.length; i++) {
      if (this.dataStore[i] === element) {
        return true;
      }
    }
    return false;
  }
  front() {
    this.pos = 0;
  }
  end() {
    this.pos = this.listSize - 1;
  }
  prev() {
    this.pos--;
  }
  next() {
    this.pos++;
  }
  currPos() {
    return this.pos;
  }
  moveTo(position) {
    this.pos = position;
  }
  getElement() {
    return this.dataStore[this.pos];
  }
  hasNext() {
    return this.pos < this.listSize;
  }
  hasPrev() {
    return this.pos >= 0;
  }
}

// 练习一、二测试
let nums = new List();
nums.append(5);
nums.append(7);
nums.append(6);
nums.insertMax(10, 7);
nums.insertMax(4, 7);
nums.insertMin(1, 7);
nums.insertMin(15, 7);
console.log(nums);

let letterList = new List();
letterList.append("f");
letterList.insertMax("F", "f");
letterList.insertMax("z", "f");
console.log(letterList);

练习三

创建 Person 类，改类用于保存人的姓名和性别信息。创建一个至少包含 10 个 Person 对象的列表。写一个函数显示列表中所有拥有相同性别的人。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
class List {
  constructor() {
    this.listSize = 0;
    this.pos = 0;
    this.dataStore = []; //初始化一个空数组来保存列表元素
  }
  append(element) {
    this.dataStore[this.listSize++] = element;
  }
  find(element) {
    for (let i = 0; i < this.dataStore.length; i++) {
      if (this.dataStore[i] === element) {
        return i;
      }
    }
    return -1;
  }
  remove(element) {
    let foundAt = this.find(element);
    if (foundAt > -1) {
      this.dataStore.splice(foundAt, 1);
      this.listSize--;
      return true;
    }
    return false;
  }
  lenth() {
    return this.listSize;
  }
  toString() {
    return this.dataStore;
  }
  insert(element, after) {
    let insertPos = this.find(after);
    if (insertPos > -1) {
      this.dataStore.splice(insertPos, 0, element);
      this.listSize++;
      return true;
    }
    return false;
  }
  clear() {
    delete this.dataStore;
    this.dataStore.length = 0;
    this.listSize = this.pos = 0;
  }
  contains(element) {
    for (let i = 0; i < this.dataStore.length; i++) {
      if (this.dataStore[i] === element) {
        return true;
      }
    }
    return false;
  }
  front() {
    this.pos = 0;
  }
  end() {
    this.pos = this.listSize - 1;
  }
  prev() {
    this.pos--;
  }
  next() {
    this.pos++;
  }
  currPos() {
    return this.pos;
  }
  moveTo(position) {
    this.pos = position;
  }
  getElement() {
    return this.dataStore[this.pos];
  }
  hasNext() {
    return this.pos < this.listSize;
  }
  hasPrev() {
    return this.pos >= 0;
  }
}

// 定义客户类
class Person {
  constructor(name, sex) {
    this.name = name;
    this.sex = sex;
  }
  toString() {
    return "\nname: " + this.name + "@" + "sex: " + this.sex;
  }
}

let personList = new List();
for (let i = 0; i < 10; i++) {
  let name = "jovy_" + i;
  let sex = ["female", "male"][Math.round(Math.random())];
  const person = new Person(name, sex);
  personList.append(person);
}

function displayList(list, sex) {
  console.log("All: " + list.dataStore);
  let newList = list.dataStore.filter(element => {
    return element.sex === sex;
  });
  console.log("Filter: " + newList);
}

displayList(personList, "male");

练习四

修改本章的影碟租赁程序，当一部影片检出后，将其加入一个已租影片列表。每当有客户检出一部影片，都显示该列表中的内容。（代码见练习五）

练习五

为影碟租赁程序创建一个 check-in()函数，当客户归还一部影片时，将该影片从已租列表中删除，同时添加到现有影片列表中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
// 练习四和练习五
class List {
  constructor() {
    this.listSize = 0;
    this.pos = 0;
    this.dataStore = []; //初始化一个空数组来保存列表元素
  }
  append(element) {
    this.dataStore[this.listSize++] = element;
  }
  find(element) {
    for (let i = 0; i < this.dataStore.length; i++) {
      if (this.dataStore[i] === element) {
        return i;
      }
    }
    return -1;
  }
  remove(element) {
    let foundAt = this.find(element);
    if (foundAt > -1) {
      this.dataStore.splice(foundAt, 1);
      this.listSize--;
      return true;
    }
    return false;
  }
  lenth() {
    return this.listSize;
  }
  toString() {
    return this.dataStore;
  }
  insert(element, after) {
    let insertPos = this.find(after);
    if (insertPos > -1) {
      this.dataStore.splice(insertPos, 0, element);
      this.listSize++;
      return true;
    }
    return false;
  }
  clear() {
    delete this.dataStore;
    this.dataStore.length = 0;
    this.listSize = this.pos = 0;
  }
  contains(element) {
    for (let i = 0; i < this.dataStore.length; i++) {
      if (this.dataStore[i] === element) {
        return true;
      }
    }
    return false;
  }
  front() {
    this.pos = 0;
  }
  end() {
    this.pos = this.listSize - 1;
  }
  prev() {
    this.pos--;
  }
  next() {
    this.pos++;
  }
  currPos() {
    return this.pos;
  }
  moveTo(position) {
    this.pos = position;
  }
  getElement() {
    return this.dataStore[this.pos];
  }
  hasNext() {
    return this.pos < this.listSize;
  }
  hasPrev() {
    return this.pos >= 0;
  }
}

// 定义客户类
class Customer {
  constructor(name, movie) {
    this.name = name;
    this.movie = movie;
  }
  toString() {
    return this.name + "@" + this.movie;
  }
}
// 显示清单
function displayList(list) {
  for (list.front(); list.hasNext(); list.next()) {
    if (list.getElement() instanceof Customer) {
      console.log(
        list.getElement()["name"] + ", " + list.getElement()["movie"]
      );
    } else {
      console.log(list.getElement());
    }
  }
}

// 检出电影
function checkOut(name, movie, movieList, customerList, checkOutMovieList) {
  if (movieList.contains(movie)) {
    let c = new Customer(name, movie);
    customerList.append(c);
    movieList.remove(movie);
    // 练习4
    checkOutMovieList.append(movie);
    console.log("\nCheckOutMovieList: \n");
    displayList(checkOutMovieList);
  } else {
    console.log(movie + " is not available.");
  }
}
// 练习5
function checkIn(name, movie, movieList, customerList, checkOutMovieList) {
  let c = customerList.dataStore.find(element => {
    return element.name === name && element.movie === movie;
  });

  customerList.remove(c);
  movieList.append(movie);
  checkOutMovieList.remove(movie);
}

// 测试+++++++++++++++++++++++++++++++
// 模拟读取数据
let moviesStr =
  "肖申克的救赎，教父，教父2，低俗小说，黄金三镖客，十二怒汉，辛德勒名单，黑暗骑士，指环王：王者归来，搏击俱乐部，星球大战5：帝国反击战，飞越疯人院，指环王：护戒使者，盗梦空间，好家伙，星球大战，七武士，黑客帝国，阿甘正传，上帝之城";
let movies = moviesStr.split("，");

// 使用列表管理电影数据
let movieList = new List();
movies.forEach(element => {
  movieList.append(element);
});
// 使用列表管理客户数据
let customerList = new List();

let checkOutMovieList = new List();

console.log("Available movies: \n");
displayList(movieList);
checkOut("Jovysun", "教父", movieList, customerList, checkOutMovieList);
console.log("\nCustomer Rentals: \n");
displayList(customerList);
console.log("\nMovies Now Available\n");
displayList(movieList);

console.log("after check-in+++++++++++++++++++++++++++++++++++++++");
checkIn("Jovysun", "教父", movieList, customerList, checkOutMovieList);
console.log("\nCustomer Rentals: \n");
displayList(customerList);
console.log("\nMovies Now Available\n");
displayList(movieList);
console.log("\nCheckOutMovieList: \n");
displayList(checkOutMovieList);

参考

《数据结构与算法 JavaScript 描述》