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

65 阅读 0 评论 43 点赞

我是靠谱客的博主无语黑夜，最近开发中收集的这篇文章主要介绍线性表的相关操作-初始化、增添、删除删除操作，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

线性表的定义

线性表是具有相同数据类型的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;