文章目录
1.删除链表中的重复元素
前一个与后一个比较，相同就删除结点，并释放内存。
void DeleteEqual(PNODE &pHead){ //删除链表中的重复元素
PNODE p,q,prev;
if (p=pHead->next){
prev=p;
p=p->next;
}
while (p){
if (p->data==prev->data){
q=p;
p=p->next;
prev->next=p;
free(q);
}
else
{
prev=p;
p=p->next;
}
}
}
运行结果：
2.删除递增有序链表中大于min，小于max的元素
先找到两个前驱，释放中间结点，并且将链表重新链起来。
void DeleteSelect(PNODE &pHead,int min,int max){ //删除递增有序链表中大于min，小于max的元素
PNODE p=pHead,minPrev,maxPrev;
int flag=0;
while (p->next){
if(p->next->data>min&&!flag){
minPrev=p;
flag=1;
}
if(p->next->data>=max){
maxPrev=p;
break;
}
p=p->next;
}
PNODE temp,start;
start=minPrev->next;
while(start->data!=maxPrev->data){
temp=start;
start=start->next;
free(temp);
temp=NULL;
}
minPrev->next=maxPrev->next;
free(maxPrev);
maxPrev=NULL;
}
运行结果：
3.逆置链表
第一种策略：
void LinkListReverse(PNODE &L){ //逆置链表，元素个数要大于2
PNODE p,q,s;
p=L->next;
q=p->next;
s=q->next;
p->next=NULL;
while(s->next){
q->next=p;
p=q;
q=s;
s=s->next;
}
q->next=p;
s->next=q;
L->next=s;
}
第二种策略
void LinkListReverse2(PNODE &L){ //逆置链表
PNODE p,s,prev;
if (p=L->next){
prev=p;
s=p;
p=p->next;
prev->next=NULL;
}
while(p){
s=p;
p=p->next;
s->next=prev;
prev=s;
}
L->next=s;
}
运行结果：
完整代码：
#include<iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;
typedef struct Node//结点
{
int data;//数据域
struct Node *next;//指针域
}NODE, *PNODE;//NODE等价于struct Student st||PNODE等价于struct Node *next
PNODE InputStudent(void)
{
int len;//学生的人数
NODE stu;
PNODE pHead = (PNODE)malloc(sizeof(NODE));//定义一个头结点并且为头结点分配内存
if(NULL == pHead) //判断内存是否为空
{
printf("内存分配失败,程序终止!\n");
exit(-1);
}
PNODE pTail = pHead;//定义一个指向头结点的指针
pTail->next = NULL;//清空指针域
printf("请输入个数:");
scanf("%d",&len);
for(int i=0; i<len; i++)
{
printf("请输入第%d个:\n", i+1);
cin>>stu.data;
PNODE pNew = (PNODE)malloc(sizeof(NODE)); //为新节点分配内存
if(NULL == pNew) //判断内存是否为空
{
printf("内存分配失败,程序终止!\n");
exit(-1);
}
pNew->data = stu.data;//初始化结点的数据域
pTail->next = pNew;//将新结点挂到老结点后
pNew->next = NULL;//清空新结点的指针域
pTail = pNew;//将pTail移到新结点上
}
return pHead;
}
void OutputStudent(PNODE pHead)//输出学生信息
{
PNODE p = pHead->next;//定义一个指针用于遍历学生信息
printf("\n数据如下:\n");
while(NULL != p)
{
printf("%d ", p->data);
p = p->next;
}
}
void DeleteEqual(PNODE &pHead){ //删除链表中的重复元素
PNODE p,q,prev;
if (p=pHead->next){
prev=p;
p=p->next;
}
while (p){
if (p->data==prev->data){
q=p;
p=p->next;
prev->next=p;
free(q);
}
else
{
prev=p;
p=p->next;
}
}
}
void DeleteSelect(PNODE &pHead,int min,int max){ //删除递增有序链表中大于min，小于max的元素
PNODE p=pHead,minPrev,maxPrev;
int flag=0;
while (p->next){
if(p->next->data>min&&!flag){
minPrev=p;
flag=1;
}
if(p->next->data>=max){
maxPrev=p;
break;
}
p=p->next;
}
PNODE temp,start;
start=minPrev->next;
while(start->data!=maxPrev->data){
temp=start;
start=start->next;
free(temp);
temp=NULL;
}
minPrev->next=maxPrev->next;
free(maxPrev);
maxPrev=NULL;
}
void LinkListReverse(PNODE &L){ //逆置链表
PNODE p,q,s;
p=L->next;
q=p->next;
s=q->next;
p->next=NULL;
while(s->next){
q->next=p;
p=q;
q=s;
s=s->next;
}
q->next=p;
s->next=q;
L->next=s;
}
void LinkListReverse2(PNODE &L){ //逆置链表
PNODE p,s,prev;
if (p=L->next){
prev=p;
s=p;
p=p->next;
prev->next=NULL;
}
while(p){
s=p;
p=p->next;
s->next=prev;
prev=s;
}
L->next=s;
}
int main(){
PNODE L= InputStudent();
cout<<endl<<"输入的数据如下:";
OutputStudent(L);
// DeleteEqual(L);
// cout<<endl<<"删除后:";
// OutputStudent(L);
// LinkListReverse2(L);
// cout<<endl<<"逆置后:";
// OutputStudent(L);
DeleteSelect(L,2,10);
cout<<endl<<"删除后:";
OutputStudent(L);
return 0;
}