双向链表二分查找失效求助：需排序但不知如何实现

问题描述 #

从CSV文件读取字符串存入自定义双向链表后，使用二分查找无法找到目标字符串，但线性搜索功能正常。已知二分查找要求数据必须有序，不过不清楚如何对双向链表进行排序。

现有代码 #

双向链表类（DLL） #

public class DLL
{
    /*双向链表，包含指向第一个节点的头指针和指向最后一个节点的尾指针，count字段记录链表中的节点总数*/
    
    public Node headNode;
    public Node tailNode;
    public int countNodes;

    public int CountNodes
    {
        get { return this.countNodes; }
    }

    public void AddLastNode(string color)
    {
        Node newNode = new Node(color);

        if (this.headNode == null)
        {
            headNode = newNode;
            tailNode = newNode;
        }
        else
        {
            newNode.prevNode = this.tailNode; //Node类的prevNode属性
            this.tailNode.nextNode = newNode;
            this.tailNode = newNode;
        }

        this.countNodes++;
    }
    
    //根据索引获取对应节点
    private Node getNodeIndex(int i)
    {
        if (i < 0 || i >= this.countNodes)
        {
            throw new IndexOutOfRangeException();
        }

        Node currNode = this.headNode;
        int currI = 0;

        while (currI < i)
        {
            currNode = currNode.nextNode; //Node类的nextNode属性
            currI++;
        }

        return currNode;
    }

    public int binarySearch(string colorBs) //二分查找实现
    {
        if(headNode == null)
        {
            return -1;
        }

        int st = 0;
        int end = this.countNodes - 1;

        while (st <= end)
        {
            int m = (st + end) / 2;
            Node mNode = getNodeIndex(m);

            int comparison = string.Compare(colorBs, mNode.color, StringComparison.OrdinalIgnoreCase);

            if (comparison == 0)
            {
                return m;
            }else if (comparison < 0)
            {
                end = m - 1;
            }
            else
            {
                st = m + 1;
            }
        }
        return -1;
    }

    public int linearSearch(string colorLs) //线性查找实现
    {
        if (headNode == null)
        {
            return -1;
        }

        Node currNode = headNode;
        int i = 0;

        while (currNode != null)
        {
            if (String.Equals(colorLs, currNode.color, StringComparison.OrdinalIgnoreCase)) ///忽略大小写，视为相同字符串
            {
                return i;
            }

            currNode = currNode.nextNode;
            i++;
        }
        return -1;
    }

    public void trFwd() //正向遍历
    {
        Node currNode = this.headNode;

        while (currNode != null)
        {
            Console.WriteLine(currNode.color);
            currNode = currNode.nextNode;
        }
    }

    public void trBwd() //反向遍历
    {
        Node currNode = this.tailNode;

        while (currNode != null)
        {
            Console.WriteLine(currNode.color);
            currNode = currNode.prevNode;
        }
    } 
}

Node类 #

public class Node
{
    //节点属性：存储颜色字符串数据，以及指向下一个和上一个节点的指针
    public string color { get; set; }
    public Node nextNode { get; set; }
    public Node prevNode { get; set; }

    public Node(string color)
    {
        this.color = color;
        this.nextNode = null;
        this.prevNode = null;
    }
}

CSV处理类（CsvS） #

namespace DoubleLinkedList;

public class CsvS
{
    private DLL dll;

    public CsvS()
    {
        this.dll = new DLL();
    }

    public DLL getDll()
    {
        return this.dll;
    }

    public void nodeBuilder(string pathCsv)
    {
        using (StreamReader reader = new StreamReader(pathCsv))
        {
            string line;
            while ((line = reader.ReadLine()) != null)
            {
                string[] fields = line.Split(','); 
                if(fields.Length>=2)
                {
                    string fieldValue = fields[1].Trim();
                    dll.AddLastNode(fieldValue);
                }
            }
        }
    }

    public int binarySearchCsv(string colorBs)
    {
        return dll.binarySearch(colorBs);
    }
}

Program.cs #

using System;
using System.IO;
using DoubleLinkedList;

CsvS csv = new CsvS();
csv.nodeBuilder("colors.csv");

string searchColor = "Black";
int position = csv.binarySearchCsv(searchColor);

if (position != -1)
{
    Console.WriteLine($"Position of '{searchColor}' is {position}");
}
else
{
    Console.WriteLine($"'{searchColor}' not found !");
}

Console.WriteLine("Traversing fwd:");
csv.getDll().trFwd();

Console.WriteLine("Traversing bwd:");
csv.getDll().trBwd();

解决方案 #

1. 给双向链表添加排序方法 #

由于双向链表无法随机访问，适合使用冒泡排序（原地排序，通过调整节点指针实现）。在DLL类中添加以下排序方法：

public void BubbleSort()
{
    if (headNode == null || headNode.nextNode == null)
        return;

    bool swapped;
    Node current;
    Node lastSorted = null;

    do
    {
        swapped = false;
        current = headNode;

        while (current.nextNode != lastSorted)
        {
            // 使用和二分查找一致的忽略大小写规则比较
            int compareResult = string.Compare(current.color, current.nextNode.color, StringComparison.OrdinalIgnoreCase);
            if (compareResult > 0)
            {
                // 交换两个节点的位置
                SwapNodes(current, current.nextNode);
                swapped = true;
            }
            else
            {
                current = current.nextNode;
            }
        }
        lastSorted = current;
    } while (swapped);
}

private void SwapNodes(Node nodeA, Node nodeB)
{
    // 处理相邻节点的指针关联
    if (nodeA.prevNode != null)
        nodeA.prevNode.nextNode = nodeB;
    else
        headNode = nodeB; // nodeA是头节点的情况

    if (nodeB.nextNode != null)
        nodeB.nextNode.prevNode = nodeA;
    else
        tailNode = nodeA; // nodeB是尾节点的情况

    // 交换两个节点自身的prev和next指针
    Node tempPrev = nodeA.prevNode;
    nodeA.prevNode = nodeB;
    nodeB.prevNode = tempPrev;

    Node tempNext = nodeA.nextNode;
    nodeA.nextNode = nodeB.nextNode;
    nodeB.nextNode = tempNext;
}

2. 在CSV读取完成后执行排序 #

修改Program.cs，在读取CSV数据后调用排序方法，确保链表有序再进行二分查找：

using System;
using System.IO;
using DoubleLinkedList;

CsvS csv = new CsvS();
csv.nodeBuilder("colors.csv");

// 新增：对链表进行排序，保证二分查找的前提条件
csv.getDll().BubbleSort();

string searchColor = "Black";
int position = csv.binarySearchCsv(searchColor);

if (position != -1)
{
    Console.WriteLine($"Position of '{searchColor}' is {position}");
}
else
{
    Console.WriteLine($"'{searchColor}' not found !");
}

Console.WriteLine("Traversing fwd:");
csv.getDll().trFwd();

Console.WriteLine("Traversing bwd:");
csv.getDll().trBwd();

说明 #

• 冒泡排序通过逐次比较相邻节点，交换不符合顺序的节点位置，最终让链表整体有序。
• 排序时使用和二分查找一致的StringComparison.OrdinalIgnoreCase规则，保证比较逻辑统一。
• 排序完成后，二分查找就能基于有序数据正常工作，准确找到目标字符串的位置。

内容的提问来源于stack exchange，提问作者CatCoderInHisUniDays