注册 登录
编程论坛 数据结构与算法

小程序 运行时不对 求懂的人帮忙看一下

吕同斌 发布于 2011-11-02 09:55, 825 次点击
/*2.20②  同2.19题条件,试写一高效的算法,删除表中所
有值相同的多余元素 (使得操作后的线性表中所有元素的
值均不相同) 同时释放被删结点空间,并分析你的算法的
时间复杂度。*/

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;
typedef char ElemType;
int n;

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

Status InitList(LinkList &L)
{   //操作结果:构造一个空的链式线性表L
    L=(LinkList)malloc(sizeof(LNode));
    if(!L)
    exit(OVERFLOW);
    L->next=NULL;
    return OK;
}

void Create_List(LinkList L,int N)
{   // 输入链式线性表
    LinkList p;

    for(int i=N;i>0;i--)
    {
        p=(LinkList)malloc(sizeof(LNode));
        printf("请输入这%ld个数: ",N);
        scanf("%d",&p->data);
        p->next=L->next;
        L->next=p;
    }
}

void DispList_List(LinkList L)
{   //输出链式线性表
    LinkList p=L->next;
    while (p)
    {    printf("%ld",p->data);
         p=p->next;
    }
    printf("\n");
}  

void Purge(LinkList &L)
{   //删除表中所有值相同的多余项
    LinkList p,q;
    p=L;q=L->next;
    if(!q);
    else {p=q;
          q=q->next;}
    while(q)
       {
        if(p->data==q->data)
           {p->next=q->next;
            free(q);
            q=p->next;
           }
        else
           {p=q;
            q=q->next;
           }
       }   
}

int main()
{
    int n;
    LinkList L;
    printf("请输入数据的个数: ");
    scanf("%ld",&n);
    Create_List(L,n);
    printf("\n");
    Purge(L);
    DispList_List(L);
    return 0;
}
好像是输出有问题  求解释  THANKS
4 回复
#2
yanchina2011-11-02 17:25
楼主定义的L没初始化   算法也有问题  只有连续相邻的数才能删
#3
liao065501072011-11-04 13:53
程序代码:
#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;
typedef char ElemType;
int n;

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

Status InitList(LinkList &L)
{   //操作结果:构造一个空的链式线性表L
    L=(LinkList)malloc(sizeof(LNode));
    if(!L)
    exit(OVERFLOW);
    L->next=NULL;
    return OK;
}

void Create_List(LinkList &L,int N)//采用引用
{   // 输入链式线性表
    LinkList p;
    int j=1;

    for(int i=N;i>0;i--)
    {
        p=(LinkList)malloc(sizeof(LNode));
        printf("请输入第%ld个数: ",j++);
        scanf("%d",&p->data);
        p->next=L->next;
        L->next=p;
    }
}

void DispList_List(LinkList L)
{   //输出链式线性表
    LinkList p=L->next;
    while (p)
    {    printf("%5ld",p->data);
         p=p->next;
    }
    printf("\n");
}  

void Purge(LinkList &L)
{   //删除表中所有值相同的多余项
    LinkList p,q;
    p=L;q=L->next;
    if(!q);
    else
    {
        p=q;
        q=q->next;
    }
    while(q)
       {
        if(p->data==q->data)
           {
                p->next=q->next;
                free(q);
                q=p->next;
           }
        else
           {
                p=q;
                q=q->next;
           }
       }   
}

int main()
{
    int n;
    LinkList L;
    printf("请输入数据的个数: ");
    scanf("%ld",&n);
    InitList(L);//初始化
    Create_List(L,n);
    printf("\n");
    Purge(L);
    DispList_List(L);
    return 0;
}
#4
无名可用2011-11-04 14:22
你的算法有问题。
可以额外开哈希表,应该快些
#5
austral2012-03-30 01:32
删除那部分写多余了

精简了下
LinkList p,q,s;
  p=L;
  q=p->next;  
  while(q!=NULL)
  {
   if(q->data==p->data)
    {
     p->next=q->next;//删去q
     free(q);   
    }
    else  //p,q数据不等才执行
    p=p->next;//p,q后移
    q=p->next;
  }
1