《数据结构》实验指导书（源代码）

s->data=i； r->next=s； r=s；

cin>>i； } r->next=NULL； return p； }

//输出单链表

void print(1ink *head) {link *p；

p=head->next；

while(p->next!=NULL) {

cout<data<<\”; //输出表中非最后一个元素 p=p->next； )

cout<data； //输出表中最后一个元素 cout<

link *Locate(1ink *head，int x) ∥在单链表中查找第x个结点 {link *p； p=head； int j=0；

while((p!=NULL)&&(jnext; j++；} return p； }

void delete I(1ink *head，elemtype x)

//在head为头指针的单链表中，删除值为x的结点 {

link *p, *q； q=head；

p=head->next；

while((p!=NULL)&&(p->data!=x)) {

q=p；

p=p->next；)

if(p==NULL)cout<<”要删除的结点不存在“; else {

q->next=p->next；

5

delete(p)； } }

void insert(1ink *head，int x,elemtype y)

//在头指针head所指单链表中，在第x个结点之后插入值为y的结点 {link *p， *s； s=new link； s->data=y；

if(head->next==NULL)//链表为空 {

head->next=s； s->next=NULL： }

p=Locate(head，x)； //调用查找算法 if(p==NULL)

cout<<”插入位置非法”; else

{s->next=p->next； p->next=s； }}

void change(1ink *p,elemtype x，elemtype y) {∥将单链表P中所有值为x的元素改成值为y link *q； q=p->next； while(q!=NULL)

{if(q->data==x)q->data=y； q=q->next； } }

void count(1ink *h) //统计单链表中结点个数 (1ink *p；int n=0； p=h->next； while(p!=NULL) {n++；p=p->next；} retum n; }

void main() { int n;

6

link p,q;

p=rcreat()；//尾插法建立链表

print(p)； //输出刚建立的单链表 cout<<”请输入要删除的元素”； cin>>y；

deletel(p，y)；

print(p)； //输出删除后的结果 cout<<”请输入插入位置”; cin>>x；

cout<<”请输入待插元素值”； cin>>y；

insert(p，x，y)；

print(p)； //输出插入后的结果

cout<<”请输入修改前、后的元素值”; cin>>x>>y；

change(p，x，y)； print(p)；

cout<<“请输入要查找的元素值”; cin>>x；

q=Locate(p ,x)；

if(q==NULL)cout<

}

六、选作实验

试设计一元多项式相加（链式存储）的加法运算。 A（X）=7+3X+9X8+5X9

B（X）=8X+22X7-9X8 1．建立一元多项式； 2．输出相应的一元多项式； 3．相加操作的实现。

7

实验二 循环链表的操作

一、实验目的：

通过本实验中循环链表和双向链表的使用，使学生进一步熟练掌握链表的操作方式。

二、实验内容：

本次实验可以从以下两个实验中任选一个：

1．建立一个单循环链表并实现单循环链表上的逆置。

所谓链表的逆置运算(或称为逆转运算)是指在不增加新结点的前提下，依次改变数据

元素的逻辑关系，使得线性表(al，a2，a3，?，an)成为(an，?，a3，a2，a1)。 2. 构建一个双向链表，实现插入、查找和删除操作。 三、实验要求：

1. 根据实验内容编写程序，上机调试、得出正确的运行程序。 2. 写出实验报告（包括源程序和运行结果）。

四、实验学时：2学时 五、实验步骤：

1．进入编程环境，建立一新文件；

2. 参考以下相关内容，编写程序，观察并分析输出结果。

① 建立一个带头结点的单循环链表，从头到尾扫描单链表L，把p作为活动指针，沿着链表向前移动，q作为p前趋结点，r作为q的前趋结点。其中，q的next值为r；r的初值置为head。

② 双向链表的构造与单链表相同，至于它的插入与删除运算比单链表复杂，插入运算需要4步操作，删除运算需要2步操作，注意语句的次序，不要任意交换位置，以免不能正确插入或删除结点。

③ 部分参考程序

//循环链表

∥头文件h1．h的内容 #define NULL 0 #include #include typedef struct node {int num；

struct node *next；

}linklist；

∥以下是主程序 #include”h1．h”

∥输出循环链表的信息 void output(linklist *head) {linklist *p； p=head->next； while(p!=head) {printf(”％d”，p->num)； p=p->next；

8