//* * * * * * * * * * * * * * * * * * * * * * * *
//*CHAPTER          :2  (2_3)                   *
//*PROGRAM          :雙向鏈表                   *
//*CONTENT          :生成,插入,刪除,定位,查找   *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include <conio.h>
#include <dos.h>
#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(struct dunode)//定義雙向鏈表一個(gè)節(jié)點(diǎn)的長(zhǎng)度
enum BOOL{False,True};    //定義BOOL型
typedef struct dunode     //定義雙向鏈表的結(jié)構(gòu)
{char data;       //數(shù)據(jù)域
 struct dunode *prior,*next;//前項(xiàng)指針和后項(xiàng)指針
} *DuLink;

void CreatDuLink(DuLink &);   //逆序法建立一個(gè)雙向鏈表
DuLink DuLinkFind(DuLink,int);  //按序號(hào)查找
BOOL DuLinkInsert(DuLink,char,int);   //插入
void Insafter(DuLink,char);  //插入一個(gè)元素到指定元素之后
BOOL DuLinkDelete(DuLink,int);        //刪除一個(gè)元素
void DuLinkPrint(DuLink);             //顯示所有元素

void main()
{DuLink DL;
 int loc,flag=1;
 char j,ch;
 BOOL temp;
 textbackground(3); //設(shè)置屏幕顏色
 textcolor(15);
 clrscr();
 //---------------------程序解說-----------------------
 printf("本程序?qū)崿F(xiàn)雙向鏈表結(jié)構(gòu)的線性表的操作。\n");
 printf("可以進(jìn)行插入，刪除，定位，查找等操作。\n");
 //----------------------------------------------------
 printf("請(qǐng)輸入初始時(shí)雙向鏈表的各元素(以#結(jié)束):\n例如:abcdefg#\n");
 CreatDuLink(DL);              //建立一個(gè)雙向鏈表
 DuLinkPrint(DL);              //顯示
 while(flag)
    { printf("請(qǐng)選擇:\n");
      printf("1.顯示所有元素\n");
      printf("2.刪除一個(gè)元素\n");
      printf("3.插入一個(gè)元素\n");
      printf("4.退出程序    \n");
      scanf(" %c",&j);
      switch(j)
	{case '1':DuLinkPrint(DL);  //顯示
		  break;
	 case '2':printf("請(qǐng)輸入要?jiǎng)h除的元素所在位置:");
		  scanf("%d",&loc);          //輸入要?jiǎng)h除元素的序號(hào)
		  temp=DuLinkDelete(DL,loc); //刪除
		  if(temp==False) printf("刪除失敗!\n"); //刪除失敗
		  else printf("刪除成功!\n");  //成功刪除
		  DuLinkPrint(DL);
		  break;
	 case '3':printf("請(qǐng)輸入要插入的元素(一個(gè)字符)和插入位置:\n");
		  printf("格式：字符，位置；例如：a,3\n");
		  scanf(" %c,%d",&ch,&loc);      //輸入要插入的元素和位置
		  temp=DuLinkInsert(DL,ch,loc);  //插入
		  if(temp==False) printf("插入失敗!\n"); //插入失敗
		  else printf("插入成功!\n");  //插入成功		  
                  DuLinkPrint(DL);
		  break;
	 default:flag=0;printf("程序結(jié)束，按任意鍵退出!\n");
	}
    }
getch();
}
void CreatDuLink(DuLink &head)
{//生成一個(gè)以head為頭針的雙向鏈表
 DuLink p;
 char ch;
 p=head=(DuLink)malloc(LEN);//生成頭結(jié)點(diǎn)
 head->prior=head->next=head;//頭結(jié)點(diǎn)的前向和后向指針都指向自己
 scanf(" %c",&ch);
 while(ch!='#')              //依次插入其后的節(jié)點(diǎn)到頭節(jié)點(diǎn)之后
    {Insafter(p,ch);
     scanf("%c",&ch);
   }
 }

DuLink DuLinkFind(DuLink head,int location)
{//在雙向鏈表中查找位置為location的元素，并返回其指針，
 //若沒有找到，返回指針為NULL
 int k;
 DuLink p;
 p=head;
 k=0;
 while((k<location)&&(p->next!=head))//p指針向后移直到
    {k=k+1;p=p->next;}               //所找位置或表尾
 if(k==location||k==0)        //找到該位置，返回其指針
    return p;
 else return(NULL);     //該位置不存在，返回NULL
}

BOOL DuLinkInsert(DuLink head,char e,int loc)
{//在雙向鏈表的第i個(gè)位置插入元素e,成功返回True，失敗返回False
 DuLink p;
 if((p=DuLinkFind(head,loc-1))!=NULL)     //如果該位置存在，插入該元素
     {Insafter(p,e);return True;}
 else return False;
}
void Insafter(DuLink pi,char ch)
{//在雙向鏈表的一個(gè)指定節(jié)點(diǎn)之后插入一個(gè)新節(jié)點(diǎn)
 DuLink s;                      
 s=(DuLink)malloc(LEN);         //生成一個(gè)新節(jié)點(diǎn)
 s->data=ch;                    //賦值
 s->next=pi->next;              //插入
 pi->next->prior=s;
 pi->next=s;
 s->prior=pi;
}
BOOL DuLinkDelete(DuLink head,int loc)
{//在雙向鏈表中刪除位置為loc的元素，成功返回True，失敗返回False
 DuLink p;
 p=DuLinkFind(head,loc);         //尋找該元素的地址
 if(p==NULL) return False;       //如果為NULL,該序號(hào)不存在
 else {p->prior->next=p->next;   //刪除該節(jié)點(diǎn)
       p->next->prior=p->prior;
       free(p);
       return True;              //釋放所刪節(jié)點(diǎn)的空間
       }
}

void DuLinkPrint(DuLink head)       
{//顯示雙向鏈表的所有節(jié)點(diǎn)
 DuLink q;
 q=head->next;
 if(head->next==head) printf("雙向鏈表為空!\n");
 else{printf("雙向鏈表所有元素:");
      while(q!=head)
	 {printf("%c ",q->data);q=q->next;}
      printf("\n");
     }
}