欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

删除单链表中多个重复值

程序员文章站 2022-06-05 18:36:00
...

题目

在不带表头结点的单链表,增加一个函数,删除表中指定的元素值 x ,假设该元素值在单链表中可能出现多次。

部分代码

删除多个重复值函数

PS:此函数有漏洞,有些情况不能实现题目所述功能,待改进。

Status del(SingleList *L, int n,int y){
    Node *q,*p,*t;
    int j,i=0;
    if(!L->n){
        return ERROR;
    }
    p=L->first;
    q=p->link;
    t=L->first;
    while(t->link!=NULL){  //p指向当前位置,判断是否等于想删除元素
        if(p->element==y){  // 相等的情况
            if(p==L->first){  // 如果p是第一位
                L->first=q;
                free(p);
                p=q;
                q=p->link;
                t=p;
            }
            else if(p->link==NULL){
                t->link=NULL;
                free(p);
                free(q);
            }
            else{  // p不是第一位
                for(j=0;j<i-1;j++){
                    t=t->link;
                }
                t->link=q;
                free(p);
                p=q;
                q=p->link;
            }
        }
        else{
            t=p;
            p=q;
            q=p->link;
            i++;
        }
    }
    return OK;
}

完整程序

#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef int Status;
#define ERROR 0
#define OK 1

typedef struct Node {
    ElemType element;
    struct Node * link;
}Node;

typedef struct {
    struct Node* first;
    int n;
}SingleList;

Status Init(SingleList *L);
Status Output(SingleList L);
Status del(SingleList *L, int mSize,int y);
Status Insert(SingleList *L, int i, ElemType x);
// Status Delete(SeqList *L,int i);
// void Destory(SeqList *L);


// 单链表的初始化
Status Init(SingleList *L) {
    L->first = NULL;
    L->n = 0;
    return OK;
}



Status del(SingleList *L, int n,int y){
    Node *q,*p,*t;
    int j,i=0;
    if(!L->n){
        return ERROR;
    }
    p=L->first;
    q=p->link;
    t=L->first;
    while(t->link!=NULL){  //p指向当前位置,判断是否等于想删除元素
        if(p->element==y){  // 相等的情况
            if(p==L->first){  // 如果p是第一位
                L->first=q;
                free(p);
                p=q;
                q=p->link;
                t=p;
            }
            else if(p->link==NULL){
                t->link=NULL;
                free(p);
                free(q);
            }
            else{  // p不是第一位
                for(j=0;j<i-1;j++){
                    t=t->link;
                }
                t->link=q;
                free(p);
                p=q;
                q=p->link;
            }
        }
        else{
            t=p;
            p=q;
            q=p->link;
            i++;
        }
    }
    return OK;
}



Status Insert(SingleList *L, int i, ElemType x) {
    Node *p, *q;
    int j;
    if (i<-1 || i>L->n - 1)
        return ERROR;
    p = L->first;
    for (j = 0; j < i; j++) {
        p = p->link;
    }
    q = (Node*)malloc(sizeof(Node));
    q->element = x;
    if (i > -1) {
        q->link = p->link;
        p->link = q;
    }
    else {
        q->link = L->first;
        L->first = q;
    }
    L->n++;
    return OK;
}


// 单链表的输出
Status Output(SingleList L) {
    Node *p;
    if (!L.n)
        return ERROR;
    p = L.first;
    while (p) {
        printf("%d ",p->element);
        p = p->link;
    }
    return OK;
}



void main()
{
    int i, x, nn,y;
    SingleList list;
    scanf("%d", &nn);
    //printf("\n");
    Init(&list);
    for (i = 0; i < nn; i++) {
        scanf("%d", &x);
        Insert(&list, i - 1, x);
    }
    Output(list);
    printf("\n");
    scanf("%d",&y);
    del(&list,nn,y);
    printf("\n");
    Output(list);
    printf("\n");
}

实验结果

成功的情况

删除单链表中多个重复值

失败的情况

删除单链表中多个重复值

版权声明:本文为博主原创文章,如有错误,恳请大家在评论区指出,在下不胜感激~如要转载注明出处即可~
本文首发于个人博客:Wonz の Blog

相关标签: 线性表