数据结构实验报告.doc

数据结构实验报告


指导老师康松林

信息科学与工程学院
电子信息工程0503班
0903050322
邓晨



2006-12-30
目录
实验一线性表基本操作---03
实验二堆栈与队列------10
实验三二叉树基本操作----16

实验四图的基本操作------22

实验五查找----------32
心得体会--------------------34
实验1 线性表基本操作
实验目的
 熟悉C语言的上机环境,掌握C语言的基本结构。
定义单链表的结点类型。
  熟悉对单链表的一些基本操作和具体的函数定义。
  通过单链表的定义掌握线性表的链式存储结构的特点。
 熟悉对单链表的一些其它操作
实验内容
1. 实现单链表的定义和操作。该程序包括单链表结构类型以及对单链表操作的具体的函数定义
程序中的单链表(带头结点)结点为结构类型,结点值为整型。
/* 定义DataType为int类型*/typedef int DataType;
 /* 单链表的结点类型*/
typedef struct LNode
{DataType data;
struct LNode *next;
}LNode,*LinkedList;
 /* 初始化单链表*/LinkedList LinkedListInit()
 /* 清空单链表*/void LinkedListClear(LinkedList L)
 /* 检查单链表是否为空*/int LinkedListEmpty(LinkedList L)
 /* 遍历单链表*/void LinkedListTraverse(LinkedList L)
 /* 求单链表的长度*/int LinkedListLength(LinkedList L)
 /* 从单链表表中查找元素*/LinkedList LinkedListGet(LinkedList L,int i)
 /* 从单链表表中查找与给定元素值相同的元素在链表中的位置*/
int LinkedListLocate(LinkedList L, DataType x)
/* 向单链表中插入元素*/void LinkedListInsert(LinkedList L,int i,DataType x)
 /* 从单链表中删除元素*/void LinkedListDel(LinkedList L,DataType x)
 /* 用尾插法建立单链表*/LinkedList LinkedListCreat( )
2. 约瑟夫环问题:任给正整数N和K,按下述方法可以得到1,2, …,n的一个置换,将数字1,2,…,n环形排列,按顺时针方向自1开始报数,报到K时输出该位置上的数字,并使其出列。然后从他在顺时针方向的下一个数字继续报数,如此下去,直到所有的数字全部出列为止。例如N=10,K=3,则正确的出列顺序应为3,6,9,2,7,1,8,5,10,4。
3. 试单链表实现一个简单的电子通讯本管理软件,要求能查找联系地址,增加和删除联系人。联系方式假定包括姓名、电话和地址。
问题描述和分析
实现单链表的定义和操作是最为基础的内容,共有如下几个环节:
初始化单链表
清空单链表
检查单链表是否为空
遍历单链表
求单链表的长度
从单链表表中查找元素
从单链表表中查找与给定元素值相同的元素在链表中的位置
向单链表中插入元素
从单链表中删除元素
用尾插法建立单链表
2利用单链表的特性,可以将“环”用链表来表示;“报数”的过程即为链表遍历的过程;“出列”则是删除元素操作。最后没被删除的元素即为问题的解。
要求是将一串数据首尾相接然后按照一定的条件输出。本例子的输出条件是给定一个数字K,然后给这一组数据编号,相当于是让一队人排在一起报数。报到K的人便出列。然后从出列的人的下一位开始继续从一开始报数,报到K之后再出列,就这样循环进行下去直到所有的书都被输出。在这个程序可以用线性表来实现。用一个循环线性表。即表尾的元素指向标头元素。在每一个元素中再加以个用来记数的变量。用来记录和判断该元素是否是该轮的第K个元素,是否该出列。然后用一个循环语句对这一列数据进行计数,输出。
3一个功能简单的电话本。这个电话本也可以用单链表来实现。建立一个单链表用来储存信息,联系人的姓名、电话和地址。查找功能就是链表中的查找,因为里面的信息不会非常大,所以就用逐个查找的方法查找。增加和删除联系人的信息都可以用通过对链表的增加和删除非常容易的实现。
函数说明及重要算法解释
程序一
typedef struct lnode /