《数据结构》实验指导书2011年8月前言 (2)实验一、顺序表的插入和删除 (3)实验二、单链表的插入和删除 (6)实验三、栈的应用 (10)实验四、队列的应用 (13)实验五、数组的应用 (16)实验六、树的应用 (18)实验七、图的应用 (21)实验八、查找 (24)实验九、内部排序 (26)实验十、综合实验 (28)《数据结构》是软件工程专业的专业基础必修课，主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法进行分析和评价。

本课程的学习应使学生深刻地理解数据结构的逻辑结构和物理结构的基本概念及有关算法，培养学生基本的、良好的程序设计技能以及针对具体问题，选择适当的数据结构，设计出有效算法的能力。

《数据结构》是一门理论和实践相结合的课程，它在整个计算机专业教学体系中处于举足轻重的地位，是计算机科学的算法理论基础和软件设计的技术基础，其上机实验的目的主要是编程实现数据结构各章的主要算法，训练学生实际动手进行程序设计和程序调试的能力，加深对数据结构相关概念和算法的理解。

实验一顺序表的插入和删除【实验目的】1、掌握用Turbo c上机调试线性表的基本方法；2、掌握顺序表的基本操作，插入、删除、查找以及顺序表合并等运算的实现；3、运用线性表解决线性结构问题。

【实验预备知识】1、复习C语言中数组的用法。

2、了解线性表和顺序表的概念，顺序表的定义方法。

线性表是n个数据元素的有限序列，至于每个数据元素的具体含义，在不同的情况下各不相同。

顺序表是线性表的顺序存储表示，是用一组地址连续的存储单元依次存储线性表的数据元素。

在C语言中，顺序表是用数组来实现的。

3、掌握线性表在顺序存储结构上实现基本操作：查找、插入、删除和合并的算法。

在实现这些算法的时候，要注意判断输入数据的合法性，除此之外还要要注意以下内容：在实现查找的时候，首先要判断该顺序表是否为空，其次要判断查找后的结果(查到时输出查到的数据，未查到时给出未查到提示)。

在实现插入的时候，首先要判断该顺序表是否为满，如为满则报错(此时要注意：顺序表是用数组来实现的，它不能随机分配空间)；如不为满，则需判断要插入的位置是否合法（例如：如果一个线性表的元素只有10个，而要在第0个元素前插入或在第11个元素后插入就为不合法）。

其次要注意是前插还是后插，两者是有区别的；最后还要注意插入时各个数据元素移动的次序是从后面依次开始移动。

在实现删除的时候，首先要判断该顺序表是否为空，如为空则报错，如不为空，则需判断要删除的位置是否合法（例如：如果一个线性表的元素只有10个，而要删除第0个或第十一个元素就为不合法）。

其次还要注意删除时各个数据元素移动的次序是从前面依次开始移动。

【实验内容】1、顺序表的插入算法；2、顺序表的删除算法；3、顺序表的合并算法。

【实验步骤】一、用C语言编程实现建立一个顺序表，并在此表中插入一个元素和删除一个元素：1、通过键盘读取元素建立线性表；2、指定一个元素，在此元素之前插入一个新元素；3、指定一个元素，删除此元素。

二、用C语言编程实现两个按递增顺序排列线性表的合并。

【部分实验代码】1、顺序表结构的定义：#include <stdio.h>#define maxnum 255typedef int elemtype;typedef struct{ elemtype list[maxnum];int num;}qltype;2、顺序表前插（在第i号元素前插入一个新的元素）int qiancha(qltype *la,int i,int x){ int j;if(i<0||i>la->num+1){ printf(“\n the value of i is wrong!”);return 0;}if(la->num+1>=maxnum){ printf(“\n overflow!”);return 0;}. for(j=la->num;j>=i;j--)la->list[j+1]=la->list[j];la->list[i]=x;la->num++;return 1;}3、顺序表删除int shanchu(qltype *la,int i){ if(i<0||i>la->num){ printf(“\n the position is wrong!\n”);return 0;}for(i;i<la->num;i++)la->list[i-1]=la->list[i];la->num--;return 1;}实验二单链表的插入和删除【实验目的】1、了解单链表的基本概念，掌握单链表的基本操作，插入、删除、查找等运算在链式存储结构上的运算；2、运用线性表解决线性结构问题，体会线性表的两种存储结构的区别。

【实验预备知识】1、复习C语言中指针的用法，特别是结构体的指针的用法；2、了解单链表的概念，单链表的定义方法；单链表是线性表的链式存储表示，是用一组任意的存储单元依次存储线性表的数据元素。

因此，为了表示每个数据元素ai 与其直接后继元素ai+1之间的逻辑关系，对数据元素ai来说，，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置），而这部分就是用指针来完成的。

3、掌握线性表在链式存储结构上实现基本操作：查找、插入、删除的算法；在实现这些算法的时候，要注意判断输入数据的合法性，除此之外还要要注意以下内容：在实现查找的时候，首先要判断该顺序表是否为空，其次要判断查找后的结果(查到时输出查到的数据，未查到时给出错误提示)。

在实现插入的时候，由于是链式存储，它可以随机产生和回收存储空间，所以它不要判断线性表是否为满，但仍需判断要插入的位置是否合法，原因同实验一，其次要注意插入的时候语句的顺序不可颠倒，否则出错。

例如：s所指向结点要插入在p所指向的结点之后，则：正确形式：s->next=p->nextp->next=s错误形式：p->next=ss->next=p->next(因为此时p->next已经指向s了)在实现删除的时候，首先要判断线性表是否为空，为空则不能删除；其次在删除后要回收空间。

s例如：删除如上图所示s所指向的结点p->next=p->next->nextfree s【实验内容】1、单链表的插入算法2、单链表的删除算法3、循环链表的插入和删除算法（选做）【实验步骤】用C语言编程实现建立一个单链表，并在此表中插入一个元素和删除一个元素1、通过键盘读取元素建立单链表；2、指定一个元素，在此元素之前插入一个新元素；3、指定一个元素，删除此元素。

【部分实验代码】1、单链表的结构定义：#include <stdio.h>typedef int elemtype;typedef struct lnode{ elemtype data;struct lnode *next;}*linklist;2、建立单链表的算法int n; /*n作为整个程序的全局变量*/linklist *creat(void){ linklist *head, *p1, *p2;n=0;p1=p2=(linklist *)malloc(sizeof(linklist));scanf(“%d”,&p1->data);head=null;while(p1->data!=0){ n=n+1;if(n==1) head=p1;else p2->next=p1;p2=p1;p1=(linklist *)malloc(sizeof(linklist));scanf(“%d”,&p1->data);}p2->next=null;return(head);}3、单链表的插入算法int insert(linklist *head, int i,elemtype e) { linklist *p, *s;int j;p=head; j=0;while(p && j<i-1){ p=p->next;++j;}if(!p||j>i-1){ printf(“无法插入”)；return 0;}s=(linklist *)malloc(sizeof(lnode));s->data=e;s->next=p->next;p->next=s;return 1;}4、单链表的删除算法int deltree(linklist *head,int i,elemtype e){ linklist *p, *q;int j;lp=head; j=0;while(p->next && j<i-1){ p=p->next;++j;}if(!(p->next)||j>i-1){ printf(“无法删除”);return 0;}q=p->next;p->next=q->next;e=q->data;free(q);return 1;}实验三栈的应用【实验目的】1、掌握栈的顺序存储结构和链式存储结构，以便在实际背景下灵活运用；2、掌握栈的特点，即后进先出的原则；3、掌握栈的基本操作，如入栈与出栈等；运用栈解决问题。

【实验预备知识】1、掌握栈这种抽象数据类型的特点，并能在相应的应用任务中正确选用它；栈是操作受限的线性表，是限定仅在表尾进行插入或删除操作的线性表。

因此，对栈来说，表尾端有其特殊含义，称为栈顶（top），相应地，表头端称为栈底（botton）；栈又称为后进先出（Last In First Out）的线性表,简称LIFO结构，因为它的修改是按后进先出的原则进行的。

2、熟练掌握栈类型的两种实现方法，即两种存储结构表示时的基本操作实现算法，特别应注意栈满和栈空的条件以及它们的描述方法。

3、在学习顺序栈的基本操作实现算法时，应注意：在书上给出的结构定义是采用了一种动态管理方式（不够时，可以再分配），但在C语言中，用数组来存储顺序栈，是静态分配，即不能随机分配空间，这点易引起大家的误解。

【实验内容】1、顺序栈的进栈、出栈算法2、链式栈的进栈、出栈算法【实验步骤】一、用C语言编程实现建立一个顺序栈，并在此顺序栈中实现入栈和出栈操作1、通过键盘读取元素建立顺序栈；2、给定一个元素，将此元素压入此栈中；3、将栈顶一个元素弹出此栈。

二、用C语言编程实现建立一个链栈，并在此链栈中实现入栈和出栈操作1、通过键盘读取元素建立链栈；2、给定一个元素，将此元素压入此栈中；3、将栈顶一个元素弹出此栈。