链式存储结构的基本操作-SuTree.doc

广州大学学生实验报告开课学院及实验室：计算机科学与工程实验室 2014年 4月28 日学院计算机科学与教育软件学院年级、专业、班计机115姓名苏权才学号1106100134实验课程名称数据结构成绩实验项目名称实验一 链式存储结构的基本操作指导老师一、实验目的掌握单链表，顺序表，链式队列的定义及基本操作二、使用仪器、器材微机一台操作系统：WinXP编程软件：C+三、实验内容及原理1、顺序表和单链表的定义和操作及*L和L两种接口变换；2、用*L和L接口实现队列。四、实验过程原始数据记录1、在list目录下新建工程使用.h和.cpp文件，并编译：2、将List1目录改为用L*标准实现。将List2目录改为用L标准实现，并实现_union功能。1）、将List1目录改为用L*标准实现#include using namespace std;# define maxsize 100typedef int ElemType;typedef structElemType datamaxsize; int length;SqList;void InitList(SqList *&L); int ListLength(SqList *L); int GetElem(SqList *L,int i,ElemType &e); int LocateElem(SqList *L,ElemType e); int ListInsert(SqList *&L,int i,ElemType e); /void InitList(SqList *&L) L=(SqList *)malloc(sizeof(SqList);L-length=0;int ListLength(SqList *L) return (L-length); int GetElem(SqList *L,int i,ElemType &e)if(iL-length)return 0;e=L-datai-1;return 1;int LocateElem(SqList *L,ElemType e)int i=0;while(ilength&L-datai!=e)i+;if(i=L-length)return 0;elsereturn i+1;int ListInsert(SqList *&L,int i,ElemType e)int j;if(iL-length+1)return 0;i-;for(j=L-length;ji;j-)L-dataj=L-dataj-1;L-datai=e;L-length+;return 1;#include list.hvoid main()void _union(SqList *L, SqList *S);/ElemType e;SqList *La,*Lb;InitList(La); InitList(Lb); ListInsert(La,1,3); ListInsert(La,2,7);ListInsert(La,3,28); ListInsert(Lb,1,7);ListInsert(Lb,2,29);_union(La,Lb);coutList As elements:;for (int i=0;i= ListLength(La)-1; i+)/if (GetElem(La, i, e)=1)coutdatai ;coutendl;/ void _union(SqList *L, SqList *S) ElemType e; int L_len=ListLength(L); int S_len=ListLength(S); for(int i=1;i= S_len;i+) /链表第一个节点存放头节点，开始节点从一开始 GetElem(S, i, e); if (LocateElem(L, e)=0) ListInsert(L, L_len+1, e) ; 2）、将List2目录改为用L标准实现#include using namespace std;# define maxsize 100typedef int ElemType;typedef structElemType datamaxsize; int length;SqList;void CreateList(SqList *&L,ElemType a,int n); void InitList(SqList *&L); void DestroyList(SqList *&L); int ListEmpty(SqList *L); int ListLength(SqList *L); void DispList(SqList *L); int GetElem(SqList *L,int i,ElemType &e); int LocateElem(SqList *L,ElemType e); int ListInsert(SqList *&L,int i,ElemType e); int ListDelete(SqList *&L,int i,ElemType &e); /void CreateList(SqList *&L,ElemType a,int n)int i;L=(SqList *)malloc(sizeof(SqList);for(i=0;idatai=ai;L-length=n;void InitList(SqList *&L) L=(SqList *)malloc(sizeof(SqList);L-length=0;void DestroyList(SqList *&L) free(L);int ListEmpty(SqList *L) return (L-length=0);int ListLength(SqList *L) return (L-length); void DispList(SqList *L)int i;if(ListEmpty(L) return ;for(i=0;ilength;i+)cout datai;/coutendl;int GetElem(SqList *L,int i,ElemType &e)if(iL-length)return 0;e=L-datai-1;return 1;int LocateElem(SqList *L,ElemType e)int i=0;while(ilength&L-datai!=e)i+;if(i=L-length)return 0;elsereturn i+1;int ListInsert(SqList *&L,int i,ElemType e)int j;if(iL-length+1)return 0;i-;for(j=L-length;ji;j-)L-dataj=L-dataj-1;L-datai=e;L-length+;return 1;int ListDelete(SqList *&L,int i,ElemType &e)int j;if(iL-length)return 0;i-;e=L-datai;for(j=i;jlength-1;j+)L-dataj=L-dataj+1;L-length-;return 1;#include List.hvoid main()ElemType f,a1; ElemType data5=a,b,c,d,e;SqList *L;InitList(L);CreateList(L,data,5);coutLs elememts: ;DispList(L);coutendl;coutLs length: ListLength(L)endl;coutIsnt empty table returns (0): ListEmpty(L)endl; GetElem(L,3,a1);coutThe value of the third element: a1endl;coutThe position of a: LocateElem(L,a)endl;ListInsert(L,3,f);coutInsert element f in the fourth: ;DispList(L);coutendl;ListDelete(L,4,f);coutDelete elements of f:;DispList(L);coutendl;DestroyList(L);3、链式队列的基本操作#include#include#includeusing namespace std;typedef struct node /定义连接队列类型char data;struct node *link;QNode,*QLink;int EMPTYQLINK(QLink &front) /测试链接队列是否为空return front=NULL;int ADDLINKQ(QLink &front,QLink &rear) /链接队列的插入char item=n;QLink p;coutitem;if(!(p=(QLink)malloc(sizeof(QNode)return 0;p-data=item; p-link=NULL;if(front=NULL)front=p; elserear-link=p;rear=p;return 1;int DELLINKQ(QLink &front) /链接队列的删除QLink p;if(EMPTYQLINK(front)return 0;p=front;front=p-link;free(p);return 1;char GETLINKQ(QLink &front) /取当前队头元素char item;if(EMPTYQLINK(front)return 0;item=front-data;DELLINKQ(front);return item;void main()int choice;QLink front=NULL,rear=NULL;docoutX;while(!_kbhit();cout键盘有输入.;choice=ADDLINKQ(front,rear);if(choice) cout键入字符已保存至缓冲区.;coutn输出缓冲区的字符:;while(choice)if(front!=rear) coutGETLINKQ(front);else choice=0;五、实验结果及分析1、在list目录下新建工程使用.h和.c