数据结构实验报告.doc

《数据结构》实验报告
专业计算机科学与技术
班级 3班
姓名李超
学号 1008010312
学期 11—12第一学期
指导老师刘勇
数据结构上机实验报告
学号: 姓名: 所在系: 班级:
实验名称: 线性结构基本算法的实现实验日期
实验指导教师刘勇实验机房
------------------------------------------------------------------------------------------------------
实验目的:
(1) 掌握线性表顺序存储结构的基本操作:插入、删除、查找;
(2) 掌握线性表链式结构的基本操作:插入、删除、合并等运算;
(3)掌握栈和队列基本运算的算法;
(4)掌握稀疏矩阵的压缩存储的算法。
2. 实验内容:
(1)实现顺序表的创建、插入、删除和查找的操作;
(2)实现单链表插入、删除、合并的操作;
(3)实现2个有序线性表的合并;
(4)利用顺序栈实现括号匹配的算法;
(5)实现顺序队列各种基本运算的算法;
(6)实现链栈各种基本运算的算法;(选做)
(7)实现链队列各种基本运算的算法;(选做)
(8)实现稀疏矩阵压缩存储的算法。
(编程思路或流程图)
内容:
顺序表的插入和删除
有序单链表的合并
数制转换的算法实现
快速转置算法的实现
顺序表的插入和删除
#include <>
#include <>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct{
ElemType *elem;
int length;
int listsize;
}SqList;
//顺序表初始化
int InitList(SqList *L)
{
L->elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L->elem)
exit(OVERFLOW);
L->length = 0;
L->listsize = LIST_INIT_SIZE;
return OK;
}
//顺序表插入
Status ListInsert(SqList *L,int i,ElemType e)
{
ElemType *newbase;
ElemType *p,*q;
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)
exit(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 ListDelete(SqList *L,int i,ElemType *e)
{
ElemType *p,*q;
if(i<1||i>L->length)
return ERROR;
p = &(L->elem[i-1]);
*e = *p;
q = L->elem + L->length-1;
for(++p;p<=q;++p)
*(p-1)=*p;
--L->length;
return OK;
}
//顺序表的合并
void MergeList(SqList La,SqList Lb,SqList *Lc)
{
ElemType *pa_last,*pb_last;
ElemType *pa,*pb,*pc;
pa = ;
pb = ;
Lc->listsize = Lc-