Algorithm - Struct & Linked List

Course

可以參考我做的課程簡報：

Struct

tag
- struct 名字
member-list
- struct 的成員列表
variable list
- 此 struct 聲明的變數

struct <tag>{

	member list
    
}variable list;

可以直接宣告

struct student{

　　char name[5];
　　int age;
  
}st1, st2[100], *st3;

int main(){
   st1.age = 19;
}

也可以另外宣告

struct student{

　　char name[5];
　　int age;
  
};

int main(){
   struct student st1, st2[100], *st3;
}

初始化

一般寫法

struct student st1;

strcpy(st1.name, "LAVI");
st1.age = 19;

進階寫法，但不太會這樣寫

student st1={

　　.name = "LAVI",
　　.age = 19,
  
};

直接選取運算子 `.`

#include <stdio.h>
#include <string.h>

struct student{

    char name[5];
    int age;
  
};

int main(){
    
    struct student st1;
    
    strcpy(st1.name, "LAVI");
    st1.age = 19;
    
    printf("%s %d\n", st1.name, st1.age);
    
    return 0;
}

直接選取運算子 `->`

#include <stdio.h>
#include <string.h>

struct student{

    char name[5];
    int age;
  
};


int main(){

    struct student st1;
    struct student *st1Ptr = &st1;
    
    strcpy(st1.name, "LAVI");
    st1.age = 19;
    
    printf("st1: %s %d\n", st1.name, st1.age);
    printf("st1Ptr->: %s %d\n", st1Ptr->name, st1Ptr->age);
    printf("(*st1Ptr): %s %d\n", (*st1Ptr).name, (*st1Ptr).age);
    printf("&st1: %s %d\n", (&st1)->name, (&st1)->age);
    
    return 0;
}

Lab 0x0

小明是一位程式設計老師

他總共有 n 個學生、這學期考了 m 次上機考

今天小明想要當掉全班 1/2 個學生你能幫他找出誰會被當嗎 owo

Input

4                   <- 學生人數 (row)
5                   <- 考試次數 (column)
Tom 99 80 75 88 92  <- 名字&分數
Ann 88 72 60 77 72
Bee 60 55 44 88 99
Amy 99 99 99 99 99

Output

Ann 88 72 60 77 72
Bee 60 55 44 88 99

Solution Code

#include <stdio.h>

struct Student{

    char name[10];
    int scores[10];
    int totalscore;

}student[65];

int main(){

    int n, m;
    int average = 0;
    scanf("%d%d", &n, &m);

    for(int i = 0 ; i < n ; i++){
        scanf("%s", &student[i].name);

        for(int j = 0 ; j < m ; j++){
            scanf("%d", &student[i].scores[j]);

            student[i].totalscore += student[i].scores[j];
            average += student[i].scores[j];
        }

    }
    average /= n;
    printf("\n");

    for(int i = 0; i < n; i++){

        if(student[i].totalscore < average){

            printf("%s ", student[i].name);
            for(int j = 0; j < m; j++){
                printf("%d ", student[i].scores[j]);
            }
            printf("\n");
        }
    }

    return 0;
}

Linked List

malloc

memory allocation
配置指定大小的記憶體空間
- 配置的空間處於尚未初始化的狀態
動態的宣告記憶體空間
- 要多少開多少

int *dyn;

int arrlen1 = 5;
int arrlen2 = 2;

dyn = malloc( arrlen1 * arrlen2 * sizeof(int) );

free

釋放之前使用 malloc 所配置的記憶體空間
memory leak
- 程式未釋放已不再使用的內部記憶體空間
- 用完記憶體後沒有 free 掉
在程式執行完後會自動把記憶體還回去

int *dyn;

int arrlen1 = 5;
int arrlen2 = 2;

free(dyn);

用 struct 實作 linked list

struct node{

    int data;	         // 資料成員
    struct node *next;   // 鏈結成員 指向下一個節點的指標
    
}

創建一個 linked list 的 struct

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct list_node* list_pointer;

typedef struct struct list_node{

    char data[5];
    list_pointer link;
    
}ListNode;

第一個節點

int main(){

    list_pointer ptr1 = NULL, ptr2 = NULL;
    
    ptr1 = (list_pointer) malloc(sizeof(ListNode));
    
    strcpy(ptr1->data, "CPC");
    ptr1 -> link = NULL;
    
    return 0;
}

新增節點

list_pointer create2(){

	list_pointer first, second;
    
    first = (list_pointer) malloc(sizeof(ListNode));
    second = (list_pointer) malloc(sizeof(ListNode));
    
    second-> link = NULL;
    strcpy(second->data, "Mimmy");
    strcpy(first->data, "LAVI");
    first-> link = second;
    
    return first;
}

Lab 0x1

給你一個字元陣列，請用迴圈把所有人依序串接起來

char name[][10] = {"Jack", "Hank", "Jay", "Mimmy", "LAVI", "CHA", "yus", "Andy"};

本題沒有輸入 Input

Output

CPC Jack Hank Jay Mimmy LAVI CHA yus Andy 

題示範例圖：

Solution Code

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct list_node* list_pointer;

typedef struct list_node{

    char data[10];
    list_pointer link;
    
}ListNode;

char name[][10] = {"Jack", "Hank", "Jay", "Mimmy", "LAVI", "CHA", "yus", "Andy"};

int main(){


    ListNode *head = NULL;
    head = malloc(sizeof(ListNode));

    strcpy(head->data, "CPC");

    ListNode *last = head, *now;

    for(int i = 0; i < 8; i++){

        now = malloc(sizeof(ListNode));

        strcpy(now->data, name[i]);
        last->link = now;
        last = now;
    }
    last->link = NULL;

    for(ListNode *i = head; i != NULL; i = i->link){
        printf("%s ", i->data);
    }
}

Traverse

遍歷
每個點只記自己下一個點的位址
linked list 找點要遍歷，沒辦法像陣列直接取 index

int cnt = 0;
ListNode *node = head;

while(node->data != 5){

    cnt++;
    node = node->link;

}
printf("%d\n", cnt);

// output: 5

Lab 0x2

來玩躲貓貓 !
請找到 LAVI 排在整段鏈結串列中的第幾個

Tips: 請從 0 開始算哦

Solution Code

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct list_node* list_pointer;

typedef struct list_node{

    char data[10];
    list_pointer link;
    
}ListNode;

char name[][10] = {"Jack", "Hank", "Jay", "Mimmy", "LAVI", "CHA", "yus", "Andy"};

int main(){


    ListNode *head = NULL;
    head = malloc(sizeof(ListNode));

    strcpy(head->data, "CPC");

    ListNode *last = head, *now;

    for(int i = 0; i < 8; i++){

        now = malloc(sizeof(ListNode));

        strcpy(now->data, name[i]);
        last->link = now;
        last = now;
    }
    last->link = NULL;

    int cnt = 0;
    ListNode *node = head;
    
    while(strcmp(node->data, "LAVI")){

        cnt++;
	    node = node->link;
    
    }
    printf("%d\n", cnt);
}

Insertion

插入
遍歷找到要插入新節點的位址
更改前一節點的 link -> 新節點
將新節點的 link 指向原位址的節點

list_pointer insert;
insert = (list_pointer) malloc(sizeof(ListNode));

insert->data = 9;
// insert->link = NULL;

list_pointer node = head;

while(node->data != 4){
    node = node->link;  
}

insert->link = node->link;
node->link = insert;

Lab 0x3

歡迎加入 CPC 的行列 owo
試著把你的名字接在 Mimmy 學姊和 LAVI 之間並輸出

本題沒有輸入 Input

Output

Jack Hank Jay Mimmy <你的名字> LAVI CHA yus Andy

Solution Code

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct list_node* list_pointer;

typedef struct list_node{

    char data[10];
    list_pointer link;
    
}ListNode;

char name[][10] = {"Jack", "Hank", "Jay", "Mimmy", "LAVI", "CHA", "yus", "Andy"};

int main(){


    ListNode *head = NULL;
    head = malloc(sizeof(ListNode));

    strcpy(head->data, "CPC");

    ListNode *last = head, *now;

    for(int i = 0; i < 8; i++){

        now = malloc(sizeof(ListNode));

        strcpy(now->data, name[i]);
        last->link = now;
        last = now;
    }
    last->link = NULL;

    list_pointer insert;
    insert = (list_pointer) malloc(sizeof(ListNode));

    strcpy(insert->data, "ShinHung");
    insert->link = NULL;

    list_pointer node = head;
    while(strcmp(node->data, "Mimmy")){

        node = node->link;
        
    }
    insert->link = node->link;
    node->link = insert;

    for(ListNode *i = head; i != NULL; i = i->link){
        printf("%s ", i->data);
    }
}

Deleting

刪除節點
遍歷找到要刪除節點的位址
更改前一節點的指標 -> 下一節點
free 歸還被刪除之節點的記憶體空間

list_pointer edge = head, ptr = edge;
    
while(ptr->data != 9){

	edge = ptr;
	ptr = ptr->link;
    
}

edge->link = ptr->link;
free(ptr);

Lab 0x4

現在試試來把你自己刪掉 !
或是要刪其他人也可以啦 owo

本題沒有輸入 Input

Output

Jack Hank Jay Mimmy LAVI CHA yus Andy

Solution Code

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct list_node* list_pointer;

typedef struct list_node{

    char data[10];
    list_pointer link;
    
}ListNode;

char name[][10] = {"Jack", "Hank", "Jay", "Mimmy", "LAVI", "CHA", "yus", "Andy"};

int main(){


    ListNode *head = NULL;
    head = malloc(sizeof(ListNode));

    strcpy(head->data, "CPC");

    ListNode *last = head, *now;

    for(int i = 0; i < 8; i++){

        now = malloc(sizeof(ListNode));

        strcpy(now->data, name[i]);
        last->link = now;
        last = now;
    }
    last->link = NULL;

    list_pointer insert;
    insert = (list_pointer) malloc(sizeof(ListNode));

    strcpy(insert->data, "ShinHung");
    insert->link = NULL;

    list_pointer node = head;
    while(strcmp(node->data, "Mimmy")){

        node = node->link;
        
    }
    insert->link = node->link;
    node->link = insert;

    list_pointer edge = head, ptr = edge;
    
    while(strcmp(ptr->data, "ShinHung")){
        edge = ptr;
        ptr = ptr->link;
    }
    edge->link = ptr->link;
    free(ptr);

    for(ListNode *i = head; i != NULL; i = i->link){
        printf("%s ", i->data);
    }
}

Circularly

循環
最後不接 NULL 改接 head

ListNode *head = NULL;
head = malloc(sizeof(ListNode));

head->data = 0;

ListNode *last = head, *now;

for(int i = 1; i < 9; i++){

  now = malloc(sizeof(ListNode));

  now->data = i;
  last->link = now;
  last = now;

}

last->link = head;

Lab 0x5

把鏈結串列頭尾連起來讓大家停不下來 !

Solution Code

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct list_node* list_pointer;

typedef struct list_node{

    char data[10];
    list_pointer link;
    
}ListNode;

char name[][10] = {"Jack", "Hank", "Jay", "Mimmy", "LAVI", "CHA", "yus", "Andy"};

int main(){


    ListNode *head = NULL;
    head = malloc(sizeof(ListNode));

    strcpy(head->data, "CPC");

    ListNode *last = head, *now;

    for(int i = 0; i < 8; i++){

        now = malloc(sizeof(ListNode));

        strcpy(now->data, name[i]);
        last->link = now;
        last = now;
    }
    last->link = head;

    for(ListNode *i = head; i != NULL; i = i->link){
        printf("%s ", i->data);
    }
    printf("\n\n");
    
}

Doubly Linked List

雙向 Linked List
左指標與右指標
- 右指標接下個節點
- 左指標接上個節點

typedef struct list_node *list_pointer;

typedef struct list_node{
    int data;
    list_pointer leftlink;
    list_pointer rightlink;
}ListNode;

ListNode *head = NULL;
head = malloc(sizeof(ListNode));

head->data = 0;
head->leftlink = NULL;

ListNode *last = head, *now;

for(int i = 1; i < 9; i++){
  now = malloc(sizeof(ListNode));
  now->data = i;

  last->rightlink = now;
  now->leftlink = last;
  last = now;
}
last->rightlink = NULL;

Insertion

插入
- 遍歷找到要插入新節點的位址
- 前一節點的右指標 -> 新節點
- 新節點的左指標 -> 前一節點
- 新節點的右指標 -> 下一節點
- 下一節點的左指標 -> 新節點

list_pointer insert;
insert = (list_pointer) malloc(sizeof(ListNode));

insert->data = 9;

list_pointer node = head, ptr = head;

while(ptr->data != 3){
  node = ptr;
  ptr = ptr->rightlink;  
}

insert->rightlink = node->rightlink;
node->rightlink->leftlink = insert;

insert->leftlink = node;
node->rightlink = insert;

Deleting

刪除
- 遍歷找到要刪除節點的位址
- 前一節點的右指標 -> 被刪除節點之下一節點
- 下一節點的左指標 -> 前一節點
- free 歸還被刪除之節點的記憶體空間

list_pointer edge = head, pt = edge;
        
while(pt->data != 9){

  edge = pt;
  pt = pt->rightlink;

}

edge->rightlink = pt->rightlink;
pt->rightlink->leftlink = edge;

free(pt);

Lab 0x6

把大家手牽手左右牽起來~

本題沒有輸入 Input

Output

from begining to end
CPC Jack Hank Jay Mimmy LAVI CHA yus Andy

from end to begining
Andy yus CHA LAVI Mimmy Jay Hank Jack CPC

Solution Code

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct list_node *list_pointer;

typedef struct list_node{

    char data[10];
    list_pointer leftlink;
    list_pointer rightlink;
    
}ListNode;

char name[][10] = {"Jack", "Hank", "Jay", "Mimmy", "LAVI", "CHA", "yus", "Andy"};

int main(){

    ListNode *head = NULL;
    head = malloc(sizeof(ListNode));

    strcpy(head->data, "CPC");
    head->leftlink = NULL;

    ListNode *last = head, *now;

    for(int i = 0; i < 8; i++){

        now = malloc(sizeof(ListNode));
        strcpy(now->data, name[i]);

        last->rightlink = now;
        now->leftlink = last;
        last = now;
    }
    last->rightlink = NULL;

    printf("from begining to end\n");
    for(ListNode *i = final; i != NULL; i = i->rightlink){
        printf("%s ", i->data);
    }

    printf("\n\nfrom end to begining\n");
    for(ListNode *i = last; i != NULL; i = i->leftlink){
        printf("%s ", i->data);
    }
}

UVA Problem

UVA 11988 - Broken Keyboard

Algorithm - Struct & Linked List

Course

Struct

初始化

直接選取運算子 .

直接選取運算子 ->

Lab 0x0

Input

Output

Solution Code

Linked List

malloc

free

用 struct 實作 linked list

創建一個 linked list 的 struct

第一個節點

新增節點

Lab 0x1

Output

Solution Code

Traverse

Lab 0x2

Solution Code

Insertion

Lab 0x3

Output

Solution Code

Deleting

Lab 0x4

Output

Solution Code

Circularly

Lab 0x5

Solution Code

Doubly Linked List

Insertion

Deleting

Lab 0x6

Output

Solution Code

UVA Problem

直接選取運算子 `.`

直接選取運算子 `->`