資料結構鍊錶程式碼

該文章使用 Google 翻譯處理。

簡單鍊錶

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


#include <stdio.h>
 
struct student
{
    long num;
    float score;
    struct student *next;
};
 
void main()
{
    struct student a, b, c, *head, *p;
    a.num = 99101; a.score = 89.5;
    b.num = 99103; b.score = 90;
    c.num = 99107; c.score = 85;  // 對結點的 num 和 score 成員賦值
    head = &a;  // 將結點 a 的起始位址賦給頭指標 head
    a.next = &b;  // 將結點 b 的起始位址賦給 a 結點的 next 成員
    b.next = &c;
    c.next = NULL;  // c 結點的 next 成員不存放其他結點位址
    p = head;  // 使 p 指標指向 a 結點
    do
    {
        printf("%ld %5.1f\n", p->num, p->score);  // 輸出 p 指向的結點的數據
        p = p->next;  // 使 p 指向下一個結點
    }while(p != NULL);  // 輸出完 c 結點後 p 的值為 NULL
    system("pause");
}

記憶體分配函數

malloc 函數

1

void *malloc(unsigned int size);

作用是在記憶體的動態儲存區中分配一個長度為 size 的連接空間。有些函數的值（即傳回值）是一個指向分配空間起始位址的指標（基底型別為 void）。如果些函數未能成功地執行（例如記憶體空間不足）則傳回空指標 NULL。

calloc 函數

1

void *calloc(unsigned n, unsigned size);

其作用是在記憶體的動態區儲存中分配 n 個長度為 size 的連續空間。函數傳回一個指向分配空間起始位址的指針，如果分配不成功，則傳回 NULL。用 calloc 函數可以為一維數組開啟動態儲存空間， n 為數組元素個數，每個元素長度為 size。

free 函數

1

void free(void *p);

其作用是釋放由 p 指向的記憶體區，使這部分記憶體區能被其它變數使用， p 是最後一次呼叫 calloc 或 malloc 函數時傳回的值。 free 函數無回傳值。請注意：以前的C版本提供的 malloc 和 calloc 函數得到的是指向字元型資料的指標。 ANSI C 提供的 malloc 和 calloc 函數規定為 void * 類型。

動態鍊錶的實現

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184


#include <stdio.h>
#include <stdlib.h>
 
#define NULL 0
#define LEN sizeof(struct student)

struct student
{
    long num;
    float score;
    struct student *next;
};
 
struct student *create()
{
    struct student *p1, *p2, *head;
    int num;
    float score;
    int n = 0;
 
    head = NULL;
 
    p1 = p2 = (struct student *)malloc(LEN);
 
    printf("please input num and score.\n");
    scanf("%d,%f", &p1->num, &p1->score);
 
    while(p1->num != 0)
    {
        n ++;
        if(n == 1)
            head = p1;
        else
            p2->next = p1;
        p2 = p1;
        p1 = (struct student *)malloc(sizeof(struct student));
 
        printf("please input num and score.\n");
 
        scanf("%d,%f", &p1->num, &p1->score);
    }
    p2->next = NULL;
    return head;
}
 
void printlist(struct student *head)
{
    struct student *p;
    p = head;
    if(head != NULL)
    {
        do
        {
            printf("num=%d score=%f\n", p->num, p->score);
            p = p->next;
        }while(p != NULL);
    }
}
 
void main()
{
    struct student *head;
    head = create();
    printlist(head);
    system("pause");
}

// 列印鍊錶
void printlist(struct student *head)
{
    struct student *p;
    p = head;

    if(head != NULL)
    {
        do 
        {
            printf("num=%d score=%5.2f\n", p->num, p->score);
            p = p->next;
        } while (p != NULL);
    }
    /* while(p -> next != NULL)
    {
        printf("num=%d score=%f\n", p->num, p->score);
        p = p->next;
    }*/
}

// 刪除節點
struct student *delNode(struct student *head, int num)
{
    printf("delNode.\n");
    struct student *p1, *p2;
    if(head == NULL)
    {
        printf("The List is NULL.\n");
    }
    else
    {
        p1 = head;
        while(p1->next != NULL && p1->num != num)
        {
            p2 = p1;
            p1 = p1->next;
        }
        if(p1->num == num)
        {
            if(p1 == head)
                head = p1->next;
            else
                p2->next = p1->next;
        }
        else
            printf("Can not find list num.\n");
    }
    return head;
}

// 更新節點
struct student *update(struct student *head, int index, int num, float score)
{
    printf("update.\n");
    struct student *p;
    if(head == NULL)
    {
        printf("The List is NULL.\n");
    }
    else
    {
        p = head;
        while(p->next != NULL && p->num != index)
        {
            p = p->next;
        }
        if(p->num == index)
        {
            p->num = num;
            p->score = score;
        }
        else
            printf("Can not find list index.\n");
    }
    return head;
}

// 增加節點
struct student *add(struct student *head, int index, int num, float score)
{
    printf("add.\n");
    struct student *p1, *p2, *p3;
    if(head == NULL)
    {
        printf("The List is NULL.\n");
    }
    else
    {
        p1 = p2 = head;
        while(p1->next != NULL && p1->num != index)
        {
            p1 = p1->next;
            p2 = p1;
        }
        if(p1->num == index)
        {
            p3 = (struct student *)malloc(LEN);
            p3->num = num;
            p3->score = score;

            if(p2->next == NULL)
            {
                p2->next = p3;
                p3->next = NULL;
            }
            else
            {
                p3->next = p2->next;
                p2->next = p3;   
            }
        }
        else
            printf("Can not find list index.\n");
    }
    return head;
}