数据结构实验一.doc

精品资料

数据结构实验报告

实验一

班级:06111504
学号:1120151570
姓名:刘庭欣

1.实验题目：
采用单向环表实现约瑟夫环。
请按以下要求编程实现：
① 从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。环表中的结点编号依次为1，2，……，m。
② 从键盘输入整数s（1<=s<=m）和n，从环表的第s个结点开始计数为1，当计数到第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出了这个环表的全部结点为止。
例如，m=10，s=3，n=4。则输出序列为：6，10，4，9，5，2，1，3，8，7。
2.源代码:
#include<stdio.h>
#include<malloc.h>
typedef struct list
{ int num;
struct list * next;
}list,* plist;
plist h,p,q;
void Create(int n)
{
h=(plist)malloc(sizeof(list));

h->next=NULL; h->num=0;
while(--n)
{
p=(plist)malloc(sizeof(list));

p->num=n;
p->next=h->next;
h->next=p;
}
while (p->next)
p=p->next;
p->next=h->next; }
void Find(int m,int s)
{
p=h;
while(p->num!=s)
p=p->next;
}
void OutNum(int n)
{
while(p->next!=p)
{
for(int i=1;i<n-1;i++)
p=p->next;
q=p->next;
printf("%-4d",p->next->num);
p->next=q->next;
p=p->next;
free(q); }
printf("%-4d\n",p->num); }

int main()
{
int m,s,n;
scanf("%d%d%d",&m,&s,&n);
Create(m+1);
Find(m,s);
OutNum(n);
}

3. 运行结果截屏:

4. 编写与调试过程中遇到的问题:
在编写的过程中，首先遇到的困难是如何把算法转化为一个c语言程序,对于链表的操作，自己已经搞忘的差不多了，编写的时候对于如何实现一个环形链表，自己刚开始时有些不知所措，后来在同学的指导下，有了思路。还有就是对于把算法转化为程序的步骤，自己还要加强。还有就是自己编写程序时，粗心大意，总是忘记加一些符号。比如第一次调试的时候，出现了这样的错误。

后来才发现，少加了一个大括号，以后这种情况要少出现。

1. 实验题目：
归并顺序表（选作）。
请按以下要求编程实现：
① 从键盘输入两个升序排列的整数序列linka和linkb，每个序列以输入0为结束标记。
② 将链表linka和linkb归并为linkc，linkc仍然为升序排列。归并完成后，linka和linkb为空表。输出linkc。
③ 对linkc进行处理，保持升序不变，删除其中重复的整数，对重复的整数只保留一个，输出删除重复整数后的链表。
例如：linka输入为：10 20 30 40 50 0
归并后的linkc为：10 15 20 20 25 30 30 35 40 40 45 50 50
删除重复后的linkc为：10 15 20 25 30 35 40 45 50

2. 源代码：
#include <stdio.h>
#include <malloc.h>

typedef struct LNode
{
int data;
struct LNode *next;
}LNode,*LinkList;

void Creat(LinkList &L);
void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc);
void Delete(LinkList &L);
void Output(LinkList &L);

int main()
{
LinkList La,Lb,Lc;
Creat(La);
Creat(Lb);
MergeList(La,Lb,Lc);
free(La);
free(Lb);
Delete(Lc);
Output(Lc);
}

void Creat(LinkList &L)
{
LinkList p,q;
int num;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
p=L;
scanf("%d",&num);
while(num!=0)
{
q=(LinkList)malloc(sizeof(LNode));
q->data=num;
q->next=p->next;
p->next=q;
p=q;
scanf("%d",&num);
}
}

void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)
{
LinkList pa,pb,pc,p,q;
pa=La->next;
pb=Lb->next;
Lc=(LinkList)malloc(sizeof(LNode));
Lc->next=NULL;
pc=Lc;
while(pa&&pb)
{
q=(LinkList)malloc(sizeof(LNode));
if(pa->data<=pb->data)
{
q->data=pa->data;
pa=pa->next;
}
else
{
q->data=pb->data;
pb=pb->next;
}
q->next=pc->next;
pc->next=q;
pc=pc->next;
}
while(pa)
{
p=(LinkList)malloc(sizeof(LNode));
p->data=pa->data;
p->next=pc->next;
pc->next=p;
pa=pa->next;
}
while(pb) / {
p=(LinkList)malloc(sizeof(LNode));
p->data=pb->data;
p->next=pc->next;
pc->next=p;
pb=pb->next;
}
}
void Delete(LinkList &L)
{
LinkList p,q,r;
p=L->next;
q=L->next->next;
r=q;
while(q!=NULL)
{
if(q->data==p->data)
{
q=q->next;
p->next=r->next;
free(r);
r=q;
}
else
{
p=p->next;
q=q->next;
r=q;
}
}
}

void Output(LinkList &L）
{
LinkList p;
p=L->next;
while(p->next!=NULL)
{
printf("%d,",p->data);
p=p->next;
}
printf("%d\n",p->data);
}
3. 运行结果截屏:

4. 编写和调试遇到的问题：
对于链表合并的问题，书上本来有例子，但是在编写的过程中，却遇到了很多问题，比如对于算法步骤的不熟悉，不知道从哪里开始，其次没有想到最后还要删除原来的两个链表，所以导致结果一直没有正确。还有就是在创建链表的时候没有把数据加进去，结果编译通过了，但是输入数字，却没有反应。
可编辑修改