《数据结构》实验报告
专业:
学号:
姓名:
实验二线性表
【实验目的】
1.熟悉VC环境,学习如何使用C语言实现线性表的两种存储结构。
2.通过编程、上机调试,进一步理解线性表的基本概念,东运用C语言实现线性表基本操作。
3.熟练掌握线性表的综合应用问题。
【实验内容】
1、一个线性表有n个元素(n-MAXSIZE.MAXSIZE指线性表的最大长度),且递增有。
现有一元素x要插入到线性表的适当位置上,并保持线性表原有的顺序不变。
设计程序实现。
要求:采用顺序存储表示实现;采用链式存储表示方法实现:比较两种方法的优劣。
2.从单链表中删除指定的元素x,若x在单链表中不存在,给出提示信息。
要求:
①指定的值x由键盘输入;
②程序能处理空链表的情况。
3.设有头结点的单链表,编程对表中的任意值只保留一个结点,删除其余值相同的结点。
要求:
①该算法用函数(非主函数)实现;
②在主函数中调用创建链表的函数创建一个单链表,并调用该函数,验证算法的正确性。
LinkedList Exchange(LinkedList HEAD,p)
//HEAD是单链表头结点的指针,p是链表中的一个结点。
本算法将p所指结点与其后
继结点交换。
(q=head->next;//q是工作指针,指向链表中当前待处理结点。
pre=head;//pre是前驱结点指针,指向q的前驱。
while(q'=null &&q1=p)(pre=q;q=q->next;]/未到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.设有一个单链表,编写能够完成下列功能的算法:
①找出最小值的结点,且打印该数值;
②若该数值是奇数,则将其与直接后继结点交换;
④若该数值是偶数,则将其直接后继结点删除。
要求:
编写主函数验证算法的正确性。
6.在一链表中,已知每个结点含有三个域:data、next和prior,其中prior域为空,设计一个算法,使每个结点的prior指向它的前驱结点,形成双向循环链表。
要求:
①建立一个结点中含有三个域的单链表;
②在主函数中调用此算法,构成双向循环链表;
③在主函数中利用正向和逆向两种方式输出链表中的数据,验证算法的正确性。
7.用链表建立通讯录。
通讯录内容有:姓名、通讯地址、电话号码。
①通讯录是按姓名项的字母顺序排列的:
②能查找通讯录中某人的信息;
提示:
可用链表来存放这个通讯录,一个人的信息作为一个结点。
成链的过程可以这样考虑:先把头结点后面的第一个数据元素结点作为链中的首结点,也是末结点。
从第二个数据开始逐一作为‘工作结点”,需从链表的首结点开始比较,如果‘工作结点’的数据比链中的‘当前结点’的数据小,就插在其前面。
否则,再看后面是否还有结点,若没有结点了就插在其后面成为末结点:若后面还有结点,再与后面的结点逐一比较处理。