不努力的话,天赋就会被收回

  menu

OJ作业-线性表和链表

2018级计算机科学与技术《数据结构与算法分析》第1次作业

问题 A: 线性表的建立

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            SeqList<Integer> s = new SeqList<Integer>();
            while(n > 0){
                s.add(sc.nextInt());
                n--;
            }
            System.out.println("遍历线性表为:" + s);
        }
    }
}

interface List<T> {
    boolean isEmpty();                      //  判断线性表是否为空

    int length();                           //  求线性表长度

    void clear();                           //  清空线性表

    void add(T elem);                       //  向表尾添加元素

    void addAll(List<? extends T> list);    //  合并两个表

    T get(int index);                       //  获得指定位置的值

    void insert(int index, T elem);         //  向指定位置插入元素

    void replace(int index, T elem);        //  替换指定位置的值

    int indexOf(T elem);                    //  返回元素在表中的位置

    T remove(int index);                    //  删除指定位置的值

    boolean contains(T elem);               //  判断值是否在表中
}

class SeqList<T> implements List<T> {

    private int defaultCapacity = 10;       //  默认容器大小
    private Object[] elemData;              //  存储元素的容器
    private int size;                       //  线性表长度

    public SeqList() {
        elemData = new Object[defaultCapacity];
    }

    public SeqList(int initialCapacity) {
        elemData = new Object[initialCapacity];
    }

    public SeqList(Object[] arr) {
        this.elemData = new Object[arr.length];
        System.arraycopy(arr, 0, elemData, 0, arr.length);
        size = arr.length - 1;
    }

    /**
     * 判空
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 获得表长
     * @return
     */
    public int length() {
        return size;
    }

    /**
     * 清空
     */
    public void clear() {
        elemData = new Object[defaultCapacity];
        size = 0;
    }

    public void add(T elem) {
        if (size > elemData.length) {
            throw new IndexOutOfBoundsException("顺序表已满!");
        }
        elemData[size++] = elem;
    }

    public void addAll(List<? extends T> list) {
        for (int i = 0; i < list.length(); i++) {
            insert(this.length(), list.get(i));
        }
    }

    /**
     * 获得顺序表指定位置的元素
     * @param index
     * @return
     */
    public T get(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException(index + "超出线性表范围");
        }
        return (T) elemData[index];
    }

    /**
     * 向指定位置插入元素,如果表满了,则进行扩容操作
     * @param index
     * @param elem
     */
    public void insert(int index, T elem) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException(index + "超出线性表范围");
        }
        Object[] objects = elemData;

        /**
         * 表满了,扩容
         */
        if (size == elemData.length) {
            elemData = new Object[objects.length * 2];
            for (int j = 0; j < index; j++) {
                this.elemData[j] = objects[j];
            }
        }
        for (int i = size - 1; i >= index; i--) {
            elemData[i + 1] = objects[i];
        }
        elemData[index] = elem;
        size++;
    }

    /**
     * 替换指定位置的元素
     * @param index
     * @param elem
     */
    public void replace(int index, T elem) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException(index + "超出线性表范围");
        }
        elemData[index] = elem;
    }

    /**
     * 获得指定元素第一次出现的位置
     * @param elem
     * @return
     */
    public int indexOf(T elem) {
        for (int i = 0; i < size; i++) {
            if (elemData[i].equals(elem)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 删除表中指定位置的元素
     * @param index
     * @return
     */
    public T remove(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException(index + "超出线性表范围");
        }
        T old = (T) this.elemData[index];
        for (int j = index; j < size - 1; j++) {
            this.elemData[j] = this.elemData[j + 1];
        }
        //将表的末尾元素置空
        this.elemData[this.size - 1] = null;
        size--;
        return old;
    }

    /**
     * 判断表中是否包含此元素
     * @param elem
     * @return
     */
    public boolean contains(T elem) {
        return indexOf(elem) != -1;
    }

    public Object[] toArray() {
        Object[] arr = new Object[this.length()];
        for (int i = 0; i < size; i++) {
            arr[i] = elemData[i];
        }
        return arr;
    }

    /**
     * 将线性表反转
     *
     * @param list
     * @return
     */
    public Object[] reverseList(Object[] list) {

        //计算出要移动元素的长度
        int len = list.length % 2 == 0 ? list.length / 2 : list.length / 2 + 1;
        for (int i = 0; i < len; i++) {
            Object temp = list[list.length - i - 1];
            list[list.length - i - 1] = list[i];
            list[i] = temp;
        }
        return list;
    }

    public String toString() {
        StringBuffer sb = new StringBuffer();
        sb.append(elemData[0]);
        for (int i = 1; i < this.size; i++)
            sb.append(" " + this.elemData[i]);
        return sb.toString();
    }

    public void Print(){
        for(int i = 0; i < this.size; i++){
            if(elemData[i] != null)
                System.out.println(elemData[i]);
        }
    }
}

问题 B: 人事档案

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sin = new Scanner(System.in);

        while (sin.hasNext()) {
            int n = sin.nextInt();
            if (n == 0) {
                break;
            }
            SqeList pList = new SqeList(n);
            for (int i = 0; i < n; i++) {
                Person per = new Person(sin.next(), sin.next(), sin.next(), sin.next(), sin.next());
                pList.insert(per);
            }
            int m = sin.nextInt();
            for (int i = 0; i < m; i++) {
                String s = sin.next();
                if ("L".equals(s)) {
                    System.out.println("L=" + pList.listSize());
                } else if ("Q".equals(s)) {
                    String l = sin.next();
                    System.out.println(pList.search(l));
                } else if ("G".equals(s)) {
                    String l = sin.next();
                    pList.remove(l);
                } else if ("I".equals(s)) {
                    Person per = new Person(sin.next(), sin.next(), sin.next(), sin.next(), sin.next());
                    pList.insert(per);
                } else if ("O".equals(s)) {
                    System.out.println("Show All Files:");
                    System.out.println(pList);
                }
            }
        }
    }
}

class Person {
    String No;
    String Name;
    String Sex;
    String Univerity;
    String Major;

    public Person(String No, String Name, String Sex, String Univerity, String Major) {
        this.Major = Major;
        this.Name = Name;
        this.No = No;
        this.Sex = Sex;
        this.Univerity = Univerity;
    }

    public String toString() {
        return this.No + " " + this.Name + " " + this.Sex + " " + this.Univerity + " " + this.Major;
    }
}

class SqeList {
    int Maxsize;
    int size;
    Person list[];

    public SqeList() {
        this(100);
    }

    public SqeList(int size) {
        Maxsize = size + 1;
        this.size = 0;
        list = new Person[size + 100];
    }

    public void clear() {
        size = 0;
    }

    public int listSize() {
        return size;
    }

    public void insert(Person per) {
        list[size++] = per;
    }

    public void sort() {
        Person person;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size - i - 1; j++) {
                if (list[j].No.compareTo(list[j + 1].No) > 0) {
                    person = list[j];
                    list[j] = list[j + 1];
                    list[j + 1] = person;
                }
            }
        }
    }

    public String search(String No) {
        for (int i = 0; i < size; i++) {
            if (list[i].No.equals(No)) {
                return list[i].No + " " + list[i].Name + " " + list[i].Sex + " " + list[i].Univerity + " " + list[i].Major;
            }
        }
        return "Can't find " + No;
    }

    public void remove(String No) {
        for (int i = 0; i < size; i++) {
            if (list[i].No.equals(No)) {
                for (int j = i; j < size - 1; j++) {
                    list[j] = list[j + 1];
                }
            }
        }
        size--;
    }

    public String toString() {
        StringBuffer SB = new StringBuffer();
        for (int i = 0; i < size; i++) {
            SB.append(list[i] + "\n");
        }
        return SB.toString();
    }
}

问题 C: 线性表的各种操作

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            if(n == 0){
                break;
            }
            SeqList<Integer> s = new SeqList<Integer>();
            while(n > 0){
                s.add(sc.nextInt());
                n--;
            }
            System.out.println("线性表里面的内容:" + s);
            int index = sc.nextInt();
            s.insert(index,sc.nextInt());
            System.out.println("线性表里面的内容:" + s);
            s.remove(sc.nextInt());
            System.out.println("线性表里面的内容:" + s);
            System.out.println();
        }
    }
}

interface List<T> {
    boolean isEmpty();                      //  判断线性表是否为空

    int length();                           //  求线性表长度

    void clear();                           //  清空线性表

    void add(T elem);                       //  向表尾添加元素

    void addAll(List<? extends T> list);    //  合并两个表

    T get(int index);                       //  获得指定位置的值

    void insert(int index, T elem);         //  向指定位置插入元素

    void replace(int index, T elem);        //  替换指定位置的值

    int indexOf(T elem);                    //  返回元素在表中的位置

    T remove(int index);                    //  删除指定位置的值

    boolean contains(T elem);               //  判断值是否在表中
}

class SeqList<T> implements List<T> {

    private int defaultCapacity = 10;       //  默认容器大小
    private Object[] elemData;              //  存储元素的容器
    private int size;                       //  线性表长度

    public SeqList() {
        elemData = new Object[defaultCapacity];
    }

    public SeqList(int initialCapacity) {
        elemData = new Object[initialCapacity];
    }

    public SeqList(Object[] arr) {
        this.elemData = new Object[arr.length];
        System.arraycopy(arr, 0, elemData, 0, arr.length);
        size = arr.length - 1;
    }

    /**
     * 判空
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 获得表长
     * @return
     */
    public int length() {
        return size;
    }

    /**
     * 清空
     */
    public void clear() {
        elemData = new Object[defaultCapacity];
        size = 0;
    }

    public void add(T elem) {
        if (size > elemData.length) {
            throw new IndexOutOfBoundsException("顺序表已满!");
        }
        elemData[size++] = elem;
    }

    public void addAll(List<? extends T> list) {
        for (int i = 0; i < list.length(); i++) {
            insert(this.length(), list.get(i));
        }
    }

    /**
     * 获得顺序表指定位置的元素
     * @param index
     * @return
     */
    public T get(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException(index + "超出线性表范围");
        }
        return (T) elemData[index];
    }

    /**
     * 向指定位置插入元素,如果表满了,则进行扩容操作
     * @param index
     * @param elem
     */
    public void insert(int index, T elem) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException(index + "超出线性表范围");
        }
        Object[] objects = elemData;

        /**
         * 表满了,扩容
         */
        if (size == elemData.length) {
            elemData = new Object[objects.length * 2];
            for (int j = 0; j < index; j++) {
                this.elemData[j] = objects[j];
            }
        }
        for (int i = size - 1; i >= index; i--) {
            elemData[i + 1] = objects[i];
        }
        elemData[index] = elem;
        size++;
    }

    /**
     * 替换指定位置的元素
     * @param index
     * @param elem
     */
    public void replace(int index, T elem) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException(index + "超出线性表范围");
        }
        elemData[index] = elem;
    }

    /**
     * 获得指定元素第一次出现的位置
     * @param elem
     * @return
     */
    public int indexOf(T elem) {
        for (int i = 0; i < size; i++) {
            if (elemData[i].equals(elem)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 删除表中指定位置的元素
     * @param index
     * @return
     */
    public T remove(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException(index + "超出线性表范围");
        }
        T old = (T) this.elemData[index];
        for (int j = index; j < size - 1; j++) {
            this.elemData[j] = this.elemData[j + 1];
        }
        //将表的末尾元素置空
        this.elemData[this.size - 1] = null;
        size--;
        return old;
    }

    /**
     * 判断表中是否包含此元素
     * @param elem
     * @return
     */
    public boolean contains(T elem) {
        return indexOf(elem) != -1;
    }

    public Object[] toArray() {
        Object[] arr = new Object[this.length()];
        for (int i = 0; i < size; i++) {
            arr[i] = elemData[i];
        }
        return arr;
    }

    /**
     * 将线性表反转
     *
     * @param list
     * @return
     */
    public Object[] reverseList(Object[] list) {

        //计算出要移动元素的长度
        int len = list.length % 2 == 0 ? list.length / 2 : list.length / 2 + 1;
        for (int i = 0; i < len; i++) {
            Object temp = list[list.length - i - 1];
            list[list.length - i - 1] = list[i];
            list[i] = temp;
        }
        return list;
    }

    public String toString() {
        StringBuffer sb = new StringBuffer();
        sb.append(elemData[0]);
        for (int i = 1; i < this.size; i++)
            sb.append("," + this.elemData[i]);
        return sb.toString();
    }

    public void Print(){
        for(int i = 0; i < this.size; i++){
            if(elemData[i] != null)
                System.out.println(elemData[i]);
        }
    }
}

问题 D: 线性表的比较和合并

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int m = sc.nextInt();
            int n = sc.nextInt();
            if(m == 0 && n == 0){
                break;
            }
            SeqList<Integer> s1 = new SeqList<Integer>(m);
            SeqList<Integer> s2 = new SeqList<Integer>(n);
            for(int i = 0; i < m; i++){
                s1.add(sc.nextInt());
            }
            for(int i = 0; i < n; i++){
                s2.add(sc.nextInt());
            }
            if(s1.equals(s2)){
                System.out.println("相等");
            }else {
                System.out.println("不相等");
            }
            System.out.println("合并后:" + s1.mergeTwoLists(s2));
        }
    }
}

interface List<T> {
    boolean isEmpty();                      //  判断线性表是否为空

    int length();                           //  求线性表长度

    void clear();                           //  清空线性表

    void add(T elem);                       //  向表尾添加元素

    void addAll(List<? extends T> list);    //  合并两个表

    T get(int index);                       //  获得指定位置的值

    void insert(int index, T elem);         //  向指定位置插入元素

    void replace(int index, T elem);        //  替换指定位置的值

    int indexOf(T elem);                    //  返回元素在表中的位置

    T remove(int index);                    //  删除指定位置的值

    boolean contains(T elem);               //  判断值是否在表中
}

class SeqList<T> implements List<T> {

    private int defaultCapacity = 10;       //  默认容器大小
    private Object[] elemData;              //  存储元素的容器
    private int size;                       //  线性表长度

    public SeqList() {
        elemData = new Object[defaultCapacity];
    }

    public SeqList(int initialCapacity) {
        elemData = new Object[initialCapacity];
    }

    public SeqList(Object[] arr) {
        this.elemData = new Object[arr.length];
        System.arraycopy(arr, 0, elemData, 0, arr.length);
        size = arr.length;
    }

    /**
     * 判空
     *
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 获得表长
     *
     * @return
     */
    public int length() {
        return size;
    }

    /**
     * 清空
     */
    public void clear() {
        elemData = new Object[defaultCapacity];
        size = 0;
    }

    public void add(T elem) {
        if (size > elemData.length) {
            throw new IndexOutOfBoundsException("顺序表已满!");
        }
        elemData[size++] = elem;
    }

    public void addAll(List<? extends T> list) {
        for (int i = 0; i < list.length(); i++) {
            insert(this.length(), list.get(i));
        }
    }
    
    public SeqList<T> mergeTwoLists(SeqList<T> s){
        Object[] obj = new Object[this.size + s.length()];
        System.arraycopy(this.toArray(),0,obj,0,this.size);
        System.arraycopy(s.toArray(),0,obj,size,s.toArray().length);
        SeqList<T> newList = new SeqList<T>(obj);
        return newList;
    }

    public boolean equals(SeqList<T> s) {
        if (this.size != s.length()) {
            return false;
        }
        for (int i = 0; i < this.size; i++) {
            if (!this.get(i).equals(s.get(i))) {
                return false;
            }
        }
        return true;
    }

    /**
     * 获得顺序表指定位置的元素
     *
     * @param index
     * @return
     */
    public T get(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException(index + "超出线性表范围");
        }
        return (T) elemData[index];
    }

    /**
     * 向指定位置插入元素,如果表满了,则进行扩容操作
     *
     * @param index
     * @param elem
     */
    public void insert(int index, T elem) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException(index + "超出线性表范围");
        }
        Object[] objects = elemData;

        /**
         * 表满了,扩容
         */
        if (size == elemData.length) {
            elemData = new Object[objects.length * 2];
            for (int j = 0; j < index; j++) {
                this.elemData[j] = objects[j];
            }
        }
        for (int i = size - 1; i >= index; i--) {
            elemData[i + 1] = objects[i];
        }
        elemData[index] = elem;
        size++;
    }

    /**
     * 替换指定位置的元素
     *
     * @param index
     * @param elem
     */
    public void replace(int index, T elem) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException(index + "超出线性表范围");
        }
        elemData[index] = elem;
    }

    /**
     * 获得指定元素第一次出现的位置
     *
     * @param elem
     * @return
     */
    public int indexOf(T elem) {
        for (int i = 0; i < size; i++) {
            if (elemData[i].equals(elem)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 删除表中指定位置的元素
     *
     * @param index
     * @return
     */
    public T remove(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException(index + "超出线性表范围");
        }
        T old = (T) this.elemData[index];
        for (int j = index; j < size - 1; j++) {
            this.elemData[j] = this.elemData[j + 1];
        }
        //将表的末尾元素置空
        this.elemData[this.size - 1] = null;
        size--;
        return old;
    }

    /**
     * 判断表中是否包含此元素
     *
     * @param elem
     * @return
     */
    public boolean contains(T elem) {
        return indexOf(elem) != -1;
    }

    public Object[] toArray() {
        Object[] arr = new Object[this.length()];
        for (int i = 0; i < size; i++) {
            arr[i] = elemData[i];
        }
        return arr;
    }

    /**
     * 将线性表反转
     *
     * @param list
     * @return
     */
    public Object[] reverseList(Object[] list) {

        //计算出要移动元素的长度
        int len = list.length % 2 == 0 ? list.length / 2 : list.length / 2 + 1;
        for (int i = 0; i < len; i++) {
            Object temp = list[list.length - i - 1];
            list[list.length - i - 1] = list[i];
            list[i] = temp;
        }
        return list;
    }

    public String toString() {
        StringBuffer sb = new StringBuffer();
        sb.append(elemData[0]);
        for (int i = 1; i < this.size; i++)
            sb.append(" " + this.elemData[i]);
        return sb.toString();
    }

    public void Print() {
        for (int i = 0; i < this.size; i++) {
            if (elemData[i] != null)
                System.out.println(elemData[i]);
        }
    }
}

问题 E: 约瑟夫环

C++版本

#include<iostream>
#include<iomanip>
#include<string>
#include<stdlib.h>
#include<vector>
#include<list>
#include<map>
#include<stack>
#include<queue>
using namespace std;
class Point {
public:
    int x;
    int y;
public:
    Point(int x, int y) :x(x), y(y) {};
};
void Josephus(int m, int n, int q) {
    queue<Point> Pointqueue;
    queue<int> Shuqueue;
    int k;
    int l = 1;
    for (int i = 1; i <= m; i++) {
        cin >> k;
        Point *point = new Point(i, k);
        Pointqueue.push(*point);
    }
    for (int i = 1; i < n; i++) {
        Point *point = new Point(Pointqueue.front().x, Pointqueue.front().y);
        Pointqueue.pop();
        Pointqueue.push(*point);
    }
    Shuqueue.push(Pointqueue.front().x);
    while (!Pointqueue.empty()) {
        Point p = Pointqueue.front();
        Pointqueue.pop();
        if (!Pointqueue.empty()) {
            for (int i = 1; i < p.y; i++) {
                Point *point = new Point(Pointqueue.front().x, Pointqueue.front().y);
                Pointqueue.pop();
                Pointqueue.push(*point);
            }
        }
        if (!Pointqueue.empty()) {
            Shuqueue.push(Pointqueue.front().x);
        }
    }
    cout << "Case " << (q++) << ":";
    while (!Shuqueue.empty()) {
        if (l == 1) {
            cout << Shuqueue.front();
            Shuqueue.pop();
        }
        else {
            cout << "->" << Shuqueue.front();
            Shuqueue.pop();
        }
        l++;
    }
    cout << endl;
}
int main() {
    int count;
    int m;
    int n;
    while (cin >> count) {
        queue<Point> Pointqueue;
        queue<int> Shuqueue;
        int q = 1;
        while (count > 0) {
            cin >> m;
            cin >> n;
            Josephus(m, n, q++);
            count--;
       }
    }
}

Java版本

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            for (int k = 1; k <= n; k++) {
                int a = sc.nextInt();
                int b = sc.nextInt();
                SinglyLinkedList<Position> s = new SinglyLinkedList<Position>();
                for (int i = 1; i <= a; i++) {
                    s.addLast(new Position(i, sc.nextInt()));
                }
                System.out.print("Case " + k + ":");
                Josephus(b, s);
            }
        }
    }

    private static void Josephus(int val, SinglyLinkedList<Position> s) {
        if (s.getsize() == 1) {
            System.out.println(s.removeHead().index);
            return;
        }else{
            Position p = null;
            for (int i = 1; i < val; i++) {
                p = s.removeHead();
                s.addLast(p);
            }
            p = s.removeHead();
            System.out.print(p.index + "->");
            Josephus(p.val, s);
        }
    }
}

/**
 * 单链表实现
 *
 * @param <T>
 */
class SinglyLinkedList<T extends Comparable<? super T>> {

    private Node<T> head;          //  指向链表头结点
    private Node<T> tail;          //  指向链表尾结点
    private int size;              //  链表长度

    public SinglyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    /**
     * 向链表头部添加元素
     *
     * @param val
     */
    public void addFirst(T val) {
        Node<T> new_node = new Node<T>(val, null);
        if (!isEmpty()) {
            new_node.next = head;
            head = new_node;
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 向链表尾部添加元素
     *
     * @param val
     */
    public void addLast(T val) {
        Node<T> new_node = new Node<T>(val, null);
        if (!isEmpty()) {
            Node<T> p_node = head;
            while (p_node.next != null) {
                p_node = p_node.next;
            }
            p_node.next = new_node;
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 有序添加元素(自定义升序排序)
     *
     * @param val
     */
    public void add(T val) {
        Node<T> new_node = new Node<T>(val, null);
        if (!isEmpty()) {
            if (this.tail.item.compareTo(new_node.item) <= 0) {
                tail.next = new_node;
                tail = tail.next;
            } else {
                if (new_node.item.compareTo(head.item) < 0) {
                    new_node.next = head;
                    head = new_node;
                } else {
                    Node<T> p_node = this.head;
                    Node<T> q_node = p_node;
                    while (p_node != null) {
                        if (new_node.item.compareTo(p_node.item) <= 0) {
                            break;
                        }
                        q_node = p_node;
                        p_node = p_node.next;
                    }
                    new_node.next = p_node;
                    q_node.next = new_node;
                }
            }
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 插入指定位置
     *
     * @param index
     * @param val
     */
    public void insert(int index, T val) {
        Node<T> new_node = new Node<T>(val, null);
        if (isEmpty()) {
            head = new_node;
        } else {
            if (index > size + 1) {
                System.out.println("下标超限");
            } else {
                Node<T> pre = findIndex(index - 1);
                new_node.next = pre.next;
                pre.next = new_node;
            }
        }
        size++;
    }

    /**
     * 查找指定位置的结点
     *
     * @param index
     * @return
     */
    public Node<T> findIndex(int index) {
        int i = 1;
        Node<T> p = head;
        while (p != null) {
            if (i == index) {
                return p;
            }
            i++;
            p = p.next;
        }
        return null;
    }

    /**
     * 寻找链表中指定结点
     *
     * @param val
     * @return
     */
    public Node<T> find(T val) {
        Node<T> x = this.head;
        Node<T> t = new Node<T>(val, null);
        while (x != null) {
            if (x.item.compareTo(t.item) == 0) {
                return x;
            }
            x = x.next;
        }
        return null;
    }

    public T removeHead() {
        T obj = this.head.item;
        this.head = head.next;
        size--;
        return obj;
    }

    /**
     * 判断链表中是否含有指定的Val
     *
     * @param val
     * @return
     */
    public boolean containsVal(T val) {
        Node<T> p_node = this.head;
        Node<T> q_node = new Node<T>(val, null);
        while (p_node != null) {
            if (p_node.item.compareTo(q_node.item) == 0) {
                return true;
            }
            p_node = p_node.next;
        }
        return false;
    }

    /**
     * 反转链表
     *
     * @param head
     * @return 反转后的头指针
     */
    public Node<T> reverseList(Node<T> head) {
        Node<T> new_head = null;
        while (head != null) {
            Node<T> p = head.next;
            head.next = new_head;
            new_head = head;
            head = p;
        }
        return new_head;
    }

    /**
     * 删除链表中重复元素
     *
     * @return 删除重复元素后的头指针
     */
    public Node<T> deleteDuplicates() {
        Node<T> current = this.head;
        while (current != null && current.next != null) {
            if (current.item.compareTo(current.next.item) == 0) {
                current.next = current.next.next;
                size--;
            } else {
                current = current.next;
            }
        }
        return head;
    }

    /**
     * 删除链表中指定元素
     *
     * @param head
     * @param val
     * @return
     */
    public void remove(T val) {
        Node<T> dummyNode = new Node<T>(val, null);
        dummyNode.next = head;
        Node<T> prev = dummyNode;
        while (prev.next != null) {
            if (prev.next.item.compareTo(dummyNode.item) == 0) {
                prev.next = prev.next.next;
                size--;
            } else {
                prev = prev.next;
            }
        }
    }

    /**
     * 合并两个有序链表(迭代)
     *
     * @param l1
     * @param l2
     * @return 合并后的头结点
     */
    public Node<T> mergeTwoLists(Node<T> l1, Node<T> l2) {
        Node<T> prehead = new Node<T>();
        Node<T> prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.item.compareTo(l2.item) <= 0) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }

    /**
     * 将链表以数组的形式返回
     *
     * @return
     */
    public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
        for (Node<T> x = head; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }

    /**
     * 判断链表是否为空
     *
     * @return head == null
     */
    private boolean isEmpty() {
        return this.head == null;
    }

    public Node<T> getHead() {
        return head;
    }

    public Node<T> getTail() {
        return tail;
    }

    public int getsize() {
        return size;
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        Node<T> p_node = this.head;
        while (p_node != null) {
            sb.append(p_node.item + "\n");
            p_node = p_node.next;
        }
        return sb.toString();
    }

    public void Print() {
        Node<T> p = this.head;
        while (p != null) {
            System.out.println(p.item);
            p = p.next;
        }
    }

    /**
     * 节点类
     *
     * @param <T>
     */
    private class Node<T> {
        T item;
        Node<T> next;

        public Node() {
        }

        public Node(T item, Node<T> next) {
            this.item = item;
            this.next = next;
        }
    }
}

class Position implements Comparable<Position> {
    int index;
    int val;

    public Position(int index, int val) {
        this.index = index;
        this.val = val;
    }

    @Override
    public int compareTo(Position o) {
        return 0;
    }
}

问题 F: 人事档案(有序)

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sin = new Scanner(System.in);

        while (sin.hasNext()) {
            int n = sin.nextInt();
            if (n == 0) {
                break;
            }
            SqeList pList = new SqeList(n);
            for (int i = 0; i < n; i++) {
                Person per = new Person(sin.next(), sin.next(), sin.next(), sin.next(), sin.next());
                pList.insert(per);
            }
            int m = sin.nextInt();
            for (int i = 0; i < m; i++) {
                String s = sin.next();
                if ("L".equals(s)) {
                    System.out.println("L=" + pList.listSize());
                } else if ("Q".equals(s)) {
                    String l = sin.next();
                    System.out.println(pList.search(l));
                } else if ("G".equals(s)) {
                    String l = sin.next();
                    pList.remove(l);
                } else if ("I".equals(s)) {
                    Person per = new Person(sin.next(), sin.next(), sin.next(), sin.next(), sin.next());
                    pList.insert(per);
                } else if ("O".equals(s)) {
                    System.out.println("Show All Files:");
                    pList.sort();
                    System.out.println(pList);
                }
            }
        }
    }
}

class Person {
    String No;
    String Name;
    String Sex;
    String Univerity;
    String Major;

    public Person(String No, String Name, String Sex, String Univerity, String Major) {
        this.Major = Major;
        this.Name = Name;
        this.No = No;
        this.Sex = Sex;
        this.Univerity = Univerity;
    }

    public String toString() {
        return this.No + " " + this.Name + " " + this.Sex + " " + this.Univerity + " " + this.Major;
    }
}

class SqeList {
    int Maxsize;
    int size;
    Person list[];

    public SqeList() {
        this(100);
    }

    public SqeList(int size) {
        Maxsize = size + 1;
        this.size = 0;
        list = new Person[size + 100];
    }

    public void clear() {
        size = 0;
    }

    public int listSize() {
        return size;
    }

    public void insert(Person per) {
        list[size++] = per;
    }

    public void sort() {
        Person person;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size - i - 1; j++) {
                if (list[j].No.compareTo(list[j + 1].No) > 0) {
                    person = list[j];
                    list[j] = list[j + 1];
                    list[j + 1] = person;
                }
            }
        }
    }

    public String search(String No) {
        for (int i = 0; i < size; i++) {
            if (list[i].No.equals(No)) {
                return list[i].No + " " + list[i].Name + " " + list[i].Sex + " " + list[i].Univerity + " " + list[i].Major;
            }
        }
        return "Can't find " + No;
    }

    public void remove(String No) {
        for (int i = 0; i < size; i++) {
            if (list[i].No.equals(No)) {
                for (int j = i; j < size - 1; j++) {
                    list[j] = list[j + 1];
                }
            }
        }
        size--;
    }

    public String toString() {
        StringBuffer SB = new StringBuffer();
        for (int i = 0; i < size; i++) {
            SB.append(list[i] + "\n");
        }
        return SB.toString();
    }
}

问题 G: 集合的运算

import java.util.Scanner;
import java.util.Queue;
 
public class Main {
    public static void main(String[] args) {
        Scanner sin = new Scanner(System.in);
        while (sin.hasNext()) {
            int m = sin.nextInt();
            int n = sin.nextInt();
            int ppzA[] = new int[m];
            int ppzB[] = new int[n];
            for (int i = 0; i < m; i++) {
                ppzA[i] = sin.nextInt();
            }
            for (int i = 0; i < n; i++) {
                ppzB[i] = sin.nextInt();
            }
            SqeList A = new SqeList(ppzA, m);
            SqeList B = new SqeList(ppzB, n);
            System.out.println("A与B的交集为" + A.Intersection(B));
            System.out.println("A与B的并集为" + A.Union(B));
            System.out.println("A与B的差集为" + A.DifferenceSet(B));
        }
        sin.close();
    }
}
 
interface List {
    public SqeList Intersection(SqeList s);
 
    public SqeList Union(SqeList s);
 
    public SqeList DifferenceSet(SqeList s);
}
 
class SqeList implements List {
    private int arrays[];
    private int length;
 
    public SqeList() {
        arrays = new int[100];
        length = 0;
    }
 
    public SqeList(int arrays[], int length) {
        this.arrays = arrays;
        this.length = length;
    }
 
    public SqeList Intersection(SqeList B) {
        SqeList s = new SqeList();
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < B.length; j++) {
                if (arrays[i] == B.arrays[j]) {
                    s.arrays[s.length++] = arrays[i];
                }
            }
        }
        return s;
    }
 
    public SqeList Union(SqeList B) {
        SqeList s = new SqeList();
        for (int i = 0; i < arrays.length; i++) {
            s.arrays[s.length++] = arrays[i];
        }
        for (int i = 0; i < B.length; i++) {
            s.arrays[s.length++] = B.arrays[i];
        }
        for (int i = 0; i < s.length; i++) {
            for (int j = i + 1; j < s.length; j++) {
                if (s.arrays[j] == s.arrays[i]) {
                    for (int k = j; k < s.length; k++) {
                        s.arrays[k] = s.arrays[k + 1];
                    }
                    s.length--;
                }
            }
        }
        SqeList a = Sort(s);
        return a;
    }
 
    public SqeList Sort(SqeList s) {
        for (int i = 0; i < s.length; i++) {
            for (int j = 0; j < s.length - i - 1; j++) {
                if (s.arrays[j] > s.arrays[j + 1]) {
                    int temp = s.arrays[j];
                    s.arrays[j] = s.arrays[j + 1];
                    s.arrays[j + 1] = temp;
                }
            }
        }
        return s;
    }
 
    public SqeList DifferenceSet(SqeList B) {
        SqeList c = new SqeList();
        for (int i = 0; i < length; i++) {
            int j = 0;
            for (j = 0; j < B.length; j++) {
                if (arrays[i] == B.arrays[j]) {
                    break;
                }
            }
            if (j == B.length) {
                c.arrays[c.length++] = arrays[i];
            }
        }
 
        return c;
    }
 
    public String toString() {
        StringBuilder sb = new StringBuilder("{");
        for (int i = 0; i < length - 1; i++) {
            sb.append(arrays[i] + ",");
        }
        if (length > 0) {
            sb.append(arrays[length - 1] + "}");
        } else {
            sb.append("}");
        }
        return sb.toString();
    }
}

2018级计算机科学与技术《数据结构与算法分析》第2次作业

问题 A: 链表的建立

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            SinglyLinkedList<Student> s = new SinglyLinkedList<Student>();
            while(n > 0){
                s.addLast(new Student(sc.next(),sc.next(),sc.next(),sc.next()));
                n--;
            }
            System.out.print(s);
        }
    }
}

/**
 * 单链表实现
 * @param <T>
 */
class SinglyLinkedList<T extends Comparable<? super T>> {

    private Node<T> head;          //  指向链表头结点
    private Node<T> tail;          //  指向链表尾结点
    private int size;              //  链表长度

    public SinglyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    /**
     * 向链表头部添加元素
     *
     * @param val
     */
    public void addFirst(T val) {
        Node<T> new_node = new Node<T>(val, null);
        if (!isEmpty()) {
            new_node.next = head;
            head = new_node;
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 向链表尾部添加元素
     *
     * @param val
     */
    public void addLast(T val) {
        Node<T> new_node = new Node<T>(val, null);
        if (!isEmpty()) {
            tail.next = new_node;
            tail = tail.next;
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 有序添加元素(自定义升序排序)
     *
     * @param val
     */
    public void add(T val) {
        Node<T> new_node = new Node<T>(val, null);
        if (!isEmpty()) {
            if (this.tail.item.compareTo(new_node.item) <= 0) {
                tail.next = new_node;
                tail = tail.next;
            } else {
                Node<T> p_node = this.head;
                Node<T> q_node = p_node;
                while (p_node != null) {
                    if (new_node.item.compareTo(p_node.item) < 0) {
                        break;
                    }
                    q_node = p_node;
                    p_node = p_node.next;
                }
                new_node.next = p_node;
                q_node.next = new_node;
            }
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 插入指定位置
     *
     * @param index
     * @param val
     */
    public void insert(int index, T val) {
        Node<T> new_node = new Node<T>(val, null);
        if (isEmpty()) {
            head = new_node;
        } else {
            if (index > size + 1) {
                System.out.println("下标超限");
            } else {
                Node<T> pre = findIndex(index - 1);
                new_node.next = pre.next;
                pre.next = new_node;
            }
        }
        size++;
    }

    /**
     * 查找指定位置的结点
     *
     * @param index
     * @return
     */
    public Node<T> findIndex(int index) {
        int i = 1;
        Node<T> p = head;
        while (p != null) {
            if (i == index) {
                return p;
            }
            i++;
            p = p.next;
        }
        return null;
    }

    /**
     * 寻找链表中指定结点
     *
     * @param val
     * @return
     */
    public Node<T> find(T val) {
        Node<T> x = this.head;
        Node<T> t = new Node<T>(val, null);
        while (x != null) {
            if (x.item.compareTo(t.item) == 0) {
                return x;
            }
            x = x.next;
        }
        return null;
    }

    /**
     * 判断链表中是否含有指定的Val
     *
     * @param val
     * @return
     */
    public boolean containsVal(T val) {
        Node<T> p_node = this.head;
        Node<T> q_node = new Node<T>(val, null);
        while (p_node != null) {
            if (p_node.item.compareTo(q_node.item) == 0) {
                return true;
            }
            p_node = p_node.next;
        }
        return false;
    }

    /**
     * 反转链表
     *
     * @param head
     * @return 反转后的头指针
     */
    public Node<T> reverseList(Node<T> head) {
        Node<T> new_head = null;
        while (head != null) {
            Node<T> p = head.next;
            head.next = new_head;
            new_head = head;
            head = p;
        }
        return new_head;
    }

    /**
     * 删除链表中重复元素
     *
     * @return 删除重复元素后的头指针
     */
    public Node<T> deleteDuplicates() {
        Node<T> current = this.head;
        while (current != null && current.next != null) {
            if (current.item.compareTo(current.next.item) == 0) {
                current.next = current.next.next;
                size--;
            } else {
                current = current.next;
            }
        }
        return head;
    }

    /**
     * 删除链表中指定元素
     *
     * @param head
     * @param val
     * @return
     */
    public void remove(T val) {
        Node<T> dummyNode = new Node<T>(val, null);
        dummyNode.next = head;
        Node<T> prev = dummyNode;
        while (prev.next != null) {
            if (prev.next.item == val) {
                prev.next = prev.next.next;
            } else {
                prev = prev.next;
            }
        }
    }

    /**
     * 合并两个有序链表(迭代)
     *
     * @param l1
     * @param l2
     * @return 合并后的头结点
     */
    public Node<T> mergeTwoLists(Node<T> l1, Node<T> l2) {
        Node<T> prehead = new Node<T>();
        Node<T> prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.item.compareTo(l2.item) <= 0) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }

    /**
     * 将链表以数组的形式返回
     *
     * @return
     */
    public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
        for (Node<T> x = head; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }

    /**
     * 判断链表是否为空
     *
     * @return head == null
     */
    private boolean isEmpty() {
        return this.head == null;
    }

    public Node<T> getHead() {
        return head;
    }

    public Node<T> getTail() {
        return tail;
    }

    public int getsize() {
        return size;
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        Node<T> p_node = this.head;
        while (p_node != null) {
            sb.append(p_node.item + "\n");
            p_node = p_node.next;
        }
        return sb.toString();
    }

    public void Print(){
        Node<T> p = this.head;
        while(p != null){
            System.out.println(p.item);
            p = p.next;
        }
    }

    /**
     * 节点类
     * @param <T>
     */
    private class Node<T>{
        T item;
        Node<T> next;

        public Node() {
        }

        public Node(T item, Node<T> next) {
            this.item = item;
            this.next = next;
        }
    }
}

class Student implements Comparable<Student> {
    private String num;
    private String sex;
    private String name;
    private String come_from;

    public Student() {
    }

    public Student(String num, String sex, String name, String come_from) {
        this.num = num;
        this.sex = sex;
        this.name = name;
        this.come_from = come_from;
    }

    public String getNum() {
        return num;
    }

    public void setNum(String num) {
        this.num = num;
    }

    public String getSex() {
        return sex;
    }

    public void setSex(String sex) {
        this.sex = sex;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getCome_from() {
        return come_from;
    }

    public void setCome_from(String come_from) {
        this.come_from = come_from;
    }

    @Override
    public String toString() {
        return this.num + " " + this.sex + " " + this.name + " " + this.come_from;
    }

    @Override
    public int compareTo(Student o) {
//        return (int)(Long.parseLong(this.num) - Long.parseLong(o.getNum()));
        return 0;
    }
}

问题 B: 链表的插入

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            SinglyLinkedList<Student> s = new SinglyLinkedList<Student>();
            while(n > 0){
                s.add(new Student(sc.next(),sc.next(),sc.next(),sc.next()));
                n--;
            }
            System.out.print(s);
        }
    }
}

/**
 * 单链表实现
 * @param <T>
 */
class SinglyLinkedList<T extends Comparable<? super T>> {

    private Node<T> head;          //  指向链表头结点
    private Node<T> tail;          //  指向链表尾结点
    private int size;              //  链表长度

    public SinglyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    /**
     * 向链表头部添加元素
     *
     * @param val
     */
    public void addFirst(T val) {
        Node<T> new_node = new Node<T>(val, null);
        if (!isEmpty()) {
            new_node.next = head;
            head = new_node;
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 向链表尾部添加元素
     *
     * @param val
     */
    public void addLast(T val) {
        Node<T> new_node = new Node<T>(val, null);
        if (!isEmpty()) {
            tail.next = new_node;
            tail = tail.next;
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 有序添加元素(自定义升序排序)
     *
     * @param val
     */
    public void add(T val) {
        Node<T> new_node = new Node<T>(val, null);
        if (!isEmpty()) {
            if (this.tail.item.compareTo(new_node.item) <= 0) {
                tail.next = new_node;
                tail = tail.next;
            } else {
                Node<T> p_node = this.head;
                Node<T> q_node = p_node;
                while (p_node != null) {
                    if (new_node.item.compareTo(p_node.item) < 0) {
                        break;
                    }
                    q_node = p_node;
                    p_node = p_node.next;
                }
                new_node.next = p_node;
                q_node.next = new_node;
            }
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 插入指定位置
     *
     * @param index
     * @param val
     */
    public void insert(int index, T val) {
        Node<T> new_node = new Node<T>(val, null);
        if (isEmpty()) {
            head = new_node;
        } else {
            if (index > size + 1) {
                System.out.println("下标超限");
            } else {
                Node<T> pre = findIndex(index - 1);
                new_node.next = pre.next;
                pre.next = new_node;
            }
        }
        size++;
    }

    /**
     * 查找指定位置的结点
     *
     * @param index
     * @return
     */
    public Node<T> findIndex(int index) {
        int i = 1;
        Node<T> p = head;
        while (p != null) {
            if (i == index) {
                return p;
            }
            i++;
            p = p.next;
        }
        return null;
    }

    /**
     * 寻找链表中指定结点
     *
     * @param val
     * @return
     */
    public Node<T> find(T val) {
        Node<T> x = this.head;
        Node<T> t = new Node<T>(val, null);
        while (x != null) {
            if (x.item.compareTo(t.item) == 0) {
                return x;
            }
            x = x.next;
        }
        return null;
    }

    /**
     * 判断链表中是否含有指定的Val
     *
     * @param val
     * @return
     */
    public boolean containsVal(T val) {
        Node<T> p_node = this.head;
        Node<T> q_node = new Node<T>(val, null);
        while (p_node != null) {
            if (p_node.item.compareTo(q_node.item) == 0) {
                return true;
            }
            p_node = p_node.next;
        }
        return false;
    }

    /**
     * 反转链表
     *
     * @param head
     * @return 反转后的头指针
     */
    public Node<T> reverseList(Node<T> head) {
        Node<T> new_head = null;
        while (head != null) {
            Node<T> p = head.next;
            head.next = new_head;
            new_head = head;
            head = p;
        }
        return new_head;
    }

    /**
     * 删除链表中重复元素
     *
     * @return 删除重复元素后的头指针
     */
    public Node<T> deleteDuplicates() {
        Node<T> current = this.head;
        while (current != null && current.next != null) {
            if (current.item.compareTo(current.next.item) == 0) {
                current.next = current.next.next;
                size--;
            } else {
                current = current.next;
            }
        }
        return head;
    }

    /**
     * 删除链表中指定元素
     *
     * @param head
     * @param val
     * @return
     */
    public void remove(T val) {
        Node<T> dummyNode = new Node<T>(val, null);
        dummyNode.next = head;
        Node<T> prev = dummyNode;
        while (prev.next != null) {
            if (prev.next.item == val) {
                prev.next = prev.next.next;
            } else {
                prev = prev.next;
            }
        }
    }

    /**
     * 合并两个有序链表(迭代)
     *
     * @param l1
     * @param l2
     * @return 合并后的头结点
     */
    public Node<T> mergeTwoLists(Node<T> l1, Node<T> l2) {
        Node<T> prehead = new Node<T>();
        Node<T> prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.item.compareTo(l2.item) <= 0) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }

    /**
     * 将链表以数组的形式返回
     *
     * @return
     */
    public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
        for (Node<T> x = head; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }

    /**
     * 判断链表是否为空
     *
     * @return head == null
     */
    private boolean isEmpty() {
        return this.head == null;
    }

    public Node<T> getHead() {
        return head;
    }

    public Node<T> getTail() {
        return tail;
    }

    public int getsize() {
        return size;
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        Node<T> p_node = this.head;
        while (p_node != null) {
            sb.append(p_node.item + "\n");
            p_node = p_node.next;
        }
        return sb.toString();
    }

    public void Print(){
        Node<T> p = this.head;
        while(p != null){
            System.out.println(p.item);
            p = p.next;
        }
    }

    /**
     * 节点类
     * @param <T>
     */
    private class Node<T>{
        T item;
        Node<T> next;

        public Node() {
        }

        public Node(T item, Node<T> next) {
            this.item = item;
            this.next = next;
        }
    }
}

class Student implements Comparable<Student> {
    private String num;
    private String sex;
    private String name;
    private String come_from;

    public Student() {
    }

    public Student(String num, String sex, String name, String come_from) {
        this.num = num;
        this.sex = sex;
        this.name = name;
        this.come_from = come_from;
    }

    public String getNum() {
        return num;
    }

    public void setNum(String num) {
        this.num = num;
    }

    public String getSex() {
        return sex;
    }

    public void setSex(String sex) {
        this.sex = sex;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getCome_from() {
        return come_from;
    }

    public void setCome_from(String come_from) {
        this.come_from = come_from;
    }

    @Override
    public String toString() {
        return this.num + " " + this.sex + " " + this.name + " " + this.come_from;
    }

    @Override
    public int compareTo(Student o) {
        return (int)(Long.parseLong(this.num) - Long.parseLong(o.getNum()));
//        return 0;
    }
}

问题 C: 链表的合并

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            SinglyLinkedList<Book> s = new SinglyLinkedList<Book>();
            while(n > 0){
                s.add(new Book(sc.next(),sc.next()));
                n--;
            }
            int m = sc.nextInt();
            while(m > 0){
                s.add(new Book(sc.next(),sc.next()));
                m--;
            }

            System.out.print(s);
        }
    }
}

/**
 * 单链表实现
 * @param <T>
 */
class SinglyLinkedList<T extends Comparable<? super T>> {

    private Node<T> head;          //  指向链表头结点
    private Node<T> tail;          //  指向链表尾结点
    private int size;              //  链表长度

    public SinglyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    /**
     * 向链表头部添加元素
     *
     * @param val
     */
    public void addFirst(T val) {
        Node<T> new_node = new Node<T>(val, null);
        if (!isEmpty()) {
            new_node.next = head;
            head = new_node;
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 向链表尾部添加元素
     *
     * @param val
     */
    public void addLast(T val) {
        Node<T> new_node = new Node<T>(val, null);
        if (!isEmpty()) {
            tail.next = new_node;
            tail = tail.next;
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 有序添加元素(自定义升序排序)
     *
     * @param val
     */
    public void add(T val) {
        Node<T> new_node = new Node<T>(val, null);
        if (!isEmpty()) {
            if (this.tail.item.compareTo(new_node.item) <= 0) {
                tail.next = new_node;
                tail = tail.next;
            } else {
                if(new_node.item.compareTo(head.item) < 0){
                    new_node.next = head;
                    head = new_node;
                }else{
                    Node<T> p_node = this.head;
                    Node<T> q_node = p_node;
                    while (p_node != null) {
                        if (new_node.item.compareTo(p_node.item) <= 0) {
                            break;
                        }
                        q_node = p_node;
                        p_node = p_node.next;
                    }
                    new_node.next = p_node;
                    q_node.next = new_node;
                }
            }
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 插入指定位置
     *
     * @param index
     * @param val
     */
    public void insert(int index, T val) {
        Node<T> new_node = new Node<T>(val, null);
        if (isEmpty()) {
            head = new_node;
        } else {
            if (index > size + 1) {
                System.out.println("下标超限");
            } else {
                Node<T> pre = findIndex(index - 1);
                new_node.next = pre.next;
                pre.next = new_node;
            }
        }
        size++;
    }

    /**
     * 查找指定位置的结点
     *
     * @param index
     * @return
     */
    public Node<T> findIndex(int index) {
        int i = 1;
        Node<T> p = head;
        while (p != null) {
            if (i == index) {
                return p;
            }
            i++;
            p = p.next;
        }
        return null;
    }

    /**
     * 寻找链表中指定结点
     *
     * @param val
     * @return
     */
    public Node<T> find(T val) {
        Node<T> x = this.head;
        Node<T> t = new Node<T>(val, null);
        while (x != null) {
            if (x.item.compareTo(t.item) == 0) {
                return x;
            }
            x = x.next;
        }
        return null;
    }

    /**
     * 判断链表中是否含有指定的Val
     *
     * @param val
     * @return
     */
    public boolean containsVal(T val) {
        Node<T> p_node = this.head;
        Node<T> q_node = new Node<T>(val, null);
        while (p_node != null) {
            if (p_node.item.compareTo(q_node.item) == 0) {
                return true;
            }
            p_node = p_node.next;
        }
        return false;
    }

    /**
     * 反转链表
     *
     * @param head
     * @return 反转后的头指针
     */
    public Node<T> reverseList(Node<T> head) {
        Node<T> new_head = null;
        while (head != null) {
            Node<T> p = head.next;
            head.next = new_head;
            new_head = head;
            head = p;
        }
        return new_head;
    }

    /**
     * 删除链表中重复元素
     *
     * @return 删除重复元素后的头指针
     */
    public Node<T> deleteDuplicates() {
        Node<T> current = this.head;
        while (current != null && current.next != null) {
            if (current.item.compareTo(current.next.item) == 0) {
                current.next = current.next.next;
                size--;
            } else {
                current = current.next;
            }
        }
        return head;
    }

    /**
     * 删除链表中指定元素
     *
     * @param head
     * @param val
     * @return
     */
    public void remove(T val) {
        Node<T> dummyNode = new Node<T>(val, null);
        dummyNode.next = head;
        Node<T> prev = dummyNode;
        while (prev.next != null) {
            if (prev.next.item == val) {
                prev.next = prev.next.next;
            } else {
                prev = prev.next;
            }
        }
    }

    /**
     * 合并两个有序链表(迭代)
     *
     * @param l1
     * @param l2
     * @return 合并后的头结点
     */
    public Node<T> mergeTwoLists(Node<T> l1, Node<T> l2) {
        Node<T> prehead = new Node<T>();
        Node<T> prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.item.compareTo(l2.item) <= 0) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }

    /**
     * 将链表以数组的形式返回
     *
     * @return
     */
    public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
        for (Node<T> x = head; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }

    /**
     * 判断链表是否为空
     *
     * @return head == null
     */
    private boolean isEmpty() {
        return this.head == null;
    }

    public Node<T> getHead() {
        return head;
    }

    public Node<T> getTail() {
        return tail;
    }

    public int getsize() {
        return size;
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        Node<T> p_node = this.head;
        while (p_node != null) {
            sb.append(p_node.item + "\n");
            p_node = p_node.next;
        }
        return sb.toString();
    }

    public void Print(){
        Node<T> p = this.head;
        while(p != null){
            System.out.println(p.item);
            p = p.next;
        }
    }

    /**
     * 节点类
     * @param <T>
     */
    private class Node<T>{
        T item;
        Node<T> next;

        public Node() {
        }

        public Node(T item, Node<T> next) {
            this.item = item;
            this.next = next;
        }
    }
}

class Book implements Comparable<Book> {
    private String bookName;
    private String ISBN;

    public Book() {
    }

    public Book(String bookName, String ISBN) {
        this.bookName = bookName;
        this.ISBN = ISBN;
    }

    public String getBookName() {
        return bookName;
    }

    public void setBookName(String bookName) {
        this.bookName = bookName;
    }

    public String getISBN() {
        return ISBN;
    }

    public void setISBN(String ISBN) {
        this.ISBN = ISBN;
    }

    @Override
    public String toString() {
        return this.ISBN + " " + this.bookName;
    }

    @Override
    public int compareTo(Book o) {
        return this.ISBN.compareTo(o.getISBN());
//        return 0;
    }
}

问题 D: 链表的删除

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            SinglyLinkedList<Book> s = new SinglyLinkedList<Book>();
            while(n > 0){
                s.addLast(new Book(sc.next(),sc.next()));
                n--;
            }
            int m = sc.nextInt();
            while(m > 0){
                s.remove(new Book(sc.next(),sc.next()));
                m--;
            }

            System.out.print(s);
        }
    }
}

/**
 * 单链表实现
 * @param <T>
 */
class SinglyLinkedList<T extends Comparable<? super T>> {

    private Node<T> head;          //  指向链表头结点
    private Node<T> tail;          //  指向链表尾结点
    private int size;              //  链表长度

    public SinglyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    /**
     * 向链表头部添加元素
     *
     * @param val
     */
    public void addFirst(T val) {
        Node<T> new_node = new Node<T>(val, null);
        if (!isEmpty()) {
            new_node.next = head;
            head = new_node;
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 向链表尾部添加元素
     *
     * @param val
     */
    public void addLast(T val) {
        Node<T> new_node = new Node<T>(val, null);
        if (!isEmpty()) {
            tail.next = new_node;
            tail = tail.next;
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 有序添加元素(自定义升序排序)
     *
     * @param val
     */
    public void add(T val) {
        Node<T> new_node = new Node<T>(val, null);
        if (!isEmpty()) {
            if (this.tail.item.compareTo(new_node.item) <= 0) {
                tail.next = new_node;
                tail = tail.next;
            } else {
                if(new_node.item.compareTo(head.item) < 0){
                    new_node.next = head;
                    head = new_node;
                }else{
                    Node<T> p_node = this.head;
                    Node<T> q_node = p_node;
                    while (p_node != null) {
                        if (new_node.item.compareTo(p_node.item) <= 0) {
                            break;
                        }
                        q_node = p_node;
                        p_node = p_node.next;
                    }
                    new_node.next = p_node;
                    q_node.next = new_node;
                }
            }
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 插入指定位置
     *
     * @param index
     * @param val
     */
    public void insert(int index, T val) {
        Node<T> new_node = new Node<T>(val, null);
        if (isEmpty()) {
            head = new_node;
        } else {
            if (index > size + 1) {
                System.out.println("下标超限");
            } else {
                Node<T> pre = findIndex(index - 1);
                new_node.next = pre.next;
                pre.next = new_node;
            }
        }
        size++;
    }

    /**
     * 查找指定位置的结点
     *
     * @param index
     * @return
     */
    public Node<T> findIndex(int index) {
        int i = 1;
        Node<T> p = head;
        while (p != null) {
            if (i == index) {
                return p;
            }
            i++;
            p = p.next;
        }
        return null;
    }

    /**
     * 寻找链表中指定结点
     *
     * @param val
     * @return
     */
    public Node<T> find(T val) {
        Node<T> x = this.head;
        Node<T> t = new Node<T>(val, null);
        while (x != null) {
            if (x.item.compareTo(t.item) == 0) {
                return x;
            }
            x = x.next;
        }
        return null;
    }

    /**
     * 判断链表中是否含有指定的Val
     *
     * @param val
     * @return
     */
    public boolean containsVal(T val) {
        Node<T> p_node = this.head;
        Node<T> q_node = new Node<T>(val, null);
        while (p_node != null) {
            if (p_node.item.compareTo(q_node.item) == 0) {
                return true;
            }
            p_node = p_node.next;
        }
        return false;
    }

    /**
     * 反转链表
     *
     * @param head
     * @return 反转后的头指针
     */
    public Node<T> reverseList(Node<T> head) {
        Node<T> new_head = null;
        while (head != null) {
            Node<T> p = head.next;
            head.next = new_head;
            new_head = head;
            head = p;
        }
        return new_head;
    }

    /**
     * 删除链表中重复元素
     *
     * @return 删除重复元素后的头指针
     */
    public Node<T> deleteDuplicates() {
        Node<T> current = this.head;
        while (current != null && current.next != null) {
            if (current.item.compareTo(current.next.item) == 0) {
                current.next = current.next.next;
                size--;
            } else {
                current = current.next;
            }
        }
        return head;
    }

    /**
     * 删除链表中指定元素
     *
     * @param head
     * @param val
     * @return
     */
    public void remove(T val) {
        Node<T> dummyNode = new Node<T>(val, null);
        dummyNode.next = head;
        Node<T> prev = dummyNode;
        while (prev.next != null) {
            if (prev.next.item.compareTo(dummyNode.item) == 0) {
                prev.next = prev.next.next;
            } else {
                prev = prev.next;
            }
        }
    }

    /**
     * 合并两个有序链表(迭代)
     *
     * @param l1
     * @param l2
     * @return 合并后的头结点
     */
    public Node<T> mergeTwoLists(Node<T> l1, Node<T> l2) {
        Node<T> prehead = new Node<T>();
        Node<T> prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.item.compareTo(l2.item) <= 0) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }

    /**
     * 将链表以数组的形式返回
     *
     * @return
     */
    public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
        for (Node<T> x = head; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }

    /**
     * 判断链表是否为空
     *
     * @return head == null
     */
    private boolean isEmpty() {
        return this.head == null;
    }

    public Node<T> getHead() {
        return head;
    }

    public Node<T> getTail() {
        return tail;
    }

    public int getsize() {
        return size;
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        Node<T> p_node = this.head;
        while (p_node != null) {
            sb.append(p_node.item + "\n");
            p_node = p_node.next;
        }
        return sb.toString();
    }

    public void Print(){
        Node<T> p = this.head;
        while(p != null){
            System.out.println(p.item);
            p = p.next;
        }
    }

    /**
     * 节点类
     * @param <T>
     */
    private class Node<T>{
        T item;
        Node<T> next;

        public Node() {
        }

        public Node(T item, Node<T> next) {
            this.item = item;
            this.next = next;
        }
    }
}

class Book implements Comparable<Book> {
    private String bookName;
    private String ISBN;

    public Book() {
    }

    public Book(String bookName, String ISBN) {
        this.bookName = bookName;
        this.ISBN = ISBN;
    }

    public String getBookName() {
        return bookName;
    }

    public void setBookName(String bookName) {
        this.bookName = bookName;
    }

    public String getISBN() {
        return ISBN;
    }

    public void setISBN(String ISBN) {
        this.ISBN = ISBN;
    }

    @Override
    public String toString() {
        return this.ISBN + " " + this.bookName;
    }

    @Override
    public int compareTo(Book o) {
        return this.ISBN.compareTo(o.getISBN());
//        return 0;
    }
}

(づ ̄3 ̄)づ╭❤~ 不用感谢我 嘿嘿(・ω<) てへぺろ


愿你生活的每一个角落,都有细微安静的美,愿你看淡世事沧桑,内心安然无恙,愿你洗净铅华,能被岁月温柔相待

标题:OJ作业-线性表和链表
作者:Bursteretion
地址:https://www.lwjppz.cn/OJ-01-HomeWork.html
版权声明:本博客除了特殊声明的文章外,均采用CC BY 3.0 CN协议进行许可。转载请署名作者且注明文章出处。
评论
  • 约瑟夫环那题,用递归重写了一遍😄

    Reply
  • 算了,我还是再看看吧(-̩̩̩-̩̩̩-̩̩̩-̩̩̩-̩̩̩___-̩̩̩-̩̩̩-̩̩̩-̩̩̩-̩̩̩)

    Reply
  • 我的可以,没有报错( ̄︶ ̄)↗,不过我用了@SuppressWarnings("unchecked")抑制了警告(VSCode我装个一个插件,警告和错误的提示一多就满屏红黄

    Reply
  • 那两题人事档案的,应该是OJ的原因(〃'▽'〃),把泛型强转OJ会编译错误,搞了好久,最后还是直接抄以前的(ㄒoㄒ)

    Reply
  • 众多Java中藏了一题C++,hhhh
    那题我写了好久,最后推倒重写5分钟搞定 (吐血.jpg

    Reply