数据结构实验说明书新版.doc_第1页
数据结构实验说明书新版.doc_第2页
数据结构实验说明书新版.doc_第3页
数据结构实验说明书新版.doc_第4页
数据结构实验说明书新版.doc_第5页
已阅读5页,还剩7页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

计算机系数据结构实验说明书上机实验是对学生的一种全面综合训练,是与课堂听讲,自学和练习相辅相成的必不可少的一个教学环节,实验着眼于原理与应用的结合。使学生能够利用书上的知识解决实际问题,同时也提高了学生的动手能力,起到了深化理解和灵活掌握教学内容的目的。实验一:线性表实验目的:在于帮助学生熟练掌握线性表的基本操作在两种存储结构上的实现,其中以各种链表的操作和应用为重点内容。实验题目: 1. 顺序表逆置算法. 2. 单链表的逆置算法.算法参考答案:1. 顺序表逆置算法.-结构的定义及宏定义- #define ERROR 0#define OK 1#define OVERFLOW -2#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef int ElemType;typedef struct ElemType *elem; int length; int listsize; Sqlist;typedef int Status;-初始化顺序表-Status 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_Sq(Sqlist *L,int i,ElemType e) ElemType *newbase,*q,*p; if (iL-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-elemi-1); for(p=&(L-elemL-length-1);p=q;-p) *(p+1)=*p; *q=e; +L-length; return OK;/*-顺序表的转置-*/Status rev(Sqlist *L) /*顺序表的输出函数*/void Output(Sqlist *L )/*-主函数-*/main() /验证部分2. 单链表的逆置算法.-结构定义及宏定义-#include malloc.h#define NULL 0#define ERROR 0#define OK 1typedef int ElemType;typedef int Status;typedef struct LNode ElemType data; struct LNode *next; LNode,*LinkList;-建立单链表-LinkList CreateList_L(int n) int i; LinkList L,p; L=(LinkList)malloc(sizeof(LNode); L-next=NULL; for(i=n;i0;-i) p=(LinkList)malloc(sizeof(LNode); scanf(%d,&p-data); p-next=L-next; L-next=p; return L; /*-单链表的转置函数-*/Status rev(LinkList L)/*单链表的输出函数*/void Output(LinkList L) /*-主函数-*/main()/验证部分实验二:栈与队列实验目的:使学生深入了解栈与队列的特性,以便在实际背景下灵活运用他们,同时还将巩固这两种结构的构造方法。实验题目:1. 检测表达式中,()扩号匹配算法. 2. 检测字符串是否回文的算法算法参考答案:-结构定义及宏定义-#include stdio.h;#include string.h#define STACK_INIT_SIZE 30#define STACKINCREMENT 10#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef int SElemType;typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;-初始化栈- Status InitStack(SqStack *S) S-base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S-base) return ERROR; S-top=S-base; S-stacksize=STACK_INIT_SIZE; return OK; -压栈- Status Push(SqStack *S,SElemType e) if(S-top-S-base=S-stacksize) S-base=(SElemType *)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(SElemType); if(!S-base) exit (OVERFLOW); S-top=S-base+S-stacksize; S-stacksize+=STACKINCREMENT; *S-top+=e; return OK; -出栈- Status Pop(SqStack *S,SElemType *e) if (S-top=S-base) return ERROR; *e=*-S-top; return OK; Status StackEmpty(SqStack *S) return (S-base=S-top); -取栈顶元素- Status GetTop(SqStack *S,SElemType *e) if(StackEmpty(S) return ERROR; *e=*(S-top-1); return OK; /*括号区配*/int pair(char *s) /*回文*/ int Ishuiwen(char *s) /*主函数*/main() /验证部分实验三:串实验目的: 掌握串的基本操作和在串上实现的模式匹配算法实验题目:1.串的模式匹配算法算法参考答案:-结构定义及宏定义-#include string.h#define NULL 0#define OVERFLOW -2#define OK 1#define ERROR 0typedef struct char *ch; int length;HString;typedef int Status;-生成堆串-Status StrAssign(HString *T,char *chars) int i,j; char *c; for(i=0,c=chars;ich=NULL;T-length=0; else if (!(T-ch=(char *)malloc(i*sizeof(char) exit(OVERFLOW); for(j=0;jchj=charsj; T-length=i; return OK;-串的模式区配-int Index(HString *T,HString *S,int pos) -主函数-main() /验证部分实验四: 数组实验目的: 数组的压缩存储方法及运算的实现,广义表的逻辑结构和存储结构实验题目:矩阵(三元组表示)相加的算法。算法参考答案:-结构定义及宏定义-#define MAXSIZE 100typedef int ElemType;typedef struct int i,j; ElemType e; Triple;typedef struct Triple dataMAXSIZE+1; int mu,nu,tu;TSMatrix;-生成三元组-void InitArray(TSMatrix *M,int col,int row) int i,j; ElemType d; M-mu=col; M-nu=row; M-tu=0; printf(Please input array data:); for(i=0;imu;i+) for(j=0;jnu;j+) scanf(%d,&d); if (d) M-tu+; M-dataM-tu.i=i; M-dataM-tu.j=j; M-dataM-tu.e=d; /*输出三元组*/void OutArray(TSMatrix *M) /*三元组相加*/void AddArray(TSMatrix *A,TSMatrix *B,TSMatrix *C) /*主函数*/main() 验证部分实验五 二叉树与树实验目的: 掌握二叉树的性质,二叉树的遍历,二叉树的线索化及构造赫夫曼树。二叉树上各种算法特别是递归算法的设计实验题目:1用先序方法建立一棵二叉树.( 二叉链表)算法. 2 中序遍历二叉树算法算法参考答案:-结构定义及宏定义-#include typedef struct BiTNodechar data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;-建立二叉树-BiTree CreateBiTree()BiTree T; char ch; scanf(%c,&ch); if(ch=#) T=NULL; else T=(BiTNode *)malloc(sizeof(BiTNode); if(!T) exit(-2); T-data=ch; T-lchild=CreateBiTree(); T-rchild=CreateBiTree(); return(T);/*-中序遍历*/void InOrder(BiTree T)/*主函数*/main()/验证部分实验六 图实验目的: 掌握图的定义和术语,图的四种存储结构(数组表示法,邻接表,十字链表和邻接多重链表)及图的两种遍历方法。图的连通性问题。拓扑排序和关键路径等问题。实验题目: 1 建立一个图(邻接表). 2 实现对图的深度遍历算法.算法参考答案:-结构定义及宏定义-#include #define MAX_VERTEX_NUM 20#define MAXQSIZE 30enum BOOL False,True;typedef struct ArcNodeint adjvex; struct ArcNode *nextarc;ArcNode;typedef structArcNode* AdjListMAX_VERTEX_NUM; int vexnum,arcnum; int GraphKind;Graph;typedef structint elemMAXQSIZE; int front; int rear;SqQueue;enum BOOL visitedMAX_VERTEX_NUM;-建立图-void CreateGraph(Graph *G) int i; int start,end; ArcNode *s; for(i=1;ivexnum;i+) G-AdjListi=NULL; for(i=1;iarcnum;i+) printf(input edge(1,2):); scanf(%d,%d,&start,&end); s=(ArcNode *)malloc(sizeof(ArcNode); s-nextarc=G-AdjListstart; s-adjvex=end; G-AdjListstart=s; if(G-GraphKind=0) s=(ArcNode *)malloc(sizeof(ArcNode);s-nextarc=G-AdjListend;s-adjvex=start;G-AdjListend=s; -深度遍历算法-void DFSTraverse(Graph *G)void DFS(Graph *G,int i)-主函数-main() /验证部分实验七 查找实验目的: 掌握静态查找表,动态查找表,及哈希表查找.实验题目: 1. 折半查找算法.算法参考答案:-折半查找算法-int binseach(int a,int data)-主函数-main() /验证部分实验八 内部排序实验目的: 掌握各种排序方法.(插入,快速,选择,归并,基数等)实验题目: 1. 快速排序算法. 2. 堆排序算法.算法参考答案:1. 堆排序算法.-结构定义及宏定义-#include #define MAXSIZE 20typedef structint elemwordMAXSIZE; int length;SqList;void InitialSqList();void HeapSort();void HeapAdjust();void PrintSqList();-初始化顺序表-void InitialSqList(SqList *L) int i; printf(input data num:); scanf(%d,&L-length); printf(input data:n); for(i=1;ilength;i+) s

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论