详细代码如下
#include "stdio.h"
#include "malloc.h"
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define TRUE 1
#define FALSE 0
#define List_Init_Size 10
#define ListIncrement 2
typedef int ET;
typedef ET * Ep;
typedef int Status;
typedef struct LNode{
ET data;
struct LNode *next;
}LNode, *LinkList;
LinkList La,Lb,Lc;
//打印链表中的元素
void printlk(LinkList L) {
LinkList p;
p=L->next;
while (p) {
printf("%d ",p->data);
p = p->next;
}
printf("\n");
}
//生成一个空链表
LinkList initList()
{
LinkList L;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
return L;
}
LinkList initList1( LinkList L)
{
LinkList p;
p=(LinkList)malloc(sizeof(LNode));
p->next=NULL;
Lb= p;
return L;
}
//头插法生成链表
void CreatList(LinkList L )
{
int j,n,k;
LinkList p;
printf("请输入链表中的元素个数 : ");
scanf("%d",&n);
L->next=NULL;
for (j=n;j>0;j--)
{
p=(LinkList)malloc(sizeof(LNode));
printf("请读入第%d个元素值\n",j);
scanf ("%d", &k);
p->data = k;
p->next = L->next;
L->next = p;
}
}
void clear(LinkList L){
L->next=NULL;
}
void CreatList1(LinkList L)
//尾插法生成链表
{
int s,i,n;
LinkList r,p;
printf("请输入链表中的元素个数 : ");
scanf("%d",&n);
r=L;
for(i=0;i<n;++i){
p=new LNode;
printf("请读入第%d个元素值\n",i);
scanf("%d",&s);
p->data=s;
p->next=NULL;
r->next=p;
r=p;
}
}
void MenuList()
{
printf("\n\n\n**************************\n");
printf(" 1 ------- 初始化 LA\n");
printf(" 2 ------- 尾插法生成链表La\n");
printf(" 3 ------- 头插法生成链表La\n");
printf(" 4 ------- 向链表中第i号位置插入元素\n");
printf(" 5 ------- 删除链表中第i号元素 \n");
printf(" 6 ------- 求链表中元素个数 \n");
printf(" 7 ------- 查找链表中值为x的第一个元素 \n");
printf(" 8 ------- 查找链表中第i号元素 \n");
printf(" 9 ------- 链表的归并 \n");
printf(" 10 ------- 单链表La的倒置 \n");
printf(" 11 ------- 删除单链表La中值为X的结点\n");
printf(" 12 ------- 约瑟夫环问题求解 \n");
printf(" 13 ------- 输出LA中的元素 \n");
printf(" 14 ------- 清空LA中的元素 \n");
printf(" 15 ------- 删除绝对值相等的结点 \n");
printf("**************************\n");
}
LinkList Insert(LinkList L)
{
LinkList p=L,s;
int i,j=0,s2;
printf("请插入元素的下标以及值： \n");
scanf("%d,%d",&i,&s2);
while(p&&(j<i-1)){
p=p->next;
++j;
}
s=(LinkList)malloc(sizeof(LNode));
s->data=s2;
s->next=p->next;
p->next=s;
printlk(L);
return L;
}
LinkList deletedata(LinkList L)
{//删除元素
LinkList p,q;
int j=1,k,x;
p=L;
printf("输入删除位置：\n");
scanf("%d",&k);
while((p)&&(j<k)){
j++;
p=p->next;
}
if(p->next){
q=p->next;
p->next=q->next;
delete q;
}else printf("输入的位置不正确");
printlk(L);
return L;
}
void locatedata(LinkList L)
{//查找第i个元素
LinkList p;
int i,m=1;
printf("请输入要查找的是第i个元素：\n");
scanf("%d",&i);
p=L->next;
while(p&&m!=i){
p=p->next;
m++;
}
printf("查找到的第i个元素是%d： \n",p->data);
}
LinkList finddata(LinkList L,int x)
{ //查找值为X的元素
LinkList p,q;
p=L->next;//p指向首元结点
q=L;
while(p&&p->data!=x) {
p=p->next;
q=q->next;
}
if(p==NULL)
printf("该链表中不存在值为%d的元素",x);
return q;//返回值为x的结点的前驱
}
int sqlength(LinkList L)
{//求链表中的元素个数
LNode *p; //p需要声明为LNode类型
p=L->next;
int j=0;
while(p!=NULL)
{
j++;
p=p->next; //将p向下移动一个结点
}
printf("链表中的长度为%d",j);
printf("\n");
return 1;
}
LinkList Un(LinkList L)
{//将链表倒置
LinkList p,q,pr;
p = L->next;
q = NULL;
L->next = NULL;
while(p){
pr = p->next;
p->next = q;
q = p;
p = pr;
}
L->next = q;
printlk(L);
return L;
}
LinkList delx(LinkList L)
{删除所有值为x的结点
int x;
LinkList p,q,t;//q指向p的前驱
p=L->next;
q=L;
printf("请输入要删除的x的值为：\n");
scanf("%d",&x);
if(p==NULL)
return 0;//表为空
while(p!=NULL){
if(p->data==x){
t=p;//t指向被删结点
p=p->next;
q->next=p;
free(t);
}
else{
q=p;
p=p->next;
}
}
printlk(L);
return L;
}
LinkList meg_sql(LinkList La, LinkList Lb, LinkList Lc)//有问题
{//合并递减的La和递减的Lb
Lb=initList();
printf("--创建递减的链表Lb--\n");
CreatList1(Lb);
printf("La为：\n");
printlk(La);
printf("Lb为：\n");
printlk(Lb);
Lc=initList();
LinkList pa,pb,pc;
pa=La->next;
pb=Lb->next;
pc=Lc;
while(pa&&pb){
if(pa->data>=pb->data){
pc->next=pa;
pc=pa;
pa=pa->next;
}
else{
pc->next=pb;
pc=pb;
pb=pb->next;
}
}
pc->next=pa?pa:pb;
free(Lb);
printf("得到的Lc为：\n");
printlk(Lc);
return Lc;
}
LinkList simplify_list(LinkList head){//删除绝对值相等的结点
//申请n+1个位置的辅助数组
LinkList p=head,r;
int n;
printf("请输入值n");
scanf("%d",n);
// LinkList q=(LinkList)malloc(sizeof(LNode));
int *q = (int *)malloc(sizeof(int)*(n+1));
printf("!!");
for(int i=0;i<n+1;i++){//数组元素初值设为0
*(q+i)=0;
}
printf("%%%");
printf("$$");
while(p->next!=NULL){
int data = p->next->data;
int addr = data >0? data:-data;
if(*(q+addr)==0){//需要删除当前结点p
*(q+addr)=1;
p=p->next;
}
else{
r=p->next;
p->next=r->next;
free(r);
}
}
free(q);
printlk(head);
return head;
}
LinkList initLink(int n){//循环链表初始化
LinkList head=(LinkList)malloc(sizeof(LNode));
head->data=1;
head->next=NULL;
LinkList p=head;
for (int i=2; i<=n; i++) {
LinkList q=(LinkList)malloc(sizeof(LNode));
q->data=i;
q->next=NULL;
p->next=q;
p=p->next;
}
p->next=head;//首尾相连
return head;
}
void joseph(LinkList head,int k,int m){
LinkList r=head;
//找到链表第一个结点的上一个结点，为删除 *** 作做准备
while (r->next!=head) {
r=r->next;
}
LinkList p=head;
//找到编号为m的位置
while (p->data!=m) {
r=p;
p=p->next;
}
//从编号为m的位置开始，只有符合p->next==p时，说明链表中除了p结点，所有编号都出列了，
while (p->next!=p) {
//找到从m开始报数，报k的位置，并且还要知道k-1的人的位置r，方便做删除 *** 作。
for (int i=1; i<k; i++) {
r=p;
p=p->next;
}
r->next=p->next;//从链表上将p结点摘下来
printf("出列位置为:%d\n",p->data);
free(p);
p=r->next;//继续使用p指针指向出列编号的下一个编号，游戏继续
}
printf("出列位置为:%d\n",p->data);//最后一个出列
free(p);
}
int main( )
{ int i=100,x;
LinkList p;
while(i!=0)
{MenuList();
printf("请输入选择:");
scanf("%d" ,&i);
if (i==1){
La=initList();
printf("空间申请成功\n");
}
if (i==2){
CreatList(La);
printlk(La);
printf("La创建成功\n");
}
if (i==3)
CreatList1(La);
if(i==4) {
Insert(La);
}
if (i==5)deletedata(La);
if(i==6)sqlength(La);
if(i==7){
printf("请输入要查找的元素的值：");
scanf("%d",&x);
p=finddata(La,x);
int n;
LinkList q;
q=La;
for(n=1;p!=q;n++){
q=q->next;
}
printf("值为%d的元素第一次出现在链表的第%d个\n",x,n);
printf("其地址为：%p",p);
}
if(i==8) locatedata(La);
if(i==9) {
meg_sql(La,Lb,Lc);
}
if(i==10)Un(La);
if(i==11)delx(La);
if(i==12){
printf("请输入循环链表中的元素个数：");
int n;
scanf("%d",&n);
LinkList head=initLink(n);
int m;
printf("开始报数的位置为(k>1且k<%d)：",n);
scanf("%d",&m);
int k;
printf("重复开始报数的人与开始报数的人位置差：");
scanf("%d",&k);
joseph(head, k, m);
}
if (i==13)
printlk(La);
if(i==14)clear(La);
if(i==15)simplify_list(La) ;
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）