#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
int temptag = 0;
typedef int ElemType;
typedef struct LNode //定义单链表结点类型
{
ElemType data;
struct LNode *next;
} LinkList;
void InitList(LinkList *&L) //初始化链表，若要重新输入数据，就应该先初始化链表
{
L=(LinkList *)malloc(sizeof(LinkList)); //创建头结点
L->next=NULL;
printf("初始化链表成功！\n");
}
void DestroyList(LinkList *&L) //销毁链表，也就是释放内存
{
LinkList *p=L,*q=p->next;
while (q!=NULL)
{
free(p);
p=q;
q=p->next;
}
free(p);
}
int ListLength(LinkList *L) //输出链表的长度
{
LinkList *p=L;int i=0;
while (p->next!=NULL)
{
i++;
p=p->next;
}
return(i);
}
void DispList(LinkList *L) //显示链表的数据
{
printf("链表中的数据如下：\n");
LinkList *p=L->next;
while (p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
int GetElem(LinkList *L,int i,ElemType &e) //获取链表中的任意位置的元素。但是不能越界
{
int j=1;
LinkList *p=L->next;
while (j<i && p!=NULL)
{
j++;
p=p->next;
}
if (p==NULL)
return 0;
else
{
e=p->data;
return 1;
}
}
int ListInsert(LinkList *&L,int i,ElemType e) //插入新的节点
{
int j=0;
LinkList *p=L,*s;
while (j<i-1 && p!=NULL)
{
j++;
p=p->next;
}
if (p==NULL) //未找到第i-1个结点
{
printf("未找到第%d个节点！\n", (i-1));
return 0;
}
else //找到第i-1个结点*p
{
s=(LinkList *)malloc(sizeof(LinkList)); //创建新结点*s
s->data=e;
s->next=p->next; //将*s插入到*p之后
p->next=s;
return 1;
}
}
int ListDelete(LinkList *&L,int i) //删除相应位置的节点
{
int j=0;
LinkList *p=L,*q;
while (j<i-1 && p!=NULL)
{
j++;
p=p->next;
}
if (p==NULL) //未找到第i-1个结点
return 0;
else //找到第i-1个结点*p
{
q=p->next; //q指向要删除的结点
if (q==NULL) return 0;
//e=q->data;
p->next=q->next; //从单链表中删除*q结点
free(q); //释放*q结点
return 1;
}
}
void Delete2(LinkList *&L)//删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同），
{
LinkList *p,*q,*s;
p=L;
q=L->next;
while(q->next)
{
if(q->data==q->next->data)
{
p->next=q->next;
s=q;
q=q->next;
free(s);
}
else
{
p=p->next;
q=q->next;
}
}
printf("删除成功!!!!\n");
}
void jiangxu(LinkList *&L) //降序排列链表中的元素
{
int temp1, temp2;
LinkList *q, *temp;
q = L->next;
while(q != NULL)
{
temp = q->next;
while(temp != NULL)
{
temp1 = q->data;
temp2 = temp->data;
if(temp1 < temp2)
{
q->data = temp2;
temp->data = temp1;
}
temp = temp->next;
}
q = q->next;
}
}
void nizhi(LinkList *&L) //将链表中的元素顺序逆置
{
LinkList *New, *p, *q;
p = L->next;
New = (LinkList *)malloc(sizeof(LinkList));
New->next = NULL;
while(p != NULL)
{
LinkList *s=(LinkList *)malloc(sizeof(LinkList));
s->data = p->data;
p = p->next;
s->next = New->next;
New->next = s;
}
L = New;
}
void MaxAndMin(LinkList *&L) //求最大值和最小值
{
LinkList *temp;
int Max, Min;
temp = L->next;
Max = -100;
Min = 100;
while(temp != NULL)
{
if(temp->data <= Min)
{
Min = temp->data;
}
if(temp->data >= Max)
{
Max = temp->data;
}
temp = temp->next;
}
printf("最大值是：%d\n最小值是：%d\n", Max, Min);
}
void Add(LinkList *&L) //添加一个新的链表，并与之前的链表合并，降序输出
{
LinkList *List2, *p;
InitList(List2);
int data, tag = 1;
printf("请输入第二个链表的数据：\n");
scanf("%d", &data);
while(data != -1)
{
ListInsert(List2, tag, data);
tag++;
scanf("%d", &data);
}
printf("第一个链表：\n");
DispList(L);
printf("第二个链表：\n");
DispList(List2);
p = List2->next;
while(p != NULL)
{
LinkList *s=(LinkList *)malloc(sizeof(LinkList));
s->data = p->data;
p = p->next;
s->next = L->next;
L->next = s;
}
jiangxu(L);
Delete2(L);
printf("合并后的链表：\n");
DispList(L);
}
int main()
{
LinkList *h;
ElemType e;
int temp = 1, data;
while(temp != 0)
{
printf(" (1 )输入 1，初始化单链表h\n");
printf(" (2 )输入 2，采用尾插法插入元素, -1表示输入结束\n");
printf(" (3 )输入 3，输出单链表h:\n");
printf(" (4 )输入 4，输出单链表h长度\n");
printf(" (5 )输入 5，然后输入N，查找单链表的第N个元素\n");
printf(" (6 )输入 6，在第M个元素位置上插入元素NUM\n");
printf(" (7 )输入 7，然后输入K，删除链表的第K个元素\n");
printf(" (8)输入 8，将链表元素降序排列\n");
printf(" (9)输入 9，输出最大值和最小值\n");
printf(" (10)输入 10，将该链表逆置\n");
printf(" (11)输入 11，创建第二个链表，并合并之前链表，降序输出\n");
scanf("%d", &temp);
if(temp == 1)
InitList(h);
else if(temp == 2)
{
printf("请输入数据:");
int tag = 1;
scanf("%d", &data);
while(data != -1)
{
ListInsert(h, tag, data);
tag++;
scanf("%d", &data);
}
printf("数据插入成功！\n");
}
else if(temp == 3)
DispList(h);
else if(temp == 4)
printf("该单链表的长度 = %d\n",ListLength(h));
else if(temp == 5)
{
int N;
printf("请输入数据N:");
scanf("%d", &N);
if(N<1||N>ListLength(h))
printf("你输入的数据不合法！\n");
else
{
GetElem(h,N,e);
printf("第%d个元素是%d\n", N, e);
}
}
else if(temp == 6)
{
int M, num;
printf("请输入M值和NUM值:\n");
scanf("%d%d", &M, &num);
if(M<=0||M>ListLength(h)+1)
printf("你输入的数据不合法！\n");
else
ListInsert(h, M, num);
}
else if(temp == 7)
{
int K;
printf("请输入数据k:");
scanf("%d", &K);
if(K<=0||K>ListLength(h))
printf("无效输入请重新选择删除 \n");
else
ListDelete(h,K);
}
else if(temp == 8)
{
printf("降序成功");
jiangxu(h);
}
else if(temp == 9)
{
MaxAndMin(h);
}
else if(temp == 10)
{ printf("逆置成功");
nizhi(h);
}
else if(temp == 11)
{
Add(h);
}
}
system("pause");
return 0;
} |
|
楼主
标题置顶
标题高亮
