单链表的有关问题

2012-12-14

单链表的问题设计算法：将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号

单链表的问题
设计算法：将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，B表中含有原表中序号为偶数的元素，且保持其相对顺序。
我写了一个程序，可是运行错误，好像内存溢出。请高手指教。谢谢！
#include<stdio.h>
#define uint unsigned int
#define uchar unsigned char
#define N 10           //N为链表中数据元素的个数

struct node
{
       int data;
       struct node *next;
};
typedef struct node NODE;
NODE *head,*s;
NODE *p1;
NODE *A,*B;
NODE *r,*p,*q;

NODE *creatlink2()
{

     NODE *p;
     int num;
     head=(NODE *)malloc(sizeof(NODE));
     scanf("%d",&num);
     p=head;
     while(num!=0)
     {
          s=(NODE *)malloc(sizeof(NODE));
          s->data=num;
          p->next=s;
          p=s;
          scanf("%d",&num);
     }
     p->next=NULL;
     return head;
}

int length()
{
    NODE *p;
    int j;
    p=head;
    j=0;
    while(p!=NULL)
    {
         p=p->next;
         j++;
    }
    return (j-1);
}
void disA()
{

     B=(NODE *)malloc(sizeof(NODE));     //建立单链表B的头结点
     r=B;
     p1=B;

     p=head->next;

     while((p!=NULL)&&(p->next!=NULL))
     {
          //r=(NODE *)malloc(sizeof(NODE));
          q=p->next;
          p->next=q->next;
          r->next=q;
          r=q;
          p=p->next;
     }
     r->next=NULL;
     p->next=NULL;
}
int main()
{
    uchar i;
    int k;
    creatlink2();
    /*for(i=0;i<9;i++)
    {
        head=head->next;
        printf("%d\n",head->data);
    }*/
    k=length();
    printf("%d\n",k);
    disA();

    getchar();
    getchar();

    return 0;

}

[最优解释]

void disA()
你想用這個函數來拆分A鏈表嗎？

給你設計一個新的函數接口:
NODE* displace(NODE* A);
返回的是B鏈表，當然，A鏈表也被修改為含有原表中序号为奇数的元素了。

過一會兒給你一個參考

[其他解释]
用split這個名字更好點，下面的代碼僅供參考思路, 沒測試。

NODE* split(NODE* A)
{
NODE *B=NULL;
NODE *pa=NULL; //pa is the tail of new A
NODE *pb=NULL; //pb is the tail of B
NODE *p=NULL; //pa is the head of old A
if (A) B=p=A->next;
else return B;
pa = A;
pb = B;
while (p != NULL){
NODE* pnext = p->next;
pa->next = p->next;
if (pnext) pb->next = pnext->next;
else break;

p = pnext->next;
pa = pnext;
if (p) pb = p;
}
if (pa) pa->next = NULL;
if (pb) pb->next = NULL;

return B;
}
[其他解释]
看你代码分配了节点空间都没释放，很费空间的。链表没输出。
错误我只看出一点点。
void disA()
{

     B=(NODE *)malloc(sizeof(NODE));     //建立单链表B的头结点
     r=B;
     p1=B;

     p=head->next;

     while((p!=NULL)&&(p->next!=NULL))
     {
          //r=(NODE *)malloc(sizeof(NODE));
          q=p->next;
          p->next=q->next;
          r->next=q;
          r=q;
          p=p->next;
     }
     r->next=NULL;
     p->next=NULL;
}
出错了，可能要把p->next=NULL;
改成if(p){p->next=NULL;}
举个例子：链表有两个节点1和2
p=head->next指向1，head->next->next指向2，head->next->next->next=NULL;
while((p!=NULL)&&(p->next!=NULL))条件成立进入循环
q=p->next;//q指向2
p->next=q->next;//p的下一个元素指向第三个元素即为空
p->next=q->next;
r->next=q;
r=q;
p=p->next;//注意这里即是p=NULL了
结束循环做
p->next=NULL;
即是NULL->next=NULL出错

错误只要是空指针指向空指针

没测试过。。。仅供参考


[其他解释]
幫你改好了,你自己慢慢消化吧,不懂儘管問

#include<stdio.h>
#include <stdlib.h>
#define uint unsigned int
#define uchar unsigned char
#define N 10           //N为链表中数据元素的个数

struct node
{
       int data;
       struct node *next;
};
typedef struct node NODE;
NODE *head,*s;
NODE *p1;
NODE *A,*B;
NODE *r,*p,*q;

NODE *creatlink2() 
 
{
     
     NODE *p=NULL;
     int num;
     //head=(NODE *)malloc(sizeof(NODE));
     head = NULL;
     scanf("%d",&num);
     while(num!=0)
     {
          s=(NODE *)malloc(sizeof(NODE));
          s->data=num;
          if (p) p->next=s;
          p = s;

          if (head==NULL) head = p;
          scanf("%d",&num);
     } 
     p->next=NULL;
     return head;
}
void deletelink(NODE* lnk)
{
  NODE *p = lnk;
  while (p) {
    NODE* t = p;
    p=p->next;
    free(t);
  }
}

int length()
{
    NODE *p;
    int j;
    p=head;
    j=0;
    while(p!=NULL)
    {
         p=p->next;
         j++;
    }
    return (j-1);
}
NODE* split(NODE* A)
{
  NODE *B=NULL;
  NODE *pa=NULL; //pa is the tail of new A
  NODE *pb=NULL; //pb is the tail of B
  NODE *p=NULL; //pa is the head of old A
  if (A) B=p=A->next;
  else return B;
  pa = A;
  pb = B;
  while (p != NULL){
    NODE* pnext = p->next;
    pa->next = p->next;
    if (pnext) pb->next = pnext->next;
    else break;

    p = pnext->next;
    pa = pnext;
    if (p) pb = p;
  }
  if (pa) pa->next = NULL;
  if (pb) pb->next = NULL;

  return B;
}
void prtlink(NODE*lnk)
{
  NODE *p = lnk;
  while (p) {
    printf("%d, ",p->data);
    p=p->next;
  }
}
int main()
{
    uchar i;
    int k;
    NODE*A = creatlink2();
    NODE*B=NULL;
prtlink(A);    
printf("\n");

    //k=length();
    //printf("%d\n",k);
    //disA();
    B=split(A);

    prtlink(A);
    printf("\n");
    prtlink(B);

    deletelink(A); 
 
    deletelink(B);

    getchar();
   
return 0;
}

[其他解释]
谢谢！等你的参考。

热点排行

C语言

单链表的有关问题