数据结构—线性结构—(顺序表)

叁歲伎倆 2023-07-18 14:00 78阅读 0赞

### 目录 ###

*   *  定义：
     *  存取方式:
     *  两种内存的分配方式：
     *  顺序表的基本操作：
     *   *  插入操作：
         *  删除操作：
         *  按值查找：

## 定义： ##

线性表的顺序存储称为顺序表

即：一组地址连续存放的的存储单元依次存放线性表的元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

（顺序表当中的逻辑顺序和物理顺序是相同的）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]

## 存取方式: ##

一般选择用数组存放顺序表

顺序表可以随机存取，因为可以从起始的元素推测出其他元素的位置

（ LOC ( A ) + ( X ) \* sizeof ( ElemType ) ）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]

## 两种内存的分配方式： ##

数组静态分配

在初始化结构体的同时，创建了一个长度为 MaxSize 的 ElemType 类型的数组，所以不需要给新元素分配空间。

#define MaxSize 50 //定义了一个宏，使 MaxSize=50
    typedef struct{              //定义一个结构体，由多个基本数据类型组成一个新的数据类型
    	ElemType data[MaxSize]; //表示一个长度为 MaxSize 的 ElemType 类型的数组
    	int length;             //定义成员变量 length 表示顺序表的长度
    }SqList;                    //表示结构体类型的名字

数组动态分配

结构体中仅仅申请了一个指针类型的 data *（即: LOC(A)）* 用于储存第一个元素的地址，并没有申请空间用于储存 ElemType 类型的元素，所以存储元素的空间需要动态分配。

#define MaxSize 50 //定义了一个宏，使 MaxSize=50
    typedef struct{              //定义一个结构体，由多个基本数据类型组成一个新的数据类型
    	ElemType * data;        //用一个指针储存第一个 ElemType 元素的地址
    	int length;             //定义成员变量 length 表示顺序表的长度
    }SqList;                    //表示结构体类型的名字

动态分配语句

> C语言 ：L.data = (ElemType\*)malloc(sizeof(ElemType)\*InitSize);  
> C++中：L.data = new ElemType\[InitSize\];

## 顺序表的基本操作： ##

### 插入操作： ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 4]  
插入操作：时间复杂度 O(n)

//插入成功返回 true，否则返回 false
    bool ListInsert(SqList &L, int i, ElemType e)
    {    //在线性顺序表 L 中第 i 个位置插入一个元素 e，
    	if( i < 1||i > L.length + 1 ){  //如果该位置不合法，就返回 false
    		return false;
    	}
    	if( L.length >= MaxSize ){     //若数组已没有位置能继续插入，就返回 false
    		return false;
    	}
    	for(int j=L.length;j>=i;j++){  //从第i个元素开始，每个元素向后移动一个单元
    		L.data[j]=L.data[j-1];
    	}
    	L.data[i-1]=e;           //数组是从零开始的，下标为 i-1 即第 i 个位置
    	L.length++;				 //因为插入成功一个元素，顺序表长度+1
    	return true;
    }

### 删除操作： ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 7]  
删除操作：时间复杂度 O(n)

//删除成功返回 true，否则返回 false
    bool ListDelete(SqList &L, int i, ElemType &e)
    { 			//在线性顺序表 L 中删除第 i 个位置元素 e，
    	if( i < 1||i > L.length ){   //判断删除的位置是否合法
    		return false;
    	}
    	e = L.data[i-1];		//获取要删除的元素 e
    	for(int j=i;j<L.length;j++){ //从第i+1个元素开始，每个元素向前移动一个单元
    		L.data[j-1]=L.data[j];
    	}
    	L.length--; //删除元素成功，L总长度-1
    	return true;
    }

### 按值查找： ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 9]  
按值查找：时间复杂度 O(n)

//在L中找出与元素e相等的元素，并返回其位置
    int LocateElem(SqList L,ElemType e)
    { //需要改变参数时采用引用变量，不需要改变参数时不需要采用引用变量
    	int i;
    	for(i=0;i<L.length;i++){   //从第一个元素开始遍历整个顺序表
    		if(L.data[i]==e){      //如果找到了与元素e相同的元素
    			return i+1;		  //返回找到的元素的位置
    		}
    	}
    	return 0;		//如果没有找到与元素e相同的元素，返回一个不存在的位置
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]: /images/20230528/124f2fc526c14c69a61f3b796e7bd0bb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]: /images/20230528/3fab872585874b42a9bbe92a4ff0b8f5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 2]: /images/20230528/f5e07250bf5549f4adaee922bab7a2aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 3]: /images/20230528/9499de8d9bce485aa8ca75cb83421ec9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 4]: /images/20230528/458cc45be03948459928b6fcb06bb01a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 5]: /images/20230528/ac9addf9572641d2bc918ca4affc4df7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 6]: /images/20230528/aaa0eef318a54dae8b5b60c11b36e507.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 7]: /images/20230528/dd1687f3f62b428e80a614a34b70466f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 8]: /images/20230528/53bb219c56794d5e9341e47683b4527e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 9]: /images/20230528/0044cb79e07046e9aac49284f0bd4345.png