Java:顺序排序名称并保存到随机访问文件中

Question

我正在尝试制作一个可以添加名称的程序，并且它应该保存在RandomAccessFile中(按字母顺序排列)。每当我添加一个名称时，它都会保存在文件中，它应该在末尾有下一个名称的下一个对应位置。每当我添加以 A 开头的名称，然后添加以 C 开头的名称时，我都会遇到保存问题，如果我在哪里添加以 B 开头的名称，它不会按正确的字母顺序指向我。

以下是程序应执行的操作的示例:

我添加了一个以 A 开头的名称。

“左侧”的数字正是下一个名称的开始位置，“右侧”的数字是指向下一个名称的指针

[0]-----A----[-1] -------------- “-1”指针表示它是列表的末尾

我添加了一个以 C 开头的名称。

[0]-----A----[100] ---------- “100”指针表示下一个名称“C”从第 100 字节开始

[100]---C----[-1] ---------链表指针结束，注意A不再有“-1”指针

我添加了一个以 B 开头的名称。

[0]-----A----[200] ------ “A”不再指向 100，因为下一个字母应该是“B”

[100]---C----[-1] -------- -1 仍然表示“C”是列表指针的末尾

[200]---B----[100] --------- “B”指向“C”，因为后面的下一个字母

这是到目前为止我的代码，但我缺少添加属于列表中间的名称的部分。

公共(public) boolean 添加(字符串名称，字符串姓氏，字符串telf){

    try {
        fileSize = file.length();
    } catch (IOException ex) {
        ex.printStackTrace();
    }
    if (fileSize == 0) { //must be a new entry

        try {

            byte entry[] = new byte[sizeEntry];  // size of each entry
            file.write(entry);
            file.seek(file.getFilePointer() - sizeEntry);

            file.writeUTF(name);   //name gets saved
            file.writeUTF(lastName);// last name gets saved
            file.writeUTF(telf);    // telf gets saved
            file.writeUTF("N");     // deleted "Y" or "N" gets saved
            file.writeUTF("-1");    // pointer gets saved

        } catch (IOException e) {
            System.out.println("Error at saving....");
            e.printStackTrace();
        }

    } else {
        pPresent= 0;     //variable for the pointer reading
        pPrevious= 0; // variable for the pointer read

        try {
            file.seek(0); //start reading at the top
            do {
                pPresent= file.getFilePointer();//saves present pointer
                file.seek(pPresent);//seeks to present pointer
                nameRead = file.readUTF();  //reads name
                file.readUTF();  //reads last name
                file.readUTF();  //reads telf
                file.readUTF();  //reads deleted?
                pNext= Long.parseLong(file.readUTF()); // reads the next pointer

                int comparison= name.compareTo(nameRead);
                if (comparison< 0) {

                    //enters here if the new entry goes before the present entry
                    if (pNext!= -1) {
                        file.seek(pNext);//enters here if pointer is not at end of list
                    } else {
                        try {// proceeds to writing a new entry 

                            file.seek(file.length()); //goes to the end of the file
                            byte entry[] = new byte[sizeEntry];
                            file.write(entry);
                            file.seek(file.getFilePointer() - sizeEntry);

                            file.writeUTF(name);
                            file.writeUTF(lastname);
                            file.writeUTF(telf);
                            file.writeUTF("N");
                            file.writeUTF(Long.toString(pPrevious));//writes the previous pointer

                            file.seek(pPrevious);//seeks to the previous entry
                            file.readUTF();//reads name
                            file.readUTF();//reads lastname
                            file.readUTF();//reads telf
                            file.readUTF();//reads deleted?
                            file.writeUTF(Long.toString(pPrevious));//overwrites the new previous

                        } catch (IOException e) {
                            System.out.println("Error at saving...");
                            e.printStackTrace();
                        }
                        break;//exits
                    }
                } else {//enteres here if the entry is bigger than the present

                    if (pNext!= -1) {
                        file.seek(pNext);
                    } else {
                        try {

                            pPresent= file.length()-sizeEntry;//saves present entry
                            file.seek(pPrevious); //seeks to previous entry
                            file.readUTF();//reads name
                            file.readUTF();//reads last name
                            file.readUTF();//reads telf
                            file.readUTF();//reads deleted
                            file.writeUTF(Long.toString(pPresent+100));//overwrites the next pointer

                            file.seek(file.length());//seeks at the end
                            byte entry[] = new byte[sizeEntry];//creates a new entry
                            file.write(entry);
                            file.seek(file.getFilePointer() - sizeEntry);

                            file.writeUTF(name);//writes name
                            file.writeUTF(lastname);//writes lastname
                            file.writeUTF(telf);//writes telf
                            file.writeUTF("N");//writes deleted
                            file.writeUTF(Long.toString(pNext));//writes next pointer

                        } catch (IOException e) {
                            System.out.println("Error at saving...");
                            e.printStackTrace();
                        }
                        break;//exits
                    }
                }
                pPresent= file.getFilePointer();//present pointer read
                pPrevious= pPresent;//present pointer becomes previous
            } while (true);


        } catch (IOException e) {

            System.out.println("Error at saving....");
            e.printStackTrace();
        }
    }
    return false;
}

我希望你们现在通过源代码更好地理解该程序的思想。我不知道该怎么做的部分是添加一个属于列表中间的条目。请记住，名称的顺序不会仅更改指向下一个 do 的指针。

Answer 1

查找插入点需要遍历列表，而这又需要对每个名称进行磁盘访问。假设您有 100 万个名称，典型的磁盘访问时间为 10 毫秒，则插入单个名称大约需要 3 小时。换句话说，链表是一种极不适合在磁盘上存储数据的数据结构。

合理的数据结构，例如 B-Tree将允许在短短 3 次磁盘访问中查找和插入 100 万个名称。