CPJ Linux Dev Engineer

3-1-1-2双向链表

2017-08-16

WELCOME TO READ ME

头文件以及宏

#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<math.h> /* floor(),ceil(),abs() */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef int ElemType;
typedef struct DuLNode
{
  ElemType data;
  struct DuLNode *prior,*next;
}DuLNode,*DuLinkList;

一 初始化双向链表

 /* bo2-5.c 双链循环线性表(存储结构由c2-4.h定义)的基本操作(14个) */
Status InitList(DuLinkList *L) 
{ /* 产生空的双向循环链表L */
  *L=(DuLinkList)malloc(sizeof(DuLNode));
  if(*L)
  {
    (*L)->next=(*L)->prior=*L;
    return OK;                  
  }
  else
    return OVERFLOW;
}

二 查找链表长度

int ListLength(DuLinkList L)
{ /* 初始条件:L已存在。操作结果:返回L中数据元素个数 */
  int i=0;
  DuLinkList p=L->next; /* p指向第一个结点 */
  while(p!=L) /* p没到表头 */
  {
    i++;
    p=p->next;
  }
  return i;
}

三 查找第i个元素位置

DuLinkList GetElemP(DuLinkList L,int i) /* 另加 */
{ /* 在双向链表L中返回第i个元素的位置指针*/
  int j;
  DuLinkList p=L;
  for(j=1;j<=i;j++)
    p=p->next;
  return p;
}

--
Status GetElem(DuLinkList L,int i,ElemType *e) 
{ /* 当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR */
  int j=1; /* j为计数器 */
  DuLinkList p=L->next; /* p指向第一个结点 */
  while(p!=L&&j<i) /* 顺指针向后查找,直到p指向第i个元素或p指向头结点 */
  {
    p=p->next;
    j++;
  }
  if(p==L||j>i) /* 第i个元素不存在 */
    return ERROR;
  *e=p->data; /* 取第i个元素 */  
  return OK; 
}

四 i位置前插入元素e

Status ListInsert(DuLinkList L,int i,ElemType e)
{ /* 在带头结点的双链循环线性表L中第i个位置之前插入元素e,i的合法值为1≤i≤表长+1 */
  DuLinkList p,s;
  if(i<1||i>ListLength(L)+1) /* i值不合法 */
    return ERROR;
  p=GetElemP(L,i-1); /* 在L中确定第i-1个元素的位置指针p */
  if(!p) /* p=NULL,即第i-1个元素不存在 */
    return ERROR;
  s=(DuLinkList)malloc(sizeof(DuLNode));
  if(!s)
    return OVERFLOW;
  s->data=e; /* 在第i-1个元素之后插入 */
  s->prior=p;
  s->next=p->next;
  p->next->prior=s;
  p->next=s;
  return OK;
}

五 visit遍历每个元素

void ListTraverse(DuLinkList L,void(*visit)(ElemType))
{ /* 由双链循环线性表L的头结点出发,正序对每个数据元素调用函数visit() */
  DuLinkList p=L->next; /* p指向头结点 */
  while(p!=L)
  {
    visit(p->data);               
    p=p->next;
  }
  printf("\n");
}
void vd(ElemType c) /* ListTraverse()调用的函数(类型一致) */
{
  printf("%d ",c);
}
//for example:
// ListTraverse(L,vd); /* 正序输出 */

六 删除第i个元素

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

七 判断是否为空

  Status ListEmpty(DuLinkList L)
 { /* 初始条件:线性表L已存在。操作结果:若L为空表,则返回TRUE,否则返回FALSE */
   if(L->next==L&&L->prior==L)
    ¦return TRUE;
   else
    ¦return FALSE;
 }

八 双链表的反转

PNode DList_Reverse2(DList *L) 
{
    PNode p = L->head,pre = NULL;
    printf("lynn tast:PNode p = L->head,pre = NULL;\n");
    if(p == NULL) return pre;
    printf("lynn tast:PNode p != NULL;\n");
    while(p != NULL)
    {   
    ¦   PNode temp = p->next;
    ¦   p->previous = temp;
    ¦   p->next = pre;
    ¦   pre = p;
    ¦   p = temp;
    } 
   return pre; 
}

Similar Posts

上一篇 3-1-1-1单链表

Comments