数组|链表实现及与栈和队列的关系

Algorithm


数组的特点：随机访问

数组实现-动态数组

结点构造:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define INITSIZE 10 // 数组初始容量
#define E int

/*
// 静态数组节点定义
typedef struct {
    E data[INITSIZE];  // 数组长度为固定长度
    int size;
}Array;
*/

// 动态数组节点定义
typedef struct {
    E * data;      // 动态分配数组的空间基址
    int capacity;  // 数组的最大容量
    int size;      // 数组元素当前所占容量 size:0 表示数组空
                   // 有的教材是int last指向数组最后一个元素的下标  初始时为空：last = -1 两个原理一致
}Array;

初始化及相关操作：

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
// 初始化动态数组
Array * initArray(){
    Array *arr = (Array *) malloc(sizeof(Array));
    arr->data = (E *) malloc(sizeof(E) * INITSIZE);
    arr->capacity = INITSIZE;
    arr->size = 0;
}

// 获取数组的容量   O(1)
int getCapacity(Array * arr){
    return arr->capacity;
}

// 获取数组中的元素个数  O(1)
int getSize(Array * arr){
    return arr->size;
}

// 返回数组是否为空 O(1)
int isEmpty(Array * arr){
    return arr->size;
}

// 打印数组信息
void printMessage(Array * arr){
    printf("Array:size = %d  , capacity = %d \n",arr->size,arr->capacity);
    int i;
    printf("[");
    for (i = 0; i < arr->size; ++i) {
        printf("%d", arr->data[i]);
        if (i != arr->size - 1) {
            printf(", ");
        }
    }
    printf("]\n");
}

插入操作:
在数组头部插入数据需要O(N)，尾部插入数据需要O(1),平均插入数据需要O(N)

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
// 将数组空间的容量扩容成newCapacity大小 O(N)
void resize(Array * arr,int newCapacity){
    E *newDate = (E *) malloc(sizeof(E) * newCapacity); // 此处可以使用realloc
    int i;
    for (i = 0; i < arr->size; ++i) {
        newDate[i] = arr->data[i];
    }
    arr->data = newDate;
    arr->capacity = newCapacity;
}

// 在index索引的位置插入一个新元素e   index∈[0,size]  O(N)
void add(Array * arr,int index, E e){
    if (index < 0 || index > arr->size) { // index位置不合法
        printf("Add failed. Require index [0,size].");
        return;
    }
    if (arr->size == arr->capacity){ // 数组满 动态增长数组
        resize(arr, 2 * arr->capacity);
    }
    int i;
    for (i = arr->size-1; i >=index ; --i) {
        arr->data[i + 1] = arr->data[i];
    }
    arr->data[index] = e;
    arr->size++;
}

// 向所有元素后添加一个新元素   O(1)
void addLast(Array * arr,E e){
    add(arr, arr->size, e);
}

// 在所有元素前添加一个新元素   O(N)
void addFirst(Array * arr,E e){
    add(arr, 0, e);
}

删除操作:
在数组头删除元素需要O(N)，数组尾删除元素O(1),平均删除元素需要O(N)

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
// 从数组中删除index位置的元素, 返回删除的元素   O(N)
E Remove(Array * arr,int index){
    if (index < 0 || index >= arr->size) { // index ∈[0,size)
        printf("Remove failed. Index ∈ [0,size).");
        return -9999999;
    }
    E res = arr->data[index];
    int i;
    for (i = index + 1; i < arr->size; ++i) {
        arr->data[i-1] = arr->data[i];
    }
    arr->size--;
    // 动态缩减数组 更好的写法：arr->size == arr->capacity / 4 && arr->capacity / 2 !=0
    if (arr->size == arr->capacity / 2) {
        resize(arr, arr->capacity / 2);
    }
    return res;
}

// 从数组中删除第一个元素, 返回删除的元素   O(N)
E removeFirst(Array * arr){
    return Remove(arr, 0);
}

// 从数组中删除最后一个元素, 返回删除的元素  O(1)
E removeLast(Array * arr){
    return Remove(arr, arr->size - 1);
}

// 从数组中删除元素e   O(N)
void removeElement(Array * arr,E e){
    int index = find(arr, e);
    if (index != -1) {
        Remove(arr, index);
    }
}

修改操作:
已知索引O(1),未知索引是O(N)

1
2
3
4
5
6
7
8
// 修改index索引位置的元素为e O(1)
void set(Array * arr,int index, E e){
    if (index < 0 || index > arr->size) { // index∈[0,size)
        printf("Set failed. Index ∈ [0,size).");
        return;
    }
    arr->data[index] = e;
}

查找操作:
已知索引O(1),未知索引是O(N)

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
// 获取index索引位置的元素 O(1)
E get(Array * arr,int index){
    if (index < 0 || index >= arr->size) {
        printf("Get failed. Index ∈ [0,size).");
        return -9999999;
    }
    return arr->data[index];
}

// 查找数组中是否有元素e  O(N)
int contains(Array * arr,E e){
    int i;
    for (i = 0; i < arr->size; ++i) {
        if (arr->data[i] == e) {
            return 1;
        }
    }
    return 0;
}

// 查找数组中元素e所在的索引，如果不存在元素e，则返回-1  O(N)
int find(Array * arr,E e){
    int i;
    for (i = 0; i < arr->size; ++i) {
        if (arr->data[i] == e) {
            return i;
        }
    }
    return -1;
}

链表实现

节点定义：

1
2
3
4
5
6
#define E int

typedef struct Node{
    E data;                       // 数据域
    struct Node * next;           // 指针域
}LinkNode;

初始化及相关操作：

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
// 初始化链表
LinkNode * initLink(){
    LinkNode *dummyHead = (LinkNode *) malloc(sizeof(LinkNode)); // 创建虚拟头节点
    dummyHead->next = NULL;
    return dummyHead;
}

// 获取链表中的元素个数  O(N)  可以通过加入size成员 来使复杂度降为O(1) 虽然需要维护size 见java版
int getSize(LinkNode * dummyHead){
    LinkNode *curNode = dummyHead->next;
    int size = 0, i;
    while (curNode != NULL) {
        size++;
        curNode = curNode->next;
    }
    return size;
}

// 返回链表是否为空
int isEmpty(LinkNode * dummyHead){
    return NULL == dummyHead->next;
}

// 打印信息
void printMessage(LinkNode *dummyHead){
    if (isEmpty(dummyHead)){
        printf("printMessage failed. LinkedList is empty.\n");
        return;
    }
    int i;
    printf("LinkedList : ");
    LinkNode * curNode = dummyHead->next;
    while (curNode != NULL) {
        printf("%d -> ", curNode->data);
        curNode = curNode->next;
    }
    printf("NULL\n");
}

插入操作:
在链表头部插入数据需要O(1)，尾部插入数据需要O(N),平均插入数据需要O(N)

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
// 在链表的索引为index位置添加新的元素e  index从0开始  O(N)
// dummyHead -> 1 -> 2 -> 3
// index        0    1    2    则index可以使在索引为0,1,2,3的位置插入 即index ∈ [0,getSize()]
void add(LinkNode * dummyHead,int index, E e){
    if (index < 0 || index > getSize(dummyHead)) {
        printf("Add failed. index index ∈ [0,getSize()]\n");
        return;
    }
    LinkNode *pre = dummyHead;
    int i;
    for (i = 0; i < index; ++i) {
        pre = pre->next;
    }
    LinkNode *newNode = (LinkNode *) malloc(sizeof(LinkNode));
    newNode->data = e;
    newNode->next = pre->next;
    pre->next = newNode;
}


// 在链表头添加新的元素e   O(1)
void addFirst(LinkNode * dummyHead,E e){
    add(dummyHead, 0, e);
}

// 在链表末尾添加新的元素e  O(N)
void addLast(LinkNode * dummyHead,E e){
    add(dummyHead, getSize(dummyHead), e);
}

删除操作:
在链表头删除元素需要O(1)，链表尾删除元素O(N),平均删除元素需要O(N)

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
// 从链表中删除index ∈ [0,getSize()-1]位置的元素, 返回删除的元素  O(N)
E Remove(LinkNode * dummyHead,int index){
    if (index < 0 || index >= getSize(dummyHead)){
        printf("remove failed. index ∈ [0,getSize()-1].\n");
        return -9999999;
    }
    LinkNode *pre = dummyHead;
    int i;
    for (i = 0; i < index; ++i) {
        pre = pre->next;
    }
    LinkNode *delNode = pre->next;
    E res = delNode->data;
    pre->next = delNode->next;
    free(delNode);
    delNode = NULL;
    return res;
}

// 从链表中删除第一个元素, 返回删除的元素  O(1)
E removeFirst(LinkNode * dummyHead){
    return Remove(dummyHead, 0);
}

// 从链表中删除最后一个元素, 返回删除的元素  O(N)
E removeLast(LinkNode * dummyHead){
    return Remove(dummyHead, getSize(dummyHead) - 1);
}

// 从链表中删除元素e  O(N)
void removeElement(LinkNode * dummyHead,E e){
    LinkNode *pre = dummyHead;
    while (pre->next != NULL) {
        if (pre->next->data == e){
            LinkNode *delNode = pre->next;
            pre->next = delNode->next;
            free(delNode);
            delNode = NULL;
            return;
        }
        pre = pre->next;
    }
}

修改操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
// 修改链表的第index ∈ [0,getSize()-1]个位置的元素为e  O(N)
void set(LinkNode *dummyHead, int index, E e){
    if (index < 0 || index >= getSize(dummyHead)) {
        printf("set failed. index index ∈ [0,getSize()-1]\n");
        return;
    }
    LinkNode *curNode = dummyHead->next;
    int i;
    for (i = 0; i < index; ++i) {
        curNode = curNode->next;
    }
    curNode->data = e;
}

查找操作：

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
// 获得链表的第index ∈ [0,getSize()-1]个位置的元素  O(N)
E get(LinkNode * dummyHead,int index){
    if (index < 0 || index >= getSize(dummyHead)) {
        printf("get failed. index index ∈ [0,getSize()-1]\n");
        return -9999999;
    }
    LinkNode *curNode = dummyHead->next;
    int i;
    for (i = 0; i < index; ++i) {
        curNode = curNode->next;
    }
    return curNode->data;
}

// 获得链表的第一个元素  O(1)
E getFirst(LinkNode *dummyHead) {
    return get(dummyHead, 0);
}

// 获得链表的最后一个元素  O(N)
E getLast(LinkNode *dummyHead){
    return get(dummyHead, getSize(dummyHead) - 1);
}

// 查找链表中是否有元素e O(N)
int contains(LinkNode * dummyHead, E e){
    LinkNode *curNode = dummyHead->next;
    while (curNode != NULL) {
        if (curNode->data == e) {
            return 1;
        }
        curNode = curNode->next;
    }
    return 0;
}

总结

数组：

基于数组实现的栈和队列都是 数组操作的子集

  • 栈(数组)：addLast() 入栈 O(1); removeLast() 出栈 O(1); get(index:size-1)读栈顶元素O(1)
  • 队列(数组)： addLast() 入队 O(1); removeFirst() 出队 o(N) ; get(index:0) 读队头元素 O(1)；get(index:size-1) 度队尾元素O(1)因为出队是O(N) 于是加入队尾指针并进行对应的改变 使出队变成O(1)

链表：

基于链表实现的栈和队列都是 链表操作的子集

  • 栈(链表)：addFirst()入栈 removeFirst()出栈 getFirst()取栈顶元素 都是O(1)
  • 队列(链表)：removeFirst()出队 addLast()入队 getFirst()队头元素 队列出队，取队头O(1),入队需要O(N) 但是如果在头指针的基础上设尾指针 降为O(1)

pS: C源代码链接
pS: java源代码链接

本文标题:数组|链表实现及与栈和队列的关系

文章作者:XerDemo

发布时间:2019-02-01, 23:49:43

最后更新:2019-02-06, 16:17:13

原始链接:https://xerdemo.github.io/2019/02/01/数组链表形成栈和队列详解/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 数组实现-动态数组
  2. 2. 链表实现
  3. 3. 总结
|