数据结构链表代码

简单链表

 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;
}