線性表的順序存儲結構實驗

1. 數據結構實驗，線性表的順序存儲結構的實現

C++代碼編寫的

#include<iostream>
#include<string>
usingnamespacestd;
typedefintElemType;
typedefstructLNode
{
ElemTypedata;
structLNode*next;
}LinkList;
voidCreatListR(LinkList*&L,ElemTypea[],intn)
{
LinkList*s,*r;
inti;
//L=(LinkList*)malloc(sizeof(LinkList));
L=newLinkList();
r=L;
for(i=0;i<n;i++)
{
//s=(LinkList*)malloc(sizeof(LinkList));
s=newLinkList();
s->data=a[i];
好信r->next=s;
r=s;
}
r->next=NULL;
}
voidDispList(LinkList*L)
{
LinkList*p=L->next;
while(p!=NULL)
{
cout<<p->data<<"";
p=p->next;
}
cout<<endl;
}
intListInsert(LinkList*&L,inti,ElemTypee)
{
intj=0;
LinkList*p=L,*s;
while(j<i-1&&p!=NULL)
{
j++;
p=p->next;
}
if(p==NULL)
return0;
else
{
s=newLinkList();
s->data=e;
s->next=p->next;
p->next=s;
return1;
}
}
intListDelete(LinkList*&L,inti)
{
intj=0;
LinkList*p=L,*q;
while(j<i-1&&p!=NULL)
{
j++;
槐皮p=p->next;
}
if(p==NULL)
{
return0;
}
else
{
q=p->next;
if(q==NULL)
{
return0;
}
p->next=q->next;
inta=q->data;
free(q);
returna;
}
}
intmain()
{
LinkList*L,*L1;
鉛襪差inta[]={1,5,7,9,12,18,19,20,30,43,45,56,41,42,78};
intn=15,i,x,y,j;
CreatListR(L,a,n);
DispList(L);
cout<<"請輸入i"<<endl;
cin>>i;
cout<<"請輸入x"<<endl;
cin>>x;
ListInsert(L,i,x);
DispList(L);
cout<<"請輸入j"<<endl;
cin>>j;
y=ListDelete(L,j);
DispList(L);
cout<<y<<endl;
return0;
}

2. 求數據結構試驗 線性表的順序存儲結構

#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);

3. 綰挎ц〃鐨勯『搴忓瓨鍌ㄧ粨鏋

瀛樺偍鍗曞厓鍦板潃榪炵畫錛屽畠浠モ滅墿鐞嗕綅緗鐩擱偦鈥濇潵琛ㄧず綰挎ц〃涓鏁版嵁鍏冪礌闂寸殑閫昏緫鍏崇郴錛屽彲闅忔満瀛樺彇琛ㄤ腑浠諱竴鍏冪礌銆

欏哄簭琛ㄦ槸鍦ㄨ＄畻鏈哄唴瀛樹腑浠ユ暟緇勭殑褰㈠紡淇濆瓨鐨勭嚎鎬ц〃錛岀嚎鎬ц〃鐨勯『搴忓瓨鍌ㄦ槸鎸囩敤涓緇勫湴鍧榪炵畫鐨勫瓨鍌ㄥ崟鍏冧緷嬈″瓨鍌ㄧ嚎鎬ц〃涓鐨勫悇涓鍏冪礌銆佷嬌寰楃嚎鎬ц〃涓鍦ㄩ昏緫緇撴瀯涓婄浉閭葷殑鏁版嵁鍏冪礌瀛樺偍鍦ㄧ浉閭葷殑鐗╃悊瀛樺偍鍗曞厓涓銆

綰挎ц〃緇撴瀯鐗圭偣

1銆佸潎鍖鎬э紝鉶界劧涓嶅悓鏁版嵁琛ㄧ殑鏁版嵁鍏冪礌鍙浠ユ槸鍚勭嶅悇鏍風殑錛屼絾瀵逛簬鍚屼竴綰挎ц〃鐨勫悇鏁版嵁鍏冪礌蹇呭畾鍏鋒湁鐩稿悓鐨勬暟鎹綾誨瀷鍜岄暱搴︺

2銆佹湁搴忔э紝鍚勬暟鎹鍏冪礌鍦ㄧ嚎鎬ц〃涓鐨勪綅緗鍙鍙栧喅浜庡畠浠鐨勫簭鍙鳳紝鏁版嵁鍏冪礌涔嬪墠鐨勭浉瀵逛綅緗鏄綰挎х殑錛屽嵆瀛樺湪鍞涓鐨勨滅涓涓鈥滃拰鈥滄渶鍚庝竴涓鈥濈殑鏁版嵁鍏冪礌錛岄櫎浜嗙涓涓鍜屾渶鍚庝竴涓澶栵紝鍏跺畠鍏冪礌鍓嶉潰鍧囧彧鏈変竴涓鏁版嵁鍏冪礌(鐩存帴鍓嶉┍)鍜屽悗闈㈠潎鍙鏈変竴涓鏁版嵁鍏冪礌錛堢洿鎺ュ悗緇э級銆

4. 數據結構完整版實驗報告

(一)實驗目的和要求
實驗目的：熟練掌握線性表的基本操作在順序存儲結構上的實現。
實驗要求：任選一種高級程序語言編寫源程序，並調試通過，測試正確。

(二)實驗主要內容
1. 建立n個元素的順序表SqList，實現順序表的基本操作；
2. 在SqList的元素i之後插入一個元素，實現順序表插入的基本操作；
3. 在sqList中刪除指定位置i上的元素，實現順序表刪除的操作。
4.
(三)主要儀器設備
PC機，Windows XP操作平台，Visual C++

(四)實驗原理
順序表操作：定義一個順序表類，該類包括順序表的存儲空間、存儲容量和長度，以及構造、插入、刪除、遍歷等操作的方法

(五)實驗步驟與調試分析：
順序表操作：先構造有四個數據的順序表，在第4個位置插入9，再讀取並刪除第3個元素。

(六)實驗結果與分析：
順序表操作：

（七）附錄（源程序）：
#include<iostream>
using namespace std;

const int LIST_INIT_SIZE=10; //順序表初始長度
const int LISTINCREMENT=5; //順序表長度增值
class SqList
{
int *L; //定義存儲空間起始地址
int length; //順序表當前長度
int listsize; //順序表當前存儲容量
bool flag; //設立標志值記錄操作成敗
public:
SqList(int v1,int v2,int v3,int v4); //構造函數構造並初始化順序表
void ListInsert(int i,int e); //實現將e插入到順序表中第i個位置
void ListDelete(int i,int &e); //實現刪除順序表第i個元素
void ListVisit(); //實現順序表的遍歷
};
SqList::SqList(int v1,int v2,int v3,int v4) //構造並初始化順序表
{
L=new int[LIST_INIT_SIZE];
if(!L) //分配失敗
{
flag=false;
cout<<"ERROR"<<endl;
}
else //分配成功，進行初始化
{
*L=v1;
*(L+1)=v2;
*(L+2)=v3;
*(L+3)=v4;
length=4;
listsize=LIST_INIT_SIZE;
flag=true;
}
}
void SqList::ListInsert(int i,int e) //插入元素
{
int *p,*q;
int t;
if(i<1||i>length+1) cout<<"ERROR"<<endl; //插入位置錯誤
else
{
if(length==listsize) //空間不足，增加分配
{
p=new int[listsize+LISTINCREMENT];
if(!p) cout<<"ERROR"<<endl; //分配失敗
else //分配成功，復制順序表
{
for(t=0;t<length;t++)
*(p+t)=*(L+t);
q=L;L=p;p=q;
delete q;
listsize+=LISTINCREMENT;
}
}
for(t=length;t>=i;t--)
*(L+length)=*(L+length-1);
*(L+i-1)=e;
length++; //插入成功，表長加1
}
}
void SqList::ListDelete(int i,int &e)
{
if(i<1||i>length) cout<<"ERROR"<<endl; //刪除位置錯誤
else
{
e=*(L+i-1);
while(i<length)
{
*(L+i-1)=*(L+i);
i++;
}
length--; //刪除成功表長減1
}
}
void SqList::ListVisit() //遍歷
{
int i;
for(i=0;i<length;i++)
cout<<" "<<*(L+i);
cout<<endl;
}

int main()
{
int e=0;
SqList list(2,3,4,5);
list.ListVisit();
list.ListInsert(4,9);
list.ListVisit();
list.ListDelete(3,e);
list.ListVisit();
cout<<"e="<<e<<endl;
return 0;
}

5. 順序表的基本操作實驗總結

順序表的基本操作實驗總結：

順序表是在計算機內存中以數組的形式保存的線性表，線性表的順序存儲是指用一組地址連續的存儲單元依次存儲線性表中的各個元素、使得線性表中在邏輯結構上相鄰的數據元素存儲在相鄰的物理存儲單元中，

即通過數據元素物理存儲的相鄰關系來反映數據元素之間邏輯上的相鄰關系，採用順序存儲結構的線性表通常稱為順序表。順序表是將表中的結點依次存放在計算機內存中一組地址連續的存儲單元中。

將表中元素一個接一個的存入一組連續的存儲單元中，這種存儲結構是順序結構。採用順序存儲結構的線性表簡稱為「 順序表」。順序表的存儲特點是：只要確定了起始位置，表中任一元素的地址都通過下列公式得到：LOC（ai）=LOC（a1）+（i-1）*L 1≤i≤n

其中，L是元素佔用存儲單元的長度。如順序表的每個結點佔用len個內存單元，用location (ki)表示順序表中第i個結點ki所佔內存空間的第1個單元的地址。則有如下的關系:location (ki+1) = location (ki) +len