数据结构系列－线性表的顺序存储及基本操作

怼烎@ 2022-05-30 11:05 201阅读 0赞

程序设计就是对一个确定的问题，选择一个合适的结构来表示，然后通过好的算法去实现，所以说数据结构、算法是很重要的基础。

顺序存储的线性表，在查找指定位置元素时非常快，时间复杂度是O(1)，但是删除、插入元素时可能要移动元素导致效率变慢，时间复杂度可能是O(n)，还有一个问题就是存储空间容量要事先确定的。

针对顺序存储的不足，有了链式存储。

线性表就是零个或多个数据元素的有限序列。

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

sequential\_storage\_list.c

#include "stdio.h"
    #include "stdlib.h"
    #include "io.h"
    #include "math.h"
    #include "time.h"
    
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    
    #define MAXSIZE 20 //存储空间初始容量
    
    typedef int Status; //status表示函数返回的结果状态码
    typedef int ElemType; //数据的类型
    
    typedef struct{
    	ElemType data[MAXSIZE];	
    	int length;
    }SqList;

如果在linux下出现io.h找不到，可以找这个目录有没有./usr/include/x86\_64-linux-gnu/sys/io.h，然后将其cp到./usr/include/。

线性表的基本操作，获取元素，插入元素，删除元素等。

为了测试要先初始化一个线性表

//访问一个元素
    Status visit(ElemType et){
    	printf("%d",et);
    	return OK;
    }
    
    //初始化线性表
    Status InitList(SqList *L){
    	L->length =0;
    	return OK;
    }
    
    //判断线性表是否为null，
    Status ListEmpty(SqList L){
    	if(L.length ==0){
    		return TRUE;	
    	}else{
    		return FALSE;
    	}
    }
    
    
    //清空线性表
    Status ClearList(SqList *L){
    	L->length =0;
    	return OK;
    }
    
    //返回线性表元素的个数
    int ListLength(SqList L){
    	return L.length;
    }
    
    //获取指定位置的元素，
    Status GetElem(SqList L,int i, ElemType *e){
    	if(L.length == 0 || i<0 || i>L.length-1)
    		return ERROR;
    	*e =L.data[i];
    
    	return OK;
    }
    
    //返回执行元素在列表中的位置,
    int LocateElem(SqList L, ElemType e){
    	int i;
    	if(L.length == 0)
    		return 0;
    
    	for(i =0; i<L.length; i++){
    		if(L.data[i] == e)
    			break;
    	}
    	
    	if(i>=L.length)
    		return 0;
    
    	return i;
    }
    
    //在线性表指定位置前插入新元素ｅ
    Status ListInsert(SqList *L, int i, ElemType e){
    	int k;
    	if(L->length == MAXSIZE)
    		return ERROR;//表已满
    	if(i <0 || i >L->length)
    		return ERROR;
    	//插入位置不在表尾，元素后移
    	if(i <= L->length){
    		for(k = L->length -1; k>=i; k--)
    			L->data[k+1] = L->data[k];
    	}
    	L->data[i] =e;
    	L->length++;
    	return OK;
    }
    
    //删除指定位置的元素
    Status ListDelete(SqList *L, int i, ElemType *e){
    	int k;
    	if(L->length == 0)
    		return ERROR;
    	if(i <0 || i > L->length-1)
    		return ERROR;
    
    	*e =L->data[i];
    	//删除的位置不是最后位置，要前移元素
    	if(i<L->length){
    		for(k=i; k<L->length;k++)
    			L->data[k] = L->data[k+1];
    	}	
    	L->length--;
    	return OK;
    }
    
    //遍历输出表元素
    Status ListTraverse(SqList L){
    	int i;
    	for(i =0; i<L.length; i++)
    		visit(L.data[i]);
    
    	printf("\n");
    	return OK;
    }
    
    //合并两个线性表
    void unionList(SqList *La, SqList Lb){
    	int La_len, Lb_len,i;
    	ElemType e;
    	La_len = ListLength(*La);
    	Lb_len = ListLength(Lb);
    	for(i=0; i< Lb_len; i++){
    		GetElem(Lb,i,&e);
    		//如果表lb中的元素不在la中，则插入
    		if(!LocateElem(*La,e))
    			ListInsert(La,La_len,e);
    	}
    }

编写测试代码：

int main(){
    	SqList L;
    	SqList Lb;
    
    	ElemType e;
    	Status i;
    	int j,k;
    	i = InitList(&L);
    	printf("初始化后的Ｌ：L.length = %d\n",L.length);
    
    	for(j=1 ;j<5; j++){
    		i= ListInsert(&L,i,j);
    	}
    	printf("在L的表头依次插入1,2,3,4,5后，L.data=");
    	ListTraverse(L);
    
    	printf("L.length=%d\n",L.length);
    	i=ListEmpty(L);
    	printf("L空表？：　i=%d\n",i);
    
    	i= ClearList(&L);
    	printf("清空L后,L.length=%d\n",L.length);
    
    	for(j=1 ;j<10; j++){
    		i= ListInsert(&L,i,j);
    	}
    	printf("在L的表头依次插入1,2,3,4,5,6,7,8,9,10后，L.data=");
    	ListTraverse(L);
    
    	k=ListLength(L);	
    	i= ListDelete(&L,k/2,&e);//删除中间元素
    	ListTraverse(L);
    
    	return 0;
    }

测试结果：

![20180311103750798][]

[20180311103750798]: /images/20220530/a1c5eeadb8e644d1b3f23b21e0a4e5ae.png