线性表的相关操作-初始化、增添、删除

浅浅的花香味﹌ 2022-12-11 07:26 109阅读 0赞

## 线性表的定义 ##

线性表是具有相同数据类型的n个元素的有限序列，n是表长（每个元素占的空间是一样的）  
ai是线性表中的“第i个”元素线性表中的位序（位序从1开始，数组下标从0开始）

### 线性表的初始化和简单遍历 ###

#include <stdio.h>
    #include "stdlib.h"
    #define maxsize 10
    
    typedef struct {
        
        int data[maxsize];//用静态的数组存放数据元素
        int length;//线性表当前长度
    }SqList;
    //初始化顺序表
    void Initilist(SqList &L){
        //此处引用需要在C++环境进行，C语言环境编译不出来,&L对参数的修改结果带过来
        int i;
        for(i=0;i<maxsize;i++)
            L.data[i]=0;//将所有数据元素默认为初始值
        L.length=0;//顺序表的初始长度为0
    
    }
    int main() {
        
        SqList L;//声明一个顺序表
        Initilist(L);//初始化顺序表
        for(int i=0;i<maxsize;i++){
        
            printf("%d ",L.data[i]);
        }
    }

#### 这是通过静态分配去实现线性表的初始化 ####

要值得注意的是，若一开始没有讲相应的数据默认初始化为0，将会出现“脏数据”的情况

## 通过动态分配实现 ##

因为静态分配的方法不能改变数组的长度，而且如果静态分配的空间太小，容易造成数据溢出，但是如果分配空间太大容易造成空间的浪费。因此这里我们需要考虑动态分配内存的方式  
动态分配实现的基本套路

L.data=(ElemType *)malloc(sizeof(Elemtype) *InitiSize)
    //ElemType 指的是数据类型 InitSize初始化的长度大小

#include<stdio.h>
    #include "stdlib.h"
    #define InitSize 10
    typedef struct {
        
        int *data;//动态分配数组的指针
        int maxsize;//顺序表最大容量
        int length;//当前长度
    }Sqlist;
    void IniLIst(Sqlist &L){
        
        L.data=(int *)malloc(sizeof(int )*InitSize);
        //动态分配空间
        L.length=0;
        L.maxsize=InitSize;
    }
    //增加长度
    void Increase(Sqlist *L,int len){
        
         int *p=L->data;
         L->data=(int *)malloc(sizeof(int)*(len+L->maxsize));
         for(int i=0;i<L->length;i++){
        
             L->data[i]=p[i];//将数据复制到新区域
         }
        L->length=L->maxsize+len;//顺序表最大长度增加N
         free(p);
    }

## 插入操作 ##

bool ListInsert(Sqlist &L,int i,int e){
        
        if(i<1||i>L.length+1)//判断i的范围是否有效
           return false
        if(L.length>=MaxSize)//当前存储空间已满，不能插入
           return false
          for(int j=L.length;j>=i;i--)//将第i个元素往后移
             L.data[j]=L.data[j-1];
             L.data[i-1]=e;//位置i是指位序，对应数组下标要减1
             L.length+=1;
             return True;
             }

## 插入的时间复杂度为O(N) ##

# 删除操作 #

bool delete(Sqlist &L,int i,int &e）
    if(i<1||i>L.length)
    return false;
    e=L.data[i-1];//将被删除元素赋值给e
    for(int j=i;j<L.length;j++)//从前面的元素依次移动
    		L.data[j-1]=L.data[j];//元素前移
    		L.length--;
    	return true;