数据结构之线性表的顺序存储结构（C语言）

客官°小女子只卖身不卖艺 2023-02-11 12:24 1阅读 0赞

### 定义 ###

**线性表（List）：零个或者多个数据元素的有限序列。**  
这里需要强调几个关键的地方。  
首先它是一个序列。也就是说，元素之间是有顺序的，若元素存在多个，则第一个元素没有前驱结点，最后一个元素没有后继结点，其他的元素的都有且只有一个前驱和后继。  
然后线性表强调是有限的，班级人数是有限的，元素个数当然也是有限的。事实上，在计算机中处理的对象都是有限的，那种无限的序列，只存在数学概念中。

**数学语言定义**  
若将线性表即为（a1，……ai-1，ai,ai+1,……，an）则表中ai-1领先于ai，ai领先于,ai+1,称,ai+1是ai的直接后继元素。当i=1，2，……，n-1时，ai有且仅有一个直接后继，当i=2,3，……n时，ai有且仅有一个直接前驱。  
![在这里插入图片描述][20200523181445991.png]线性表元素的个数n（n>=0）定义为线性表的长度，当n=0时，称为空表。

**在较复杂的线性表中，一个数据元素可以由若干数据项组成。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70]

### 顺序存储结构 ###

线性表的顺序存储结构指的是用一段连续的存储单元依次存储线性表的数据元素。  
![在这里插入图片描述][2020052318252387.png]

#### 插入与删除操作 ####

**获得元素操作**  
对于线性表的顺序存储结构，如果我们要实现GetEle操作，即将线性表L中的第i个位置元素值返回。就程序而言，只要i的数值在数组的下标范围内，就是把数组i-1下标的值返回即可。

#define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    
    typedef int Status;
    /*
    Status 是函数的类型，其值是函数结果状态代码，如OK
    初始条件：顺序线性表L存在，1<=i<=ListLength(L)
    操作结果：用e返回L中第i个数据元素的值。
    */
    Status GetEle(SqList L,int i,ElemType *e){
        
    	if(L.length == 0 || i < 1 || i > L.length){
        
    		return ERROR;
    	}
    	*e = L.data[i-1]
    	return OK;
    }

注意这里返回值类型Status是一个整型，返回OK代表1，ERROE代表0。

**插入元素操作**  
如果我们要实现ListInsert（\*L,i,e）即在线性表L中的第i个位置插入新元素e，应该如何操作？

举个例子，本来我们在春运时去买火车票，大家都排队排的好好的。这时来了一个美女，对着队伍中排在第三位的你说，“大哥，求求你帮帮忙，我家母亲有病，我得急着回去看她，这队伍这么长，你可否让我排在你的前面？”你心一软，就同意了。这时，你必须得退后一步，否则她是没法进到队伍来的。这可不得了，后面的人像蠕虫一样，全部都得退一步。骂起四声。但后面的人也不清楚这加塞是怎么回事，没什么办法。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70 1]**插入算法思路：**  
1、如果插入位置不合理，抛出异常。  
2、如果线性表长度大于等于数组的长度，则抛出异常或者动态增加容量。  
3、从最后一个元素开始向前遍历到第i个位置，分别将他们向后移动一个位置。  
4、将要插入元素填入位置i。  
5、表长加1。

/* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */
    /* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
    Status ListInsert(SqList *L,int i,ElemType e)
    {
         
    	int k;
    	if (L->length==MAXSIZE)  /* 顺序线性表已经满 */
    		return ERROR;
    	if (i<1 || i>L->length+1)/* 当i比第一位置小或者比最后一位置后一位置还要大时 */
    		return ERROR;
    
    	if (i<=L->length)        /* 若插入数据位置不在表尾 */
    	{
        
    		for(k=L->length-1;k>=i-1;k--)  /* 将要插入位置之后的数据元素向后移动一位 */
    			L->data[k+1]=L->data[k];
    	}
    	L->data[i-1]=e;          /* 将新元素插入 */
    	L->length++;
    
    	return OK;
    }

**删除操作**  
接着刚才的例子，此时后面排队的人群意见都很大，都说怎么可以这样，不管是什么原因，插队就是不行，有本事，找火车站开后门去，就在这时，远处跑来一个胖子对着美女喊，可找到你了，你这骗子，还我钱。只见这女子二话不说，突然就冲出了队伍，胖子追在其后，消失在人群中，于是排队的人群，均向前移动了一步。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70 2]**删除算法的思路**  
1、如果删除位置不合理，则抛出异常。  
2、取出删除元素。  
3、从删除位置开始遍历到最后一个元素位置，分别将他们都向前移动一个位置。  
4、表长减一。

/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
    /* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
    Status ListDelete(SqList *L,int i,ElemType *e) 
    {
         
        int k;
        if (L->length==0)               /* 线性表为空 */
    		return ERROR;
        if (i<1 || i>L->length)         /* 删除位置不正确 */
            return ERROR;
        *e=L->data[i-1];
        if (i<L->length)                /* 如果删除不是最后位置 */
        {
        
            for(k=i;k<L->length;k++)/* 将删除位置后继元素前移 */
    			L->data[k-1]=L->data[k];
        }
        L->length--;
        return OK;
    }

### 总结 ###

线性表顺序存储结构的优缺点。  
优点：  
1、无须为表示表中元素之间的逻辑关系而增加额外的存储空间。  
2、可以快速的存取表中任一位置的元素。

缺点：  
1、插入和删除操作需要移动大量元素。  
2、当线性表长度变化较大时，难以确定存储空间的容量。  
3、造成存储空间的“碎片”。

### 完整代码 ###

#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是函数的类型,其值是函数结果状态代码，如OK等 */
    typedef int ElemType;        /* ElemType类型根据实际情况而定，这里假设为int */
    
    
    Status visit(ElemType c)
    {
        
        printf("%d ",c);
        return OK;
    }
    
    typedef struct
    {
        
    	ElemType data[MAXSIZE];        /* 数组，存储数据元素 */
    	int length;                                /* 线性表当前长度 */
    }SqList;
    
    /* 初始化顺序线性表 */
    Status InitList(SqList *L) 
    {
         
        L->length=0;
        return OK;
    }
    
    /* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
    Status ListEmpty(SqList L)
    {
         
    	if(L.length==0)
    		return TRUE;
    	else
    		return FALSE;
    }
    
    /* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
    Status ClearList(SqList *L)
    {
         
        L->length=0;
        return OK;
    }
    
    /* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */
    int ListLength(SqList L)
    {
        
    	return L.length;
    }
    
    /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
    /* 操作结果：用e返回L中第i个数据元素的值,注意i是指位置，第1个位置的数组是从0开始 */
    Status GetElem(SqList L,int i,ElemType *e)
    {
        
        if(L.length==0 || i<1 || i>L.length)
                return ERROR;
        *e=L.data[i-1];
    
        return OK;
    }
    
    /* 初始条件：顺序线性表L已存在 */
    /* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
    /* 若这样的数据元素不存在，则返回值为0 */
    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+1;
    }
    
    
    /* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */
    /* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
    Status ListInsert(SqList *L,int i,ElemType e)
    {
         
    	int k;
    	if (L->length==MAXSIZE)  /* 顺序线性表已经满 */
    		return ERROR;
    	if (i<1 || i>L->length+1)/* 当i比第一位置小或者比最后一位置后一位置还要大时 */
    		return ERROR;
    
    	if (i<=L->length)        /* 若插入数据位置不在表尾 */
    	{
        
    		for(k=L->length-1;k>=i-1;k--)  /* 将要插入位置之后的数据元素向后移动一位 */
    			L->data[k+1]=L->data[k];
    	}
    	L->data[i-1]=e;          /* 将新元素插入 */
    	L->length++;
    
    	return OK;
    }
    
    /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
    /* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
    Status ListDelete(SqList *L,int i,ElemType *e) 
    {
         
        int k;
        if (L->length==0)               /* 线性表为空 */
    		return ERROR;
        if (i<1 || i>L->length)         /* 删除位置不正确 */
            return ERROR;
        *e=L->data[i-1];
        if (i<L->length)                /* 如果删除不是最后位置 */
        {
        
            for(k=i;k<L->length;k++)/* 将删除位置后继元素前移 */
    			L->data[k-1]=L->data[k];
        }
        L->length--;
        return OK;
    }
    
    /* 初始条件：顺序线性表L已存在 */
    /* 操作结果：依次对L的每个数据元素输出 */
    Status ListTraverse(SqList L)
    {
        
    	int i;
        for(i=0;i<L.length;i++)
                visit(L.data[i]);
        printf("\n");
        return OK;
    }
    
    void unionL(SqList *La,SqList Lb)
    {
        
    	int La_len,Lb_len,i;
    	ElemType e;
    	La_len=ListLength(*La);
    	Lb_len=ListLength(Lb);
    	for (i=1;i<=Lb_len;i++)
    	{
        
    		GetElem(Lb,i,&e);
    		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后：L.length=%d\n",L.length);
        for(j=1;j<=5;j++)
                i=ListInsert(&L,1,j);
        printf("在L的表头依次插入1～5后：L.data=");
        ListTraverse(L); 
    
        printf("L.length=%d \n",L.length);
        i=ListEmpty(L);
        printf("L是否空：i=%d(1:是 0:否)\n",i);
    
        i=ClearList(&L);
        printf("清空L后：L.length=%d\n",L.length);
        i=ListEmpty(L);
        printf("L是否空：i=%d(1:是 0:否)\n",i);
    
        for(j=1;j<=10;j++)
                ListInsert(&L,j,j);
        printf("在L的表尾依次插入1～10后：L.data=");
        ListTraverse(L); 
    
        printf("L.length=%d \n",L.length);
    
        ListInsert(&L,1,0);
        printf("在L的表头插入0后：L.data=");
        ListTraverse(L); 
        printf("L.length=%d \n",L.length);
    
        GetElem(L,5,&e);
        printf("第5个元素的值为：%d\n",e);
        for(j=3;j<=4;j++)
        {
        
                k=LocateElem(L,j);
                if(k)
                        printf("第%d个元素的值为%d\n",k,j);
                else
                        printf("没有值为%d的元素\n",j);
        }
        
    
        k=ListLength(L); /* k为表长 */
        for(j=k+1;j>=k;j--)
        {
        
                i=ListDelete(&L,j,&e); /* 删除第j个数据 */
                if(i==ERROR)
                        printf("删除第%d个数据失败\n",j);
                else
                        printf("删除第%d个的元素值为：%d\n",j,e);
        }
        printf("依次输出L的元素：");
        ListTraverse(L); 
    
        j=5;
        ListDelete(&L,j,&e); /* 删除第5个数据 */
        printf("删除第%d个的元素值为：%d\n",j,e);
    
        printf("依次输出L的元素：");
        ListTraverse(L); 
    
    	//构造一个有10个数的Lb
    	i=InitList(&Lb);
        for(j=6;j<=15;j++)
                i=ListInsert(&Lb,1,j);
    
    	unionL(&L,Lb);
    
    	printf("依次输出合并了Lb的L的元素：");
        ListTraverse(L); 
    
        return 0;
    }

[20200523181445991.png]: https://img-blog.csdnimg.cn/20200523181445991.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200523182256229.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz,size_16,color_FFFFFF,t_70
[2020052318252387.png]: https://img-blog.csdnimg.cn/2020052318252387.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200523183719773.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200523190414829.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz,size_16,color_FFFFFF,t_70