首页 > Java > java教程 > 详细解析线性表的原理及简单实现方法

详细解析线性表的原理及简单实现方法

ringa_lee
发布: 2017-10-15 10:43:57
原创
3127 人浏览过

下面小编就为大家带来一篇浅谈线性表的原理及简单实现方法。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧

一、线性表

原理:零个或多个同类数据元素的有限序列

原理图:

特点 :

1、有序性

2、有限性

3、同类型元素

4、第一个元素无前驱,最后一个元素无后继,中间的元素有一个前驱并且有一个后继

线性表是一种逻辑上的数据结构,在物理上一般有两种实现 顺序实现和链表实现

二、基于数组的 线性表顺序实现

原理 : 用一段地址连续的存储单元依次存储线性表数据元素。

原理图:

算法原理:

1、初始化一个定长的数组空间 elementData[] , size 存储长度 存储元素

2、通过索引来快速存取元素

3、通过数组复制实现元素的插入和删除

总结:

1、无需为表示表中元素之间的逻辑关系增加额外的存储空间

2、可以快速存取表中任一位置元素

3、插入和删除需要进行数组复制(即大量元素的移动)

4、线性表长度变化较大时,需要频繁扩容,并造成存储空间碎片

实现代码:

接口定义:


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

package online.jfree.base;

 

/**

 * author : Guo LiXiao

 * date : 2017-6-14 11:46

 */

 

public interface LineList <E>{

 

 /**

  * lineList 是否为空

  * @return

  */

 boolean isEmpty();

 

 /**

  * 清空 lineList

  */

 void clear();

 

 /**

  * 获取指定位置元素

  * @param index

  * @return

  */

 E get(int index);

 

 /**

  * 获取元素第一次出现的位置

  * @param e

  * @return

  */

 int indexOf(E e);

 

 /**

  * 判断 lineList是否包含指定元素

  * @param e

  * @return

  */

 boolean contains(E e);

 

 /**

  * 设置指定位置数据,如数据已存在 则覆盖原数据

  * @param index

  * @param e

  * @return

  */

 E set(int index, E e);

 

 /**

  * 移除指定位置元素

  * @param index

  * @return

  */

 E remove(int index);

 

 /**

  * 在lineList结尾插入元素

  * @param e

  * @return

  */

 E add(E e);

 

 /**

  * 在index后面插入元素

  * @param index

  * @param e

  * @return

  */

 E add(int index, E e);

 

 /**

  * 返回lineList长度

  * @return

  */

 int size();

 

 

 

}

登录后复制

算法实现:


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

package online.jfree.base;

 

/**

 * author : Guo LiXiao

 * date : 2017-6-15 13:44

 */

 

public class OrderedLineList<E> implements LineList<E> {

 

 private static final int INIT_CAPACITY = 10;

 

 private transient E[] elementData;

 

 private transient int elementLength;

 

 private int size;

 

 public OrderedLineList() {

  this(0);

 }

 

 public OrderedLineList(int initCapacity) {

  init(initCapacity);

 }

 

 private void init(int initCapacity) {

  if (initCapacity >= 0) {

   this.elementData = (E[]) new Object[initCapacity];

   this.elementLength = initCapacity;

  } else {

   throw new IllegalArgumentException("Illegal Capacity: " +

     initCapacity);

  }

  this.size = 0;

 }

 

 /**

  * 扩容

  */

 private void dilatation() {

  int oldCapacity = this.elementLength;

  int newCapacity = oldCapacity;

  if (oldCapacity <= this.size) {

   newCapacity = oldCapacity + INIT_CAPACITY;

  }else if(oldCapacity - INIT_CAPACITY > this.size){

   newCapacity = oldCapacity - INIT_CAPACITY;

  }

  if (oldCapacity != newCapacity){

   E[] newElementData = (E[]) new Object[newCapacity];

   System.arraycopy(elementData, 0, newElementData, 0, oldCapacity);

   this.elementLength = newCapacity;

   this.elementData = newElementData;

  }

 }

 

 /**

  * 校验列表索引越界

  * @param index

  */

 private void checkCapacity(int index){

  if (index > this.size - 1 || index < 0)

   throw new IndexOutOfBoundsException(new StringBuffer("[index : ").append(index).append("] , [size : ").append(size).append("] ").toString());

 }

 

 @Override

 public boolean isEmpty() {

  return this.size == 0;

 }

 

 @Override

 public void clear() {

  this.init(0);

 }

 

 @Override

 public E get(int index) {

  this.checkCapacity(index);

  return this.elementData[index];

 }

 

 @Override

 public int indexOf(E e) {

  for (int i = 0; i < this.size; i++){

   if (e == null && elementData[i] == null || e.equals(elementData[i])){

    return i;

   }

  }

  return -1;

 }

 

 @Override

 public boolean contains(E e) {

  return this.indexOf(e) > 0;

 }

 

 @Override

 public E set(int index, E e) {

  this.checkCapacity(index);

  this.dilatation();

  E oldElement = this.elementData[index];

  this.elementData[index] = e;

  return oldElement;

 }

 

 @Override

 public E remove(int index) {

  this.dilatation();

  E e = elementData[index];

  if (index == size - 1) elementData[index] = null;

  else {

   int length = size - index - 1;

   System.arraycopy(elementData, index + 1, elementData, index, length);

  }

  size --;

  return e;

 }

 

 @Override

 public E add(E e) {

  return this.add(size, e);

 }

 

 @Override

 public E add(int index, E e) {

  this.dilatation();

  if (index == size) elementData[index] = e;

  else {

   index++;

   int lastLength = size - index;

   E[] lastElementData = (E[]) new Object[lastLength];

   System.arraycopy(elementData, index, lastElementData, 0, lastLength);

   elementData[index] = e;

   System.arraycopy(lastElementData, 0, elementData, index + 1, lastLength);

  }

  size ++ ;

  return e;

 }

 

 @Override

 public int size() {

  return this.size;

 }

 

}

登录后复制

以上是详细解析线性表的原理及简单实现方法的详细内容。更多信息请关注PHP中文网其他相关文章!

相关标签:
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板