数据结构实验指导书

数据结构实验指导书白劲波编黑龙江工程学院计算机科学与技术系2008年1月·哈尔滨实验一线性表的运算与应用实验目的1、熟悉使用Turboc2.0编辑、调试、运行程序的步骤和方法。

2、掌握数据结构实验的方法和步骤。

3、掌握线性结构的特点及线性表顺序存储与链式存储两种存储结构的特点。

4、掌握线性表的创建、插入、删除等操作的算法思路和实现方法。

实验内容预备知识——Turboc2.0的使用1、进入Turboc编辑环境：双击Turboc安装目录下的tc.exe文件。

2、最大化编辑窗口：<Alt>+<Enter>3、激活菜单：<F10>4、新建文件：File/New5、打开文件：File/Load或<F3>6、保存文件：File/Save或<F2>7、编译源程序：Compile/Compile to OBJ8、生成可执行文件：Compile/Make EXE File9、运行程序：<Ctrl>+<F9>10、查看结果：<Alt>+<F5>预定义常量和类型在数据结构实验中，程序中经常会用到像NULL、OK等符号常量，为以后编程方便起见，将这些程序中经常用到的符号常量和类型编写成一个头文件mydefine.h，这样以后编程时需要这些符号常量和类型时，只要将该头文件包含在程序中即可。

头文件mydefine.h的内容如下：#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define NULL 0typedef int Status;内容【问题描述】实现单链表的创建、遍历、插入、删除、查找等基本操作。

【基本要求】（1）从键盘输入元素的个数n，按逆位序创建一个具有n个元素的带表头结点的单链表。

（2）遍历单链表，依次输出各数据元素的值。

（3）在单链表的第i个位置插入一个值为x 的结点，要求从键盘输入要插入的元素值及其插入位置。

（4）在单链表中删除第一个值为x的结点，从键盘输入要删除的结点值x。

（5）从键盘输入一个数x，在单链表中查找第一个值为x的元素在链表中的位置。

（6）编写主函数依次调用上述各算法，进行测试，写出测试过程和结果。

【程序实现】进入Turboc编辑环境，输入、调试、运行下面的程序，观察并分析程序的运行结果，回答程序后面的问题。

（1）建立链表是从无到有地建立起一个链表，即一个一个地输入各结点数据，并建立起前后相互链接的关系。

首先建立一个空链表，然后依次生成各结点，新生成结点始终插入在链表的第1个位置（头插法）。

#include "mydefine.h"typedef struct LNode //单链表的存储结构定义{int data;struct LNode *next;}LNode,*Linklist;Linklist create_L (int n) //逆序创建单链表{ Linklist L,p; int i;L=(Linklist)malloc(sizeof(LNode));L->next=NULL;printf("input numbers in list:");for(i=n;i>0;--i){ p=(Linklist)malloc(sizeof(LNode));scanf("%d",&p->data);p->next=L->next; L->next=p;return(L);}（2）遍历链表是将链表中各结点的数据依次显示。

设一个指针变量p，先指向第1个结点，显示p所指结点的数据，然后p后移一个结点再显示之，直到链表尾结点。

void print_L(Linklist L){ Linklist p;printf("The list is:\n");p=L->next;while(p){ printf("%3d",p->data);p=p->next;}printf("\n");}（3）在单链表的第i个位置插入一个值为x 的结点，首先要找到链表中的第i-1个结点，然后生成新结点，将新结点插入到第i-1个结点的后面。

Status ListInsert_L(Linklist L,int i,int x){ Linklist p,s; int j;p=L;j=0;while(p&&j<i-1) //寻找第i-1个结点{ p=p->next; ++j;}if(!p||j>i-1) return ERROR; //i小于1或大于表长s=(Linklist)malloc(sizeof(LNode)); //生成新结点s->data=x; s->next=p->next; p->next=s; //插入L中return OK;}（4）删除链表中的结点是从第1个结点开始，检查该结点的数据是否等于要删除的数据，如果相等就将该结点删除，如不相等，则后移一个结点，如此进行下去，直到表尾为止。

void ListDelete_X(Linklist L,int x){ Linklist p,q;p=L;q=p->next;while(q && q->data!=x ) { p=q;q=q->next;}if(q){ p->next=q->next; free(q);} //删除q所指向的结点else printf("%d does not exist!",x);}（5）在单链表中查找第一个值为x的元素在链表中的位置，只需用一个循环依次扫描表中的每个结点，每扫描一个结点，计数器i加1，记录当前位置，如果当前结点的值等于要查找的值则结束搜索，否则扫描下一个结点。

int Locate_X(Linklist L,int x){ int i=0;Linklist p;p=L->next;while(p){ i++;if(p->data==x) break;p=p->next;}if(p) return i;else return 0;}（6）利用下面的main()函数，测试上述各算法。

main(){int n,i,x;Linklist L;clrscr();printf("input n:");scanf("%d",&n); //输入线性表中元素的个数L=create_L(n); //按逆位序创建线性表print_L(L); //打印线性表printf("input i,x:"); //输入要插入的位置i和要插入的数xscanf("%d,%d",&i,&x);ListInsert_L(L,i,x); //将x插入在L的第i个位置print_L(L);printf("input x:");scanf("%d",&x); //输入要删除的数xListDelete_X(&L,x); //在线性表L中删除第一个值为x的结点print_L(L); //打印删除后的线性表printf("input x:"); //输入要查找的数xscanf("%d",&x);i=Locate_X(L,x); //查找x在L中的位置printf("\nposition of %d is %d",x,i);}问题：（1）写出创建单链表的步骤。

（2）写出程序中实现建立空链表操作的语句。

（3）写出将结点p插入到头结点之后的语句。

（4）分别写出将指针指向链表第一个结点和将指针后移一个结点的语句。

（5）写出在带头结点的单链表L中第i个位置插入值为x的结点的步骤。

（6）写出删除函数ListDelete_X中指针p和指针q所指结点的关系。

【选作内容】（1）从键盘输入元素的个数n，按正位序创建一个具有n个元素的带表头结点的单链表。

（2）建立一个线性链表L，其元素值依次为从键盘输入正整数（以输入一个非正整数为结束）；在线性表中值为x的元素前插入一个值为y的数据元素。

若值为x的结点不存在，则将y插在表尾。

（3）在单链表中删除所有值为x的结点，从键盘输入要删除的结点值x。

实验二栈和队列及其应用实验目的1、深入了解栈和队列的特性。

2、掌握栈和队列基本操作的实现及其应用。

实验内容【问题描述】用栈和队列来判断一串字符是否为回文。

【基本要求】栈采用顺序栈，队列采用链队。

从键盘读入要测试的字符串。

【实现提示】1、分析：（1）判断一串字符是否为回文可以借助一个栈和一个队列来完成，分别定义栈和队列的存储结构及所需要的操作（初始化、入栈/队、出栈/队）。

（2）从键盘逐个读入要测试的字符串的字符（以#结束），每读入一个字符，则将该字符分别入栈和队列。

（3）所有字符读完后，如果栈不空，则每次从栈和队列中各取出一个元素进行比较，如不等则打印不是回文的信息，结束程序，否则继续读数比较，直到栈空，打印是回文的信息。

2、步骤：（1）编写所需的头文件◆编写栈实现的头文件：stack.h内容包括：栈的存储结构描述、初始化栈、压栈、弹栈◆编写队列实现的头文件：queue.h内容包括：队列的存储结构描述、初始化队列、入队、出队（2）编写源程序实现题目功能，源程序内容如下，试在空白处填上所需内容。

（1）//文件包含命令：包含预定义常量的头文件mydefine.h（2）//文件包含命令：包含栈实现的头文件stack.h（3）//文件包含命令：包含队列实现的头文件queue.hmain(){ char a,b,c;sqstack s;linkQueue Q;clrscr();（4）//调用队列的初始化函数初始化队列Q（5）//调用栈的初始化函数初始化栈Sscanf("%c",&c);while(c!='#'){ （6）; //将字符c入栈（7）; //将字符c入队（8）; //输入下一个字符}while( （9）) //如果栈不空{ （10）; //弹出栈顶元素赋给变量a（11）; //将队头元素出队赋给变量bif( （12）){printf("This isn't a cycle.\n"); exit(0); } //打印不是回文，并退出程序}printf("This is a cycle.\n");}【选作内容】利用栈实现数制转换程序。