JavaScriptデータ構造とアルゴリズム-リスト練習

6830 ワード

実行リストクラス
//    
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.hasNext = hasNext;
    this.hasPrev = hasPrev;
    this.length = length;
    this.currPos = currPos; //          
    this.moveTo = moveTo;
    this.getElement = getElement; //          
    this.contains = contains;
}
// append:        
function append (element) {
    this.dataStore[this.listSize++] = element;
}
// find:            indexOf?
function find (element) {
    for (let i = 0; i < this.dataStore.length; i++) {
        if (this.dataStore[i] === element) {
            return i;
        }
    }
    return -1;
}
// remove:         
function remove (element) {
    let foundAt = this.find(element);
    if (foundAt > -1) {
        this.dataStore.splice(foundAt, 1);
        this.listSize--;
        return true;
    }
    return false;
}
// length:            listSize  ?
function length () {
    return this.listSize;
}
// toString:         
function toString () {
    return this.dataStore;
}
// insert:           
function insert (element, after) {
    let insertPos = this.find(after);
    if (insertPos > -1) {
        this.dataStore.splice(insertPos + 1, 0, element);
        this.listSize++;
        return true;
    }
    return false;
}
// clear:           
function clear () {
    delete this.dataStore;
    this.dataStore.length = 0;
    this.listSize = this.pos = 0;
}
// contains:             find?
function contains (element) {
    for (let i = 0; i < this.dataStore.length; i++) {
        if (this.dataStore[i] === element) {
            return true;
        }
    }
    return false;
}
//     
function front () {
    this.pos = 0;
}
function end () {
    this.pos = this.listSize - 1;
}
function prev () {
    --this.pos;
}
function next () {
    if (this.pos < this.listSize) {
        ++this.pos;
    }
}
function currPos () {
    return this.pos;
}
function moveTo (position) {
    this.pos = position;
}
function getElement () {
    return this.dataStore[this.pos];
}
function hasNext () {
    return this.pos < this.listSize;
}
function hasPrev () {
    return this.pos >= 0;
}
練習します
一.リストに要素を挿入する方法を追加します.この方法は、挿入要素がリストより大きいすべての要素に対してのみ実行されます.ここの大きさは複数の意味があり、数字に対しては指数の大きさです.アルファベットについては、アルファベットに表示される順序を指します.
List.prototype.insertThen = function (element) {
    let type = typeof element;
    if (type === `number`) {
        // debugger;
        for (let i = 0; i < this.dataStore.length; i++) {
            if (typeof this.dataStore[i] === `number` && element > this.dataStore[i]) { //                       
                this.append(element);
                return true;
            }
        }
    } else {
        let newArr = this.dataStore.filter((val) => {
            return typeof val !== `number`;
        }).concat([element]).sort();
        if (newArr.indexOf(element) === (newArr.length - 1)) {
            this.append(element);
            return true;
        }
    }
    return false;
};
//   
let DataThen = new List();
DataThen.append(`Mazey`);
DataThen.append(`Cherrie`);
DataThen.append(`Luna`);
DataThen.append(`John`);
DataThen.append(`July`);
DataThen.append(23);
DataThen.append(73);
console.log(DataThen.toString()); // ["Mazey", "Cherrie", "Luna", "John", "July", 23, 73]
DataThen.insertThen(99);
DataThen.insertThen(12);
console.log(DataThen.toString()); // ["Mazey", "Cherrie", "Luna", "John", "July", 23, 73, 99]
DataThen.insertThen(`Jay`);
DataThen.insertThen(`Zero`);
console.log(DataThen.toString()); // ["Mazey", "Cherrie", "Luna", "John", "July", 23, 73, 99, "Zero"]
二.リストに要素を挿入する方法を追加します.この方法は、挿入要素がリストのすべての要素より小さいときにのみ挿入操作を実行します.
List.prototype.insertThen = function (element) {
    let type = typeof element;
    if (type === `number`) {
        // debugger;
        for (let i = 0; i < this.dataStore.length; i++) {
            if (typeof this.dataStore[i] === `number` && element < this.dataStore[i]) { //                       
                this.append(element);
                return true;
            }
        }
    } else {
        let newArr = this.dataStore.filter((val) => {
            return typeof val !== `number`;
        }).concat([element]).sort();
        if (newArr.indexOf(element) === 0) {
            this.append(element);
            return true;
        }
    }
    return false;
};
//   
let DataThen = new List();
DataThen.append(`Mazey`);
DataThen.append(`Cherrie`);
DataThen.append(`Luna`);
DataThen.append(`John`);
DataThen.append(`July`);
DataThen.append(23);
DataThen.append(73);
console.log(DataThen.toString()); // ["Mazey", "Cherrie", "Luna", "John", "July", 23, 73]
DataThen.insertThen(99);
DataThen.insertThen(12);
console.log(DataThen.toString()); // ["Mazey", "Cherrie", "Luna", "John", "July", 23, 73, 12]
DataThen.insertThen(`Jay`);
DataThen.insertThen(`Zero`);
DataThen.insertThen(`Ada`);
console.log(DataThen.toString()); // ["Mazey", "Cherrie", "Luna", "John", "July", 23, 73, 12, "Ada"]
三.Person類を作成し、人間の名前と性別情報を保存するために使用します.少なくとも10個のPersonオブジェクトを含むリストを作成します.関数を書いて、同じ性別を持つすべての人を表示します.
function Person () {
    this.list = [];
    this.save = save;
    this.showSameGender = showSameGender;
}
//        
function save (name, gender) {
    let littleCase = {
        name,
        gender
    };
    this.list.push(littleCase);
}
//         
function showSameGender (gender) {
    let ret = [];
    let len = this.list.length;
    while (len--) {
        if (this.list[len].gender === gender) {
            ret.push(this.list[len].name);
        }
    }
    return ret;
}
//   
let people = new Person();
people.save(`Mazey`, `male`);
people.save(`John`, `male`);
people.save(`Zero`, `male`);
people.save(`July`, `male`);
people.save(`Bob`, `male`);
people.save(`Ada`, `female`);
people.save(`Cherrie`, `female`);
people.save(`Luna`, `female`);
people.save(`Lucy`, `female`);
people.save(`June`, `female`);
console.log(people.list);
console.log(people.showSameGender(`male`)); // ["Bob", "July", "Zero", "John", "Mazey"]
console.log(people.showSameGender(`female`)); // ["June", "Lucy", "Luna", "Cherrie", "Ada"]