数据结构实验指导09级

1、实验一 线性表的顺序表示与实现1 实验目的(1) 掌握线性表的顺序存储结构；(2) 验证顺序表及其基本操作的实现；(3) 掌握数据结构及算法的程序实现的基本方法。2 实验内容（1） 建立含有若干个元素的顺序表；（2） 对已经建立的顺序表实现插入、删除、查找、合并等基本操作。3 实现算法首先，定义顺序存储结构如下：Typedef struct Elemtype *elem;Int length;Int listsize;sqlist;其次，建立含有n个元素的顺序表，算法如下：Status InitList_Sq( SqList & L ) / 构造一个空的顺序表 L.elem = (El

2、emType*) malloc (LIST_INIT_SIZE*sizeof (ElemType); if (!L.elem) exit(OVERFLOW);L.length = 0;L.listsize = LIST_INIT_SIZEreturn OK; 最后，对建立的顺序表设计插入、删除、查找等基本操作的算法如下：Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在顺序表L的第 i 个元素之前插入新的元素e if (i < 1 | i > L.length+1) return ERROR; if (L.lengt

3、h >= 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； Statu

4、s ListDelete_Sq (SqList &L, int i, ElemType &e) /删除算法if (i < 1) | (i > L.length) return ERROR; p = &(L.elemi-1); e = *p; q = L.elem+L.length-1; for (+p; p <= q; +p) *(p-1) = *p; -L.length; return OK; int locate_sq(SqList L ,elemtype x) /查找算法 for(i=0;i<L.length;i+) If(L.elemi=

5、x) return i+1; return 0;4根据上面设计的算法，用C/C+语言实现，调试通过并输出正确的结果。实验二 线性表的链式表示与实现1实验目的(1)掌握线性表的链接存储结构；(2)验证单链表及其基本操作的实现；(3)进一步掌握数据结构及算法的程序实现的基本方法。2实验内容（1）用头插法和尾插法建立含有若干个元素的带头结点的单链表；（2）对已经建立的单链表实现插入、删除、查找等基本操作。3实现算法4根据上面设计的算法，用C/C+语言实现，调试通过并输出正确的结果。实验三、四 栈与队列及其应用1实验目的(1)掌握栈的顺序存储结构和队列的链式存储结构；(2)掌握栈和队列的操作特性；(3

6、)掌握基于顺序栈和链队列的基本操作的实现方法。2实验内容（1）建立一个空栈；（2）对已经建立的栈实现入栈、出栈、取栈顶元素等基本操作。（3） 建立一个空队列；（4）对已经建立的队列实现插入、删除等基本操作3实现算法4根据上面设计的算法，用C/C+语言实现，调试通过并输出正确的结果。实验五 二叉树的应用1实验目的(1)掌握二叉树的逻辑结构；(2)掌握二叉树的二叉链表存储结构；(3)掌握基于二叉链表存储的二叉树的遍历操作的实现。2实验内容（1）建立一棵含有n个结点的二叉树；（2）前序（或中序、后序）遍历该二叉树； （3） 求该树叶子结点个数。3实现算法4根据上面设计的算法，用C/C+语言实现，调试

7、通过并输出正确的结果。实验六 图的遍历与应用1实验目的(1)掌握图的逻辑结构；(2)掌握图的邻接矩阵存储结构和邻接表存储结构；(3)掌握图的邻接矩阵存储结构和邻接表存储结构下遍历算法的实现。2实验内容（1）建立无向图的邻接矩阵存储；（2）对已经建立的无向图进行深度优先和广度优先遍历操作。 （3） 建立有向图的邻接表存储；（4）对已经建立的有向图进行深度优先和广度优先遍历操作。3实现算法 4根据上面设计的算法，用C/C+语言实现，调试通过并输出正确的结果。实验七 查找技术1实验目的(1)掌握顺序查找和折半查找算法的基本思想；(2)掌握顺序查找和折半查找算法的实现方法；(3)掌握顺序查找和折半查找

8、算法的时间性能。2实验内容 对给定的长度为n的数组，分别使用顺序查找、折半查找查找数组中与给定值k相等的元素。3实现算法4根据上面设计的算法，用C/C+语言实现，调试通过并输出正确的结果。实验八 内部排序1实验目的(1)掌握直接插入排序、冒泡排序和简单选择排序的基本思想；(2)掌握直接插入排序、冒泡排序和简单选择排序的实现方法；(3)掌握快速排序的基本思想和实现方法。2实验内容 对一组数据进行直接插入排序、冒泡排序、简单选择排序和快速排序。（升序）3实现算法4根据上面设计的算法，用C/C+语言实现，调试通过并输出正确的结果。附录一：山东理工大学实验教学授课计划表附录二：实验一的源代码山东理工大

9、学实验教学授课计划表10 11 学年第 1 学期开课实验室名称计算机中心实验室课程名称数据结构课程代码052054开课时间总实验学时16课程类别主讲教师肖爱梅院（部）计算机科学与技术课程性质专业基础课开课班级计科09实验人数及实验者类别 本科序号实验项目名称学时实验类别实验要求实验类型实验计划时间（到周节）备注1线性表的顺序表示和实现 2专业必选设计第三周周二7-8节2线性表的链式表示和实现2专业必选设计第四周周二7-8节3栈的实现及其应用 2专业必选设计第六周周六3-4节4队列的实现及其应用2专业必选设计第八周周六3-4节5二叉树及其应用 2专业必选设计第十周周二7-8节6图及其应用 2专业

10、必选设计第十二周周二7-8节7查找技术 2专业必选设计第十四周周二7-8节8内部排序2专业必选设计第十五周周二7-8节9101112131415教学部主任： 院(部)分管领导：注：1本表由任课教师填写，课程所在院（部）统一于每学期第一周报送实验室，跨院部的另报实验室管理科一份。本表留存实验室；2实验类别：基础 /技术（或专业）基础/专业/其他（含毕业论文和毕业设计的实验）；3实验类型：验证 /创新 /综合 /设计 /研究 /演示；4实验要求：必修 /选修；4备注：改进/新开 。4实验要求：必修 /选修。5备注：改进/新开 。附录二：C语言实现：#include <stdio.h>#

11、include <conio.h>#include <stdlib.h>#define OK 1#define ERROR 0#define OVERFLOW 0#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef int Status;typedef struct int *elem; int length; int listsize;SqList;int InitList_Sq(SqList *L) (*L).elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int); i

12、f(!(*L).elem) exit(OVERFLOW); (*L).length=0; (*L).listsize=LIST_INIT_SIZE; return OK; /创建顺序表 int CreateList_Sq(SqList *L) int i; cout<<"请输入数据:" for(i=0;i<(*L).length;i+) scanf("%d",&(*L).elemi); return OK; /顺序表赋值 Status listinsert_sq(SqList *L,int i,int e) int *q,*p,

13、*newbase; if(i<1|i>(*L).length+1) return ERROR; if(*L).length>=(*L).listsize) newbase=(int *)realloc(*L).elem,(*L).listsize+LISTINCREMENT)* sizeof(int); if(!newbase) exit(OVERFLOW); (*L).elem=newbase; (*L).listsize+=LISTINCREMENT; q=&(*L).elemi-1); for(p=&(*L).elem(*L).length-1);p&g

14、t;=q;-p) *(p+1)=*p; *q=e; +(*L).length; return OK; /顺序表的插入Status listdelete_sq(SqList *L,int i,int &e)int *p,*q;if(i<1|i>(*L).length) return ERROR;p=&(*L).elemi-1);e=*p; q=(*L).elem+(*L).length-1;for(+p;p<=q;+p) *(p-1)=*p; -(*L).length; return OK;/顺序表的删除 void output(SqList *L) cout&

15、lt;<"输出序列为:" int i; for(i=0;i<(*L).length;i+) cout<<" "<<(*L).elemi; cout<<endl; /输出函数 void main() int i,n,e; SqList L; InitList_Sq(&L); cout<<"请输入表长n:" cin>>n; L.length=n; CreateList_Sq(&L); output(&L); cout<<"

16、请输入插入位置i和插入的元素e的值：" cin>>i>>e; listinsert_sq(&L,i,e); cout<<endl; output(&L); cout<<"请输入删除位置i：" cin>>i; e=0; listdelete_sq(&L,i,e); cout<<"被删除的元素为第"<<i<<"位的"<<e; cout<<endl; output(&L);C+语言

17、实现：#include "iostream.h"#include "sqlist.h"void main()int r=1,2,3,4,5,6,7,8,9,10;sqlist <int> a(r,10);cout<<"执行插入操作前数据为："<<endl;a.printlist();a.insert(2,99); cout<<"执行插入操作后数据为："<<endl;a.printlist();cout<<"值为3的元素位置为：&quo

18、t;<<endl;cout<<a.locate(3)<<endl;a.remove(1); cout<<"执行删除操作后数据为："<<endl;a. printlist();文件中进行如下的顺序表类定义 const int MaxSize=100;template<class T>class sqlistpublic:sqlist()length=0;sqlist(T a,int n);void insert(int i,T x);T remove(int i);int locate(T x);void printlist();private:T elemMaxSize;int length;template<class T>sqlist<T>:sqlist(T a,int n)if(n>MaxSize) cout<< "参数非法" for(int i=0;i<n;i+)elemi=ai;length=n;template<class T>void sqlist<T>:insert(int i,T x)if(length&l