KTV歌曲点播列表管理功能的设计与开发 其他类 本科组 郭明月

内容摘要本文主要研究了KTV中歌曲点播列表的管理功能及各种管理功能在Turbo C中的算法设计与实现过程，研究通过实地走访、了解需求、根据需求设计算法、调试算法的方式进行，改进了KTV中歌曲点播列表的管理功能，也可作为数据结构课程的教学实例。

关键词：歌曲点播列表管理功能算法实现AbstractThis paper looks into the managing functions of the list of songs in KTV. It also studies the algorithm and implementation of these managing functions in Turbo C .By visiting KTV, learning the needs, designing algorithms based on the demand and debugging the algorithms, the study can not only improve the managing functions of the list of songs in KTV, but also serve as teaching examples on data structure courses.Key words: list of songs, managing functions, algorithm，implementation目录一、引言二、文献回顾与文献综述三、功能设计(一)点歌(二)切歌(三)移动(四)调换(五)添加(六)插入(七)删除四、系统实施(一)将一首歌曲移动到另一首歌曲之后(二)将两首歌曲的位置相互调换(三)添加(四)插入(五)删除五、小结六、附录KTV歌曲点播列表管理功能的设计与开发本文研究了KTV中歌曲点播列表的管理功能在Turbo C中的设计与实现，包括其中已有的添加、插入、删除等功能在Turbo C中的实现，与根据顾客需要，用Turbo C设计的实现两首歌曲调换、移动功能的算法实现，其研究意义在于改进了KTV中已有的歌曲点播列表的管理功能，进一步方便了广大顾客的使用；同时，本文中用到的算法涉及到数据结构中有关单链表、链式队列中的种种算法的实现思想，因此，本文的研究意义还在于可以将其中的算法作为数据结构中的教学实例，以帮助学生更加灵活地运用单链表。

除此之外，本文的研究意义也在于鼓励学生运用所学知识去解决实际生活中遇到的问题，从而激发学生的学习热情，营造良好的学习氛围。

本文研究的理论背景即为大一所开课程《数据结构》中单链表的建立、插入、删除、查找，链式队列的入队、出队等运算的实现思想。

现实背景则是由于当今社会计算机的飞速发展以及人们娱乐生活的不断丰富，KTV已成为广受青睐的娱乐场所，而随着计算机技术的进步与普及，KTV等娱乐场所中对计算机的应用也随处可见，本文研究的KTV中歌曲点播列表管理功能的设计与开发便是KTV中应用计算机进行信息管理的重要组成部分。

本文采用的研究方法大体为：首先通过走进位于北京市昌平区昌平东关的“雷石KTV”进行实地调查，了解顾客对KTV的歌曲点播列表中不同管理功能的需要，然后将每一个功能用Turbo C中的程序语言写成一个函数，接着编写主函数，通过在主函数中调用上面编写的功能函数，完成提示功能、选择功能、实现功能等任务，最后在Turbo C 3.0中调试由主函数和功能函数构成的程序，以模拟在KTV中根据顾客的实际需要对歌曲播放列表实现各种管理功能的过程，并最终调试成功①。

本文的研究主题是KTV中歌曲点播列表的管理功能以及其在Turbo C中的实现，包括其中已有功能如添加、插入、删除在Turbo C 3.0环境下的算法与实现，以及通过实地调研、根据顾客需要新增加的功能如移动、调换在Turbo C 3.0环境下的算法与实现。

本文的创新点在于对顾客需要、但KTV中没有的功能如调换、移动给出了在Turbo C中的算法与相应程序代码、使得这些功能在Turbo C环境下得以实现，从而改进了KTV中的歌曲点播列表；另一方面，如今大多数KTV中的歌曲点播列表主①要是基于数据库运行的，而本文则提供了类似的歌曲点播列表在Turbo C环境下、以单链表作为数据的存储结构，并以C语言源文件的形式存储在个人计算机内存中的管理与实现方法，这也是本文的创新点之一。

同时，由于有关数据结构的教材中缺少在KTV歌曲点播列表中运用单链表实现点歌、切歌、添加、插入、删除、调换、移动等功能的例题与分析，本文的创新点还在于为数据结构的教学提供了新的实例与应用；另外，本文也为因专业知识储备不够而困惑的大一学生提供了运用课堂所学知识解决实际问题的方法。

本文余下部分的结构如下:第一部分:文献回顾与文献综述;第二部分:功能设计;第三部分:系统实施;第四部分:小结;第五部分:附录;一、文献回顾与文献综述KTV点歌系统开发基于C/S 结构软件的设计模式，界面采用PowerBuilder 设计开发，后台数据库采用SQL sever 实现。

在设计系统过程中建立了四张表（管理员信息表，歌手信息表，歌曲信息表及歌曲点播列表）用于各项信息的有效管理①。

以上介绍的KTV点歌系统充分利用了数据库存储数据量大的优点,但对于数据库等专业知识较为缺乏的大一学生来说,整个点歌系统的原理与实现过程不易理解,不便与其专业课的知识相结合。

然而，对于系统中四张表中的一部分，即“歌曲点播列表”，则便于运用大一课程中的C语言、数据结构等知识来模拟实现对其进行管理时的相关功能。

其中，列表上显示的歌手信息、歌曲信息可作为结构体中的数据域。

因此，本文着重讨论其中的“歌曲点播列表”，在Turbo C环境下编写对其实现添加、插入、删除、调换、移动等功能的算法，因此，需要提供计算机与用户的交互界面，并在Turbo C中编写相应的算法，如下：void clear() （此函数为清屏幕函数）{①王号，陈骏. KTV 点歌系统的设计与实现[EB/OL].clrscr(); （此语句功能为清屏幕）gotoxy(0,0); （此语句功能为将光标定位在屏幕左上角）textbackground(15); （此语句功能为设置背景颜色为灰色）textcolor(0); （此语句功能为设置文字颜色为黑色）}①以上算法提供了计算机内存中的“歌曲点播列表”与用户的交互界面，其颜色搭配合理、清晰，因此，本文后面所编写的算法中对其有所引用。

在实现添加、插入、删除、调换、移动等功能的过程中，需要对字符串进行比较与复制。

在Turbo C中，实现对字符串进行比较的函数为strcmp(s,t),其作用是比较字符串s和t的大小，若s和t相等，则返回0；若s和t不相等，则返回非0整数值。

实现对字符串进行复制的函数是strcpy(s,t),其作用是将字符串t复制到字符串s中②。

二、功能设计要实现对歌曲点播列表的管理，首先要建立一个歌曲点播列表。

歌曲点播列表的逻辑结构符合线性结构的特征，即列表中每一首歌曲（除第一首和最后一首歌曲外），前面只有一首等待（或正在）播放的歌曲（即前驱），后面也只有一首接着要播放的歌曲（即后继）；而第一首歌曲（正在播放的歌曲）前面没有等待或正在播放的歌曲（前驱），后面只有一首等待播放的歌曲（后继）；最后一首歌曲后面没有等待播放的歌曲（后继），前面只有一首等待或正在播放的歌曲（前驱）。

因此要建立的歌曲点播列表为线性表。

由于歌曲点播列表中记录的歌曲数可以无限增多，也可以无限减少，也就是说其长度可以任意变化，若采用顺序存储结构，则需要事先估计容量，会存在浪费内存空间或预留空间不足的问题，所以采用链式存储结构。

而在链式存储结构中，由于单链表和双链表的存储结点中的数据域是相同的，而双链表每个存储结点中需要两个指针域，比单链表多一个，因此其存储密度③比单链表小，存储空间的利用率较单链表低。

另外，歌曲点播列表中的最后一首歌曲与第一首正在播放的歌曲之间并没有明显的逻辑关系，所以不必采用循环链表。

因此，选择单链表作为存储结构。

每个结点包含两个数据域和一个指针域，两个数据域均为字符数组，分别记录歌曲名和歌手姓名，指针域指向记录下一首歌曲信息的结点。

①田鲁怀. 数据结构[M]. 北京: 电子工业出版社, 2006: 53-53②张书云. C语言程序设计[M]. 北京: 中国铁道出版社, 2008:124-124③本文中要讨论的对于歌曲点播列表的操作如下：点歌、切歌、移动、调换、添加、插入、删除。

(一)点歌点歌的过程可以用向单链表的尾部插入结点的过程来模拟，因而点歌的算法设计运用了用尾插法建立带头结点的单链表①的算法设计思想，也可以说是运用了链接队列的入队运算②的算法设计思想。

值得注意的是，在刚进入KTV包间，交费之后，点歌之前，屏幕并不是空闲的，而是正播放一首系统默认的宣传歌曲（非顾客所点），这不妨用一个初始化的头结点来表示。

在第四部分介绍的程序中，初始化头结点的歌曲名设为NULL,歌手姓名设为null。

而点歌之后，系统自动开始播放被点歌曲，无需人工操作，如果点歌之后用头结点来记录正在被播放的歌曲，那么这一过程就是头结点的自动更新。

这也正是本文中所编写的点歌算法与用尾插法建立带头结点的单链表的算法和链接队列的入队运算的算法的不同之处。

因此，模拟点歌过程的算法设计思想如图1:图 1①田鲁怀. 数据结构[M]. 北京: 电子工业出版社, 2006:33-33②(二)切歌切歌过程也是对歌曲点播列表进行修改的基本操作之一，其算法的实现运用了链接队列的出队运算①的思想。

由于队列在执行出队运算前要判断队列是否为空，即判断队列中是否有元素，因此，这里也需要考虑到一种极端情况，即所有点过的歌都被切掉（尽管这种情况在KTV中顾客实际消费的时候很少见）。

这样，模拟切歌过程的算法设计思图 2不难发现，在点歌与切歌的过程中，对歌曲点播列表的运算符合队列②的运算限制，即只允许在歌曲点播列表的首部进行切歌，而在其尾部进行点歌。

因此，将可以将歌曲点播列表视为等待播放的歌曲的队列，其队头为正在被播放的歌曲。

所以，最先点的歌即为最先进入队列的元素，一定在歌曲点播列表中仅次于正在被播放的歌曲的位置，最后点的歌是最后进入队列的元素，必定在歌曲点播列表的尾部，每首歌必须按照点歌的次序顺序被切掉或被播放完毕，即离队。

这也与队列的先进先出（First In First Out,FIFO）的特征完全吻合。

又由于本文中的歌曲点播列表是以单链表为存储结构存储的，所以，表头指针指向的是正在被播放的歌曲，点歌过程类似于链接队列的入队运算，切歌过程类似于链接队列的出队运算。