20、双向链表

  1 #define _CRT_SECURE_NO_WARNINGS
  2 
  3 #include<stdio.h>
  4 #include<stdlib.h>
  5 #include<string.h>
  6 
  7 #define OK 1
  8 #define ERROR 0
  9 #define TRUE 1
 10 #define FALSE 0
 11 
 12 typedef int ElemType;
 13 typedef int Status;
 14 typedef struct DuLNode {
 15     ElemType data;
 16     struct DuLNode *prior;
 17     struct DuLNode *next;
 18 }DuLNode,*DuLinkList;
 19 //初始化链表
 20 void Init_DuL(DuLinkList &L) {
 21     L = (DuLinkList)malloc(sizeof(DuLNode));
 22     L->data = NULL;
 23     L->next = L;
 24     L->prior = L;
 25 }
 26 //链表长度
 27 Status Length_DuL(DuLinkList &L) {
 28     DuLinkList p;
 29     p = L->next;
 30     int i=0;
 31     while (p->data != NULL) {
 32         p = p->next;
 33         i++;
 34     }
 35     return i;
 36 }
 37 
 38 DuLinkList GetElemP_DuL(DuLinkList &L, int i) {
 39     DuLinkList p = L->next;
 40     int j = 1;
 41     while (p&&j < i) {//p不为空或者计数器j还没有等于i时，循环继续
 42         p = p->next; ++j;
 43     }
 44     if (!p || j>i || i>(Length_DuL(L) + 1)) {//第i个元素不存在或i大于表长加1时，p指向空
 45         p=NULL;
 46     }
 47     if (i == Length_DuL(L) + 1) {//i等于表长加1时，p指向头结点
 48         p = L;
 49     }
 50     return p;
 51 }
 52 
 53 Status ListInsert_DuL(DuLinkList &L, int i, ElemType e) {
 54     //在带条结点的双链循环线性表L中第i个位置之前插入元素e
 55     //i的合法值为1<=i<=表长+1
 56     DuLinkList p,s;
 57     if (!(p = GetElemP_DuL(L, i)))//在L中确定插入位置指针p
 58         return ERROR;
 59     if (!(s = (DuLinkList)malloc(sizeof(DuLNode)))) {
 60         return ERROR;
 61     }
 62     s->data = e;
 63     s->prior = p->prior;
 64     p->prior->next = s;
 65     s->next = p;
 66     p->prior = s;
 67     return OK;
 68 }
 69 //删除带头结点的双链循环线性表L的第i个元素
 70 Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e) {
 71     DuLinkList p;
 72     if (!(p = GetElemP_DuL(L, i))) {//在L中确定第i个元素的位置指针
 73         return ERROR;                //p=NULL，即第i个元素不存在
 74     }
 75     e = p->data;
 76     p->prior->next = p->next;
 77     p->next->prior = p->prior;
 78     free(p);
 79     return OK;
 80 }
 81 //释放销毁
 82 void Destory_DuL(DuLinkList &L) {
 83     DuLinkList p,q;
 84     p = L->next;
 85     while (p->data != NULL) {
 86         q = p->next;
 87         p->prior->next = p->next;
 88         p->next->prior = p->prior;
 89         free(p);
 90         p = q;
 91     }
 92     free(L);
 93 }
 94 
 95 //输出打印
 96 void printf_DuL(DuLinkList &L) {
 97     DuLinkList p;
 98     p = L->next;
 99     for (int i = 0; i < Length_DuL(L); i++) {
100         printf("%d ", p->data);
101         p = p->next;
102     }
103     printf("
");
104 }
105 
106 int main()
107 {
108     DuLinkList list;
109     ElemType a[] = { 11,22,33,44,55,66 };
110     ElemType e;
111     //初始化
112     Init_DuL(list);
113     //插入数据
114     for (int i = 0; i < 6; i++) {
115         ListInsert_DuL(list, i+1, a[i]);
116     }
117     //输出
118     printf_DuL(list);
119     printf("删除前长度：%d
", Length_DuL(list));
120     //删除
121     ListDelete_DuL(list, 1, e);
122     //输出
123     printf_DuL(list);
124     printf("删除后长度：%d
", Length_DuL(list));
125     printf("删除的元素：%d
", e);
126 
127     //销毁
128     Destory_DuL(list);
129 
130     printf("
");
131     system("pause");
132     return 0;
133 }
VS2015运行结果：