数据结构上机实验报告-单链表的实现

《数据结构上机实验报告-单链表的实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、华东交通大学软件学院上机/实验报告册专业____________________________班级____________________________姓名____________________________课程名称____________________________教师____________________________学期____________________________软件学院上机实验报告备注：学生应根据实验的要求，设计一个实验过程（包括程序代码、各种定义说明），并根据实验的结论

2、及实验过程中出现的情况（错误、异常等）得出的体会。要求学生每人一台计算机，独立完成实验的全过程。实验题目：单链表的实现实验目的：1.掌握单链表的逻辑结构2.掌握单链表的存储结构和结构特点3.掌握单链表基本操作的实现和指针的操作4.了解单链表基本操作的效率和特点实验要求：1.线性表的抽象数据类型2.单链表存储结构的C++语言定义3.单链表基本操作的实现：⑴初始化⑵销毁⑶创建⑷获取元素⑸插入⑹删除4.单链表的使用5.实验结果实验内容：1.线性表的抽象数据类型ADT线性表（List）Data线性表的数据对象集合为

3、{a1，a2,……,an}，每个元素的类型均为DataType。其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。OperationInitList（*L）：初始化操作，建立一个空的线性表L。ListEmpty（L）：若线性表为空，返回ture，否则返回false。ClearList（*L）：将线性表清空。GetElem（L,i,*e）:将线性表L中的第i个元素值返回给e。LocateElem（L,e）：在

4、线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则，返回0表示失败。2.单链表存储结构的C++定义：/*线性表的单链表存储结构*/typedefstructNode{Elemtypedata;StructNode*next;}Node;Node*Linklist;/*定义Linklist*/3.单链表基本操作的实现：㈠初始化：InitList(*L){L=(LinkList)malloc(sizeof(LinkList))L->next=NULLreturnL;}㈡销毁：/

5、*初始条件：线性表L已存在；操作结果：将L重置为空表*/StatusClearList(LinkList*L){LinkListp,q;p=(*L)->next;While(p){q=p->next;free(p);p=q;}(*L)->next=NULL;returnOK;}㈢创建：/*随机产生n个元素的值，建立带头结点的单链表L（头插法）*/VoidCreateListHead(LinkList*L,intn){LinkListp;intI;srand(time(0));*L=(LinkList)mal

6、loc(sizeof(Node));(*L)->next=NULL;For(i=0,idata=rand()%100+1;p->next=(*L)->next;(*L)->next=p;}}㈣获取元素：/*初始条件：顺序线性表L已存在，1≤i≤ListLength(L)*//*操作结果：用e返回L中第i个数据元素的值*/StatusGetElem(LinkListL,inti,ElemType*e){intj;LinkL

7、istp;p=L->next;j=1;while(!p==NULL&&jnext;++j;}if(!p

8、

9、j>i)returnERROR;*e=p->data;returnOK;}㈠插入：/*初始条件:线性表L已存在，1≤i≤ListLength(L)*//*操作结果：在L中第i个位置之前插入新的数据元素e，L长度加1*/StatusListInsert(LinkList*L,inti,ElemTypee){intj;LinkListp,s;p=*Lj=1;while(p&&j

10、p->next;++j;}If(!p

11、

12、j>i)returnERROR;s=(LinkList)malloc(sizeof(Node));s->data=e;s->next=p->next;p->next=s;returnOK;}㈡删除：/*初始条件：线性表L已存在，1≤i≤ListLength(L)*//*操作结果：删除L的第i个数据元素，并用e返回其值，L长度减1*/StatusListDelete(Link