数据结构实验报告.doc

实验报告
实验课程: 数据结构
学生姓名:
学号:
专业班级:

2010年 6月 15日
目录
实验一线性表及其应用……………………………………3
实验二栈和队列……………………………………………12
实验三二叉树及其应用……………………………………19
实验四图的运用……………………………………………24
实验五查找排序………………………………………… 29
南昌大学实验报告
---(1)线性表及其应用
学生姓名: 学号: 专业班级:
实验类型:□验证□综合■设计□创新实验日期: 2010-3-8 实验成绩:

帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现,尤以链表的操作和应用作为重点。

构造一个空的线性表L;
在线性表L的第i个元素之前插入新的元素e;
在线性表L中删除第i个元素,并用e返回其值。

,并设计出在不同的存储结构中线性表的基本操作算法。
,对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行分析。
 
PC微机
DOS操作系统或 Windows 操作系统
Turbo C 程序集成环境或 Visual C++ 程序集成环境

,设计出线性表的顺序和链表存储结构;
设计出这两种存储结构下的线性表的插入、删除算法;
用所选择的语言实现算法;
测试程序,并对不同存储结构下的算法分析。

:
输入数据:L = ( ) ListInsert (L, 1, 'k'),
正确结果:L = (k)
输入数据:L = (EHIKMOP) ListInsert (L, 9, 't'),
正确结果:return ERROR; L = (EHIKMOP)
输入数据:L = (ABCEHKNPQTU) ListInsert(L, 4, 'u'),
正确结果: L = (ABCuEHKNPQTU)
:
输入数据:L = () ListDelete (L, 1, e)
正确结果:ERROR, L = ()
输入数据:L = (DEFILMNORU) ListDelete_Sq(L, 5, e)
正确结果: L = (DEFIMNORU), e='L'
输入数据:L = (CD) ListDelete_Sq(L, 1, e)
正确结果: L = (D), e = 'C'
,对两种存储结构下插入和删除的时间复杂度进行分析。

顺序存储C程序:
#include <>
#include <>
typedef int elemtype;
typedef int status;
#define ERROR -1
#define OK 1
#define OVERFLOW 2008
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct{
elemtype *elem;
int length;
int listsize;
}sqlist;
status InitList_Sq(sqlist *L){
//构造一个空的线性表L
elemtype *a=0;
a=(elemtype *)malloc(LIST_INIT_SIZE*sizeof(elemtype));
L->elem=a;
if(!(*L).elem)return OVERFLOW;
(*L).listsize=LIST_INIT_SIZE;
(*L).length=0;
return OK;
}
status List_Insert(sqlist *L,int i,elemtype e){
//在第i个元素之前插入元素e
elemtype * p=0; elemtype *q=0;elemtype * newbase=0;
if(i<1||i>(*L).length+1) return ERROR;
if((*L).length>=(*L).listsize){
newbase=(elemtype *)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(elemtype));
if(!newbase)return(OVERFLOW);
(*L).elem=newbase;
(*L).l