数据结构与算法分析（1）顺序表的插入

数据结构与算法分析（1）顺序表的插入

关键思路： 1.FindPos函数寻找插入位置，使用for循环将原顺序表元素与插入元素做比较，从而找出插入位置。 2.将插入位置传入Insert函数，利用for循环将插入位置后的每一个元素向后移一位，从而空出插入位置L.[i]，而后将插入值e赋给L.[i]。最后顺序表长度L.length++，插入完成

具体代码实现如下：

C语言实现：

#include<stdio.h> #include<stdlib.h> #define InitSize 10//默认最大长度 typedef int Status; typedef struct{ int *data; int maxsize; int length; }SqList; Status Init_List(SqList &L) { L.data=(int *)malloc(InitSize*sizeof(int));//用malloc函数随机分配一片内存空间 L.length=0; L.maxsize=InitSize; } Status Insert(SqList &L,int a,int pos) { for(int i=L.length;i>=pos;i--) L.data[i+1] = L.data [i];//将插入位置后的每一个元素都后移一个位置 L.data[pos] = a; L.length++; } Status FindPos(SqList &L,int n,int m) { int pos=0; for(int i=0;i<n;i++) { if(m>=L.data[i]) pos++; } Insert(L,m,pos); } Status Scan(SqList &L) { int m,n; printf("Plz Enter the Number of Elements of Sqlist:"); scanf("%d",&n); printf("Plz Enter the Elements of Sqlist in order:"); for(int i=0;i<n;i++) { scanf("%d",&L.data[i]); L.length++; } printf("Plz Enter the Element that Insert:"); scanf("%d",&m); FindPos(L,n,m);//寻找插入位置 } Status Print(SqList &L) { for(int i=0;i<L.length;i++) { printf("%d",L.data[i]); } } int main() { SqList L; Init_List(L);//建立顺序表 int m; Scan(L);//键入需要插入的数字 Print(L);//打印顺序表 return 0; }

时间复杂度分析： T(n)=O(n); 在实际运用中可以添加一些代码以增强健壮性 1.在Scan函数中检验输入值的合法性。 2.在Init_List函数中若顺序表空间不足使用realloc函数分配空间。