单向循环链表操作实现~ - 数据结构与算法

xxyshow115

等　级：新手上路
帖　子：8
专家分：0
注　册：2007-6-4

楼主

问题点数：0 回复次数：5

单向循环链表操作实现~

/*1：输出单向循环链表的所有结点的值
2：查找第i个结点或值为某一个值的结点
3：在指定的地方插入一个结点
4：删除指定的结点
5: 退出系统*/

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "malloc.h"
#include "iostream.h"
#define DATATYPE char
struct LINKLIST
{
DATATYPE data;
struct LINKLIST *next;
};

void print(struct LINKLIST *head) //输出链表元素
{
struct LINKLIST *p;//定义一个指针
p=head->next;
cout<<"输出元素值：";
while(p!=head)
{
cout<<p->data<<" ";
p=p->next;
}
}

void get(int i,struct LINKLIST *head)//按序号查找
{
struct LINKLIST *p;
int j;
j=0;
p=head;
while((j<i)&&(p->next!=head))
{
p=p->next;
j++;
}
if(j==i)
cout<<"您要找的第"<<i<<"个元素是："<<p->data;
else
cout<<"没有找到您要找的元素！";
}

struct LINKLIST * locat(DATATYPE x,struct LINKLIST *head)//按值查找元素
{
struct LINKLIST *p;
p=head->next;
while(p!=head)
{
if(p->data==x)
{
return p;
}
else
{
p=p->next;
}
}
if(p==head)
{
return NULL;
}
}

void insertafter(DATATYPE insertdata,struct LINKLIST *p)//在已知结点之后插入一个结点
{
LINKLIST *t;
if(p)
{
t=(struct LINKLIST *)malloc(sizeof(struct LINKLIST));
t->data=insertdata;
t->next=p->next;
p->next=t;
}

}

int deletafter(struct LINKLIST *head,struct LINKLIST *p) // 删除后继结点
{
struct LINKLIST *t;
int r=1;
if(p->next!=head)
{
t=p->next;
p->next=t->next;
free(t);
}
else
r=0;
return r;
}

int deletself(struct LINKLIST *head,struct LINKLIST *p) //删除结点本身
{

LINKLIST *q;

q=head;
if(!p)
return 0;
else
while(q->next!=p && q->next!=head)
q=q->next;
q->next=p->next;
free(p);
return 1;

}
void main()
{
int i;
LINKLIST *p;
LINKLIST *head,*t,*last;
// p=head;

t=( LINKLIST *)malloc(sizeof(LINKLIST));//单链表的建立(尾插入法)
char ch,insertdata;
head=t;
last=t;
t->next=head;
printf("单链表元素为单个字符，连续输入(不要空格)，以“0”为结束标志:\n");
while((ch=getchar())!='0')
{
t=( LINKLIST *)malloc(sizeof(LINKLIST));
t->data=ch;
t->next=head;

last->next=t;
last=t;
}
cout<<endl<<"/*********************************************/";
cout<<endl<<"/*************单向循环链表的操作**************/";
cout<<endl<<"/*********************************************/";
cout<<endl<<"/******************欢迎使用！*****************/";
cout<<endl<<"/*********************************************/";
cout<<endl<<"/*************制作者：xxyshow115、just、ㄣ黑銫禮ゞ菔******/";
cout<<endl<<"/*********************************************/";
cout<<endl<<endl<<"1………………………输出链表元素";
cout<<endl<<"2………………………按序号查找元素";
cout<<endl<<"3………………………按值查找元素";
cout<<endl<<"4………………………在指定结点后插入元素";
cout<<endl<<"5………………………删除后继结点";
cout<<endl<<"6………………………删除结点本身";
cout<<endl<<"7………………………退出系统";

do
{
cout<<endl<<"请选择您要执行的操作：";
cin>>i;
switch(i)
{
case 1:print(head);break;

case 2:int j;
cout<<"请输入你要查找的序号：";
cin>>j;
get(j,head);
break;

case 3:cout<<"请输入你要查找的字符：";
cin>>ch;
p=locat(ch,head);
if(p)
cout<<"已经找到你要的元素:"<<p->data;
else
cout<<endl<<"无此结点!";
break;

case 4: cout<<"在哪个结点后插入:";
cin>>ch;
p=locat(ch,head);
if(!p)
cout<<endl<<"您输入的值不存在！";
else
{
cout<<"插入结点值:";
cin>>insertdata;
insertafter(insertdata,p);
cout<<endl<<"操作后的链表为：";
print(head);
}
break;

case 5: cout<<"删除哪个结点的后继:";
cin>>ch;
p=locat(ch,head);
if(!p)
cout<<endl<<"您输入的值不存在！";
else
{
if(deletafter(head,p))
cout<<"删除成功！";
cout<<"操作后的链表为：";
print(head);
}
break;
case 6: cout<<"删除哪个结点:";
cin>>ch;
p=locat(ch,head);
if(!p)
cout<<endl<<"您输入的值不存在！";
else
{
if(deletself(head,p))
cout<<"删除成功！";
cout<<"操作后的链表为：";
print(head);
}
break;
case 7:exit(0);
}
}while(i!=7);
}