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 && 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&&j ++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． 顺序栈出栈操作的基本步骤：首先判断顺序栈是否为空，如果空，则函数返回ERROR，否则将栈顶指针前移一个存储单元位置，即将top值减1,再将top所指示的栈顶元素用e返回其值，并使函数返回OK。 【核心算法描述】 status Push(Sqstack &S,Selemtype e) /*将数据元素e压入到顺序栈S中，使其成为新的栈项元素*/ { if (S.top >=MAXSIZE) /*如果栈满，则函数返回ERROR*/ return ERROR; S.base[S.top++]=e;/*将新元素e存放在top所指示的存储单元中,并使top值加1*/ return OK; } status Pop(Sqstack &S,Selemtype &e) /*将顺序栈S中的栈顶元素从栈中删除，并用e返回其值*/ { if (S.top==0) /*如果栈空，则函数返回ERROR*/ Return ERROR; e=S.base[--S.top];/*将top值减1,并用e保存top所指示的栈顶元素值*/ return OK; } 3．源程序代码参考 #define MAXSIZE 100 typedef struct { int base[MAXSIZE]; int top; /*top指示存储栈顶元素的下一存储单元*/ }Sqstack; /*顺序栈的类型定义*/ Sqstack Push(Sqstack S,int e) /*顺序栈的入栈操作函数*/ { if (S.top>=MAXSIZE) printf(\ else S.base[S.top++]=e; return S; } Sqstack Pop(Sqstack S,int *e) /*顺序栈的出栈操作函数*/ { if (S.top==0) printf(\ else 20