《解析内存中的数据链.doc》由会员分享，可在线阅读，更多相关《解析内存中的数据链.doc（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、解析内存中的数据链于佳欣摘 要：本地计算机的内存中有多个数据连接。需要申请存储，不必返回，易于使用。但是，我们不知道存储在此数据链路中的内存，以及它是否可以完全释放。这不是在数据结构的学习和实践中详细讨论的，而是存储器的每个部分都是清晰可见的。由于二叉树和广义表之间的数据链路变得更加复杂，因此这些问题将不可避免地难以理解定义的学习。这是此论文研究的目的，因此学生可以更好地理解数据连接，从而更直观、更容易理解学习数据结构。在接下来的实验中，我将详细解释如何读取节点和数据连接的地址方向，然后根据数据结构的原理设计和实现以下实验：二叉树的存储器实验、用于广义表的存储器实验以及用于链接和存储线性表的存
2、储器实验。并尝试详细解释数据连接。关键词：单链表；内存释放；二叉树；广义表；数据链；数据链路技术是现代军事信息技术的重要组成部分，是现代军事信息技术的核心和基础。它是由海军在战术协调后的需求形成的，首次用于解决船舶与飞机的协调中存在的问题。如今，通过大数据、在线办公、智能制造、在线购物等开发，数据连接进入了人类生活的各个领域。在此论文研究中，我们只研究数据链路的一小部分，即内存数据链路。通过数据链路的存储结构，我们将讨论以下三个方面。首先，我们应该理解数据链路，然后在这些实验之后详细地分析数据连接的结构，以加深对计算机的理解。实验包括线性表的二叉树、广义表和链接存储线性表。如何读懂数据链我们现
3、在使用LNode节点类型作为一个简单的例子，例子如下：我们现在分别在键盘上输出输入50、70和90这三个数字，则例子中运行的结果也应该是50、70和90。具体步骤如下：我们首先创建具有三个节点的单个链路径列表，然后在单个链路径列表中输入每个节点的值。对于该程序，单链列表中的每个节点是动态节点(即，由动态映射生成的节点)。通过这个简单的实验室学习数据连接。1.1实验所用到的程序我们进行举例，例子如下所示:#include typedef int ElemType;struct LNode ElemType data;LNode * next;/ /结构体类型的结点被next这个指针指向;void
4、 main()LNode *p, *q, *p1;p1=p=new LNode ; /并且把他的地址给p和pl这两个指针cout 结 点 建 立 ： pendl;/将刚建立的结点的地址显示出来for (int i=0;i3;i+) q=new LNode; coutqq-data ; / q结点拥有从键盘输入一个整数/结点的值域为 q所指向的。 p-next=q; / p结点之后链接q结点 p=q; /使p结点指向新的结点qp-next =NULL;/置链表中的最后一个结点，它的指针域为空p=p1-next;/附加结点要越过表头cout 结 点 遍 历 ： ;/ pl结点的指针域指向的结点为链
5、表的表头结点while(p!=NULL) /从表头开始，来输出每一个结点的值 coutp ;/输出并得出结点p的地址 coutdatanext; / 使p结点指向链表中的下一个结点coutendl;/将程序占用的内存释放出来cout 将 结 点 占 用 的 内 存 归 还 给 操 作 系 统 ： ;p=p1;while(p!=NULL) coutpnext;delete p;p=p1;1.2实验得到的数据以及结果如下所示：地址的指向结点的建立如下：0x007607A00x00760A10 500x00760C80 700x00760CB8 90结点的遍历如下：0x00760A10 50 0x0
6、0760C80 70 0x00760CB8 90结点占用的内存归还给操作系统如下：0x007607A0 0x00760A10 0x00760C80 0x00760CB8由上述数据得到如下的内存数据链示意图：图1 ：数据链示意图1.3对数据链路的说明如下：该实验一共生成了以下四个结点，第一个结点由p1指向，p1的值为0x007607A0则p1指向的地址为0x007607A0的链表结点。地址为0x007607A0的结点为表头附加结点，next域的值为0x00760A10，说明指向的地址为0x00760A10的结点。地址为0x00760A10的结点的data域的值为50，next域的值为0x0076
7、0C80，说明指向的地址为0x00760C80的结点。地址为0x00760C80的结点的data域的值为70，next域的值为0x00760CB8，说明指向的地址为0x00760CB8的结点。地址为0x00760CB8的结点的data域的值为90，next域的值为0，说明指至此数据链结束。2.通过链接存储线性表的实验来探究数据链的内存结构链接表的每一个结点结构均为struct LNode ElemType data; LNode* next; ; 此链接要求我们插入并继续设置线性表和线性表数据，以保存线性表的初始化操作。通过删除操作来更改数据链接；通过交叉行表操作显示数据链接；通过删除操作将已
8、消耗的内存返回到操作系统。因为标题被记录在链接列表中，所以可以节省更多的时间将其插入到标题中。单链表的操作通常要比顺序表的操作节省更多的时间，更加方便快捷，当然前提是在相同数量级的情况下。2.1实验所用到的算法的程序我们进行举例，例子如下所示：#include #include typedef int ElemType;struct LNodeElemType data;LNode* next;#includelink.hvoid main()int a14=2,4,6,8,10,12,14,16,18,20,22,24,26,28;int i;ElemType x;LNode* t;Init
9、List(t);for(i=0;i14;i+) InsertList(t,ai,i+1);SortList(t);TraverseList(t);InsertList(t,28,13);InsertList(t,26,0);cout 初 始 插 入 后 14 个 数 据 如 下 所 示 ： endl;coutx;if(DeleteList(t,x,0) cout 删 除 成 功 ! endl;else cout 删 除 失 败 ! endl;for(i=0;i6;i+)cout 将 要 删 除 第 i+1 个 endl;TraverseList(t); DeleteList(t,x,i+1);
10、cout 删 除 后 的 数 据 如 下 所 示 ： endl;TraverseList(t);coutx;if(InsertList(t,x,0) cout 插 入 成 功 ! endl;else cout 插 入 失 败 ! endl;cout 插 入 一 个 数 据 后 的 数 据 链 数 据 如 下 所 示 ： endl;TraverseList(t);ClearList(t);/实验用的link.h头文件/要初始化的单链表void InitList1(LNode*& HL)HL = NULL; /置空这个单链表/将单链表遍历void TraverseList1(LNode* HL)
11、coutHLendl;/将链表头的地址显示出来 while(HL!=NULL) /从表头开始输出结点的值 coutHLdata,nextnext; coutendl;/按条件在单链表中插入元素bool InsertList1(LNode* &HL, ElemType item, int pos)if(pos-1) coutpos 值 无 效 ! data=item;LNode* cp=HL;LNode* ap=NULL; if(pos=0) while(cp!=NULL) if(itemdata) break; else /为了实现顺序向后比较，我们要将ap和cp指针均后移 ap=cp; cp
12、=cp-next; else if(pos=-1) while(cp!=NULL) ap=cp; cp=cp-next; else int i=0; while(cp!=NULL) i+; if(i=pos) break; else /为了实现顺序向后比较，我们将ap和cp指针均后移 ap=cp; cp=cp-next; if(cp=NULL & posi+1) coutpos值超出单链表长度加1!next=HL; HL=newptr; else newptr-next=cp; ap-next=newptr; return true;/ 即第一个符合给定条件的元素。bool DeleteLis
13、t1(LNode* &HL, ElemType& item, int pos)if(HL=NULL)cerr 单 链 表 为 空 ， 删 除 操 作 无 效 ! endl; return false;if(pos-1) coutpos值无效!data) break; else /为了实现顺序向后比较，我们将ap指针和cp指针均后移动 ap=cp; cp=cp-next; if(cp=NULL) cout单链表中没有相应的结点可删除!next!=NULL) ap=cp; cp=cp-next; else int i=0; while(cp!=NULL) i+; if(i=pos) break;
14、else ap=cp; cp=cp-next; if(cp=NULL) coutpos值无效!next; else ap-next=cp-next; delete cp;return true;/如果我们删除成功的话，则返回为真2.2实验数据如下所示：初 始 插 入 后 14 个 数 据 如 下 所 示 ：0x007C08580x007C08582,0x007C08900x007C08904,0x007C08C80x007C08C86,0x007C09000x007C09008,0x007C09380x007C093810,0x007C09700x007C097012,0x007C09A80x
15、007C09A814,0x007C09E00x007C09E016,0x007C0A180x007C0A1818,0x007C0A500x007C0A5020,0x007C0A880x007C0A8822,0x007C0AC00x007C0AC024,0x007C0AF80x007C0AF826,0x007C0B300x007C0B3028,0x00000000输 入 待 删 除 的 元 素 值 为 ： 12删 除 成 功 !删 除 后 的 数 据 如 下 所 示 ：0x007C08900x007C08904,0x007C09000x007C09008,0x007C09A80x007C09A8
16、14,0x007C0A180x007C0A1818,0x007C0A880x007C0A8822,0x007C0AF80x007C0AF826,0x007C0B300x007C0B3028,0x00000000按 值 插 入 , 输 入 待 插 入 的 元 素 值 为 ：5插 入 成 功 !0x007C08900x007C08904,0x007C0AC00x007C0AC05,0x007C09000x007C09008,0x007C09A80x007C09A814,0x007C0A180x007C0A1818,0x007C0A880x007C0A8822,0x007C0AF80x007C0AF
17、826,0x007C0B300x007C0B3028,0x000000002.3对数据链路的说明如下所示：2.3.1初始插入后14个数据分别为：地址为0x007C0858的结点为表头结点data域的值为2，next域的值为0x007C0890，说明指向的地址为0x007C0890的结点。地址为0x007C0890的结点的data域的值为4，next域的值为0x00611390，说明指向的地址为0x007C08C8的结点。地址为0x007C08C8的结点的data域的值为6，next域的值为0x007C0900，说明指向的地址为0x007C0900的结点。地址为0x007C0900的结点的dat
18、a域的值为8，next域的值为0x007C0938，说明指向的地址为0x007C0938的结点。地址为0x007C0938的结点的data域的值为10，next域的值为0x007C0970，说明指向的地址为0x007C0970的结点。地址为0x007C0970的结点的data域的值为12，next域的值为0x007C09A8，说明指向的地址为0x007C09A8的结点。地址为0x007C09A8的结点的data域的值为14，next域的值为0x007C09E0，说明指向的地址为0x007C09E0的结点。地址为0x007C09E0的结点的data域的值为16，next域的值为0x007C0A1
19、8，说明指向的地址为0x007C0A18的结点。地址为0x007C0A18的结点的data域的值为18，next域的值为0x007C0A50，说明指向的地址为0x007C0A50的结点。地址为0x007C0A50的结点的data域的值为20，next域的值为0x007C0A88，说明指向的地址为0x007C0A88的结点。地址为0x007C0A88的结点的data域的值为22，next域的值为0x007C0AC0，说明指向的地址为0x007C0AC0的结点。地址为0x007C0AC0的结点的data域的值为24，next域的值为0x007C0AF8，说明指向的地址为0x007C0AF8的结点。
20、地址为0x007C0AF8的结点的data域的值为26，next域的值为0x007C0B30，说明指向的地址为0x007C0B30的结点。地址为0x007C0B30的结点的data域的值为28，next域的值为0，说明指至此数据链结束。2.3.2 删除后的数据链路为：地址为0x007C0890的结点为表头结点data域的值为4，next域的值为0x007C0900，说明指向的地址为0x007C0900的结点。地址为0x007C0900的结点的data域的值为8，next域的值为0x007C09A8，说明指向的地址为0x007C09A8的结点。地址为0x007C09A8的结点的data域的值为1
21、4，next域的值为0x007C0A18，说明指向的地址为0x007C0A18的结点。地址为0x007C0A18的结点的data域的值为18，next域的值为0x007C0A88，说明指向的地址为0x007C0A88的结点。地址为0x007C0A88的结点的data域的值为22，next域的值为0x007C0AF8，说明指向的地址为0x007C0AF8的结点。地址为0x007C0AF8的结点的data域的值为26，next域的值为0x007C0B30，说明指向的地址为0x007C0B30的结点。地址为0x007C0B30的结点的data域的值为28，next域的值为0，说明指至此数据链结束。2
22、.3.3 插入一个数据后的数据链路为：地址为0x007C0890的结点为表头结点data域的值为4，next域的值为0x007C0AC0，说明指向的地址为0x007C0AC0的结点。地址为0x007C0AC0的结点的data域的值为5，next域的值为0x007C0900，说明指向的地址为0x007C0900的结点。地址为0x007C0900的结点的data域的值为8，next域的值为0x007C09A8，说明指向的地址为0x007C09A8的结点。地址为0x007C09A8的结点的data域的值为14，next域的值为0x007C0A18，说明指向的地址为0x007C0A18的结点。地址为0
23、x007C0A18的结点的data域的值为18，next域的值为0x007C0A88，说明指向的地址为0x007C0A88的结点。地址为0x007C0A88的结点的data域的值为22，next域的值为0x007C0AF8，说明指向的地址为0x007C0AF8的结点。地址为0x007C0AF8的结点的data域的值为26，next域的值为0x007C0B30，说明指向的地址为0x007C0B30的结点。地址为0x007C0B30的结点的data域的值为28，next域的值为0，说明指至此数据链结束。3.通过广义表的实验，我们来探究数据链的内存结构在一个广义表中，将数据元素划分为两种类型，分别为
24、单个元素和子表，使得存储器节点也被划分为对应的存储器结构中的单个元素和子表节点。对单个元素结点就包括指向它后继结点的指针域以及值域；指向子表中的第一个结点的表头指针域也包含在子表结点中，以及指向它后继结点的指针域。要区分通用表中的两个单独的元素节点和子表节点，必须向每个节点添加一个新的标记字段，以便标记字段可以假定两个不同的值，允许区分两个不同的结点。如果我们思考一个广义表的复杂递归结构，我们分配给它的空间通常很难用于仅使用固定容量的存储空间，而是选择了动态链接结构。广义表的数据结构为：struct GLNode bool tag;union ElemType data; GLNode * s
25、ublist;GLNode * next;我们要通过创建一个这样的广义表，建立这个广义表，建立的数据为“(#),a,(b,(c,d);”，此时输出建立时广义表的部分数据，空表我们就在其圆括号内使用一个字符 “”表示，在此操作点，当我们创建广义表时，我们给出了一个概括表的一部分数据，这反映了创建广义表的顺序。以在清理操作期间删除它的顺序显示广义表的所有数据。3.1实验算法的程序我们进行举例如以下例子所示：#include #include typedef char ElemType;struct GLNode bool tag; union ElemType data; GLNode * sub
26、list; ; GLNode * next;int num;#include genlist.hvoid main() GLNode* g = NULL; Create(g);coutendl; Delete(g); /num=0; /Delete1(g);/内存的释放 /coutnum ch; / 可以读入以下一个字符，此处该程序只能读入英文字母、括号或者是空格(#)。 if (ch=# ) GL=NULL; /GL else if (ch=() / 创建由GL递归或者是所指向的子表结点并构建的子表 GL= new GLNode; GL-tag=true;coutGLsublist); el
27、se / 我们来创建这些由GL指针所指向的单个元素的结点 GL = new GLNode;coutGL chtag = false; GL-data = ch; cin ch; / 此处可以读入的字符，只能为分号、左括号或者是逗号 if (GL= NULL);/ 此时的ch指针，其必定是)字符，它并没有任何作用 else if (ch=, ) Create (GL-next); / 这一步我们来递归构建的后继表 else if (ch=)|(ch=;) GL-next = NULL; / 如果没有后继表的话，我们要将GL指针的后继指针域置为空。 void Delete(GLNode * GL)
28、/ 这里的GL可以为引用参数，而后输出带有表头的附加结点的，由值参GL所指向的，广义表if (GL!=NULL) if (GL-tag = true) if (GL-sublist != NULL) Delete(GL-sublist); if (GL-next!=NULL) Delete3(GL-next); coutendlGLtag=false)coutdata; else coutsublist ; coutnext; delete GL;3.2实验数据如下：(#),a,(b,(c,d);广义表在建立时，所生产的部分数据结果如下所示:0x00260A280x00260C980x0026
29、0CD0 a0x00260D080x00260D40 b0x00260D780x00260DB0 c0x00260DE8 d删除广义表时，所显示的广义表的完整数据结果如下所示:0x00260DE8 d 0x000000000x00260DB0 c 0x00260DE80x00260D78 0x00260DB0 0x000000000x00260D40 b 0x00260D780x00260D08 0x00260D40 0x000000000x00260CD0 a 0x00260D080x00260C98 0x00000000 0x00260CD00x00260A28 0x00260C98 0x
30、000000003.3广义表的数据链路如下所示：地址为0x00260DE8的结点为表头结点，tag域的值为0，sublist域的值为d，next域的值为空，说明其并不指向下一个结点。地址为0x00260DB0的结点的tag域的值为0，sublist域的值为c，next域的值为0x00260DE8，说明其指向的地址为0x00260DE8的结点。地址为0x00260D78的结点的tag域的值为1，sublist域的值为0x00260DB0，next域的值为空，说明其并不指向下一个结点。地址为0x00260D40的结点的tag域的值为0，sublist域的值为b，next域的值为0x00260D78
31、，说明其指向的地址为0x00260D78的结点。地址为0x00260D08的结点的tag域的值为1，sublist域的值为0x00260D40，next域的值为空，说明其并不指向下一个结点。地址为0x00260CD0的结点的tag域的值为0，sublist域的值为a，next域的值为0x00260D08，说明其指向的地址为0x00260D08的结点。地址为0x00260C98的结点的tag域的值为1，sublist域的值为0，next域的值为0x00260CD0，说明其指向的地址为0x00260CD0的结点。地址为0x00260A28的结点的tag域的值为1，sublist域的值为 0x002
32、60C98 ，next域的值为空，说明其并不指向下一个结点。至此数据链就结束了。以下为广义表数据链的示意图：图2：广义表数据链示意图4.通过二叉树的实验，我们来探究数据链的内存结构二叉树是数据结构的基础数据类型，他的数据结构为:struct BTreeNode / 我们将要定义二叉树，它的结点类型 ElemType data; / 我们将其称之为它的值域 BTreeNode * left; / 我们将其称之为它的左指针域 BTreeNode * right; /我们将其称之为它的右指针域;二叉树可以由堆栈结构建立，二叉树数据可以在前序操作过程中输出，并且通过清除过程再次显示二进制树数据。在此基
33、础上，对数据链路和数据链路示意图，进行了研究。4.1二叉树实验算法的程序如下所示：#include#includetypedef char ElemType; /我们要将二叉树中元素的类型，定义为字符型struct BTreeNode / 对二叉树的结点类型进行分类 ElemType data; / 这里表示的是值域 BTreeNode * left; / 这里表示的是左指针域 BTreeNode * right; / 这里表示的是右指针域;#include btree.h / 此 b树 头文件中，包含着有对进行各种操作的二叉树的算法void main() BTreeNode* bt; /我们
34、用它作为树根的指针，并且定义将其指向二叉树结的以下指针， InitBTree(bt); / 我们要置树根指针 指针bt为空 ，即初始化我们的二叉树 char b50; / 定义一个用于存放的字符数组，用来存放我们的二叉树的广义表 cout 输 入 一 个 用 二 叉 树 广 义 表 表 示 的 字 符 串 ： endl; cin.getline(b,sizeof(b);/将刚刚我们输入的字符串，存放在b树的数组中。 CreateBTree(bt,b);/ 我们来建立链接存储结构，先决条件是要以bt作为树根指针的二叉树 cout 前 序 遍 历 : ;PreOrder_sjl(bt);coute
35、ndl; / 我们以bt树为树根指针的二叉树，要进行前序的遍历 cout 清 除 二 叉 树 ： ; ClearBTree_sjl(bt); / 我们要清除，以bt树树为树根指针的二叉树/btree.h/我们要输出二叉树数据，因此要利用前序遍历。void PreOrder_sjl1(BTreeNode * BT)if (BT!=NULL) coutendlBT left data right; /以此来访问这个根结点 /按照顺序 我们来输出二叉树的结点地址/然后是左孩子的地址/然后是结点的值、/最后是右孩子的地址 PreOrder_sjl(BT-left); / 我们将左子树，进行前序的遍历
36、。 PreOrder_sjl(BT-right); /然后我们将 右子树，进行前序遍历/下面我们来初始化这个二叉树void InitBTree1(BTreeNode * & BT) / 如何初始化二叉树，就是要把树根的指针置空 BT=NULL;/ 我们建立二叉树的算法描述，具体方法如下所示：void CreateBTree1(BTreeNode*& BT, char* a)/我们先按照字符串 a 所给出的，用广义表所表示的二叉树，来创建与之相对应的存储结构， const int MaxSize=10; /栈数组长度，我们要 要大于等于二叉树的深度然后再减去减1 BTreeNode* sMaxS
37、ize; /s数组所起的作用，是存储根结点的指针的栈的作用 int top=-1; /为空栈，其初值是-1，栈顶指针为top， BT=NULL; /从空树进行起首，即置树根的指针为空值 BTreeNode* p;/我们来定义p指针，为指向二叉树的结点的指针 int k; /我们将k，用于标记来处理结点的左子树以及结点的右子树， /当k的值为2时我们要来处理它的右子树，当k的值为1时我们要来处理它的左子树， int i=0; /我们将i，用于检测以及扫描数组a中，所存储的二叉树的广义表的字符串。 while (ai) /在检测到扫描到字符串的结束停止符0之前，每一轮循环都要处理一个字符，直到扫描到，我们才可以截止。 switch(ai) case : /我们不处理任何的空格 break; case (: if(top=MaxSize-1) cout 栈 空 间 过 小 ， 需 要 增 加 M a x S I z e 的 值 ! endl; exit(1); top+; stop=p; k=1; break; case ): if(top=-1) cout 二 叉 树 广 义 表 字 符 串 是 错 的 ! endl; exit(1); top-; break; case ,: k=2; break; default: /其只能为结点值，即其为字符