顺序表的基本操作_【数据结构】顺序表基本操作的实现（C语言）

╰+攻爆jí腚メ 2023-10-05 18:36 2阅读 0赞

![e81d084085198de12953e01452b2a582.png][]

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

线性表元素为**逻辑上**相邻，顺序存储时在物理上也相邻（以**数组**的形式进行存储）

**L=(**

![equation?tex=a\_%7B1%7D][equation_tex_a_7B1_7D] ,

![equation?tex=a\_%7B2%7D][equation_tex_a_7B2_7D] ,...,

![equation?tex=a\_%7Bi%7D][equation_tex_a_7Bi_7D] ,

![equation?tex=a\_%7Bi%2B1%7D][equation_tex_a_7Bi_2B1_7D] ,...

![equation?tex=a\_%7Bn%7D][equation_tex_a_7Bn_7D]

**)**

![c8bbc69d9a4ef29e8a71082d60f7ec4a.png][]

**注意：**

*  顺序表下标从1开始，而数组下标从0开始
 *  数组大小是固定的，线性表的大小不是固定的
 *  顺序表是一维的，而数组可以是多维的

### 1，顺序表的定义： ###

数组静态分配

#define MaxSize 50
    #define ElemType int 
    typedef struct 
    {
         
    	ElemType data[MaxSize];
    	int length;
    }SqList;

数组动态分配

#define MaxSize 50
    #define ElemType int 
    typedef struct
    {
         
    	ElemType* data;
    	int length;
    }SqList;

通过将数组定义为指针类型可以实现数组的动态变化，但此时的data仅是定义的变量（表示初始地址），使用时需要**动态分配内存**（为数组分配空间）。

**动态分配语句**(其中InitSize为需要的元素个数)：

**C  *L.data=(ElemType\*)malloc(sizeof(ElemType)\*InitSize);***

**C++ *L.data=new ElemType\[InitSize\];***

### 2，顺序表中元素的插入： ###

在顺序表的i位置上插入e

bool ListInsert(SqList& L, int i, ElemType &e) 
      //&L表示引用类型，使用引用可以改变L，而不仅仅是值传递
    {
         
    	if (i<1 || i>L.length + 1)         //位置不能为0或负数，也不能使顺序表之间有间隔
    		return false;
    	if (L.length >= MaxSize)           //顺序表的长度不能超过数组的长度
    		return false;
    	for (int j = L.length; j >= i; j--)
    	{
         
    		L.data[j] = L.data[j - 1];    //将i位置之后的数据依次
    		L.data[i - 1] = e; 
    		L.length++;
    		return true;
    	}
    }

最好时间复杂度：O(1) 平均时间复杂度：O(n) 最坏时间复杂度：O(n)

### 3，顺序表中元素的删除： ###

删除顺序表i位置上的数据，存储到e

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

最好时间复杂度：O(1) 平均时间复杂度：O(n) 最坏时间复杂度：O(n)

### 4，顺序表的按值查找： ###

int LocateElem(SqList L, ElemType e)
    {
         
    	int i;
    	for (i = 0; i < L.length; i++)
    	{
         
    		if (L.data[i] == e)
    		{
         
    			return i + 1;
    		}
    		return 0;
    	}
    }

查找成功则返回元素e在顺序表中的位置

最好时间复杂度：O(1) 平均时间复杂度：O(n) 最坏时间复杂度：O(n)

[e81d084085198de12953e01452b2a582.png]: https://img-blog.csdnimg.cn/img_convert/e81d084085198de12953e01452b2a582.png
[equation_tex_a_7B1_7D]: https://www.zhihu.com/equation?tex=a_%7B1%7D
[equation_tex_a_7B2_7D]: https://www.zhihu.com/equation?tex=a_%7B2%7D
[equation_tex_a_7Bi_7D]: https://www.zhihu.com/equation?tex=a_%7Bi%7D
[equation_tex_a_7Bi_2B1_7D]: https://www.zhihu.com/equation?tex=a_%7Bi%2B1%7D
[equation_tex_a_7Bn_7D]: https://www.zhihu.com/equation?tex=a_%7Bn%7D
[c8bbc69d9a4ef29e8a71082d60f7ec4a.png]: https://img-blog.csdnimg.cn/img_convert/c8bbc69d9a4ef29e8a71082d60f7ec4a.png