線性表的順序存儲結構演算法

Ⅰ 什麼是線性表線性表有哪兩種存儲結構它們是如何存儲數據元素的各有什麼優點

線性表：有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);