在 C 语言中实现 ArrayList

发表于 更新于

最近在读《妙趣横生的算法(C语言实现)》中关于有序序列的章节，其中有List 相关内容的实现。
我在此基础上实现了 IntList，并且使用面向对象的思想增加了相关对列表操作的接口。下面是其实现及测试代码。

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
#ifndef ARRAY_LIST_H
#define ARRAY_LIST_H
#include <limits.h>
#include <stdlib.h>
#define MaxSize 10

typedef struct
{
  int *elem;
  int length;
  int capacity;
  void (*toString) (void *);
  void (*add)(void*,int data);
  void (*insertAt) (void *, int position, int data);
  void (*deleteAt) (void *, int position);
} IntList;

void printArrayList (void *data);
void insertAt (void *list, int i, int data);
void add(void *list,int data);
void deleteAt (void *list, int i);
void
initIntList (IntList * arrayList)
{
  arrayList->elem = malloc (MaxSize * sizeof (int));
  if (!arrayList->elem)
    {
      exit (0);
    }
  arrayList->length = 0;
  arrayList->capacity = MaxSize;
  arrayList->toString = printArrayList;
  arrayList->insertAt = insertAt;
  arrayList->add = add;
  arrayList->deleteAt = deleteAt;
}

IntList *
obtainIntList ()
{
  IntList *list = (IntList *) malloc (sizeof (IntList));
  initIntList (list);
  return list;
}

void add(void *out,int data){
    IntList *list = (IntList*)out;
    list->insertAt(out,list->length,data);
}

void
insertAt (void *out, int i, int data)
{
  IntList *list = (IntList *) out;
  int *base, *insertPtr, *p;
  if (i < 0 || i > list->length)
    {
      exit (0);
    }
  if (list->length >= list->capacity)
    {
      base = realloc (list->elem, (list->capacity + 10) * sizeof (int));
      list->elem = base;
      list->capacity = list->capacity + 10;
    }
  insertPtr = &(list->elem[i]);
  for (p = &(list->elem[list->length - 1]); p >= insertPtr; p--)
    {
      *(p + 1) = *p;
    }
  *insertPtr = data;
  list->length++;
}

void
deleteAt (void *out, int position)
{
  IntList *list = (IntList *) out;
  int *deleteItem,*q;
  if (position < 0 || position > list->length - 1)
    {
      exit (0);
    }
  deleteItem = &(list->elem[position]);
  q = list->elem + list->length - 1;
  for (deleteItem; deleteItem < q; ++deleteItem)
    {
      *(deleteItem) = *(deleteItem + 1);
    }
  list->length--;
}

void
printArrayList (void *data)
{
  IntList *list = (IntList *) data;
  printf ("[");
  for (int i = 0; i < list->length; i++)
    {
      if (i != list->length - 1)
  {
    printf ("%d,", list->elem[i]);
  }
      else
  {
    printf ("%d", list->elem[i]);
  }

    }
  printf ("]\n");
}

#endif

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>
#include "IntList.h"
int
main ()
{
  IntList *list = obtainIntList ();
  printf ("init an empty int list\n");
  list->toString (list);
  for (int i = 0; i < 5; i++)
    {
      list->insertAt (list, i, i);
    }
  printf ("add 5 item to list\n");
  list->toString (list);
  for (int i = 5; i < 10; i++)
    {
      list->add (list, i);
    }
  printf ("add 5 item to list\n");
  list->toString (list);
  printf ("delete the item at index of 2\n");
  list->deleteAt (list, 2);
  list->toString (list);
  free (list);
  return 0;
}

一下是运行结果：

1
2
3
4
5
6
7
8
init an empty int list
[]
add 5 item to list
[0,1,2,3,4]
add 5 item to list
[0,1,2,3,4,5,6,7,8,9]
delete the item at index of 2
[0,1,3,4,5,6,7,8,9]