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

### 问题描述

` ` 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的递归调用

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;
}
``````