2017年3月30日 星期四

example two for Data Structure Course

程式題目

撰寫一個linked list(連結串列)

程式範例1

/*the filename: main
 *the filename extension: .c
 */
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int data;
    struct node *next;
} N;

typedef struct a {
    int b;  //b是用來記錄串列長度
    N *head;  //head為一指標變數，用來指向連結串列之起始節點
} L;

int main(){
    L *myList;

    myList = (L *) malloc(sizeof(L));
    creatList(myList);

    insertFirstList(myList, 72);
    insertFirstList(myList, 39);
    insertFirstList(myList, 9);
    insertFirstList(myList, 23);
    printList(myList);
    return 0;
}
void creatList(L *listHead) {  //類似建構子(constructor)

    listHead->b = 0;
    listHead->head = NULL;
}

void insertFirstList(L *listHead, int data){

    N *pNew;
    pNew = (N *) malloc(sizeof(N));
    pNew->data = data;

    pNew->next = listHead->head;
    listHead->head = pNew;

    listHead->b++;
}

void printList(L *listHead){

    N *curr;
    if (listHead->head != NULL){
        printf("the total count = %d\n", listHead->b);
        for (curr = listHead->head; curr != NULL; curr = curr->next){  //curr = listHead->head：把curr的指標變數儲存listHead->head的位置
          //  printf("%d\n", listHead->head);                            //curr = listHead->next：把curr的指標變數儲存listHead->next的位置
          //  printf("%d\n", curr->next);
            printf("%d\n", curr->data);
        }
    }
    else{
        printf("the list is empty\n");
    }
}
<說明>

  • 何謂串列?

    • 有次序排列的資料稱為串列。
  • 何謂連結串列?

    • 由動態記憶體配置節點(Node)串接而成。

    與陣列的最大差別是：它的各元素之間的記憶體位置是不連續的、隨機(Random)的，不像陣列是規規矩矩的由0開始編號下去，所以這也是連結串列的一個缺點，當各位想要找取第n個串列的資料時，它必須從頭開始去找，而不能像陣列一樣直接指定讀取某個陣列內的元素(ex.a[n])。
  • 何謂節點(Node)?


    • 程式碼基本結構： 
    typedef struct node {
    int data;  //用以儲存節點資料內容
    struct node *next;  //用以紀錄下一個節點的記憶體位置
} N;
  • 以圖說明本程式的運作架構：


  • code instruction：
    L *myList;

    creatList(myList);

void creatList(L *listHead) {  //類似建構子(constructor)
 
    listHead->b = 0;
    listHead->head = NULL;
}

  insertFirstList(myList, 72);

void insertFirstList(L *listHead, int data){
 
    N *pNew;
    pNew = (N *) malloc(sizeof(N));
    pNew->data = data;
 
    pNew->next = listHead->head;
    listHead->head = pNew;
 
    listHead->b++;
}

  insertFirstList(myList, 39);

  insertFirstList(myList, 9);

  insertFirstList(myList, 23);

void printList(L *listHead){
 
    N *curr;
    if (listHead->head != NULL){
        printf("the total count = %d\n", listHead->b);
        for (curr = listHead->head; curr != NULL; curr = curr->next){  //curr = listHead->head：把curr的指標變數儲存listHead->head的位置
          //  printf("%d\n", listHead->head);                            //curr = listHead->next：把curr的指標變數儲存listHead->next的位置
          //  printf("%d\n", curr->next);
            printf("%d\n", curr->data);
        }
    }
    else{
        printf("the list is empty\n");
    }
}
第52行code：
for loop：

程式範例2

使用ADT(抽象資料型別, Abstract Data Type)的技巧來撰寫本程式

<寫法一>
/*the filename: main
 *the filename extension: .c
 */
#include <stdio.h>
#include <stdlib.h>
#include "list.h"

int main(){
    L *myList;

    myList = (L *) malloc(sizeof(L));
    creatList(myList);

    insertFirstList(myList, 72);
    insertFirstList(myList, 39);
    insertFirstList(myList, 9);
    insertFirstList(myList, 23);
    printList(myList);

}


/*the filename: list
 *the filename extension: .h
 */
#ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED

typedef struct n {
    int data;
    struct n *link;
} N;

typedef struct a {
    int b;
    N *head;
} L;

void creatList(L *listHead);
void insertFirstList(L *listHead, int data);
void printList(L *listHead);


void creatList(L *listHead) {

    listHead->b = 0;
    listHead->head = NULL;
}

void insertFirstList(L *listHead, int data){

    N *pNew;
    pNew = (N *) malloc(sizeof(N));
    pNew->data = data;

    pNew->link = listHead->head;
    listHead->head = pNew;

    listHead->b++;
}

void printList(L *listHead){

    N *curr;
    if (listHead->head != NULL){
        printf("the total count = %d\n", listHead->b);
        for (curr = listHead->head; curr != NULL; curr = curr->link){  //curr = listHead->head：把curr的指標變數儲存listHead->head的位置
          //  printf("%d\n", listHead->head);                            //curr = listHead->link：把curr的指標變數儲存listHead->link的位置
          //  printf("%d\n", curr->link);
            printf("%d\n", curr->data);
        }
    }
    else{
        printf("the list is empty\n");
    }
}
#endif // LIST_H_INCLUDED

<寫法二>
/*the filename: main
 *the filename extension: .c
 */
#include <stdio.h>
#include <stdlib.h>
#include "list.h"

int main(){
    L *myList;

    myList = (L *) malloc(sizeof(L));
    creatList(myList);

    insertFirstList(myList, 72);
    insertFirstList(myList, 39);
    insertFirstList(myList, 9);
    insertFirstList(myList, 23);
    printList(myList);

}

/*the filename: list
 *the filename extension: .h
 */
#ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED

typedef struct n {
    int data;
    struct n *link;
} N;

typedef struct a {
    int b;
    N *head;
} L;

void creatList(L *listHead);
void insertFirstList(L *listHead, int data);
void printList(L *listHead);

#endif // LIST_H_INCLUDED

/*the filename: list_implement
 *the filename extension: .c
 */
#include <stdio.h>
#include <stdlib.h>
#include "list.h"

void creatList(L *listHead) {

    listHead->b = 0;
    listHead->head = NULL;
}

void insertFirstList(L *listHead, int data){

    N *pNew;
    pNew = (N *) malloc(sizeof(N));
    pNew->data = data;

    pNew->link = listHead->head;
    listHead->head = pNew;

    listHead->b++;
}

void printList(L *listHead){

    N *curr;
    if (listHead->head != NULL){
        printf("the total count = %d\n", listHead->b);
        for (curr = listHead->head; curr != NULL; curr = curr->link){  //curr = listHead->head：把curr的指標變數儲存listHead->head的位置
          //  printf("%d\n", listHead->head);                            //curr = listHead->link：把curr的指標變數儲存listHead->link的位置
          //  printf("%d\n", curr->link);
            printf("%d\n", curr->data);
        }
    }
    else{
        printf("the list is empty\n");
    }
}
如果以上範例都理解了以後，以下這個題目相信已經難不倒各位了：
Supposedly, there is an ADT “List” contains two parts: “list.h” and “listImpl.c”. Further, there is an APP which uses ADT “List” and listed below. Use a C program to implement “listImpl.c”.      (from ccu Bo)

list.h
The main function of App
typedef struct node {
    int data;
    struct node *link;
} NODE;
typedef struct list {
    int count;
    struct node *head;
} LIST;
void creatList(LIST *listHead);
void insertFirstList(LIST *listHead, int data);
void printList(LIST *listHead);
….
int main(){
    LIST *myList;
    NODE *pNew, *pNew1;
    myList = (LIST *) malloc(sizeof(LIST));
    creatList(myList);
    insertFirstList(myList, 72);
    insertFirstList(myList, 39);
    printList(myList);
}
張貼者： 於

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)