顺序链表的定义及操作

顺序链表

---

• 定义:

顺序链表 的本质是一个数组, 但和数组不一样.
它额外增添了一个属性—长度, 用来记录存储数据的个数.

所以将 长度 和 数组 封装在一起就形成了新的数据结构—顺序链表

	typedef struct{
	    ElemType data[MAXSIZE];
	    int length; 
	}SqList;
1
2
3
4

• 获取元素

顺序链表, 获取数据的方式较简单, 只需要根据位置, 直接索引即可, 然后通过传入e的地址来接收数据

代码如下: 时间复杂度为O(1)

Status GetElem(SqList L, int i, ElemType *e){
   if(L.length == 0 || i < 1 || i > L.length ) 
   //先判断给定位置的正确性, 和检验链表是否为空
   {
       return ERROR;
   }
   *e = L.data[i-1];  //与数组下标相对, 获取第i个元素

  return OK;
} 
1
2
3
4
5
6
7
8
9
10

• 插入元素

顺序存储结构的插入元素比较复杂, 因为每个元素都是紧挨着, 且连续的, 要想插入一个元素, 必须先移动其他元素, 将要插入的位置空出来了,才能插入.

代码如下: 时间复杂度为O(n)

Status ListInsert(SqList *L, int i, ElemType e){
   int k;
//先判断
   if (L->length == MAXSIZE) //链式表已经满了
   {
       return ERROR;
   }
   if (i < 1 || i > L->length + 1) 
   //如果i > length+1 中间就会空一个位置, 不再连续了 
   {
       return ERROR;  //抛出异常
   }
   if (i <= L->length) 
   //若插入数据位置不在表尾, 就要移动其他数据
   {
       //将要插入的位置和后面的元素, 向后移动一位
       for( k = L->length-1; k >= i-1; k--)
       //length-1为表的最后一个元素, i-1为该放入的位置
       {
           L->data[k+1] = L->data[k]; 
       //将原来的元素都往后移动一位, 直到移动完至i-1, 就空出了i-1那个位置
       }
   }

   //将数据插入空出的那个位置
   L->data[i-1] = e;
   L->length++; //插入了一个新元素后记得 长度加一

   return OK;
   }
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

• 删除元素

和插入元素差不多, 删除一个元素后, 需要其后面的元素都往前移动一位, 把位置补上, 这样才能保持连续, 对于删除操作,直接移位覆盖就好了, 同时返回删除的数据

代码如下: 时间复杂度为O(n)

		Status ListDelete(SqList *L, int i, ElemType *e){
	    int k;
	
	    if (L->length == 0){
	        return ERROR;
	    }
	    if (i < 1 || i > length){
	        return ERROR;
	    }
	
	    *e = L->data[i-1]; //把删除的值给e;
	
	    if (i < L->length){ // 如果不是最后一个, 就要移动
	        for(k = i-1; k < length-1; k++){ 
	        //这次是从前面开始移动的, 如果从后面开始就覆盖了
	            L->data[k] = L->data[k+1];
	        }  //直到最后一个元素移到length-2的位置就结束了
	    }
	
	    L->length--;
	
	    return OK;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---

总结

顺序存储结构的优势在于: 获取数据非常方便, 直接索引下标即可. 但是对于插入, 和删除操作却比较复杂, 而且长度是相对有限的, 因此顺序存储结构适合存储已知一定大小的数据, 并且增删数据较少, 查找数据较多的情况.