第一篇：2012《数据结构》上机实验报告 链表
西华大学数计学院学生上机实践报告
西华数学与计算机学院上机实践报告
课程名称：数据结构 指导教师：唐剑梅 上机实践名称：
上机实践编号：1 年级： 2011 姓名：蒋俊 学
号
：
***
上机实践成绩：
上机实践日期：2012-11-6
上机实践时间：8:00-9:30
一、实验目的
1.了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。
2.重点是线性表的基本操作在两种存储结构上的实现；其中以链表的操作为侧重点；并进一步学习程序设计方法。
3.掌握栈这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。
4.掌握队列这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。
5.了解和掌握递归程序设计的基本原理和方法。
6.掌握使用 C++面向对象的程序设计技术设计数据结构源程序的方法。
二、实验内容
1.熟悉前面的【程序示例2】，按照约瑟夫问题的方法2，试着不设头结点改写原来的程序，上机调试运行。
2.用链表建立通讯录。通讯录内容有：姓名、通讯地址、电话号码。
要求：（1）通讯录按姓名项的字母顺序排列；
（2）能查找通讯录中某人的信息；
[提示] 用链表来存放这个通讯录，一个人的信息作为一个结点。成链的过程可以这样考虑：先把头结点后面的
西华大学数计学院学生上机实践报告
char name[20];
// 姓名子域
NodeType *next;
// 指针域
};class Jose
//类声明
{ private: NodeType *Head;
public:
Jose(){};
~Jose(){ };
void creat();
void outs();
};void Jose::creat(){ int i=0, n;
NodeType *newp, *pre;
cout<<“n
输入总人数 n=”;cin>>n;
pre=new NodeType;
Head=new NodeType;
pre->num=1;
cout<<“n 编号”<<1<<“的人
姓名=”;
cin>>pre->name;
cout<<“n 密码”<<1<<“的人
密码=”;
cin>>pre->psw;
Head=pre;
Head->next=Head;
for(i=1;i { newp=new NodeType; newp->num=i+1; cout<<“n 编号”< 姓名=”;cin>>newp->name; cout<<“n 密码”< 密码=”; cin>>newp->psw; newp->next=Head; pre->next=newp; pre=newp; } } void Jose::outs() { int m,i; NodeType *q=Head, *p; cout<<“n 输入m值(m>=2)”;cin>>m; cout<<“n 根据m值，开始报数输出：”< while(q->next!=q) 西华大学数计学院学生上机实践报告 { for(i=1;i cout<<“编号为：”< cout<<“n 编号为:”< m=q->psw; p->next=q->next;delete q; q=p->next; } cout<<“编号为：”< cout<<“n 编号为:”< delete q;} int main() { Jose h; h.creat(); h.outs(); return 0;} 西华大学数计学院学生上机实践报告 { char Add[20]; char name[20]; char tel[20]; };struct NodeType { ElemType data; NodeType *next;};class Sqlist { private: NodeType *Head; public: Sqlist(); ~Sqlist(); void creat(); void Insert(ElemType x); void Delet(ElemType x); void PrintOut(); };Sqlist::Sqlist(){ Head=new NodeType;Head->next=NULL;strcpy(Head->data.name,“姓名”);strcpy(Head->data.Add,“地址”);strcpy(Head->data.tel,“电话号码”);} Sqlist::~Sqlist(){ NodeType *p=Head->next; while(p!=NULL) {Head->next=p->next; delete p; p=Head->next;} } void Sqlist::creat() //初步建立一个通讯录 { NodeType*p,*s,*q;ElemType x; 西华大学数计学院学生上机实践报告 int a;q=Head;cout<<“n 输入姓名：”;cin>>x.name;cout<<“n 输入通讯地址：”;cin>>x.Add;cout<<“n 输入电话号码：”;cin>>x.tel;p=new NodeType;p->data=x;Head->next=p;p->next=NULL;cout<<“输入一个数。若为-1，结束输入:”< while(a!=-1){ cout<<“n 输入姓名：”;cin>>x.name;cout<<“n 输入通讯地址：”;cin>>x.Add;cout<<“n 输入电话号码：=”;cin>>x.tel;s=new NodeType;s->data=x;if(strcmp(s->data.name,p->data.name)>0){ p->next=s;s->next=NULL; p=s;} else{ s->next=p;q->next=s;} q=q->next; cout<<“输入一个数。若为-1，结束输入:”< 西华大学数计学院学生上机实践报告 s->data=x;q=Head;p=q->next;while(p!=NULL&&strcmp(p->data.name,x.name)<0){q=p;p=p->next;} s->next=p;q->next=s;} void Sqlist::Delet(ElemType x)//删除 { NodeType *p,*q;q=Head;p=Head->next;while(p!=NULL&&strcmp(p->data.name,x.name)!=0){q=p;p=p->next;} if(p!=NULL){ q->next=p->next;delete p;cout<<“删除结点成功”< { NodeType *p;p=Head->next;while(p!=NULL){ cout< data.name<<“ ”;cout< data.tel<<“ ”;cout< data.Add<<“ ”;p=p->next;} cout< Sqlist as; cout<<“n 通讯录演示”; do{ cout<<“nn”; cout<<“nn 1.初步建立一个通讯录（单链表） ”; 西华大学数计学院学生上机实践报告 cout<<“nn 2.插入新的电话记录 ”; cout<<“nn 3.删除一个电话记录”; cout<<“nn 4.结束程序”; cout<<“n******************************** ”; cout<<“n 请输入你的选择(1,2,3,4)”;cin>>k;switch(k){ case 1:{ as.creat();as.PrintOut();}break; case 2:{ cout<<“n 插入的数据 姓名”;cin>>e.name; cout<<“n 插入的数据 电话号”;cin>>e.tel; cout<<“n 插入的数据 地址”;cin>>e.Add; as.Insert(e);as.PrintOut(); }break; case 3:{ cout<<“n 被删除的姓名= ”; cin>>e.name; as.Delet(e); as.PrintOut(); }break; default:break; } }while(k>=1&&k<4); cout<<“n 再见!”; return 0;} 西华大学数计学院学生上机实践报告 西华大学数计学院学生上机实践报告 西华大学数计学院学生上机实践报告 const int MAXSIZE=100; // 数组的容量 class SqStack { private: ElemType elem[MAXSIZE]; int top; public: SqStack(); ~SqStack(){}; void SqStack::push(ElemType e); ElemType SqStack::pop(); void SqStack::PrintOut(); int SqStack::IsEmpty(); void f(ElemType N,ElemType M);};void SqStack::f(ElemType N,ElemType M){ SqStack s; ElemType e;while(N){ s.push(N%M); N=N/M;} while(!s.IsEmpty()){ e=s.pop(); if(e>=10) { e=e%10; switch(e) { case 1:cout<<“b”< case 2:cout<<“c”< case 3:cout<<“d”< case 4:cout<<“e”< case 5:cout<<“f”< default:cout<<“a”< } } else cout< 西华大学数计学院学生上机实践报告 } cout< {cout<<“栈满溢出”< return; } else{top++; elem[top]=e;} } ElemType SqStack::pop(){ElemType x; if(top==0) { cout<< “ 栈为空，不能出栈操作”< else { x=elem[top]; top--; return x;} } void SqStack::PrintOut() {int k; cout<<“n PrintOut Data:n”; for(k=top;k>=1;k--)cout< cout< else return 0;} void main(){ ElemType a,m;cout<<“请输入一个正整数:”< 西华大学数计学院学生上机实践报告 五、总结 通过本次实验，我熟悉了链表的操作，了解了线性表在现实生活中的运用，认识了顺序存储和链式存储这两种结构。本次上机实践基本完成了实验内容，但完成的不是很好，以后需要更加努力地掌握基本的知识。实验内容对于队列的运用没有涉及，希望以后有所涉及。 西华大学数计学院学生上机实践报告 数据结构实验报告 课程 数据结构 _ 院 系 专业班级 实验地点 姓 名 学 号 实验时间 指导老师 数据结构上机实验报告1 一﹑实验名称： 实验一——链表 二﹑实验目的： 1.了解线性表的逻辑结构特性； 2.熟悉链表的基本运算在顺序存储结构上的实现，熟练掌握链式存储结构的描述方法； 3.掌握链表的基本操作（建表、插入、删除等）4.掌握循环链表的概念，加深对链表的本质的理解。5.掌握运用上机调试链表的基本方法 三﹑实验内容： （1）（2）（3）（4）创建一个链表 在链表中插入元素 在链表中删除一个元素 销毁链表 四﹑实验步骤与程序 #include LinkList p,q;L=(LinkList)malloc(sizeof(Lnode));L->next=NULL;q=L; cout<<“请输入一个链表：”< for(int i=0;i { p=(LinkList)malloc(sizeof(Lnode)); cin>>p->data; p->next=q->next; q->next=p; q=p; } } int PrintLinkList(LinkList &L){//输出链表L的数据元素 LinkList p; } void LinkListLengh(LinkList &L){//计算链表L的数据元素个数。int i=0;p=L->next;if(L->next==NULL){ } cout<<“链表的数据元素为:”;while(p) { cout< data<<“ ”; p=p->next;} cout<<“链表没有元素!”< } LinkList p;p=L->next;while(p){ i++; p=p->next; } cout<<“链表的数据元素个数为:”< LinkList p,s;int j=0;p=L; while(p&&j } if(!p||j>i-1){ p=p->next;++j; } } cout<<“插入元素的位置不合理!”;return 0;s=(LinkList)malloc(sizeof(LNode));s->data=x;s->next=p->next;p->next=s;return 1;int DeleteLinkList(LinkList &L,int i){//删除链表L的第I个数据元素。 LinkList p,q;int j=0;p=L;while(p->next&&j } if(!(p->next)||j>i-1){ p=p->next;++j; } } cout<<“删除元素的位置不合理!”;return 0;q=p->next;p->next=q->next;i=q->data;free(q);return 1;void DestroyLinkList(LinkList &L){//销毁链表L。 LinkList p,q;p=L->next;while(L->next!=NULL){ q=p->next;L->next=q; free(p);} p=q; free(L); cout<<“链表已经被销毁!”< LinkList L; int i,j,x;cout<<“第一次数据结构上机实验—链表”< CreatLinkList(L,j); LinkListLengh(L); PrintLinkList(L); cout<<“在第几个元素前插入:”;cin>>i;cout<<“输入插入的元素:”;cin>>x; InsertLinkList(L,i,x); LinkListLengh(L); PrintLinkList(L); cout<<“输入删除元素的位置:”;cin>>i; DeleteLinkList(L,i); LinkListLengh(L); PrintLinkList(L); cout<<“销毁程序后为:”< DestroyLinkList(L);} 五﹑实验结果 六﹑实验心得体会： 链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据，二为下一个结点的地址。 实验的程序设计规划（实现的功能、分几个模块、子函数）（1）编写链表创建子函数void CreatLinkList(L,j)（2）编写链表插入子函数 int InsertLinkList(LinkList &L, int i, int x)（3）链表的打印int PrintLinkList(LinkList &L)（4）编写链表删除子函数 int DeleteLinkList(LinkList &L,int i)（5）编写链表销毁子函数void DestroyLinkList(LinkList &L)（6）编写主函数Main()，通过功能菜单调用子函数（7）编译调试程序 经过多次的调试，修改，实验结果终于正确了，在这个过程中，经历了不知道怎么进行声明区的编写如包含文件，宏定义，函数声明，全局变量声明，结构体等的定义等的结合，到学会了使用先把程序主要规划为四个部分来写就简单多了，第一，定义；第二，写所要调用的子函数；第三，写主函数，调用子函数；第四就是程序的编译与调试，修改。数据结构实验需要我们对每个程序的算法有深刻的理解，才能应用到实际中去，因此我们需要在做实验之前要熟悉实验的内容，且先把所要实验的程序写出来，在实验中就可以查找错误并加以改正，这是一个成长的过程。 数据结构上机实验报告一﹑实验名称： 实验二—队列 二﹑实验目的： 1.掌握队列这种抽象数据类型的特点, 掌握栈与队列在实际问题中的应用和基本编程技巧,并能在相应的问题中选用它;2.熟练掌握循环队列和链队列的基本操作实现算法，特别是队满和队空的描述方法； 3．掌握栈与队列的数据类型描述及特点； 4.掌握栈的顺序和链式存储存表示与基本算法的实现； 5.掌握队列的链式存储表示与基本操作算法实现;6.按照实验题目要求，独立完成实际程序的编写编写、调试和运行，并通过用例数据的运行过程抓获相关屏面验证程序设计的正确性； 7.认真书写实验报告，并按时提交。 三﹑实验内容： 对顺序循环队列，常规的设计方法是使用対尾指针和对头指针，对尾指针用于指示当前的対尾位置下标，对头指针用于指示当前的対头位置下标。现要求： （1）掌握栈和队列的特点，即后进先出和先进先出的原则。（2）设计一个使用对头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化，入队列，出队列，取对头元素和判断队列是否为空； （3）编写主函数进行测试。 四﹑实验步骤与程序 #include #define OK 1 #define ERROR 0 #define OVERFLOW 0 typedef struct QNode { int data;struct QNode *next;}QNode,*QueuePtr;typedef struct { QueuePtr front;QueuePtr rear;}LinkQueue;int InitQueue(LinkQueue &Q){ } Q.rear=Q.front=(QueuePtr)malloc(sizeof(QNode));if(!Q.rear)exit(OVERFLOW);Q.front->next=NULL;return OK;void QueueEmpty(LinkQueue Q){ } void EnQueue(LinkQueue &Q,int e){ } int EnnQueue(LinkQueue &Q,int e){ QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));if(!p)printf(“error”);if(Q.front==Q.rear)printf(“该链队为空:”);else printf(“该链队不为空:”);p->data=e;Q.rear->next=p;Q.rear=p;printf(“元素%d入队成功”,e); } if(!p)return ERROR;p->data=e;Q.rear->next=p;Q.rear=p; return OK;void DeQueue(LinkQueue &Q){ } void GetHead(LinkQueue &Q){ QueuePtr p;QueuePtr p;if(Q.front==Q.rear)printf(“该链队为空”);p=Q.front->next;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);printf(“队首元素删除成功”); } if(Q.front==Q.rear)printf(“该链队为空”);p=Q.front->next;printf(“队首元素为:%d”,p->data);void OutQueue(LinkQueue &Q){ } void LengthQueue(LinkQueue &Q){ int f=0;QueuePtr p;if(Q.front==Q.rear)QueuePtr p;if(Q.front==Q.rear)printf(“该链队为空”);p=Q.front->next;while(p!=Q.rear->next){ } printf(“%d%,”,p->data);p=p->next; } printf(“该队列的长度为:%d”,f);else { } p=Q.front->next;while(p!=Q.rear->next){ } printf(“该队列的长度为:%d”,f);p=p->next;f++;void main(){ system(“cls”);int flag=1,i;LinkQueue Q;InitQueue(Q);printf(“************************链队列功能菜单***********************n”);printf(“1:初始化链队列，2:判断链队列是否为空, 3:进入队列，4:取出队首元素n”);printf(“5:输出该队列的所有元素,6:输出该队列的长度，7:结束程序，8:清屏n”); while(flag){ printf(“n请输入操作符:”);scanf(“%d”,&i);switch(i){ case 1: int e,n,k;printf(“请输入队列的长度:”);scanf(“%d”,&n);printf(“请输入队列的元素:”);for(e=1;e<=n;e++){ } printf(“初始化链队成功”);break;scanf(“%d”,&k);EnnQueue(Q,k);case 2: QueueEmpty(Q); break;case 3: int j;printf(“请输入要进入队列的元素”);scanf(“%d”,&j);EnQueue(Q,j);break;case 4: GetHead(Q);break;case 5: printf(“该队列的元素为:”);OutQueue(Q);break; case 6: LengthQueue(Q);break;case 7: flag=0;break;case 8: system(“cls”);} break; } } 五﹑实验结果 六﹑实验心得体会： 程序主要构造了主函数main（）和 InitQueue（），QueueEmpty（）EnQueue()，OutQueue()等调用函数，实现了队列的创立，队列是否为空的判断，入队和出队等功能。 通过此次实验，加深了对队列的存储结构的了解，同时也对程序设计能力有了提高，加深了对队列先进先出性质的理解，它允许在表的一端进行插入，在另一端删除元素，这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。我们往往写不出程序，这其中的原因我觉得是对程序的结构不是很了解，对实验的内容也不熟练的结果，数据结构给我们许多程序的算法和模型，对我们写程序的思维有很大的锻炼，我们应珍惜每次上机实验的机会去实践课堂上所学的东西并从中发现问题，从而达到提升写程序的能力。 数据结构上机实验报告一﹑实验名称： 实验三—二叉树的遍历 二﹑实验目的： 1、熟悉二叉树的结构特性，了解相应的证明方法； 2、掌握二叉树的生成，掌握二叉树的定义和存储表示，学会建立一棵特定二叉树的方法； 3、理解二叉树的三种遍历方法：先序遍历、中序遍历和后序遍历； 4、学会编写实现树的各种操作的算法。 二、实验内容： 1、使用类定义实现二叉树，补充完整所缺的函数，并实现创建和遍历二叉树的基本操作； 2、编程实现在二叉链表这种存储方式下，实现二叉的遍历，可采用递归或者非递归实现，遍历算法为在先序、中序和后序遍历算法。 三、实验步骤与程序： #include void PreOrder(BiTree T)//先序 { if(T!=NULL){ printf(“%c”,T->data);PreOrder(T->lchild);PreOrder(T->rchild);} } void InOrder(BiTree T)//中序 { if(T!=NULL){ InOrder(T->lchild);printf(“%c”,T->data);InOrder(T->rchild);} } void PostOrder(BiTree T)//后序 { if(T!=NULL){ PostOrder(T->lchild);PostOrder(T->rchild);printf(“%c”,T->data);} } void main()//主函数 { printf(“------------二叉树的遍历-------------n”);printf(“请输入要遍历的数：”);BiTree Ta;Ta=CreateBiTree();printf(“先序遍历:”);printf(“n”);PreOrder(Ta);printf(“n”);printf(“中序遍历:”);printf(“n”);InOrder(Ta);printf(“n”);printf(“后序遍历:”);printf(“n”);PostOrder(Ta);} 五﹑实验结果 六﹑实验心得体会： 实验的程序设计规划（实现的功能、分几个模块、子函数）（1）先序遍历递归算法函数：void PreOrder(BiTree T)（2）中序遍历递归算法函数：void InOrder(BiTree T)（3）后续遍历递归算法函数：void PostOrder(BiTree T)（4）主函数的实现：void main() 在实验前我认真阅读关于二叉树的实现的内容，为编程实现第一步，本次实验通过按上述的实验步骤一步步实现的，实验过程中出现了一些错误，经过一步步的调试，修改错误，得到了二叉树的遍历用递归运算的方法的程序。通过这个实验，我体会到了理解数据结构的重要性，这有真正理解了定义数据类型的好处，才能用好这样一种数据结构。二叉树的先序，中序与后序的输出都用了递归的算法，而且用起来不是很复杂，这使我更进一步理解了函数递归调用并得到灵活运用；在实现算法上，从算法的效率看，递归方法书写形式较为简洁，更为直观，一般具有较好的空间效率。 总之，不管做什么实验，我们在做实验前都要先预习，对所做的实验有较深的理解，在做实验的时候需要很严谨，仔细的查找错误，从而能在实验中收获知识，提升自己。 数据结构上机实验报告4 一﹑实验名称： 实验四—查找 二﹑实验目的： 1、熟悉掌握顺序表的查找方法； 2、熟练掌握二叉排序树的构造方法和查找算法 3、掌握描述查找过程的判定树的构造方法，以及按照定义计算各种查找方法在等概率情况下查找成功时的平均查找长度； 4、学会定义线性表的储存类型，实现C++程序的基本结构对线性表的一些基本操作和具体的函数定义； 5、掌握顺序表的基本操作，实现顺序表的查找的等基本运算； 6、掌握对于多函数程序的输入，编辑，调试和运算过程。 二、实验内容： 1、实现顺序表的查找算法 2、关于衡量查找的主要操作—查找的查找平均效率的平均长度的讨论。 三、实验步骤与程序： #include element list[MAX_SIZE]; int seqsearch(element list[],int searchnum,int num);int main(){ int i,num,searchnum,k; printf(“---------------数据结构查找实验-------------n”);printf(“请输入数据元素的个数：”);scanf(“%d”,&num);printf(“请输入数据的元素：n”);for(i=0;i printf(“请输入要查询的数据元素:”);scanf(“%d”,&searchnum);k=seqsearch(list,searchnum,num);if(k!=-1){ printf(“所查询元素的下标为：”);printf(“%dn”,k);} else printf(“查询元素不存在。n”);} return 0;} int seqsearch(element list[],int searchnum,int num){ int j; list[num].key=searchnum; for(j=0;list[j].key!=searchnum;j++);return j 六﹑实验心得体会： 实验的程序设计规划为先写一个主函数int main()，再写一个查找的子函数int seqsearch(element list[],int searchnum,int num)，主函数通过调用子函数的方法实现程序的设计。 所谓“查找”即为在一个众多的数据元素（或记录）的查找表中找出某个“特定的”数据元素（或记录），通过本次实验，我更进一步的了解数据结构程序实验设计实现算法的基本模型，和算法实现等基本内容，学会了顺序表的查找方法。 数据结构上机实验报告5 一﹑实验名称： 实验五—内部排序 二﹑实验目的： 1、通过实现下述实验内容，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况，并加以灵活应用。 2、掌握各种排序时间复杂度的分析方法。 二、实验内容： 1、插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。 2、快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成。 3、讨论各种内部排序方法的基本思路，算法特点，排序过程及它们的时间复杂度的分析。 三、实验步骤与程序： #include } int x;void charu();void kuaisu();printf(“----------内部排序---------n”);printf(“ 1、插入排序：n”);printf(“ 2、选择排序：n”);printf(“请根据序号选择：”);scanf(“%d”,&x);if(x==1)charu();else kuaisu();void charu(){ int a[7],j,i,m; printf(“插入排序n”); printf(“请输入个您想排序的数据:n”); for(i=0;i<7;i++)scanf(“%d”,&a[i]); for(j=1;j<7;j++) { m=a[j]; for(i=j-1;i>=0;i--) { if(a[i] break; else a[i+1]=a[i]; } a[i+1]=m; } printf(“排序成功:”); for(i=0;i<7;i++) printf(“ %d”,a[i]); printf(“n”);} quick(int first,int end,int L[]){ int left=first,right=end,key; key=L[first]; while(left { while((left right--; if(left L[left++]=L[right]; while((left left++; if(left L[left]=key; return left; } quick_sort(int L[],int first,int end) { int split; if(end>first) { split=quick(first,end,L); quick_sort(L,first,split-1); quick_sort(L,split+1,end); } } void kuaisu(){ int a[7],i; printf(“快速排序n”); printf(“请输入个您想排序的数据:n”); for(i=0;i<7;i++) scanf(“%d”,&a[i]); quick_sort(a,0,9); printf(“排序成功:”); for(i=0;i<7;i++) printf(“ %d”,a[i]); printf(“n”);} 五﹑实验结果： 六﹑实验心得体会： 排序的功能是将一个数据元素（或记录）的任意序列，从新排成按关键字有序的序列；直接插入排序的稳定性比快速排序高，且算法较简单。本次实验运用到的是插入排序和快速排序。 实习报告 题 目 : 实现一个约瑟夫环程序 班级：031021姓名：王帅学号：03102076 一、需求分析 1． 本演示程序中，利用单向循环链表存储结构存储约瑟夫环数据（即n个人的编号和密码）。 2． 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中需要输入的数据，运算结果显示在其后。 3． 程序执行的命令包括： 1)构造单向循环链表；2）进行数值的输入，并作判断分析；3）约瑟夫算法的实现与结果输出；4）结束。 4． 测试数据 m 的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，（正确的出列顺序为6，1，4，7，2，1，3，5）。 二、概要设计 1．单向循环链表的抽象数据类型定义为： ADT List｛ 数据对象：D=｛ai | ai↔正整数，I=1，2，......，n,n≥0｝数据关系：R1=｛< ai-1，ai > |，ai-1，ai↔D,I=1，2，......，n｝基本操作： Init List(&L) 操作结果：构造一个空的线性表L。 List Insert(&L,i,e) 初始条件：线性表L已存在，1≤i≤List Length(L)+1.操作结果：在L中第i个位置之前插入新的数据元素e，L长度加1。List Delete(&L,i,&e) 初始条件：线性表L存在非空，1≤i≤List Length(L).操作结果：删除L的第i个元素，并用e返回其值，L长度减1。 2． 程序包含四个模块： 1）主程序模块： void main() { 初始化； for（;;） {} while（命令=开始） { 接受命令； 处理命令； } for（;;） { } } 2）有序表单元模块——实现有序表的抽象数据类型； 3）节点结构单元模块——定义有序表的节点结构； 4）数据输入分析模块——判断输入数据正确有效； 各模块之间的调用关系如下： 主程序模块 ↓ 有序表结构模块 ↓ 节点结构单元模块 ↓ 数据输入分析模块 三、详细设计 1、结点类型，指针类型 TypedefstructLNode{ int code,date;//code 为人所在位置 date为人持有的密码 struct LNode *next; };// 结点类型，指针类型 2、构造单向循环链表 struct LNode *p,*head,*q;//定义头节点，和指针 for(i=2;i<=n;i++) { struct LNode *s=(struct LNode *)malloc(sizeof(struct LNode));//分配 新结点空间 s->code=i; input(s->date); p->next=s; p=p->next; } p->next=head;//根据输入的人数，进行单项循环链表的创建，p指向最后一个结点，并与头节点链接，形成单项循环链表 3、约瑟夫环的程序实现部分 while(n!=1)//判断输入人数，如为1则直接输出结果，不循环 { for(i=1，m=m%n;i { p=p->next; } q=p->next;//找到要删除节点 p->next=q->next;//找到要删除节点的后继，并连接新环m=q->date;//找到下一个密码 printf(“%d”,q->code); free(q);//释放已删除节点空间 n--;//链表长度减一 } printf(“%d”,p->code);//约瑟夫环的结果输出 4、其他函数代码 数值的输入限制 int input() { int y,k,z=0; char c;//元素类型 char a[4];//数组初始化 if(!z)//输入判断，确定位数字或控制字符且位置和密码不为零 { for(y=0;y<4;y++) { c=getch(); if(c>=48&&c<=57)//确定为输入数字 {a[y]=c; putch(c); } else { y--; if(c=='r')//确定输入为控制字符 即回车或者删除 break; else if(c==8) {a[y]='n'; y--;} continue; } } k=atoi(a);//确定最终输入数字的值 printf(“n”); z=k; if(z==0) printf(“ERROR!The number couldn't be 0!n”);// 输入为零，重新输入 } return(k);//数值的返回 5、函数的调用关系图反映程序层次结构 Main→input 四、调试分析 1、早期程序只写了约瑟夫环的实现部分，没有对输入数据进行筛选，调试的时候会经常出错。比如是输入字母，或者输入0，大于32767溢出； 2、早期的循环过程中没有进行优化，导致循环次数过多，浪费时间； 3、为了输出时美观，分别在input和main函数主体内做了两次，输入非零的判断，浪费了资源； 4、算法的时空分析 为了限制在输入过程中不会上溢，只在输入中限定为四个不全为零的数字，但是做的是do……while循环，复杂度为o（1）; 当n大于1时： 在数据输入中，链表的创建是for循环，时间复杂度为o（n-1） 在约瑟夫环实现程序中，为for循环。时间复杂度为o（m%n-1） 当n=1时，复杂度为o（1）。 五、用户手册 用户根据提示，先输入起始密码m，然后输入人数n，再根据人数，分别输入每个人的密码date，数值均不能为0，否则会提示重新输入，输入为字母则自动丢弃，输入错误可用删除键进行修改，输入完成后按回车键确定本次输入完毕（若输入数字大于9999，则第五位自动转换为下一个数字的起始位，依此类推）。 当n个数字全部输入完毕，则自动显示结果，按任意键则退出本程序。 六、测试结果 第一组：m 的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，出列顺序为6，1，4，7，2，1，3，5。 第二组： m 的初值为30；n=8，7个人的密码依次为：5，1，6，9，4，7，2，3，出列顺序为6，5，2，3，7，1，4，8。 第三组 : m 的初值为15；n=6，7个人的密码依次为：5，3，4，7，6，9，出列顺序为3，1，2，6，4，5。 七、附录 源程序头文件名清单： #include “malloc.h”//内存空间分配头文件 #include “stdio.h”//输入输出函数头文件 #include “stdlib.h”//input函数中字符串转短整形函数的头文件 #include “conio.h”//最后显示结果、清屏函数头文件 北京邮电大学 数据结构试验报告 实验名称： 实验一 线性表 学生姓名： 班 级： 班内序号： 学 号： 日 期： 2014年1月3日 实验目的 熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 实验内容 2.1题目1 根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。 线性表存储结构（五选一）： 1、带头结点的单链表 2、不带头结点的单链表 3、循环链表 4、双链表 5、静态链表 线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。程序分析 3.1 存储结构 单链表的存储结构： 3.2 关键算法分析 一、关键算法 1.头插法 自然语言描述：a.在堆中建立新结点 b.将a[i]写入到新结点的数据域 c.修改新结点的指针域 d.修改头结点的指针域,将新结点加入链表中 代码描述： template front = new Node } } s->next = front->next;front->next = s;时间复杂度：O(n) 2.尾插法 自然语言描述：a.在堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 代码描述: template front = new Node } } s->data = a[i];s->next = r->next;r->next= s;r=s;时间复杂度：O(n) 3.析构函数 自然语言描述：a.新建立一个指针，指向头结点 b.移动a中建立的指针 c.逐个释放指针 代码描述: template Node } } delete front;4.按位查找函数 自然语言描述: a.初始化工作指针p和计数器j，p指向第一个结点，j=1 b.循环以下操作，直到p为空或者j等于1 b1：p指向下一个结点 b2：j加1 c.若p为空，说明第i个元素不存在，抛出异常 d.否则，说明p指向的元素就是所查找的元素，返回元素地址 代码描述: template Node if(j } else break;p = p->next;j++; } if(!p)throw“查找位置非法”;else return p;} 时间复杂度：O(n) 5.按值查找函数 自然语言描述：a.初始化工作指针p和计数器j，p指向第一个结点，j=1 b.循环以下操作，找到这个元素或者p指向最后一个结点 b1.判断p指向的结点是不是要查找的值，如果是，返回j; b2.否则p指向下一个结点,并且j的值加一 c.如果找到最后一个结点还没有找到要查找的元素，返回查找失败信息 代码描述: template Node } return-1;if(p->data == x)return j;else { p = p->next; j++;} } 时间复杂度：O(n)6.插入函数 自然语言描述： a.在堆中建立新结点 b.将要插入的结点的数据写入到新结点的数据域 c.修改新结点的指针域 d.修改前一个指针的指针域，使其指向新插入的结点的位置 代码描述: template Node } else throw“插入位置非法”;Node 自然语言描述：a.从第一个结点开始，查找要删除的位数i前一个位置i-1的结点 b.设q指向第i个元素 c.将q元素从链表中删除 d.保存q元素的数据 e.释放q元素 代码描述: template T x=q->data; } p->next = q->next;delete q;return x; 8.遍历打印函数 自然语言描述: a.判断该链表是否为空链表，如果是，报错 b.如果不是空链表，新建立一个temp指针 c.将temp指针指向头结点 d.打印temp指针的data域 e.逐个往后移动temp指针，直到temp指针的指向的指针的next域为空 代码描述: template } Node } cout< 自然语言描述： a.判断该链表是否为空链表，如果是，输出长度0 b.如果不是空链表，新建立一个temp指针，初始化整形数n为0 c.将temp指针指向头结点 d.判断temp指针指向的结点的next域是否为空，如果不是，n加一，否则return n e.使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next域为0，返回n 代码描述: template } Node } return i-1;p = p->next;i++;4 程序运行结果 4.1主函数流程图 4.2程序运行框图 实验心得 1.调试时出现的问题及解决的方法 在编写按值查找函数时，由于没有处理好指针类型的原因，导致指针无法正常返回，屡屡报错。最后意识到c++没有指针强制类型的转换机制，经过细致检查后才改正错误使得程序正常运行。2.心得体会 了解了单链表的基本的操作函数实现，对链式存储结构有了较好的认识 3.下一步的改进 可以增加完善报错机制，增强程序的健壮性 完整源代码 #include template }; template }; //template Node template } template } template } front = p;p = p->next;delete front;front = new Node } Node } Node } Node } cout< template } template } Node } return-1;if(p->data == x)return j;else { } p = p->next; j++;Node } if(!p)throw“查找位置非法”;else return p;if(j } else break;p = p->next;j++; template } template } template } void main(){ Node } return i-1;p = p->next;i++;Node } else throw“插入位置非法”;Node T x=q->data; } int n;cout<<“将要输入的链表长度为：”;cin>>n;int *b=new int[n];cout<<“输入链表中的元素：”;for(int k=0;k “计算机软件技术基础”课程实验报告 （六）实验名称：数据库及SQL语言 班级_______ 姓名__________ 学号______实验日期： 实验机时：3 学时实验成绩： ----------------- 一.实验目的： 1、学习数据库设计的一般过程及相关技术； 2、学习access数据库管理系统； 3、掌握数据库的输入、查询、更新操作。 二.实验内容： 1、需求陈述：某校图书馆要建立一个图书数据管理系统。该图书馆的图书（书名、分类号、作者、出版社）存放在不同的借阅室（室名），读者（姓名、系名、类别）在书架上找到所需图书后，可以到服务台办理借阅（借阅时间）。 设计要求： 分析需求，建立数据库的概念模型； 将概念模型转换为关系模型（注意：是否需要作规范化处理）； 写出创建基本表的SQL语句； 写出以下查询要求的SQL语句： （1）所有“高等数学习题集”书的信息； （2）读者“李林”借了什么书？ （3）“社会学原理”在哪个借阅室？ 2、在access数据库管理系统中建立所设计的关系表； 3、向各表中输入一组实验数据（元组）（注意：关系完整性）； 4、对数据库进行查询。 三.实验结果： 1、实体-关系图； 2、数据库表； 3、创建基本表的语句； 4、查询语句。第二篇：数据结构上机实验报告
第三篇：数据结构上机实验报告
第四篇：北邮数据结构实验报告 单链表
第五篇：《数据结构》上机作业——实验报告(六)
![下载2012《数据结构》上机实验报告 链表[★]word格式文档](http://static.xiexiebang.com/skin/default/images/icon_word.png){kind=icon}
点击咨询 