线性表操作

实验报告

院系名称：数学与信息学院

2011年10 月20 日

一、实验目的与任务：

1、掌握用VC++调试程序的基本方法；

2、掌握线性表的基本运算：初始化、遍历、插入、删除、

查找等在顺序存储结构上的实现方法；

二、实验涉及的相关知识点：

对线性表的建立，线性表的简单插入，删除。

三、实验内容与过程：

线性表的操作，怎样建立一个空的线性表，以及对线性表的查找，插入，删除等基本操作。

四、实验结果及分析：

在自己编写的过程中，才发现自己有很多的不足，程序中的许多内容都不够熟悉，而且出现很多编译问题，以至于大多数所编是参考的程序，自己还需要更加的努力，然后勤加练习。

五、实验相关说明：

注意头文件的正确书写，对数据结构语言的正确应用。注意线性表的非递减排列，以及存储地址。

六、实验有关附件（如程序、附图、参考资料，等）：

#include

#include

#include

#include

#define OK 1

#define ERROR 0

#define OVERFLOW -2

#define LIST_INIT_SIZE 100

#define LISTINCREMENT 10

typedef int ElemType;

typedef int Status;

class SqList

{

private:

ElemType *elem;

int length;

int listsize;

Status Initlist.Sq(Sqlist &L){

//构造一个空的线性表。

L.elem=(ElemType

*)malloc(LIST_INIT_SIZE*sizeof(ElemType));

if (!L.elem) exit(OVERFLOW); //存储分配失败L.length=0;//空表长度为0

L.listsize=LIST_INIT_SIZE;//初始存储容量Return OK;

}//Initlist.Sq

Destorylist.Sq(Sqlist&L)

{//销毁L.elem

free(L.elem);L.elem=NULL;

}//Destroylist.Sq

void ClearList.Sq(Sqlist &L)

{//置空表。

L.length=0;

}//Clearlist.Sq

Status ListInsert_Sq(Sqlist&L,int i,ElemType e)

{//1≤i≤L.length+1，在L的第i元之前插入值为e的元。

ElemType *newbase;

//ElemType *q,*p;

int j;

if (i<1||i>L.length+1) return ERROR;

if (L.length>=L.listsize)

{newbase=(ElemType

*)realloc(L.elem,(L.listsize+LISTINCREMENT)*s izeof(ElemT

ype));

if (!newbase) exit(OVERFLOW);

L.elem=newbase;L.listsize += LISTINCREMENT;} //增加储存容量

q=&(L.elem[i-1]);

//q为插入位置

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

//插入位置及之后的元素位移

*q=e;

//插入e

for(j=L.length;j>=i;j--) L.elem[j]=L.elem[j-1];

L.elem[i-1]=e;

++L.length;

//表长加1

return OK;

}//listinsert.Sq

int LocateElem_Sq(Sqlist L,ElemType e)

{//在线性表L中查找第1个值与e相等的元素。

int i=1;

while(i<=L.length && L.elem[i-1]!=e) ++i;

if (i<=L.length) return i;else return 0;

}//Locatelem.Sq

int ListLength_Sq(Sqlist&L)

{

return L.length;

}//ListLength.Sq

Status GetElem_Sq(Sqlist&L,int i,ElemType &e) {//1≤i≤L.length

//用e返回L中i个元素的值

if (i<1||i>L.length) return ERROR;

e=L.elem[i-1];

return OK;

}//Getelem.Sq

void ListTraverse_Sq(Sqlist&L)

{//输出L的全部元素的值

int i;

for (i=1;i<=L.length;i++) cout<

cout<<"\n";

}//output

}; //SqList

void un(SqList &La,SqList &Lb)

{int i,La_len,Lb_len; ElemType e;

La_len=ListLength(La);Lb_len=ListLength(Lb);

for (i=1;i<=Lb_len;i++)

{GetElem(Lb,i,&e);

if (!LocateElem(La,e)) ListInsert(&L,i,e);

}

}//union

void MergeList(List La,List Lb,List Lc){

//已知顺序线性表La和Lb的元素按值非递减排列

//归并La和Lb得到新的线性表Lc，并且Lc也非递减排列i=j=1;k=0;

ClearList(Lc);

La_len=ListLength(La);Lb_len=Listlength(Lb);

while((i<=La_len)&&(j<=Lb_len)){//La和Lb均非空GetElem(La,i,ai); GetElem(Lb,j,bj);

if (ai<=bj) {ListInsert(Lc,++k,ai);++i;}

else {ListInsert(Lc,++k,bj);++j}

}

while(i<=La_len)

{GetElem(La,i,ai); ListInsert(Lc,++k,ai);

}

while(j<=Lb_len)

{GetElem(Lb,j,bj); ListInsert(Lc,++k,bj);

}

}//Mergelist

void main()

{

int m,n,i;ElemType e;

List La,Lb,Lc;

cin>>m>>n;

for(i=1;i<=m;i++){cin>>e;ListInsert(La,i,e);}

for(i=1;i<=n;i++){cin>>e;ListInsert(Lb,i,e);}

MergeList(La,Lb,Lc);

un(La,Lb);

ListTraverse(La);

ListTraverse(Lb);

ListTraverse(Lc);

}

注：（1）第一部分由实验指导老师确定，学生填写；第二至六部分由学生整理完成，详细内容由实验学生附纸完成（包括电子版和书面版两个文档）；

（2）主要用于基础性、综合性和设计性实验；

（3）请各位指导老师务必指导学生认真填写。