数据结构实验指导09级.

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

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

3、gt;= L.listsize) newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType);if (!n ewbase) exit (OVERFLOW);L.elem = n ewbase;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 List

4、Delete_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.le ngth-1;for (+p; p <= q; +p)*(p-1) = *p;-L.le ngth;return OK;int locate_sq(SqList L ,elemtype x) / 查找算法 for(i=0;i<L.length;i+)If(L.elemi=x) return

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

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

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

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

9、调试通过并输出正确的结果。附录一：山东理工大学实验教学授课计划表附录二：实验一的源代码山东理工大学实验教学授课计划表1011学年第1 学期开课实验室名称计算机中心实验室课程名称数据结构课程代码052054开课时间2010.9总实验学时16课程类别主讲教师肖爱梅院（部）计算机科学与技术课程性质专业基础课开课班级计科09实验人数本科及实验者类别序 号实验项 目名称学时实验类别实验 要求实验类型实验计划时间（到周节）备注1线性表的顺序表示和实现2专业必选设计第三周周二7-8节2线性表的链式表示和实现2专业必选设计第四周周二7-8节3栈的实现及其应用2专业必选设计第六周周六3-4节4队列的实现及其应用

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

11、。5备注：改进/新开。附录二： C 语言实现：#include <stdio.h>#include <conio.h>#include <stdlib.h>#define OK 1#define ERROR 0#define OVERFLOW 0#define LIST_INIT_SIZE 100#define LISTINCREMENT 10 typedef int Status;typedef struct int *elem;int length;int listsize;SqList;int InitList_Sq(SqList *L) (*L).e

12、lem=(int *)malloc(LIST_INIT_SIZE*sizeof(int); if(!(*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 listinse

13、rt_sq(SqList *L,int i,int e) int *q,*p,*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(

14、p=&(*L).elem(*L).length-1);p>=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;/ 顺序表的删除vo

15、id output(SqList *L) cout<<" 输出序列为 :"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

16、);cout<<" 请输入插入位置 i 和插入的元素 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 的值： "<<e;cout<<endl

17、; output(&L);C+语言实现:#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<

18、;<" 值为 3 的元素位置为: "<<endl;cout<<a.locate(3)<<endl;a.remove(1);cout<<" 执行删除操作后数据为: "<<endl;a. printlist();sqlist.h 文件中进行如下的顺序表类定义const int MaxSize=100;template<class T>class sqlist public:sqlist()length=0;sqlist(T a,int n);void insert(int i,T

19、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<=MaxSize)