数据结构实验报告(2015级)及答案 《数据结构》实验报告
专 业 __信息管理学院______ 年 级 __2015级___________ 学 号 ___ _______ 学生姓名 ___ _ _______ 指导老师 ____________
华中师范大学信息管理系编 2
I 实验要求 1.每次实验中有若干习题,每个学生至少应该完成其中的两道习题。 2.上机之前应作好充分的准备工作,预先编好程序,经过人工检查无误后,才能上机,以提高上机效率。 3.独立上机输入和调试自己所编的程序,切忌抄袭、拷贝他人程序。 4.上机结束后,应整理出实验报告。书写实验报告时,重点放在调试过程和小节部分,总结出本次实验中的得与失,以达到巩固课堂学习、提高动手能力的目的。
II 实验内容 实验一 线性表 【实验目的】 1.熟悉VC环境,学习如何使用C语言实现线性表的两种存储结构。 2.通过编程、上机调试,进一步理解线性表的基本概念,熟练运用C语言实现线性表基本操作。 3.熟练掌握线性表的综合应用问题。 【实验内容】 1.一个线性表有n个元素(nMAXSIZE指线性表的最大长度),且递增有。现有一元素x要插入到线性表的适当位置上,并保持线性表原有 3
的顺序不变。设计程序实现。要求:采用顺序存储表示实现;采用链式存储表示方法实现;比较两种方法的优劣。 2. 从单链表中删除指定的元素x,若x在单链表中不存在,给出提示信息。 要求: ①指定的值x由键盘输入; ②程序能处理空链表的情况。 3.设有头结点的单链表,编程对表中的任意值只保留一个结点,删除其余值相同的结点。 要求: ①该算法用函数(非主函数)实现; ②在主函数中调用创建链表的函数创建一个单链表,并调用该函数,验证算法的正确性。 LinkedList Exchange(LinkedList HEAD,p) ∥HEAD是单链表头结点的指针,p是链表中的一个结点。本算法将p所指结点与其后 继结点交换。 {q=head->next; ∥q是工作指针,指向链表中当前待处理结点。 pre=head; ∥pre是前驱结点指针,指向q的前驱。 while(q!=null && q!=p){pre=q;q=q->next;} ∥ 4
未找到p结点,后移指针。 if(p->next==null)printf(“p无后继结点\n”); ∥p是链表中最后一个结点,无后继。 else∥处理p和后继结点交换 {q=p->next; ∥暂存p的后继。 pre->next=q; ∥p前驱结点的后继指向p的后继。 p->next=q->next;∥p的后继指向原p后继的后继。 q->next=p ;∥原p后继的后继指针指向p。 } }∥算法结束。 4.已知非空单链表第一个结点由head指出,请写一算法,交换p所指结点与其下一个结点在链表中的位置。 要求: ①该算法用函数Reverse(head,p)实现,其中head为表头指针,p指向要交换的结点; ②在主函数中调用创建链表的函数创建一个单链表,并调用该函数,验证算法的正确性。 5.设有一个单链表,编写能够完成下列功能的算法: ①找出最小值的结点,且打印该数值; ②若该数值是奇数,则将其与直接后继结点交换; ③若该数值是偶数,则将其直接后继结点删除。 5
要求: 编写主函数验证算法的正确性。 6.在一链表中,已知每个结点含有三个域:data、next和prior,其中prior域为空,设计一个算法,使每个结点的prior指向它的前驱结点,形成双向循环链表。 要求: ①建立一个结点中含有三个域的单链表; ②在主函数中调用此算法,构成双向循环链表; ③在主函数中利用正向和逆向两种方式输出链表中的数据,验证算法的正确性。 7.用链表建立通讯录。通讯录内容有:姓名、通讯地址、电话号码。 要求: ①通讯录是按姓名项的字母顺序排列的; ②能查找通讯录中某人的信息; 提示: 可用链表来存放这个通讯录,一个人的信息作为一个结点。成链的过程可以这样考虑:先把头结点后面的第一个数据元素结点作为链中的首结点,也是末结点。从第二个数据开始逐一作为‘工作结点’,需从链表的首结点开始比较,如果‘工作结点’的数据比链中的‘当前结点’的数据小,就插在其前面。否则,再看后面是 6
否还有结点,若没有结点了就插在其后面成为末结点;若后面还有结点,再与后面的结点逐一比较处理。
【实验报告】 实习时间:2016/10/14 实习地点: 实习机号: 7
具 体 实 验 内 容
作了1,2,3,4,5,6题 1题
采用顺序存储表示实现的算法:
主数: 运行结果: 8
算法代码: bool Insert_Sq(SqList &L,ElemType x) { int i; if(L.length>=L.listsize) { L.elem=(ElemType *)realloc(L.elem,(L.listsize+L.incrementsize)*sizeof(ElemType)); if(!L.elem) return false; L.listsize+=L.incrementsize; } for(i=L.length-1;x=0;i--) L.elem[i+1]=L.elem[i]; L.elem[i+1]=x; L.length++; return true; }
采用链表实现的算法: 9
主函数: 运行结果:
算法代码: void Insert_L(LinkList &L,ElemType x) { LinkList p,q,m; p=L->next; q=L; while(p) 10
{ if(x>p->data&&p->next) {p=p->next;q=q->next;} else if(x>p->data&&!(p->next)) {
m=(LinkList)malloc(sizeof(LNode)); m->data=x; p->next=m; m->next=NULL; return; } else { m=(LinkList)malloc(sizeof(LNode)); m->data=x; m->next=p; q->next=m; return; } } } 比较两种算法的优劣:顺序表和链表都要和x逐项比较,顺序表找到x应放的位置之后插入,后面的元素都要向后移位,但链表只需修改指针即可,链 11
表相对易操作一些 2题算法:
主函数: 代码: 12
void Delete_L(LinkList &L) { ElemType x; cout<<"请输入元素x:"; cin>>x; LinkList p,q; p=L; if(!(p->next)) { cout<<"链表不存在"
q=p->next; p->next=NULL; free(q); return; } p=p->next; } cout<<"x不存在" 3题 算法: 14 主函数: 运行结果: 算法代码: void DeleteRepeat_L(LinkList &L) { LinkList p,q,m; p=L->next; 15 while(p->next!=NULL) { q=p; while(q->next!=NULL) { if(q->next->data==p->data) { m=q->next; q->next=m->next; free(m); } else q=q->next; } p=p->next; } } 4题 算法: