数据结构实验指导.pdfVIP

《数据结构》

实

验

指

导

计算机科学与技术教研室

2009年2月

实验一线性表（2学时）

一．目的与要求

本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式

存储结构上的实现，提高分析和解决问题的能力。要求仔细阅读并理解下列例题，上机通过，

并观察其结果，然后独立完成后面的实习题。

二．实验内容

[问题描述]

用链表形式存储一个字符串，插入、删除某个字符，最后按正序、逆序两种方式输出字

符串。

[输入]

初始字符串，插入位置，插入字符，删除字符。

[输出]

已建立链表（字符串），插入字符后链表，删除字符后链表，逆转后链表。

[存储结构]

采用链式存储结构

[算法的基本思想]

建立链表：当读入字符不是结束符时，给结点分配存储空间，写数据域，将新结点插到

表尾；插入字符：根据读入的字符在链表中找插入位置，将新结点插入到该位置之前；删除

字符：根据读入的删除字符在链表中找到被删结点后，将其从链表中删除；链表逆转：从链

表的第一个结点开始对所有结点处理，将每个结点的前驱变为它的后继；打印链表：从链表

的第一个结点开始，依次打印各个结点的数据域。

三．实验要求：

在上机后写出全部源程序完毕并完成实验报告,实验报告包括：需求分析、概要设计、详细

设计、调试分析、用户使用说明和测试结果。

附加题目：（从中挑选一题）

1．设顺序表A中的数据元素递增有序，试写一程序，将x插入到顺序表的适当位置上，使

该表仍然有序。

12n

2．用单链表ha存储多项式A（x）=a+ax+ax+„+ax(其中a为非零系数)，用单链表

012nI

12m

hb存储多项式B（x）=b+bx+bx+„+bx(其中b为非零系数)，要求计算C（x）

012mj

=A（x）+B（x），结果存到单链表hc中。试写出程序。

3．设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从

出列的下一个人重新开始报数，数到m的人又出列，如此重复，直到所有的人全部出列

为止。Josephus问题是：对于任意给定的n，m，s，求出按出列次序得到的n个人员的

顺序表。

实验二栈及队列的操作（2学时）

一．目的与要求

实验目的：熟练掌握栈及队列基本操作的实现。

二．实验内容：

（1）建立栈并进行元素（8，9，5，4）入栈，实现链栈的建立及入栈的基本操作；

（2）实现元素（9，5）的出栈，实现链栈的出栈的操作；

（3）建立链队列，并实现元素(4,5,7,6,8)入队，实现链队列的建立和入队的基本操作；

（4）实现元素(4,5,7,6,8)出队，实现链队列的出队的基本操作。

三．实验要求：

在上机后写出全部源程序完毕并完成实验报告,实验报告包括：需求分析、概要设计、详细

设计、调试分析、用户使用说明和测试结果。

附加题

停车场管理

问题描述：

设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在

停车场内按车辆达到时间的先后顺序，依次由北向南排列（大门在最南端，最先达到的第一

辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上

等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在

它之后进入的车辆必