文档介绍：实验报告
实验课程:
学生姓名:
学号:
专业班级:
2012年 6月 5日
目录
(1)线性表及其应用 3
(2)栈和队列 11
(3)数组 18
(4)二叉树及其应用 28
(5)图的应用 33
(6)查找排序 38
计算机系数据结构实验报告
---(1)线性表及其应用
学生姓名: 学号: 专业班级:
实验类型:□验证□综合■设计□创新实验日期: 2012/3/18 实验成绩:
帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现,尤以链表的操作和应用作为重点。
构造一个空的线性表L;
在线性表L的第i个元素之前插入新的元素e;
在线性表L中删除第i个元素,并用e返回其值。
,并设计出在不同的存储结构中线性表的基本操作算法。
,对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行分析。
:
输入数据: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).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