数据结构与算法-C版(王卓)day02

た入场券 2022-11-14 10:26 246阅读 0赞

# 数据结构与算法(王卓) #

> 参考于B站视频：[数据结构与算法基础（青岛大学-王卓）][-]。笔记仅用于个人复习、专升本备考、考研复习。

--------------------

> 上一篇：[第一章 绪论][Link 1]

## 第二章 线性表 ##

### 2.1 线性表的定义和特点 ###

*  线性表是具有相同特性的数据元素的一个有限序列。
    
     *  ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center]
     *  由n(n≥0)个数据元素（结点）a1， a2.… an组成的有限序列。
     *  其中数据元素的个数n定义为表的长度。
     *  当n=0时，称为空表。
     *  将非空的线性表(n>0)，记作：(a1，a2，…an）。
     *  这里的数据元素ai（1≤i≤n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。
 *  例1，分析26个英文字母组成的英文表。
    
     *  (A,B,C,D………,Z)。
     *  数据元素都是字母；元素间关系是线性。
 *  例2，分析某单位历年拥有计算机的数量。
    
     *  (6,17,28，50，92，188)。
 *  同一线性表中的元素必定具有相同特性，数据元素间的关系是线性关系。

>  *  从以上例子可看出线性表的逻辑特征是：
>     
>      *  在非空的线性表，有且仅有一个开始结点a1 ，它没有直接前趋，而仅有一个直接后继a2 ；
>      *  有且仅有一个终端结点an ，它没有直接后继，而仅有一个直接前趋an-1 ；
>      *  其余的内部结点ai （2 ≤ i ≤ n-1）都有且仅有一个直接前趋a1 和一个直接后继ai+1 。
>  *  线性表是一种典型的线性结构。

### 2.2 案例引入 ###

*  【案例1】一元多项式的运算：实现两个多项式加、减、乘运算。
    
     *   P n ( x ) = p 0 + p 1 x + p 2 x 2 + … + p n x n P\_\{n\}(x)=p\_\{0\}+p\_\{1\} x+p\_\{2\} x^\{2\}+\\ldots+p\_\{n\} x^\{n\} Pn(x)=p0\+p1x\+p2x2\+…\+pnxn
     *  线性表P=(p0 , p1 , p2 , …… , pn )，（每一项的指数 i 隐含在其系数pi 的序号中）
     *  ![在这里插入图片描述][20210328213014960.png_pic_center]
     *  ![在这里插入图片描述][20210328213022948.png_pic_center]
 *  案例2：稀疏多项式的运算。
    
     *  多项式非零项的数组表示。
     *  ![在这里插入图片描述][20210328213042468.png_pic_center]
     *  ![在这里插入图片描述][20210328213051471.png_pic_center]
     *  线性表A=((7,0), (3,1), (9,8), (5,17))
     *  线性表B=((8,1), (22,7), (-9,8))
     *  创建一个新数组C。
     *  分别从头遍历比较a和b的每一项：
        
         *  指数相同，对应系数相加，若其和不为零，则在C中增加一个新项；
         *  指数不相同，则将指数较小的项复制到c中。
     *  一个多项式已遍历完毕时，将另一个剩余项依次复制到c中即可。
 *  顺序存储结构存在问题：
    
     *  存储空间分配不灵活；
     *  运算的空间复杂度高。
 *  ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 1]
 *  ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 2]
 *  ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 3]
 *  ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 4]

### 2.3 线性的类型定义 ###

*  抽象数据类型线性表的定义如下：

ADT List{  
        数据对象: D={ ai | ai属于Elemset, (i=1,2,…n,n≥0)} 
        数据关系: R={ < ai-1 < ai > ai-1,ai属于D,(i=2,3,…n} 
        基本操作: 
           InitList(&L);  DestroyList(&L);
           Listinsert(&L,i,e);  ListDelete(&L,i,&e);
             ....等等 
    }ADT List

*  基本操作：
    
     *  InitList (&L)
        
         *  操作结果：构造一个空的线性表L。
     *  DestroyList(&L)
        
         *  初始条件：线性表L已存在。
         *  操作结果：销毁线性表L。
     *  ClearList (&L)
        
         *  初始条件：线性表L已存在。
         *  操作结果：将L重置为空表。
     *  ListEmpty(L)
        
         *  初始条件：线性表L已存在。
         *  操作结果：若L为空表， 则返回true, 否则返回false。
     *  ListLength(L)
        
         *  初始条件：线性表L已存在。
         *  操作结果：返回L中数据元素个数。
     *  GetElem(L,i,&e)
        
         *  初始条件：线性表L巳存在，且1<= i <= ListLength(L)。
         *  操作结果：用e返回L中第1个数据元素的值。
     *  LocateElem(L,e, compare())
        
         *  初始条件：线性表L已经存在，compare()是数据元素判定函数。  
            操作结果：返回L中第1个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回值为0。
     *  PriorElem(r,cur\_e,&pre\_e)
        
         *  初始条件：线性表L已存在。
         *  操作结果：若cur\_e是L的数据元素，且不是第一个，则用pre\_e返回其前驱，否则操作失败，pre\_e无定义。
     *  NextElem(L,cur\_e,&next\_e)
        
         *  初始条件：线性表L已存在。
         *  操作结果：若cur\_e是L的数据元素，且不是最后一个，则用next\_e返回其后继，否则操作失败，next\_e无定义。
     *  Listinsert(&L,i,e)
        
         *  初始条件：线性表L已存在，且1<= i <= ListLength (L) +1。
         *  操作结果：在 L中第1个位置之前插入新的数据元素 e, L的长度加1。
        
        ![在这里插入图片描述][20210328213145780.png_pic_center]
     *  ListDelete(&L,i,&e)
        
         *  初始条件：线性表L已存在且非空 ，且1 <= i <= ListLength(L)。
         *  操作结果：删除L的第1个数据元素，L的长度减1。
        
        ![在这里插入图片描述][20210328213156336.png_pic_center]
     *  ListTraverse(&L,visited())
        
         *  初始条件：线性表L已经存在。
         *  操作结果：依次对线性表中每个元素调用visited（）。

> 以上所提及的运算是逻辑结构上定义的运算。只要给出这些运算的功能是“做什么”，至于“如何做“等实现细节，只有待确定了存储结构之后才考虑。

### 2.4 线性表的顺序表示和实现 ###

#### 2.4.1 线性表的顺序存储表示 ####

*  线性表的顺序表示又称为顺序存储结构或顺序映像。
 *  顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
 *  ![在这里插入图片描述][20210328213208701.png_pic_center]
 *  线性表的第1个数据元素a的存储位置，称作线性表的起始位置或基地址。

--------------------

**顺序存储结构**

*  例如：线性表（1，2，3，4，5，6）的存储结构：
    
     *  ![在这里插入图片描述][20210328213220722.png_pic_center]
 *  依次存储，地址连续——中间没有空出存储单元。这是一个典型的线形表顺序存储结构。
    
     *  ![在这里插入图片描述][20210328213228196.png_pic_center]
 *  地址不连续——中间存在空的存储单元。不是一个线形表顺序存储结构。
 *  线形表顺序存储结构占用一片连续的存储空间。知道某个元素的存储位置就可以计算其他元素的存储位置。

--------------------

**顺序表中元素存储位置的计算**

*  ![在这里插入图片描述][20210328213238466.png_pic_center]
 *  假设线性表的每个元素需占 j 个存储单元，则第 i+1 个数据元素的存储位置和第 i 个数据元素的存储位置之间满足关系：
    
     *  LOC(ai+1 )=LOC(ai )+ j
 *  由此，所有数据元素的存储位置均可由第一个数据元素的存储位置得到：
    
     *  LOC(ai )=LOC(a1 )+(i-1)x j
 *  ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 5]
 *  顺序表的特点：
    
     *  以物理位置相邻表示逻辑关系。
     *  任一元素均可随机存取。（优点）
 *  ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 6]
 *  ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 7]
    
        #define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量 
        typedef struct{  
            ElemType elem[LIST_INIT_SIZE]; 
            int length；// 当前长度 
        }SqList;
 *  定义线性表

#define MAXSIZE 1000 //多项式可能达到的最大长度
    typedef struct{  //多项式非零项的定义
        float p; // 系数
        int e; // 指数
    }Polynomial;
    
    typedef struct{ 
        Polynomial *elem; // 存储空间的基地址
        int length; // 多项式中当前项的个数
    }SqList; // 多项式的顺序存储结构类型为SqList

#### 类C语言有关操作补充 ####

*  顺序表类型定义
    
        typedef struct{ 
            ElemType data[];  // 可修改ElemType，来定义数据类型
         // char data[];
         // float data[];
            int length;
        }SqList;    // 顺序表类型
    
     *  若不想修改内部，可提前外部定义
    
        typedef char ElemType;
        typedef int ElemType;
    
     *  或者这样，定义多个：
    
        typedef struct {  
            float p; 
            int  e; 
        }Polynomial;
        
        typedef struct{ 
            Polynomial *elem;
            int length; 
        }SqList;

--------------------

*  数组静态分配：

typedef struct{ 
        ElemType data[MaxSize];
        int length;
    }SqList;    // 顺序表类型

*  数组动态分配：

typedef struct{ 
        ElemType *data;
        int length;
    }SqList;    // 顺序表类型

*  C语言的内存动态分配：
    
     *  malloc(m)函数，开辟m字节长度的地空间）并返回这段空间的首地址。
     *  sizeof(x)运算，计算变量x的长度
     *  free§函数，释放指针p所指变量的存储空间，即彻底删除一个变量。
     *  需要加载头文件：<stdlib.h>

// 使用如下内存动态分配函数，对数组进行动态分配。
    SqList L; // 定义一个L的顺序表变量
    L.data=(Elem Type*)malloc(sizeof(Elem Type)*MaxSize);
    
    // 例如
    #define Size 5 // 对Size进行宏定义，表示顺序表申请空间的大小
    table initTable(){ 
        table t;
        t.head=(int*)malloc(Size*sizeof(int));// 构造一个空的顺序表，动态申请存储空间
        if (!t.head) // 如果申请失败，作出提示并直接退出程序
        { 
            printf("初始化失败");
            exit(0);
        }
        t.length=0;// 空表的长度初始化为0
        t.size=Size;// 空表的初始存储空间为Size
        return t;
    }

--------------------

*  C++的动态存储分配：
 *  new 类型名T (初值列表)
    
     *  功能：申请用于存放T类型对象的内存空间，并依初值列表赋以初值。
     *  结果值：
        
         *  成功：T类型的指针，指向新分配的内存。
         *  失败：0(NULL）。

new 类型名T (初值列表)
    int *p1 = new int;   
    或
    int *p1 = new int(10);

*  delete 指针P
    
     *  功能：—释放指针P所指向的内存。P必须是ney操作的返回值。

--------------------

*  C++中的参数传递
    
     *  函数调用时传送给形参表的实参必须与形参三个一致！
        
         *  类型、个数、顺序。
     *  参数传递有两种方式：
        
         *  传值方式（参数为整型、实型、字符型等）；
            
             *  把实参的值传送给函数局部工作区相应的副本中，函数使用这个副本执行必要的功能。函数修改的是副本的值，实参的值不变。
        
            #include <iostream> 
            using namespace std;
            void swap(float m,float n){
            	float temp;
            	temp = m;
            	m = n;
            	n = temp;
            }
            int main(){
            	float a,b;
            	cin>>a>>b;
            	swap(a,b);
            	cout<<a<<endl<<b<<endl;
            }
        
         *  传地址：
            
             *  参数为指针变量；
             *  参数为引用类型；
             *  参数为数组名。
    
        // 参数为指针变量
        // 形参变化影响实参
        #include <iostream> 
        using namespace std;
        void swap(float *m,float *n){
        	float t;
        	t = *m;
        	*m = *n;
        	*n = t;
        }
        int main(){
        	float a,b,*p1,*p2;
        	cin>>a>>b;
        	p1=&a;p2=&b;
        	swap(p1,p2);
        	cout<<a<<endl<<b<<endl;
        }
    
        // 参数为指针变量
        // 形参变化不影响实参？？？
        #include <iostream> 
        using namespace std;
        void swap(float *m,float *n){
        	float *t;
        	t = m;
        	m = n;
        	n = t;
        }
        int main(){
        	float a,b,*p1,*p2;
        	cin>>a>>b;
        	p1=&a;p2=&b;
        	swap(p1,p2);
        	cout<<a<<endl<<b<<endl;
        }
    
        // 参数为数组名
        // 传递的是数组的首地址，对形参数组所做的任何改变都将反映到实参数组中。
        // 用数组作函数的参数，求10个整数的最大数
        #include <iostream> 
        using namespace std;
        #define N 10
        int max(int b[]){
        	int i,n;
        	n=b[0];
        	for(i=1;i<N;i++){
        		if(n<b[i])	n=b[i];
        	}
        	return n;
        }
        int main(){
        	int a[10];
        	int i,m;
        	for(i=0;i<N;i++)
        		cin>>a[i];
        	m=max(a);
        	cout<<"the max number is:" << m <<endl;
        }
    
        // 参数为引用类型
        // 什么是引用？？？
        // 引用：它用来给一个对象提供一个替代的名字。
        #include <iostream> 
        using namespace std;
        
        int main(){ 
        	int i=5;
        	int &j=i;
        	i=7; 
        	cout<<"i="<<i<<" j="<<j<<endl;
        
        
        // j是一个引用类型，代表i的一个替代名i值改变时
        // j值也跟着改变，所以会输出 i=7 j=7
    
        // 参数为引用类型
        #include <iostream> 
        using namespace std;
        void swap(float& m,float& n){
        	float temp;
        	temp = m;
        	m = n;
        	n = temp;
        }
        int main(){
        	float a,b;
        	cin>>a>>b;
        	swap(a,b);
        	cout<<a<<endl<<b<<endl;
        }
 *  引用类型作形参的三点说明
    
     *  （1)传递引用给函数与传递指针的效果是一样的，形参变化实参也发生变化。
     *  （2)引用类型作形参，在内存中并没有产生实参的副本，它直接对实参操作而一般变量作参数，形参与实参就占用不同的存储单元，所以形参变量的值是实参变量的副本。因此，当参数传递的数据量较大时，用引用比用一般变量传递参数的时间和空间效率都好。
     *  （3)指针参数虽然也能达到与使用引用的效果，但在被调函数中需要重复使用“\*指针变量名”的形式进行运算，这很容易产生错误且程序的阅读性较差；另一方面，在主调函数的调用点处，必须用变量的地址作为实参。

--------------------

*  顺序表
    
     *  ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 8]
     *  注意：逻辑位序和物理位序相差1。
     *      // 静态分配 
            #define MAXSIZE 100
            typedef struct{
            	ElemType elem [MAXSIZE];
            	int length;
            }SqList;
            
            // 动态分配
            typedef struct{
            	ElemType *elem;
            	int length;
            }SqList;  
            L.elem=(ElemType*)malloc(sizeof(ElemType)*MAXSIZE);
 *  顺序表示意图

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 9]

#### 2.4.2 顺序表中基本操作的实现 ####

*  线性表的基本操作
    
     *  InitList(&L)//初始化操作，建立一个空的线性表L；
     *  DestroyList(&L)//销毁已存在的线性表L；
     *  ClearList(&L)//将线性表清空；
     *  Listlnsert(&L,i,e)//在线性表L中第i个位置插入新元素e；
     *  ListDelete(&L,i,&e)//删除线性表L中第i个位置元素，用e返回；
     *  IsEmpty(L) //若线性表为空，返回true，否则false；
     *  ListLength(L) //返回线性表L的元素个数；
     *  LocateElem(L,e)//L中查找与给定值e相等的元素，若成功返回该元素在表中的序号，否则返回0；
     *  GetElem(L，i,&e)//将线性表L中的第i个位置元素返回给e；
 *  操作算法中用到的预定义常量和类型：
    
     *      // 函数结果状态代码 
            #define TRUE 1 
            #define FALSE 0 
            #define OK 1 
            #define ERROR 0 
            #define INFEASIBLE -1 
            #define OVERFLOW -2 
            // Status 是函数的类型，其值是函数结果状态代码 
            typedef int Status; 
            typedef char ElemType;
 *  线性表L的初始化（参数用引用）
    
     *      status Initlist Sq(SqList &y){		// 构造一个空的顺序表L
                L.elem=new Elem Type[MAXSIZE];	// 为顺序表分配空间
                if(!L.elem)	exit(OVERFLOW);	// 存储分配失败
                L.length=0;		// 空表长度为0
                return OK;
 *  销毁、清空线性表L
    
     *      // 销毁线性表L 
            void DestroyList(SqList &L){ 
                if(L.elem)  delete L.elem;		// 释放存储空间 
            } 		
            // 清空线性表L 
            void ClearList(SqList&L){ 
                L.length=0;		// 将线性表的长度置为0
            }
 *  求线性表L的长度、判断是否为空
    
     *      // 求线性表L的长度 
            int GetLength(SqList L){ 
                return(L.length); 
            }
            // 判断线性表L是否为空 
            int IsEmpty(SqList L){ 
                if(L.length==0)	return 1; 
                else return 0;
            }

--------------------

*  顺序表的取值(根据位置i获取相应位置数据元素的内容)
    
     *      int GetElem(SqList L,int i,ElemType &e){
                if(i<1||i>L.length)	return ERROR; // 判断i面是否合理，若不合理，返回ERROR
                e=lelem[i-1]); // 第i-1的单元存储着第i个数据
                return OK;
            }

--------------------

*  顺序表的查找
    
     *  在线性表L中查找与指定值e相同的数据元素的位置。
     *  从表的一端开始，逐个进行记录的关键字和给定值的比较。找到，返回该元素的位置序号，未找到，返回0。
    
        int LocateELem(SqList L,ElemType e){
            // 在线性表L中查找值为e的数据元素，返回其序号(是第几个元素)
            for(i=0;n<L.length;i++)
                if(L.elem[i]==e)	return i+1;	// 查找成功，返回序号
            return 0; // 查找失败，返回0
        }
 *  顺序表的查找算法分析：
 *  因为查找算法的基本操作为：将记录的关键字同给定值进行比较。
    
     *  基本操作：L.elem\[i\]==e

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 10]

*  平均查找长度ASL(Average Search Length)：
    
     *  为确定记录在表中的位置，需要与给定值进行比较的关键字的个数的期望值叫做查找算法的平均查找长度。
     *  ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 11]

--------------------

*  顺序表的插入

![在这里插入图片描述][20210328213429206.png_pic_center]

*  插入不同位置的演示：

![在这里插入图片描述][20210328213436367.png_pic_center]

*  线性表的插入运算是指在表的第i（1≤ i ≤ n+1)个位置上，插入一个新结点e，使长度为n的线性表（a1, ……, ai-1, ai, ……an)变成长度为n+1的线性表(a1,…ai-1,e,ai，……an)
    
     *  算法思想：
     *  ①判断插入位置i是否合法。
     *  ②判断顺序表的存储空间是否已满，若已满返回ERROR。
     *  ③将第n至第i位的元素依次向后移动一个位置，空出第 i 个位置。
     *  ④将要插入的新元素e放入第i个位置。
     *  ⑤表长加1，插入成功返回OK。

Status Listlnsert_Sq(SqList &L,int i,ElemType e){ 
    ①   if(i<1 || i>L.length+1)	return ERROR; // i值不合法 
    ②	if(L.length==MAXSIZE)	return ERROR; // 当前存储空间已满 
    ③   for(j=L.length-1;j>=i-1;j--) 
        	L.elem[j+1]=L.elem[j]; // 插入位置及之后的元素后移 
    ④	L.elem[i-1]=e; // 将新元素e放入第个位置 
    ⑤	L.length++; // 表长增1 
         return OK;
    }

*  算法时间主要耗费在移动元素的操作上。
    
     *  若插入在尾结点之后，则根本无需移动（特别快）；
     *  若插入在首结点之前，则表中元素全部后移（特别慢）；
     *  若要考虑在各种位置插入（共n+1种可能）的平均移动次数，该如何计算？

![在这里插入图片描述][2021032821344983.png_pic_center]

*  顺序表插入算法的平均时间复杂度为O(n)。

--------------------

*  顺序表的删除
 *  ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 12]
 *  线性表的删除运算是指将表的第i（1≤ i ≤ n)个结点删除。
    
     *  使长度为n的线性表(a1, ……,ai-1,a，ai+1,…an)；
     *  变成长度为n-1的线性表(a1,…,ai-1,ai+1,.……, an)
     *  算法思想：
     *  ①判断删除位置i是否合法（合法值为1≤ i ≤ n)。
     *  ②将欲删除的元素保留在e中。
     *  ③将第i+1至第n位的元素依次向前移动一个位置。
     *  ④表长减1，删除成功返回OK。

Status ListDelete_Sq(SqList&L,intiy( 
    ①   if(i<1 || i>L.length)	return ERROR;	// i值不合法 
    ②   for(j=i;j<=L.length-1;j++) 
        	L.elem[j-1]=L.elem[j];	//	被删除元素之后的元素前移 
    ③   L.length--; // 表长减1 
         return OK;
    }

*  算法时间主要耗费在移动元素的操作上：
    
     *  若删除尾结点，则根本无需移动（特别快）；
     *  若删除首结点，则表n-1个元素全部前移（特别慢）；
     *  若要考虑在各种位置删除（共n种可能）的平均移动次数，该如何计算？  
        ![在这里插入图片描述][20210328213509810.png_pic_center]
     *  顺序表删除算法的平均时间复杂度为O(n)。

--------------------

*  顺序表（线性表的顺序存储结构）的特点：
    
     *  ① 利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构一致；
     *  ② 在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。  
        因此可以粗略地认为，访问每个元素所花时间相等
     *  这种存取元素的方法被称为随机存取法。
 *  顺序表的操作算法分析：
    
     *  时间复杂度
        
         *  查找、插入、删除算法的平均时间复杂度为O(n)。
     *  空间复杂度
        
         *  显然，顺序表操作算法的空间复杂度S(n)=O(1)（没有占用辅助空间）。
 *  顺序表优缺点：
    
     *  优点：
        
         *  存储密度大（结点本身所占存储量/结点结构所占存储量）；
         *  可以随机存取表中任一元素。
     *  缺点：
        
         *  在插入、删除某一元素时，需要移动大量元素；
         *  浪费存储空间；
         *  属于静态存储形式，数据元素的个数不能自由扩充。

> 下一篇：第二章 线性表(中)

[-]: https://www.bilibili.com/video/BV1nJ411V7bd
[Link 1]: https://blog.csdn.net/m0_46153949/article/details/115221010
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/a850dc0c2d554c939d9c155965ba8e9f.png
[20210328213014960.png_pic_center]: /images/20221022/7f9e8e68fa454ae0b220da1a35182765.png
[20210328213022948.png_pic_center]: /images/20221022/e507d57d95fb45118b5dbb486525cdd7.png
[20210328213042468.png_pic_center]: https://img-blog.csdnimg.cn/20210328213042468.png#pic_center
[20210328213051471.png_pic_center]: https://img-blog.csdnimg.cn/20210328213051471.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20210328213103317.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/2021032821311148.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20210328213119846.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/2021032821312770.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[20210328213145780.png_pic_center]: https://img-blog.csdnimg.cn/20210328213145780.png#pic_center
[20210328213156336.png_pic_center]: https://img-blog.csdnimg.cn/20210328213156336.png#pic_center
[20210328213208701.png_pic_center]: https://img-blog.csdnimg.cn/20210328213208701.png#pic_center
[20210328213220722.png_pic_center]: https://img-blog.csdnimg.cn/20210328213220722.png#pic_center
[20210328213228196.png_pic_center]: https://img-blog.csdnimg.cn/20210328213228196.png#pic_center
[20210328213238466.png_pic_center]: https://img-blog.csdnimg.cn/20210328213238466.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20210328213250205.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20210328213300417.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/2021032821330969.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 8]: https://img-blog.csdnimg.cn/202103282133353.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 9]: https://img-blog.csdnimg.cn/20210328213344832.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 10]: https://img-blog.csdnimg.cn/20210328213404864.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 11]: https://img-blog.csdnimg.cn/20210328213419579.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[20210328213429206.png_pic_center]: https://img-blog.csdnimg.cn/20210328213429206.png#pic_center
[20210328213436367.png_pic_center]: https://img-blog.csdnimg.cn/20210328213436367.png#pic_center
[2021032821344983.png_pic_center]: https://img-blog.csdnimg.cn/2021032821344983.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5_size_16_color_FFFFFF_t_70_pic_center 12]: https://img-blog.csdnimg.cn/20210328213458891.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTUzOTQ5,size_16,color_FFFFFF,t_70#pic_center
[20210328213509810.png_pic_center]: https://img-blog.csdnimg.cn/20210328213509810.png#pic_center