链表实验报告1.doc

实验 一 线性表的基本操作实现及其应用 一、实验目的 1、熟练掌握线性表的基本操作在两种存储结构上的实现。 2、会用线性链表解决简单的实际问题。 二、实验内容 题目一 链表基本操作 该程序的功能是实现单链表的定义和操作。该程序包括单链表结构类型以及对单链表操 作的具体的函数定义和主函数。其中，程序中的单链表（带头结点）结点为结构类型， 结点值为整型。单链表操作的选择以菜单形式出现，如下所示： please input the operation： 1.初始化 2.清空 3.求链表长度 4.检查链表是否为空 5.检查链表是否为满 6.遍历链表（设为输出元素）7.从链表中查找元素 8.从链表中查找与给定元素值相同的元素在表中的位置 9.向链表中插入元素 10. 从链表中删除元素 其他键退出。。。。。 题目二 约瑟夫环问题 设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，每个人持有一个正整数 密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报 数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重 新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序 模拟此过程，求出出列编号序列。 struct node //结点结构 { int number; /* 人的序号 */ int cipher; /* 密码 */ struct node *next; /* 指向下一个节点的指针 */ }; 三．实验步骤 题目一 链表基本操作 (一)、数据结构与核心算法的设计描述 1、单链表的结点类型定义 /* 定义DataType为int类型 */ typedef int DataType; /* 单链表的结点类型 */ typedef struct LNode { DataType data; struct LNode *next; }LNode,*LinkedList; 2、初始化单链表 LinkedList LinkedListInit() { //函数功能：对链表进行初始化 参数：链表(linklist L) 成功初始化返回1,否则返回0 } 3、清空单链表 void LinkedListClear(LinkedList &L) {//函数功能：把链表清空 参数：链表(linklist L) 成功清空链表返回1 } 4、 检查单链表是否为空 int LinkedListEmpty(LinkedList L) { //函数功能:判断链表是否为空 参数：链表(linklist L) 链表为空时返回0,不为空返回1 } 5、 遍历单链表 void LinkedListTraverse(LinkedList L) { //函数功能:遍历链表,输出每个节点的elem值 参数：链表(linklist L) 通过循环逐个输出节点的elem值 } 6、 求单链表的长度 int LinkedListLength(LinkedList L) { //函数功能:返回链表的长度 参数：链表(linklist L) 函数返回链表的长度 } 7、 从单链表表中查找元素 LinkedList LinkedListGet(LinkedList L,int i) { //函数功能: 从链表中查找有无给定元素 参数;链表(linklist L),给定元素(int i) 如果链表中有给定元素(i)则返回1,否则返回0 } 8、从单链表表中查找与给定元素值相同的元素在链表中的位置 LinkedList LinkedListLocate(LinkedList L, DataType x) {//函数功能: 从链表中查找给定元素的位置 参数;链表(linklist L),给定元素(int i) 如果链表中有给定元素i则返回元素的位置, 没有则返回0 } 9、 向单链表中插入元素 void LinkedListInsert(LinkedList &L,int i,DataType x) { // L 为带头结点的单链表的头指针，本算法 // 在链表中第i 个结点之前插入新的元素 x } 10、 从单链表中删除元素 void LinkedListDel(LinkedList &L,DataType x) { 删除以 L 为头指针的单链表中第 i 个结点 } （二）、函数调用及主函数设计 zhujiemian(); cin>>a; do { switch(a) { case 1: if(init(L)==1) cout<<"成功初始化！"<<endl; else cout<<"初始化失败！"<<endl; break; case 2: if(makeempty(L)==1) cout<<"链表 【链表实验报告】 实验一主要关注线性表的基本操作，包括在两种不同的存储结构（这里没有具体提及第二种，但通常是指数组）上的实现。实验的核心是单链表，其结点包含整型数据，且带有头结点。实验内容分为两部分：链表基本操作和约瑟夫环问题。 在链表基本操作中，涉及以下功能： 1. **初始化**：创建一个空的单链表。`LinkedListInit()`函数用于初始化链表，返回一个链表的头指针，如果成功返回1，否则返回0。 2. **清空链表**：`LinkedListClear()`函数将链表中的所有结点移除，使链表为空。成功清空后返回1。 3. **检查链表是否为空**：`LinkedListEmpty()`函数通过检查链表头指针是否为空来判断链表状态，如果为空返回0，否则返回1。 4. **遍历链表**：`LinkedListTraverse()`函数遍历链表并打印每个结点的值，通常通过循环完成。 5. **求链表长度**：`LinkedListLength()`函数返回链表中的结点数量，即链表的长度。 6. **查找元素**：`LinkedListGet()`函数根据给定索引查找元素，若找到返回1，否则返回0。 7. **查找元素位置**：`LinkedListLocate()`函数寻找链表中与给定值相等的元素，返回其位置，若未找到返回0。 8. **插入元素**：`LinkedListInsert()`函数在链表的指定位置插入新元素，需要修改链表结构。 9. **删除元素**：`LinkedListDel()`函数删除链表中特定位置的元素，需维护链表的连通性。 在约瑟夫环问题中，给定人数n和报数上限m，模拟报数过程，每次报到m的人出局，然后重新从下一个人开始报数，直至所有人都出局。每个参与者有一个正整数密码，出局者的密码成为新的m值。实验要求实现一个程序，当n最大取30时，输出所有出局者的编号序列。 实验步骤涵盖了数据结构的设计（如单链表结点的定义）和核心算法的描述，以及函数的调用和主函数的构建。在主函数中，用户可以通过输入选择不同操作，并根据函数的返回值判断操作是否成功。 通过这个实验，学生不仅可以掌握线性链表的操作，还能了解如何运用链表解决实际问题，例如约瑟夫环问题。此外，实验还强调了链表操作的实现细节，如插入和删除操作对链表结构的影响，以及如何有效地遍历链表来查找和更新元素。这些技能对于理解和使用链表这一重要的数据结构至关重要。