dul_list.rar_C 双向链表_vc list_双向链表

#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"); } } }