《数据结构实验指导书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 ListL
4、ength(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的元素，并返回删除的元素个数vo
5、id 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(O
6、dSqList 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.length;i+)printf(%d ,L.elemi-1);printf()n);int LocateElem(OdSqList L, ElemType e)/ 在顺序表中查询第一个满足判定条件的数据元素，若存在，则返回它的位序，否则返回 0int i;i = 1; / i 的初值为第 1 元素的位序ElemType *p;p = L.e
7、lem; / p 的初值为第 1 元素的存储位置while (i = L.length & *p+!=e) +i;if (i = L.listsize) / 当前存储空间已满，增加分配newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof (ElemType);if (!newbase) exit(OVERFLOW);/ 存储分配失败L.elem = newbase; / 新基址L.listsize += LISTINCREMENT; / 增加存储容量q = &(L.elem0); / q 指示第1个元素位置
8、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 为被删除元素的位置e = *p; / 被删除元素的值赋给 eq = L.elem+L.length-1; / 表尾元素的位置for (+p;
9、p = q; +p) *(p-1) = *p; / 被删除元素之后的元素左移-L.length; / 表长减1return OK;void Destroy(OdSqList& L)/销毁有序顺序表free(L.elem);void ClearList(OdSqList& L)/清空有序表L.length=0;Status ListEmpty(OdSqList L)/判有序表为空if(L.length=0)return TRUE;else return FALSE;int ListLength(OdSqList L)/求表长return L.length;int ListDeletem(OdSq
10、List& L, ElemType e)/ 删除所有值为e的元素,返回删除的元素个数ElemType *p,*q,*r;int i=0;/删除的元素个数p=&L.elem0;/扫描指针for(q=&L.elemL.length-1;*pe&p=q;p+);if(p=q&*p=e)i+;for(r=p+1;*r=e&r=q;r+,i+);if(r=q)for(;r=q;r+,p+)*p=*r;L.length-=i;return i;int ListDeletemn(OdSqList& L, ElemType mink, ElemType maxk)/ 删除所有值界于minkmaxk的元素，并返
11、回删除的元素个数ElemType *p,*q,*r,temp;int i=0;if(maxkmink)temp=maxk;maxk=mink;mink=temp;p=&L.elem0;for(q=&L.elemL.length-1;*pmink&p=q;p+);/p指针指向第1个大于等于mink的元素if(p=q&*p=maxk)/若*p小于等于maxki+;for(r=p+1;*r=maxk&r=q;r+,i+);/r指针指向第1个大于maxk的元素if(r=q)for(;r=q;r+,p+)*p=*r;L.length-=i;return i;app.cpp文件:#include#incl
12、ude#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);printf(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);
