抽象数据类型的表示与实现数据结构实验报告.doc

1、实 验 报 告 册实验报告（1）实验名称抽象数据类型的表示与实现同组人姓名实验性质 基本操作 验证性 综合性 设计性实验日期实验成绩教师评价：实验预习 实验操作 实验结果 实验报告 其它 教师签名：一、实验目的及要求1) 熟悉类C语言的描述方法，学会将类C语言描述的算法转换为C源程序实现；2) 理解抽象数据类型的定义，编写完整的程序实现一个抽象数据类型（如三元组）。3) 认真阅读和掌握本实验的参考程序，上机运行程序，保存和打印出程序的运行结果，并结合程序进行分析。二、实验内容线性表链式结构的创建，删除，插入等操作。线性表顺序结构的创建，删除，插入等操作。线性表顺序结构：一头文件：#ifndef

2、 _STDIO_H#define _STDIO_H#include stdio.h#include stdlib.h#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERLOW -2typedef int ElemType;typedef int Status;typedef structElemType *elem;int length;int listsize; SqL

3、ist;Status InitList_Sq(SqList &L);void Destory_Sq(SqList &L);void ClearList_Sq(SqList &L);Status ListEmpty(SqList &L);Status ListLength(SqList &L);Status GetElem_Sq(SqList &L,int i,ElemType e);Status LocateElem_Sq(SqList &L,ElemType e);Status ListInsert_Sq(SqList &L,int i,ElemType e);Status ListDele

4、te_Sq(SqList &L,int i,ElemType e);void unionlist_Sq(SqList &La,SqList &Lb);#endif二，功能实现函数#includeh1.hStatus InitList_Sq(SqList &L)L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)exit(OVERLOW);L.length=0;L.listsize=LIST_INIT_SIZE; return OK;void Destory_Sq(SqList &L)if(L.elem)free

5、(L.elem); L.elem=NULL;L.length=0;L.listsize=0;void ClearList_Sq(SqList &L)L.length=0;Status ListEmpty(SqList &L)if(L.length=0)printf(成功);return TRUE;else printf(失败);return FALSE;Status ListLength(SqList &L)return (L.length);Status GetElem_Sq(SqList &L,int i,ElemType e)if (iL.length)return FALSE;e=L.

6、elemi;printf(%d,e);return e;Status LocateElem_Sq(SqList &L,ElemType e)int i;for(i=1;i=L.length;i+)if(e=L.elemi)return i;return FALSE;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.listsi

7、ze+LISTINCREMENT)*sizeof(ElemType);if (!newbase)exit(-2);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 ListDelete_Sq(SqList &L,int i,ElemType e)int k;if(iL.length)return ERROR;e=L.elemi; for (k=i+1; k=L.length; k+) L.elemk-1=L.ele

8、mk;L.length-;return e;void unionlist_Sq(SqList &La,SqList &Lb)Status La_len,Lb_len;La_len=ListLength(La);Lb_len=ListLength(Lb);for(int i=1;i=Lb_len;+i)ElemType e;scanf(%d,&e);GetElem_Sq(Lb,i,e);if(!LocateElem_Sq(La,e) ListInsert_Sq(La,La.length+1,e);三，主函数#include h1.hvoid main()SqList l,lb;ElemType

9、i,a,e,j,k;doprintf( InitList-1n);printf( DestoryList-2n);printf( ClearList-3n);printf( ListEmpty-4n);printf( ListLength-5n);printf( GetElem-6n);printf( LocateElem-7n);printf( ListInsert-8n);printf( ListDelete-9n);printf( MergeList-10n);printf( 退出-0n);printf(请输入您的选择：);scanf(%d,&a);/while (a!=0);switc

10、h (a)case 1:InitList_Sq(l);break;case 2:Destory_Sq(l);break;case 3:ClearList_Sq(l);break;case 4:ListEmpty(l);break;case 5:k=ListLength(l);printf(长度为%dn,k);break;case 6:printf(请输入i en);scanf(%d %d,&i,&e);GetElem_Sq(l,i,e);printf(%dn,e);break;case 7:printf(请输入e:n);scanf(%d,&e);j=LocateElem_Sq(l,e);bre

11、ak;case 8:printf(请输入i e:n);scanf(%d %d,&i,&e);ListInsert_Sq(l,i,e);break;case 9:printf(请输入i e:n);scanf(%d %d,&i,&e);ListDelete_Sq(l,i,e);break;case 10:scanf(%d %d %d,&lb.elem,&lb.length,&lb.listsize);unionlist_Sq(l,lb);break;while (a!=0);线性表链式结构：一， 头文件#ifndef H #define H#include #include stdlib.h#de

12、fine ERROR 0#define OK 1typedef int ElemType;typedef int Status;typedef struct LNodeElemType length;ElemType data;struct LNode *next;LNode,*LinkList; void CreatList_L(LinkList &L,int n);Status GetElem_L(LinkList L,int i,ElemType &e);void ClearList_L(LinkList &L);Status ListInsert_L(LinkList &L,int i

13、,ElemType e);Status ListDelete_L(LinkList &L,int i,ElemType &e);Status ListLength(LinkList &L);#endif二， 功能实现函数#include h1.hvoid CreatList_L(LinkList &L,int n)int i;LinkList p=NULL;L=(LinkList)malloc(sizeof(LNode);L-next=NULL;for (i=n;i0;i-) p=(LinkList)malloc(sizeof(LNode);printf(输入第%d个数n,n);scanf(%

14、d,&p-data);p-next=L-next;L-next=p;+(L-length);Status GetElem_L(LinkList L,int i,ElemType &e)int j;LinkList p=NULL;p=L-next;j=1;while(p&jnext;+j;if(!p|ji)return ERROR;e=p-data;printf(%d,e);return OK;void ClearList_L(LinkList &L)LinkList p=NULL;while(L-next)p=L-next;L-next=p-next;free(p);Status ListDe

15、lete_L(LinkList &L,int i,ElemType &e)LinkList p,q;p = L;int j=0;while(p-next&jnext;+j;if(!(p-next)|ji-1)return ERROR;q=p-next;p-next=q-next;e=q-data;free(p);printf(删除成功);return OK;Status ListInsert_L(LinkList &L,int i,ElemType e)LinkList s,p=L;int j=0;while(p&jnext;+j;if(!p|ji-1)return ERROR;s=(Link

16、List)malloc(sizeof(LNode);s-data=e;s-next=p-next;p-next=s;return OK;Status ListLength(LinkList &L)return (L-length);三， 主函数#include h1.hvoid main()int i,n;ElemType e;LinkList l;doprintf(creat-1n);printf(insert-2n);printf(delete-3n);printf(clear-4n);printf(Get-5n);printf(Look-6n);printf(exit-0n);print

17、f(请输入您的选择：n);scanf(%d,&i);switch(i)case 1: printf(请输入n：n);scanf(%d,&n);CreatList_L(l,n);break;case 2: printf(输入i的值n);scanf(%d,&i);ListInsert_L(l,i,e);break;case 3: printf(输入i的值n);scanf(%d,&i);ListDelete_L(l,i,e);break;case 4: ClearList_L(l);break;case 5: printf(输入i的值n);scanf(%d,&i);GetElem_L( l,i,e)

18、;break;case 6:printf(长度为%dn,ListLength(l);break;while(i!=0);三、主要设备及软件PC机1台, VC 6.0 平台四、问题写程序其实一直是我的硬伤，特别是运行的时候总是会有这样或那样的问题，每次都搞得我接近崩溃，也只有不断不断的检查不断不断的修改，都把我的耐心修炼到极致了。实验报告（2）实验名称线性表实验同组人姓名实验性质 基本操作 验证性 综合性 设计性实验日期2012年10月25日实验成绩教师评价：实验预习 实验操作 实验结果 实验报告 其它 教师签名：一、实验目的及要求（1） 熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）

19、上的实现，以线性表的各种操作（建立、插入、删除等）的实现为实验重点；（2） 通过本次实验帮助学生加深对顺序表、链表的理解，并加以应用；（3） 掌握循环链表和双链表的定义和构造方法二、实验内容（1） 编程实现线性表两种存储结构（顺序存储、链式存储）中的基本操作的实现（线性表的创建、插入、删除和查找等），并设计一个菜单调用线性表的基本操作。（2） 建立一个按元素递增有序的单链表L，并编写程序实现：a） 将x插入其中后仍保持L的有序性；b） 将数据值介于min和max之间的结点删除，并保持L的有序性；c） （选做）将单链表L逆置并输出；（3） （选做）编程实现将两个按元素递增有序的单链表合并为一个新

20、的按元素递增的单链表。三、主要设备及软件PC机1台, VC 6.0 平台四、实验流程、操作步骤或核心代码、算法片段（1）：顺序存储define.h:#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef int Status;typedef int ElemType;typedef structElemType * elem;int length

21、;int listsize;SqList;Sqlist.h:Status InitList_Sq(SqList &L);Status ListInsert_Sq(SqList &L, int i, ElemType e);Status ListDelete_Sq(SqList &L, int i, ElemType &e);Status compare(ElemType a,ElemType b);int LocateElem_Sq(SqList L, ElemType e,Status (*compare)(ElemType, ElemType);Sqlist.cpp:#include de

22、fine.h#include #include using namespace std;Status InitList_Sq(SqList &L) L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType);if (!L.elem) return OK; L.length = 0; L.listsize = LIST_INIT_SIZE; return OK;Status ListInsert_Sq(SqList &L, int i, ElemType e) ElemType *p;if (i L.length+1) return E

23、RROR; if (L.length = L.listsize) ElemType *newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof (ElemType);if (!newbase) return ERROR; L.elem = newbase; L.listsize += LISTINCREMENT; ElemType *q = &(L.elemi-1); for (p = &(L.elemL.length-1); p=q; -p) *(p+1) = *p;*q = e; +L.length; re

24、turn OK;Status ListDelete_Sq(SqList &L, int i, ElemType &e) ElemType *p, *q;if (iL.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;Status compare(ElemType a,ElemType b)if(a=b)return 1;else return 0;int LocateElem_Sq(SqList L,

25、 ElemType e,Status (*compare)(ElemType, ElemType)int i;ElemType *p;i = 1; p = L.elem; while (i = L.length & !(*compare)(*p+, e) +i;if (i = L.length) return i;else return 0;main.cpp:#include define.h#include Sqlist.h#include using namespace std;void main(void)SqList L;int select,i;ElemType e;while (1

26、)cout1.InitListendl;cout2.ListInsertendl;cout3.ListDeleteendl;cout4.LocateElemendl;coutselect;switch (select)case 1:if(InitList_Sq(L)coutInitList OK !endl;break;case 2:couti;coute;if(ListInsert_Sq(L,i,e)coutInsert OK !endl;break;case 3:couti;if(ListDelete_Sq(L,i,e)coutDelete OK !endl;coutthe data is

27、 :eendl;break;case 4:coute;int to;if(to=LocateElem_Sq(L,e,compare)coutcompare e place is :toendl;break;链式结构：define.h:#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef struct LNodeElemType data;struct LNode

28、*next;LNode,*LinkList;List_L.h:#include define.hStatus GetElem_L(LinkList &L,int i, ElemType &e);Status ListInsert_L(LinkList &L, int i, ElemType e);Status ListDelete_L(LinkList &L, int i, ElemType &e);int LocateElem_L(LinkList &L,ElemType e);List_L.cpp:#include define.h#include Status GetElem_L(Lin

29、kList &L,int i, ElemType &e) LinkList p;p = L-next; int j = 1; while (p & jnext; +j;if ( !p | ji ) return ERROR; e = p-data; return OK;Status ListInsert_L(LinkList &L, int i, ElemType e) LinkList p,s;p = L; int j = 0;while (p & j next;+j; if (!p | j i-1) return ERROR; s = (LinkList)malloc(sizeof(LNo

30、de); s-data = e; s-next = p-next; p-next = s;return OK;Status ListDelete_L(LinkList &L, int i, ElemType &e) LinkList p,q;p = L;int j = 0;while (p-next & j next;+j;if (!(p-next) | j i-1) return ERROR; q = p-next;p-next = q-next; e = q-data;free(q);return OK; int LocateElem_L(LinkList &L,ElemType e)in

31、t i=0;while(L)i+;if(L-data=e)return i;break;L=L-next;return 0;main.cpp:#include List_L.h#include using namespace std;void main(void)int select,i;LinkList L;ElemType e;while(1)coutendl;cout1.GetElemendl;cout2.Insertendl;cout3.Deleteendl;cout4.LocateElemendl;coutselect;switch (select)case 1:couti;if(G

32、etElem_L(L,i,e)coutin the place is :eendl;break;case 2:couti;coute;if(ListInsert_L(L,i,e)coutInsert OK !endl;break;case 3:couti;if(ListDelete_L(L,i,e)coutDelete OK !endl;coutDelete data is:eendl;break;case 4:coute;int to;if(to=LocateElem_L(L,e)coutplace is :toendl;break;代码三：List.h:#include define.hS

33、tatus Init_L(LinkList &L);Status GetElem_L(LinkList &L,int i, ElemType &e);Status ListInsert_L(LinkList &L, int i, ElemType e); Status ListDelete_L(LinkList &L, int i, ElemType &e); define.h:#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int S

34、tatus;typedef int ElemType;typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;List.cpp:#include define.h#include const int N=50;Status Init_L(LinkList &L)int i;for(i=1;idata=i;L=L-next;L=0;return OK;Status GetElem_L(LinkList &L,int i, ElemType &e) LinkList p;p = L-next; int j = 1; while (p & jnext; +j;if ( !p | ji ) return ERROR; e = p-data; return OK;Status ListInsert_L(LinkList &L, int i, ElemType e) LinkList p,s;p = L; int j = 0;while (p & j next;+j; if (!p | j i-1) return ERROR; s = (LinkList)malloc(sizeof(LNode); s-data = e; s-next = p-next; p-next = s;r