Sci论文 - 至繁归于至简,Sci论文网。 设为首页|加入收藏
当前位置:首页 > 教育论文 > 正文

数据结构在计算机网络课程中的应用论文

发布时间:2019-11-19 17:28:31 文章来源:SCI论文网 我要评论














SCI论文(www.scipaper.net):

摘要:论文针对计算机网络与数据结构课程的特点,对常用数据结构进行概述的基础上,阐述常见计算机网络协议及相应数据结构,然后结合具体案例详细分析线性表、队列、图、二叉树等数据结构在计算机网络课程中应用,旨在通过数据结构和计算机网络课程的融合,降低课程内容的抽象性,以提高课程教学效果。

关键词:计算机网络;数据结构;课程教学;实验

Application of Data Structure in Computer Network Course

Huang Yong-ping,Tan Cheng-xiang

(School of Mathematics and Computer Science,Guangxi Normal University for Nationalities,Guangxi,Chongzuo,China)

Abstract:According to the characteristics of computer network and data structure course,this paper summarizes the common data structures,expounds the common computer network protocols and corresponding data structures,and then combines specific cases to analyze in detail the application of linear table,queue,graph,binary tree and other data structures in computer network course,aiming at the communication.Through the integration of data structure and computer network course,the abstraction of course content is reduced,so as to improve the teaching effect.

Key words:Computer network;Data structure;Course teaching;Experiment

       计算机网络课程覆盖知识面广,概念多、内容抽象,如果采用纯理论教学方式,学生对真实的网络环境缺乏了解,教师很难在有限时间内把计算机网络抽象的原理和协议讲述清楚,学生也很难真正掌握计算机网络相关技术[1]。有些学校计算机网络课程教学过程中安排了网络设备(如交换机、路由器)的配置实验,这些实验在学生了解网络的常用硬件、理解路由原理等方面有很大帮助。但计算机网络课程中,对网络体系结构、网络协议的理解和掌握也很重要[2]。如果,在授课过程中能结合使用抓包工具(Wireshark等)截取和分析协议报文,让学生对本是抽象的协议报文有比较直观的认识和理解。在学生对协议报文有一定理解的基础上,再把计算机网络课程和数据结构课程结合起来,使用程序设计语言把常见网络协议的数据结构定义出来,为协议报文的构建及网络通信的实现打下坚实的编程基础。同时,在讲解网络中算法时,让学生在理解算法原理的基础上,选择合适的数据结构编程实现网络中的算法,以加深学生对网络知识的理解,提高网络应用技能,同时提高数据结构应用能力。

一网络协议及其数据结构

        数据结构是研究数据及其结构和算法的学科,是软件设计的基础课程。数据结构分为逻辑结构和存储结构,常见的逻辑结构有一般线性表、栈、队列、串、树和图等,而针对各种逻辑结构相应的存储结构主要有顺序存储和链式存储两种。

        因此在具体应用中有顺序表、链表、顺序栈、链栈、顺序队列、链式队列、二叉链和图的邻接矩阵和邻接表等存储结构。

       在网络课程当中,可以根据具体的网络协议和应用选择合适存储结构,实现网络协议和应用的编程。网络中的常见协议有IP,ARP,ETHERNET,TCP,UDP,DNS,HTTP,ICMP等等。其协议报文可以选择顺序存储结构来实现。如IP的头部结构描述(用C语言):

typedef struct{
char VersionAndHeaderLen;//版本信息与头部长度
char ServiceType;//服务类型short TotalLen;//IP报文长度short PacketID;//标识符
short Sliceinfo;//分片信息
char TTL;//生存时间
char ProtocolType; //协议类型
short CheckSum; //校验和
unsigned int SrcIp; //源ip
unsigned int DstIp;//目的ip
}IP_HEADER;

二 数据结构在网络中的应用案例

       案例1:链式存储结构在聊天室程序实现中的应用。开发一个基于C/S模式的聊天室,服务器端程序可接受多个客户的连接请求,连接成功后进入聊天室。每个跟服务器连接成功的客户既可以与其他所有连接成功的用户进行公开聊天(群聊),也可以选择只和某个用户进行一对一聊天(私聊)。聊天室实现过程中,服务器端程序需要保存请求连接的客户信息(客户名、SOCKET等),考虑到客户的请求连接或退出聊天(断开连接)比较灵活机动,即在设计数据结构时要考虑插入和删除的方便灵活,以降低程序运行的时间复杂度。基于这些考虑,可以选择链表作为存储结构。设置客户链表,当有客户连接成功进入聊天室时,服务器将客户的基本信息(客户名、SOCKET等)插入到用户链表中,当有客户退出聊天室时,将其客户基本信息(客户名、SOCKET等)从链表中删除[3]。

\

 
      聊天室客户链表结点的数据结构定义:

       struct{char UserName[NUM];//聊天室的客户名;SOCKET UserSocket;//聊天室客户的SOCKET;}User;//客户数据类型struct UserNode{User UserData;//客户链表结点数据类型;struct UserNode*next;//指向下一个客户结点的指针;}UserNode_L;//客户链表结点类型

        案例2:用队列作为数据结构计算滑动窗口内的最大网络流量。在网络流量控制机制中,往往需要计算某个时间段的最大网络流量,即已知t是某个给定的时间节点,w是滑动窗口大小,需要计算出时间段[t-w,t]内的最大网络流量max(t,w)。举个例子,假设滑动窗口大小w为8,某个具体的时间节点t的网络流量用(t,v)来表示,v表示时刻t的网络流量,即(4,6)就表示在时间点4时,网络流量是6。现有一系列流量记录:(2,8),(4,2),(6,5),(8,10),(10,3),(13,12),根据以上流量记录,可知max(13,8)等于12.因为在时间点13,滑动窗口大小为8时,落入时间段[13-8,13]的流量点有(6,5),(8,10),(10,3),(13,12),在这四个流量点中,时间点13处的流量12最大,所以max(13,8)等于12。而max(10,8)等于10,因为时间点为10,窗口大小为8时,落入时间段[10-8,10]的流量点有:(2,8),(4,2),(6,5),(8,10),(10,3),在以上时间点中流量最大的时刻点是8,流量大小为10,所以max(10,8)等于10[4]。

        通过对问题的具体分析,可以选择队列作为数据结构。设置两个队列MaxQueue和WorkingQueue,MaxQueue放最大流量节点,WorkingQueue放流量记录系列。队列数据结构可以选择顺序存储也可以选择链式存储,以顺序存储为例,WorkingQueue,MaxQueue的数据结构定义为:

typedef m QElemType;typedef struct{
QElemType*base;//初始化时动态分配存储空间
int front;//头指针
int rear;//尾指针
}SqQueue;
SqQueue WorkingQueue,MaxQueue;
流量记录节点数据结构定义:
typedef struct{int t;//时间
char V[NUM];//流量
}m;

      具体算法思路及步骤:

        (1)设置指针变量p,p初始时指向WorkingQueue队尾节点。让p从WorkingQueue队尾往前进,每往前移一步,就判断p所指向节点的时间t是否在滑动窗口范围内,同时设置变量count以统计p往前退次数。如果p所指向的流量节点时间t超出滑动窗口范围,p就往后退一步。

        (2)从p所指向的节点开始,如果队列MaxQueue为空,把p指向的流量节点直接插入队列MaxQueue;如果队列MaxQueue非空,则把p所指向的节点对应的流量V跟MaxQueue队尾节点对应的流量做比较,如果p所指向的节点对应的流量大于MaxQueue队尾节点对应的流量,就把p指向的流量节点插入队列MaxQueue,然后p加一,指向下一个流量节点,否则让p直接加一。最后MaxQueue队尾节点对应的流量就是最大流量。

         案例3:用图数据结构解决网络中通信节点间的最短路径问题。计算机网络可以用带权的有向图来表示,图中顶点表示网络节点,边表示节点间的通信链路,权表示此链路的长度或沿此链路通讯所花的时间或费用等。则网络中求通信节点间的最短路径可以转化为有向带权图的最短路径问题。所谓最短路径问题是指:如果从图中某一顶点出发到达另一顶点的路径可能不止一条,如何找到一条路径使得沿此路径上各边的权值总和达到最小。

        迪杰斯特拉(Dijkstra)算法是典型最短路径算法,其基本思想:将图中所有顶点分成两组:一组是包括已确定最短路径的顶点的集合S,另一组是尚未确定的最短路径的顶点集T=V-S。S初始仅包含源v0,不断在V-S做贪心选择扩充集合S。设图G以邻接矩阵arcs存储,矩阵中各元素的值为各边的权值。顶点间无边时其对应权值用无穷大表示。
图的邻接矩阵数据结构定义[5]://MVNum表示最大顶点数typedef struct{VerTexType vexs[MVNum]; //顶点表ArcType arcs[MVNum][MVNum];//邻接矩阵int vexnum,arcnum; //图的当前点数和边数}AMGraph;设置辅助数组Dist,其中每个分量Dist[i]表示当前所求得的从源点V0到其余各顶点i的最短路径的长度。

算法具体步骤:

(1)取源点v0加入S中。

(2)选dist中最小的权值,将其顶点(j)加入S中。

(3)修改从顶点v0到集合T(T=V-S)中各顶点(k)的最短路径长度,如果dist[j]+arcs[j][k]<dist[k]则修改dist[k]为dist[k]=dist[j]+arcs[j][k]

(4)重复(2)(3),直到求得v0到图上其余各顶点得最短路径(T为空)。

        数据结构在计算机网络中的应用案例还有很多,例如可以使用字符串为数据结构实现网络入侵检测、计算机病毒特征码匹配;网络游戏中,使用基于二叉树数据结构的排序算法或改进算法,可以降低排序工作量,提高查找速度,特别是在大规模网络游戏场景中的事件查找,可以大大提高游戏服务器的工作能力[6];网络数据传输之前一般会先进行数据压缩,利用哈夫曼树来设计数据压缩编码,可以有效地节省数据文件传输时间,提高网络数据传输效率。

三 结论

        计算机网络课程与数据结构课程都是理论性和综合性比较强的课程。在教学过程中,如果把两者紧密联系起来,用计算机网络实际的通信算法、应用例子来讲解具体的数据结构选择及应用,不但可以加深学生对计算机网络原理及协议的理解,同时提高数据结构实际应用能力。论文对常用数据结构进行概述,在此基础阐述常见计算机网络协议及相应数据结构,然后结合具体案例详细分析了计算机网络中数据结构的应用。

\

 
参考文献

[1]黄勇萍.软件工程专业“计算机网络”课程教学方法探讨[J].计算机时代,2014(8):58-62.
[2]隋永平,荆山,孙丽娟.浅谈计算机网络原理实验教学[J].计算机教育,2014(20):101-110.
[3]贺桂英.链式存储结构在网络编程中的应用[J].广东广播电视大学学报,2004(3):32-35.
[4]tyler_download.面试算法:用队列计算滑动窗口内的最大网络流量[EB/OL].https://blog.csdn.net/tyler_download/article/details/69065811,2017.
[5]严蔚敏,李冬梅,吴伟民.数据结构(C语言版|第2版)[M].北京:人民邮电出版社,2015:154.
[6]张渊,余小清,万旺根.空间二叉树排序查找算法及其在网络游戏中的应用[J].计算机应用,2007(27):356-359.
[7]王亮,田丰.计算机网络课程教学改革的一些思考[J].教育现代化,2018,5(22):75-76+83.
[8]米文丽,李芳芳.任务驱动教学在《数据结构》网络课程中的应用[J].教育现代化,2015(14):104-105.

关注SCI论文创作发表,寻求SCI论文修改润色、SCI论文代发表等服务支撑,请锁定SCI论文网!  
文章出自SCI论文网转载请注明出处:https://www.scipaper.net/jiaoyulunwen/7395.html

发表评论

Sci论文网 - Sci论文发表 - Sci论文修改润色 - Sci论文期刊 - Sci论文代发
Copyright © Sci论文网 版权所有 | SCI论文网手机版 | 豫ICP备2022008342号-1 | 网站地图xml | 百度地图xml