线性表的实现

实验报告

一、实验序号：实验二（1）

二、实验名称：线性表的顺序实现

三、实验内容：实现线性表的顺序存储结构

四、实验要求：编制并调试出三个文件，实现线性表的各种操作，对输入的数据能够正确运行并得出相应结果。五、程序清单： ⒈ 头文件

//头文件linearlist．h //定义ElemType为int类型 typedef int ElemType; //线性表顺序存储类型 struct LinearList {

ElemType *elem; //存线性表元素 int length; //存线性表长度 int listsize; //存elem数组长度 };

//初始化线性表

void InitList(LinearList &L,int ms); //清空线性表

void ClearList(LinearList &L); //求线性表长度

int ListSize(LinearList L); //检查线性表是否为空

bool ListEmpty(LinearList L); //检查线性表是否为满

bool ListFull(LinearList L); //整体赋值

void Assume(LinearList &L1,LinearList &L2); //遍历线性表

void TraverList(LinearList L); //从线性表中查找元素

bool FindList(LinearList &L,ElemType &item); //更新线性表中的给定元素

bool UpdateList(LinearList L,int mark,const ElemType &item); //向线性表插人元素

bool InsertList(LinearList &L,const ElemType &item,int mark); //从线性表中删除元素

bool DeleteList(LinearList &L,ElemType &item,int mark); //对线性表进行有序输出

void OrderOutputList(LinearList L,int mark);

⒉ 实现文件

#include #include #include\"linearlist.h\" #define LIST_INIT_SIZE 100 //初始化线性表

void InitList(LinearList &L,int ms) {

L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));

if (!L.elem) cout<<\"ERROR!\"<L.length=0; L.listsize=ms; }

//清空线性表

void ClearList(LinearList &L) {

L.length=0; }

//求线性表长度

int ListSize(LinearList L) {

return L.length; }

//检查线性表是否为空

bool ListEmpty(LinearList L) {

if(L.length==0) return true; else

return false; }

//检查线性表是否为满

bool ListFull(LinearList L) {

if(L.listsizereturn true; }

//整体赋值

void Assume(LinearList &L1,LinearList &L2) {

L1.length=L2.length;

for(int i=0;iL1.elem[i]=L2.elem[i]; } }

//遍历线性表

void TraverList(LinearList L) {

for(int i=0;icout<cout<//从线性表中查找元素

bool FindList(LinearList &L,ElemType &item) {

for(int i=0;ireturn true; }

return false; }

//更新线性表中的给定元素

bool UpdateList(LinearList L,int mark,const ElemType &item) {

if(L.elem [mark]=item) return true; else

return false; }

//向线性表插人元素

bool InsertList(LinearList &L,const ElemType &item,int mark) {

int *newbase,*p,*q;

if(mark<0||mark>L.length) return false; if(L.length>=L.listsize)

{

newbase=(ElemType*)realloc(L.elem,(L.listsize+50)*sizeof(ElemType));

if(!newbase) cout<<\"ERROR\"<q=&(L.elem[mark]);

for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; *q=item; L.length++; return true; }

//从线性表中删除元素

bool DeleteList(LinearList &L,ElemType &item,int mark) {

int *p,*q;

if(mark<0||mark>L.length) return false; p=&(L.elem[mark]); item=*p;

q=L.elem+L.length-1; for(++p;p<=q;++p) *(p-1)=*p; L.length--; return true; }

//对线性表进行有序输出

void OrderOutputList(LinearList L,int mark) {

ElemType x;

for(int j=0;jfor(int i=0;iif(L.elem[i]>L.elem[i+1]) {

x=L.elem[i];

L.elem[i]=L.elem[i+1]; L.elem[i+1]=x; } }

cout<<\"将线性表有序输出为：\"; TraverList(L); }

⒊ 主文件

#include #include\"linearlist.h\" int main() {

LinearList L1; LinearList L2;

InitList(L1,100);//初始化线性表 InitList(L2,100); int n;

cout<<\"请输入线性表长度：\"; cin>>n;

cout<<\"请输入线性表\"<cin>>L1.elem[i]; L1.length++; }

cout<<\"线性表长度为：\"<cout<<\"线性表是否为空(1为空)\"<<\" \"<cout<<\"线性表是否为(1为满))\"<<\" \"<Assume(L2,L1);//整体赋值 cout<<\"线性表L2为\"<ClearList(L1);//清空线性表L1 cout<<\"清空后线性表L1为\"<ElemType x;//查找

cout<<\"请输入需要查找的元素\"; cin>>x;

cout<<\"是否找到待查找的元素(1为找到)\"<ElemType y;//更新 int z;

cout<<\"请输入待更新的元素\"; cin>>y;

cout<<\"请输入需要更新的元素的位置：\"; cin>>z;

cout<<\"是否更新成功(1为成功)\"<int m,a;//插入

cout<<\"请输入需要插入的元素的位置：\"<<\" \"; cin>>m;

cout<<\"请输入需要插入的元素：\"<<\" \"; cin>>a;

InsertList(L2,a,m);

cout<<\"线性表L2为\"<int b,c=0;//删除

cout<<\"请输入需要删除的元素的位置：\"<<\" \"; cin>>b;

DeleteList(L2,c,b);

cout<<\"被删除的元素为:\"<cout<<\"删除第\"<OrderOutputList(L2,n);//有序输出 return 0; }

六、调试情况与运行结果

第一步输入线性表长度为10

第二步对线性表初始化并赋值1 3 5 7 9 2 4 6 8 10 第三步判断线性表是否为空是否为满 第四步清空线性表

第五步查找和更新元素6和11 第六步复制并输出

第七步在第5个位置插入13并输出 第八步在第7个位置删除4并输出 第九步将线性表有序输出 七、实验体会

1.对于线性表，我们刚开始接触，在心理上有些畏惧，很多问题不敢下手； 2.重新温习了已经学过的C语言和C++的知识,如动态分配数据空间,指针,数组,排序等问题；

3．用多文件保存很方便

4.对线性表有了进一步的掌握

5.线性表的实验对以后的实验奠定了一定的基础

6.只要细心、耐心的做，总会有收获，要锲而不舍，持之以恒，才会成功！ 八、本次分工：

成绩等第：

教师签名： 批阅日期：