线性表的顺序存储结构实验报告样例.doc

上传人:jian****018 文档编号:8270998 上传时间:2020-03-28 格式:DOC 页数:11 大小:46.50KB
返回 下载 相关 举报
线性表的顺序存储结构实验报告样例.doc_第1页
第1页 / 共11页
线性表的顺序存储结构实验报告样例.doc_第2页
第2页 / 共11页
线性表的顺序存储结构实验报告样例.doc_第3页
第3页 / 共11页
点击查看更多>>
资源描述
年南昌航空大学实验报告(用实验报告纸,手写)课程名称: 数据结构 实验名称: 实验一 线性表的顺序存储结构 班 级: 080611 学生姓名: 赖凌 学号: 08061101 指导教师评定: 签 名: 题目:有两张非递减有序的线性学生表A,B,采用顺序存储结构,两张表合并用c表存,要求C仍为非递减有序的,并删除C中值相同的表。一、需求分析 本演示程序根据已有的6位学生的信息,实现两张表的合并及删除值相同元素的操作,不需要用户重新输入学生的信息。 在演示过程序中,用户敲击键盘,即可观看演示结果。 程序执行的命令包括:(1)构造线性表A (2)构造线性表B (3)求两张表的并 (4)删除C中值相同的元素二、概要设计 为实现上述算法,需要线性表的抽象数据类型:ADT Stack 数据对象:D=ai:|aiElemSet,i=1n,n0数据关系:R1=|ai-1,aiD,i=2,n0基本操作:init(list *L)操作结果:构造一个空的线性表L。ListLength(List *L)初始条件:线性表L已经存在操作结果:返回L中数据元素的个数。 GetElem(List L, int i, ElemType *e)初始条件:线性表L已经存在,1iListLength(&L)操作结果:用e返回L中第i个数据元素的值。EqualList(ElemType *e1,ElemType *e2)初始条件:数据元素e1,e2存在操作结果:以e1,e2中的姓名项作为判定e1,e2是否相等的依据。Less_EquaList(ElemType *e1,ElemType *e2)初始条件:数据元素e1,e2存在操作结果:以e1,e2中的姓名项(为字符串)的来判定e1,e2是否有的关系。LocateElem(List *La,ElemType e,int type)初始条件:线性表La已经存在操作结果:判断La中是否有与e相同的元素。MergeList(List *La,List *Lb,List *Lc)初始条件:非递减线性表La,Lb已经存在操作结果:合并La,Lb得到Lc,Lc仍按非递减有序排列。UnionList(List *La ,List *Lb)初始条件:线性表La,Lb已经存在操作结果:将所有在Lb而不在La中的元素插入到La中表尾的位置。PrintList(List L)初始条件:线性表L已经存在操作结果:打印出表L。ListInsert(List *L, int i, struct STU e)初始条件:线性表L已经存在,1iListLength(&L)+1操作结果:在表L中第i个位置前插入元素e,L的长度加1。 ADT List2. 本程序有三个模块: 主程序模块void main()初始化;接受命令;显示结果; 线性表单元模块:实现线性表抽象数据类型; 结点结构单元模块:定义线性表中的结点结构。三、详细设计元素类型,结点类型struct STUchar name20; /学生名字、学号、年龄、分数char stuno10;int age;int score;typedef struct STU ElemType; /元素类型struct LISTElemType *elem;int length; /表的长度、大小int listsize;typedef struct LIST list; /结点类型2.对抽象数据类型中的部分基本操作的伪码算法如下:int init(List *L)Lelem=(ElemType *)malloc(sizeof(ElemType)*LIST_INIT_SIZE);If(!Lelem) exit (OVERFLOW);Llength=0;Llistsize= LIST_INIT_SIZE;Return OK;/初始化表int ListLength(List *L)return Llength;/返回表长void GetElem(List L, int i, ElemType *e)*e=L.elemi; /返回元素int locateElem(List *La, ElemType e, int type)int I;switch(type) /确定元素在表中的位置case EQVAL;for(i=0;iLalength;i+)if(EqualList(&Laelemi,&e)return 1;break;default;break;return 0;void MergeList(List *La, List *Lb, List *Lc) /将两个表合并成LcElemType *pa,*pb,*pc,*pa_last,*pb_last;Pa=Laelem;pb=Lbelem; LcListsize=Lclength=Lalength+Lblength;Pc=Lcelem=(ElemType *)malloc(Lclistsize*sizeof(ElemType);if (!Lcelem) exit(OVERFLOW);pa_last=Laelem+Lalength-1;pb_last=Lbelem+Lblength-1;while (pa=pa_last&pb=pb_last)if (Less_EqualList(pa,pb) *pc+=*pa+;else *pc+=*pb+;while (pa=pa_last) *pc+=*pa+;while (pb=pb_last) *pc+=*pb+;void UnionList(List *La, List *Lb)La_len=ListLength(La);Lb_len=ListLength(Lb);For(i=0;iLb_len;i+)GetElem(*Lb,i,&e);If (!LocateElem(La,e,EQUAL)ListInsert(La,+La_len,e);int ListInset(List *L,int i,struct STU e) /将元素插入表中if(iLlength+1) return ERROR; q=&(Lelemi-1);for(p=LelemLlength-1;p=q;p-)*(p+1)=*p;*q=e;+(Llength);return OK;/ListInsert Before i3.主函数和其他函数的伪码算法void main()Initialization();/初始化ReadCommand(cmd);/读入一个操作符MakeList(La);printList(La);/产生并打印LaMakeList(Lb);printList(Lb);/ 产生并打印LbOperateList(La,Lb);void Initialization()/系统初始化clrscr();int ReadCommand(cmd)/任意键入一个字符cmd=getch();return 1;void MakeList(La)ListInsert(&La,i,e);void OperateList(La,Lb)MergeList(&La,&Lb,&Lc);UnionList(&La,&Lb);4 函数调用关系mainInitialization MakeList OperateList ReadCommand printList UnionList MergeListLess_EqualListInit ListInsert LocateElemEqualList四、调试分析 刚开始输入时,漏掉了一些变量参数的标记&,有的则错加了&,使得程序运行出来的结果不正确,使调试程序时费时不少。 程序采用逐个输入的方法创建La,Lb,在元素较多时,会使得程序很庞大,不利于检查错误等。 算法的时空分析各操作的算法时间复杂度比较合理init,ListLength,GetElem,EqualList,Less_EqualList为O(1)LocateElem,ListInsert,printList为O(n),UnionList为O(mn),MergeList为O(n)。4.本次实验采用数据抽象的程序设计方法,将程序化为三层次结构,设计时思路清晰,使调试也较顺利,各模块有较好的可重用性。五、用户手册 本程序的运行环境为windows xp操作系统,执行文件为Exp1Prb1.c; 进入演示程序后,完成编译,连接(即同时按下Ctrl F9)进入演示界面,用户键入任一符号,都能看完整个演示过程。六、测试结果(1)同时键入Ctrl F9,演示为:-List Demo is running-First is InsertList functionname stunoagescorestu1100001801000stu3100002801000(2)键入任意字符,演示为:name stunoagescorestu1100001801000stu3100002801000stu5100003801000List A length now is 3.(3)键入任意字符,演示为:name stunoagescorestu2100001801000stu4100002801000stu6100001801000List B length now is 3.(4)键入任意字符,演示为:name stunoagescorestu1100001801000stu2100001801000stu3100002801000stu4100002801000stu5100003801000stu6100001801000Second is UnionList function.Now union List A and List B.name stunoagescorestu1100001801000stu2100002801000stu3100003801000stu4100001801000stu5100002801000stu6100001801000List A length now is 6.(5) 键入任意字符,退出演示界面,回到编辑状态。七、附录:题一源程序/-头文件#include#include#include/符号常量#define ERROR O#define OK 1#define EQUAL 1#define OVERFLOW -1#define LIST_INIT_SIZE 100/线性表存储空间的初始分配量#define LISTINCREMENT 10/线性表存储空间的分配增量/类型声明struct STU/定义学生结构体类型,包括姓名,学号,年龄,成绩char name20;char stuno10;int age;int score;stu50;typedef struct STU ElemType;/用ElemType代替学生struct LIST/定义表LIST为结构体类型ElemType *elem;/存储空间基址int length;/当前长度int listsize;/当前分配的存储容量;typedef struct LIST List;/用list代表结构体LISTint init(List *L)/构造一个空的线性表Lelem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType);If (!Lelem) exit(OVERFLOW);/ 存储分配失败Llength=0;/空表长度为0Llistsize=LIST_INIT_SIZE;/初始存储容量Return ok;int ListLength(List *L)/求表L的长度return Llength;void GetElem(List L, int i, ElemType *e)*e=L.elemi;int EqualList(ElemType *e1,ElemType *e2)/以元素e1,e2中的姓名项是否相等作为判定e1,e2是否相等的标准if (strcmp(e1name,e2name)=0)return 1;elsereturn 0;int Less_EqualList(ElemType *e1,ElemType *e2)/以姓名(字符串)的作为判定e1e2的标准if (strcmp(e1name,e2name)=0)return 1;elsereturn 0;int LocateElem(List *La,ElemType e,int type)/判断La中是否有与e符合关系type的元素int i;suitch(type)case EQUAL;for(i=0;iLalength;i+)if (EqualList(&Laelemi,&e)return 1;break;default;break;return 0;void MergeList(List *La,List *Lb,List *Lc)/合并表La,Lb,用Lc存储。已知La,Lb元素值按非递减排列,Lc中值也按非递减排列ElemType *pa,*pb,*pc,*pa_last,*pb_last;pa=Laelem;pb=Lbelem;Lclistsize=Lclength=Lalength+Lblength;Pc=Lcelem=(ElemType *)malloc(Lclistsize*sizeof(ElemType);if (!Lcelem) exit(OVERFLOW);/存储分配失败pa_last=Laelem+Lalength-1;pb_last=Lbelem+Lblength-1;while(pa=pa_last&pb=pb_last)/合并,Lc元素按非递减排列if (Less_EqualList(pa,pb) *pc+=*pa+;else *pc+=*pb+;while (pa=pa_last) *pc+=*pa+ /插入La的剩余元素while (pb=pb_last) *pc+=*pb+ /插入Lb的剩余元素void UnionList(List *La ,List *Lb)/将所有在Lb中而不在La中的元素插入到La中int La_len,Lb_len;int i;ElemType e;La_len=Listlength(La);Lb_len=Listlength(Lb);/求线性表长度for(i=0;iLb_len;i+)GetElem(*Lb,I,&e);If (!LocateElem(La,e,EQUAL)ListInsert(La,+La_len,e);int printlist(List L)/输入表Lint i;printf(name stuno age scoren);for (i=0;iL.length;i+)printf(%-cos%st%dt%dn,L.elemi.name,L.elemi.stuno,L.elemi.age,L.elemi.score);printf(n);int ListInsert(List *L,int i,struct STU e)/在表L中第i位上插入estruct STU *p,*q;if (*iLlength+1) return ERROR;/i值不合法q=&(Lelemi-1);for(p=&LelemLlength-1;p=q;-p)*(p+1)=*p;*q=e;+Llength;return ok;mainstruct STU e;/定义结构体变量eList La,Lb,Lc;/定义结构体变量,即表La,Lb,LcClrscr();Printf(nn-List Demo is running -nn);Printf(First is InsertList function.n);init(&La);/创建一个新表Lastrcpy(e.name, stu1);strcpy(e.stuno, 100001);e.age=80;e.score=1000;ListInsert(&La,1,e);/在La的第1位上插入stu1的数据元素strcpy(e.name, stu3);strcpy(e.stuno, 100002);e.age=80;e.score=1000;ListInsert(&La,2,e);/在La的第2位上插入stu3的数据元素Printlist(La);/输出LaPrintf(List A length now is %d.nn,La.length);Getch();strcpy(e.name, stu5);strcpy(e.stuno, 100003);e.age=80;e.score=1000;ListInsert(&La,3,e);/在表La的第3位上插入stu5的数据表printlist(La);/输出表Laprintf(List A length now is %d.nn,La.length);getch();init(&Lb);/创建一张新表Lbstrcpy(e.name, stu2);strcpy(e.stuno, 100001);e.age=80;e.score=1000;ListInsert(&Lb,1,e);/在表Lb的第1位上插入stu2的数据strcpy(e.name, stu4);strcpy(e.stuno, 100002);e.age=80;e.score=1000;ListInsert(&Lb,2,e);/ 在表Lb的第2位上插入stu4的数据strcpy(e.name, stu6);strcpy(e.stuno, 100001);e.age=80;e.score=1000;ListInsert(&Lb,3,e);/ 在表Lb的第3位上插入stu6的数据printlist(Lb);/输出表Lbprintf(List B length now is %d.nn,Lb.length);getch();MergeList(&La,&Lb,&Lc);/合并表La,Lb,用表Lc存储(非递减有序)Printlist(Lc);/输出表Lcgetch();printf(Second is UnionList function.n );printf(Now Union List A and List B-n );UnionLIst(&La,&Lb);/合并La,Lb,并删除值相同的元素,用La存储Printlist(La);/输出LaPrintf(List A length now is %d.nn ,La.length);getch();
展开阅读全文
相关资源
正为您匹配相似的精品文档
相关搜索

最新文档


当前位置:首页 > 管理文书 > 工作总结


copyright@ 2023-2025  zhuangpeitu.com 装配图网版权所有   联系电话:18123376007

备案号:ICP2024067431-1 川公网安备51140202000466号


本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!