线性表的顺序存储结构算法

Ⅰ 什么是线性表线性表有哪两种存储结构它们是如何存储数据元素的各有什么优点

线性表：有n（n>0）的数据元素a1，a2，a3，.....，an组成的有限序列。

两种存储结构：

顺序存储结构：存取较快，插入删除较麻烦。

链式存储结构：存取较慢，插入删除叫简单。

存储数据元素：

顺序存储结构：直接存取。优点空间连续，位置明确。

链式存储结构：由于链表特征，需要从表头扫面。优点空间分散，位置不明确。

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的，注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表。

(1)线性表的顺序存储结构算法扩展阅读：

线性表中的个数n定义为线性表的长度，n=0时称为空表。在非空表中每个数据元素都有一个确定的位置，如用ai表示数据元素，则i称为数据元素ai在线性表中的位序。

线性表的相邻元素之间存在着序偶关系。如用（a1，…，ai-1，ai，ai+1，…，an）表示一个顺序表，则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。

当i=1,2，…，n-1时，ai有且仅有一个直接后继，当i=2，3，…，n时，ai有且仅有一个直接前驱。

Ⅱ 求数据结构试验 线性表的顺序存储结构

#include<iostream.h>
#include<stdlib.h>
#include <malloc.h>
#define OVERFLOW 0
#define OK 1
#define ERROR 0
#define LIST_INIT_SIZE 100//线性表存储空间的初始增量
#define LISTINCREMENT 10 // ?
typedef struct{
int * elem;// 存储空间基址
int length;//当前长度
int listsize;//当前分配的存储容量
}SqList;
SqList L;
int InitList_Sq(SqList & L){
//构造一个新的线性表。
L.elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int));
if(!L.elem)exit(OVERFLOW);//存储容量失败
L.length=0; //空表长度为0
L.listsize=LIST_INIT_SIZE;//存储初始容量
return OK;
}//InitList_Sq
int LIstInsert_Sq(SqList & L,int i,int e){
//在顺序线性表L中第i位置之前插入新的元素e
if(i<1||i>L.length+1) return ERROR;
if(L.length>=L.listsize){
int * newbase=(int *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));
if(!newbase)exit(OVERFLOW);
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
int * q=&(L.elem[i-1]);
for(int * p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;
*q=e;
++L.length;
return OK;
}
int ListDelete_Sq(SqList&L,int i,int &e)
{
if((i<1)||(i>L.length))return ERROR;
int *p=&(L.elem[i-1]);
e=*p;
int *q=L.elem+L.length-1;
for(++p;p<=q;++p)*(p-1)=*p;
--L.length;
return OK;
}
void main()
{
SqList L;
int i,n;
int e;
cout<<"输入顺序表的个数："<<endl;
cin>>n;
int *p=(int *)malloc(n*sizeof(int));
InitList_Sq(L);
cout<<"输入线性表"<<n<<"个元素的值"<<endl;
for(i=0;i<n;i++)
{
cin>>p[i];
L.elem[i]=p[i];
}
cout<<endl;
L.length=i;
cout<<endl;
cout<<"输入要插入元素的值"<<endl;
cin>>e;
cout<<endl;
cout<<"输入要插入的位置"<<endl;
cin>>i;
LIstInsert_Sq( L, i, e);
for(i=0;i<n+1;i++)
cout<<L.elem[i];
cout<<endl;
cout<<"输入要删除的位置"<<endl;
cin>>i;
ListDelete_Sq(L,i,e)
;for(i=0;i<n;i++)
cout<<L.elem[i];
free(p);