《第一次实验线性表的实现及其应用》由会员分享，可在线阅读，更多相关《第一次实验线性表的实现及其应用（15页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验（数据结构实验（数据结构实验（数据结构实验（C C C C语言版）语言版）语言版）语言版）第一次实验第一次实验 线性表的实现及其应用线性表的实现及其应用 1一、实验内容一、实验内容1.用用C语言实现线性表的存储结构语言实现线性表的存储结构（顺序表或链表，任选其中之一）；（顺序表或链表，任选其中之一）；2.实现线性表所有基本操作的有关实现线性表所有基本操作的有关算法；算法；3.利用线性表解决某一实际问题（实利用线性表解决某一实际问题（实现学生成绩管理系统；实现集合的现学生成绩管理系统；实现集合的交运算和并运算）。交运算和并运算）。2二、关键技术分析二、关键技术分析1.顺序表的类型定义
2、顺序表的类型定义#define MAXNUM 100typedef int DateType; typedef Struct DataType dataMAXNUM; int last; /存放线性表中最后一个元素在数组存放线性表中最后一个元素在数组data 中的下中的下标标 SeqList;注意：注意：顺序表的类型定义顺序表的类型定义可存储在可存储在seqlist.h中。中。3二、关键技术分析二、关键技术分析2.顺序表的空间申请顺序表的空间申请在教材第在教材第6页中的页中的“置空表置空表”的程序的程序有错有错，缺少了申请存储空间的语句，故完整程缺少了申请存储空间的语句，故完整程序应该为：序应
3、该为：Void SeqLSetNull(SeqList *l) l=(SeqList*) malloc(sizeof(SeqList); l-last= -1; 注意：注意：教材第教材第6页至第页至第8页中的算法页中的算法给出了线性表在顺序表存储给出了线性表在顺序表存储结构下的所有基本操作的实现算法，结构下的所有基本操作的实现算法，可存储在可存储在seqlist.cpp中。中。4二、关键技术分析二、关键技术分析3.循环选择菜单的设计循环选择菜单的设计 循环选择菜单的设计可采用教材第循环选择菜单的设计可采用教材第9页至第页至第10页的方法，用页的方法，用do-while语句结合语句结合switc
4、h-case语句进行循环选择菜单的设计。语句进行循环选择菜单的设计。用户通过选择输入某个数字选择执行某个用户通过选择输入某个数字选择执行某个操作。当用户选择输入操作。当用户选择输入0时结束循环；否时结束循环；否则，每执行完某个操作（如用户输入则，每执行完某个操作（如用户输入6选选择执行插入操作）后，又重新显示菜单等择执行插入操作）后，又重新显示菜单等待用户输入新的选择数字。待用户输入新的选择数字。5二、关键技术分析二、关键技术分析4.带头结点的链表和不带头结点的链表带头结点的链表和不带头结点的链表 在实现链表的时候一定要注意，一般在实现链表的时候一定要注意，一般情况下宁可使用带头结点的链表，这
5、样在情况下宁可使用带头结点的链表，这样在实现插入操作和删除操作的时候会方便一实现插入操作和删除操作的时候会方便一些。些。 教材第教材第10页给出了单链表的结点类型页给出了单链表的结点类型LinkedList的定义；教材第的定义；教材第11页至第页至第12页中的页中的算法算法均是针对带头结点链表编的程序均是针对带头结点链表编的程序；算法算法是用是用“尾插法尾插法”建立带头结点单链表。建立带头结点单链表。算法算法是输出带头结点的单链表的算法。是输出带头结点的单链表的算法。而算而算法法是用是用“头插法头插法”建立不带头结点的单链表；建立不带头结点的单链表；可将教材第可将教材第10页中的单链表结构类型
6、定义页中的单链表结构类型定义存储在存储在linklist.h中；将算法中；将算法、 算法算法、存储在存储在linklist.cpp中，然后在主函数中用中，然后在主函数中用#include “linklist.h”和和#include “linklist.cpp”引用这两个文件。引用这两个文件。第第11页中的算法页中的算法有错，应改为：有错，应改为：void InitLList(LinkedList *L) L=(LinkedList) *malloc(sizeof(LinkedList); L-next=NULL;6二、关键技术分析二、关键技术分析5.集合交、并运算的实现集合交、并运算的实现(
7、P15P18) 这里假设集合中的元素都是某种这里假设集合中的元素都是某种DataType(如如int )类型，由于数据类型较简单类型，由于数据类型较简单,故可以利用故可以利用2.1中的顺中的顺序表（序表（seqlist.h和和seqlist.cpp ）或链表（）或链表（linklist.h和和linklist.cpp ）来实现线性表即可）来实现线性表即可(教材中是利用链表教材中是利用链表来做的来做的)。 用一个线性表来存放一个集合中的所有元素，用一个线性表来存放一个集合中的所有元素，此时只要忽略线性表的此时只要忽略线性表的“顺序顺序”特性即可特性即可。建议：建议：主函数中可设计一循环选择菜单提
8、示主函数中可设计一循环选择菜单提示 用户选择如下命令用户选择如下命令:1)输入集合输入集合A和集合和集合B； 2)求集合交运算；求集合交运算；2)3) 求集合并运算；求集合并运算； 0)退出。退出。7二、关键技术分析二、关键技术分析6.实现学生成绩管理系统实现学生成绩管理系统 但由于这里学生数据相对比较复杂，导致对单链但由于这里学生数据相对比较复杂，导致对单链表的输入、删除、插入等操作较为复杂，不能直接使表的输入、删除、插入等操作较为复杂，不能直接使用教材用教材2.1节中实现的单链表来表示线性表。必须重节中实现的单链表来表示线性表。必须重新设计线性表的结点新设计线性表的结点node(类型名为类
9、型名为LinkList，教材第，教材第19页）页）,并针对该线性表设计所需的全部操作（如建并针对该线性表设计所需的全部操作（如建立、插入、删除、输出及主函数模块）的算法。立、插入、删除、输出及主函数模块）的算法。 用一个用一个带头结点的带头结点的单链表来存放所有学生记单链表来存放所有学生记录录。注意：注意：线性链表是带头结点的链表，头指线性链表是带头结点的链表，头指针针head的类型应该为的类型应该为* LinkList类型。类型。8二、关键技术分析二、关键技术分析6.实现学生成绩管理系统实现学生成绩管理系统（1）学生记录链表的建立）学生记录链表的建立(即输入即输入)算法算法(P19P20)
10、void CreateLinkList(LinkList *head,int *n) 这里的这里的head 和和n是指针类型，是指针类型，head指向线性表的头结点指向线性表的头结点; n用作学生人数计数器（在主函数中用作学生人数计数器（在主函数中&n作为实元替代算法中作为实元替代算法中的虚元的虚元*n，通过指针类型完成，通过指针类型完成“主主”“子子”之间的数据传递，之间的数据传递，主程序中主程序中n的初值为的初值为0）；）； 程序中的指针程序中的指针s和和p为工作指针，为工作指针，s用以指示存放一条输入用以指示存放一条输入的学生记录的结点，的学生记录的结点，p用以始终指向表尾结点。用以始终
11、指向表尾结点。 对于教材（对于教材（P19P23）的几个算法，请注意）的几个算法，请注意以下几个关键点：以下几个关键点：head的初值也是在主函的初值也是在主函数中设置的，先为其申数中设置的，先为其申请一个请一个LinkList结点作结点作为头结点，并用为头结点，并用head指指向该结点。见教材向该结点。见教材23页页程序第程序第7行和第行和第8行。行。当用户输入的学号为当用户输入的学号为0时时while循环结束，否则继续输入循环结束，否则继续输入下一条学生记录。每输入一条记录成功时执行下一条学生记录。每输入一条记录成功时执行*n=*n+1;9二、关键技术分析二、关键技术分析6.实现学生成绩管
12、理系统实现学生成绩管理系统（2）在链表中插入一条学生记录）在链表中插入一条学生记录(P20P21) void InsertStu(LinkList *head,char num ,int *n) 这里的这里的head 和和n是指针类型，与上一程序中的意义相同。是指针类型，与上一程序中的意义相同。Num 是一个字符型数组，用以存储一个学号。是一个字符型数组，用以存储一个学号。 程序中设置一个标志变量程序中设置一个标志变量flag,在链表中若找到一记录的在链表中若找到一记录的学号与学号与num相等，则置相等，则置flag=1，p指向找到记录；否则指向找到记录；否则flag=0。当。当flag=1时
13、，新输入的记录的值替换时，新输入的记录的值替换p所指示的记录所指示的记录得值；当得值；当flag=0时，新输入的记录插入到表尾的位置上。时，新输入的记录插入到表尾的位置上。 对于教材（对于教材（P19P23）的几个算法，请注意）的几个算法，请注意以下几个关键点：以下几个关键点：当当flag=0时，执行一次时，执行一次*n=*n+1; 。在头指针为在头指针为head的学生记录为结点的单链表的学生记录为结点的单链表中查找有无学号等于中查找有无学号等于num的记录，若有，则的记录，若有，则用户输入的新纪录替代原老纪录；若没有，用户输入的新纪录替代原老纪录；若没有，则在单链表的末尾增加一条用户输入的新
14、纪则在单链表的末尾增加一条用户输入的新纪录，并执行一次录，并执行一次n+。10二、关键技术分析二、关键技术分析6.实现学生成绩管理系统实现学生成绩管理系统（3）在链表中删除一条学生记录操作）在链表中删除一条学生记录操作(P22) void DeleStu(LinkList *head,char num ,int *n) 这里的这里的head 、 num和和n的意义与上一程序中的意义相同。的意义与上一程序中的意义相同。其中指针类型可传递结果值至主函数或主程序。其中指针类型可传递结果值至主函数或主程序。 程序中设置工作指针程序中设置工作指针p和和s，当找到了一条记录的学号与，当找到了一条记录的学号
15、与num相等时，相等时，s指向该条记录，而指向该条记录，而p指向该条记录的直接前驱结指向该条记录的直接前驱结点，此时执行删除操作只需执行：点，此时执行删除操作只需执行： p-next=s-next; free(s);即可。即可。 对于教材（对于教材（P19P23）的几个算法，请注意）的几个算法，请注意以下几个关键点：以下几个关键点：删除成功时执行一次删除成功时执行一次*n=*n-1; ，否则，打印出错信息。，否则，打印出错信息。11二、关键技术分析二、关键技术分析6.实现学生成绩管理系统实现学生成绩管理系统（4）输出链表中所有学生记录操作）输出链表中所有学生记录操作(P22P23) void
16、DisplayStu(LinkList *head) 这里的这里的head 的意义与上一程序中的意义相同。的意义与上一程序中的意义相同。 程序中设置工作指针程序中设置工作指针h，初值指向第一条记录。每次输，初值指向第一条记录。每次输出一条记录时只需打印出一条记录时只需打印h所指的结点的各域的值即可，每打所指的结点的各域的值即可，每打印一条记录，印一条记录，h指针下移一条记录，直至指针下移一条记录，直至h为空指针值时为止。为空指针值时为止。 对于教材（对于教材（P19P23）的几个算法，请注意）的几个算法，请注意以下几个关键点：以下几个关键点：12二、关键技术分析二、关键技术分析6.实现学生成绩
17、管理系统实现学生成绩管理系统（5）主函数的设计）主函数的设计 建议设计一个循环选择菜单提供用户输入选择建议设计一个循环选择菜单提供用户输入选择操作码，当用户输入选择码为操作码，当用户输入选择码为0时结束，否则根据时结束，否则根据用户选择码执行相应操作。用户选择码执行相应操作。 对于教材（对于教材（P19P23）的几个算法，请注意）的几个算法，请注意以下几个关键点：以下几个关键点：13三、提交作业要求三、提交作业要求1.要求在虚拟机的要求在虚拟机的“作业宝作业宝”上完成并提上完成并提交作业；交作业；2.作业的第一部分应首先说明本次实验的作业的第一部分应首先说明本次实验的实验内容；实验内容；3. 作业的第二部分应给出本次实验完整的作业的第二部分应给出本次实验完整的程序清单；程序清单；4.作业的第三部分应给出实验的运行与测作业的第三部分应给出实验的运行与测试结果及其分析（应给出测试实例）。试结果及其分析（应给出测试实例）。14End15
