实验一 线性表的基本操作及其应用
一、实验目的
1、帮助读者复习C++语言程序设计中的知识。
2、熟悉线性表的逻辑结构。
3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。
二、实验内容
本次实验提供4个题目，每个题目都标有难度系数，*越多难度越大，学生可以根据自己的情况选做，其中题目一是必做题，其它选作！
ü 题目一：单链表的基本操作（必做题 *）
题目二：约瑟夫环（**）
[问题描述]
实现带头结点的单链表的建立、求长度，取元素、修改元素、插入、删除等单链表的基本操作。
[基本要求]
（1）依次从键盘读入数据，建立带头结点的单链表；
（2）输出单链表中的数据元素
（3）求单链表的长度；
（4）根据指定条件能够取元素和修改元素；
（5）实现在指定位置插入和删除元素的功能。
[测试数据]
由学生任意指定。
三、算法设计
1.算法思想：
主要设计了一个包含数据和指针域的结点。
Data *next
主要思想：
插入：
删除：
四、本函数包含八个模块
1.主函数int main() :初始化一个链表L，显示菜单，主要语句：switch语句，while语句，goto语句。
2.创建并输入链表数据linklist createlist（），在该函数中创建头结点，并输入结点上的数据。
伪代码：while（当x!=00）
{
p = new list;
p->data = x;
p->next = NULL;
q->next = p;
q = p;
}
3.显示链表数据void show（linklist L）
1）先判断是否是空表，再逐个寻找想要的元素。
2）主要代码：
while(p)
{
cout<<p->data<<"\t";
p = p->next;
}
4.获取链表长度int getlength(linklist L)
1)先判断是否为空，再遍历链表，算出链表长度。
2)主要代码：
while(p)
{
p = p->next;
length++;
}
5.获取第i个元素int getdata(linklist L,int i)
1）当0<i<length时，遍历链表，找到第i个元素。
2）主要代码：
while(p&&j<i)
{
j++;
p = p->next;
}
6.改变链表数据int changedata(linklist L,int e,int d)
1）找到要修改的值e，再把d赋值给e.
2)主要代码：
while(p&&p->data!=e)
{
p = p->next;
}
if(!p)
return ERROR;
p->data = d;
7.插入一个结点linklist insertlist(linklist L,int i,int e)
1)因为要插入第i个元素，所以要先找到第i-1个元素，在i-1后面插入。
2）主要代码：
s->data = e;
s->next = p->next ;
p->next = s;
8.删除一个结点linklist deletelist(linklist L,int i)
1）同插入差不多，先找到第i-1个元素，然后再把i-1结点指针域指向原本指向结点的下一个，把中间那个删除，再free，释放空间，
主要代码：
q = p->next;
p->next =q->next;
free(q);
五、实验过程
图1、登陆界面
图2、功能键1，2，3，4的实现
图3、功能键5、6的实现
图4、功能键7、0的实现
六、调试及感受
又是一次课设时，每次写程序总会遇到大大小小的毛病，就不断的调试调试，觉得写代码是需要很大的耐心，一直琢磨，一直分析，一直改，直至完美。可是当代码运行到自己想要的程度时，内心是那么的自豪，那么的傲娇，那么的兴奋，仿佛心长了翅膀似的，飞到高空翱翔去了，呵呵，感觉不错。不过，我希望自己下次不用再借鉴网上的代码，就能够自己迎仞有余，加油，我可以的！
并且谢谢老师的教导，老师您辛苦了！！！
七、源代码
#include<iostream>
#include<stdio.h>
#include<malloc.h>
#define ERROR -1;
using namespace std;
typedef struct node{
int data;
node *next;
}list,*linklist;
linklist createlist()//输入链表数据
{
linklist head;
head = new list;
head->next = NULL;
list *p,*q;
q = head;
int x;
cin>>x;
while(x!=00)
{
p = new list;
p->data = x;
p->next = NULL;
q->next = p;
q = p;
cin>>x;
}
return head;
}
void showlist(linklist L)//显示链表数据
{
if(L->next==NULL)
cout<<"该链表是空表!"<<endl;
else
{
list *p;
p = L->next;
cout<<"该链表数据如下所示："<<endl;
while(p)
{
cout<<p->data<<"\t";
p = p->next;
}
cout<<endl;
}
}
int getlength(linklist L)//获取链表长度
{
list *p;
p = L->next;
int length;
if(p==NULL)
return 0;
length = 0;
while(p)
{
p = p->next;
length++;
}
return length;
}
int getdata(linklist L,int i)//获取第i个元素
{
list *p;
int j = 1;
p = L->next;
while(p&&j<i)
{
j++;
p = p->next;
}
if(!p||j>i)
return ERROR;
return p->data;
}
int changedata(linklist L,int e,int d)//改变链表数据
{
list *p;
p = L->next;
while(p&&p->data!=e)
{
p = p->next;
}
if(!p)
return ERROR;
p->data = d;
return p->data ;
}
linklist insertlist(linklist L,int i,int e)//插入一个结点
{
list *p,*s;
s = new list;
int j = 1;
p = L->next;
while(p&&j<i-1)
{
j++;
p = p->next;
}
if(!p||j>i-1)
{
cout<<i<<"太大！"<<endl;
return NULL;
}
s->data = e;
s->next = p->next ;
p->next = s;
return L;
}
linklist deletelist(linklist L,int i)//删除一个结点
{
list *p,*q;
p = L;
int j = 1;
while(p&&j<i)
{
j++;
p = p->next;
}
if(!p||j>i)
return NULL;
q = p->next;
p->next =q->next;
free(q);
return L;
}
int main()//主函数
{
linklist L;
list *t;
L = new list;
L->next = NULL;
int n,x,a,b,i,flag = 0;
cout<<"\t\t++++++++++++++++++++++++++++++++++++++++++++++++++"<<endl<<endl;
cout<<"\t\t+++++++++++欢迎来到此界面！！！+++++++++++"<<endl<<endl;
cout<<"\t\t+\t1、输入链表数据"<<endl<<endl;
cout<<"\t\t+\t2、显示链表数据"<<endl<<endl;
cout<<"\t\t+\t3、显示链表长度"<<endl<<endl;
cout<<"\t\t+\t4、获取链表数据"<<endl<<endl;
cout<<"\t\t+\t5、改变链表数据 "<<endl<<endl;
cout<<"\t\t+\t6、插入一个结点"<<endl<<endl;
cout<<"\t\t+\t7、删除一个结点"<<endl<<endl;
cout<<"\t\t+\t0、退出界面"<<endl<<endl;
cout<<"\t\t++++++++++++++++++++++++++++++++++++++++++++++++++"<<endl<<endl;
loop: cout<<"====>>请选择您想要的功能键："<<endl;
while(!flag)
{
cin>>n;
switch(n)
{
case 1:
cout<<"请输入数据元素，以00结束"<<endl;
L = createlist();
goto loop;
case 2:
showlist(L);
goto loop;
case 3:
cout<<"所求表长为："<<getlength(L)<<endl;
goto loop;
case 4:
cout<<"请输入元素所在的位置："<<endl;
cin>>i;
cout<<"所找的元素为："<<getdata(L,i)<<endl;
goto loop;
case 5:
cout<<"请输入要修改元素的值和放入该位置的值："<<endl;
cin>>a>>b;
cout<<"元素"<<a<<"被替换成"<<changedata(L,a,b)<<endl;
goto loop;
case 6:
cout<<"请输入要插入的结点位置和插入该结点的元素："<<endl;
cin>>i>>x;
t = insertlist(L,i,x);
if(t == NULL)
cout<<"插入无效！"<<endl;
else
cout<<"在"<<i<<"上已插入"<<x<<",若要查看请按2进行查看："<<endl;
goto loop;
case 7:
cout<<"请输入要删除的结点位置："<<endl;
cin>>i;
t = deletelist(L,i);
if(t == NULL)
cout<<"删除不成功！"<<endl;
else
cout<<i<<"结点已删除，若要查看请按2进行查看："<<endl;
goto loop;
default:
flag = 1;
}
}
system("pause");
return 0;
}
实验一 线性表的基本操作及其应用
一、实验目的
1、帮助读者复习C++语言程序设计中的知识。
2、熟悉线性表的逻辑结构。
3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。
二、实验内容
本次实验提供4个题目，每个题目都标有难度系数，*越多难度越大，学生可以根据自己的情况选做，其中题目一是必做题，其它选作！
题目一：单链表的基本操作（必做题 *）
ü 题目二：约瑟夫环（**）
[问题描述]
约瑟夫（Joseph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。
[基本要求]
利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。
[测试数据]
由学生任意指定。
如：m的初值为20；n的值为7；密码：3，1，7，2，4，8，4；
（正确的输出结果应为6，1，4，7，2，3，5）。
(报告上要求写出多批数据测试结果)
[实现提示]
程序运行后首先要求用户输入初始报数上限值m，人数n,(设n≤30)。然后输入各人的密码。
[选作内容]
向上述程序中添加在顺序结构上实现的部分。
三、算法设计
1）先在主函数中输入几个人和初始密码
2）按照单链表那样先构造一个单链表，给结点输入元素，再把尾指针指向头结点。
3）定义两个指针，一个临时指针和一个头指针，当临时指针p和头指针head不在同一个结点时，说明还剩下多个结点，写一个for循环，找出第password个结点，用p->next = head->next将其删除，并把值pasword保留下来，然后把head指向p的下个结点，直到整个链表删除完毕。
四、本函数包含三个模块
1.主函数main()
1）写了do while循环，当输入y或者Y，继续循环。
2）主要代码：
do{
}while(stop=='y'||stop=='Y');
2.创建循环链表linklist creatlist(int n)
1）先构造两个指针，头指针head和临时指针p,然后创造一个结点，把元素password和顺序数i放入结点，再把p指向下一个结点，等快达到要求的个数n-1后，退出循环，输入最后一个结点的数据，把尾指针指向头结点。
2）主要代码：
for(i = 1;i<n;i++)
{
p->i = i;
cout<<“请输入第”<<i<<"号所带密码："<<endl;
cin>>pass;
p->password = pass;
p->next = new list;
p = p->next;
}
3.约瑟夫环实现函数void josefuhuan(linklist head,int password)
1)构造一个临时指针，然后判断该指针是否与头指针指向同一处，如果指向同一处则退出循环，然后再来一个循环，寻找密码，找到指令密码所指，并将其删除，把所删除的密码值留下来，作下一次的循环密码。
2)主要代码：
for(i = 1;p!=head;i++)
{
for(j = 1;j<password;j++)
{
p = head;
head = head->next;
}
p->next = head->next;
五、实验过程
图1.进入系统界面
图2、输入人数和上限值界面
图3、输出结果界面
六、调试及感受
由单向链表过渡到循环的链表，还真是一个思想过度的难区，思来想去许久，还得要查阅，更改，嗨！还有就是调试，代码落写了一些，一运行到某个地方就给卡住了，还好修改及时，还没那么头疼。
然后感谢老师教我们这么多东西！谢谢！！！
七、源代码
#include<iostream>
using namespace std;
typedef struct node{
int password;
int i;
node *next;
}list,*linklist;
linklist creatlist(int n)//初始化链表并输入链表数据
{
list *head,*p;
int i,pass;
head = p = new list;
for(i = 1;i<n;i++)
{
p->i = i;
cout<<"请输入第"<<i<<"号所带的密码："<<endl;
cin>>pass;
p->password = pass;
p->next = new list;
p = p->next;
}
p->i = i;
cout<<"请输入第"<<i<<"号所带的密码："<<endl;
cin>>pass;
p->password = pass;
p->next = head;
return head;
}
void josefuhuan(linklist head,int password)//约瑟夫环的实现
{
int i,j;
list *p;
p = new list;
for(i = 1;p!=head;i++)
{
for(j = 1;j<password;j++)
{
p = head;
head = head->next;
}
p->next = head->next;
cout<<"\n第"<<i<<"个出局的编号是："
<<head->i <<"号\t\t第"<<i<<"个的密码是："
<<head->password<<endl;
password = head->password;
delete head;
head = p->next;
}
i = head->password;
j = head->i;
cout<<"\n第7个出局的编号是："<<j<<"号\t\t第7个的密码是："<<i<<endl<<endl;
delete head;
}
int main()//主函数
{
int n,password;
char stop;
list *head;
cout<<"++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++"<<endl;
cout<<"+++++++++++++++++^o^……欢迎来玩“约瑟夫环”……^o^+++++++++++++++++++"<<endl;
do
{
cout<<"\n\t\t开始......\n\n输入约瑟夫环问题的人数和起始密码："<<endl;
cin>>n>>password;
head = creatlist(n);
cout<<"------------------------------------------------\n"<<endl;
cout<<"输出结果如下：\n"<<endl;
josefuhuan(head,password);
cout<<"------------------------------------------------\n"<<endl;
cout<<"是否继续进行？是按：Y（y）,否按：N（n）"<<endl;
cin>>stop;
if(stop == 'n'||stop =='N')
break;
cout<<"------------------------------------------------\n"<<endl;
}while(stop=='y'||stop=='Y');
system("pause");
return 0;
}