数学与计算机学院《数据结构》课程实验指导书适用专业: 计算机科学与技术目 录第二部分 实验指导 3实验一 线性表的插入和删除 3实验二 线性结构（二）－栈和队列 13实验三 查找算法 18实验四 排序算法 25实验五 二叉树的操作 27实验六 图的操作 31第一部分 绪论本指导书是根据《数据结构》课程实验教学大纲编写的，适用于计算机科学与技术专业一、 本课程实验的作用与任务（楷体小三号）该课程实验的作用与任务是让同学们掌握计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法数据结构的学习不但需要有扎实的理论学习过程，合理和有效的实验也是必不可少的通过数据结构实验课程的教学和实际操作，需要学生总体上把握以下三个方面：其一就是让学生学会分析研究计算机加工的数据对象的特性，以便为数据选择适当的物理结构和逻辑结构；其二，根据结构，选择适当的算法，并初步掌握算法的时间分析和空间分析；其三，学习复杂的程序设计二、 本课程实验的基础知识依据理论课的讲授情况，本书的实验安排以表（包括有序表、链表等），树，图三个主要的数据结构为重点 本书的第一个实验是表的实验，有序表、链表为重中之重，必须掌握。
第五个实验为树的实验，树也是数据结构课中的一个重点，要认真掌握应当以二叉树的建立和遍历为重点图论是近年来兴起的新兴学科，第六个实验为图的实验：邻接表的建立与图的遍历建立邻接表，应当与链表的实验相比较，并且应当站在数据结构的角度来考虑两个实验的区别、联系图的遍历，可以和二叉树的遍历相比较第三个和第四个的实验是查找和排序的实验就算法而言，排序就是使关键字有序；就数据结构而论，排序还应关注数据的逻辑结构和物理结构，即排序的对象是记录，只有这样理解，才能真正的理解数据结构这门课三、本课程实验教学项目及其教学要求序号实验项目名称学时教学目标、要求1线性结构（线性表的插入和删除4掌握用Turbo C上机调试线性表的基本方法；掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算掌握握单链表的基本操作：插入、删除、查找等运算*2线性结构（二）4掌握栈的基础知识、结构特点及应用；掌握队列的结构特点和基本操作3查找算法3掌握查找表的定义和存贮；掌握查找常用方法及过程；实现顺序查找、二分查找、二叉排序树查找等算法4排序算法3掌握常用的排序方法，并掌握用高级语言实现排序算法的方法；深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。
5二叉树的操作4进一步掌握指针变量、动态变量的含义；掌握二叉树的结构特征，以及各种存储结构的特点及适用范围；掌握用指针类型描述、访问和处理二叉树的运算6图的操作4掌握图的基本存储方法；掌握有关图的操作算法并用高级语言实现；熟练掌握图的两种搜索路径的遍历方法合 计18注：有*号的表示是选开的实验，学生自由上机完成第 39 页第二部分 实验指导实验一 线性表的插入和删除一、 实验目的1. 掌握用Turbo C上机调试线性表的基本方法；2. 掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算3. 掌握握单链表的基本操作：插入、删除、查找等运算二、 实验要求1、顺序表要用函数creatlist()随机生成,用三个函数完成顺序表的插入，删除和按值查找2、用四个函数实现单链表的建立、插入、删除和查找3、保存和打印出程序的运行结果，并结合程序进行分析4、打印出文件清单三、 实验原理线性表是最常用的而且也是最简单的一种数据结构，线性表是N个数据元素的有限序列例如26个英文元素的字母表：（A，B，C，D，···）其数据结构的描述为：Linear_list=(D,R)其中：D={ai|ai属于D0,i=1,2,3,···}R={N},N={|i=2,3,4,···}。
本实验是以数组的形式把有序表存放在计算机内存的一个连续的区域内，这样便有：LOC(ai+1)=LOC(ai)+m其中m是存放每个元素所占的内存字数LOC(ai)=LO+m·(i-1)其中LO是ai的地址，即首地址四、 主要仪器及耗材计算机，Turbo C 2.0 软件五、 实验内容与步骤程序1：线性表基本操作的实现 这个程序中演示了顺序表的创建、插入、删除和查找，请修改并完成 程序如下：#include #include /*顺序表的定义：*/#define ListSize 100typedef struct{ int data[ListSize]; /*向量data用于存放表结点*/ int length; /*当前的表长度*/}SeqList;void main(){ void CreateList(SeqList *L,int n); void PrintList(SeqList *L,int n); int LocateList(SeqList *L,int x); void InsertList(SeqList *L,int x,int i); void DeleteList(SeqList *L,int i); SeqList L; int i,x; int n=10; /*THE LENGTH OF LIST*/ L.length=0; clrscr(); CreateList(&L,n); /*CREAT THE LIST*/ PrintList(&L,n); /*PRINT THE LIST*/ printf("INPUT THE RESEARCH ELEMENT"); scanf("%d",&x); i=LocateList(&L,x); printf("the research position is %d\n",i); /*顺序表查找*/ printf("input the position of insert:\n"); scanf("%d",&i); printf("input the value of insert\n"); scanf("%d",&x); InsertList(&L,x,i); /*顺序表插入*/ PrintList(&L,n); /*打印顺序表*/ printf("input the position of delete\n"); scanf("%d",&i); DeleteList(&L,i); /*顺序表删除*/ PrintList(&L,n); getch();/*打印顺序表*/}/*顺序表的建立：*/void CreateList(SeqList *L,int n){int i;printf("please input n numbers\n");for(i=1;i<=n;i++){scanf("%d",&L->data[i]);}L->length=n;}/*顺序表的打印：*/void PrintList(SeqList *L,int n){int i;printf("the sqlist is\n");for(i=1;i<=n;i++)printf("%d ",L->data[i]);}/*顺序表的查找：*/int LocateList(SeqList *L,int x){int i;for(i=1;i<=10;i++) if((L->data[i])==x) return(i); else return(0);}/*顺序表的插入：*/void InsertList(SeqList *L,int x,int i){int j;for(j=L->length;j>=i;j--)L->data[j+1]=L->data[j];L->data[i]=x;L->length++;}/*顺序表的删除：*/void DeleteList(SeqList *L,int i){ int j;for(j=i;j<=(L->length)-1;j++)L->data[j]=L->data[j+1];}程序2：单链表基本操作的实现这个程序中演示了单链表的创建、插入、删除和查找。
程序如下： #includetypedef struct node{ int data; struct node *next;} NODE;/******************************************/NODE *Create(){ NODE *p,*head; int x; head=(NODE *)malloc(sizeof(NODE)); head->next=NULL; printf("Input data,-1 to End!\n"); scanf("%d",&x); while(x!=-1){ p=(NODE *)malloc(sizeof(NODE)); p->data=x; p->next=head->next; head->next=p; scanf("%d",&x); } return(head);}/******************************************/void Output(NODE *head){ NODE *p; p=head; printf("Begin to dump the LinkList...\n"); while(p->next!=NULL){ printf("->%d",p->next->data); p=p->next; } printf("\nThe LinkList ended!\n");}/******************************************/int Listlen(NODE *head){ int i=0; NODE *p=head; while(p->next!=NULL){ i++; p=p->next; }return(i);}/******************************************/int Get(NODE *head,int i){int j=0;NODE *p=head;while(p->next&&jnext;}if(!p->next||j>i) return(0);else return(p->data);}/*************************。