顺序表的基本操作（1）——插入操作

顺序表的插入运算

线性表的插入运算是指在表的第i (1≤i≤n+1)个位置，插入一个新元素x，使长度为n的线性表 ( a1​，…，ai−1​，ai​，…，an​) 变成长度为n+1的线性表( a1​，…，ai−1​，x，ai+1​，…，an​) 。

算法思想：用顺序表作为线性表的存储结构时，由于结点的物理顺序必须和结点的逻辑顺序保持一致，因此我们必须将原表中位置n-1，n-2，…，i-1上的结点，依次后移到位置n，n-1，…，i上，空出第i-1个位置，然后在该位置上插入新结点x。当i=n+1时，是指在线性表的末尾插入结点，所以无需移动结点，直接将x插入表的末尾即可。

算法分析：

1. 最好的情况：当i=n+1时（插入尾元素），移动次数为0；
2. 最坏的情况：当i=1时（插入第一个元素），移动次数为n；
3. 平均情况：在位置i插入新元素x，需要将ai～an的元素均后移一次，移动次数为n-i+1。假设在等概率下pi（pi=1/(n+1)），移动元素的平均次数为：

   

插入算法的主要时间花费在元素移动上，所以算法平均时间复杂度为O(n)。

编程要求

根据提示，在编辑器 Begin-End 区间补充代码，完成顺序表的初始化操作，遍历操作及插入操作三个子函数的定义，具体要求如下：

• void InitList(SqList &L); //构造一个空的顺序表L
• void DispList(SqList *L);// 输出顺序表L的每个数据元素
• int ListInsert(SqList *&L,int i,ElemType e)；//在顺序表L中第i个位置之前插入新的数据元素

测试说明

第一组测试输入：
5

12 47 5 8 69
1

99

第二组测试输入：
3

1 2 3
6

5

代码文件

#include <stdio.h>
#include <malloc.h>
#define MaxSize 50
typedef int ElemType;
typedef struct
{
	ElemType elem[MaxSize];
   	int length;
} SqList;

void DispList(SqList *L);
void InitList(SqList *&L);
int ListInsert(SqList *&L,int i,ElemType e);
int ListEmpty(SqList *L);



int main()               //main() function 
{	// 调用对应的函数，完成顺序表的插入功能 	
    /********** Begin **********/ 
	SqList *L;
	ElemType e;int M,i;
	printf("(1)初始化顺序表L\n");
	InitList(L);
	printf("(2)输入顺序表的长度M:\n");
	scanf("%d",&M);
	printf("(3)依次插入M个元素\n");
	for(i=1;i<=M;i++)
	{
		scanf("%d",&e);
		ListInsert(L,i,e);
	}
	printf("(4)输入要插入元素的位置\n");
	scanf("%d",&i);
	printf("(5)输入要插入的数据元素的值:\n");
	scanf("%d",&e);
	if(ListInsert(L,i,e)==1){
		printf("(6)输出插入后的顺序表:");
		DispList(L);
	}
	else
	printf("(6)位置不合理，无法插入");
	/********** End **********/
     
}


/*****顺序表的基本操作*****/


void InitList(SqList *&L)
{	// 操作结果：构造一个空的顺序线性表L 	
    /********** Begin **********/ 
	L=(SqList*)malloc(sizeof(SqList));
	L->length=0;
	

	/********** End **********/
}


int ListInsert(SqList *&L,int i,ElemType e)
{	// 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1
	// 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
	/********** Begin **********/ 
	if(i<1||i>L->length+1){
		return 0;
	}
	i--;
	int j;
	for (j=L->length;j>i;j--)
	    L->elem[j]=L->elem[j-1];
	L->elem[i]=e;
	L->length++;
	return 1;
	


	
	/********** End **********/
}

void DispList(SqList *L)
{ 	// 初始条件：顺序线性表L已存在
	// 操作结果：依次对L的每个数据元素调用函数vi()输出	
    /********** Begin **********/ 
	 int i;  
     if (ListEmpty(L)) return;  
     for (i=0;i<L->length;i++)  
        printf("%d ",L->elem[i]);  
     printf("\n"); 
    
	
	/********** End **********/
}
int ListEmpty(SqList *L)
{
	return(L->length==0);
}