#include<stdio.h>
#include<malloc.h>

struct Node
{ 
  char Data;
  struct Node *next;
  struct Node *pre;
};

struct Node *First;         //链表头指针
struct Node *Rear;          //链表尾指针

struct Node *Creat();       //创建新节点
void InsertFront();         //在链表头部插入新节点
void  InsertMide();          //在链表中部插入新节点
void InsertRear();          //在链表尾部插入新节点
void PrintFront();          //从头部输出链表
void PrintRear();           //从尾部输出链表
void DelFront();             //在链表头部删除一个节点
void DelMide();             //在链表中删除一个节点
void DelRear();             //在链表尾部删除一个节点

int n;  //全局变量

//---------------------------------------------------------
void main()
{
   int i=1,j;
   printf("Please input the character for creating a linklist!\n");
   printf("--------------------------------------------------\n");
   First=Creat();
   PrintFront();
   while(1)
   {
       printf("\nPlease choose the operation:     \n");
       printf("  1. Insert a character at front\n");
       printf("  2. Insert a character at Middle\n");
       printf("  3. Insert a character at rear \n");
       printf("  4. Delete a character at front\n");
       printf("  5. Delete a character at Middle\n");
       printf("  6. Delete a character at rear \n");
       printf("  7. Output the linklist at rear\n");
       printf("  0. Exit                       \n");
       scanf("%d",&j);
       if(j==1)
           InsertFront();
       else if(j==2)
           InsertMide();
       else if(j==3)
           InsertRear();
       else if(j==4)
           DelFront();
       else if(j==6)
           DelRear();
       else if(j==7)
           PrintRear();
       else if(j==5)
           DelMide();
       else 
           break;
   }
}

//--------------------------------------------------------
struct Node *Creat()   
{ 
   struct Node *head;
   struct Node *p1,*p2;
   n=0;
   p1=p2=(struct Node *)malloc(sizeof(struct Node));
   p1->next=p1->pre=NULL;
   printf("Please input the character:");
   scanf("%c",&p1->Data);
   if(p1->Data=='\n')
   {head=NULL;
   return (head);}
   else{
   while(p1->Data!='\n')
   {
       n=n+1;
       if(n==1)
           head=p2=p1; 
       else
       { 
           p2->next=p1; 
           p1->pre=p2;
       }
       p1->next=NULL;
       p2=p1;
       p1=(struct Node *)malloc(sizeof(struct Node));
       scanf("%c",&p1->Data);
   }
   Rear=p2;}
   return (head);
}

//----------------------------------------------------
void InsertFront()
{
    struct Node *p,*s;
    int k=1;
    getchar();
    while(k)
    {   
        p=First;
        s=(struct Node *)malloc(sizeof(struct Node));
        printf("Please input a new character:");
        scanf("%c",&s->Data);
        if(!First)
        {
            First=Rear=s;
            First->next=First->pre=NULL;
        }
        else
        {
           s->next=p;
           s->pre=NULL;
           p->pre=s;
           First=s;
        }
        PrintFront();
        printf("Are you want to continue(Y/N)?:");
        if(getchar()=='Y'||getchar()=='y')
            k=1;
        else
            k=0;
        getchar();
    }    
}

//-------------------------------------------------------
/*函数void InsertMide()在执行过程中有一个问题
  就是当链表中元素出现重复，而要插入的位置恰好
  在该元素前面时，链表中有一些元素会消失掉，若
  各个元素不一样，或插入位置不再重复元素的前面
  则程序运行正确，经过反复调试，目前还没有解决
  该问题。               2011-5-6*/
void InsertMide()
{
    struct Node *p,*s,*p1;
    int k=1;
    char x;
    getchar();
    while(k)
    {   
        p=First;
         printf("Please choose the character you want to insert before:");
        scanf("%c",&x);
        s=(struct Node *)malloc(sizeof(struct Node));
        printf("Please input a new character:");
        getchar();
        scanf("%c",&s->Data);
        while(p!=NULL&&p!=Rear)
        {
            p1=p->pre;
            if(p->Data==x)
            {
                if(p==First)
                {
                    p1=s;
                    p->pre=s;
                    s->next=p;
                    First=s;
                    First->pre=NULL;
                }
                else
                {
                    p1->next=s;
                    s->pre=p1;
                    p->pre=s;
                    s->next=p;         
                }
            }
            p1=p;
            p=p->next;    
        }
        if(p==Rear)
            {
                if(p->Data==x)
                {
                    p1->next=s;
                    s->pre=p1;
                    s->next=p;
                    p->pre=s;
                    Rear=p;
                    Rear->next=NULL;
                }
            }
        PrintFront();
        printf("Are you want to continue(Y/N)?:");
        if(getchar()=='Y'||getchar()=='y')
              k=1;
        else
               k=0;
        getchar();
    }
}

//---------------------------------------------------------
void InsertRear()
{
    struct Node *p,*s;
    int k=1;
    getchar();
    while(k)
    {
        p=Rear;
        s=(struct Node *)malloc(sizeof(struct Node));
        printf("Please input a new character:");
        scanf("%c",&s->Data);
        if(!Rear)
        {
            First=Rear=s;
            Rear->pre=Rear->next=NULL;
        }
        else
        {
            s->next=NULL;
            s->pre=Rear;
            p->next=s;
            Rear=s;
        }
        PrintFront();
        printf("Are you want to continue(Y/N)?:");
        if(getchar()=='Y'||getchar()=='y')
            k=1;
        else
            k=0;
        getchar();
    }
}

//------------------------------------------------------
void PrintFront()
{
    struct Node *p;
    p=First;
    printf("Output the linklist at front :");
    if(!First) 
        printf("The linklist is empty!\n");
    else
    {
        while(p!=NULL)
        {
            printf("%c ",p->Data);
            p=p->next;
        }
    }
    printf("\n");
}

//---------------------------------------------------------
void PrintRear()
{
    struct Node *p;
    p=Rear;
    printf("Output the linklist at Rear  :");
    if(!First)
        printf("The linklist is empty!\n");
    else
    {
        while(p!=NULL)
        {
            printf("%c ",p->Data);
            p=p->pre;
        }
    }
    printf("\n");
}

//-----------------------------------------------------
void DelFront()
{
    
    int k=1;
    while(k)
    {
        struct Node *p;
        p=First;
        if(First==Rear)
        {
            
            printf("\n%c is deleted!\n",p->Data);
            First=Rear=NULL;
            free(p); 
            PrintFront();
            break;
        }
        if(First!=Rear)
        {
            printf("\n%c is deleted!\n",p->Data);
            First=p->next;
            First->pre=NULL;
            free(p); 
            PrintFront();
        }
        
        printf("Are you want to continue(Y/N)?:");
        if(getchar()=='Y'||getchar()=='y')
            k=1;
        else
            k=0;
        
    }
}

//----------------------------------------------------
void DelMide()
{
    struct Node *p,*p1;
    int k=1;
    char x;
    getchar();
    
    while(k)
    {
        p=First;
       
        printf("Please choose the character you want to delete:");
        scanf("%c",&x);
        while(p!=NULL&&p!=Rear)
        {
            p1=p->pre;
            if(p->Data==x)
            {  
                if(p==First)
                {
                    p1=p->next;
                    First=p1;
                    First->pre=NULL;
                }
                else
                {

                   (p->next)->pre=p1;
                   p1->next=p->next;
                }
            }
            p1=p;
            p=p->next;
        }
        if(p==Rear)
            if(p->Data==x)
            {
                if(Rear==First)
                {
                    Rear=First=NULL;
                    PrintFront();
                    break;
                }
                else
                {
                    Rear=Rear->pre;
                    Rear->next=NULL;
                }
            }
        PrintFront();
        printf("Are you want to continue(Y/N)?:");
        if(getchar()=='Y'||getchar()=='y')
            k=1;
        else
            k=0;
        getchar();
    }
}

//-----------------------------------------------------
void DelRear()
{
    int k=1;
    while(k)
    {
        struct Node *p;
        p=Rear;
        if(First==Rear)
        {
            
            printf("\n%c is deleted!\n",p->Data);
            First=Rear=NULL;
            free(p); 
            PrintFront();
            break;
        }
        if(First!=Rear)
        {
            printf("\n%c is deleted!\n",p->Data);
            Rear=p->pre;
            Rear->next=NULL;
            free(p);
            PrintFront();
        }
        else
            printf("The linklist is empty!\n");
        printf("Are you want to continue(Y/N)?:");
        if(getchar()=='Y'||getchar()=='y')
            k=1;
        else
            k=0;
    }
}

存在问题如注释处所写， 其他部分没什么问题，

帮看看啊。。。

[ 本帖最后由 bccn_2012 于 2011-6-7 16:40 编辑 ]

来个 给解决啊？？？

你那里出问题了 你说出来  这么长的代码谁愿意看啊

while(p!=NULL&&p!=Rear)      // 问题就在这个 while 循环。这样写的话，你给定的元素有可能会被重复的“插入”。
{                            // 而重复“插入”时，由于 s 指向的一直是同一个元素，所以程序“貌似”将 s 指向的这一元素用重新插入了一次。
    p1=p->pre;               // 但是，由于第一次插入的时候，s 的前驱元素的 next 已经指向了 s，而重复插入后，s 的 next 元素有指向了重复
    if(p->Data==x)           // 出现的搜索关键字元素，所以，从 s 第一次被插入的位置到 s 最后一次被插入的位置之间的元素，自然就从链表里
    {                        // 消失了，随之而来的也就是内存泄露~
        if(p==First)
        {
            p1=s;
            p->pre=s;
            s->next=p;
            First=s;
            First->pre=NULL;
        }
        else
        {
            p1->next=s;
            s->pre=p1;
            p->pre=s;
            s->next=p;
        }
    }
    p1=p;
    p=p->next;
}

//改成下面这样：

while(p != Rear && p->Data != x)
{
    p1=p;
    p=p->next;
}
if(p==First)
{
    p1=s;
    p->pre=s;
    s->next=p;
    First=s;
    First->pre=NULL;
} else {
    p1->next=s;
    s->pre=p1;
    p->pre=s;
    s->next=p;
}

[ 本帖最后由 voidx 于 2011-6-7 17:08 编辑 ]

首先输入几个字符 （这里是 1 2 3 1）
选择2 ：在链表中间插入字符；
选择要在哪个字符前插入（这里选择 1）
结果显示：1 1 （而本来想要的结果是 1 1 2 3 1 1）

不知道这样讲明白么？

我就是想要在指定的字符前都插入一个字符，
写的时候都想得晕了。

那你得插入过一个之后再重新给 s 分配空间等等等等滴

改成这样只能在第一个 指定字符前插入啊， 但是我想在同一个字符前都插入？

我楼上说了啊~

我明白了