ผลต่างระหว่างรุ่นของ "Algo lab/linked lists"
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
| แถว 67: | แถว 67: | ||
We can use the most common data structure, arrays, to deal with lists. Arrays are good for keeping collections of data. However, array manipulations are usually inefficient. Since every element in an array is stored contiguously, insertion and deletion of array elements usually take linear time. In this chapter, we shall look at a commonly used abstract data type for linear collection called a list. You can implement a list using an array, but the another common implementation is a linked list, which allows efficient manipulation of list items. | We can use the most common data structure, arrays, to deal with lists. Arrays are good for keeping collections of data. However, array manipulations are usually inefficient. Since every element in an array is stored contiguously, insertion and deletion of array elements usually take linear time. In this chapter, we shall look at a commonly used abstract data type for linear collection called a list. You can implement a list using an array, but the another common implementation is a linked list, which allows efficient manipulation of list items. | ||
| − | |||
| − | + | === A list of colored balls === | |
| − | We will look at the simpler version of the game, where we can shoot the balls, but the balls remain in the list. In this tasks, there are enemy colored balls and you want to shoot colored balls. To be precise, the enemy balls are referred to as ball to ball , and the balls you will shoot are referred to as ball to ball . For each of your -th ball, for you shoot into the list, it will land right after ball . (Note that here is not referring to the ball numbers, as your -th ball is numbered .) You want to know the final list of balls. | + | Let's start with a concrete problem. Consider a rather popular casual game called [https://en.wikipedia.org/wiki/Zuma_(video_game) Zuma]. In this game, there is a list of enemy colored balls lining up to reach a secret gate. You want to prevent that by shooting another set of colored balls to the list. Because consecutive three balls of the same color explode, you can potentially destroy all the enemy balls. |
| + | |||
| + | We will look at the simpler version of the game, where we can shoot the balls, but the balls remain in the list. In this tasks, there are '''n''' enemy colored balls and you want to shoot m colored balls. To be precise, the enemy balls are referred to as ball '''1''' to ball '''n''', and the balls you will shoot are referred to as ball '''n+1''' to ball '''n+m'''. For each of your '''i'''-th ball, for '''1≤i≤m''' you shoot into the list, it will land right after ball '''p[i]'''. (Note that '''i''' here is not referring to the ball numbers, as your '''i'''-th ball is numbered '''n+i'''.) You want to know the final list of balls. | ||
Related task: [[Algo lab/zooma 1|Zooma 1]] | Related task: [[Algo lab/zooma 1|Zooma 1]] | ||
| − | One can deal with this task by just simulating the system and output the final result. Starting with a list of numbers from to . We iterate the array and insert ball number into the sequence right after . To do so, we need to look up where is in the sequence and insert right after it. | + | One can deal with this task by just simulating the system and output the final result. Starting with a list of '''n''' numbers from '''1''' to '''n'''. We iterate the array '''p[i]''' and insert ball number '''n+1''' into the sequence right after '''p[i]'''. To do so, we need to look up where '''p[i]''' is in the sequence and insert '''i+n''' right after it. |
Array implementation | Array implementation | ||
| − | < | + | <syntaxhighlight lang="cpp"> |
| + | main() | ||
| + | { | ||
| + | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
| − | + | We will learn a new data structure that can speed up the solution to run in time . | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== Implementations == | == Implementations == | ||
รุ่นแก้ไขเมื่อ 22:00, 9 กันยายน 2561
- Source [1]
Lists are everywhere. Comments directly replying the same status can be kept in a list. A list of monsters around you (within a particular radius) in a game is a list. When you have a collection of objects, the simplest way to deal with them is to put them in a list.
What can you do with a list?
Below is an example of a list of top Women's World Cup goal scorers.
Marta Birgit Prinz Somying Jaiyen Abby Wambach Michelle Akers Sun Wen Bettina Wiegmann Ann Kristin Aarones Heidi Mohr
It seems that there is a mistake. Somying Jaiyen should not be in the list. So let's remove it. This is the result
Marta Birgit Prinz Abby Wambach Michelle Akers Sun Wen Bettina Wiegmann Ann Kristin Aarones Heidi Mohr
Now, suppose that in year 2019 another player, Mary Playgood has just scored 12 goals. With this many goals, she has to be inserted into the list after Akers. The list becomes:
Marta Birgit Prinz Abby Wambach Michelle Akers Mary Playgood Sun Wen Bettina Wiegmann Ann Kristin Aarones Heidi Mohr
You have just heard the name Orathai Srimanee, who is a famous Thai player. You may want to check if she is in the list. To do so, you have to look at every entry in the list, and find out that she is not in the list. You want to know how many additional goals she has to score to be in the list. With the current information on the list, you cannot answer the question. You look up wikipedia and update the list with goal information.
Marta, 15 Birgit Prinz, 14 Abby Wambach, 14 Michelle Akers, 12 Mary Playgood, 12 Sun Wen, 11 Bettina Wiegmann, 11 Ann Kristin Aarones, 10 Heidi Mohr, 10
You look at the last entry and see that Heidi Mohr scored 10 goals. So Orathai Srimanee needs to score 8 more goals to have a chance to be in the list.
You can see that there is a lot of operations you can do with a list. And also, note that an entry in a list can keep fair amount of information.
This chapter discuss how we can implement a list and also an abstract data type for a list.
We can use the most common data structure, arrays, to deal with lists. Arrays are good for keeping collections of data. However, array manipulations are usually inefficient. Since every element in an array is stored contiguously, insertion and deletion of array elements usually take linear time. In this chapter, we shall look at a commonly used abstract data type for linear collection called a list. You can implement a list using an array, but the another common implementation is a linked list, which allows efficient manipulation of list items.
เนื้อหา
A list of colored balls
Let's start with a concrete problem. Consider a rather popular casual game called Zuma. In this game, there is a list of enemy colored balls lining up to reach a secret gate. You want to prevent that by shooting another set of colored balls to the list. Because consecutive three balls of the same color explode, you can potentially destroy all the enemy balls.
We will look at the simpler version of the game, where we can shoot the balls, but the balls remain in the list. In this tasks, there are n enemy colored balls and you want to shoot m colored balls. To be precise, the enemy balls are referred to as ball 1 to ball n, and the balls you will shoot are referred to as ball n+1 to ball n+m. For each of your i-th ball, for 1≤i≤m you shoot into the list, it will land right after ball p[i]. (Note that i here is not referring to the ball numbers, as your i-th ball is numbered n+i.) You want to know the final list of balls.
Related task: Zooma 1
One can deal with this task by just simulating the system and output the final result. Starting with a list of n numbers from 1 to n. We iterate the array p[i] and insert ball number n+1 into the sequence right after p[i]. To do so, we need to look up where p[i] is in the sequence and insert i+n right after it. Array implementation
main()
{
}
We will learn a new data structure that can speed up the solution to run in time .
Implementations
Array-based lists
List nodes
typedef
In C++, you can simply declare a new type based on known types using typedef.
typedef int valueType;
valueType x = 10;
We will declare new valueType so that our linked list code works fairly well with any types. We will eventually use template to make generic linked list.
struct
struct ListNode
{
valueType val;
ListNode* next;
ListNode(valueType val, ListNode* next=0)
: val(val), next(next) {}
};
