一、实验目的
1、掌握线性表中元素的前驱、后续的概念。
2、掌握链表的建立、插入元素、删除表中某元素的算法。
3、对线性表相应算法的时间复杂度进行分析。
4、理解链表数据结构的特点（优缺点）。
二、实验预习
说明以下概念
1、线性表： 线性表是最基本的一种数据结构。线性表是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。
2、链表：数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
三、实验内容和要求
1、循环链表的应用（约瑟夫回环问题）
n 个数据元素构成一个环，从环中任意位置开始计数，计到 m 将该元素从表中取出，重复上 述过程，直至表中只剩下一个元素。
提示：用一个无头结点的循环单链表来实现 n 个元素的存储。
算法代码
#include<iostream>
#include<malloc.h>
#include<stdlib.h>
using namespace std;
typedef struct LNode {
int data;
struct LNode *next;
}LinkList;//循环单链表结点类型定义
//构造一个空的循环单链表L
void InitLinkList(LinkList *L)
{
L->next=L;//循环单链表初始时next回指
}
//在循环单链表L中将e插入到第i个位置
void LinkListInsert(LinkList *L,int i,int e)
{
int j=1;
LinkList *p=L;//p指向头结点
LinkList *r;//r指向新结点。即值域为e的结点
if(p->next!=L&&i!=1)//原单链表为空表，或者只有一个元素
{
p=L->next;
while(j<i-1&&p!=L)//查找第i-1个结点
{
j++;
p=p->next;
}
if(p!=L)//注意循环单链表判断结束的条件
{
r=(LinkList *)malloc(sizeof(LinkList));//创建新结点r，其值域为e，将其插入第i-1个位置之后
r->data=e;//为新结点赋值
//加入到循环单链表L中
r->next=p->next;
p->next=r;
}
else
printf("无");//若未找到，则给出适当的提示
}
else
{
r=(LinkList *)malloc(sizeof(LinkList));//创建新结点
r->data=e;//为新结点赋值
//加入到循环单链表L中
r->next=p->next;
p->next=r;
}
}
//输出显示循环单链表L中的元素
void DispLinkList(LinkList *L)
{
LinkList *p=L->next;
while(p!=L)
{
printf("%d ",p->data);
p=p->next;
}
}
//获取循环单链表L中第i个结点的元素值
int GetLinkListElem(LinkList *L,int i)
{
int e;//用于存储返回元素的值
int j;
LinkList *p=L->next;//指向首结点
if(i==1)//判断是否为第一个结点
{
e=L->next->data;//获取第一个结点值域
return e;
}
else
{
for(j=0;j<i-1&&p!=L;j++)//p指向符合要求的位置
{
p=p->next;//指向下一个结点
}
e=p->data;//获取元素的值域
return e;//返回元素的值
}
}
//判断循环单链表L是否为空
int LinkListEmpty(LinkList *L)
{
if(L->next==L)//判断是否结束，注意循环单链表判断结束的条件
return 0;//循环单链表为空，返回0
else
return 1;//循环单链表不为空，返回1
}
//求循环单链表L的长度，即元素个数
int LinkListLength(LinkList *L)
{
int i;//i用于计数
LinkList *p=L;
for(i=0;p->next!=L;i++)//判断是否结束，注意循环单链表判断结束的条件,i的计数初值为0
{
p=p->next;//指向下一个结点
}
return i;//循环结束得到总长度值i
}
//在循环单链表L中删除第i个元素
void LinkListDelete(LinkList *L,int i)
{
LinkList *p=L;
LinkList *q;
int j;
if(i==1)//判断删除的是否为第一个元素
{
q=L->next;
L->next=q->next;//回指
free(q);
}
else
{
p=L->next;
for(j=1;j<i-1&&p!=L;j++)//查找第i-1个结点
{
p=p->next;//找到下一个结点
}
if(p!=L)//注意循环单链表判断结束的条件
{
q=p->next;
p->next=q->next;//从链表中删除该结点
free(q);//成功删除该结点
}
}
}
int main(){
int n,x,y,z;
cout<<"输入数据元素个数"<<endl;
cin>>n;
LinkList *L=(LinkList *)malloc(sizeof(LinkList));
cout<<"初始化循环单链表"<<endl;
InitLinkList(L);
cout<<"插入"<<n<<"个元素"<<endl;
for(int i=1;i<=n;i++)
{ cout<<"第"<<i<<"个元素:";
int a;
cin>>a;
LinkListInsert(L,i,a);
}
cout<<"循环单链表元素为:"<<endl;
DispLinkList(L);
cout<<endl;
cout<<"输入开始的位置：";
cin>>x;
cout<<"输入步长：";
cin>>y;
cout<<"从表中取出元素:"<<GetLinkListElem(L,x)<<endl;
LinkListDelete(L,x);
cout<<endl;
while(LinkListEmpty(L)==1) {
if((x+y-1)>LinkListLength(L))
{
if((x+y-1)%(LinkListLength(L))==0)
x=x;
else
x=(x+y-1)%(LinkListLength(L));
}
else x=x+1;
cout<<"从表中取出元素:"<<GetLinkListElem(L,x)<<endl;
LinkListDelete(L,x);
cout<<endl;
if(LinkListLength(L)==1){ cout<<"从表中取出元素:"<<GetLinkListElem(L,1)<<endl;
LinkListDelete(L,x);
return 0;
}
}
return 0;
}
编辑
2、设一带头结点的单链表，设计算法将表中值相同的元素仅保留一个结点。
提示：指针 p 从链表的第一个元素开始，利用指针 q 从指针 p 位置开始向后搜索整个链表，
删除与之值相同的元素；指针 p 继续指向下一个元素，开始下一轮的删除，直至 p＝＝null 为至，既完成了对整个链表元素的删除相同值。
算法代码
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node *next;
}Node,*PNode;
//头插法建立带有头结点的单链表
PNode creat_list(){
PNode head = (PNode)malloc(sizeof(Node));
head->next = NULL;
scanf("%d",&(head->data)); // 头结点的数据域可以存放总结点数
PNode p = NULL;
int i;
for(i=0;i<(head->data);i++){
p = (PNode)malloc(sizeof(Node));
scanf("%d",&(p->data));
//这是头插法的关键所在
p->next = head->next;
head->next = p;
}
return head;
}
//删除重复节点
void del_repeated_node(PNode head){
PNode k = head->next, pre_p = k, p = pre_p->next;
//遍历单链表的每一个节点
while(k && k->next != NULL){
//判断k后面的节点是否与k的值域重复，如果重复，则删去。
while(p){
if(k->data == p->data){
//删除重复的p节点
PNode temp = p;
pre_p ->next= p->next;
p = pre_p->next;
free(temp);
}else{
pre_p = pre_p->next;
p = pre_p->next;
}
}
k = pre_p = k->next;
p = pre_p->next;
}
}
void print_list(PNode head){
PNode p = head->next;
while(p){
printf("p->data: %d \t",p->data);
p = p->next;
}
printf("\n");
}
int main(){
PNode head = creat_list();
print_list(head);
del_repeated_node(head);
print_list(head);
return 0;
}
算法代码3、 设计与实现双向循环链表
双向循环链表的结构定义： 双向循环链表就是在双向链表的基础上，让头节点的前驱指针指向链表的最后一个节点，让最后一个节点的后继指针指向头节点。
拟实现的主要操作： 双向链表的删除
主要算法描述：双链表结点的首结点的head指向为null，tail指向下一个节点的tail;尾结点的head指向前一个结点的head，tail 指向为null，是双向的关系.
关键代码：
//在p结点之前插入一个结点s
void ListInsert_Dul(LinkList &L, int i, int &e){
LinkList s = (LNode *)malloc(sizeof(LNode));//创建新结点
s->data = e;
s->pre = q->pre;
p->pre->next = s;
s->next = p;
p->pre = s;
}
//删除p结点
void ListDelete_Dul(LinkList &L, int i, int &e){
e = p->data;
p->pre->next = p->next;
p->next->pre = p->pre;
free(p);
}
四、实验小结
循环单链表就是构造一个空的循环单链表，初始时回指，其余元素随即加入。双向循环链表双链表结点的首结点的head指向为null，tail指向下一个节点的tail;尾结点的head指向前一个结点的head，tail 指向为null，是双向的关系.。
五、教师评语
