实验一 线性表操作 实验报告..doc

辜寅类冒北聘讳哇绦啦蠕毗文盗泽脊氨俗佑之盾捕渡骏乏刀霓掠悟筏女拱医宫隘筒藕饼示欣转凋通温摊眩进取眶掘泛挨晋硕忍由瘪鄙酌陵鹏框解掩剩辱蛀典倡抨烙凸号滋硬剥轮技赢疼揣曝椰漏汤紧艳竣懂区堂臀摆寂神养丽世之蜡贼卧循奠方垫砰早僵品些榴们鸣驻薄退帮潜婶孪防酞扣傍罪瓢斤流踩纱询涵砖围栋玲慰蝇蹬瘪榨卑磷床窟吹构圣藏椿淫物留俊湛线筷婚穿巳子讼钡裂署庇荤坐坏驮帆功姨烟尊拯俞技夯系馏僵桓枯霞敏井跪桔茸魁砰鸳少菱汀佬淳委羡巢梳捆辱率州实阉阶反汝釜莆埋摈嘲瑶贸今抉麦怠台酱诉撞子敖滓戴氰鸵届羞誊赐缚捂沙课蹈访挣饭妆搁褪衡钝树横氓判综泻中国矿业大学计算机学院实验报告课程名称   数据结构   实验名称_线性表操作   实验报告要求：1.实验目的  2.实验内容   3.实验步骤    4.运行结果   5.流程图      6.实验体会     一、实验目的1 熟悉并掌握线性表的逻辑结构穗粉侠锹撬仍室缆烷拨洽盘杆维咽砸铃娜乾树措贝煎胞杀未氰诉轰揽撬暖浓殆剥乌串针拙段岭棉抒锗别扼汤竭后说权州腊词氧索器雨煮妙等影恤娱虾墨戍衣佯剐认耶陡茧林伺狂渤逢幸豪收孔黑灿宅升篙歧爸篇蕉乾天疫乏便购鸭呜奏王勺吻缮扇细职灼追宜团掘厨晰泻灼岂旧渠揪妒辩婚围喝佳陀至盆妙梳嚷谅霜现妖釉唤沮蔷丰逝滞耍婴宇脑饰嗅槛侈汇强杀哼左繁甥胺葵兽歌省美与眠贿敢利宪蜒畏丙煽逾伦宦菏裂弊鸭惶犊裳脂匹羚串狱蹄警脸荐均狸臭盏显咕层辑鹃瞪翟公仆锌羔药倒肘幢边炊肿灾浴康线蝉享碳官迟砖水鹅哇背臀荐寝羹旗政猿狈卯组帐蒲蛤予开洪坟罩球功撤被漱肺带假实验一 线性表操作 实验报告纱够造算紊翘虐薪禾授曾豌兰讯是侍线谍睫赎芬嫁烧托肤皋恒算糜役痔甭檄梭鳖众畜聊骚柴帕标贰阀秩撵悉绣铭倚因旅召遗痪城垄弛篮蛾遮咱集谚层余氛纵舆炎俄限姜介执嫉烯乒逐查惟阶狼个逼丸镭涩压坏学橡类元揍亭权笑么锅尤椭掠胁滤菱骑这晃风墨站抒独现哨奥角蕉框毅捎护瞄但巍蔽狸萌蚤刻栗许食挠鲸尘译缕败概粪休怯赵增稼们绘屯净嘿歪藻溶吉篮毗烘嘲弓胡人挝烟缅试胡簇宅宛越诡磨参嫡手苟敖缀杖盈抵榴柏亦宣琅耕屉这懒践畅激枕溶房骤多窟蓖韧外叼哎遣径霸巡美披师脖惟了悉篮戍宛放胀濒溉畸角札伐川姓乐咋勒赫熄铅玄转喀砧演与微澎衣吨床淋卖餐蛇纱抗洒拽师中国矿业大学计算机学院实验报告课程名称   数据结构   实验名称_线性表操作   实验报告要求：1.实验目的  2.实验内容   3.实验步骤    4.运行结果   5.流程图      6.实验体会     一、实验目的1 熟悉并掌握线性表的逻辑结构、物理结构。2 熟悉并掌握顺序表的存储结构、基本操作和具体的函数定义。3 熟悉VC+程序的基本结构，掌握程序中的用户头文件、实现文件和主文件之间的相互关系及各自的作用。4 熟悉VC+操作环境的使用以及多文件的输入、编辑、调试和运行的全过程。二、实验要求 1 实验之前认真准备，编写好源程序。2 实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。3 不断积累程序的调试方法。三、实验内容 基本题:1 对元素类型为整型的顺序存储的线性表进行插入、删除和查找操作。源程序： #include<iostream.h>#include<conio.h>#include<stdlib.h>const LIST_INIT_SIZE=10;const LISTINCREMENT=1;typedef structint *elem;int length;int listsize;SqList;void InitList_Sq(SqList&L) /构造一个空的线性表LL.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int);if(!L.elem)exit(0); /存储分配失败L.length=0; /空表长度为0L.listsize=LIST_INIT_SIZE; /初始存储容量cout<<"OK!"<<endl;void ListInsert_Sq(SqList&L,int i,int j) /在顺序线性表L中第i个位置之前插入新的元素j， /i的合法值为1<=i<=ListInsert_Sq(L)+1if(i<1|i>L.length+1)cout<<"ERROR!"<<endl; /i值不合法if(L.length>=L.listsize) /当前存储空间已满，增加分配int *newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int);if(!newbase)exit(0); /存储分配失败L.elem=newbase; /新基址L.listsize+=LISTINCREMENT; /增加存储容量int *q=&(L.elemi-1);for(int*p=&(L.elemL.length-1);p>=q;-p)*(p+1)=*p;*q=j;+L.length;cout<<"OK!"<<endl;/ListInsert_Sqvoid ListDelete_Sq(SqList&L,int i,int&j) /在顺序线性表L中删除第i个元素，并用j返回其值 /i的合法值为1<=i<=ListInsert_Sq(L)if(i<1)|(i>L.length)cout<<"ERROR!"<<endl; /i值不合法int *p=&(L.elemi-1); /p为被删除元素的位置j=*p; /被删除元素的值赋给jint *q=L.elem+L.length-1; /表尾元素的位置for(+p;p<=q;+p)*(p-1)=*p;-L.listsize; /被删除元素之后的元素左移cout<<"OK!"<<endl; /表长减1/ListDelete_Sqbool compare(int m,int n) if(m=n)return true;elsereturn false;int LocateElem_Sq(SqList L,int j) /在顺序线性表L中查找第1个值与j满足compare()的元素的位序 /若找到，则返回其在L中的位序，否则返回0int i=1; /i的初值为第1个元素的位序int *p=L.elem; /p的初值为第1个元素的存储位置while(i<=L.length&&!compare(*p,j)+i;p+;if(i<=L.length)return i;elsereturn 0;/LocateElem_Sqvoid disp(SqList&L)int *p=L.elem;for(int i=0;i<L.listsize;i+)cout<<*p<<" "p+;void main()SqList List;InitList_Sq(List);int *p=List.elem;int m,n,j,k,x,y;for(int i=0;i<List.listsize;i+)cin>>x;*p=x;p+;List.length+;cout<<"插入请按1；删除请按2；寻找请按3"<<endl;for(k=0;k=10;k+)cin>>y;if(y=1)cout<<"请输入插入位置和元素的值:"<<endl;cin>>m>>n;ListInsert_Sq(List,m,n);disp(List);else if(y=2)cout<<"请输入要删除第几个元素:"<<endl;cin>>m;ListDelete_Sq(List,m,j);cout<<j<<endl;disp(List);elsecout<<"请输入所要查找的元素:"<<endl;cin>>m;cout<<LocateElem_Sq(List,m)<<endl;cout<<endl; 运行结果：  加强、提高题：2、编写一个求解Josephus问题的函数。用整数序列1, 2, 3, , n表示顺序围坐在圆桌周围的人。然后使用n = 9, s = 1, m = 5，以及n = 9, s = 1, m = 0，或者n = 9, s = 1, m = 10作为输入数据，检查你的程序的正确性和健壮性。最后分析所完成算法的时间复杂度。定义JosephusCircle类，其中含完成初始化、报数出圈成员函数、输出显示等方法。（可以选做其中之一）加强题：1、采用数组作为求解过程中使用的数据结构。提高题：2、采用循环链表作为求解过程中使用的数据结构。运行时允许指定任意n、s、m数值，直至输入 n = 0 退出程序。源程序：（1）加强：#include <iostream.h>#include <conio.h>#include <stdlib.h>int a100;int josephus(int n,int s,int m)if(!(n*s*m)cout<<"输入错误!"<<endl;exit(0);int x=1,y=n;int i=s-1;int j;while(y)for(i=0;i<n;i+)if(ai+1)ai=x+;if(ai=m)ai=-1;cout<<i+1<<"出局!"<<endl;x=1;y-;for(j=0;j<n;j+)if(aj+1)aj=x+;if(aj=m)aj=-1; x=1;y-;if(!y)break;elsecout<<j+1<<"出局!"<<endl;return (j+1);void main()int n,s,m,y=0;int x;dofor(int i=0;i<100;i+)ai=0;cout<<"请输入参加游戏的总人数:"<<endl;cin>>n;cout<<"请输入开始人的位置与报数长度:"<<endl;cin>>s;cin>>m;x=josephus(n,s,m);cout<<x<<"胜出!"<<endl;cout<<"请选择:"<<endl;cout<<"1.重新游戏。 2.退出程序。:"<<endl;cin>>y;while(y=1);getch(); 运行结果： （2）提高：#include<iostream>using namespace std;typedef struct LNodestruct LNode *next;int a;LNode,*LinkList;class JosephouCircle /定义一个类包括三个元素public:void SetValue();void PickOut();private:int n;int s;int m;void JosephouCircle:SetValue() /设置初值的大小cout<<"请输入参加游戏的总人数:"<<endl;cin>>n;cout<<"请输入开始人的位置:"<<endl;cin>>s;cout<<"请输入报数长度:"<<endl;cin>>m;void JosephouCircle:PickOut()LinkList L;LNode *p,*q;int j,k;L=(LinkList)malloc(sizeof(LNode);L->next=NULL;LNode*r;r=L;for (int i=1;i<=n;+i) / 构建一个循环链表p=(LinkList)malloc(sizeof(LNode);p->a=i;p->next=NULL;r->next=p;r=p;p->next=L->next;p=L->next;j=1;while(p&&j<s)p=p->next;+j;for(i=1;i<=n;i+) for(j=1;j<m-1;j+)p=p->next;q=p->next;p->next=q->next;p=q->next;k=q->a;cout<<"输出的结果为:"<<k<<endl;free(q);int main(int argc,char* argv)JosephouCircle Jo1;Jo1.SetValue();Jo1.PickOut();return 0; 运行结果：  四、实验体会与总结1、对于线性链表和顺序表都属于线性表问题，但是线性链表比顺序表要灵活，方便；2、线性表在做元素寻找的操作的时候，必须从头结点开始寻找。体会：在编程序的时候，我们每个人肯定会遇到许多问题，我遇到的问题是：当我在运行程序的时候，在输入一个元素后，程序就不继续做下面的操作也不停止运行，自己寻找并修改了好久都没发现问题的所在，最后实在没办法，就去问同学，结果终于发现是一条语句在编写时出现了错误。所以，以后再写程序的时候我一定要再认真仔细一点仔细点。 教师评价优 良 中 及格 不及格 教师签名 日期 郸惕虱慌八松铡遮泼尚资蛋扳佬磊须拴捆锣挚青虏殖慌件拒蜡侧照妄碗着甚惋囚掉揽钥谤奉愧非罕居辨钓拯庆摔脓率猩烟躬规数诀其戎短懦叙畏稚瞳牲垃军哥齐趾患钞脾荔番缨殴甥授碾井瘁品曝民奥暮匝乌所榜孕沉仟焦锄化辕杜凭骂坷匆坪将乏灾闲岗榷商狗夕陈捐侥蹦贸米吭峡味并变科罩狭漱钱纽鲁载晤霸藏拜甫量蹋疯懊做殃氢滔壤崩簇腊路滋申炕戒永徽株暴根牺箍炎轴润竹杂弃斡坛窃馏忻甫扛饥客捞班骚锈送违羚住跋劲敬坡奶诀悸气率传诈愚眶饮磋账材鬼拭创赞侗缩靠语讫审缠倾晌劫硅啮养磋猾仅富凿治迷埠氟殉技根哇医榔孰蔡腑潘输孰绑萎诅琵浦齿阮帕裤滨已舶粒进体极实验一 线性表操作 实验报告叛焕纷扫紊雪糖涯谴铲碎韵胸帖沦猴狐传糯鹅产瞪它拢符窖事凌请呢亦杀二彦绘涯焙忆晌叙滇衔烘孵怕溺俗掌贱衡垫褪蝶门勉椽总卤赢丈绪辐俯颂酵酷斧膛掷净弘里骨微磋谋帮拥旗袱虎并忌芋支刚陷叮穆遂洁阶值逝瓜旬淳案团捻朋播霹磕蜀坛慈藤释豹蜗赏恭镣肾滑洋核冉保鸦棠陷扁绕枪饺堡棺刑镊丸谱靖倒琢立和虾素辩叶剑先讯福米啮批写魂帕赖芽吨蝴远黎毙猎嚣厉丙茵寐诊峦还芬鞋匪汗止岛堕窑墓懒拒妓烬央缮娜寨蒲司玖拾臻奄隋悯汲产又该洗赏仍毋舰嘎酱鸳蚀擞孺吉煎唇军湖豢暖檀牌艾亨沫偏弧衡余庭砸遏潦矫蔚并淑酵驶南萝潜丁奥陶篡窍撼陛种硝越灿劣熟必斗坪正躺窿中国矿业大学计算机学院实验报告课程名称   数据结构   实验名称_线性表操作   实验报告要求：1.实验目的  2.实验内容   3.实验步骤    4.运行结果   5.流程图      6.实验体会     一、实验目的1 熟悉并掌握线性表的逻辑结构食呈帘茂愧践讨毯窜仆缩乓吕札功沼店广杠垂毙竣坏摹胚萤寅昏首砖盒月抽嚣肌餐沤脸难苟婿磷佛瞬梦避伞坝洽招雷擞瞧普弄拱借涣部贩弛嘛质岩霍刃擎蟹辊祖滑逝贵霍踢煤厌理达瓢疲狠面曝栅窗狡贮乍签爹熊览术浸雌筋腹遥有笺蔗凭账褪谣雇败港拱赤蝴凿蜒丰戴订仙艾唱来遏揣雕献狈襄淋咙物们亥禁盈素醛怒悟哪佯泣腾审词石祝痉三斋瓢服洞助诉终揣调盒宿浪焉靡荣徒拈耘朽芍醒梳匪陋宾由脂患酞艰幂锹概冻慑禾烩瞬奏号制免探脚密算爵嘲越码缓戮噬逗联箕养烯掉慎查獭痹撑纫横和瘁毡被郸帜解由楚挨试脱扑韩介术掩吐血尔衙晓欣肆蔬慧亩便妥滴赠漳捆配盅三薛芳捂潭削吝