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

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

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

七、设计性实验(以下两个设计题目学生可根据自己的掌握程度或兴趣自行选择完成) 1. 编程实现在双向循环链表上的插入、删除和查找操作

⑴ 实验要求

（1）输入链表的长度和各元素的值，用尾插法建立双向循环链表，并输出链表中各元素值，观察输入的内容与输出的内容是否一致。

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

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

（4）在双向循环链表中查找值为x元素，如果查找成功，则显示该元素在链表中的位置，否则显示该元素不存在。

⑵ 核心算法提示

双向循环链表采用的存储结构描述如下：

typedef struct DULNODE

{ Elemtype data; /*数据域*/

struct DULNODE *prior; /*指向前驱结点的指针域*/ struct DULNODE *next;/*指向后继结点的指针域*/

}DULNODE,*DuLinklist; typedef int Elemtype;

不论是建立双向循环链表还是在双向循环链表中进行插入、删除和查找操作，其操作方法和步骤都跟单链表类似。只不过要注意两点：

（1）凡是在操作中遇到有修改链的地方，都要进行前驱和后继两个指针的修改。 （2）单链表操作算法中的判断条件：p= =NULL 或p!=NULL ,在循环链表的操作算法中则需改为：p!= L,其中L为链表的头指针。

⑶ 核心算法描述

void DuList_creat (DuLinklist &L,int n) /*输入n个整数（其中n为表长），将这些整数作为data

域并用尾插法建立一个带头结点的双向循环链表的函数*/

{ L=( DuLinklist)malloc(sizeof(DULNODE));/*为头结点分配空间*/

16

L->next=L->prior=L;

/*使头结点的后继指针和前驱指针都指向自身，形成空的双向循环链表*/

r=L; /*尾指针初始指向头结点*/

for (i=0;i

{ p=(DuLinklist)malloc(sizeof(DULNODE));/*为一个新结点分配空间*/ scanf(\从键盘输入值，并保存在新结点数据域中*/ p->next=r->next; /*新结点后继指针指向尾结点r的后继结点*/ p->prior=r; /*新结点的前驱指针指向尾结点r*/

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

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

}

L->prior=r; /*使尾结点成为头结点的前驱结点*/ }

status DuList_search(DuLinklist L, int i;Elemtype &e)

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

{ p=L->next; /*使指针p指向第1个元素结点*/ j=1; /*计数器赋初值为1*/

while (p!=L && jnext; j++;

} if (j!=i)

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

status DuList_insert(DuLinklist &L,int i;Elemtype x)

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

{ p=L->next; j=1;

while(p!=L &&j

{ p=p->next;

++j; }

if(j!=i)

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

/*下面四条语句就是完成修改链，将新结点s插入到p结点之前*/ s->next=p;

p->prior->next=s;

s->prior=p->prior;

p->prior=s;

return OK;

}

17

status DuList_delete(DuLinklist &L,int i,Elemtype &x)

/*在带头结点的双向循环链表L中，删除第i个元素结点，并用x返回其值*/ { p=L->next;j=1;

while(p!=L&&jnext;

++j; }

if (j!=i)

return ERROR; /*若位置不正确，即i小于1或大于表长，则出错*/

q=p; /*记下被删结点*/

p->prior->next=p->next; /*修改链使得p结点从链中脱离*/ p->next->prior=p->prior; x=q->data;

printf(\ free(q); //释放被删结点空间 return OK; }

提醒: 请将上述算法与单链表上相应操作的算法对照学习，特别注意它们不相同的地方。

2．编写一个程序，计算出一个单链表中数据域值为一个指定值x的结点个数。

实验要求：

⑴ 从键盘输入若干个整数，以此序列为顺序建立一个不带头结点的单链表； ⑵ 输出此单链表中的各个数据元素值；

⑶ 给定一个x的具体整数值，计算并返回此单链表中数据域值为x的结点个数值。

18

实验B03: 栈的操作实验

一、实验名称和性质

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

1．掌握栈的存储结构的表示和实现方法。 2．掌握栈的入栈和出栈等基本操作算法实现。 3．了解栈在解决实际问题中的简单应用。 三、实验内容

1．建立顺序栈，并在顺序栈上实现入栈和出栈操作（验证性内容）。 2．建立链栈，并在链栈上实现入栈和出栈操作（设计性内容）。 3．实现汉诺（Hanoi）塔求解问题（应用性设计内容）。 四、实验的软硬件环境要求

硬件环境要求：

PC机（单机）

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

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

编程实现如下功能：

（1）根据输入的栈中元素个数n和各元素值建立一个顺序栈，并输出栈中各元素值。 （2）将数据元素e入栈，并输出入栈后的顺序栈中各元素值。

（3）将顺序栈中的栈顶元素出栈，并输出出栈元素的值和出栈后顺序栈中各元素值。 2. 实验相关原理：

栈是一种插入和删除操作都限制在表的一端进行的特殊线性表，它的操作具有“先进后出”的特性。采用顺序存储结构的栈称为顺序栈。栈的存储结构描述如下：

#define MAXSIZE 100; /*顺序栈的最大长度*/ typedef struct

{ Selemtype base[MAXSIZE]; /*存储栈中数据元素的数组*/

int top; /*top为栈顶指针，它指示栈顶元素的存储空间的下一个存储单元*/ }Sqstack;

【核心算法提示】

19

1．顺序栈入栈操作的基本步骤：首先判断顺序栈是否为满，如果满，则函数返回ERROR，否则将待入栈的数据元素存放在top所指示的存储单元中，再使top后移一个存储单元位置，即将top值加1，最后函数返回OK。

2． 顺序栈出栈操作的基本 …… 此处隐藏：1940字，全部文档内容请下载后查看。喜欢就下载吧 ……