Zeelam's Blog.

mooc-数据结构与算法-线性表

数据结构 算法
字数统计: 1,327阅读时长: 7 min
2019/04/23 Share

线性表: 由同类型数据元素构成有序序列的线性结构

  • 表中元素个数称为线性表的长度
  • 线性表没有元素时，称为空表
  • 表起始位置称为表头，表结束位置称为表尾

线性表的抽象数据类型描述

  • 类型名称: 线性表（List）
  • 数据对象集: 线性表是n(>=0)个元素构成的有序序列()
  • 操作集：
    • List makeEmpty(): 初始化一个空线性表
    • ElementType findKth(int k, List l): 根据位序K，返回相应元素
    • int find(ElementType x, List l): 在线性表L中查找X的第一次出现位置
    • void insert(ElementType x, int i, List l): 在位序i前插入一个新元素x
    • void delete(int i, List l): 删除指定位序i的元素
    • int length(List l): 返回线性L的长度n

代码实现

数组方式实现

结构：

  • C语言实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define ELEMENT_NOT_FOUND -1
#define DEFAULT_SIZE 20

typedef int Position;
typedef struct LNode *PtrToLNode;

// 数据类型以int为例
struct LNode {
    int Data[DEFAULT_SIZE];
    Position Last;
};
typedef PtrToLNode List;
  • Java实现:
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
package com.zeelam;

/**
 * 使用范型使容器可以存放各种类型
 * @param <E>
 */
public class ArrayList<E> {

    /**
     * 默认容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 找不到元素的返回值
     */
    private static final int ELEMENT_NOT_FOUND = -1;

    /**
     * 元素的数量
     */
    private int size;

    /**
     * 所有的元素
     */
    private E[] elements;

    /**
     * 默认构造函数
     */
    public ArrayList() {
        this(DEFAULT_CAPACITY);
    }

    /**
     * 指定容量大小的构造函数
     * @param capaticy
     */
    public ArrayList(int capaticy) {
        capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capaticy;
        elements = (E[]) new Object[capaticy];
    }

}

操作方法：

  • 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
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
/**
 * 创建数组的线性表
 * @return
 */
List makeEmpty() {
    List l;
    l = (List)malloc(sizeof(struct LNode));
    l->Last = -1;
    return l;
}

/**
 * 查找
 * @param L
 * @param X
 * @return
 */
Position find(List l, int x){
    // 从0开始查起
    Position i = 0;
    // 没有到查到相应的值或者最后一个值都不停止查找
    while(i <= l->Last && l->Data[i] != x){
        i++;
    }
    // 如果超出了线性表的范围，则返回ERROR
    if (i > l->Last){
        return ELEMENT_NOT_FOUND;
    } else {
        return i;
    }
}

/**
 * 在i之前的元素插入
 * @param l
 * @param x
 * @param i
 * @return
 */
bool insert(List l, int x, int i){
    Position j;
    if (l->Last == DEFAULT_SIZE -1) {
        printf("表满");
        return false;
    }

    // DEFAULT_SIZE = n，则最后一个元素为l->Last + 1
    if (i < 1 || i > l->Last + 2) {
        printf("位序不合法");
        return false;
    }

    for (j = l->Last; j >= i - 1 ; j--) {
        l->Data[j + 1] = l->Data[j]; // 把i后面的元素向后移
    }
    l->Data[i - 1] = x;
    l->Last++;
    return true;
}

/**
 * 删除第i-1位元素
 * @param l
 * @param i
 * @return
 */
bool delete(List l, int i){
    Position j;

    if (i < 1 || i> l->Last + 1){
        printf("位序%d不存在元素", i);
        return false;
    }

    for (j = i; j <= L->Last; j++) {
        l->Data[j - 1] = l->Data[j];
    }

    l->Last--;
    return true;
}
  • Java实现:
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
/**
 * 清除所有元素
 */
public void clear() {
    for (int i = 0; i < size; i++) {
        elements[i] = null;
    }
    size = 0;
}

/**
 * 元素的数量
 * @return
 */
public int size() {
    return size;
}

/**
 * 是否为空
 * @return
 */
public boolean isEmpty() {
    return size == 0;
}

/**
 * 是否包含某个元素
 * @param element
 * @return
 */
public boolean contains(E element) {
    return indexOf(element) != ELEMENT_NOT_FOUND;
}

/**
 * 添加元素到尾部
 * @param element
 */
public void add(E element) {
    add(size, element);
}

/**
 * 获取index位置的元素
 * @param index
 * @return
 */
public E get(int index) {
    rangeCheck(index);
    return elements[index];
}

/**
 * 设置index位置的元素
 * @param index
 * @param element
 * @return 原来的元素ֵ
 */
public E set(int index, E element) {
    rangeCheck(index);
    E old = elements[index];
    elements[index] = element;
    return old;
}

/**
 * 在index位置插入一个元素
 * @param index
 * @param element
 */
public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacity(size + 1);
    for (int i = size; i > index; i--) {
        elements[i] = elements[i - 1];
    }
    elements[index] = element;
    size++;
}

/**
 * 删除index位置的元素
 * @param index
 * @return
 */
public E remove(int index) {
    rangeCheck(index);
    E old = elements[index];
    for (int i = index + 1; i < size; i++) {
        elements[i - 1] = elements[i];
    }
    elements[--size] = null;
    return old;
}

/**
 * 查看元素的索引
 * @param element
 * @return
 */
public int indexOf(E element) {
    if (element == null) {
        for (int i = 0; i < size; i++) {
            if (elements[i] == null) return i;
        }
    } else {
        for (int i = 0; i < size; i++) {
            if (element.equals(elements[i])) return i;
        }
    }
    return ELEMENT_NOT_FOUND;
}

/**
 * 保证要有capacity的容量
 * @param capacity
 */
private void ensureCapacity(int capacity) {
    int oldCapacity = elements.length;
    if (oldCapacity >= capacity) return;

    // 新容量为旧容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    E[] newElements = (E[]) new Object[newCapacity];
    for (int i = 0; i < size; i++) {
        newElements[i] = elements[i];
    }
    elements = newElements;

    System.out.println(oldCapacity + "扩容为" + newCapacity);
}

private void outOfBounds(int index) {
    throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}

private void rangeCheck(int index) {
    if (index < 0 || index >= size) {
        outOfBounds(index);
    }
}

private void rangeCheckForAdd(int index) {
    if (index < 0 || index > size) {
        outOfBounds(index);
    }
}

链表方式实现

结构:

c语言实现: 

1
2
3
4
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ELEMENT_NOT_FOUND -1

原文作者：Zeelam

原文链接：http://zeelam.com/2019/04/23/mooc-数据结构与算法-线性表/

发表日期：April 23rd 2019, 5:54:32 pm

更新日期：April 29th 2019, 2:36:50 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

目录
  1. 1. 线性表: 由同类型数据元素构成有序序列的线性结构
  2. 2. 线性表的抽象数据类型描述
  3. 3. 代码实现
    1. 3.1. 数组方式实现
    2. 3.2. 链表方式实现
Total : 9
2019
2018
Spring Cloud Eureka Spring 数据结构 算法 数学 概率论 个人 微积分 机器学习 Spring Boot
Java MOOC笔记 Java/微服务 杂记 机器学习 Java/微服务/服务治理