数据结构考研学习笔记（一）---顺序表基本操作：插入查询删除

Myth丶恋晨 2023-05-21 07:06 13阅读 0赞

# 数据结构考研学习笔记（一）—顺序表基本操作：插入 查询 删除 #

声明：本文是笔者学习数据结构的笔记，参考：王道考研

## **顺序表定义**：*线性表的顺序存储结构被称为顺序表，它是用一组地址连续的存储单元依次存储线性表中的数据元素，使得逻辑上相邻的两个元素在物理位置上也相邻。* ##

## 特点： ##

**1. 表中的元素的逻辑顺序与其物理顺序相同  
2. 最主要特点是随机访问，通过首地址和元素序号可在时间O（1）内找到指定元素  
3. 存储密度高，内个节点只存储元素  
4. 逻辑上相邻的元素物理上相邻，所以插入和删除操作需要移动大量元素**

线性表顺序存储结构

LOC(A):线性表的起始位置、sizeof（ElemType）：每个数据元素所占用的存储空间大小

<table> 
 <thead> 
  <tr> 
   <th>数组下标</th> 
   <th>顺序表</th> 
   <th>内存地址</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>0</td> 
   <td>a1</td> 
   <td>loc(A)</td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>a2</td> 
   <td>loc(A)+sizeof(ElemType)</td> 
  </tr> 
  <tr> 
   <td>…</td> 
   <td>…</td> 
   <td>…</td> 
  </tr> 
  <tr> 
   <td>i-1</td> 
   <td>ai</td> 
   <td>loc(A)+(i-1)*sizeof(ElemType)</td> 
  </tr> 
  <tr> 
   <td>…</td> 
   <td>…</td> 
   <td>…</td> 
  </tr> 
  <tr> 
   <td>n-1</td> 
   <td>an</td> 
   <td>loc(A)+(n-1)*sizeof(ElemType)</td> 
  </tr> 
  <tr> 
   <td>…</td> 
   <td>…</td> 
   <td>…</td> 
  </tr> 
  <tr> 
   <td>MaxSize-1</td> 
   <td>…</td> 
   <td>loc(A)+(MaxSize-1)sizeof(ElemType)</td> 
  </tr> 
 </tbody> 
</table>

## 静态分配和动态分配 ##

\***一维数组可以是静态分配或者动态分配，在静态分配时，由于数组大小和空间事先已经固定，一旦空间占满，再加入新的数据将会产生溢出，进而导致程序崩溃。  
而动态分配时，存储数组的空间时在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储空间的目的，不需要一次性的划分所有空间** \*  
下面展示 `静态分配`。

// 静态分配
    #define MaxSize 50       //定义线性表的最大长度
    typedef struct{
        
    ElemType data[MaxSize];   //顺序表的当前长度
    int length;               //顺序表当前长度
    }SqList                       //顺序表的类型定义

### 插入操作：在线性表的第i个位置插入元素e，如果元素不合法，则返回false，否则，将顺序表第i个元素及其后的所有元素右移一个位置，第i个位置赋值e，顺序表长度+1，插入成功，返回true ###

下面展示一些 `插入操作`。

// 插入操作
    bool ListInsert(SqList *L, int i, ElemType e)
    {
        
    	if (i<1 || i>L->length + 1)
    		return false;
    	if (L->length >= MaxSize)
    		return false;
    	for (int j = L->length; j >= i; j--)
    		L->data[j] = L->data[j - 1];
    	L->data[i - 1] = e;
    	L->length++;
    	return true;
    };

### 删除操作：删除表中第i个位置的元素，成功返回true，失败false ###

下面展示一些 `删除操作`。

//删除操作
    bool ListDelete(SqList *L, int i, ElemType e) {
        
    	if (i < 1 || i > L->length)
    		return false;
    	e = L->data[i - 1];
    	for (int j = i; j < L->length; j++)
    		L->data[j - 1] = L->data[j];
    	L->length--;
    	return true;
    }

### 按值查找:L中查找第一个元素值等于e，并返回其位序 ###

下面展示一些 `按值查找`。

/*按值查找*/
    int  LocationElem(SqList L, ElemType e)
    {
        
    	int i;
    	for (i = 0; i < L.length; i++)
    		if (e == L.data[i])
    			return i + 1;
    	return 0;
    }

补充：动态分配

#define MaxSize 50
    typedef struct{
        
    ElemType *data;
    int length;
    }SqList;
    //动态分配语句
    //C
      L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);
    //C++
    L.data = new ElemType[InitSize];

工程源码：[点击获取工程][Link 1]

## 公众号同步更新 关注不迷路“MeiXiangDao2020” ##

![在这里插入图片描述][20201006094256318.jpg_pic_center]

[Link 1]: https://download.csdn.net/download/sf9090/12376231
[20201006094256318.jpg_pic_center]: /images/20230521/01abca15e04c4fc69fe17683c6f8552c.png