线性表的插入和删除

线性表         linear list

数据项        item

记录        record

文件         file

顺序映像        sequential mapping

结点         node

线性表的顺序存储结构

插入和删除步骤

1:合法性检查（指针，位置i）

2：遍历找到位置

3：建立新结点（mallco），插入或者删除结点；

 Tip：
元素插入需后移，用--遍历

元素删除需前移，用++遍历

#define MAXSIZE 20//存储空间的初始分配量
#define OK 1 
#define ERROR 0 
#define TRUE 1 
#define FALSE 0 

typedef int Elemtype;
typedef int Status;

typedef struct{
    Elemtype data[MAXSIZE];
    int length;
}SqList;

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;
}

Status ListInsert(SqList *L,int i,Elemtype e){
    if(L->length==MAXSIZE)//1：合法性检查
    return ERROR;
    if(i<1||i>L->length+1)//i值是否合法
    return ERROR;
    if(i<=L->length)//如果插入位置不在表尾
    {
        for(int k=L->length-1;k>=i-1;k--)
            l->data[k+1]=l->data[k];/2：元素后移
        l->data[i-1]=e;//3：新元素插入
        l->length++;
        return OK;
    }
}
Status ListDelte(SqList *L,int i,Elemtype *e){
    if(L->length=0)//线性表为空
    return ERROR;
    if(i<1||i>l->length)//删除位置不存在
    return ERROR;
    *e=L->data[i-1];//通过指针返回删除的值
    if(i<L->length)//删除位置不在表尾
    {for(int k =i;k<=length-1;k++)
    //注意与插入的区别；
        L->data(k-1)=L->date(k);/删除位置后面的前移
    }
    L->length--;
    return OK;
}

 线性表的链式存储结构

//线性表的链式存储结构
typedef struct Node{
    Elemtype date;
    struct Node *next;
}Node;
typedef struct Node *LinkeList;//

Status GetElem (LinkeList L,int i,Elemtype *e){
    LinkeList p=L->next;//1:初始化
    int j=1;
    while(p&&j<i)
         j++;
         p=p->next;//2:遍历
    }
    if(!p||j>i)
    return ERROR;//3：i值合法性检测；
    
    *e=p->date;//4：返回i个元素的值
    return OK;
}
Status ListInsert(LinkeList L,int i,Elemtype e){
    LinkeList p=L;//
    int j=1;
    while(p&&j<i){//1：寻找结点i
        p=p->next;
        j++;
    }
    if(!p||j>i)
    return ERROR;//2:i的合法性检查；
    LinkeList s=(LinkeList)malloc(sizeof(Node));//3：生成新结点
    s->next=p->next;
    p->next=s;
    s->date=e;//4:链接新的结点
}

Status ListDelte(LinkeList L,int i,Elemtype *e){
    LinkeList p=L;
    int j=1;
    while(p->next&&j<i){//1：寻找结点i
        p=p->next;
        j++;
    }
    if(!p->next||j>i)
    return ERROR;//2:i的合法性检查；
    LinkeList s=p->next;
    p->next=s->next;
    *e=s->date;
    free(s);//3:删除结点
}