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

实验要求

此系统的功能包括：

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

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

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

学号 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

一个指针的链表，则称单链表。单链表的存储结构描述如下：

typedef struct Lnode {

Elemtype data;/*数据域*/ struct Lnode *next;/*指针域*/

}LNODE,*Linklist; /*其中LNODE为结点类型名，Linklist为指向结点的指针类型名*/

【核心算法提示】

1． 链表建立操作的基本步骤：链表是一个动态的结构，它不需要予分配空间，因此建立链表的过程是一个结点“逐个插入” 的过程。先建立一个只含头结点的空单链表，然后依次生成新结点，再不断地将其插入到链表的头部或尾部，分别称其为“头插法”和“尾插法”。

2． 链表查找操作的基本步骤：因链表是一种\顺序存取\的结构，则要在带头结点的链表中查找到第 i个 元素，必须从头结点开始沿着后继指针依次\点数\，直到点到第 i 个结点为止,如果查找成功，则用e返回第i个元素值。头结点可看成是第0个结点。

3． 链表插入操作的基本步骤：先确定要插入的位置，如果插入位置合法，则再生成新的结点，最后通过修改链将新结点插入到指定的位置上。

4． 链表删除操作的基本步骤：先确定要删除的结点位置，如果位置合法，则再通过修改链使被删结点从链表中“卸下”，最后释放被删结点的空间。 【核心算法描述】

void creat1(Linklist &L) /*输入一系列整数，以0标志结束，将这些整数作为data域并用头

插法建立一个带头结点的单链表的函数*/

{ L=(Linklist)malloc(sizeof(LNODE));/*生成头结点*/ L->next=NULL;/*头结点的指针域初始为空*/ scanf(\

while(node!=0)

{ p=(Linklist)malloc(sizeof(LNODE));/*为一个新结点的分配空间*/ p->data=node; /*为新结点数据域赋值*/ p->next=L->next;/*新结点指针域指向开始结点*/

L->next=p; /*头结点指针域指向新结点，即新结点成为开始结点*/

scanf(\} }

void creat2(Linklist &L) /*输入一系列整数，以0标志结束，将这些整数作为data域并用尾插

法建立一个带头结点的单链表的函数*/

{ L=(Linklist)malloc(sizeof(LNODE));/*为头结点分配空间*/ L->next=NULL; /*头结点的指针域初始为空*/ r=L; /*尾指针初始指向头结点*/

scanf(\while(node!=0)

{ p=(Linklist)malloc(sizeof(LNODE));/*为一个新结点分配空间*/ p->data=node; /*新结点数据域赋值*/ p->next=NULL; /*新结点指针域为空*/ r->next=p;/*尾结点指针域指向新结点*/

11

r=p; /*尾指针指向新结点，即新结点成为尾结点*/

scanf(\ } }

status list_search(Linklist L, int i;Elemtype &e)

/*在带头结点的单链表L中查找第i个元素，如果查找成功则用e返回其值*/

{ p=L->next; /*使指针p指向第1个元素结点*/

j=1; /*计数器赋初值为1*/

while (p&& jnext; j++; }

if (!p&& j>i)

return ERROR; /*如果i值不合法，即i值小于1或大于表长，则出错*/ e=p->data; /*如果第i个元素存在，则将该元素值赋给e*/ return OK;

}

status list_insert(Linklist &L,int i;Elemtype x)

/*在带头结点的单链表L中第i个位置之前插入新元素x*/

{ p=L; j=0;

while(p!=NULL&&j

个位置*/

{ p=p->next;

++j;

}

if(p==NULL||j>i-1)

return ERROR; /*若位置不正确,即i小于1或大于表的长度加1，则出错*/ s=(Linklist)malloc(sizeof(LNODE)); /*分配一个新结点的空间*/ s->data=x; /*为新结点数据域赋值*/

/*下面两条语句就是完成修改链，将新结点s插入到p结点之后*/

s->next=p->next; /*新结点指针域指向p的后继结点*/

p->next=s; /*新结点成为p的后继结点*/ return OK;

}

status list_delete(Linklist &L,int i,Elemtype &x)

/*在带头结点的单链表L中，删除第i个元素结点,并用x返回其值*/

{ p=L;j=0;

while(p->next!=NULL&&jnext;

++j; }

if (p->next==NULL||j>i-1)

return ERROR; /*若位置不正确，即i小于1或大于表长，则出错*/ q=p->next; /* q指向p的后继结点*/

12