《数据结构实验指导书new》由会员分享，可在线阅读，更多相关《数据结构实验指导书new（15页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验指导书实验一 线性表的创建与应用一、 实验目的1、掌握线性表的定义2、 掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在链接存储结构上的运算。二、实验内容1、阅读并运行本实验程序（有序顺序表实现）2、用单链表方式实现本程序相应功能（有序单链表）3、利用有序单链表实现一元多项式的加法的功能。三、 实验要求1、 认真阅读和掌握本实验的参考程序（有序顺序表）。2、 上机运行该程序。3、 保存和打印出程序的运行结果，并结合程序进行分析。4、 按照有序顺序表功能，重新改写程序并运行，打印出文件清单和运行结果5、创建有序单链表时，要用头插法和尾插法同时实现。6、实现一元多项式的加法
2、的功能，并输出结果。7、最好能将结果写入到文本文件中。四、 注意事项：1、实验学时：4学时2、实验完成一周内提交实验报告（实验报告本）3、实验结果要求抓图打印4、严禁抄袭五、 实验附件程序（有序顺序表）Odsqlist.h文件：#define LIST_INIT_SIZE 8 /线性表存储空间的初始分配量#define LISTINCREMENT 10 /线性表存储空间的分配增量#define OVERFLOW -2#define ERROR 0#define OK 1#define TRUE 1#define FALSE 0typedef int Status;typedef int Ele
3、mType;typedef struct ElemType *elem; / 存储空间基址int length; / 当前长度int listsize; / 当前分配的存储容量( 以sizeof(ElemType)为单位)SqList; / 俗称 顺序表typedef SqList OdSqList; /有序顺序表Status InitList(OdSqList&); / 结构初始化void Destroy(OdSqList&); /销毁有序顺序表void ClearList(OdSqList&);/清空有序表Status ListEmpty(OdSqList);/判有序表为空int List
4、Length(OdSqList);/求表长int LocateElem(OdSqList,ElemType); / 查找void ListInsert(OdSqList&,ElemType); / 插入元素Status ListDelete(OdSqList&, int,ElemType& ); / 删除元素int ListDeletem(OdSqList&L, ElemType e); / 删除所有值为e的元素,返回删除的元素个数int ListDeletemn(OdSqList&, ElemType, ElemType ); / 删除所有值界于minkmaxk 的元素，并返回删除的元素个数
5、void ListTraverse(OdSqList);/遍历非递减有序线性表odsqlist.cpp文件：#include#include#include odsqlist.hStatus InitList( OdSqList& 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; / InitListvoid ListTraverse(
6、OdSqList L)/遍历线性表int i;printf(listsize is %d.n,L.listsize);printf(listlength is %d.n,L.length);printf(the list is:();for(i=1;i= L.listsize) / 当前存储空间已满，增加分配newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof (ElemType);if (!newbase) exit(OVERFLOW);/ 存储分配失败L.elem = newbase; / 新基址L.l
7、istsize += LISTINCREMENT; / 增加存储容量q = &(L.elem0); / q 指示第1个元素位置for (p = &(L.elemL.length-1);p=q&*pe; -p) *(p+1) = *p; / 插入位置及之后的元素右移*(p+1) = e; / 插入e+L.length; / 表长增1Status ListDelete(OdSqList &L, int i, ElemType &e) ElemType *p,*q;if (i L.length) return ERROR;/ 删除位置不合法p = &(L.elemi-1); / p 为被删除元素的位
8、置e = *p; / 被删除元素的值赋给 eq = L.elem+L.length-1; / 表尾元素的位置for (+p; p #include#include odsqlist.hvoid main()OdSqList L;int k;char i;ElemType e,mink,maxk;printf(OdSqList is initn);i=InitList(L);ListTraverse(L);while(1)printf(nnplease select:n);printf(1-insertn);printf(2-traversen);printf(3-deletein);print
9、f(4-deletekn);printf(5-deletemink-maxkn);printf(6-locaten);printf(7-isemptyn);printf(8-lengthn);printf(9-clearlistn);printf(0-quitn);scanf(%d,&k);switch(k)case 1:printf(please input e:);scanf(%d,&e);ListInsert(L,e);ListTraverse(L);scanf(%c,&i);printf(please press any key to continue);scanf(%c,&i);br
10、eak;case 2:ListTraverse(L);scanf(%c,&i);printf(please press any key to continue);scanf(%c,&i);break;case 3:while(1)printf(please input delete i:);scanf(%d,&i);if(ListDelete(L,i,e)=ERROR)printf(delete positon is error!n);else printf(Deleted elem is %dn,e);break;ListTraverse(L);scanf(%c,&i);printf(ple
11、ase press any key to continue);scanf(%c,&i);break;case 4:printf(please input delete e:);scanf(%d,&e);ListTraverse(L);printf(%d elem is deleted.n,ListDeletem(L,e);ListTraverse(L);scanf(%c,&i);printf(please press any key to continue);scanf(%c,&i);break;case 5:printf(please input delete mink and maxk:)
12、;scanf(%d%d,&mink,&maxk);ListTraverse(L);printf(%d elem is deleted.n,ListDeletemn(L,mink,maxk);ListTraverse(L);scanf(%c,&i);printf(please press any key to continue);scanf(%c,&i);break;case 6:printf(please input locate e:);scanf(%d,&e);i=LocateElem(L,e);if(i=0)printf(locate Defaulted!n);else printf(l
13、ocated no. is %dn,i);ListTraverse(L);scanf(%c,&i);printf(please press any key to continue);scanf(%c,&i);break;case 7:if(ListEmpty(L)printf(the orderlist is empty!n);elseprintf(the orderlist is not empty!n);scanf(%c,&i);printf(please press any key to continue);scanf(%c,&i);break;case 8:printf(length
14、is %d.n,ListLength(L);scanf(%c,&i);printf(please press any key to continue);scanf(%c,&i);break;case 9:ClearList(L);printf(the orderlist is empty!n);scanf(%c,&i);printf(please press any key to continue);scanf(%c,&i);break;case 0:Destroy(L);exit(1);break;实验二 栈（队列）的创建与应用一、 实验目的1. 掌握栈（队列）的基本操作：初始化栈（队列）、
15、判栈（队列）为空、出栈（队列）、入栈（队列）等运算。2. 掌握栈（队列）的应用方法，应用特点。二、实验要求1 认真阅读和掌握本实验提供的参考算法程序。2 上机实现实验内容算法。 3 保存和打印出程序的运行结果，并结合程序进行分析。三、实验内容1.表达式求值：已提供的表达式求值程序结构不好，请改进，要求用多文件方式实现，并将中序表达式变为后序表达式的结果写入文件。2.迷宫问题：已提供的迷宫问题算法程序有栈和队列实现两种方式，请你分别改进，要求用多文件方式实现，并将最终的路径写入文件。（以上提供的源码已随课件发给大家了）四、实验学时实验学时：2学时实验三 树的创建与应用一、实验目的1 掌握二叉树的二叉链表的定义方法。2 掌握基于二叉链表的二叉树的创建和遍历。3 掌握用线索
