线性表实验报告.pdf
一实验名称 1.线性表基本操作；2.处理约瑟夫环问题 二试验目的：1 熟悉 C 语言的上机环境，掌握 C 语言的基本结构。2定义单链表的结点类型。3 熟悉对单链表的一些基本操作和具体的函数定义。4 通过单链表的定义掌握线性表的链式存储结构的特点。5熟悉对单链表的一些其它操作。三实验内容 1.编制一个演示单链表初始化、建立、遍历、求长度、查询、插入、删除等操作的程序。2.编制一个能求解除约瑟夫环问题答案的程序。实验一 线性表表的基本操作 问题描述：1.实现单链表的定义和基本操作。该程序包括单链表结构类型以及对单链表操作的具体的函数定义 程序中的单链表（带头结点）结点为结构类型，结点值为整型。/*定义 DataType 为 int 类型*/typedef int DataType;/*单链表的结点类型*/typedef struct LNode DataType data;struct LNode*next;LNode,*LinkedList;LinkedList LinkedListInit()/初始化单链表 void LinkedListClear(LinkedList L)/清空单链表 int LinkedListEmpty(LinkedList L)/检查单链表是否为空 void LinkedListTraverse(LinkedList L)/遍历单链表 int LinkedListLength(LinkedList L)/求单链表的长度/*从单链表表中查找元素*/LinkedList LinkedListGet(LinkedList L,int i)/*从单链表表中查找与给定元素值相同的元素在链表中的位置*/int LinkedListLocate(LinkedList L,DataType x)void LinkedListInsert(LinkedList L,int i,DataType x)/向单链表中插入元素/*从单链表中删除元素*/void LinkedListDel(LinkedList L,DataType x)/*用尾插法建立单链表*/LinkedList LinkedListCreat()2.约瑟夫环问题：任给正整数 N 和 K，按下述方法可以得到 1,2,n 的一个置换，将数字 1,2,n 环形排列，按顺时针方向自 1 开始报数，报到 K 时输出该位置上的数字，并使其出列。然后从他在顺时针方向的下一个数字继续报数，如此下去，直到所有的数字全部出列为止。例如 N=10，K=3，则正确的出列顺序应为 3，6，9，2，7，1，8，5，10，4。3.试单链表实现一个简单的电子通讯本管理软件，要求能查找联系地址，增加和删除联系人。联系方式假定包括姓名、电话和地址。基本要求：1.上机前要做好准备工作，包括程序框图、数据结构以及算法。2.按时实验 3.服从实验室老师的安排 4.独立实验，有问题可以讨论，但不得翻版。5.遵守实验室的各项纪律。四、概要设计 1.单链表的操作 (1)为了实现上述程序功能，需要定义单链表的抽象数据类型：ADT LinkedList 数据对象：D=ai|aistruct LNode set,i=0,1,2,n,n0 数据关系：R=|ai,ai+1 D 基本操作：LinkedListInit()操作结果：构造了一个带头节点的空链表 L;LinkedListCreat()初始条件：单链表 L 已存在；操作结果：建立了一个带头节点的非空链表；LinkedListClear(&L)初始条件：单链表 L 已存在；操作结果：将 L 重置为带头节点的空链表；LinkedListEmpty(&L)初始条件：单链表 L 已存在；操作结果：如果链表 L 为空则返回 1，链表 L 非空则返回 0；LinkedListLength(&L)初始条件：单链表 L 已存在；操作结果：返回单链表 L 中数据元素的个数，若 L 为空表则返回 0；LinkedListTraverse(&L)初始条件：单链表 L 已存在；操作结果：依次返回单链表 L 中各节点的元素值，若 L 为空表则显示链表为空；LinkedListGet(&L，i)初始条件：单链表 L 已存在；操作结果：显示链表 L 中第 i 个节点个元素值，若链表 L 中没有第 i 个节点则显示查询位置不正确；LinkedListLocate(&L，x)初始条件：单链表 L 已存在；操作结果：显示链表 L 中元素 x 的位置，若链表 L 中没有元素 x 则显示所查找元素不存在；LinkedListInsert(&L，i，x)初始条件：单链表 L 已存在；操作结果：在单链表 L 第 i 个节点后插入一个元素值为 x 的节点，L 的长度加 1，若单链表L 中没有第 i 个节点则显示插入位置不正确；LinkedListDel(&L，i)初始条件：单链表 L 已存在；操作结果：在单链表 L 中删除第 i 个节点，L 的长度减 1，若单链表 L 中没有第 i 个节点则显示删除位置不正确；(2)本程序包含 11 个函数：1.主函数 main()2.初始化单链表函数 LinkListInit()3.清空单链表函数 LinkedListClear（）4.检查单链表是否为空函数 LinkedListEmpty（）5.遍历遍历单链表函数 LinkedListTraverse（）6.求单链表的长度函数 LinkedListLength（）7.从单链表表中查找元素函数 LinkedListGet（）8 从单链表表中查找指定元素的位序函数 LinkedListLocate（）9.插入元素函数 LinkedListInsert（）10.删除元素函数 LinkedListDel（）11.建立单链表函数 LinkedListCreat()各函数之间的关系：五详细设计 1 结点类型和指针类型 typedef struct LNode int data;struct LNode*next;LNode,*LinkedList;2 单链表的基本操作（1）初始化单链表 LinkedList LinkedListInit()LinkedList L;L=(LinkedList)malloc(sizeof(LNode);L-next=NULL;return L;（2)清空单链表 void LinkedListClear(LinkedList L)L-next=NULL;printf(链表已经清空n);（3）检查单链表是否为空 int LinkedListEmpty(LinkedList L)main()LinkListInit()LinkedListClear（）LinkedListEmpty（）LinkedListTraverse（）LinkedListLength（）LinkedListGet（）LinkedListLocate（）LinkedListInsert（）LinkedListDel（）LinkedListCreat()if(L-next=NULL)return TRUE;else return FALSE;（4）遍历单链表 void LinkedListTraverse(LinkedList L)LinkedList p;p=L-next;if(p=NULL)printf(单链表为空表n);else printf(链表中的元素为:n);while(p!=NULL)printf(%d,p-data);p=p-next;printf(n);（5）求单链表长度 int LinkedListLength(LinkedList L)LinkedList p;int j;p=L-next;j=0;while(p!=NULL)j+;p=p-next;return j;（6）从链表中查找元素 LinkedList LinkedListGet(LinkedList L,int i)LinkedList p;int j;p=L-next;j=1;while(p!=NULL&jnext;j+;if(j=i)return p;else return NULL;（7）从链表中查找与给定元素值相同的元素在顺序表中的位置 int LinkedListLocate(LinkedList L,int x)LinkedList p;int j;p=L-next;j=1;while(p!=NULL&p-data!=x)p=p-next;j+;if(p)return j;else return 0;（8）向链表中插入元素 void LinkedListInsert(LinkedList L,int i,int x)LinkedList p,s;int j;j=1;p=L;while(p&jnext;j+;if(p=NULL|ji)printf(插入位置不正确n);else s=(LNode*)malloc(sizeof(LNode);s-data=x;s-next=p-next;p-next=s;printf(%d 已插入到链表中n,x);（9）从链表中删除元素 void LinkedListDel(LinkedList L,int i)LinkedList p,q;int j;j=1;p=L;while(p-next&jnext;j+;if(p-next=NULL)printf(删除位置不正确n);else q=p-next;p-next=q-next;free(q);printf(第%d 个元素已从链表中删除n,i);（10）建立单链表 LinkedList LinkedListCreat()LinkedList L=LinkedListInit(),p,r;int x;r=L;printf(请依次输入链表中的元素,输入负数时结束n);scanf(%d,&x);while(x=0)p=(LinkedList)malloc(sizeof(LNode);p-data=x;r-next=p;r=p;scanf(%d,&x);r-next=NULL;return L;（11）主函数 main()int i,h,d,e,x,j,n,q;char ch;LinkedList L,p;while(q!=0)printf(请选择要进行的操作n);printf(1.初始化 2.清空 3.求链表长度 4.检查链表是否为空n);printf(5.遍历链表 6.从链表中查找元素n);printf(7.从链表中查找与给定元素值相同的元素在顺序表中的位置n);printf(8.向链表中插入元素 9.从链表中删除元素n);printf(10.建立单链表n);printf(按其它键结束n);scanf(%d,&x);switch(x)case 1:L=LinkedListInit();printf(链表已经初始化 n);break;case 2:LinkedListClear(L);printf(n);break;case 3:printf(链表的长度为%dn,LinkedListLength(L);break;case 4:i=LinkedListEmpty(L);if(i)printf(链表为空n);else printf(链表非空n);break;case 5:LinkedListTraverse(L);break;case 6:printf(请输入待查询元素在链表中的位置:);scanf(%d,&j);p=LinkedListGet(L,j);if(p)printf(链表中第%d 个元素的值为:%dn,j,p-data);else printf(查询位置不正确n);break;case 7:printf(请输入待查询元素的值:);scanf(%d,&e);h=LinkedListLocate(L,e);if(h)printf(%d 在链表中的位置是:%dn,e,h);else printf(链表中没有值为%d 的元素n,e);break;case 8:printf(请输入插入元素的位置和值(中间以空格或回车分隔):n);scanf(%d%d,&d,&e);LinkedListInsert(L,d,e);break;case 9:if(LinkedListLength(L)=0)printf(链表已经为空,不能删除n);else printf(请输入待删除元素的位置:n);scanf(%d,&n);LinkedListDel(L,n);break;case 10:L=LinkedListCreat();printf(n);break;default:q=0;六测试结果 1、单链表的操作 (1)建立单链表：选择 1，然后选择 10，输入 1.2.3.4.5.6.7.8.9 最后一个负数(2)求链表长度：选择 3，得到执行结果：链表的长度为 9(3)检查链表是否为空：选择 4，得到执行结果：单链表非空 (4)遍历链表：选择 5，得到执行结果：链表中的元素为 1，2，3，4，5，6，7，8，9，(5)从链表中查找元素：选择 6，输入 5，显示：链表中第 5 个元素的值为 5 (6)从链表中查找与给定元素值相同的元素在顺序表中的位置 选择 7，输入 2，显示：2 在链表中的位置是：2 选择 7，输入 25，显示：链表中没有值为 25 的元素(7)向链表中插入元素 选择 8，输入（6，5），显示 5 以插入到链表中 选择 5：链表中的元素为 1，2，3，4，5，5，6，7，8，9，(8)从链表中删除元素 选择 9，输入 5，显示 第 5 个元素已从表中删除 选择 9，输入 12，显示 删除位置不正确 选择 5，显示 链表中的元素为 链表中的元素为 1，2，3，4，5，6，7，8，9，实验二 约瑟夫环 1.问题描述 设有编号 1,2,3。n(n0)的 N 个人围成一个圈，每个人持有一个密码（正整数）。开始时从第 k（1=k=n）个人按顺时针方向自 1 开始顺序报数，报到 m（m 为第 K 个人的密码）的人出圈，再以这个人顺时针方向上的下一个人的密码为 m，并开始重新从 1 报数。如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。例如，设总人数 n 的初值为 8，他们所持的密码分别为：3,10,7,1,4,8,4,5，开始报数人的编号 k 的初值为 7，则出列顺序为：2,1,3,4,8,5,7,6 2.数据结构设计 问题中以序号标示某个人，所以结点的数据域设为一个整型类型的变量 当某人出圈后，报数的工作要从下一个人开始继续，剩下的人仍然围成一圈，可以使用循环表。由于出圈的人将不再属于圈内，意味着数据元素的删除。因此，算法中存有频繁的元素删除操作，存储结构宜采用链表。每个结点中既存储密码还存储初始位置，所以结点有两个数据域，一个指针域。另外，每个结点代表一个人所以，可以令尾结点指针指向首元结点来进行循环。/结点类 template struct Node /数据成员:ElemType data;ElemType num;/数据域 Node*next;/指针域 /构造函数:Node();/无参数的构造函数 Node(ElemType item,ElemType item1,Node*link=NULL);/已知数数据元素值和指针建立结构;/结点类的实现部分 template Node:Node()/操作结果：构造指针域为空的结点 next=NULL;template Node:Node(ElemType item,ElemType item1,Node*link)/操作结果：构造一个数据域为 item 和 item1，指针域为 link 的结点 data=item;num=item1;next=link;#endif 3.算法设计 编写一个函数实现结点的删除与输入工作，另编写一个主函数 main（）完成链表的创建与函数调用工作。（1）插入 template Status LinkList:Insert(int position,const ElemType&e)/操作结果：在线性表的第 position 个位置前插入元素 e/position 的取值范围为 1positionLength()+1/position 合法时返回 SUCCESS,否则函数返回 RANGE_ERROR if(position Length()+1)/position 范围错 return RANGE_ERROR;/位置不合法 else /position 合法 Node*tmpPtr;/取出指向第 position-1 个结点的指针 tmpPtr=GetElemPtr(position-1);Node*newPtr;if(positionLength()/如果插入尾结点，则域指针指向首元结点 newPtr=new Node(e,position,head-next);else newPtr=new Node(e,position,tmpPtr-next);/生成新结点 tmpPtr-next=newPtr;/将 tmpPtr 插入到链表中 curPosition=position;/设置当前位置的序号 curPtr=newPtr;/设置指向当前位置的指针 count+;/插入成功后元素个数加 1 return SUCCESS;（2）删除 template Status LinkList:Delete(int position,ElemType&e)/操作结果：删除线性表的第 position 个位置的元素,并用 e 返回其值,/position 的取值范围为 1positionLength(),/position 合法时函数返回 SUCCESS,否则函数返回 RANGE_ERROR /position 合法 Node*tmpPtr;if(position=1)/如果删除首元结点，取出指向尾结点的指针 tmpPtr=GetElemPtr(Length();else /取出指向第 position-1 个结点的指针 tmpPtr=GetElemPtr(position-1);Node*nextPtr=tmpPtr-next;if(position=1)/头结点与新的首元结点相连 head-next=nextPtr-next;/nextPtr 为 tmpPtr 的后继 tmpPtr-next=nextPtr-next;/删除结点 e=nextPtr-data;/用 e 返回被删结点元素值 if(position=Length()/删除尾结点,当前结点变为头结点 curPosition=1;/设置当前位置的序号 curPtr=head-next;/设置指向当前位置的指针 else /删除非尾结点,当前结点变为第 position 个结点 curPosition=position;/设置当前位置的序号 curPtr=tmpPtr-next;/设置指向当前位置的指针 count-;/删除成功后元素个数减 1 delete nextPtr;/释放被删结点 return SUCCESS;（3）出圈次序的算法描述 template int LinkList:Pass(int position,int n,ElemType&e)int i;curPtr=GetElemPtr(position);/当前指针指向 position curPosition=position;/记录当前位置 for(i=0;inext;curPosition+;coutnum;/输出起始位置 e=curPosition;（4）主程序#includeassistance.h#includelk_list.h int POS(int n,int i)/计算当前位置的函数 if(n%i=0)n=i;else n=n%i;return n;int main()int tmp,i,k=0,n=0,key;int pos;LinkList lc;/创建空链表 while(n20)/限制人数 coutn;cout请输入每个人的密码，用空格分隔，密码大于 0:endl;for(i=1;itmp;lc.Insert(i,tmp);/插入尾结点 while(kn)cout从几号开始？0K=nk;cout0;i-)if(i=n)/一开始，从 k 开始报数 lc.GetElem(k,key);lc.Pass(k,key,tmp);/出列 pos=POS(tmp,i);/计算出列位置 lc.Delete(pos,tmp);/删除当前结点，当前指针指向当前位置的下游 else lc.GetElem(key);/取当前位置的密码 lc.Pass(key,tmp);/从当前位置开始报数，并出列 pos=POS(tmp,i);/计算出列位置 lc.Delete(pos,tmp);system(pause);return 0;九：心得体会 通过做这次实验，发现自己在数据结构这门课程中还有很多不足，有很多知识还没掌握实验的时候出现了很多错误，有很多知识还不能运用，最后在同学的帮助下，终于完成了任务。因为以前的 C 语言没学好，这学期的数据结构感到学的时候有些吃力，在实验的时候，我所以的不足都体现出来了，如果没有同学的帮助，我程序中的问题可能需要很长时间才会解决，所以以后还是要努力赶上来。在这次实验中，我也得到了很多收获，比如链表的应用，以前总是弄不明白，通过这次实验，在链表这一方面我懂了很多，但还不能运用自如，需要更多的练习。这次实验，对本学期所学习的内容也是一次巩固，让我加深了对学过知识的记忆。总之，这次实验让我既发现了自身的很多不足，又增长了很多知识。#include#include#define TRUE 1#define FALSE 0 typedef struct LNode int data;struct LNode*next;LNode,*LinkedList;LinkedList LinkedListInit()LinkedList L;L=(LinkedList)malloc(sizeof(LNode);L-next=NULL;return L;void LinkedListClear(LinkedList L)L-next=NULL;printf(链表已经清空n);int LinkedListEmpty(LinkedList L)if(L-next=NULL)return TRUE;else return FALSE;void LinkedListTraverse(LinkedList L)LinkedList p;p=L-next;if(p=NULL)printf(单链表为空表n);else printf(链表中的元素为:n);while(p!=NULL)printf(%d,p-data);p=p-next;printf(n);int LinkedListLength(LinkedList L)LinkedList p;int j;p=L-next;j=0;while(p!=NULL)j+;p=p-next;return j;LinkedList LinkedListGet(LinkedList L,int i)LinkedList p;int j;p=L-next;j=1;while(p!=NULL&jnext;j+;if(j=i)return p;else return NULL;int LinkedListLocate(LinkedList L,int x)LinkedList p;int j;p=L-next;j=1;while(p!=NULL&p-data!=x)p=p-next;j+;if(p)return j;else return 0;void LinkedListInsert(LinkedList L,int i,int x)LinkedList p,s;int j;j=1;p=L;while(p&jnext;j+;if(p=NULL|ji)printf(插入位置不正确n);else s=(LNode*)malloc(sizeof(LNode);s-data=x;s-next=p-next;p-next=s;printf(%d 已插入到链表中n,x);void LinkedListDel(LinkedList L,int i)LinkedList p,q;int j;j=1;p=L;while(p-next&jnext;j+;if(p-next=NULL)printf(删除位置不正确n);else q=p-next;p-next=q-next;free(q);printf(第%d 个元素已从链表中删除n,i);LinkedList LinkedListCreat()LinkedList L=LinkedListInit(),p,r;int x;r=L;printf(请依次输入链表中的元素,输入负数时结束n);scanf(%d,&x);while(x=0)p=(LinkedList)malloc(sizeof(LNode);p-data=x;r-next=p;r=p;scanf(%d,&x);r-next=NULL;return L;main()int i,h,d,e,x,j,n,q;char ch;LinkedList L,p;while(q!=0)printf(请选择要进行的操作n);printf(1.初始化 2.清空 3.求链表长度 4.检查链表是否为空n);printf(5.遍历链表 6.从链表中查找元素n);printf(7.从链表中查找与给定元素值相同的元素在顺序表中的位置n);printf(8.向链表中插入元素 9.从链表中删除元素n);printf(10.建立单链表n);printf(按其它键结束n);scanf(%d,&x);switch(x)case 1:L=LinkedListInit();printf(链表已经初始化 n);break;case 2:LinkedListClear(L);printf(n);break;case 3:printf(链表的长度为%dn,LinkedListLength(L);break;case 4:i=LinkedListEmpty(L);if(i)printf(链表为空n);else printf(链表非空n);break;case 5:LinkedListTraverse(L);break;case 6:printf(请输入待查询元素在链表中的位置:);scanf(%d,&j);p=LinkedListGet(L,j);if(p)printf(链表中第%d 个元素的值为:%dn,j,p-data);else printf(查询位置不正确n);break;case 7:printf(请输入待查询元素的值:);scanf(%d,&e);h=LinkedListLocate(L,e);if(h)printf(%d 在链表中的位置是:%dn,e,h);else printf(链表中没有值为%d 的元素n,e);break;case 8:printf(请输入插入元素的位置和值(中间以空格或回车分隔):n);scanf(%d%d,&d,&e);LinkedListInsert(L,d,e);break;case 9:if(LinkedListLength(L)=0)printf(链表已经为空,不能删除n);else printf(请输入待删除元素的位置:n);scanf(%d,&n);LinkedListDel(L,n);break;case 10:L=LinkedListCreat();printf(n);break;default:q=0;
