顺序表

「爱情、让人受尽委屈。」 2022-06-04 08:12 190阅读 0赞

顺序表，简而言之就是基于顺序存储结构下的线性表。所谓顺序存储结构就是使用一组连续地址的内存单元来存储整张线性表的内容。

顺序表的定义方式常有两种，一种是静态定义，另一种是动态定义和生成。

顺序表静态定义代码如下所示：

//顺序表静态定义
    #define MaxSize 100//顺序表的最大容量
    typedef int ElemType;
    
    ElemType SqList[MaxSize];
    int length;//顺序表的长度

顺序表动态定义和初始化代码如下所示：

//顺序表动态定义
    #define MaxSize 100
    typdef int ElemType;
    typedef struct {
       ElemType *elem;
       int length;//顺序表的实际长度
       int listSize;//顺序表的容量
    }SqList；
    
    /**
      *方法描述：顺序表初始化
      *输入参数：SqList *L
      *返回类型：void
      */
    void initSqList(SqList *L) {
      L->elem = (ElemType *)malloc(MaxSize * sizeof(ElemType));
      if(! L->elem) {
        exit(0);
      }
      L->length = 0;
      L->listSize = MaxSize;
    }

不管是静态定义的顺序表，又还是动态定义的顺序表，它们都具有一些相同的基本操作，例如，向顺序表的具体位置插入一个元素，删除具体位置上的元素，遍历顺序表上的内容。虽说定义方式有些差异，但是基本操作的实现方式思路较为类同。现分别以静态定义和动态定义下的插入操作为例。详细代码如下所示：

/**
     *方法描述：在静态定义的顺序表中的第i个位置插入元素
     *输入参数：ElemType sqlist[],int *len,int i,int iNum
     *返回类型：int 顺序表的长度
     */
    int insertElem(ElemType sqlist[],int *len,int i,int iNum) {
    	int t;
    	if(*len == MaxSize || i<1 || i>*len+1) {
    		printf("This insert is illlegal\n");
    		return *len ;
    	}
    
    	for(t=*len-1;t>=i-1;t--) {
    		sqlist[t+1] = sqlist[t];
    	}
    	sqlist[i-1] = iNum;
    	*len = *len + 1;
    
    	return *len;
    }
    
    /**
     *方法描述：向动态定义的顺序表中的第i个位置插入元素
     *输入参数：SqList *L,int i,ElemType item
     *返回类型：void
     */
    void insertElem(SqList *L,int i,ElemType item) {
    	ElemType *base, *insertPtr,*p;
    
    	if(i<1 || i>L->length+1) {
    		exit(0);
    	}
    
    	if(L->length >= L->listSize) {
    		base = (ElemType *) realloc(L->elem,(L->listSize + 10) * sizeof(ElemType));
    		L->elem = base;
    		L->listSize += 100;
    	}
    
    	insertPtr = &(L->elem[i-1]);
    	for(p=&(L->elem[L->length-1]);p>=insertPtr;p--) {
    		*(p+1) = *p;
    	}
    
    	*insertPtr = item;
    	L->length ++;
    
    }

同一基本操作在不同的顺序表定义方式，细微差异在于动态定义可以追加开辟存储空间，从而不用担忧顺序容量的问题。

顺序表是最简单的一种数据结构，其优点：构造简单，操作方便，并且利用数组名（或者顺序表的首地址）就可以直接对表中的内容进行随机存取，从而存取速度快，系统开销小。但是，它也存在着缺点：有可能浪费存储空间，另外在进行插入和删除基本操作时，需要对插入或删除位置后面的所有元素逐个进行移动，从而导致操作效率较低。因此，顺序表适用于表的长度不经常发生变化的场合。

参考资料：

【1】杨峰 著.妙趣横生的算法（C语言实现）.北京：清华大学出版社，2011