实验一 线性表的基本操作实现及其应用(19页).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、单链表的结点类型定义/* 预处理命令 */#define OK 1;#define ERROR 0;#define OVERFLOW -1;/* 定义DataType,status为int类型 */typedef int DataType;typedef int status;/* 单链表的结点类型 */typedef struct LNodeDataType data;struct LNode *next;LNode,*LinkedList;2、初始化单链表LinkedList LinkedListInit() /定义并返回头结点L3、清空单链表 void LinkedListClear(LinkedList L)/ L是带头结点的链表的头指针,释放除头结点外的所有内存空间4检查单链表是否为空int LinkedListEmpty(LinkedList L)/ L是带头结点的链表的头指针,判断头结点的next是否为空,如果空/返回OK，否则返回ERROR5、 遍历单链表void LinkedListTraverse(LinkedList L)/ L是带头结点的链表的头指针,遍历并输出L所有结点（不包括头/结点）的数据6、求单链表的长度int LinkedListLength(LinkedList L)/ L是带头结点的链表的头指针，通过遍历链表用i记录结点个数（不/包括头结点），并返回i7、从单链表表中查找元素LinkedList LinkedListGet(LinkedList L,int i)/L是带头结点的链表的头指针,返回第 i 个元素8、从单链表表中查找与给定元素值相同的元素在链表中的位置（位置） int LinkedListGet1(LinkedList L,DataType x)/L是带头结点的链表的头指针,返回值为x元素在链表中的位置的/位置9、从单链表表中查找与给定元素值相同的元素在链表中的位置（指针）LinkedList LinkedListLocate(LinkedList L, DataType x)/L是带头结点的链表的头指针,返回值为x元素的指针10、 向单链表中插入元素 status LinkedListInsert(LinkedList L,int i,DataType x)(二) 函数调用及主函数设计Main函数初始化链表调用菜单函数1.清空2.求链表长度3.检查链表是否为空4.遍历链表5. 按位置查找元素6.按值查找元素7.向链表中插入元素8.从链表中删除元素9.退出等待选择，等输入1-9时，调用对应函数，否则退出程序结束输入1-9输入非1-9图1.主函数流程图(三) 程序调试及运行结果分析1进入选择界面后，先选择7，进行插入：2.选择4，进行遍历，结果为：3. 选择2，得出当前链表长度.4.选择3，得出当前链表为.5. 选择分别选择5、6进行测试.6. 选择8，分别按位置和元素值删除.7. 选择9，或非1-8的字符，程序结束.(四) 实验总结 通过这次实验，我对线性链表有了更深的理解，深入明白了线性存储结构与链式存储结构在内存存储的不同特点，同时我还学会了用这些知识实际解决一些问题，能够更加熟练地将算法转化为实际程序。同时，在写程序和调试程序的过程中，学会了一些书写技巧和调试技巧，这对于自己能在短时间高效的写出正确地程序有很大作用。四、主要算法流程图及程序清单1. 主要算法流程图：(1) 从单链表表中查找与给定元素值相同的元素在链表中的位置p=p->nextp&&!(p->data=x)true调用函数，传入参数L，xp=L->nextfalse返回p调用函数，传入参数L，i，x建立新结点s，令s->data=x;p=L->nexti=1p=nullfalseL->next=s;s->next=NULL;trueL->next=s;s->next=p;j=1j<i-1&&pp=p->nextj+trueq=p->next;p->next=s;s->next=q;P不为空返回对应值FalseFalse2. 程序清单：#include<iostream>using namespace std;#include<conio.h>#include<stdlib.h>/* 预处理命令 */#define OK 1;#define ERROR 0;#define OVERFLOW -1; /* 单链表的结点类型 */typedef struct LNodeint data;struct LNode *next;LNode,*LinkedList;/*初始化单链表*/LinkedList LinkedListInit()/定义并返回头结点LinkedList L;L=(LinkedList)malloc(sizeof(LNode);L->next=NULL;return L;/*清空单链表*/void LinkedListClear(LinkedList L)/释放除头结点外的所有内存空间LinkedList p=L->next,q;L->next=NULL;while (p)q=p->next;free(p);p=q;cout<<"ttt已清空！"<<endl;/*检查单链表是否为空*/int LinkedListEmpty(LinkedList L)/判断头结点的next是否为空,如果空返回OK，否则返回ERRORif (!(L->next)return OK;return ERROR;/*遍历单链表*/void LinkedListTraverse(LinkedList L)/遍历并输出L所有结点（不含头结点）的数据LinkedList p=L->next;if (!p)cout<<"ttt链表为空！"<<endl;cout<<"tt"while(p)cout<<p->data<<"t"p=p->next;cout<<endl;/*求单链表的长度*/int LinkedListLength(LinkedList L)/通过遍历链表用i记录结点个数（不含头结点），并返回iLinkedList p=L->next;int i=0;while(p)i+;p=p->next;return i;/*从单链表表中查找元素*/LinkedList LinkedListGet(LinkedList L,int i)/L是带头结点的链表的头指针,返回第 i 个元素LinkedList p=L->next;int j=1;while(j<i&&p)p=p->next;j+;if (!p)return NULL;return p;/*从链表中查找与给定元素值相同的元素在表中的位置,返回位置*/int LinkedListGet1(LinkedList L,int x)/L是带头结点的链表的头指针,返回值为x元素的位置LinkedList p=L->next;int i=1;while(p&&!(p->data=x)i+;p=p->next;if (!p)return 0;return i;/*从单链表表中查找与给定元素值相同的元素在链表中的位置*/LinkedList LinkedListLocate(LinkedList L, int x)/L是带头结点的链表的头指针,返回值为x元素的指针LinkedList p=L->next;while(p&&!(p->data=x)p=p->next;if (!p)return NULL;return p;/*向单链表中插入元素*/int LinkedListInsert(LinkedList L,int i,int x)/ L 为带头结点的单链表的头指针，本算法/ 在链表中第i 个结点之前插入新的元素 xLinkedList s=(LinkedList)malloc(sizeof(LNode);s->data=x;LinkedList p=L->next,q;if (i=1)if (p=NULL)L->next=s;s->next=NULL;return OK;elseL->next=s;s->next=p;return OK;int j=1;while(j<i-1&&p)p=p->next;j+;if (!p)free(s);return ERROR;q=p->next;p->next=s;s->next=q;return OK;/*从单链表中删除元素*/int LinkedListDel(LinkedList L,int x)/删除以 L 为头指针的单链表中值为x结点LinkedList p=L->next,q=L;while(p&&!(p->data=x)q=p;p=p->next;if (!p)return ERROR;q->next=p->next;free(p);return OK;int LinkedListDel(LinkedList L,int i,int &x)/删除以 L 为头指针的单链表中第 i 个结点,并返回x的值LinkedList p=L->next,q=L;int j=1;while(j<=i-1&&p)q=p;p=p->next;j+;if (!p)x=0;return ERROR;q->next=p->next;x=p->data;free(p);return OK;/*菜单显示*/void ScreenShow()cout<<"ttt"<<"1.清空"<<endl;cout<<"ttt"<<"2.求链表长度"<<endl;cout<<"ttt"<<"3.检查链表是否为空"<<endl;cout<<"ttt"<<"4.遍历链表"<<endl;cout<<"ttt"<<"5.从链表中查找元素 "<<endl;cout<<"ttt"<<"6.从链表中查找与给定元素值相同的元素在表中的位置"<<endl;cout<<"ttt"<<"7.向链表中插入元素"<<endl;cout<<"ttt"<<"8.从链表中删除元素"<<endl;cout<<"ttt"<<"9.退出"<<endl;/*主函数*/int main()/初始化链表int i=1;LinkedList L=LinkedListInit();if (L)cout<<"ttt初始化成功！n"<<endl;/显示菜单ScreenShow();/进行选择，当选择为1-8时，进行对应功能函数调用，否则退出程序while(i>=1&&i<=8)cout<<"tt"<<"请选择："cin>>i;switch (i)/1、清空链表case 1:LinkedListClear(L);break;/2.求链表长度case 2:cout<<"ttt链表长度为："<<LinkedListLength(L)<<endl;getch(); break;/3.检查链表是否为空case 3:if (!LinkedListEmpty(L)cout<<"ttt链表不为空！"<<endl;elsecout<<"ttt链表为空！"<<endl;getch(); break;/4.遍历链表case 4:LinkedListTraverse(L);getch(); break;/5.从链表中查找元素case 5:cout<<"ttt请输入要查询的位置i："int j;cin>>j;if (LinkedListGet(L,j)cout<<"ttt位置i的元素值为："<<LinkedListGet(L,j)->data<<endl;elsecout<<"ttti大于链表长度！"<<endl;getch(); break;/6.从链表中查找与给定元素值相同的元素在表中的位置case 6:cout<<"ttt请输入要查找的元素值："int b;cin>>b;if (LinkedListGet1(L,b)cout<<"ttt要查找的元素值位置为："<<LinkedListGet1(L,b)<<endl;cout<<"ttt要查找的元素值内存地址为："<<LinkedListLocate(L,b)<<endl;elsecout<<"ttt该值不存在！"<<endl;getch(); break;/7.向链表中插入元素case 7:cout<<"ttt请输入要插入的值："int x; cin>>x;cout<<"ttt请输入要插入的位置："int k; cin>>k;if(LinkedListInsert(L,k,x)cout<<"ttt插入成功！"<<endl;elsecout<<"ttt插入失败！"<<endl;getch(); break;/8.从链表中删除元素case 8:cout<<"ttt1.按位置删除"<<endl;cout<<"ttt2.按元素删除"<<endl;int d;cout<<"tt请选择："cin>>d;switch(d)case 1:cout<<"ttt请输入删除位置："cin>>d;int y;if (LinkedListDel(L,d,y)cout<<"ttt"<<y<<"被删除！"<<endl;elsecout<<"ttt删除失败！"<<endl; break;case 2:cout<<"ttt请输入删除元素："int y;cin>>y;if (LinkedListDel(L,y)cout<<"ttt"<<y<<"被删除！"<<endl;elsecout<<"ttt删除失败！"<<endl; getch(); break;return 1;题二 约瑟夫环问题算法、思想为了解决这一问题，可以先定义一个长度为30（人数）的数组作为线性存储结构，并把该数组看成是一个首尾相接的环形结构，那么每次报m的人，就要在该数组的相应位置做一个删除标记，该单元以后就不再作为计数单元。这样做不仅算法较复杂，而且效率低，还要移动大量的元素。用单循环链表来解决这一问题，实现的方法相对要简单得的多。首先定义链表结点，单循环链表的结点结构与一般单链表的结点结构完全相同，只是数据域用一个整数来表示位置；然后将它们组成一个具有n个结点的单循环链表。接下来从位置为1的结点开始数，数到第m个结点，就将此结点从循环链表中删去，然后再从删去结点的下一个结点开始数起，数到第m个结点，再将其删去，如此进行下去，直至全部删去为止。代码分析(一) 创建单循环链表 struct Link int Data;Link*next; Link *Creat(int n) Link *head,*s,*r; head=new Link; r=head; for (int i=0;i<n;i+) s=new Link; cin>>s->Data; r->next=s; r=s; r->next=head->next; return head; (二) “约瑟夫环”的操作模块；Link* Jose(Link*p,int m) int s=m; if (p=p->next) return p;/递归出口即循环链表只剩下一个结点，将该结点指针返回 Link*q=NULL;/指针q用来保存删除结点的前驱 for (int j=1;j<s;j+) q=p; p=p->next; /查找要删除结点 q->next=p->next; /删除节点 cout<<p->Data<<" " /输出结点序号 Jose(p->next,s);/递归调用 (三) 主程序int main() cout<<"请输入Jose环中人数：" int n,m; cin>>n; cout<<"请输入每个人手中的序号："<<endl; Link*head=Creat(n); cout<<"请输入报数的数值" cin>>m; Link*p=head->next; cout<<endl; cout<<"离开的序号依次是：" Link*Result=Jose(p,m); cout<<Result->Data<<endl; return 0; 测试数据调试分析1、早期程序只写了约瑟夫环的实现部分，没有对输入数据进行筛选，调试的时候会经常出错。比如是输入字母，或者输入0，大于32767溢出；2、早期的循环过程中没有进行优化，导致循环次数过多，浪费时间；3、为了输出时美观，分别在input和main函数主体内做了两次，输入非零的判断，浪费了资源；4、算法的时空分析为了限制在输入过程中不会上溢，只在输入中限定为四个不全为零的数字，但是做的是dowhile循环，复杂度为o（1）;当n大于1时：在数据输入中，链表的创建是for循环，时间复杂度为o（n-1）在约瑟夫环实现程序中，为for循环。时间复杂度为o（m%n -1）当n=1时，复杂度为o（1）。实验心得1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。3、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。4、通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。-第 19 页-