实 验 报 告
试验项目名称 线性表的顺序存储
所属课程名称 实 验 类 型 试 验 日 期
学院：数学与信息科学学院 专业：信息与计算科学 班级：082班 姓名：李晓璐 学号：0801214037
实验 线性表的顺序存储结构上的操作
一、 实验目的
1、掌握用上机调试线性表的基本方法；
2、掌握线性表的顺序存储结构的基本操作，插入、删除以及有序表合并等运算在顺序存储结构上的运算。
二、实验环境
硬件：PC 微型计算机、256M以上内存，40G以上硬盘。
软件：Windows XP，Turbo C/C++
三、实验内容
线性表十二种基本操作的实现，其中线性表的插入、删除以及两个有序表的 合并操作在顺序存储结构上以如下形式体现：
当我们要在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表的第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若要删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。已知线形表La和Lb中的数据元素按值非递减排序.并归La和Lb得到新的线形表Lc,Lc的数据元素也按值非递减排序。可设两个指针i和j分别指向La和Lb中的某个元素，若i当前所指的元素为a，j当前所指的元素为b，则当前应插入到Lc中的元素为c。当a≤b时，c=a；当a>b时,c=b。显然，指针i和j的初值均为1，在所指元素插入Lc之后，在La或Lb中顺序后移。
四、实验步骤
1、本实验的程序如下
“function.h”
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define OK 1
#define ERROR 0
#define TURE 1
#define FALSE 0
#define OVERFLOW 0
#define INFEASIBLE 0
typedef int Status;
typedef int ElemType;
typedef struct{
ElemType *elem; int length; int listsize;
}SqList;
const int n=10;
“SqList.h”
Status InitList_Sq(SqList *L);
Status DestroyList(SqList *L);
Status ClearList(SqList *L);
Status ListEmpty(SqList *L);
int ListLength(SqList *L);
Status GetElem(SqList *L,int i,ElemType *e);
ElemType GetElem(SqList *L,int i);
int LocateElem(SqList *L,ElemType e,Status (*compare)(ElemType a,ElemType e));
Status PriorElem(SqList *L,ElemType cur_e,ElemType *pre_e);
ElemType PriorElem(SqList *L,ElemType cur_e);
Status NextElem(SqList *L,ElemType cur_e,ElemType *next_e);
ElemType NextElem(SqList *L,ElemType cur_e);
Status ListInsert_Sq(SqList *L,int i,ElemType e);
Status ListDelete_Sq(SqList *L,int i,ElemType *e);
ElemType ListDelete_Sq(SqList *L,int i);
void PrintSqList(SqList *L);
Status ListTraverse(SqList *L,Status (*visit)(ElemType *a));
Status EnterList_Sq(SqList *L);
Status compare(ElemType a,ElemType e);
Status visit(ElemType *a);
Status Union(SqList *La,SqList *Lb);
Status MergeList(SqList *La,SqList *Lb,SqList *Lc);
Status Sort_Increase(SqList *L);
Status Sort_Reduce(SqList *L);
“SqListOperation.h”
Status InitList_Sq(SqList *L)
{
}
Status EnterList_Sq(SqList *L)
{
int i,m; L->elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L->elem) exit(ERROR); L->length=0; L->listsize=LIST_INIT_SIZE; return OK;
ElemType *newbase;
cout<<"输入所需输入线形表元素的个数"<<endl; cin>>m;
newbase=(ElemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType));
if(!newbase) exit(OVERFLOW);//存储分配失败 L->elem=newbase;//新基址
L->listsize+=LISTINCREMENT;//增加存储容量 cout<<"依次输入所需元素:"<<endl;
for(i=0;i<m;i++) { } cin>>L->elem[i]; L->length++;
return OK;
}
Status DestroyList(SqList *L)
{
}
Status ClearList(SqList *L)
{
}
Status ListEmpty(SqList *L)
{
if(L->length==0) return TURE; L->length=0; return OK; free(L->elem); L->elem=NULL; L->length=0; L->listsize=0; return OK; else
} return FALSE;
int ListLength(SqList *L)
{
}
Status GetElem(SqList *L,int i,ElemType *e)
{
}
ElemType GetElem(SqList *L,int i)
{
ElemType e;
}
int LocateElem(SqList *L,ElemType e,Status (*compare)(ElemType a,ElemType e))
{
for(int i=0;i<L->length;i++)
}
{ } return ERROR; if((*compare)(L->elem[i],e)) return ++i; if(i<1||i>L->length){exit(ERROR);} e=L->elem[i-1]; return e; if(i<1||i>L->length){exit(ERROR);} e=L->elem+i-1; return OK; return L->length;
Status PriorElem(SqList *L,ElemType cur_e,ElemType *pre_e) {
int i=2; ElemType *p=L->elem+1; while(i<=L->length&&*p!=cur_e) { } if(i>L->length) {return INFEASIBLE;} else { p++; i++;
pre_e=--p;
return OK;
}
ElemType PriorElem(SqList *L,ElemType cur_e) {
int i=2; }
ElemType pre_e;
ElemType *p=L->elem+1; while(i<=L->length&&*p!=cur_e) { } if(i>L->length) {return INFEASIBLE;} else p++; i++;
{
pre_e=*--p;
return pre_e;
}
Status NextElem(SqList *L,ElemType cur_e,ElemType *next_e) {
int i=1; }
ElemType *p=L->elem;
while(i<L->length&&*p!=cur_e)
{
i++;
p++;
}
if(i==L->length||L->length==0)
return INFEASIBLE;
else
{
next_e=++p;
return OK;
}
ElemType NextElem(SqList *L,ElemType cur_e)
{
int i=1; }
ElemType *p=L->elem,next_e;
while(i<L->length&&*p!=cur_e)
{
i++;
p++;
}
if(i==L->length||L->length==0)
return INFEASIBLE;
else
{
next_e=*++p;
return next_e;
}
Status ListInsert_Sq(SqList *L,int i,ElemType e)
{
ElemType *p,*q,*newbase; }
if(i<1||i>L->length+1) return ERROR;//i值不合法
if(L->length>=L->listsize) {
newbase=(ElemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType));
} q=&(L->elem[i-1]); if(!newbase) exit(OVERFLOW); L->elem=newbase; L->listsize+=LISTINCREMENT;
for(p=&(L->elem[L->length-1]);p>=q;--p) *(p+1)=*(p);
}
Status ListDelete_Sq(SqList *L,int i,ElemType *e)
{ *q=e; ++L->length; return OK;
ElemType *p,*q;
if(i<1||i>L->length+1) return ERROR; p=&(L->elem[i-1]);
e=p;
q=&(L->elem[L->length-1]);
}
ElemType ListDelete_Sq(SqList *L,int i) {
ElemType *p,*q,e;
if(i<1||i>L->length+1) return ERROR; p=&(L->elem[i-1]);
e=*p; for(++p;p<=q;++p) *(p-1)=*(p); --L->length; return OK;
q=&(L->elem[L->length-1]);
}
void PrintSqList(SqList *L)
{
ElemType *p;
} p=L->elem; for(int i=1;i<=L->length;i++) { } cout<<endl; cout<<*p++<<" "; for(++p;p<=q;++p) *(p-1)=*(p); --L->length; return e;
Status ListTraverse(SqList *L,Status (*visit)(ElemType *a)) {
}
Status compare(ElemType a,ElemType e)
{
}
Status visit(ElemType *a)
{
return OK;
}
Status Union(SqList *La,SqList *Lb)
{
int La_len,Lb_len,i; if(a==e) { return OK; } else return ERROR; ElemType *p; int i; p=L->elem; for(i=0;i<L->length;i++) (*visit)(p++); cout<<endl; return OK;
ElemType e;
La_len=ListLength(La); Lb_len=ListLength(Lb); for(i=1;i<=Lb_len;i++)
} { e=GetElem(Lb,i); if(!LocateElem(La,e,compare)) { ListInsert_Sq(La,++La_len,e); } } return OK;
Status MergeList(SqList *La,SqList *Lb,SqList *Lc) {.
int i=1,j=1,k=1;
ElemType a,b;
InitList_Sq(Lc); while((i<=La->length)&&(j<=Lb->length)) { } a=GetElem(La,i); b=GetElem(Lb,j); if(a<=b) { } else { } ListInsert_Sq(Lc,k,b); ++j; ++k; ListInsert_Sq(Lc,k,a); ++i; ++k;
while(i<=La->length) {
a=GetElem(La,i);
} while(j<=Lb->length) { ListInsert_Sq(Lc,k,a); ++i; ++k;
b=GetElem(Lb,j);
}
Status Sort_Increase(SqList *L) {
int i,j; } return OK; ListInsert_Sq(Lc,k,b); ++j; ++k;
ElemType t;
for(i=0;i<L->length-1;i++) { for(j=0;j<L->length-i-1;j++) { if(L->elem[j]>L->elem[j+1]) {
t=L->elem[j];
L->elem[j]=L->elem[j+1]; L->elem[j+1]=t; }
} }
return OK;
}
Status Sort_Reduce(SqList *L) {
int i,j;
ElemType t;
for(i=0;i<L->length-1;i++) { for(j=0;j<L->length-i-1;j++) { if(L->elem[j]<L->elem[j+1]) {
t=L->elem[j];
} } L->elem[j]=L->elem[j+1]; L->elem[j+1]=t; }
return OK;
}
“SqListMain.cpp”
#include"iostream.h"
#include"malloc.h"
#include"stdlib.h"
#include"SqListOperation.h" #include"function.h"
#include "SqList.h"
void main()
{
SqList L1,L2,L3;
SqList *La=&L1,*Lb=&L2,*Lc=&L3;
ElemType e=3,*f=0;
int m; InitList_Sq(La);
InitList_Sq(Lb);
cout<<"输入表a"<<endl;
EnterList_Sq(La);
cout<<"输出表a"<<endl;
PrintSqList(La); cout<<"输出表a长:"<<ListLength(La)<<endl;
cout<<"检验表a是否空表(空为1,不空为0):"<<ListEmpty(La)<<endl;
cout<<"输入查询表a中元素的位置:"; cin>>m;
cout<<"输出线形表a中第m个元素:"<<GetElem(La,m)<<endl;
cout<<"输入查询其上个元素的元素:"; cin>>m;
cout<<"输出线形表a中第m个元素上个元素:"<<PriorElem(La,m)<<endl;
cout<<"输入查询其下个元素的元素:"; cin>>m;
cout<<"输出线形表a中第m个元素下个元素:"<<NextElem(La,m)<<endl;
cout<<"输入插入元素e及其位置m:"; cin>>m>>e; ListInsert_Sq(La,e,m); cout<<"输出插入元素后的表a:"<<endl;
PrintSqList(La);
cout<<"输入删除元素位置m:"; cin>>m;
cout<<"删除线形表a中第"<<m<<"个元素并输出其
值:"<<ListDelete_Sq(La,m)<<endl;
cout<<"输出删除元素后的表:"<<endl;
PrintSqList(La); cout<<"输入表b"<<endl;
EnterList_Sq(Lb);
cout<<"输出表b"<<endl;
PrintSqList(Lb); cout<<"给线形表La按递增排序并输出:"<<endl;
Sort_Increase(La);
PrintSqList(La); cout<<"给线形表Lb按递增排序并输出:"<<endl;
Sort_Increase(Lb);
PrintSqList(Lb); cout<<"把表a和表b按非递减排列归并到表c,并输出表c:"<<endl; MergeList(La,Lb,Lc);
PrintSqList(Lc);
cout<<"删除线形表Lc"<<endl;
ClearList(Lc);
DestroyList(Lc);
}
2、本程序运行的结果如下：
输入表a
输入所需输入线性表元素的个数
5
依次输入所需元素 cout<<"输出删除线形表Lc后的表长:"<<ListLength(Lc)<<endl;
39
74
24
63
99
输入表a
39 74 24 63 99
输出表a长：5
检验表a是否空表<空为1，不空为0>：0 输入查询表a中元素的位置：5
输出线性表a中第m个元素：99
输入查询其上个元素的元素：24
输出线性表a中第m个元素上个元素：74 输入查询其下个元素的元素：34
输入查询其下个元素的元素下个元素：74 输入插入元素e及其位置m：19
4
输出插入元素后的表a：
34 74 24 19 63 99
输入删除元素位置m：5
删除线性表a中第5个元素并输出其值：63 输出删除元素后的表：
34 74 24 19 99
输入表b
输入所需输入线性表元素的个数 3
依次输入所需元素：
2
71
14
输出表b
2 17 14
给线性表La按递增排序并输出：
19 24 34 74 99
给线性表Lb按递增排序并输出：
2 14 71
把表a和表b按非递减排列归并到表c，并输出表c：
2 14 19 24 34 71 74 99
删除线性表Lc
输出删除线性表Lc后的表长：0
五、实验小结
通过此次实验，使我更好的把握了线性表的顺序存储结构，更清楚的认识了线性表的十二种基本操作，特别是对线性表的插入删除操作以及两个有序表的合并有了更深刻的理解！