论坛 › 数据结构与算法 › 求大神看看我这个程序那里错了

一介白书生 发表于 2013-5-15 21:22:56

求大神看看我这个程序那里错了

已知线性表的元素按递增顺序排列，并以带头结点的单链表作为存储结构。试编写一个删除表中所有值大于min并且小于max的元素的算法。
函数原型：void del(struct node *head,int min,int max);
单链表结点结构为：
struct node
{   int data;
    struct node *next;
};

Input

第一行 包含一个n，代表链表中所含元素的个数。
第二行 包含n个数，代表链表中的元素。
第三行 max 与min ( max > min )。
注意：测试数据包含多组
Output

要求删除区间内的所有元素，若不存在，则不执行任何操作。
Sample Input
5
1 2 3 4 5
2 3
6
12 5 6 4 6 9
2 4
Sample Output
1 4 5
12 5 6 6 9
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
    int data;
    struct node *next;
}Node;
Node *CreatNode()
{
    Node *p = (Node*)malloc(sizeof(Node));
    p->next = NULL;
    return p;
}
void InsertNodeElem(Node *head,int elem)
{
    Node *pCur = head,*pNew = (Node*)malloc(sizeof(Node));
    pNew->data = elem;

    pNew->next = pCur->next;
    pCur->next = pNew;
}
void del(Node *head,int min,int max)
{
    Node *pCur = head,*pTemp,*pCurrent,*pT;
       while(pCur!=NULL)
       {
         pT = pCur->next;pTemp = pT;
         if((pT==NULL) && (pCur->data >= min) && (pCur->data<=max))
         {
               free(pCur);
               break;
         }

      if(pTemp->data >= min && pTemp->data <= max)
      {
            pCurrent = pTemp;
            if(pCurrent->next==NULL)
            {
                pCur->next = NULL;
                free(pCurrent);
                break;
            }
            pCur->next = pCurrent->next;
            free(pTemp);
      }
      else
      {
            pCur = pCur->next;
      }
       }



}
void PrintNode(Node *head)
{
    Node *pCur = head->next;
    while(pCur!=NULL)
    {
      printf("%d ",pCur->data);
      pCur = pCur ->next;
    }
}
int NodeLength(Node *head)
{
    int len = 0;
    Node *pCur = head->next;
    while(pCur!=NULL)
    {
      len++;
      pCur = pCur ->next;
    }
    return len;
}
void main()
{
    Node *head = CreatNode();
    int len = 0,i = 0,elem = 0,max = 0,min = 0;
    scanf("%d",&len);
    for(i=0;i<len;i++)
    {
       scanf("%d",&elem);
       InsertNodeElem(head,elem);
    }
    scanf("%d %d",&min,&max);
    del(head,min,max);
    PrintNode(head);
}
应该是删除函数有错，

小新110 发表于 2013-5-15 21:54:16

确实是del函数有点问题

void del(Node *head,int min,int max)
{
        Node *pCur = head,*pTemp,*pCurrent,*pT;
        while(pCur!=NULL)
        {
                pT = pCur->next;pTemp = pT;
                if(pT==NULL)
                {
                        if ((pCur->data >= min) && (pCur->data<=max))
                        {
                                free(pCur);
                        }
                        break;
                }

                if(pTemp->data >= min && pTemp->data <= max)
                {
                        pCurrent = pTemp;
                        if(pCurrent->next==NULL)
                        {
                                pCur->next = NULL;
                                free(pCurrent);
                                break;
                        }
                        pCur->next = pCurrent->next;
                        free(pTemp);
                }
                else
                {
                        pCur = pCur->next;
                }
        }
}

熊文杰 发表于 2013-5-15 22:36:00

本帖最后由 熊文杰 于 2013-5-15 22:38 编辑

这个题目首先第一个要抓住的要点是
按递增顺序排列
既然是按照递增的顺序排列，那就简单了。因为顺序是排好的，
1.只要找到第一个比min大的结点，让pHead头指针指向那个结点，此结点之前的全部free掉。
2.找到最后一个比max小的结点，这个结点就是最后一个尾结点。这个结点之后的全部free掉。

充分利用递增顺序表这个规则，可以简化程序
在你的代码基础上 我加了几个函数如下。所有的代码如下通过visual stdio 2005编译运行测试成功#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
      int data;
      struct node *next;
}Node;
Node *CreatNode()
{
      Node *p = (Node*)malloc(sizeof(Node));
      p->next = NULL;
      return p;
}
void InsertNodeElem(Node *head,int elem)
{
      Node *pCur = head;
      Node* pNew = (Node*)malloc(sizeof(Node));
      pNew->data = elem;

      pNew->next = pCur->next;
      pCur->next = pNew;
}

//清除pHead开始的全部结点
void clear(Node *pHead)
{
      Node *pNode = pHead;
      Node *pFront = NULL;//指向pNode前面一个结点
      while (pNode)
      {
                pFront = pNode;
                pNode = pNode->next;
                free(pFront);
                pFront = NULL;
      }
      pHead = NULL;
}

void delMin(Node *head,int min)
{
      Node *pNode = head;
      while (head)
      {
                pNode = head->next;
                if (pNode)
                {
                        if (pNode->data > min)
                        {
                              head->next = pNode;
                              break;
                        }
                        else
                        {
                              head->next = pNode->next;
                              free(pNode);
                              pNode = NULL;
                        }
                }
      }
}

void delMax(Node *head,int max)
{
      Node *pNode = head;
      Node *pEndNode = head->next;   //指向结尾结点
      while (pEndNode)
      {
                pNode = pNode->next;

                if (pNode)
                {
                        if (pNode->data < max)
                        {
                              pEndNode = pNode;
                              continue;
                        }
                        else
                        {
                              clear(pNode);
                              pEndNode->next = NULL;
                              break;
                        }
                }
      }
}
void deleteObj(Node *head,int min,int max)
{
      delMin(head,min);
      delMax(head,max);
}

void del(Node *head,int min,int max)
{
      Node *pCur = head;
      Node *pTemp = NULL;
      Node *pCurrent = NULL;
      Node *pT = NULL;

      while(pCur!=NULL)
      {
                pT = pCur->next;
                pTemp = pT;
                if((pT==NULL) && (pCur->data >= min) && (pCur->data<=max))
                {
                        free(pCur);
                        break;
                }

                if(pTemp->data >= min && pTemp->data <= max)
                {
                        pCurrent = pTemp;
                        if(pCurrent->next==NULL)
                        {
                              pCur->next = NULL;
                              free(pCurrent);
                              break;
                        }
                        pCur->next = pCurrent->next;
                        free(pTemp);
                }
                else
                {
                        pCur = pCur->next;
                }
      }



}
void PrintNode(Node *head)
{
      Node *pCur = head->next;
      while(pCur)
      {
                printf("%d ",pCur->data);
                pCur = pCur ->next;
      }
}
int NodeLength(Node *head)
{
      int len = 0;
      Node *pCur = head->next;
      while(pCur!=NULL)
      {
                len++;
                pCur = pCur ->next;
      }
      return len;
}

int _tmain(int argc, _TCHAR* argv[])
{
      Node *head = CreatNode();
      int len = 0,i = 0,elem = 0,max = 0,min = 0;
      scanf("%d",&len);
      for(i=0;i<len;i++)
      {
                scanf("%d",&elem);
                InsertNodeElem(head,elem);
      }
      scanf("%d %d",&min,&max);

      deleteObj(head,min,max);
      PrintNode(head);
      return 0;
}

一介白书生 发表于 2013-5-16 21:49:05

小新110 发表于 2013-5-15 21:54 static/image/common/back.gif
确实是del函数有点问题

谢谢，我已经知道怎么写了

y290176346 发表于 2015-9-19 16:41:50

我是来领 鱼币的

东河 发表于 2015-9-21 15:37:11

看看

鱼C工作室.YCGZS 发表于 2015-12-7 17:09:55

好像有些标点什么的是检测不出的

查看完整版本: 求大神看看我这个程序那里错了