《数据结构》实验指导书（C语言版）(2)

{ for (i=0;i

/*从第一个元素开始依次将每个元素值与给定值x比较*/

if (i

3．源程序代码参考 #define MAXLEN 50

typedef struct{int elem[MAXLEN]; int length;}Sqlist;

Sqlist Sqlist_insert(Sqlist L,int i,int x) /*顺序表插入函数*/ {int j;

if(i<1||i>L.length+1) printf(\ else if(L.length>=MAXLEN) printf(\

else { for(j=L.length-1;j>=i-1;j--)

L.elem[j+1]=L.elem[j];

L.elem[i-1]=x; L.length++;

} return L; }

Sqlist Sqlist_delete(Sqlist L,int i) /*顺序表删除函数*/ {int j;

if(i<1||i>L.length) printf(\ else { for(j=i;j<=L.length-1;j++) L.elem[j-1]=L.elem[j];

L.length--;

} return L; }

int Sqlist_search(Sqlist L,int x)/* 顺序表查找函数*/ { int i;

for (i=0;i

6

else

return 0; }

void Sqlist_display(Sqlist L) /*顺序表元素输出函数*/ { int j;

for(j=0;j<=L.length-1;j++) printf(\ printf(\}

main() /*主函数 */ { Sqlist L; int i,x,j;

printf(\请求输入顺序表中元素个数*/ scanf(\

printf(\请求输入顺序表中各个元素*/ for(j=0;j<=L.length-1;j++)

scanf(\

printf(\请求输入插入操作位置*/ scanf(\

printf(\请求输入需要插入的新元素*/ scanf(\

L=Sqlist_insert(L,i,x);/*调用顺序表插入函数*/ Sqlist_display(L);/*调用顺序表元素输出函数*/

printf(\请求输入删除操作位置*/ scanf(\

L=Sqlist_delete(L,i);/*调用顺序表删除函数*/ Sqlist_display(L);/*调用顺序表元素输出函数*/ printf(\ scanf(\

if (Sqlist_search(L,x)) /*如果查找成功，则显示查找成功和找到的元素位置，否则显示查

找不成功*/

printf(\ else

printf(\ }

7

4．运行结果参考如图1-1所示：

图1-1: 验证性实验运行结果

七、设计性实验(以下两个设计题目学生可根据自己的掌握程度或兴趣自行选择完成) 1．编程实现删除有序顺序表中的所有重复元素，即使有序顺序表中相同的元素只保留一个。 ⑴ 实验要求

① 根据输入的n个非递减的有序数据建立一个有序顺序表，并输出有序顺序表中各元素值。

② 删除有序顺序表中所有的重复元素，并显示删除后的有序顺序表中各元素值。 ⑵ 核心算法提示

要在有序顺序表中删除重复的元素，首先就要抓住有序顺序表的特性：重复的元素总是在相邻的位置上，如：12，15，15，15，35，56，56，78。则删除重复元素后所得的有序表为：12，15，35，56，78。下面给出大致的操作步骤：从第1 个元素开始，依次将它与后面相邻的元素进行比较，如果相等则将前面那个相等的元素从顺序表中删除；如果不相等，则继续往下比较，如此重复，直到最后一个元素为止。

⑶ 核心算法描述 Sqlist delSqlist(Sqlist L)

{int i=0,j;

while(i

if (L.elem[i]==L.elem[i+1]) /*如果第i个及第i+1个相邻元素值相等*/

{ for (j=i+1;j

除第i个元素的目的*/

L.elem[j-1]=L.elem[j];

L.length--; /*有序顺序表的表长减1*/ } else i++; return L; }

2．编程实现一个简单学生成绩表的操作。

8

实验要求

此系统的功能包括：

① 查询：按特定的条件查找学生

② 修改：按学号对某个学生的某门课程成绩进行修改 ③ 插入：增加新学生的信息

④ 删除：按学号删除已退学的学生的信息。 学生成绩表的数据如下：

学号 2008001 2008002 2008003 2008004 2008006 2008006 姓名 Alan Danie Helen Bill Peter Amy 性别 F M M F M F 大学英语 高等数学 93 75 56 87 79 68 88 69 77 90 86 75 要求采用顺序存储结构来实现对上述成绩表的相关操作。

9

实验B02: 链表的操作实验

一、实验名称和性质

所属课程 实验名称 实验学时 实验性质 必做/选做 数据结构 链表的操作 2 □验证 □综合 √设计 √必做 □选做 二、实验目的

1．掌握线性表的链式存储结构的表示和实现方法。 2．掌握链表基本操作的算法实现。 三、实验内容

1．建立单链表，并在单链表上实现插入、删除和查找操作（验证性内容）。 2．建立双向链表，并在双向链表上实现插入、删除和查找操作（设计性内容）。 3．计算已知一个单链表中数据域值为一个指定值x的结点个数（应用性设计内容）。 四、实验的软硬件环境要求

硬件环境要求：

PC机（单机）

Windows环境下的TurboC2.0以上或VC++ 等。 使用的软件名称、版本号以及模块： 五、知识准备

前期要求熟练掌握了C语言的编程规则、方法和单链表和双向链表的基本操作算法。 六、验证性实验 1．实验要求

编程实现如下功能：

（1）根据输入的一系列整数，以0标志结束，用头插法建立单链表，并输出单链表中各元素值，观察输入的内容与输出的内容是否一致。

（2）在单链表的第i个元素之前插入一个值为x的元素，并输出插入后的单链表中各元素值。

（3）删除单链表中第i个元素，并输出删除后的单链表中各元素值。

（4）在单链表中查找第i个元素，如果查找成功，则显示该元素的值，否则显示该元素不存在。 2. 实验相关原理：

线性表的链式储结构是用一组任意的存储单元依次存放线性表中的元素，这组存储单元可以是连续的，也可以是不连续的。为反映出各元素在线性表中的前后逻辑关系，对每个数据元素来说，除了存储其本身数据值之外，还需增加一个或多个指针域，每个指针域的值称为指针，又称作链，它用来指示它在线性表中的前驱或后继的存储地址。这两个部分的的一起组成一个数据元素的存储映像，称为结点，若干个结点链接成链表。如果一个结点中只含

10