算法与数据结构系列之[线性表的顺序存储结构]

说到线性表的顺序存储结构，我们平时最常用的数组就是顺序存储结构，即用一段地址连续的存储单元依次存储线性表的数据元素。说的通俗一点，就是需要为数组在内存中开辟连续的存储空间。这样连续的存储结构也是优缺点非常明显的，因为数组元素的存储地址是连续的，所以查询起来就很方便，通过数组元素的下标就可以查询到任意的数组元素，且查询的时间复杂度为O(1),对于大数据量的查询性能优势很明显，这也是随机存取的好处。但是数组元素的插入和删除操作的缺点也就很突出了，每插入和删除一个元素，就需要将从该位置起所有的元素向后或向前移动。在最好的情况下，如果元素要插入到最后一个位置，或者删除最后一个元素，此时的时间复杂度为O(1)。最坏的情况是，如果元素要插入到第一个位置或是删除第一个元素，此时的时间复杂度就是O(n)了，插入到第i个位置的平均时间复杂度也是O(n),可以得出数组的插入和删除操作的时间复杂度就是O(n)，所以对于大数据量的数组频繁的插入和删除操作，这样的性能消耗也是很大的，此时使用链表就比使用数组更合适。

C语言代码 （IDE使用的是CLion,至于IDE的配置，大家可以网上找找，不懂的地方可以关注我的微信公众号：源码复兴号，加我微信联系我）： 1、SqList.c

#define INITSIZE 100 //线性表存储空间的初始分配量 #define OK 1 #define ERROR 0 #define LISTINCREMENT 10 //线性表存储空间的分配增量 #define TRUE 1 #define FALSE 0 #include <stdio.h> #include <stdlib.h> typedef int ElementType; typedef int Status; def struct { ElementType *data; //声明了一个名为data的长度不确定的数组，也叫“动态数组” int length; //记录当前顺序表的长度 int size; //记录顺序表分配的存储容量 }SqList; /** * 初始化顺序表 * @param L * @return */ Status InitList(SqList *L){ L->data = (ElementType *)malloc(INITSIZE* sizeof(ElementType)); //分配存储空间为100 if(!L->data) exit(0); //存储分配失败 L->length = 0; //初始线性表长度为0 L->size = INITSIZE; //初始存储容量 return OK; } /** * 查询第i个位置的元素值，并用e返回 * @param L * @param i * @param e * @return */ Status GetElem(SqList L,int i,ElementType *e){ if(L.length==0 || i<1 || i>L.length) return ERROR; *e=L.data[i-1]; return OK; } /** * 在第I的位置插入元素 * @param L * @param i * @param e * @return */ Status ListInsert(SqList *L,int i,ElementType e){ int k; if(i<1 || i>L->length+1) //当i不在范围内 return ERROR; if(L->length >= L->size){ //当前的存储空间已满时，增加内存分配 L->data =(ElementType *)realloc(L->data,(L->size+LISTINCREMENT)* sizeof(ElementType)); if(!L->data) //存储分配失败 exit(0); L->size += LISTINCREMENT; //增加存储容量 } if(i<=L->length){ for (int k = L->length-1; k >=i-1 ; k--) { L->data[k+1]=L->data[k]; } } L->data[i-1]=e; L->length++; return OK; } /** * 删除线性表中第i个位置的元素 * @param L * @param i * @param e * @return */ Status ListDelete(SqList *L,int i,ElementType *e){ int k; if(L->length == 0) return ERROR; if(i<1 || i>L->length) //i的值不合法 return ERROR; *e=L->data[i-1]; if(i<L->length){ for (int k = i; k < L->length; k++) { L->data[k-1] = L->data[k]; } } L->length--; return OK; } /** * 判断线性表是否为空 * @param list * @return */ Status ListEmpty(SqList list){ if(list.length == 0) return TRUE; return FALSE; } /** * 清空线性表，将线性表L置为一个空表 * @param L * @return */ Status ClearList(SqList *L){ L->length = 0; return OK; } /** * 销毁线性表，释放内存 * @param L * @return */ Status DestroyList(SqList *L){ if(L->data){ free(L->data); L->data = NULL; L->size =0; return TRUE; } return FALSE; } /** * 返回线性表中元素个数 * @param L * @return */ int ListLength(SqList L){ return L.length; } /** * 返回线性表的内存容量 * @param L * @return */ int ListSize(SqList L){ return L.size; } /** * 遍历打印线性表元素 * @param L */ void DisplayList(SqList L){ for (int i = 0; i < L.length; i++) { printf("%d ",L.data[i]); } }

2、SqList.h

#ifndef TEST_SQLIST_H #define TEST_SQLIST_H typedef int ElementType; typedef int Status; #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef struct { ElementType *data; //声明了一个名为data的长度不确定的数组，也叫“动态数组” int length; //记录当前顺序表的长度 int size; //记录顺序表分配的存储容量 }SqList; //初始化线性表 Status InitList(SqList *L); //查询第i个位置的元素 Status GetElem(SqList L,int i,ElementType *e); //添加元素 Status ListInsert(SqList *L,int i,ElementType e); //删除元素 Status ListDelete(SqList *L,int i,ElementType *e); //判断线性表是否为空 Status ListEmpty(SqList list); //清空线性表，将线性表L置为一个空表 Status ClearList(SqList *L); //销毁线性表，释放内存 Status DestroyList(SqList *L); //返回线性表中元素个数 int ListLength(SqList L); //返回线性表的内存容量 int ListSize(SqList L); //遍历打印线性表元素 void DisplayList(SqList L); #endif //TEST_SQLIST_H

3、main.c

#include <stdio.h> #include "src/hello.h" #include "src/data/SqList.h" int main() { //初始化一个具有20个元素的线性表 SqList list; InitList(&list); for (int i = 1; i <=20 ; i++) { list.data[i-1]=i; list.length++; } //遍历线性表 DisplayList(list); printf("\n"); //输出线性表的长度，即线性表元素个数 printf("%d",ListLength(list)); printf("\n"); //线性表是否为空 printf("%d",ListEmpty(list)); printf("\n"); //打印线性表中第三个位置的元素 int num ; int *n =# GetElem(list,3,n); printf("%d",*n); printf("\n"); //给线性表添加一个元素，并重新遍历 ListInsert(&list,5,30); DisplayList(list); printf("\n"); //删除线性表指定位置的元素，并重新遍历,并打印出将要删除的元素 int delete; int *d = &delete; ListDelete(&list,10,d); printf("%d",*d); printf("\n"); DisplayList(list); printf("\n"); //清空线性表 ClearList(&list); DisplayList(list); //此次遍历线性表中已经没有元素 printf("\n"); printf("%d",ListLength(list)); //元素个数为0 printf("\n"); printf("%d",ListSize(list)); //此时给线性表分配的内存容量还为100 printf("\n"); //销毁线性表,并释放内存 int result = DestroyList(&list); DisplayList(list); //此次遍历线性表中已经没有元素 printf("\n"); printf("%d",ListLength(list)); //元素个数为0 printf("\n"); printf("%d",ListSize(list)); //此时给线性表分配的内存容量0 printf("\n"); return 0; }

4、运行结果

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 20 0 3 1 2 3 4 30 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 9 1 2 3 4 30 5 6 7 8 10 11 12 13 14 15 16 17 18 19 20 0 100 0 0

java代码:

public class Array<E>{ private E[] data; private int size; /** * 构造函数，传入数组容量capacity构造array * @param capacity */ public Array(int capacity){ data = (E[]) new Object[capacity]; size = 0; } /** * 无参构造，数组的容量默认为100 */ public Array(){ this(10); } public Array(E[] arr){ data = (E[]) new Object[arr.length]; for (int i = 0; i < arr.length; i++) { data[i] = arr[i]; } } /** * 获取数组的元素个数 * @return */ public int getSize(){ return size; } /** * 获取数组容量 * @return */ public int getCapacity(){ return data.length; } /** * 判断数组是否为空 * @return */ public boolean isEmpty(){ return size == 0; } /** * 向数组指定位置插入元素 * @param index * @param e */ public void add(int index,E e){ if(index<0 || index>size){ throw new IllegalArgumentException("下标越界"); } if(size == data.length){ resize(2*data.length); } for(int i=size-1;i>=index;i--){ data[i+1] = data[i]; } data[index] = e; size++; } /** * 向数组的第一个位置添加元素 * @param e */ public void addFirst(E e){ add(0,e); } /** * 向数组的最后一个位置添加元素 * @param e */ public void addLast(E e){ add(size,e); } /** * 当数组容量已满时自动扩容2倍 * @param newCapacity */ private void resize(int newCapacity) { E[] newData = (E[]) new Object[newCapacity]; for (int i = 0; i <size ; i++) { newData[i] = data[i]; } data = newData; } /** * 向数组中插入元素 * @param e */ public void add(E e){ add(size,e); } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append(String.format("Array: size = %d , capacity = %d\n",size,data.length)); res.append("["); for (int i = 0; i <size ; i++) { res.append(data[i]); if(i != size-1){ res.append(","); } } res.append("]"); return res.toString(); } /** * 查询指定位置的数组元素 * @param index * @return */ public E get(int index){ if(index < 0 || index > size){ throw new IllegalArgumentException("传入的数组索引值不合法"); } return data[index]; } /** * 查询数组的第一个元素 * @return */ public E getFirst(){ return get(0); } /** * 查询数组的最后一个元素 * @return */ public E getLast(){ return get(size-1); } /** * 修改数组指定位置的元素 * @param index * @param e */ public void set(int index,E e){ if(index < 0 || index > size){ throw new IllegalArgumentException("传入的数组索引值不合法"); } data[index] = e; } /** * 查询数组中是否包含某个元素e * @param e * @return */ public boolean contains(E e){ for (int i = 0; i <size; i++) { if(data[i] == e){ return true; } } return false; } /** * 查询并返回某个元素e的下标 * @param e * @return */ public int find(E e){ for (int i = 0; i < size; i++) { if(data[i] == e){ return i; } } return -1; } /** * 删除指定索引值的元素，并返回该元素 * @param index * @return */ public E remove(int index){ if(index<0 || index>size){ throw new IllegalArgumentException("所传入的数组索引值不合法"); } E ret = data[index]; for (int i = index + 1; i <size ; i++) { data[i-1] = data[i]; } data[--size] = null; if(size == data.length/4 && data.length/2 !=0){ resize(data.length/2); } return ret; } /** * 删除数组的第一个元素 * @return */ public E removeFirst(){ return remove(0); } /** * 删除数组的最后一个元素 * @return */ public E removeLast(){ return remove(size-1); } /** * 从数组中删除元素e * @param e */ public boolean removeElement(E e){ int index = find(e); if(index != -1){ remove(index); return true; } return false; } /** * 数组元素交换 * @param i * @param j */ public void swap(int i,int j){ if(i < 0 || i >= size || j < 0 || j >= size) throw new IllegalArgumentException("非法索引"); E temp = data[i]; data[i] = data[j]; data[j] = temp; } }

微信公众号：