线性表实验报告

1、一.实验名称1 .线性表基本操作；2.处理约瑟夫环问题二.试验目的：1 .熟悉C语言的上机环境，掌握C语言的基本结构。2 .定义单链表的结点类型。3 .熟悉对单链表的一些基本操作和具体的函数定义。4 .通过单链表的定义掌握线性表的链式存储结构的特点。5 .熟悉对单链表的一些其它操作。三.实验内容L编制一个演示单链表初始化、建立、遍历、求长度、查询、插入、删除等操作的程序。2 .编制一个能求解除约瑟夫环问题答案的程序。实验一线性表表的基本操作问题描述:1 .实现单链表的定义和基本操作。该程序包括单链表结构类型以及对单链表操作 的具体的函数定义程序中的单链表（带头结点）结点为结构类型，结点值为整型

2、。/*定义DataType为int类型*/typedef int DataType;/*单链表的结点类型*/typedef struct LNode DataType data; struct LNode *next;LNodez *LinkedList;LinkedList LinkedListlnit () /初始化单链表void LinkedListClear (LinkedList L) / 清空单链表 int LinkedListEmpty (LinkedList L)检查单链表是否为空 void LinkedListTraverse (LinkedList L) / 遍历单链表 i

3、nt LinkedListLength (LinkedList L) 求单链表的长度 /*从单链表表中查找元素*/ LinkedList LinkedListGet(LinkedList L,int i)/*从单链表表中查找与给定元素值相同的元素在链表中的位置*/ int LinkedListLocate(LinkedList L, DataType x) void LinkedListlnsert (LinkedList L, int iz DataType x) 向单链表中插入元素/*从单链表中删除元素*/void LinkedListDel(LinkedList L,DataType x

4、)/*用尾插法建立单链表*/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, 4o3,试单链表实现一个简单的电子通讯本管理软件，要求能查找联系地址，增加和删除 联系人。联系方式假定包括姓名、电话和地址。基本要求：1 .上机前要做好准备工作

5、，包括程序框图、数据结构以及算法。2 .按时实验3 .服从实验室老师的安排4 .独立实验，有问题可以讨论，但不得翻版。5 .遵守实验室的各项纪律。四、概要设计1.单链表的操作(1)为了实现上述程序功能，需要定义单链表的抽象数据类型：ADT LuikedList 数据对象：D=ai ai G stiuct LNode set,i=0J2数据关系：R= <ai,ai+1 >|ai,ai+1 D基本操作：LinkedListInit()操作结果：构造了一个带头节点的空链表L;LHikedListCreatQ初始条件：单链表L已存在；操作结果：建立了一个带头节点的非空链表；LinkedLi

6、stClear(&L)初始条件：单链表L已存在；操作结果：将L重置为带头节点的空链表；LuikedListEmptv(&L)初始条件：单链表L已存在；操作结果：如果链表L为空则返回1,链表L非空则返回0：LHikedListLength(&L)初始条件：单链表L已存在；操作结果：返回单链表L中数据元素的个数，若L为空表则返回0： LuikedListTraverse(&L)初始条件：单链表L已存在；操作结果：依次返回单链表L中各节点的元素值，若L为空表则显示链表为空； LuikedListGet(&L, i)初始条件：单链表L已存在；操作结果：显示链表L

7、中第1个节点个元素值，若链表L中没有第1个节点则显示查询位置 不正确：LuikedListLocate(&L, x)初始条件：单链表L已存在；操作结果：显示链表L中元素x的位置，若链表L中没有元素x则显示所查找元素不存在： LuikedListInseit(&L, i, x)初始条件：单链表L已存在；操作结果：在单链表L第1个节点后插入一个元素值为x的节点，L的长度加1,若单链表 L中没有第1个节点则显示插入位置不正确；LuikedListDel(&L, i)初始条件：单链表L已存在；操作结果：在单链表L中删除第1个节点，L的长度减1,若单链表L中没有第1个节点则 显示

8、删除位置不正确；(2)本程序包含11个函数：1 .主函数niarnQ2 .初始化单链表函数LuikListhutO3 .清空单链表函数LuikedListClear ()4 .检查单链表是否为空函数LuikedListEmpty ()5,遍历遍历单链表函数LmkudListTraverse ()6 .求单链表的长度函数LnikedListLength ()7 .从单链表表中查找元素函数LmkedListGet ()8从单链表表中查找指定元素的位序函数LuikedListLocate ()9 .插入元素函数 LnikedListliisert ()10 .删除元素函数LinkedListDel

9、()11 .建立单链表函数LinkedListCreat()各函数之间的关系：LuikL IStllllt 0Luike dList Clear ()Linke dList EmptLiiike dList Trave rse ()Liiike dList Lengt h ()LinkeLiiikeLiiikeLinkeLiiikedListdListdListldListdListGetOLocatnseitDelOCreat(e ()()五.详细设计1结点类型和指针类型 typedef stnict LNode mt data;struct LNode "next; LNode,

10、*LuikedList;2单链表的基本操作(1)初始化单链表LnikedList LmkedListlnitQ LuikedList L;L=(LinkedList)malloc(sizeof(LNode);L->next=NULL;return L;)(2)清空单链表void LinkedListCleai (LnikedList L) L->next=NULL;pnntf("链表已经清空n)(3)检查单链表是否为空 mt LnikedListEmpty(LuikedList L)if(L->next=NULL) return TRUE;else return F

11、ALSE;)(4)遍历单链表void LinkedListTraverse(LuikedList L) LuikedList p;p=L->next;if(p=NULL) pnntf("单链表为空表 1T);elseprintf("链表中的元素为NT);while(p!=NULL)printf(H%d fp->data); p=p->next; jpnntff'n")；(5)求单链表长度mt LuikedListLength (LuikedList L) LuikedList p;intj;p=L->next;J=°；wh

12、ile(p!=NULL) j+;p=p->next; return j;(6)从链表中查找元素LuikedList LuikedListGet(LHikedList Ljnt i) LuikedList p=L->next; j=l;while (p!=NULL && j<i)p=p->next; j+; if (j=i) return p; else return NULL; )(7)从链表中查找与给定元素值相同的元素在顺序表中的位置 mt LnikedListLocate (LuikedList L, mt x) LuikedList p=L->

13、;next; j=l;while (p!=NULL && p->data != x) p=p->next;j+; if(p) return j;else return 0;j(8)向链表中插入元素void LinkedListIiisert(LiiikedList L, mt i, mt x) LuikedList p,s;intj;J=1；P=L；while(p&&j<i)p=p->nextj+; if(p=NULL|j>i) pnntf("插入位置不正确n) else s=(LNode *)nialloc(sizeof

14、(LNode); s->data=x;s->next=p->next; p->next=s;pnntf("d已插入到链表中11"了)； ) )(9)从链表中删除元素void LinkedListDel(LiiikedList L,int i) LinkedList p,q;intj;J=1；P=L；while(p->next&&j <i)p=p->next;j+;if(p->next=NULL)pnntf("删除位置不正确n")；else q=p->next;p->next=q-

15、>next;fiee(q);printf("第d个元素已从链表中删除111);) )(10)建立单链表LinkedList LiiikedListCreat() LinkedList L=LinkedListInit(),p,t; mt x;r=L;pnntf("请依次输入链表中的元素，输入负数时结束1门； scanf(”d”,&x);while (x>=0)p=(LuikedList)malloc(sizeof(LNode);p->data=x;r->next=p; r=p；scanf("%d”.&x);)r->ne

16、xt=NULL;return L;)(11)主函数niainQ mt i,h,d,e,xj,n,q; chai ch;LinkedList L,p;while(q!=0) pnntf("请选择要进行的操作W)pnntf(“L初始化2.清空3.求链表长度4.检查链表是否为空n")；pnntf("5.遍历链表6,从链表中查找元素n")；pnntf(”7 .从链表中查找与给定元素值相同的元素在顺序表中的位置n")；pnntf(”8.向链表中插入元素9.从链表中删除元素W)priiitf(nl 0 .建立单链表 n")； printf(&qu

17、ot;按其它键结束n) scanf(”d”,&x);switch(x)case l:L=LinkudList!nit();printf("链表已经初始化 nn);break;case 2:LinkedListCleai(L);prmtf(niiH);bieak;case 3:printf("链表的长雇为 %dn,LinkedListLength(L);bieak;case 4:i= LinkedListEmpty(L);if pnntf("链表为空 n");else printf("链表非空 n”);break;case 5 :Link

18、edListTraveise(L); break;case 6:pnntf(“请输入待查询元素在链表中的位置:")；scanf(”%d”,&j);p=LnikedListGet(L,j);if(p) pnntff链表中第泡 个元素的值为:dh“j,p->data);else piintf("查询位置不正确n)break;case 7:pnntf("请输入待查询元素的值:)scanf(',%d,&e);h=LinkedListLocate(L,e);时)pnntf("d在链表中的位置是:%MT,e,h);else pnntf(

19、"链表中没有值为(1的元素n”,e);break;case 8:pnntf(“请输入插入元素的位置和值(中间以空格或回车分隔)An”)；scanff'%d%d”,&d,&e);LnikedListIiisert(L,d,e);break;case 9:if(LuikedListLength(L)=O)pnntf("链表已经为空，不能删除n)else pnntf("请输入待删除元素的彳立置:n")；scanf(”d”,&n);LnikedListDel(L,n);break;case 10: L=LHikedListCrea

20、t();prmtf(nnH);break;default:q=O:)六.测试结果1、单链表的操作(1)建立单链表：选择1,然后选择10 ,输入123.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,显示：链表中没有

21、值为25的元素向链表中插入元素选择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.问J描述设有编号1,2,3。n（n>0）的N个人围成一个圈，每个人持有一个密码（正整数）。开始时从第k （1<=k<=n）个人按顺时针方向自1开始顺序报数，报到m （m为第K个人的密码）的人出圈，再以这个人顺时针方向

22、上的下一个人的密码为m,并开始重新从1报数。如此下去，宜至所有人 全部出列为止。试设计一个程序求出出列顺序。例如，设总人数n的初值为8.他们所持的密码分 别为：3,10,7,1,4,8,4,5,开始报数人的编号k的初值为7,则出列顺序为:2,1,3,4,8,57,62.数据结构设计问题中以序号标示某个人，所以结点的数据域设为一个整型类型的变量当某人出圈后，报数的工作要从下一个人开始继续，剩下的人仍然围成一圈，可以使用循环 表。由于出圈的人将不再屈于圈内，意味着数据元素的删除。因此，算法中存有频繁的元素删除 操作，存储结构宜采用链表。每个结点中既存储密码还存储初始位置，所以结点有两个数据域， 一

23、个指针域。另外，每个结点代表一个人所以，可以令尾结点指针指向首元结点来进行循环。/结点类template <class ElemType>struct Node/数据成员：/数据域 指针域ElemType data;ElemType num;Node<ElemType> *next;/构造函数：Node();/无参数的构造函数Node(ElemType item, ElemType iteml ,Node<ElemType> *link = NULL);/已知数数据元素值和指针建立结构;/结点类的实现部分 template<class ElemType

24、> Node<ElemType>:Node()/操作结果：构造指针域为空的结点 (next = NULL;)template<class ElemType>Node<ElemType>:Node(ElemType item, ElemType iteml,Node<ElemType>*link)/操作结果：构造一个数据域为item和iteml,指针域为link的结点data = item;num = iteml;next = link; #endif3.算法设计编写一个函数实现结点的删除与输入工作，另编写一个主函数main ()完成链 表的

25、创建与函数调用工作。(1)插入template <class ElemType>Status LinkList<ElemType>:lnsert(int position, const ElemType &e)/操作结果：在线性表的第position个位置前插入元素e/ position 的取值范围为 1WpositionWLength()+1/ position合法时返回SUCCESS,否则函数返回RANGE_ERROR(if (position < 1 | position > Length() + 1) “position 范围错return

26、RANGE_ERROR; / 位置不合法) else/ position 合法Node<ElemType> *tmpPtr;/取出指向第position-1个结点的指针tmpPtr = GetElemPtr(position - 1);Node<ElemType> *newPtr;if(position>Length()/如果插入尾结点，则域指针指向首元结点newPtr = new Node<ElemType>(e, position,head->next); elsenewPtr= new Node<ElemType>(e, pos

27、ition,tmpPtr->next);/ 生成新结点/将tmpPtr插入到链表中/设置当前位置的序号设置指向当前位置的指针/插入成功后元素个数加1tmpPtr->next = newPtr; curPosition = position; curPtr = newPtr;count+;return SUCCESS;)(2)删除template <class ElemType>Status LinkList<ElemType>:Delete(int position, ElemType &e)操作结果：删除线性表的第position个位置的元素，并用

28、e返回其值,/ position 的取值范围为 1WpositionWLength。,/ position合法时函数返回SUCCESS,否则函数返回RANGE.ERROR/ position 合法Node<ElemType> *tmpPtr;if(position=1)/如果删除首元结点，取出指向尾结点的指针tmpPtr=GetElemPtr(Length();else/取出指向第position-1个结点的指针tmpPtr = GetElemPtr(position - 1);Node<ElemType> *nextPtr = tmpPtr->next;if(p

29、osition=1)头结点与新的首元结点相连head->next=nextPtr->next; / nextPtr 为 tmpPtr 的后继 tmpPtr->next = nextPtr->next;II 删除结点e = nextPtr->data;用e返回被删结点元素值if (position = Length()/设置当前位置的序号 设置指向当前位置的指针 II删除尾结点,当前结点变为头结点curPosition = 1;curPtr = head->next;)else/删除非尾结点，当前结点变为第position个结点curPosition = po

30、sition; curPtr = tmpPtr->next;)count-;delete nextPtr;return SUCCESS;)(3)出圈次序的算法描述template <class ElemType>/设置当前位置的序号II设置指向当前位置的指针II删除成功后元素个数减1II释放被删结点int LinkList<ElemType>:Pass(int position , int n ,ElemType &e)int i;curPtr = GetElemPtr(position);curPosition=position;for(i=0;i<

31、;n-1 ;i+)curPtr = curPtr->next;curPosition+;)coutvvcurPtr->numvv" ”；e=curPosition;当前指针指向position记录当前位置依次报数直到n输出起始位置)(4)主程序#includeHassistance.hH#include"lk_list.h"int POS(int n,int i)计算当前位置的函数jf(n%i=O) n=i;else n=n%i;return n;int main() int tmp,i,k=O,n=O,key;int pos;LinkList<

32、int> Ic;创建空链表while(n<1|n>20)限制人数cout<<”请输入人数，人数小于20:”；cin»n;coutvv”请输入每个人的密码，用空格分隔，密码大于0:“vvendl;for(i=1;i<=n;i+)cin»tmp;插入尾结点lc.lnsert(i,tmp); 1while(k<1|k>n) coutvv”从几号开始？ 0<K<=H«n<<,1:11;cin»k;coutvv"出列顺序:"；for(i=n;i>0;i-)if(i=n

33、)一开始，从k开始报数出列计算出列位置删除当前结点，当前指针指向当前位置的下游取当前位置的密码从当前位置开始报数，并出列计算出列位置lc.GetElem(k,key); lc.Pass(k,key,tmp); pos=POS(tmp,i); lc.Delete(pos,tmp);)elselc.GetElem(key); lc.Pass(key,tmp); pos=POS(tmp,i); lc.Delete(pos,tmp); ) ) system(Hpause"); return 0;)九：心得体会通过做这次实验，发现自己在数据结构这门课程中还有很多不足，有很多知识 还没掌握实验的

34、时候出现了很多错误，有很多知识还不能运用，最后在同学的帮助 下，终于完成了任务。因为以前的C语言没学好，这学期的数据结构感到学的时候有些吃力，在实验 的时候，我所以的不足都体现出来了，如果没有同学的帮助，我程序中的问题可能 需要很长时间才会解决，所以以后还是要努力赶上来。在这次实验中，我也得到了很多收获，比如链表的应用，以前总是弄不明白，通过这次实验，在链表这一方面我懂了很多，但还不能运用自如，需要更多的练习。这次实验，对本学期所学习的内容也是一次巩固，让我加深了对学过知识的记 忆。总之，这次实验让我既发现了自身的很多不足，又增长了很多知识。#include<stdio .h>#i

35、nclude<malloc.h>#defuie TRUE 1#defuie FALSE 0typedef stnict LNodehit data;stnict LNode *next; LNode, *LnikedList;LnikedList LinkedListImt()LinkedList L;L=(LinkedList)malloc(sizeof(LNode);L->next=NULL;return L;void LinkedListCleai(LuikedList L)L->next=NULL;pnntf("链表已经清空n)mt LinkedLis

36、tEnipty(LnikedList L) if(L->next=NULL) return TRUE;else return FALSE;void LinkedListTraverse(LHikedList L)LinkedList p;p=L->next;if(p=NULL) pnntf("单链表为空表 n”)；elsepnntf("链表中的元素为:n");wliile(p!=NULL)priiitf(M%d fp->data); p=p->next;mt LinkedListLength (LinkedList L) LinkedLis

37、t p;intj;p=L->next;J=0；while(p!=NULL)j+；p=p->next; return j;LnikedList LuikedListGet(LnikedList L,int i)LinkedList j;p=L->next; j=l;while (p!=NULL && j<i)p=p->next; j+; if (j=i) return p; else return NULL;mt LinkedListLocate (LinkedList L. int x) LinkedList p=L->next; j=l;w

38、hile ( p!=NULL && p->data != x) p=p->next;j+; if(p) retuinj;else return 0;void LinkedListIiiseit(LHikedList L, mt i. int x) LinkedList p,s;intj;j=l；P=L；while(p&&j<i)p=p->next;j+;if(p=NULL|j>i)pnntf("插入位置不正确11");else s=(LNode *)malloc(sizeof(LNode);s->data=

39、x;s->next=p->next;p->next=s;pnntf("%d已插入到链表中11"不)；void LinkedListDel(LHikedList Ljnt i) LuikedList p,q;intj;j=l；P=L；wlule(p->next&&j<i)p=p->next;j+; if(p->next=NULL) pnntf("删除位置不正确n")； else q=p->next;p->next=q->next;fiee(q);printf("第d个元素已从链表中删除)LuikedList LuikedListCreat() LuikedList L=LuikedListIiiit(),p,i;mt x;r=L;pnn氓”请依次输入链表中的元素，输入负数时结束 scanfC%d&