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

广州大学学生实验报告开课学院及实验室：计算机科学与工程实验室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*标准实现#includeiostreamusingnamespacestd;#definemaxsize100typedefintElemType;typedefstruct{ElemTypedata[maxsize];intlength;}SqList;voidInitList(SqList*&L);intListLength(SqList*L);intGetElem(SqList*L,inti,ElemType&e);intLocateElem(SqList*L,ElemTypee);intListInsert(SqList*&L,inti,ElemTypee);//////////////////////////////////////////////////////////////////////voidInitList(SqList*&L){L=(SqList*)malloc(sizeof(SqList));L-length=0;}intListLength(SqList*L){return(L-length);}intGetElem(SqList*L,inti,ElemType&e){if(i1||iL-length)return0;e=L-data[i-1];return1;}intLocateElem(SqList*L,ElemTypee){inti=0;while(iL-length&&L-data[i]!=e)i++;if(i=L-length)return0;elsereturni+1;}intListInsert(SqList*&L,inti,ElemTypee){intj;if(i1||iL-length+1)return0;i--;for(j=L-length;ji;j--)L-data[j]=L-data[j-1];L-data[i]=e;L-length++;return1;}#includelist.hvoidmain(){void_union(SqList*L,SqList*S);//ElemTypee;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);coutListA'selements:;for(inti=0;i=ListLength(La)-1;i++){//if(GetElem(La,i,e)==1)coutLa-data[i];}coutendl;}///////////////////////////////////////////void_union(SqList*L,SqList*S){ElemTypee;intL_len=ListLength(L);intS_len=ListLength(S);for(inti=1;i=S_len;i++){//链表第一个节点存放头节点，开始节点从一开始GetElem(S,i,e);if(LocateElem(L,e)==0)ListInsert(L,L_len+1,e);}}2）、将List2目录改为用L标准实现#includeiostreamusingnamespacestd;#definemaxsize100typedefintElemType;typedefstruct{ElemTypedata[maxsize];intlength;}SqList;voidCreateList(SqList*&L,ElemTypea[],intn);voidInitList(SqList*&L);voidDestroyList(SqList*&L);intListEmpty(SqList*L);intListLength(SqList*L);voidDispList(SqList*L);intGetElem(SqList*L,inti,ElemType&e);intLocateElem(SqList*L,ElemTypee);intListInsert(SqList*&L,inti,ElemTypee);intListDelete(SqList*&L,inti,ElemType&e);//////////////////////////////////////////////////////////////////////voidCreateList(SqList*&L,ElemTypea[],intn){inti;L=(SqList*)malloc(sizeof(SqList));for(i=0;in;i++)L-data[i]=a[i];L-length=n;}voidInitList(SqList*&L){L=(SqList*)malloc(sizeof(SqList));L-length=0;}voidDestroyList(SqList*&L){free(L);}intListEmpty(SqList*L){return(L-length==0);}intListLength(SqList*L){return(L-length);}voidDispList(SqList*L){inti;if(ListEmpty(L))return;for(i=0;iL-length;i++)coutL-data[i];//coutendl;}intGetElem(SqList*L,inti,ElemType&e){if(i1||iL-length)return0;e=L-data[i-1];return1;}intLocateElem(SqList*L,ElemTypee){inti=0;while(iL-length&&L-data[i]!=e)i++;if(i=L-length)return0;elsereturni+1;}intListInsert(SqList*&L,inti,ElemTypee){intj;if(i1||iL-length+1)return0;i--;for(j=L-length;ji;j--)L-data[j]=L-data[j-1];L-data[i]=e;L-length++;return1;}intListDelete(SqList*&L,inti,ElemType&e){intj;if(i1||iL-length)return0;i--;e=L-data[i];for(j=i;jL-length-1;j++)L-data[j]=L-data[j+1];L-length--;return1;}#includeList.hvoidmain(){ElemTypef,a1;ElemTypedata[5]={'a','b','c','d','e'};SqList*L;InitList(L);CreateList(L,data,5);coutL'selememts:;DispList(L);coutendl;coutL'slength:ListLength(L)endl;coutIsn'temptytablereturns(0):ListEmpty(L)endl;GetElem(L,3,a1);coutThevalueofthethirdelement:a1endl;coutThepositionofa:LocateElem(L,'a')endl;ListInsert(L,3,'f');coutInsertelementfinthefourth:;DispList(L);coutendl;ListDelete(L,4,f);coutDeleteelementsoff:;DispList(L);coutendl;DestroyList(L);}3、链式队列的基本操作#includeiostream#includemalloc.h#includeconio.husingnamespacestd;typedefstructnode//定义连接队列类型{chardata;structnode*link;}QNode,*QLink;intEMPTYQLINK(QLink&front)//测试链接队列是否为空{returnfront==NULL;}intADDLINKQ(QLink&front,QLink&rear)//链接队列的插入{charitem='\n';QLinkp;cout\n读入用户键入的字符:;while(item!='0'){cinitem;if(!(p=(QLink)malloc(sizeof(QNode))))return0;p-data=item;p-link=NULL;if(front==NULL)front=p;elserear-link=p;rear=p;}return1;}intDELLINKQ(QLink&front)//链接队列的删除{QLinkp;if(EMPTYQLINK(front))return0;p=front;front=p-link;free(p);return1;}charGETLINKQ(QLink&front)//取当前队头元素{charitem;if(EMPTYQLINK(front))return0;item=front-data;DELLINKQ(front);returnitem;}voidmain(){intchoice;QLinkfront=NULL,rear=NULL;do{coutX;}while(!_kbhit());cout键盘有输入.;choice=ADDLINKQ(front,rear);if(choice)cout键入字符已保存至缓冲区.;cout\n输出缓冲区的字符:;while(choice){if(front!=rear){coutGETLINKQ(front);}elsechoice=0;}}五、实验结果及分析1、在list目录下新建工程使用.h和.cpp文件，并编译：2、将List1目录改为用L*标准实现。将List2目录改为用L标准实现，并实现_union功能。1）、将List1目录改为用L*标准实现2）、将List2目录改为用L标准实现3、链式队列的基本操作六、实验心得通过本实验，了解了顺序表、单链表及队列的定于和基本操作，掌握了顺序表两种定义接口List*L和ListL的实现模式，对单链表的ListL理解不足还不能掌握。同时也知道了链表的数据存储从data[1]开始，data[0]位置为头结点。