实 实验课程：学生姓名：学 号：专业班级：
验 报 告
数 据 结 构
2010年 6月 15日
1
目 录
实验一 线性表及其应用??????????????3 实验二 栈和队列?????????????????12 实验三 二叉树及其应用??????????????19 实验四 实验五
图的运用?????????????????24 查找 排序???????????????? 29 2
南昌大学实验报告
---（1）线性表及其应用
学生姓名： 学 号： 专业班级：
实验类型：□ 验证 □ 综合 ■ 设计 □ 创新 实验日期： 2010-3-8 实验成绩：
一．实验目的
帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现，尤以链表的操作和应用作为重点。
二．问题描述
1． 构造一个空的线性表L；
2． 在线性表L的第i个元素之前插入新的元素e； 3． 在线性表L中删除第i个元素，并用e返回其值。
三．实验要求
1．分别利用顺序和链表存储结构实现线性表的存储，并设计出在不同的存储结构中线性表的基本操作算法。
2．在实验过程中，对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行分析。
四．实验环境
PC微机
DOS操作系统或 Windows 操作系统
Turbo C 程序集成环境或 Visual C++ 程序集成环境
五．实验步骤
1．用学生选择的语言，设计出线性表的顺序和链表存储结构； 1． 设计出这两种存储结构下的线性表的插入、删除算法； 2． 用所选择的语言实现算法；
3． 测试程序,并对不同存储结构下的算法分析。
六．测试数据和分析
1．插入操作：
输入数据：L = ( ) ListInsert (L, 1, 'k'), 正确结果：L = (k)
输入数据：L = (EHIKMOP) ListInsert (L, 9, 't'), 正确结果：return ERROR; L = (EHIKMOP)
3
输入数据：L = (ABCEHKNPQTU) ListInsert(L, 4, 'u'), 正确结果： L = (ABCuEHKNPQTU)
2．删除操作：
输入数据：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'
3．如线性表有n个结点，对两种存储结构下插入和删除的时间复杂度进行分析。
七．实验结果
顺序存储C程序： #include
#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 }
status List_Insert(sqlist *L,int i,elemtype e){ //在第i个元素之前插入元素e
elemtype * p=0; elemtype *q=0;elemtype * newbase=0;
4
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;
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).listsize+=LISTINCREMENT; }
q=&((*L).elem[i-1]);
for(p=&((*L).elem[(*L).length-1]);p>=q;--p) *(p+1)=*p; *q=e;
++(*L).length; return OK; }
status GetElem(sqlist *L,int i,elemtype *e) {
(*e)=(*L).elem[i-1]; return OK; }
status List_Delete(sqlist *L,int i) {//删除线性表的第i个元素 if(i<1||i>(*L).length) return ERROR; elemtype *p; elemtype *q; p=&((*L).elem[i]); q=p-1;int num;
for(num=1;num<=((*L).length-i);num++) {(*q)=(*p); p++;q++; }
(*L).length--; return OK; }
status List_Travel(sqlist *L,status (* visit)(elemtype e)) {
//遍历线性表中的元素
int i=1; for (i=1;i<=((*L).length);i++)//循环（*L）.LENGTH次
{
printf(\第%d个元素为：\(* visit)((*L).elem[i-1]);
5