数据结构与算法(一)顺序表和单链表的比较

Posted on | In

线性查找法

  • 线性查找又称顺序查。基本思路是从第一个记录开始，
  • 逐个比较记录的关键字，直到和给定的K值相等，则查找成功；
  • 若比较结果与文件中n个记录的关键字都不等，则查找失败。
  • 时间复杂度：O(N)

二分查找法

  • 二分查找法又叫折半查找法。比如小时候玩的猜数字游戏

  • 胖虎说：大熊你猜猜我现在心中想的数字是什么。给你一个范围1-100之间，不限次数猜，猜不中就打你一次，看你需要被我打多少次才可以猜出来（心中想的是25）。

  • 大熊想：…. 心中犯嘀咕。这不是明摆着欺负我。不行我得拿出吃奶的力气快速想出来。减少挨打的份 大熊随口说两个50

  • 胖虎说：不对。随即甩手就是一嘴巴。 并说太高了

  • 大熊：…. 真TM难。思考一番。那我就在减半 随口说是数字：25 这次就猜对了

类似这种折半猜数字的方法就是二分法查找。

基本思路

  • 首先设置一个左标记为0和一个右标标记为当前数组长度，

  • 第二步 让当前待查元素与表中间元素进行匹配，如果一致则直接返回中间索引，

  • 第三步 如果小于中间索引则让右标记等于当前中间索引，

  • 第四步 如果大于中间索引，则让左标示等于当前中间索引

    二分法查找比线性查找才查询次数上会大大减少。所以效率也就高了。就是要待查询的表为有序表，并且只对查询效率有所优化，
    当修改和插入数据的时候这种效率就很低了。

代码示范

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
public class 二分法查找 {
	public static void main(String[] args) {
		 int[] number = {1,2,3,4,5,6,7,8,9,10};
	     int key = 10;
	     int result =halfSort(number, key);
	     System.out.println("查找出的下标："+result);
	}
	public static int halfSort(int[] data,int key){
	     int min,mid,max;
	     max=data.length;
	     min=1;
	    while (min<=max){
		mid=(min+max)/2;  //折半
		if(key<data[mid]){ //如查找值比中值小
		   max=mid-1;	//最高下标调证到中值下标的小一位
		}else if(key>data[mid]){
		   min=mid+1;
		}else{
		  return  mid;
	        }
	     }
		return  0;
	  }
}

  // 二分查找递归实现   
    public static int binSearch(int srcArray[], int start, int end, int key) {   
        int mid = (end - start) / 2 + start;   
        if (srcArray[mid] == key) {   
            return mid;   
        }   
        if (start >= end) {   
            return -1;   
        } else if (key > srcArray[mid]) {   
            return binSearch(srcArray, mid + 1, end, key);   
        } else if (key < srcArray[mid]) {   
            return binSearch(srcArray, start, mid - 1, key);   
        }   
        return 0;   
    }

线性表

0个或多个数据元素的有限序列。 首先它是一个序列。也就是说，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继 。

线性表的顺序存储结构

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

顺序存储结构

插入算法思路:

  • 如果插入位置不合理，抛出异常;
  • 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量;
  • 从最后一个元素开始向前遍历到第 i 个位置，分别将它们都向后移动一个位置;
  • 将要插入元素填入位置 i 处，表长加 1 。

输入图片说明

删除算法的思路:

  • 如果删除位置不合理，抛出异常 i
  • 取出删除元素;
  • 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动 一
    个位置;
  • 表长减 1 。

输入图片说明

代码实现 

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
public interface MyList<E> {
	 int size();
	 boolean contains(Object o);
	 void add(int i,E e)throws Exception;
	 void add(E e)throws Exception;
	 void remove(int i)throws Exception ;
	 String toArray();
}


public class MyArrayList<E> implements MyList<E> {
	
	//数组作为线性表的存储空间
	private  Object[] elementData;

	//线性表的当前长度
	private int size;

	public MyArrayList(int initialCapacity) {
		//初始化数据大小
		this.elementData=new Object[initialCapacity];
		
		this.size=0;
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public boolean contains(Object o) {
	     if (o == null){
	            for (int i = 0; i < size; i++)
	                if (elementData[i]==null)
	                    return true;
	        }else{
	            for (int i = 0; i < size; i++)
	                if (o.equals(elementData[i])){
	                	return true;
	                }   
	    }
		return false;
	}

	@Override
	public void add(int i, E e) throws Exception{
		if(size==elementData.length){
			  throw new Exception("存储空间已满");
		}
		if(i<0 || i>size){
			  throw new Exception("添加参数下标越界");
		}
	    for (int j = size; j > i; j--){
	    	// 插入位置及之后的元素后移(下标加1)  比如 123  插入元素4 到的2的位置
			 elementData[j] = elementData[j - 1]; ;
			 System.out.println("移动："+toArray());
		 }

	 	 elementData[i] = e; //插入
	     ++size; //长度增加
		 System.out.println("移动："+toArray());
	}

	/**
	 * 插入算法的思路;
	, 如果插入位置不合理，抛出异常;
	• 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量;
	• 从最后一个元素开始向前遍历到第 i 个位置，分别将它们都向后移动一个位
	置;
	• 将要插入元素填入位置 i 处;
	• 表长加 1 。
	 */
	@Override
	public void add(E e)throws Exception {
		if(size==elementData.length){
			throw new Exception("存储空间已满");
		}
		  elementData[size++] =e;

	}
	
	/**
	 * 	 删除算法的思路:
		• 如果删除位置不合理，抛出异常 i
		• 取出删除元素;
		• 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动 一
		个位置;
		• 表长减 1 。
	 */
	@Override
	public void remove(int i)throws Exception {
		if (i < 0 || i > size - 1){
			 throw new Exception("删除位置不合法");
		}
		for (int j = i; j < size - 1; j++)  {
			  elementData[j] = elementData[j + 1];// 被删除元素之后的元素左移  
		 }
		  size--; // 表长度减1  
	}
	@Override
	public String toArray() {
		StringBuilder str=new StringBuilder();
		str.append("toArray:[");
		for (int i = 0; i <size; i++) {
			str.append(elementData[i]+",");
		}
		str.append("]");
		return str.toString();
	}

	
	public static void main(String[] args) {
		MyList<Integer> list=new MyArrayList<>(10);
		try {
			list.add(1);
			list.add(2);
			list.add(3);
			System.out.println(list.size());
			System.out.println(list.toArray());
//			list.remove(0);
//			System.out.println(list.size());
//			System.out.println(list.toArray());
			list.add(1, 4);
			System.out.println(list.toArray());
		} catch (Exception e) {
			e.printStackTrace();
		}
	}


}

链式存储结构

  • 链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，
    这组存储单元可以是连续的，也可以是不连续的。
  • 除了存储其本身的信息之外，还需存储一个指示其直接后继的信息指针
  • 链式存储结构是基于指针实现的。我们把一个数据元素和一个指针称为结点。
1
2
数据域：存数数据元素信息的域。
指针域：存储直接后继位置的域。
  1. 单链表
  • 单链表是以指针作为连接，各个节点都由next指针指向下一个节点的地址，将各个节点相互连接起来形成一个单向链表
  • 单链表分为有头结点和非头结点两种。一般都是有头结点的
  • 头结点即在链表的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。

单链表

带头结点的单链表的插入操

输入图片说明

  • 采用带头结点的单链表结构，插入时。不管是在中间插入还是头部插入元素。操作方式都是统一的，改变的是插入元素位置上一个节点的next指针区域的指向。以及插入元素next指针区域的指向
  • 头结点即在链表的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。

输入图片说明

代码实现 

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
public class Node {
	Object element; // 数据域
	Node next; // 指针域

	// 头结点的构造方法
	public Node(Node nextval) {
		this.next = nextval;
	}

	// 非头结点的构造方法
	public Node(Object obj, Node nextval) {
		this.element = obj;
		this.next = nextval;
	}

	// 获得当前结点的指针域
	public Node getNext() {
		return this.next;
	}

	// 获得当前结点数据域的值
	public Object getElement() {
		return this.element;
	}

	// 设置当前结点的指针域
	public void setNext(Node nextval) {
		this.next = nextval;
	}

	// 设置当前结点数据域的值
	public void setElement(Object obj) {
		this.element = obj;
	}

	public String toString() {
		return this.element.toString();
	}
}

public class MyLinkList {
	Node head; // 头指针
	Node current;// 当前结点对象
	int size;// 结点个数

	public MyLinkList() {
		// 初始化头结点，让头指针指向头结点。并且让当前结点对象等于头结点。
		this.head = current = new Node(null);
		this.size = 0;// 单向链表，初始长度为零。
	}

	//使用当前结点对象 定位到要操作结点的前一个结点。
	public void index(int index) throws Exception {
		if (index < -1 || index > size - 1) {
			throw new Exception("参数错误！");
		}
		// 说明在头结点之后操作。
		if (index == -1){
			// 第一个数据元素结点的下标是0，那么头结点的下标自然就是-1
			return;
		}
		current = head.next;
		int temp=0;	 	//临时变量 用户循坏判断当前节点是否到达
		while (current!=null && temp<index){
				//循环找到插入节点的前一个节点
				current=current.next;
				temp++;
		}
	}


	/**
	 * 删除思路：
	 *
	 * 1。定位到当前要删除的下标的对像的前一个节点
	 * 2. 通过改变当前删除对象前一个节点的指针域。》指向当前要删除对象的指针域指向的下一个节点。
	 * @param index
	 * @throws Exception
	 */
	public void delete(int index) throws Exception {
		// 判断链表是否为空
		if (isEmpty()) {
			throw new Exception("链表为空，无法删除！");
		}
		if (index < 0 || index > size) {
			throw new Exception("参数错误！");
		}
		index(index - 1);// 定位到要操作结点的前一个结点对象。
		current.setNext(current.next.next);
		size--;
	}

	/**
	 * 获取思路：
	 * 		从头节点开始遍历。用临时变量temp记录遍历的次数。一直遍历等于index就不会再行循坏，直接取出当前下标的节点
	 * @param index
	 * @return
	 * @throws Exception
	 */
	public Object get(int index) throws Exception {
		if (index < -1 || index > size - 1) {
			throw new Exception("参数非法！");
		}
		current = head.next;
		int temp=0;	 	//临时变量 用户循坏判断当前节点是否到达
		while (current!=null && temp<index){
			//循环找到插入节点的前一个节点
			current=current.next;
			temp++;
		}
		return current.getElement();
	}

	/**
	 * 指定位置插入节点
	 * @param index
	 * @param obj
	 * @throws Exception
	 */
	public void save(int index, Object obj) throws Exception {
		if (index < 0 || index > size) {
			throw new Exception("参数错误！");
		}
		index(index-1);//定位到要操作结点的前一个结点对象。
		current.setNext(new Node(obj,current.next));
		size++;

	}

	/**
	 * 未指定下标末尾插入
	 * @param obj
	 * @throws Exception
	 */
	public void save(Object obj) throws Exception {
		/**
		 * 1.判断当前节点指向一下节点的指针域是否为空
		 * 如果指针域为空 说明是此节点是末尾节点
		 * 直接在尾部修改默认节点的指针域执指向新增的节点，并把新增的节点的指针域指向null
		 */
		while (current.next!=null){
			//循环判断当前节点指针域是否有下一个节点
			current=current.next;
		}
		current.setNext(new Node(obj, current.next));
		size++;
	}

	public boolean isEmpty() {
		return size == 0;
	}

	public int size() {
		return this.size;
	}

	public static void main(String[] args) throws  Exception {
		MyLinkList list=new MyLinkList();
//		list.save(1);
		list.save(0,0);
		list.save(1,111);
		list.save(2,222);
		System.out.println("删除之前：");
		for (int i = 0; i < list.size; i++) {
			System.out.print(list.get(i) + " ");
		}
		System.out.println();
		list.delete(1);
		System.out.println("删除之后：");
		for (int i = 0; i < list.size; i++) {
			System.out.print(list.get(i) + " ");
		}
	}

}

顺序表和单链表的比较

顺序表：

  • 优点：在存, 读数据时, 不管是哪个位置，时间复杂度都是 0(1) ;
    *缺点：插入或删除时，时间复杂度都是 O(n)。需要运动大量元素当线性表长度变化较大时，难以确定存储空间的容量会产生存储空间“碎片”

    单链表：

  • 优点：主要优点是不需要预先给出数据元素的最大个数。另外，单链表插入和删除操作时不需要移动数据元素；

  • 缺点：主要缺点是每个结点中要有一个指针，因此单链表的空间利用率略低于顺序表的。另外，单链表不支持随机读取，单链表取数据元素操作的时间复杂度为O（n）；而顺序表支持随机读取，顺序表取数据元素操作的时间复杂度为O（1）。

觉得本文不错的话，分享一下给小伙伴吧~