C语言数据结构002——线性表的顺序表示

青旅半醒 2023-10-06 17:59 36阅读 0赞

## 线性表的定义(线性表包含顺序表示和链式表示) ##

线性表是一种由n(n≥0)个相同类型数据元素a0, a1,…, an-1组成的线性结构。可以在任意位置插入和删除数据元素操作；

## 一、顺序表（线性表的顺序表示） ##

顺序存储结构的线性表称作顺序表(Sequence List)。

### 顺序表的存储结构 ###

实现顺序存储结构的方法是使用数组。数组把线性表的数据元素存储在一块连续地址空间的内存单元中，这样线性表中逻辑上相邻的数据元素在物理存储地址上也相邻。数据元素间的逻辑上的前驱、后继逻辑关系就表现在数据元素的存储单元的物理前后位置上。  
![在这里插入图片描述][20210622091705819.png]

### 顺序表的实现 ###

//顺序表的结构体
    typedef  struct
    {
        	
    	DataType list[MaxSize];	//list表示顺序表存储数据元素的数组，MaxSize表示存储顺序表的数组的最大存储单元个数，			
    	int size; //size表示顺序表当前存储的数据元素个数。
    } SeqList;
    
    //（1）初始化
    void ListInitiate(SeqList *L)
    {
        	
    	L->size= 0;  /*定义初始数据元素个数*
    }
    
    //（2）求当前数据元素的个数
    int ListLength(SeqList L)		 
    {	
    	return L.size;
    } 
    
    //（3）插入数据元素
    //在顺序表L的第i（0≤i ≤ length）个位置前插入数据元素x
    //插入成功返回1，失败返回0
    int ListInsert(SeqList *L, int i, DataType x)
    {	
    	int j;
    	if(L-> size >=MaxSize)
    	{
    		printf(“顺序表已满无法插入！\n”);
    		return 0;
    	}
    	else if(i<0||i>L-> size )
    	{
    		printf(“参数i不合法！\n”);
    		return 0;
    	}  
    	else {
    		for(j = L-> size; j > i; j--){
        	    L->list[j] = L->list[j-1];      /*依次后移*/
        	}
     		L->list[i] = x;			 /*插入x*/
    		L->size ++;			 /*元素个数加1*/
    		return 1;
    	}
    }
    
    //（4）删除数据元素
    //删除顺序表L中位置i（0≤i ≤ length-1）上的数据元素并保存到x中
    //删除成功返回1，删除失败返回0
    int ListDelete(SeqList *L, int i, DataType *x)	
    {
        	
    	int j;
    	if(L-> size <=0)
    	{
        
    		printf("顺序表已空无数据元素可删！\n");
    		return 0;
    	}
    	else if(i<0||i>L-> size -1)
    	{
        
    		printf("参数i不合法！\n");
    		return 0;
    	}  else 
    	{
        
    		*x = L->list[i];					 /*保存删除的元素到x中*/
     		for(j = i +1; j <= L->size-1; j++){
         
           		L->list[j-1] = L->list[j];   /*依次前移*/
           	}
    		L-> size --;						 /*数据元素个数减1*/
    		return 1;
    	}
    }
    
    //（5）取数据元素
    int ListGet(SeqList L, int i, DataType *x)
    {
        	
    	if(i < 0 || i > L. size -1)
    	{
        
    	    printf("参数i不合法! \n");
    	    return 0;
    	}
    	else
    	{
        
    	    *x = L.list[i];
    	    return 1;
    	}
    } 
    
    //main函数测试
    void main(void)
    {
                
    	 SeqList myList;
         int i , x; 	
         ListInitiate(&myList);
         for(i = 0; i < 10; i++){
         
            ListInsert(&myList, i, i+1);
         }
         ListDelete(&myList, 4, &x);
         for(i = 0; i < ListLength(myList); i++){
        
         	ListGet(myList, i, &x);
    		printf("%d   ", x); //myList.list[i]		
    	 }
    }
    
    程序运行结果：
    1   2   3   4   6   7   8   9   10

[20210622091705819.png]: https://img-blog.csdnimg.cn/20210622091705819.png