dul.cpp

双向链表的vc++实现 是在命令行下的双向链表

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


typedef struct DuLNode{
	ElemType data;
	struct DuLNode  *prior;
	struct DuLNode  *next;


}DuLNode, *DuLinkList;



DuLinkList GetElemP_DuL(DuLinkList va, int i) {  
  // L为带头结点的单链表的头指针。
  // 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
  DuLinkList p;
  p=(DuLinkList )malloc(sizeof(DuLinkList));
  p = va->next;   
  int j = 1;  // 初始化，p指向第一个结点，j为计数器
  while (p!=va && j<i) { //顺指针向后查找，直到p指向第i个元素或p为空
    p = p->next;
    ++j;
  }
  if (p==va && j<i) return NULL;  // 第i个元素不存在
  else return p;
} // GetElem_L

Status ListInsert_DuL(DuLinkList &L, int i, ElemType e) { //算法2.18
  // 在带头结点的双链循环线性表L的第i个元素之前插入元素e，
  // i的合法值为1≤i≤表长+1。
  DuLinkList p,s;
  p=(DuLinkList )malloc(sizeof(DuLinkList));

  if (!(p = GetElemP_DuL(L, i)))  // 在L中确定第i个元素的位置指针p
    return ERROR;                 // p=NULL, 即第i个元素不存在
  if (!(s = (DuLinkList)malloc(sizeof(DuLinkList))))
    return ERROR;
  s->data = e;
  s->prior = p->prior;
  p->prior->next = s;
  s->next = p;
  p->prior = s;
  return OK;
} // ListInsert_DuL


Status ListDelete_DuL(DuLinkList &L, int i,ElemType &e) {//算法2.19
  // 删除带头结点的双链循环线性表L的第i个元素，i的合法值为1≤i≤表长
   DuLinkList p;
   p=(DuLinkList )malloc(sizeof(DuLinkList));
  if (!(p = GetElemP_DuL(L, i)))  // 在L中确定第i个元素的位置指针p
    return ERROR;                 // p=NULL, 即第i个元素不存在
  e = p->data;
  p->prior->next = p->next;
  p->next->prior = p->prior;
  //free(p);    
  return OK;
} // ListDelete_DuL


void main()
{
	int e=0;
	int order=0;
	int length=5;
	DuLinkList L;
	DuLinkList p;
	DuLinkList q;
    ElemType a;
	int i;
	
	L=(DuLinkList )malloc(sizeof(DuLinkList));
	L->next=L;
	L->prior=L;
  	p=(DuLinkList )malloc(sizeof(DuLinkList));
    q=(DuLinkList )malloc(sizeof(DuLinkList));

     printf("1.建立一个有序的带表头结点的双链表\n");
	 printf("2.双向遍历该双链表；\n");
	 printf("3.按位置号查找该双链表\n");
	 printf("4.按结点值查找该双链表\n");
	 printf("5.逆置该双链表\n");
	 printf("6.插入一元素\n");
	 printf("7.删除指定位置号\n");
	 printf("8.退出\n");
	 printf("输入第一条选项\n");
	 while(order!=8)
	 {
     scanf("%d",&order);
	 switch(order)
	 {
	 case 1:    
		        for(i=1;i<length+1;i++)
				{
		           printf("input ");
		           scanf("%d",&e);
		           ListInsert_DuL(L, i, e);

				};
		        printf("输入下一条选项");
		        break;

	 case 2:    for(i=1;i<length+1;i++)
				{
	               p = GetElemP_DuL(L, i); // 在L中确定第i个元素的位置指针p
			       printf("%d\n",p->data);
				}
                printf("\n");
                for(i=length;i>0;i--)
				{
	               p = GetElemP_DuL(L, i); // 在L中确定第i个元素的位置指针p
			       printf("%d\n",p->data);
				};

				printf("输入下一条选项");
				break;

	 case 3:    printf("输入位置号\n");
		        scanf("%d",&i);
				p = GetElemP_DuL(L, i); // 在L中确定第i个元素的位置指针p
			    printf("%d位置号上为%d\n",i,p->data);
				printf("输入下一条选项");
				
				break;

	 case 4:    printf("输入节点值\n");
		        scanf("%d",&e);
		        for(i=1;i<length+1;i++)
				{
	               p = GetElemP_DuL(L, i); // 在L中确定第i个元素的位置指针p
				   if(e==p->data)
					   printf("该节点在%d位置\n",i);
				   else
                       printf("error");
				} 
				
				printf("输入下一条选项");
				break;

     case 5:   

			   for(i=1;i<length+1;i++)
			   {
				   
				   q->next=L->next;
                   L->next=L->prior;
				   L->prior=q->next;
				   q=L;
				   L=L->next;
				   L->prior=q;
				   
			   }

			  
			/*	whiel
                while(L->prior!=L)
				{
					q=L->prior;
					q->prior->next = q->next;
					q->next->prior = q->prior;

					p->prior->next=q;
					q->prior=p->prior;
					p->prior=q;
					q->next=p;
				}*/


				 for(i=1;i<length+1;i++)
				{
	               p = GetElemP_DuL(L, i); // 在L中确定第i个元素的位置指针p
			       printf("%d\n",p->data);
				}

                printf("输入下一条选项");
		        break;

     case 6:   printf("输入位置号\n");
		       scanf("%d",&i);
		       printf("输入值\n");
	           scanf("%d",&e);
               ListInsert_DuL(L, i, e);
			   length++;
			   printf("输入下一条选项");
			   break;

	 case 7:   printf("输入位置号\n");
		       scanf("%d",&i);
               ListDelete_DuL(L,i,a);
			   length--;
			   printf("输入下一条选项");
			   break;

     case 8:   printf("退出\n");

	 default:  printf("ERROR\n");		   
	 }
	 
     }
	 
}