线性表的双向链表存储结构
typedef struct DuLNode{ElemType data;DuLNode *prior, *next;}DuLNode, *DuLinkList;
带有头结点的双向循环链表的14个基本操作
void InitList(DuLinkList &L){L = (DuLinkList)malloc(sizeof(DuLNode));if (!L)exit(OVERFLOW);L->next = L->prior = L;}void ClearList(DuLinkList &L){DuLinkList p = L->next;//p指向第1个结点while (p != L){//p未指向头结点p = p->next;//p指向下一个结点free(p->prior);//释放p的前驱结点}L->next = L->prior = L;//头结点的两个指针域均指向自身}void DestroyList(DuLinkList &L){ClearList(L);free(L);L = NULL;}Status ListEmpty(DuLinkList L){if (L->next == L && L->prior == L)return TRUE;;}int ListLength(DuLinkList L){DuLinkList p = L->next;//p指向第1个结点int i = 0;while (p != L)//p未指向头结点{i++;//计数器+1p = p->next;//p指向下一个结点}return i;}Status GetElem(DuLinkList L, int i, ElemType &e){int j = 1;//初始化，j为计数器，初值为1DuLinkList p = L->next;//p指向第1个结点while (p != L && j < i)//顺时针向后查找,直到p指向第i个元素或p指向头结点{j++;p = p->next;}if (p == L || j > i)return ERROR;//第i个元素不存在e = p->data;return OK;}int LocateElem(DuLinkList L, ElemType e, Status(*compare)(ElemType, ElemType)){int i = 0;//计数器初值为0DuLinkList p = L->next;//p指向第1个元素while (p!=L)//p未指向头结点{i++;i;//返回其位序p = p->next;//p指向下一个结点}return 0;//满足关系的数据元素不存在}Status PriorElem(DuLinkList L, ElemType cur_e, ElemType &pre_e){DuLinkList q, p (pcur_e){//p指向值为cur_e的结点pre_e OK;}p = p->next;//q指向p的后继}return ERROR;}Status NextElem(DuLinkList L, ElemType cur_e, ElemType &next_e){DuLinkList p (pcur_e){//p所指结点的值为cur_enext_e OK;}p = p->next;//p指向下一个结点}return ERROR;}DuLinkList GetElemP(DuLinkList L, int i){int j;DuLinkList p i < ListLength(L)) return NULL;for (j = 1; j <= i; j++)//p指向第i个结点p = p->next;//p指向下一个结点return p;}Status ListInsert(DuLinkList L, int i, ElemType e){DuLinkList s, p;i > ListLength(L) + 1) return ERROR;p (!p) return ERROR;//p=NULL，，即第i个结点的前驱不存在（设头结点为第1个结点的前驱）s = (DuLinkList)malloc(sizeof(DuLNode));if (!s) return ERROR;//生成新结点失败返回ERRORse;//将e赋给新结点s->prior = p;//新结点的前驱为第i-1个结点s->next = p->next;//新结点的后继为第i个结点p->next->prior = s;//第i-1个结点的后继指向新结点p->next = s;//第i-1个结点的后继指向新结点return OK;}Status ListDelete(DuLinkList L, int i, ElemType &e){DuLinkList p;if (i < 1) return ERROR;//删除失败p = GetElemP(L, i);if(!p) return ERROR;//p=NULL，即第i个元素不存在e = p->data;//将第i个元素的值赋给ep->prior->next = p->next;//第i-1个结点的后继指向原第i+1个结点p->next->prior = p->prior;//原第i+1个结点的前驱指向第i-1个结点free(p);return OK;}void ListTraverse(DuLinkList L, void(*visit)(ElemType&)){DuLinkList p = L->next;//p指向首元结点while (p != L)//p不指向头结点{visit(p->data);p = p->next;}printf(“\n”);}void ListTraverseBack(DuLinkList L, void(*visit)(ElemType&)){DuLinkList p = L->prior;//p指向首元结点while (p != L)//p不指向头结点{visit(p->data);p = p->prior;}printf(“\n”);}
人要有梦想，有了梦想才会努力奋斗，
