1.什么是顺序存储结构

线性表的存储结构有顺序存储结构和链式存储结构两种。而我们把线性表的顺序存储结构称为顺序表。顺序表就是把线性表中的所有元素按照其逻辑顺序，依次存储到从指定的存储位置开始的一块连续的存储空间。

2.顺序存储结构的特点

（1）随机访问性

（2）占用连续的存储空间

（3）存储分配只能预先进行，即静态分配

3.顺序存储结构的实现

#define maxsize 100 typedef struct Sqlist{ int data[maxsize];//存放顺序表元素的数组 int length;//存放顺序表的长度 }Sqlist;

4.顺序表实现增删查

#include<stdio.h> #define maxsize 100 typedef struct Sqlist{     int data[maxsize];     int length; }Sqlist; //查找x的位置 int findElem(Sqlist l,int x){     int i;     for(i=0;i<l.length;i++){         if(x==l.data[i]){             return i;         }     }     return 0; } //在p位置上插入x int insertElem(Sqlist *l,int p,int x){     int i;     if(p<1 || p>l->length || l->length==maxsize-1){         return 0;     }     for(i=l->length;i>=p;i--){         l->data[i+1]=l->data[i];     }     l->data[p]=x;     ++(l->length);     return 1; } //删除p位置上的元素，将删除的值传递给e int deleteElem(Sqlist *l,int p,int *e){     int i;     if(p<1 || p>l->length || l->length==maxsize-1){         return 0;     }     *e=l->data[p];     for(i=p;i<l->length;i++){         l->data[i]=l->data[i+1];     }     --(l->length);     return 1; } void main(){     int i,j=0;     Sqlist l={{0,1,2,3,4,5,6},7};     //int position =findElem(l,3);     //printf("查询3的位置为：%d\n",position);     //int result=insertElem(&l,3,9);     deleteElem(&l,4,&j);     for(i=0;i<l.length;i++){         printf("%d\n",l.data[i]);     }     printf("删除元素为：%d\n",j); }结果：

查找：

插入：

删除：

5.计算题

题目：具有n个元素的顺序表，插入一个元素所进行的平均移动个数为多少？

解：

（1）求任一位置插入元素的概率

首先我们知道插入的位置是随机的，所以每个位置插入元素的可能性都是一样的。有n个插入位置，所以任一位置插入元素的概率为

p=1/n。

（2）求对应的每个插入位置需要移动的元素的个数

如果我们把新元素插入在表的第i个位置后，那么就需要将第i位置之后的元素向后移动一个位置。所以移动的元素个数为n-i。

所以

       n

E=p∑(n-i)=(n-1)/2

       1

所以插入的时间复杂度为O(n)。