【数据结构实验期末考试】—删除单链表中第一个最大元素及其重复结点
题目
- 已知单链表A，编写一个算法，删除单链表中第一个最大元素。
- 已知单链表L, 编写一个算法，删除其重复的结点（只保留一个）。
程序设计
1）概要设计
设计几个函数来实现初始化、尾插法建表、删除第一个最大元素、删除重复结点的功能，然后再主函数中调用函数来实现操作。
2）详细设计
导入相关的库
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
单链表的存储结构。
注意：LinkList 和 Node * 同为结构体指针类型，这两种类型是等价的。
通常习惯上用LinkList说明指针变量，强调它是某个单链表的头指针变量。
such as 使用定义LinkList L，则L为单链表的头指针，从而提高程序的可读性。
使用Node * 来定义只想单链表中节点的指针，例如，Node *p,则p为指向单链表中节点的指针变量。
typedef int ElemType;
typedef struct Node
{
ElemType data;
struct Node * next;
}Node,* LinkList;
/*LinkList 和 Node * 同为结构体指针类型，这两种类型是等价的。
通常习惯上用LinkList说明指针变量，强调它是某个单链表的头指针变量。
such as 使用定义LinkList L，则L为单链表的头指针，从而提高程序的可读性。
使用Node * 来定义只想单链表中节点的指针，例如，Node *p,则p为指向单链表中节点的指针变量。*/
初始化单链表
//初始化单链表
void Init_LinkList(LinkList *L)
{
*L=(LinkList)malloc(sizeof(Node));//建立头结点
(*L)->next=NULL;//建立空的单链表
//注意：L是指向单链表头结点的指针，用来接收主程序中带初始化单链表的头指针变量的地址，
//*L相当于主程序中带初始化单链表的头指针变量。
}
尾插法建表
算法思想：将新节点插到前单链表的表尾上。为此需要增加一个尾指针r，使之只想当前单链表的表尾。
//尾插法建表
void CreateFromTail(LinkList L)
{
Node *r,*s;//一个动态的尾指针r
int flag=1;
r=L;
char c;
while(flag)
{
c=getchar();
// printf(" ");
if(c!='$')
{
s=(Node*)malloc(sizeof(Node));
s->data=(int)c;
r->next=s;
r=s;//r始终是在最后的
}
else
{
flag=0;
r->next=NULL;//将最后一个结点的next链域设为空，表示链表的结束
}
}
}
显示单链表。
算法思想：顺着指针一个一个地打印。
//display单链表
void Display_LinkList(LinkList L)
{
//printf("display调用开始\n");
Node *p;
ElemType s;
p=L;
while(p->next)
{
//p=p->next;
printf("%c ",p->next->data);//由于前面是getchar（），所以%c
//printf(" ");
p=p->next;
}
//printf("display调用结束\n");
}
删除单链表中第一个最大元素
//删除单链表中第一个最大元素
void delmaxnode(LinkList L)
{
Node *p=L->next,*pre=L,*maxp=p,*maxpre=pre;
while (p!=NULL)
{
if (maxp->data<p->data) //若找到一个更大的节点
{
maxp=p; //更改maxp
maxpre=pre; //更改maxpre
}
pre=p; //p、pre同步后移一个节点
p=p->next;
}
maxpre->next=maxp->next; //删除*maxp节点
free(maxp); //释放*maxp节点
}
删除重复节点
//删除重复节点
void del_repeated_node(LinkList L)
{
Node *k = L->next;
Node *pre_p=k;
Node *p=pre_p->next;
//遍历单链表的每一个节点
while(k && k->next != NULL)
{ //判断k后面的节点是否与k的值域重复，如果重复，则删去。
while(p)
{
if(k->data == p->data)
{
//删除重复的p节点
Node* temp = p;
pre_p ->next= p->next;
p = pre_p->next;
free(temp);
}
else
{
pre_p = pre_p->next;
p = pre_p->next;
}
}
k = k->next;
pre_p=k;
p = pre_p->next;
}
}
主函数
用一种“菜单”的形式使单链表的操作更加地清晰地展示出来。
int main()
{
LinkList L;
ElemType e,x;
int i=1,k,j;
Init_LinkList(&L);
printf("尾插法建立单链表如下：\n(输入规则：一个数字一个数字地输入，不用加空格和回车，空格和回车也会被当作是一个字符，结束的时候请输入'$')\n");
CreateFromTail(&L);
//system("cls");
while(i)//保证一直进行
{
printf("\n现在的链表: ");
Display_LinkList(&L);
printf("\n-------------------------------------\n");
printf(" Main Menu \n");
printf(" 1 删除第一个最大元素 \n");
printf(" 2 删除重复的结点 \n");
printf(" 3 清屏 \n");
printf(" 0 结束程序 \n");
printf("--------------------------------------\n");
printf("请输入你选择的菜单号<1, 2, 3, 0>:\n");
scanf("%d",&i);
switch(i)
{
case 1:
delmaxnode(&L);
break;
case 2:
del_repeated_node(&L);
break;
case 3:
system("cls");
break;
case 0:
exit(0);
break;
default:
printf("输入有误~");
}
}
return 0;
}
实验结果
两个最大的数在不同位置，实现了删除第一个，删除重复结点也顺利实现了。
最后附上完整的代码
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
//用typedef 给int定义个名字为ElemType，意思是表中元素的type
typedef int ElemType;
typedef struct Node
{
ElemType data;
struct Node * next;
}Node,* LinkList;
//初始化单链表
void Init_LinkList(LinkList *L)
{
*L=(LinkList)malloc(sizeof(Node));//建立头结点
(*L)->next=NULL;//建立空的单链表
}
//删除单链表中第一个最大元素
void delmaxnode(LinkList L)
{
Node *p=L->next,*pre=L,*maxp=p,*maxpre=pre;
while (p!=NULL)
{
if (maxp->data<p->data) //若找到一个更大的节点
{
maxp=p; //更改maxp
maxpre=pre; //更改maxpre
}
pre=p; //p、pre同步后移一个节点
p=p->next;
}
maxpre->next=maxp->next; //删除*maxp节点
free(maxp); //释放*maxp节点
}
//删除重复节点
void del_repeated_node(LinkList L)
{
Node *k = L->next;
Node *pre_p=k;
Node *p=pre_p->next;
//遍历单链表的每一个节点
while(k && k->next != NULL)
{ //判断k后面的节点是否与k的值域重复，如果重复，则删去。
while(p)
{
if(k->data == p->data)
{
//删除重复的p节点
Node* temp = p;
pre_p ->next= p->next;
p = pre_p->next;
free(temp);
}
else
{
pre_p = pre_p->next;
p = pre_p->next;
}
}
k = k->next;
pre_p=k;
p = pre_p->next;
}
}
//尾插法建表
void CreateFromTail(LinkList L)
{
Node *r,*s;//一个动态的尾指针r
int flag=1;
r=L;
char c;
while(flag)
{
c=getchar();
// printf(" ");
if(c!='$')
{
s=(Node*)malloc(sizeof(Node));
s->data=(int)c;
r->next=s;
r=s;//r始终是在最后的
}
else
{
flag=0;
r->next=NULL;//将最后一个结点的next链域设为空，表示链表的结束
}
}
}
//display单链表
void Display_LinkList(LinkList L)
{
//printf("display调用开始\n");
Node *p;
ElemType s;
p=L;
while(p->next)
{
//p=p->next;
printf("%c ",p->next->data);
//printf(" ");
p=p->next;
}
//printf("display调用结束\n");
}
int main()
{
LinkList L;
ElemType e,x;
int i=1,k,j;
Init_LinkList(&L);
printf("尾插法建立单链表如下：\n(输入规则：一个数字一个数字地输入，不用加空格和回车，空格和回车也会被当作是一个字符，结束的时候请输入'$')\n");
CreateFromTail(&L);
//system("cls");
while(i)//保证一直进行
{
printf("\n现在的链表: ");
Display_LinkList(&L);
printf("\n-------------------------------------\n");
printf(" Main Menu \n");
printf(" 1 删除第一个最大元素 \n");
printf(" 2 删除重复的结点 \n");
printf(" 3 清屏 \n");
printf(" 0 结束程序 \n");
printf("--------------------------------------\n");
printf("请输入你选择的菜单号<1, 2, 3, 0>:\n");
scanf("%d",&i);
switch(i)
{
case 1:
delmaxnode(&L);
break;
case 2:
del_repeated_node(&L);
break;
case 3:
system("cls");
break;
case 0:
exit(0);
break;
default:
printf("输入有误~");
}
}
return 0;
}