数据结构 二 线性表

数据结构 线性表
数据结构 线性表
发布日期:   2021-06-24

线性表 新的实现

更新日期：202107021044

链表在ADT一节中已经实现过了，不过实现的并不是特别的完善，只是一个ADT的使用例子而已，现在正式地将链表进行实现。
本系列参考数据结构严蔚敏c语言版、c primer plus、STL进行实现

ADT

  1. 构造一个空线性表
  2. 销毁一个线性表
  3. 清空线性表
  4. 判断线性表是否为空
  5. 获得线性表中元素的个数
  6. 获得特定位置元素
  7. 返回第一个满足关系的元素位置
  8. 返回某元素的前驱
  9. 返回某元素的后继
  10. 再特定位置插入元素
  11. 删除特定位置的元素
  12. 使用特定的函数遍历所有元素

线性表的顺序实现

接口说明

由于c语言不支持c++那样的引用操作，所以我的实现和教材上略有不同。

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
//线性表 重新实现
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <time.h>

typedef struct Item
{
    int value;
} Item;

typedef struct LinearList
{
    //存放元素
    Item *items;
    //当前长度
    int length;
    //当前分配的存储容量
    int listsize;
} * LinearList;

//初始化
bool InitLinearList(LinearList(*List), int initsize);

//销毁
bool DestroyLinearList(LinearList(*List));

//清空
bool ClearLinearList(LinearList(*List));

//判断是否为空
bool EmptyLinearList(LinearList(*List));

//full
bool FullLinearList(LinearList(*List));

//获得元素
bool GetItemLinearList(LinearList(*List), int location, Item *itemsave);

//定位第一个满足条件的元素
int LocateLinearList(LinearList(*List), bool (*fun)(Item item));

//插入
bool InsertLinearList(LinearList(*List), int location, Item *item);

//删除
bool DeleteLinearList(LinearList(*List), int location);

void TraverseLinearList(LinearList(*List), void (*fun)(Item item));

void AutoFillLinearList(LinearList(*List));

接口实现

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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
#include "linearlist.h"

bool InitLinearList(LinearList(*List), int initsize)
{
    //根据下面的论断更正后 List 是指向 LinearList 的指针。
    //malloc (*List)    因为这里重新给 (*List) 分配内存了，所以 现在的List 不指向传进来的参数的List的指向，所以相当于这一切的初始化白做了。
    //这就是为什么书上的函数都是直接取变量的地址了，这样在函数中再反取地址就可以直接更改源数据了。
    //也可以在函数中自己重新定义一个一样的数据，完成之后赋值给传进来的参数，但是这样在有些情况写太费了，不好。
    (*List) = (struct LinearList *)malloc(sizeof(struct LinearList));
    //malloc items
    (*List)->items = (Item *)malloc(initsize * sizeof(Item));
    if (!(*List)->items)
    {
        printf("你要的空间太大了，分配不了\n");
        return false;
    }
    else
    {
        (*List)->length = 0;
        (*List)->listsize = initsize;
        printf("初始化成功,容量为%d\n", (*List)->listsize);
        return true;
    }
}

//销毁
bool DestroyLinearList(LinearList(*List))
{
    free((*List)->items);
    (*List)->items = NULL;
    free((*List));
    (*List) = NULL;
    if ((*List) == NULL)
    {
        printf("销毁成功\n");
        return true;
    }
    else
    {
        printf("销毁失败\n");
        return false;
    }
}

//清空
bool ClearLinearList(LinearList(*List))
{
    (*List)->length = 0;
    printf("清空成功\n");
    return true;
}

//判断是否为空
bool EmptyLinearList(LinearList(*List))
{
    if ((*List)->length == 0)
    {
        printf("空\n");
        return true;
    }
    else
    {
        printf("不空\n");
        return false;
    }
}

bool FullLinearList(LinearList(*List))
{
    if ((*List)->length == (*List)->listsize)
    {
        printf("满了\n");
        return true;
    }
    else
    {
        printf("没有满\n");
        return false;
    }
}
//获得元素
bool GetItemLinearList(LinearList(*List), int location, Item *itemsave)
{
    if (location < 0 || location >= (*List)->length)
    {
        printf("范围超限\n");
        return false;
    }
    else
    {
        *itemsave = (*List)->items[location];
    }
}

//定位第一个满足条件的元素
int LocateLinearList(LinearList(*List), bool (*fun)(Item item))
{
    for (int i = 0; i <= (*List)->length; i++)
    {
        if (fun((*List)->items[i]))
        {
            printf("第一个满足条件的元素在%d\n", i);
            return i;
        }
    }
    printf("没有元素满足条件\n");
    return -1;
}

//插入  这个函数有问题 内存
bool InsertLinearList(LinearList(*List), int location, Item *item)
{
    printf("InsertLinearList\n");
    if (FullLinearList(List))
    {
        //自动申请扩容
        printf("满了，自动申请扩容.\n");

        if (List == NULL)
        {
            printf("List is NULL\n");
        }
        if (*List == NULL)
        {
            printf("*List is NULL\n");
        }
        if ((*List)->items == NULL)
        {
            printf("(*List)->items is NULL\n");
        }

        (*List)->items = (Item *)realloc((*List)->items, ((*List)->listsize + 1) * sizeof(Item));
        if ((*List)->items)
        {
            (*List)->listsize++;
            printf("自动申请扩容, 成功,当前容量为%d\n", (*List)->listsize);
        }
        else
        {
            printf("自动申请扩容, 失败，插入失败\n");
            (*List)->items = NULL;
            return false;
        }
    }
    (*List)->length++;
    if (location < 0)
    {
        location = 0;
    }
    else if (location >= (*List)->length)
    {
        location = (*List)->length - 1;
    }
    for (int i = (*List)->length - 1; i >= location + 1; i--)
    {
        (*List)->items[i] = (*List)->items[i - 1];
    }
    (*List)->items[location] = *item;
    printf("插入成功,当前容量为%d,可用容量为%d\n", (*List)->listsize, (*List)->listsize - (*List)->length);
    return true;
}

//删除
bool DeleteLinearList(LinearList(*List), int location)
{
    if (location < 0 || location >= (*List)->length)
    {
        printf("删除的范围错误\n");
        return false;
    }
    else
    {
        for (int i = location; i <= (*List)->length - 2; i++)
        {
            (*List)->items[i] = (*List)->items[i + 1];
        }
        (*List)->length--;
    }
    printf("删除成功\n");
    return true;
}

void TraverseLinearList(LinearList(*List), void (*fun)(Item item))
{
    for (int i = 0; i <= (*List)->length - 1; i++)
    {
        fun((*List)->items[i]);
    }
}

void AutoFillLinearList(LinearList(*List))
{
    int listsize = (*List)->listsize;
    for (int i = 1; i <= listsize * 2; i++)
    {
        srand((double)time(NULL) * i);
        Item item;
        item.value = rand() % ((*List)->listsize);
        item.value = i;
        InsertLinearList(List, i, &item);
    }
}

bool KuoRong(LinearList *List)
{
    if (FullLinearList(List))
    {
        (*List)->items = (Item *)realloc((*List)->items, (*List)->listsize + 1);
        if ((*List)->items)
        {
            (*List)->listsize++;
            printf("自动申请扩容, 成功,当前容量为%d\n", (*List)->listsize);
        }
        else
        {
            printf("自动申请扩容, 失败，插入失败\n");
            return false;
        }
    }
    (*List)->length++;
    return true;
}

接口使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include "linearlist.c"

bool fun1(Item item)
{
    if (item.value >= 100)
        return true;
    return false;
}
void fun2(Item item)
{
    printf("item: %d\n", item.value);
}
int main()
{
    LinearList List = NULL;
    Item itemsave;
    InitLinearList(&List, 10);
    AutoFillLinearList(&List);
    GetItemLinearList(&List, 1, &itemsave);
    printf("item: %d\n", itemsave.value);
    TraverseLinearList(&List, (*fun2));
    DestroyLinearList(&List);
}

线性表的链性实现

接口说明

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
//链表
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <time.h>

#define AUTOFILLSIZE 10

typedef struct Item
{
    int value;
} Item;

typedef struct Node
{
    Item item;
    struct Node *next;
    //先实现单向链表
    //struct Node * prev;
} Node, *LinkList;

//初始化
bool InitLinkList(LinkList(*list));

//销毁
bool DestroyLinkList(LinkList(*list));

//清空
bool ClearLinkList(LinkList(*list));

//判断是否为空
bool EmptyLinkList(LinkList(*list));

//full
bool FullLinkList(LinkList(*list));

//获得元素
bool GetItemLinkList(LinkList(*list), int location, Item *itemsave);

//定位第一个满足条件的元素
int LocateLinkList(LinkList(*list), bool (*fun)(Item item));

//插入
bool InsertLinkList(LinkList(*list), int location, Item *item);

//删除
bool DeleteLinkList(LinkList(*list), int location);

void TraverseLinkList(LinkList(*list), void (*fun)(Item item));

void AutoFillLinkList(LinkList(*list));

接口实现

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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
#include "linklist.h"

//初始化
bool InitLinkList(LinkList(*list))
{
    (*list) = NULL;
    printf("初始化LinkList成功\n");
    return true;
}

//销毁
bool DestroyLinkList(LinkList(*list))
{
    LinkList p = (*list);
    while (p != NULL)
    {
        LinkList q = p->next;
        free(p);
        p = q;
    }
    (*list) = NULL;
    printf("销毁LinkList成功\n");
    return true;
}

//清空
bool ClearLinkList(LinkList(*list))
{
    DestroyLinkList(list);
}

//判断是否为空
bool EmptyLinkList(LinkList(*list))
{
    if ((*list) == NULL)
    {
        printf("链表空\n");
        return true;
    }
    else
    {
        printf("链表不空\n");
        return false;
    }
}

//full
bool FullLinkList(LinkList(*list))
{
    LinkList p = (LinkList)malloc(sizeof(Node));
    if (p == NULL)
    {
        printf("满了\n");
        return true;
    }
    else
    {
        printf("不满\n");
        return false;
    }
}

//获得元素
bool GetItemLinkList(LinkList(*list), int location, Item *itemsave)
{
    LinkList p = (*list);
    for (int i = 0; i <= location - 1; i++)
    {
        if (p == NULL)
        {
            printf("没有找到这个元素\n");
            itemsave = NULL;
        }
        else
        {
            p = p->next;
        }
    }
    //现在p指向location元素
    if (p == NULL)
    {
        printf("没有找到这个元素\n");
        //直接改变itemsave时改变形参，对外面的实参没有任何影响。
        //itemsave = NULL;
        return false;
    }
    else
    {
        //这里itemsave肯定要提前申请好内存
        //为了兼容性，直接改变itemsave的指向即可，不需要其事先拥有内存。
        //直接改变itemsave时改变形参，对外面的实参没有任何影响。  只有 *itemsave=    才会有作用。
        //假如要不申请内存 直接改变传入的实参的指针指向的话需要使用二重指针。不过这样有点麻烦了。不如申请内存了事
        *itemsave = p->item;
        printf("找到了，第%d元素的值为%d\n", location, p->item.value);
        return true;
    }
}

//定位第一个满足条件的元素
int LocateLinkList(LinkList(*list), bool (*fun)(Item item))
{
    LinkList p = (*list);
    int location = 0;
    while (p != NULL)
    {
        if (fun(p->item))
        {
            printf("第一个满足条件的元素为第%d\n", location);
            return location;
        }
        else
        {
            p = p->next;
        }
    }
    printf("没有满足条件的元素\n");
}

//获得元素个数
int CountLinkList(LinkList(*list))
{
    LinkList p = (*list);
    int count = 0;
    while (p != NULL)
    {
        p = p->next;
        count++;
    }
    return count;
}

//插入
bool InsertLinkList(LinkList(*list), int location, Item *item)
{
    if (FullLinkList(list))
    {
        printf("满了，无法插入\n");
        return false;
    }
    LinkList new = (LinkList)malloc(sizeof(Node));
    new->item = *item;
    new->next = NULL;
    LinkList p = (*list);
    //本为空
    if (EmptyLinkList(list))
    {
        (*list) = new;
        printf("插入成功\n");
        return true;
    }
    //头插 要移动头节点
    else if (location <= 0)
    {
        location = 0;
        //new->next=p;
        //p=new;
        new->next = (*list);
        (*list) = new;
        printf("插入成功\n");
        return true;
    }
    //尾插
    else if (location >= CountLinkList(list))
    {
        location = CountLinkList(list);
        while (p->next != NULL)
        {
            p = p->next;
        }
        p->next = new;
        printf("插入成功\n");
        return true;
    }
    //中间插
    else
    {
        while (location != 1)
        {
            location--;
            p = p->next;
        }
        //插到p后面
        new->next = p->next;
        p->next = new;
        printf("插入成功\n");
        return true;
    }
    printf("插入失败\n");
    return false;
}

//删除
bool DeleteLinkList(LinkList(*list), int location)
{
    if (EmptyLinkList(list))
    {
        printf("空，无法删除\n");
        return false;
    }

    if (location < 0)
    {
        location = 0;
    }
    else if (location >= CountLinkList(list) - 1)
    {
        location = CountLinkList(list) - 1;
    }

    //删除第零个元素
    if (location == 0)
    {
        location = 0;
        LinkList p = (*list);
        (*list) = (*list)->next;
        free(p);
        printf("删除成功\n");
        return true;
    }
    else if (location <= CountLinkList(list) - 1)
    {
        LinkList p = (*list);
        while (location != 1)
        {
            location--;
            p = p->next;
        }
        //删除p->next
        LinkList del = p->next;
        p->next = p->next->next;
        free(del);
        printf("删除成功\n");
        return true;
    }
}

void TraverseLinkList(LinkList(*list), void (*fun)(Item item))
{
    LinkList p = (*list);
    while (p != NULL)
    {
        fun(p->item);
        p = p->next;
    }
}

void AutoFillLinkList(LinkList(*list))
{
    for (int i = 0; i <= AUTOFILLSIZE; i++)
    {
        Item item;
        item.value = i;
        InsertLinkList(list, i, &item);
    }
}

接口使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include "linklist.c"

void fun(Item item)
{
    printf("item: %d\n", item.value);
}

int main()
{
    LinkList list;
    Item itemsave; //= (Item *)malloc(sizeof(Item));
    InitLinkList(&list);
    AutoFillLinkList(&list);

    //由于是值传递，所以传入指针的值，在函数中进行更改不会改变实参的数据。
    GetItemLinkList(&list, 2, &itemsave);
    printf("item: %d\n", itemsave.value);

    //TraverseLinkList(&list,(*fun));
    //DeleteLinkList(&list,5);
    //TraverseLinkList(&list,(*fun));
    //DestroyLinkList(&list);
}

旧的实现

我觉得之前的这个实现不优雅，所以重现实现一遍，旧代码封存。

线性表的ADT

  1. 构造一个空的线性表
  2. 销毁—个线性表
  3. 清空一个线性表中的所有元素，重置为空表
  4. 判断是否为空表
  5. 判断是否已满
  6. 确定元素个数
  7. 返回表的容量
  8. 增加容量
  9. 减少容量
  10. 将容量减少到当前实际使用的大小
  11. 得到线性表第i个元素的值
  12. 返回第一个满足特定要求的元素的位置 定位元素
  13. 返回最后一个满足特定要求的元素的位置 定位元素
  14. 返回某元素的前驱 15. 返回一个元素的后继
  15. 在第i个位置之前插入新的元素，使其称为新的第i个元素
  16. 删除第i个元素
  17. 使用特定的函数遍历线性表中每一个元素
  18. 对线性表进行排序，排序规则为默认的升序
  19. 对线性表进行排序，自定义排序规则
  20. 将两个线性表合并
  21. 将一个线性表复制为另一个线性表

其实链表最重要的是学会链表的思想，即使用指针将处于分散内存的数据连接起来，以及相关数据结点的定义和操作，学会了这些才能为之后的树和图打下基础，也可以自己实现更加高级的数据结构

线性表的顺序实现

接口说明

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
//线性表的顺序实现
#include <stdbool.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <stdio.h>
#define MAX_ITEM_COUNT 100

//这是链表的数据部分
typedef struct
{
    int value;
} Item;

//顺序性的链表中的一个结点的定义
typedef struct
{
    //位置 指名是第几个元素
    int location;
} Node;

//顺序性的链表的定义 List 是指向顺序表的一个指针
struct Data
{
    //存储数据
    Item *items;
    //存储的数据大小
    int size;
    //最大可以容纳的数据大小
    int capacity;
};
typedef struct Data ListStruct;
typedef ListStruct *List;

//初始化一个空的顺序表
//输入链表，希望获取的容量的大小。
//成功则返回true,反之则返回false
bool Initialize(List *list, int capacity);

//销毁一个顺序表
//输入一个顺序表，释放其所有内存
//成功则返回true,反之则返回false
bool Destroy(List *list);

//清空一个顺序表
//清空一个顺序表，但是不要释放其内存
//成功则返回true,反之则返回false
bool Clear(List *list);

//判断是否为空表
//空表则返回true,反之则返回false
bool Empty(List *list);

//判断是否已满
//满则返回true,反之则返回false
//对于顺序表来讲满的话就不能添加元素了，因为申请的内存已经确定了，
//但是链表还可以增加，因为可以再申请内存
bool Full(List *list);

//确定元素个数
//返回元素的个数
int Count(List *list);

//确定当前容量
//返回当前容量
int Capacity(List *list);

//增加容量为
//成功则返回true
bool AddCapacityTo(List *list, int addcapacity);
//减少容量为
//成功则返回true
bool SubCapacityTo(List *list, int subcapacity);
//将容量减少到当前实际使用的大小
bool Shrink_To_Fit(List *list);

//得到第i个元素 成功返回true
//将得到的item返回给 item_to_save
bool At(List *list, int i, Item *item_to_save);

//返回第一个满足要求的元素的位置，并保存这个元素
//将得到的item返回给 item_to_save    位置返回给location
//若不存在则返回-1
int LocateFirst(List *list, Item *item_to_save, bool (*fun)(Item item));

//返回最后一个满足要求的元素的位置，并保存这个元素
//将得到的item返回给 item_to_save    位置返回给location
//若不存在则返回-1
int LocateLast(List *list, Item *item_to_save, bool (*fun)(Item item));

//返回元素node的前驱 存放在Node*previous
//若没有则返回false
bool Previous(List *list, Node *node, Node *previous);

//返回元素node的后继 存放在Node*success
//若没有则返回false
bool Success(List *list, Node *node, Node *success);

//在第i个位置之前插入新的元素，使其称为新的第i个元素
//成功则返回true
bool Insert(List *list, int location, Item item);

//删除第i个元素
//成功则返回true
bool Delete(List *list, int location);

//使用特定的函数遍历顺序表中的每一个元素
void Traverse(List *list, void (*fun)(Item item));

//对线性表进行升序排序
void Sort_Up(List *list);
//对线性表进行降序排序
void Sort_Down(List *list);
//自定义函数排序
void Sort_DIY(List *list, bool (*fun)(Item cur, Item next));

//合并两个线性表(简单拼接不排序)返回新的list
//成功则返回true
bool Merge(List *list1, List *list2, List *list);

//复制线性表
bool Copy(List *list_tobe_copied, List *List_copied_to);

接口实现

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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
#include "list.h"

//顺序性的链表的定义 List 是指向顺序表的一个指针
/*
typedef struct
{
    //存储数据
    Item *items;
    //存储的数据大小
    int size;
    //最大可以容纳的数据大小
    int capacity;
} *List;
*/
//初始化一个空的顺序表
//输入链表，希望获取的容量的大小。
//成功则返回true,反之则返回false
bool Initialize(List *list, int capacity)
{
    //List是指向顺序表的指针，list是指向该指针的指针
    (*list) = (ListStruct *)malloc(sizeof(ListStruct));
    (*list)->capacity = capacity;
    (*list)->size = 0;
    (*list)->items = (Item *)malloc(capacity * sizeof(Item));
    if ((*list)->items != NULL)
    {
        printf("初始化成功！！！   表的可用容量为%d\n", (*list)->capacity);
        return true;
    }
    else
    {
        printf("初始化失败！！！\n");
        return false;
    }
}

//销毁一个顺序表
//输入一个顺序表，释放其所有内存
//成功则返回true,反之则返回false
bool Destroy(List *list)
{
    free((*list)->items);
    free(*list);
    printf("销毁顺序表成功！！！\n");
    return true;
}

//清空一个顺序表
//清空一个顺序表，但是不要释放其内存
//成功则返回true,反之则返回false
bool Clear(List *list)
{
    (*list)->size = 0;
    printf("已清空表，当前表中元素个数为%d,表的可用容量为%d\n", (*list)->size, (*list)->capacity - (*list)->size);
    return true;
}

//判断是否为空表
//空表则返回true,反之则返回false
bool Empty(List *list)
{
    if ((*list)->size == 0)
    {
        printf("空表！！！\n");
        return true;
    }
    else
    {
        printf("不是空表！！！\n");
        return false;
    }
}

//判断是否已满
//满则返回true,反之则返回false
//对于顺序表来讲满的话就不能添加元素了，因为申请的内存已经确定了，
//但是链表还可以增加，因为可以再申请内存
bool Full(List *list)
{
    if ((*list)->size == (*list)->capacity)
    {
        printf("满了！！！\n");
        return true;
    }
    else
    {
        printf("还没有满！！！\n");
        return false;
    }
}
//确定元素个数
//返回元素的个数
int Count(List *list)
{
    printf("当前表中元素个数为%d\n", (*list)->size);
    return (*list)->size;
}

//确定表的容量
//返回表的容量
int Capacity(List *list)
{
    printf("表的容量为%d ,表的可用容量为%d\n", (*list)->capacity, (*list)->capacity - (*list)->size);
    return (*list)->capacity;
}

//增加容量为
//成功则返回true
bool AddCapacityTo(List *list, int addcapacity)
{
    int curcapacity = (*list)->capacity;
    if (addcapacity >= curcapacity)
    {
        (*list)->items = (Item *)realloc((*list)->items, addcapacity * sizeof(Item));
        (*list)->capacity = addcapacity;
        printf("容量增加成功！！！\n");
        printf("表的容量为%d ,表的可用容量为%d\n", (*list)->capacity, (*list)->capacity - (*list)->size);
    }
    else
    {
        printf("容量增加函数不可以减小容量\n");
        printf("表的容量为%d ,表的可用容量为%d\n", (*list)->capacity, (*list)->capacity - (*list)->size);
        return false;
    }
}
//减少容量为
//成功则返回true
bool SubCapacityTo(List *list, int subcapacity)
{
    int curcapacity = (*list)->capacity;
    if (subcapacity <= curcapacity && subcapacity > 0)
    {
        (*list)->items = (Item *)realloc((*list)->items, subcapacity * sizeof(Item));
        (*list)->capacity = subcapacity;
        if ((*list)->size > subcapacity)
        {
            (*list)->size = subcapacity;
        }
        printf("容量减少成功！！！\n");
        printf("表的容量为%d ,表的可用容量为%d\n", (*list)->capacity, (*list)->capacity - (*list)->size);
    }
    else if (subcapacity <= 0)
    {
        printf("容量只可以为正数\n");
        printf("表的容量为%d ,表的可用容量为%d\n", (*list)->capacity, (*list)->capacity - (*list)->size);
        return false;
    }
    else
    {
        printf("容量减少函数不可以增加容量\n");
        printf("表的容量为%d ,表的可用容量为%d\n", (*list)->capacity, (*list)->capacity - (*list)->size);
        return false;
    }
}
//将容量减少到当前实际使用的大小
bool Shrink_To_Fit(List *list)
{
    (*list)->items = (Item *)realloc((*list)->items, (*list)->size * sizeof(Item));
    //表为空的情况下fit也应该成立
    if ((*list)->items != NULL || ((*list)->items == NULL && (*list)->size == 0))
    {
        (*list)->capacity = (*list)->size;
        printf("fit成功！！！表的容量为%d ,表的可用容量为%d\n", (*list)->capacity, (*list)->capacity - (*list)->size);
        return true;
    }
    else
    {
        printf("fit失败！！！表的容量为%d ,表的可用容量为%d\n", (*list)->capacity, (*list)->capacity - (*list)->size);
        return false;
    }
}

//得到第i个元素 成功返回true
//将得到的item返回给 item_to_save
bool At(List *list, int location, Item *item_to_save)
{
    if (location < 0 || location >= (*list)->size)
    {
        printf("AT超限！！！\n");
        return false;
    }
    *item_to_save = (*list)->items[location];
    printf("这就是你AT的元素\n");
    return true;
}

//返回第一个满足要求的元素的位置，并保存这个元素
//将得到的item返回给 item_to_save    位置返回给location
//若不存在则返回-1
int LocateFirst(List *list, Item *item_to_save, bool (*fun)(Item item))
{
    int location = -1;
    for (int i = 0; i <= (*list)->size - 1; i++)
    {
        if (fun((*list)->items[i]))
        {
            location = i;
            *item_to_save = (*list)->items[i];
            break;
        }
    }
    if (location != -1)
    {
        printf("找到了，第%d个元素满足条件\n", location);
    }
    else
    {
        printf("没有找到满足条件的元素\n");
    }
    return location;
}

//返回最后一个满足要求的元素的位置，并保存这个元素
//将得到的item返回给 item_to_save    位置返回给location
//若不存在则返回-1
int LocateLast(List *list, Item *item_to_save, bool (*fun)(Item item))
{
    int location = -1;
    for (int i = (*list)->size - 1; i >= 0; i--)
    {
        if (fun((*list)->items[i]))
        {
            location = i;
            *item_to_save = (*list)->items[i];
            break;
        }
    }
    if (location != -1)
    {
        printf("找到了，第%d个元素满足条件\n", location);
    }
    else
    {
        printf("没有找到满足条件的元素\n");
    }
    return location;
}

//返回元素node的前驱 存放在Node*previous
//若没有则返回false
bool Previous(List *list, Node *node, Node *previous)
{
    if (node->location >= 1 && node->location <= (*list)->size - 1)
    {
        previous->location = node->location - 1;
        printf("找到了前驱！！！\n");
        return true;
    }
    else
    {
        printf("没有前驱！！！\n");
        return false;
    }
}

//返回元素node的后继 存放在Node*success
//若没有则返回false
bool Success(List *list, Node *node, Node *success)
{
    if (node->location >= 0 && node->location <= (*list)->size - 2)
    {
        success->location = node->location + 1;
        printf("找到了后继！！！\n");
        return true;
    }
    else
    {
        printf("没有后继！！！\n");
        return false;
    }
}

//在第i个位置之前插入新的元素，使其称为新的第i个元素
//成功则返回true
bool Insert(List *list, int location, Item item)
{
    if ((*list)->size == (*list)->capacity)
    {
        printf("满了，不能插入！！！\n");
        return false;
    }
    else if (location < 0 || location > (*list)->size)
    {
        printf("插入位置不合法！！！\n");
        return false;
    }
    else if ((*list)->size < (*list)->capacity)
    {
        for (int i = (*list)->size; i != location; i--)
        {
            (*list)->items[i] = (*list)->items[i - 1];
        }
        (*list)->items[location] = item;
        (*list)->size++;
        printf("插入成功！！！\n");
        printf("表的大小为%d ,表的容量为%d ,表的可用容量为%d\n", (*list)->size, (*list)->capacity, (*list)->capacity - (*list)->size);
        return true;
    }
}

//删除第i个元素
//成功则返回true
bool Delete(List *list, int location)
{
    if (location < 0 || location >= (*list)->size)
    {
        printf("插入位置不合法！！！\n");
        return false;
    }
    else
    {
        for (int i = location; i <= (*list)->size - 2; i++)
        {
            (*list)->items[i] = (*list)->items[i + 1];
        }
        (*list)->size--;
        printf("删除成功！！！\n");
        printf("表的大小为%d ,表的容量为%d ,表的可用容量为%d\n", (*list)->size, (*list)->capacity, (*list)->capacity - (*list)->size);
        return true;
    }
}

//使用特定的函数遍历顺序表中的每一个元素
void Traverse(List *list, void (*fun)(Item item))
{
    for (int i = 0; i <= (*list)->size - 1; i++)
    {
        fun((*list)->items[i]);
    }
}

//对线性表进行升序排序
void Sort_Up(List *list)
{
    int n = (*list)->size;
    for (int i = 0; i <= n - 1; i++)
    {
        for (int j = 0; j <= n - 1 - i; j++)
        {
            if ((*list)->items[j].value > (*list)->items[j - 1].value)
            {
                Item temp = (*list)->items[j];
                (*list)->items[j] = (*list)->items[j - 1];
                (*list)->items[j - 1] = temp;
            }
        }
    }
}
//对线性表进行降序排序
void Sort_Down(List *list)
{
    int n = (*list)->size;
    for (int i = 0; i <= n - 1; i++)
    {
        for (int j = 0; j <= n - 1 - i; j++)
        {
            if ((*list)->items[j].value < (*list)->items[j - 1].value)
            {
                Item temp = (*list)->items[j];
                (*list)->items[j] = (*list)->items[j - 1];
                (*list)->items[j - 1] = temp;
            }
        }
    }
}
//自定义函数排序
void Sort_DIY(List *list, bool (*fun)(Item cur, Item next))
{
    int n = (*list)->size;
    for (int i = 0; i <= n - 1; i++)
    {
        for (int j = 0; j <= n - 2; j++)
        {
            if (fun((*list)->items[j], (*list)->items[j + 1]))
            {
                Item temp = (*list)->items[j];
                (*list)->items[j] = (*list)->items[j + 1];
                (*list)->items[j + 1] = temp;
            }
        }
    }
}

//合并两个线性表(简单拼接不排序)返回新的list
//成功则返回true
bool Merge(List *list1, List *list2, List *list)
{
    int size = (*list)->size;
    int size1 = (*list1)->size;
    int size2 = (*list2)->size;
    int capacity = (*list)->capacity;
    int capacity1 = (*list1)->capacity;
    int capacity2 = (*list2)->capacity;
    if (capacity < size1 + size2)
    {
        printf("目的表太小了！！！\n");
        return false;
    }
    else
    {
        int cur = 0;
        (*list)->size = 0;
        for (int i = 0; i <= size1 - 1; i++)
        {
            (*list)->items[cur++] = (*list1)->items[i];
            (*list)->size++;
        }
        for (int i = 0; i <= size2 - 1; i++)
        {
            (*list)->items[cur++] = (*list2)->items[i];
            (*list)->size++;
        }
        return true;
    }
}

//复制线性表
bool Copy(List *list_tobe_copied, List *List_copied_to)
{
    int size1 = (*list_tobe_copied)->size;
    int size2 = (*List_copied_to)->size;
    int capacity1 = (*list_tobe_copied)->capacity;
    int capacity2 = (*List_copied_to)->capacity;
    if (capacity2 < size1)
    {
        printf("目标顺序表容量太小了，装不下！！！\n");
    }
    else
    {
        Clear(List_copied_to);
        for (int i = 0; i <= size1 - 1; i++)
        {
            (*List_copied_to)->size++;
            (*List_copied_to)->items[i] = (*list_tobe_copied)->items[i];
        }
    }
}

接口使用

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
#include "list.c"
#include <time.h>
#define MAX_CAPACITY 100
bool fun1(Item item)
{
    if (item.value >= 10)
        return true;
    else
        return false;
}
void fun2(Item item)
{
    printf("元素： %d\n", item.value);
}
bool fun_sort(Item item1, Item item2)
{
    if (item1.value > item2.value)
        return true;
    else
        return false;
}
int main()
{
    List mylist;
    Item myitem1;
    myitem1.value = 0;
    Item item_to_save;
    Node node1;
    node1.location = 1;
    Node nodeprevious;
    Node nodesuccess;
    Initialize(&mylist, MAX_CAPACITY);
    //Destroy(&mylist);
    Clear(&mylist);
    Insert(&mylist, 0, myitem1);
    Delete(&mylist, 0);
    Empty(&mylist);
    Full(&mylist);
    Count(&mylist);
    Capacity(&mylist);
    AddCapacityTo(&mylist, MAX_CAPACITY + 1);
    SubCapacityTo(&mylist, 10);
    //Shrink_To_Fit(&mylist);
    At(&mylist, 0, &myitem1);
    LocateFirst(&mylist, &item_to_save, (*fun1));
    LocateLast(&mylist, &item_to_save, (*fun1));
    Previous(&mylist, &node1, &nodeprevious);
    Success(&mylist, &node1, &nodesuccess);
    for (int i = 1; i <= 10; i++)
    {
        myitem1.value = i;
        Insert(&mylist, 0, myitem1);
    }
    //Sort_Up(&mylist);
    Sort_DIY(&mylist, (*fun_sort));
    Traverse(&mylist, (*fun2));

    List mylist1;
    List mylist2;
    Initialize(&mylist1, 10);
    Initialize(&mylist2, 10);
    for (int i = 1; i <= 10; i++)
    {
        srand((int)time(NULL) * i);
        myitem1.value = rand() % 100;
        Insert(&mylist1, 0, myitem1);
    }
    for (int i = 1; i <= 10; i++)
    {
        srand((int)time(NULL) * i);
        myitem1.value = rand() % 10;
        Insert(&mylist2, 0, myitem1);
    }
    AddCapacityTo(&mylist, 100);
    Merge(&mylist1, &mylist2, &mylist);
    Traverse(&mylist, (*fun2));

    List mylist3;
    Initialize(&mylist3, 100);
    Copy(&mylist, &mylist3);
    Traverse(&mylist3, (*fun2));
}

线性表的链性实现

接口说明

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
//list.h
//线性表的链性实现
#include <stdbool.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <stdio.h>

//这是链表的数据部分
typedef struct
{
    int value;
} Item;

//顺序性的链表中的一个结点的定义
struct node
{
    Item item;
    struct node *next;
    struct node *prev;
};

typedef struct node Node;

//List指针指向Node结点
typedef Node *List;

//初始化一个空的顺序表
//输入链表，希望获取的容量的大小。
//成功则返回true,反之则返回false
bool Initialize(List *list);

//销毁一个链表
//输入一个链表，释放其所有内存
//成功则返回true,反之则返回false
bool Destroy(List *list);

//判断是否为空表
//空表则返回true,反之则返回false
bool Empty(List *list);

//判断是否已满
//满则返回true,反之则返回false
//对于顺序表来讲满的话就不能添加元素了，因为申请的内存已经确定了，
//但是链表还可以增加，因为可以再申请内存
bool Full(List *list);

//确定元素个数
//返回元素的个数
int Count(List *list);

//得到第i个元素 成功返回true
//将得到的item返回给 item_to_save
bool At(List *list, int i, Item *item_to_save);

//返回第一个满足要求的元素的位置，并保存这个元素
//将得到的item返回给 item_to_save    位置返回给location
//若不存在则返回-1
int LocateFirst(List *list, Item *item_to_save, bool (*fun)(Item item));

//返回最后一个满足要求的元素的位置，并保存这个元素
//将得到的item返回给 item_to_save    位置返回给location
//若不存在则返回-1
int LocateLast(List *list, Item *item_to_save, bool (*fun)(Item item));

//在第i个位置之前插入新的元素，使其称为新的第i个元素
//成功则返回true
bool Insert(List *list, int location, Item item);

//删除第i个元素
//成功则返回true
bool Delete(List *list, int location);

//使用特定的函数遍历顺序表中的每一个元素
void Traverse(List *list, void (*fun)(Item item));

//自定义函数排序
void Sort_DIY(List *list, bool (*fun)(Item cur, Item next));

//合并两个线性表(简单拼接不排序)返回新的list
//成功则返回true
bool Merge(List *list1, List *list2, List *list);

//复制线性表
bool Copy(List *list_tobe_copied, List *List_copied_to);

接口实现

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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
//list.c
#include "list.h"

//初始化一个空的顺序表
//输入链表，希望获取的容量的大小。
//成功则返回true,反之则返回false
bool Initialize(List *list)
{
    *list = NULL;
    if (*list == NULL)
    {
        printf("初始化成功\n");
        return true;
    }

    else
    {
        printf("初始化失败\n");
        return false;
    }
}

//销毁一个链表
//输入一个链表，释放其所有内存
//成功则返回true,反之则返回false
bool Destroy(List *list)
{
    //先找到链表的头
    List head = *(list);
    //若为空则说明链表为空
    if (head == NULL)
        return true;
    while (head->prev != NULL)
    {
        head = head->prev;
    }
    printf("到了head\n");
    while (head->next != NULL)
    {
        head = head->next;
        free(head->prev);
    }
    free(head);
    *list = NULL;
    printf("链表已经销毁了\n");
    return true;
}

//判断是否为空表
//空表则返回true,反之则返回false
bool Empty(List *list)
{
    //先找到链表的头
    List head = *(list);
    //若为空则说明链表为空
    if (head == NULL)
    {
        printf("链表空\n");
        return true;
    }
    else
    {
        printf("链表不空\n");
        return false;
    }
}

//判断是否已满
//满则返回true,反之则返回false
//对于顺序表来讲满的话就不能添加元素了，因为申请的内存已经确定了，
//但是链表还可以增加，因为可以再申请内存
bool Full(List *list)
{
    Node *test;
    test = (Node *)malloc(sizeof(Node));
    if (test != NULL)
    {
        printf("还可以申请空间，所以链表不满\n");
        free(test);
        return false;
    }
    else
    {
        printf("不可以申请空间，所以链表满了\n");
        return true;
    }
}

//确定元素个数
//返回元素的个数
int Count(List *list)
{
    List head = *list;
    if (head == NULL)
    {
        printf("元素个数为0\n");
        return 0;
    }
    while (head->prev != NULL)
    {
        head = head->prev;
    }
    int count = 0;
    while (head != NULL)
    {
        count++;
        head = head->next;
    }
    printf("元素个数为%d\n", count);
}

//得到第i个元素 成功返回true
//将得到的item返回给 item_to_save
bool At(List *list, int i, Item *item_to_save)
{
    int count = Count(list);
    if (i < 0 || i >= count)
    {
        printf("范围超标\n");
        return false;
    }
    //经过上面的判断，现在的链表肯定不空。
    List head = *(list);
    while (head->prev != NULL)
    {
        head = head->prev;
    }
    int n = i;
    while (i > 0)
    {
        head = head->next;
    }
    printf("第%d个元素为%d\n", n, head->item.value);
    *item_to_save = head->item;
    return true;
}

//返回第一个满足要求的元素的位置，并保存这个元素
//将得到的item返回给 item_to_save    位置返回给location
//若不存在则返回-1
int LocateFirst(List *list, Item *item_to_save, bool (*fun)(Item item))
{
    List head = *list;
    if (head == NULL)
    {
        printf("没有找到。\n");
        return -1;
    }
    while (head->prev != NULL)
    {
        head = head->prev;
    }
    int location = 0;
    while (head != NULL)
    {
        if (fun(head->item))
        {
            *item_to_save = head->item;
            printf("找到了，在第%d个元素\n", location);
            return location;
        }
        head = head->next;
        location++;
    }
    printf("没有找到。\n");
    return -1;
}

//返回最后一个满足要求的元素的位置，并保存这个元素
//将得到的item返回给 item_to_save    位置返回给location
//若不存在则返回-1
int LocateLast(List *list, Item *item_to_save, bool (*fun)(Item item))
{
    List tail = *list;
    if (tail == NULL)
    {
        printf("没有找到。\n");
        return -1;
    }
    while (tail->next != NULL)
    {
        tail = tail->next;
    }
    int location = Count(list) - 1;
    while (tail != NULL)
    {
        if (fun(tail->item))
        {
            *item_to_save = tail->item;
            printf("找到了，在第%d个元素\n", location);
            return location;
        }
        tail = tail->prev;
        location--;
    }
    printf("没有找到。\n");
    return -1;
}

//在第i个位置之前插入新的元素，使其称为新的第i个元素
//成功则返回true
bool Insert(List *list, int location, Item item)
{
    printf("插入到第%d个\n", location);
    if (location < 0 || location > Count(list))
    {
        //printf("插入的范围超限\n");
        location = 0;
    }
    else if (location > Count(list))
    {
        //printf("插入的范围超限\n");
        location = Count(list);
    }
    List head = *list;
    List new = (List)malloc(sizeof(Node));
    if (new == NULL)
    {
        printf("满了,无法插入\n");
        return false;
    }
    new->item = item;
    new->next = NULL;
    new->prev = NULL;
    if (head == NULL)
    {
        //链表本为空  空就是虚无缥缈的，所以找到一个新的元素给它安家
        *list = new;
        printf("插入成功\n");
        return true;
    }
    //链表本来就不空
    while (head->prev != NULL)
    {
        head = head->prev;
    }
    *list = head;
    int i = location;
    List p = head;
    //头插
    if (location == 0)
    {
        new->next = p;
        p->prev = new;
    }
    //尾插
    else if (location = Count(list))
    {
        p = head;
        while (p->next != NULL)
            p = p->next;
        p->next = new;
        new->prev = p;
    }
    //插在中间
    else
    {
        p = head;
        while (i > 0)
        {
            i--;
            p = p->next;
        }
        //插在p前面
        p->prev->next = new;
        new->prev = p->prev;
        new->next = p;
        p->prev = new;
    }
    printf("插入成功\n");
    return true;
}

//删除第i个元素
//成功则返回true
bool Delete(List *list, int location)
{
    if (location < 0 || location >= Count(list))
    {
        printf("删除的范围超限\n");
        return false;
    }
    //经过上面的判断，现在的链表肯定不空。
    List head = *(list);
    while (head->prev != NULL)
    {
        head = head->prev;
    }
    *list = head;
    int n = location;
    while (n > 0)
    {
        head = head->next;
    }
    //删除第一个
    if (head->prev == NULL)
    {
        *list = head->next;
        free(head);
        printf("删除成功\n");
        Count(list);
        return true;
    }
    else
    {
        head->prev->next = head->next;
        free(head);
        printf("删除成功\n");
        Count(list);
        return true;
    }
}

//使用特定的函数遍历顺序表中的每一个元素
void Traverse(List *list, void (*fun)(Item item))
{
    List head = *list;
    if (head == NULL)
    {
        printf("空，无法遍历\n");
        return;
    }
    while (head->prev != NULL)
    {
        head = head->prev;
    }
    while (head != NULL)
    {
        fun(head->item);
        head = head->next;
    }
}

//自定义函数排序
void Sort_DIY(List *list, bool (*fun)(Item cur, Item next))
{
    List head = *list;
    if (head == NULL)
        return;
    while (head->prev != NULL)
        head = head->prev;
    List p = head;
    List l1 = head;
    List l2 = head;
    while (l1 != NULL)
    {
        l2 = head;
        while (l2->next != NULL)
        {
            if (fun(l2->item, l2->next->item))
            {
                Item item = l2->item;
                l2->item = l2->next->item;
                l2->next->item = item;
            }
            l2 = l2->next;
        }
        l1 = l1->next;
    }
}

//合并两个线性表(简单拼接不排序)返回新的list
//成功则返回true
bool Merge(List *list1, List *list2, List *list)
{
    Destroy(list);
    List p = *list;
    List p1 = *list1;
    List p2 = *list2;
    while (p2->next != NULL)
    {
        p2 = p2->next;
    }
    while (p1->prev != NULL)
    {
        p1 = p1->prev;
    }
    p2->next = p1;
    *list = p2;
    return true;
}

//复制线性表
bool Copy(List *list_tobe_copied, List *List_copied_to)
{
    List l1 = *list_tobe_copied;
    List l2 = *List_copied_to;
    for (int i = 0; i <= Count(&l1) - 1; i++)
    {
        Insert(&l2, i, l1->item);
        l1 = l1->next;
    }
    return true;
}

接口使用

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
//main.c
#include "list.c"
#include <time.h>
bool fun1(Item item)
{
    if (item.value == 0)
    {
        return true;
    }
    else
        return false;
}
void fun2(Item item)
{
    printf("ITEM：%d\n", item.value);
}
bool fun3(Item item1, Item item2)
{
    return (item1.value > item2.value);
}
//生成一个随机的链表
List RandomList(int size)
{
    List list;
    Item item;
    Initialize(&list);
    for (int i = 0; i <= size - 1; i++)
    {
        srand((int)time(NULL) * i);
        item.value = rand() % 10000;
        Insert(&list, i, item);
    }
    return list;
}
int main()
{
    List list = RandomList(1000000);
    //List list1 = RandomList(10);
    //List list2 = RandomList(10);
    /*
    Item item_to_save;
    Item item;
    item.value=0;
    Initialize(&list);
    Destroy(&list);
    Empty(&list);
    Full(&list);
    Count(&list);
    At(&list,0,&item_to_save);
    LocateFirst(&list,&item_to_save,(*fun1));
    LocateLast(&list,&item_to_save,(*fun1));
    Insert(&list,0,item);
    Delete(&list,0);
*/
    //Traverse(&list, (*fun2));
    Item item;
    item.value = 0;
    //while(1)
    Insert(&list, 0, item);
    Sort_DIY(&list, (*fun3));
    Traverse(&list, (*fun2));
}
文章作者: 崔文耀
文章链接: http://myblog.cuimouren.cn
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 崔文耀 !
数据结构 线性表
  目录