数据结构实验报告—链表

1、算法与数据结构课程实 验 报 告教师评阅意见:签名：年 月曰实验成绩:一、实验目的1、实现线性表的链式存储结构(链表)。2、熟悉C+程序的基本结构，掌握程序中的头文件、实现 文件和主 文件之间的相互关系及各自的作用。3、熟悉链表的基本操作方式，掌握链表相关操作的具体实现。二、实验内容及要求对链式存储结构的线性表进行一些基本操作。主要包括：(1)插入：操作方式为在指定元素前插入、在指定元素之后插入、在 指定位置完成插入(2)删除：操作方式可分为删除指定元素、删除指定位置的元素等， 尝试实现逻辑删除操作。(3)显示数据。(4)查找：查询指定的元素(可根据某个数据成员完成查询操作)。(5)定位操作：

2、定位指定元素的序号。(6)更新：修改指定元素的数据。(7)数据文件的读写操作等。其它操作可根据具体需要自行补充。三、系统分析(1)数据方面：该链表数据元素类型采用整型，并且约定该链表不能存储 0元 素，在此基础上进行链表相关操作，链表上的数据采用文件保存，并且可在之前 文件数据基础上进行链表操作。(2)功能方面：能够实现链表的一些基本操作，主要包括：1 .可以通过前插法、后插法两种方式进行链表的创建，并将数据保存至文本 文档中。2 .可以在原有文本文档数据的基础上进行相关操作3 .计算链表中存储元素个数即当前长度。4 .能够进行搜索操作，可返回搜索项所在地址，也可通过搜索数据项返回该元素地址。

3、5 .能够进行取值操作，根据用户需求取出表中某项的值。6 .能够进行修改操作，在用户选择修改项后将输入内容修改到对应位置。7 .能够进行插入操作，在用户选择合理位置后输入插入元素值。8 .能够进行删除操作，用户根据选择表中项数删除对应数据。9 .能够进行判断表空或表满。10 .能够进行排序操作，能够将链表中存在的元素进行从小到大排序。11 .采用文本文档保存数据。四、系统设计（ 1）设计的主要思路链表结构是一种使用对象引用变量来创建对象间联系的数据结构。 根据实验要求， 以及课上老师对于链表各个操作的讲解， 在了解链表操作原理后将链表的模板类完成， 并将各个功能代码的实现编写完成， 基本代码完

4、成后， 在实现编写菜单界面进行调试。 由于要求用文件操作处理链表数据， 故决定使用两个菜单进行关联。 第一个菜单用于用户通过文件操作创建链表， 第二菜单用于实现链表各个功能的调试操作。（ 2）数据结构的设计链式结构是一种使用对象引用变量来创建对象间的链的数据结构， 对象引用变量可用于创建链式结构对象引用变量所存储的特定地址一般无关紧要。 换句话说， 重要的是能够使用引用变量来访问对象， 而对象在内存中的特定存储位置并不重要。 在了解链式结构的基本原理后， 故通过构建一个类属性为每一个链表结点数据域与指针域，在此基础上实现链表的各项操作。（ 3）基本操作的设计链表中关键的算法就是搜索、插入、删除

5、以及排序操作。在单链表中进行搜索操作， 只能从链表的首结点开始， 通过每个结点的指针域来依次访问链表中的每个结点以完成相应的搜索操作。在搜索操作中通过用户输入需要搜索的数据x ，搜索成功返回该结点的地址，否则返回NULL 值，也可通过用户输入结点位置返回结点所处地址。 单链表的插入操作需要用户输入两个数据分别是插入点的位置以及插入值。 在单链表中插入算法不需要移动元素， 只需要修改元素的指针即可。 具体操作则是通过指针操作指明新结点的后继与前驱。 在单链表中的删除算法则是类似于插入算法。 值得注意的是， 在设计该单链表为了使程序更加简洁，在单链表的最前面添加了头结点。 在头结点中不存储任何实质

6、的数据对象， 其指针域指向第一个数据所在的结点。 这样就可以在执行插入、 删除算法时代码更为 简洁。五、编程环境与实验步骤（ 1）编程环境操作系统： Windows 操作系统；编程工具软件： Visual Studio 2017（ 2）实验步骤只说明程序相关的各种文件创建步骤及文件的作用，不需说明文件的具体内容。程序相关文件为 LinkNode.h 头文件、 List.h 头文件以及主函数调试文件 main.cpp。（ 3）编译参数无编译参数，在Vs2017或其他版本中新建项目然后将三个文件 LinkNode.h、List.h、main.cpp添加到解决方案中的头文件中调试即可。六、实现代码#

7、include <iostream> #include <fstream> #include "LinkNode.h" using namespacestd;template <class T> class List protected :LinkNode<T> *first; public :List() first =new LinkNode<T>List( constfirst =T& x) new LinkNode <T >( x);/ 复制构造函数/ 析构函数/ 将链表置为空表/ 计算

8、链表的长度List( List <T>& L);List() makeEmpty(); void makeEmpty();int Length();LinkNode<T> *getHead() return first;/ 返回附加头结点地址搜索含数据x的元素/ 搜索第 i 个元素的地址取出第 i 个元素的值用x修改第i个元素的值在第 i 个元素后插入 x删除第 i 个元素，x 返回该元素的值true : false ;/ 判表空否？空则返回 trueLinkNode<T> *Search( T x);/LinkNode<T> *Loca

9、te( int i );boolgetData( inti, T& x);/voidsetData( inti, T& x);/boolInsert( inti,T& x);/boolRemove(inti,T& x);/bool IsEmpty() return first->link = NULL?bool IsFull() return false ;voidSort();/voidinputFront(TendTag);/voidinputRear(TendTag);/voidpreviousData(T endTag);voidoutput();

10、voidoutputFile();/List <T>& operator= ( List <T>& L);/ 判表满否？不满则返回 false排序前插法输入后插法插入/ 打开原有链表数据文件数据文件/ 输出输出到文件/ 重载函数：赋值;/* * 复制构造函数*/ template <class T>List <T>:List( List <T>& L) T value;LinkNode<T> *srcptr = L.getHead();LinkNode<T> *destptr = fir

11、st = new LinkNode < T >while (srcptr->link != NULL) value = srcptr->link->data;destptr->link = new LinkNode<T>(value);destptr = destptr->link;srcptr = srcptr->link;destptr->link = NULL;/* * 将链表置为空表*/template <class T>void List <T>:makeEmpty() LinkNode<

12、T> *q;while (first->link != NULL) q = first->link;first->link = q->link; delete q;/* * 计算带附加结点的单链表的长度*/ template <class T>intint count = 0;List <T>:Length() LinkNode<T> *p = first->link; while (p != NULL) p = p->link; count+;return count;/*在表中搜索含数据x的结点，搜索成功时函数返

13、回该结点地址，否则返回NULL!*/ template <class T>LinkNode<T> * List <T>:Search( T x) LinkNode<T> *current = first->link;while (current != NULL) if (current->data = x)break ;elsecurrent = current->link;/* 定位函数：返回表中第*/ returncurrent;i 个元素的地址。若i<0 或 i 超出表中的结点个数，则返回 NULLtemplate

14、<class T>LinkNode<T> * List <T>:Locate( int if ( i < 0)i) return NULL;LinkNode<T> *current = first;int k = 0;while (current != NULL&& k < current = current->link; k+;i) return current; /* 取出链表中第i 个元素的值*/template <class T>boolList <T>:getData( int

15、i , T& x) if ( i <= 0) return NULL;LinkNode<T> *current = Locate( i );if (current = NULL) return false ;else x = current->data; return true ;/* 给链表中第i 个元素赋值x* /template <class T>voidList <T>:setData( int i , T& x) if ( i <= 0) return ;LinkNode<T> *current = L

16、ocate( i );if (current = NULL) return ;else current->data = x;/* 将新元素x插入在链表中第i个结点之后* /template <class T>bool List <T>:Insert( int i , T& x) LinkNode<T> *current = Locate( i );if (current = NULL) return false ;LinkNode<T> *newNode = new LinkNode<T>(x);if (newNode

17、= NULL) cerr << " 存储分配错误！ " << endl; exit(1);newNode->link = current->link;current->link = newNode;return true ;* 将链表中的第i 个元素删去，通过引用型参数x 返回该元素的值*/template <class T>boolList < T >:Remove( int i , T& x) LinkNode<T> *current = Locate( i - 1);if (curr

18、ent = NULL| current->link = NULL)return false ;LinkNode<T> *del = current->link; current->link = del->link;x = del->data; delete del;return true ;/* 单链表的输出函数：将单链表中所有数据按逻辑顺序输出到屏幕上*/template <class T>voidList <T>:output() LinkNode<T> *current = first->link; wh

19、ile (current != NULL) cout << current->data <<current = current->link;cout << endl;/*重载函数：赋值操作，形式如 A=B其中娓调用此操作的List对象，B是与参数表中的引用型参数L结合的实参*/template <class T>List<T>& List <T>: operator= ( List <T>& L) T value;LinkNode<T> *srcptr = L.getHe

20、ad();LinkNode<T> *destptr = first =new LinkNode<T>while (srcptr->link !=NULL) value = srcptr->link->data;destptr->link = new LinkNode<T>(value);destptr = destptr->link; srcptr = srcptr->link;destptr->link = NULL;return * this ;/* * 后插法实现输入函数：链表中各结点中数据的逻辑顺序与输入数据

21、顺序一致*endTag是约定的输入序列结束的标志*/template <class T>void List <T>:inputRear( T endTag) LinkNode<T> *newNode, *last;T val;makeEmpty();fstream file( "List.txt" , ios :out);if ( ! file) cout << " 文件不能打开！ " << endl;else cin >> val;file << val <<

22、;" " ;last = first;while (val != endTag) newNode = new LinkNode <T>(val);if (newNode = NULL) cerr << "存储分配错误！ " << endl; exit(1);last->link = newNode; last = newNode;cin >> val;file << val <<" " ;last->link = NULL;file.close();/

23、* 前插法实现输入函数：链表中各结点中数据的逻辑顺序与输入数据顺序相反*endTag是约定的输入序列结束的标志*/template <class T>void List <T>:inputFront( T endTag) LinkNode<T> *newNode; T val;makeEmpty();fstream file( "List.txt" , ios :out);if ( ! file) cout << " 文件不能打开！ " << endl;else cin >> val

24、;file << val <<" " ;while (val != endTag) newNode = new LinkNode <T>(val);if (newNode = NULL) cerr << " 存储分配错误！ " << endl; exit(1);newNode->link = first->link;first->link = newNode;cin >> val;file << val <<file.close();/* 将

25、之前数据文件中数据放入链表中在进行后续操作*/template <class T>voidList <T>:previousData( T endTag) LinkNode<T> *newNode, *last;T val;makeEmpty();ifstream file( "List.txt" );if (! file) cout << " 文件不能打开！ " << endl;elsefile >> val;last = first;while (val != endTag) n

26、ewNode = new LinkNode <T>(val);if (newNode = NULL) cerr << " 存储分配错误！ " << endl; exit(1);last->link = newNode; last = newNode;file >> val;last->link = NULL;file.close();/* * 将之前数据文件中数据放入链表中在进行后续操作*/ template <class T>void List <T>:outputFile() LinkN

27、ode<T> *current = first->link;fstream file( "List.txt" , ios :out);while (current != NULL file << current->data <<""current = current->link;file<< 0;file<< endl;file.close();template <class T>void List <T>:Sort() LinkNode<T>

28、; *p = new LinkNode<T>LinkNode<T> *q = new LinkNode<T>int temp;for (p = first->link; p->link !=NULL p=p->link) for (q = p->link; q != NULL q=q->link) if (q->data < p->data) temp = q->data; q->data = p->data; p->data = temp;七、测试结果与说明链表操作:链表的创建:4m

29、* 4* 法& 探 件I* L 率卜一k斑凝的白粒之列率帚i8£莉的埴址 I尘衰办:斑据工的，匚木曹*4jHHi-p #f t 1:国”建上新熔乘2曲轴靖工勘留表-3二在原行融龙上推粗4;：中修¥尊*¥*相曰*事¥*=口=*¥¥*4*才*料*4W卷入%的通推1-4】：，崎人世七以。川土砧：- 3 5 9 10 6 4 0!-4 ；取出第十元联的值一5/卜修由第1个元案的依& ：件第i外衣痴行植A jig L删除靠i个岳坨 R :判断表是否为空 9 :判断K淌?IQ:做据无点棒印11 JLiitorl式二文件操作傀存取叠

30、13 :退 H h 百输入你的揖射匚lT3i链表长度:第皿塞掾 II：心*«4"«川啤4I 2:匾索第i着元青I的地址 - 3拟出 看数据？南北案T :联曲搪上+此KH _ -5:川工桂改吊i甭冗翼的ffi 9 :和端iT/项旧抽入后代工 H-7:删除第i个 在匈（- 9 :MK兼母否为生一- Iio ：数抻元求棒字;11：粒确无点始山I12:支仲捅便惬存簟箱福薪的选择1一1琉' "1宿梗的长度7” 盘京食世地址3二档*土峨也x的儿联T二相吃小个无索加巾M ：网能性灰常j个鹏露的帆10 ：板 笫1年电/& 播 入-疝 卡K -7：H

31、87;mj 十衣埔s：利新表是否为空1g；网断麦森西-疝：&翩山*排序-代程无水抬离12一 £百挂作冰存数据L3:iHdji 中餐上酒的第并nrsili植人儿累检: 3041DFD6CI搜索含数据x元素位置:取出第i个元素位置:1 -畸收而良速2.:乳点东i拜无业 内士恸巾卜5川囊含蒯据H的无泉I4:取出第1,无泰的曲-F5 -用工峰或 55iTjt4iffJ tfl6 -在弟1飞衣见! h j插入JL.装XI上副除第i年轮呗T刷新衣用种为空-T:到场者漏苦-lOilfcffijiAdlPrT1停黜无制H一1也文件抵作保并的掘一*轨比操作卓申峰*事申事事|1: 岳的氏度一二丁

32、:一 k一.2 :舞亚 * i钟/上盘的她址-1一-7:按量峨«U的元青一_-7 .取用第i个元标的值一5: JHk摊段第i个无蠡前像6:在第二牛去项L岛入虻塞工 -7 :删除第 j 小衣坝=一 “ -“ -3 '9 :用断表胸白14 基枇屋房排序-门.段撒无吐乂产提柞保存欧据W鹿其体晌电择口7瓦搜索第i个元素地址:喻强案的他;Lo用x修改第i个元素的值:在第i个表项后插入x比MM此修，$ 3一粒或元卡的ffh 99描步虚动E 翠*济& 操 H *，LU1 ：畤蓑机 KISN般 塞第i不疝带的地址3精直管1H（如用匠长一-4 ：如出余i力X卡翁/I5: Olslfe及

33、彘4个北安加也一TW：曲十点期后捅入元胤（7如蹄军i怕缸&史判嘲袤些书脸9:刊的拓浦ft10：效外工素排呼11: W位不脩出13： £件海作保存散戏-濡雁A牌的见t+n-lXh11J 3 gglJ 10 6 4般人拙人%金位.五工2脑入久足充讷fth 9S插凡味如1-1:的 &的 玄处-3推维旗i善无4t的地址3.捶* A数据干曲北班T：lttll| 捻：l + 无' 的佣5 :用M*用时i个冗装的值6:在第i不耐诵hit®入兀盘工T：.Nt察1个箴弧-8:判断妻*;点为书,T:为曲 息淌 苔 101股胤嬉泉建于-11 ；鱼麻兀衣lb曲-1立文件城作

34、保在 昨13： jHht 话输入怫他运界I卜1$:11 23辅，35寻$删除第i个表项:判断表满否:5扎曲的mtu-uL请输入你的运抨I7W：曲人副除无去粒 G 酬除加元新也9卜年*军*0*¥*k*本第#：饼表刃（力1:1X虺他|2例菱嫡1杵元上代地址把屈米才就席硼兀*=4.喻K藏洋国章京5-用工生盘第if兀宸的也-也正事不去噢析推耳n.索工”7：制降解i 4展用 乱时隔点学量为生1M板期北蠹排层11.也第五K*tb!? £件斥栉牌春酉饵liiJHdji - 京地人储常氐情【；-"工1.:他.的任Jjf一2二接索笫:郭元的地址，3：搜索*0）（的邦索4.联;1第:

35、+ 疝青的俏秋Uh悻&第i个疳泰的旗-6:把第，小农项后插入疝泉式7.则康笫£十表二 肌判断出及笆为空9：轲断衣涵杏10敷知耳盍弹序'11:数窗元素输出T2：X好常保春雪舞一,忠出工请输入你的选择1-13L文件保存:清翰夫用的工异11色而故判4：Uuh-1J , 9>>£ a * * 雄情人*. r应T*L14h数据元素排序:不蛆入你 j：J ills 1-1$ =,10帏序成功Ig* 耕事布N 粕1呼连 役操祚味口 和口落善*1:被表的卷衣 2：拙童第i片支卡的出址3也求才毅帆捎元案4 ：取：h蟾i不元晶的屈i "川T"工力

36、、无长白S 6:在痂+段理*恸*无米工 7z制除第j中甚出8 ;到场点整转为七 卜a：可新如同用一1。：歌胡,居制1L1:.放押 元最希H ；12 :史件卷惮保存敷察U；亚由* 请人你的选打Il-LR：112 3 4 10 99 S9八、实验分析(1)算法的性能分析为了实现的方便，为链表加上一个“附加头结点”。它位于链表第一个结点 之前。附加头结点的data域可以不存储任何信息，也可以存放一个特殊标志或 表长。由于在链表的第一个结点之前还有一个附加头结点。因此，只要把附加头结点当作含数据a0的结点，在算法中查找第ai-1个结点时从k=0开始，如果i 不超过表的长度加1,总能找到含ai-1的结点

37、并让指针指向它。这样，在空表或 非空表第一个结点之前的插入可以不作为特殊情况专门处理，与一般情况一样统一进行处理。因而在附加头结点的单链表中插入时， 不必区分在何处插入，可以 统一处理，具体插入算法图解如下：node在p结点后插入一个新结点node,首先要让node的next指针指向p的next结 点，再让p的next指向node结点即可。对于删除算法，在附加头结点的单链表中与插入算法一致，在链表的第一个 结点处删除与在链表中间或尾部删除均可以用一种方式处理，图解如下：删除curr位置的结点，如果这个位置不存在则返回 false,如果找到对应结点， 则通过重新拉链的方式，将被删结点从链中摘下，并将删除值保存在一个引用型 实参中。对于单链表的搜索算法，其主要思想是：根据需要查找元素结点的位置来查找结点，从链表的首结点开始不断递增移动 next指针，当计数位置等于查找位 置时，即找到待查找结点并返回该结点地址。对于单链表的排序算法，该程序使用的时冒泡排序法实现。每次循环都是从 头结点开始，但是第一次结尾是最后一个元素，第二次结尾时倒数第二个元素， 利用两个for循环即可。具体图解如下：2）数据结构的分析由单链表的存储结构可得出以下优缺点：1. 优点： 通过结点的 next 指针作为线索来访问元素