单链表实验报告及程序.doc

数据结构与算法实验课程-单链表兰州财经大学班级： 姓名： 学号： 指导老师：目录一前言21.1实验目的21.2 实验内容21.3 实验环境3二需求分析32.1线性表32.2抽象数据类型线性表定义32.3 线性表的链式表示42.3.1链接存储方法42.3.2链表的结点结构52.3.3头指针head和终端结点指针域的表示52.3.4单链表类型描述52.3.5指针变量和结点变量6三编程实现63.1主要函数代码63.1.1主程序63.2单链表的建立、插入、删除等操作。11四.测试调试与结果分析134.1正常测试数据及运行结果13五收获及体会17六.参考文献17一前言1.1实验目的掌握单链表的基本操作，插入、删除、查找等算法的实现。1.2 实验内容(1)初始化单链表。 (2)在单链表中插入一个新结点。(3)删除单链表中的某一个结点。 (4)在单链表中查找某结点并返回其位置。(5)打印输出La中的结点元素值1.3 实验环境1、硬件：PC/4G内存/512G硬盘/100M /NIC2、软件：操作系统Windows 7Microsoft Visual Studio 6.0 集成开发环境VC+6.0二需求分析2.1线性表1、线性表概念：n个数据元素组成的有限序列。表示为（a1，a2，ai，ai+1，an)。2、逻辑特征：（1）1in时，ai的直接前驱是ai-1，a1无直接前驱；ai的直接后继是ai+1，an无直接后继。（2）元素同构，且不能出现缺项。2.2抽象数据类型线性表定义通常采用抽象数据类型研究数据结构。线性表查询数据类型如下：ADT List 数据对象：D ai | ai ElemSet，i=1,2,.,n, n0 数据关系：R1 |ai-1 ,aiD, i=2,.,n 基本操作： InitList( &L ) 操作结果：构造一个空的线性表L。DestroyList( &L ) 初始条件：线性表L已存在。 操作结果：销毁线性表L。 ListEmpty( L ) 初始条件：线性表L已存在。 操作结果：若L为空表，则返回TRUE，否则FALSE。 ListLength( L ) 初始条件：线性表L已存在。GetElem( L, i, &e ) 初始条件：线性表L已存在，1iListLength (L)操作结果：用e返回L中第i个元素的值。 LocateElem( L, e, compare( ) ) 初始条件：线性表L已存在，compare( )是元素判定函数。 操作结果：返回L中第i个与e满足关系compare( )的元素的位序。若这样的元素不存在，则返回值为0。 操作结果：返回L中元素个数。PriorElem( L, cur_e, &pre_e ) 初始条件：线性表L已存在。 操作结果：若cur_e是L的元素，但不是第一个，则用pre_e 返回它的前驱，否则操作失败，pre_e无定义。NextElem( L, cur_e, &next_e ) 初始条件：线性表L已存在。 操作结果：若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。ListTraverse(L, visit( ) 初始条件：线性表L已存在。 操作结果：依次对L的每个元素调用函数visit( )。一旦visit( )失败，则操作失败。ClearList( &L ) 初始条件：线性表L已存在。 操作结果：将L重置为空表。PutElem( L, i, &e ) 初始条件：线性表L已存在，1i ListLength (L) 操作结果：L中第i个元素赋值同e的值。ListInsert( &L, i, e ) 初始条件：线性表L已存在，1i ListLength (L) +1 操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。ListDelete(&L, i, &e) 初始条件：线性表L已存在且非空，1i ListLength (L) 操作结果：删除L的第i个元素，并用e 返 回其值，L的长度减1。 ADT List2.3 线性表的链式表示2.3.1.链接存储方法链接方式存储的线性表简称为链表（Linked List），链表的具体存储表示为： 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的） 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）注意：链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。2.3.2.链表的结点结构datanextdata域-存放结点值的数据域next域-存放结点的直接后继的地址（位置）的指针域（链域）注意：链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。每个结点只有一个链域的链表称为单链表（Single Linked List）。2.3.3、头指针head和终端结点指针域的表示单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。2.3.4、单链表类型描述typedef char DataType; /假设结点的数据域类型为字符typedef struct node/结点类型定义DataType data;/结点的数据域struct node *next;/结点的指针域ListNode;typedef ListNode *LinkList;ListNode *p;LinkList head;2.3.5指针变量和结点变量三编程实现3.1主要函数代码3.1.1主程序#includelinklist.h#includeFILE*fp;LinkList LL,p;Status Cmp(ElemType e1, ElemType e2)if(!strstr(e1.num,e2.num) return OK;return ERROR;/*Status Cmp(ElemType e1, ElemType e2)if(e1=e2) return OK;return ERROR;*/int savedata(LinkList L,char *file)char str50;int i;LinkList p;if(fp=fopen(file,wt)=NULL)printf(Cannot open file strike any key exit!);/getch();exit(1);/for(i=0;inext;while(p)/sprintf(str,%s - %s - %d - %dn,(p-data).no,(p-data).name,(p-data).age,(p-data).score);sprintf(str,%dn,p-data);fputs(str,fp);/printf(%s,str);p=p-next;fclose(fp);return OK;/int opendata(SqList &L,char *file)int opendata(LinkList &L,char *file)char str50;ElemType e;if(fp=fopen(file,rt)=NULL)printf(Cannot open file strike any key exit!);/getch();exit(1);/for(i=0;i=L.length-1;i+)while(fgets(str,50,fp)/fgets(str,50,fp);/printf(%s,str);/sprintf(str,n %s - %s - %d - %d ,L.elemi.no,L.,L.elemi.age,L.elemi.score);/sscanf(str,%s - %s - %d - %d,e.no,,&(e.age),&(e.score) );sscanf(str,%d,&e);printf(n %d ,e);/printf(n|%8s|%9s|%10d|%11d| ,e.no,,e.age,e.score);/ListInsert_Sq(L,1,e);ListInsert_L(L,1,e);fclose(fp);return OK;void main()ElemType e;int se,cntl,i;/*InitList_Sq(sq) ;for(int i=0;i5;i+)scanf(%s%s%s%d,e.num,,e.gender,&e.score);ListInsert_Sq(sq, 1, e) ;printf(nNo Name Gender Scoren);for(i=1;i=sq.length;i+)GetElem_Sq(sq,i, e);printf(n%10s%12s%8s%5d,e.num,,e.gender,e.score);DestroyList_Sq(sq);*/*InitList_L(LL) ;for( i=0;i5;i+)/scanf(%s%s%s%d,e.num,,e.gender,&e.score);scanf(%d,&e);ListInsert_L(LL, 1, e) ;/printf(nNo Name Gender Scoren);/for(i=1;inext;i=1;while(p)GetElem_L(LL,i, e);i+;p=p-next;/printf(n%10s%12s%8s%5d,e.num,,e.gender,e.score);printf( %d ,e);DestroyList_L(LL);*/cntl=1;while(cntl)/clr();printf(n%30s单链表基础实验测试, );printf(nn%20s=, );printf(n%20s1.单链表建立, );printf(n%20s2.插入, );printf(n%20s3.删除, );printf(n%20s4.查找, );printf(n%20s5.保存链表信息, );printf(n%20s6.读取链表信息, );printf(n%20s7.列表输出, );printf(n%20s0.退出, );printf(nn%20s=, );printf(n请选择(0-7)：);scanf(%d,&se);cntl=1;switch(se)case 0:cntl=0;DestroyList_L(LL);break;case 1:InitList_L(LL) ;break;case 2:/scanf(%s%d%d,,&e.x,&e.y);scanf(%d,&e);ListInsert_L(LL, 1, e) ;break;case 3:/scanf(%s%d%d,,&e.x,&e.y);printf(n输入要删除数据的位置);scanf(%d,&i);if(ListDelete_L(LL, i, e)=OK)printf( %d ,e);elseprintf(n没找到);break;case 4:printf(n输入要查询数据);scanf(%d,&e);LinkList p;p=LocateElem_L(LL, e, Cmp);if(p)/printf(n%60s%8d%5d,,p-data.x,p-data.y);printf( %d ,e);elseprintf(n没找到);break;case 7:for(i=1;i=1000;i+)if (GetElem_L(LL,i, e)=ERROR)break;/printf(n%60s%8d%5d,,e.x,e.y);printf( %d ,e);break;case 5:savedata(LL,e:mydata.dat);break;case 6:opendata(LL,e:mydata.dat);break;3.2单链表的建立、插入、删除等操作。/#include#includelinklist.hStatus InitList_L(LinkList &L) / 构造一个空的线性表L。 L = (LinkList )malloc(sizeof(LNode); if (!L ) return ERROR; / 存储分配失败 L-next = NULL; return OK; / InitList_SqStatus ListInsert_L(LinkList L, int i, ElemType e) / 算法2.4 / 在顺序线性表L的第i个元素之前插入新的元素e， / i的合法值为1iListLength_Sq(L)+1 LinkList p,s; int j; / L 为带头结点的单链表的头指针，本算法 / 在链表中第i 个结点之前插入新的元素 e p = L; j = 0;while (p & j next; +j; / 寻找第 i-1 个结点if (!p | j i-1) return ERROR; / i 大于表长或者小于1 s = (LinkList) malloc ( sizeof (LNode); / 生成新结点s-data = e; s-next = p-next; p-next = s; / 插入return OK; / LinstInsert_LStatus ListDelete_L(LinkList L, int i, ElemType &e) / 算法2.5 / 在顺序线性表L中删除第i个元素，并用e返回其值。 / i的合法值为1iListLength_Sq(L)。 LinkList p, q; int j; p = L; j = 0;while (p-next & j next; +j; / 寻找第 i 个结点，并令 p 指向其前趋if (!(p-next) | j i-1) return ERROR; / 删除位置不合理 / 表长减1q = p-next; p-next = q-next; / 删除并释放结点e = q-data; free(q);return OK; / ListDelete_SqLinkList LocateElem_L(LinkList L, ElemType e, Status (*compare)(ElemType, ElemType) / 在顺序线性表L中查找第1个值与e满足compare()的元素的位序。 / 若找到，则返回其在L中的位序，否则返回0。/ int i; LinkList p; /ElemType *p; / i = 1; / i的初值为第1个元素的位序 p = L-next; / p的初值为第1个元素的存储位置 while (p & !(*compare)(p-data, e) p=p-next; return p; / LocateElem_LStatus GetElem_L(LinkList L,int i, ElemType &e)/ L是带头结点的链表的头指针，以 e 返回第 i 个元素LinkList p;int j;p = L-next; j = 1; / p指向第一个结点，j为计数器while (p & jnext; +j; / 顺指针向后查找，直到 p 指向第 i