排序插入到链接列表中 [英] Sorted insert into Linked List

查看:51
本文介绍了排序插入到链接列表中的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

自周日以来,我一直在使用此迭代函数,但没有成功,我想为排序的插入创建迭代函数,但是经过一小时的节点绘制,我认为我需要对该函数进行一些帮助:

结构声明:

  typedef struct E_Type *列表;结构E_Type{整数数据;struct E_Type *接下来;}; 

功能:

 布尔插入(List& l,int data){而(l!= 0){for(列表p = l; p; p = p-> next){如果(p-> data == data)返回false;}if(l-> data> data){清单new_list = new E_Type;new_list-> data = data;new_list-> next = 1;l = new_list;返回true;} if if(l-> data< data){清单new_list = new E_Type;new_list-> data = data;l-> next = new_list;l = new_list;返回true;}}如果(l == 0){清单new_list = new E_Type;new_list-> data = data;new_list-> next = 1;l = new_list;返回true;}} 

btw:该功能是否还可能...有关此插入的所有教程,信息等均包含对next-data的递归调用

解决方案

我可以看到您如何陷入困境.您的 insert 函数尝试执行多个任务(检查重复项,找到要在其中插入新元素的位置并进行实际插入),并且混淆了每个任务所需的步骤.

我最好的建议是退后一步,编写三个函数:

  1. 使函数检查某个元素是否已经存在(让我们将其命名为 bool find_element(List l,int data)).
  2. 使函数在现有列表的开头插入新元素并返回新列表( List insert_front(List l,int data)).此功能可以利用以下事实: List 的每个元素也可以视为列表的头.
  3. 使函数确定要在哪里插入新元素( Listlocate_insertion_point(List l,int data)).
  4. 使用三个新功能编写您的 insert 函数.

     布尔型插入(List& l,int数据){如果(find_element(l,data))返回false;列表插入= locate_insertion_point(l,数据);如果(插入== NULL){/*不能在任何点后插入.在前面插入*/清单new_list = new E_Type;new_list-> data = data;new_list-> next = 1;l = new_list;}别的{/*插入后插入*/列出下一个= insert-> next;insert-> next = insert_front(next,data);}返回true;} 

i have been working with this iterative function since Sunday without any success, I want to create iterative function for sorted insert but after hour of node drawings, I think i would need some help with the function:

struct declaration:

  typedef struct E_Type * List;

  struct E_Type
  {
      int data;
      struct E_Type* next;
  };

the function:

bool insert(List & l, int data) {
    while (l != 0) {
        for (List p = l; p; p = p->next) {
            if (p->data == data)
                return false;
        }

        if (l->data > data) {
            List new_list = new E_Type;
            new_list->data = data;
            new_list->next = l;
            l = new_list;
            return true;
        } else if (l->data < data) {

            List new_list = new E_Type;
            new_list->data = data;
            l->next = new_list;
            l = new_list;
            return true;
        }
    }

    if (l == 0) {
        List new_list = new E_Type;
        new_list->data = data;
        new_list->next = l;
        l = new_list;
        return true;
    }
}

btw: is this function even possible... all tutorials, infos etc about this insertion are with recursive call for next-data

解决方案

I can see how you have gotten stuck. Your insert function tries to do multiple tasks (check for duplicates, find where to insert a new element and do the actual insertion) and the steps needed for each task have gotten muddled up.

My best advice is to take a step back and write three functions:

  1. Make function that checks if an element already exists (lets call it bool find_element(List l, int data)).
  2. Make a function that inserts a new element at the front of an existing list and returns the new list (List insert_front(List l, int data)). This function can make use of the fact that each element of a List can be regarded as the head of a list as well.
  3. Make a function that determines where to insert a new element (List locate_insertion_point(List l, int data)).
  4. Write your insert function in terms of the three new functions.

    bool insert(List& l, int data)
    {
        if (find_element(l, data))
            return false;
    
        List insert = locate_insertion_point(l, data);
        if (insert == NULL)
        { /* Can't insert after any point. Insert at the front */
            List new_list = new E_Type;
            new_list->data = data;
            new_list->next = l;
            l = new_list;
        }
        else
        { /* insert after insert */
            List next = insert->next;
            insert->next = insert_front(next, data);
        }
        return true;
    }
    

这篇关于排序插入到链接列表中的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆