用双链表对值排序

本文关键字：排序 链表 | 更新日期: 2023-09-27 18:02:59

我正在用一些简单的按钮来填充随机数字的数组/列表，并尝试在之后对它们进行排序。我就是没法把东西分类好。帮助感激。

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace DoublyLinkedList1
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }
        private void Sortbtn_Click(object sender, EventArgs e)
        {
            listBox2.Items.Clear();
            int[] array = new int[listBox1.Items.Count];
            for (int i = 0; i < array.Length; i++)
                {
                    array[i] = int.Parse(listBox1.Items[i].ToString());
                }
            array = cN.notearray(array);
            for (int i = 0; i < array.Length; i++)
            {
                listBox2.Items.Add(array[i]);
            }
        }
        private void filllstbtn_Click(object sender, EventArgs e)
        {
            listBox1.Items.Clear();
            Random rd = new Random();
            for (int i = 0; i < 8; i++)
            {
                listBox1.Items.Add(rd.Next(1, 9));  
            }
            }
        }
    }

类cN: 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DoublyLinkedList1
{
    class cN
    {
        public int V;
        public cN L;
        public cN R;
        private static cN[] n_array;
        private static cN head = null;
        public cN(cN nR, cN nL, int nV)
        {
            V = nV;
            L = nL;
            R = nR;
        }
        public static int[] notearray(int[] array)
        {
            n_array = new cN[array.Length];
            //Fill array with notes
            for (int i = 0; i < array.Length; i++)
            {
                n_array[i] = new cN(null, null, array[i]);
            }
            head = n_array[0];
            //sort array
            for (int i = 0; i < n_array.Length; i++)
            {
                sortnode(head, n_array[i]);
            }
            return array_composed();
        }
        private static void sortnode(cN chead, cN node)
        {
            if (node.V > chead.V)
            {
                if (chead.R != null)
                {
                    sortnode(chead.R, node);
                }
                 else 
                {
                    chead.R = node;
                    node.L = chead;
                }
            }
            else
            {
                if (head == chead)
                {
                    head = node;
                    node.R = chead;
                    chead.L = node;
                }
                else
                {
                    node.R = chead;
                    node.L = chead.L;
                    chead.R = node;
                    chead.L = node;
                }
            }

        }
        private static int[] array_composed()
        {
            int[] iarr = new int[n_array.Length];
            cN chead = head;
            int counter = 0;
            while (chead != null)
            {
                iarr[counter] = chead.V;
                chead = chead.R;
                counter++;
            }
            iarr[counter] = chead.V;
            return iarr;
        }
    }
}

似乎我的sortnode方法有问题。它一直在无限循环中循环，我似乎无法使它正常工作。

用双链表对值排序

为了简化问题，您要将值数组转换为排序的双链接列表，我希望我得到这部分的权利。老实说，我建议你改变一下方法。

我建议首先实现一些重要的方法，比如在列表中插入一个新的cN。下面是我编写notearray函数的方法:

public static int[] notearray(int[] array)
{
      n_array = new cN[array.Length];
      for(int i=0 ; i<array.Length ; i++)
      {
          n_array[i] = insertItem(array[i]);
      }
}
private static cN insertItem(int value)
{
      cN item = new cN(null,null,value)
      int i=0;
      while(n_array[i]!=null && n_array[i].V < value)
      {
          i++;
      }
      /*
        remember to check special conditions like if this new item is going to be head or going
        to be last item in the list or both in case of empty list
      */

      item .L = n_array[i].L;
      item .R = n_array[i];
      n_array[i].L = item;
      return item;
}

注意n_array实际上并没有排序，所以你必须像这样迭代才能在排序条件下使用它们:

cn iterator = head;
for(...)
{
    doSomthing(iterator);
    iterator = iterator.R;
}
相关文章：