# 2019-06-21 劉宥辰
* https://github.com/tony2037/linked_list
## Q1: linked list
假設某個 linked list 採用 Linux 核心的 `list.h` 實作，並且已事先排序過。
以下函式允許我們新增一個節點到已排序的 linked list:
```cpp
#include <stddef.h>
#include <stdint.h>
#include "list.h"
struct listitem {
uint16_t i;
struct list_head list;
};
static inline int cmpint(const void *p1, const void *p2) {
const uint16_t *i1 = (const uint16_t *) p1;
const uint16_t *i2 = (const uint16_t *) p2;
return *i1 - *i2;
}
void list_insert(struct listitem *entry, struct list_head *head) {
{
if (list_empty(head)) {
list_add(&entry->list, head);
return;
}
...
}
```
請補完程式碼，結構體 listitem 的成員 `i` 是排序比較的數值。
Hint: `list_add`, `
`, `list_for_each_entry`
==>
```cpp
void list_insert(struct listitem *entry, struct list_head **head) {
if (list_empty(*head)) {
list_add(&entry->list, *head);
return;
}
struct listitem *p = NULL;
struct list_head *insert = *head;
list_for_each_entry(p, *head, list) {
if (entry->i < p->i) {
insert = &p->list;
continue;
}
}
list_add(&entry->list, insert);
}
```
- [ ] main
```cpp
#include <stdlib.h>
#include "list.h"
#include "linked_list.h"
int main(int argc, char **argv) {
struct list_head *head = malloc(sizeof(struct list_head));
INIT_LIST_HEAD(head);
uint16_t data [5] = {5, 3, 20, 1, 40};
for (size_t j = 0; j < 5; ++j) {
struct listitem *k = malloc(sizeof(struct listitem));
k->i = data[j];
INIT_LIST_HEAD(&k->list);
list_insert(k, &head);
}
display_list(head);
}
```
- [ ] output
```shell
e24056310@luffy:~/linked_list$ make
gcc -g -Wall -O0 -I ./include -c linked_list.c -o linked_list.o
gcc -g -Wall -O0 -I ./include -c main.c -o main.o
gcc -g -Wall -O0 -I ./include linked_list.o main.o -o main
e24056310@luffy:~/linked_list$ ./main
40
20
5
3
1
```
---
## Q2: 以 Q1 的程式解釋雙向環狀的考量
* 對於 head tail 的操作方便許多
* 比如: list_add_tail 不需要 traverse 整個 linked-list
---
## Q3: linked list & sort
承 Q1，給定一個「尚未」排序的 linked list，移去裡頭排名第 k 的節點
- [ ] 簡單版本的實現
- [ ] `linked_list.c`
```cpp=
void list_remove_kth(struct list_head **head, const int k) {
struct list_head *tmp = malloc(sizeof(struct list_head));
INIT_LIST_HEAD(tmp);
struct listitem *p = NULL;
struct listitem *n = NULL;
list_for_each_entry_safe(p, n, *head, list) {
list_del(&p->list);
list_insert(p, &tmp);
}
int i = 0;
list_for_each_entry_safe(p, n, tmp, list) {
if(++i == k) {
list_del(&p->list);
continue;
}
list_move(&p->list, *head);
}
}
```
- [ ]
- [ ] `ksort.c`
```cpp=
#include <stdlib.h>
#include <stdio.h>
#include "list.h"
#include "linked_list.h"
int main(int argc, char **argv) {
struct list_head *head = malloc(sizeof(struct list_head));
INIT_LIST_HEAD(head);
uint16_t data [5] = {50, 3, 20, 1, 40};
for (size_t j = 0; j < 5; ++j) {
struct listitem *k = malloc(sizeof(struct listitem));
k->i = data[j];
INIT_LIST_HEAD(&k->list);
list_add(&k->list, head);
}
display_list(head);
printf("====================\n");
list_remove_kth(&head, 3);
display_list(head);
}
```
- [ ]
- [ ] `output`
```shell=
e24056310@luffy:~/linked_list$ ./ksort
40
1
20
3
50
====================
1
3
40
50
```
==> https://www.cnblogs.com/grandyang/p/4539757.html
* Partition 的概念太有趣了
* 首先找出一個 pivot (樞), 這也就是比較的基準值, 這邊選用最右邊(尾巴) 的值
* 一個指標 i 可以想成比較小那一群的代表
* 一個指表 j 想成比較大那群的代表
* 關鍵來了: j 先往右走 (我把他想成去找碴的人)
* 如果 j 指到的人比 pivot 小, 代表這個元素屬於**比較小**的那群:
* 這時候 i 往右走一個 然後 i , j 兩個元素交換
* 這時候比小 pivot 的元素就成功被丟到左邊了~
* j 走到盡頭代表這個 list 走完囉~
* 此時 i 的下一位就是我們 **值為 pivot 那個元素** 的位置囉
* [https ://www.youtube.com/watch?v=MZaf_9IZCrc](https://www.youtube.com/watch?v=MZaf_9IZCrc)
Sign in with Wallet
Connect another wallet