1 /*双向循环链表*/  2   3 #include <stdio.h>  4 #include <stdlib.h>  5 #include <time.h>  6   7 #define OK 1  8 #define ERROR 0  9 typedef int Status; 10 typedef int ElemType; 11  12 typedef struct DCNode 13 { 14     ElemType data; 15     struct DCNode* next; 16     struct DCNode* front; 17 }DCNode; 18  19 typedef struct DCNode* DCLinkList; 20  21 Status InitList(DCLinkList* L)  //初始化操作，建立一个空的线性表.想把头指针里面的值改掉，所以传个头指针的地址 22 { 23     *L = (DCLinkList)malloc(sizeof(DCNode)); 24     if (!(*L)) 25         return ERROR; 26     (*L)->next = *L; 27     (*L)->front = *L; 28     return OK; 29 } 30 Status ListEmpty(DCLinkList L)  //若线性表为空，返回true,否则返回false 31 { 32     if (L->next == L) 33         return OK; 34     return ERROR; 35 } 36 Status ClearList(DCLinkList* L) //清空线性表 37 { 38     DCLinkList p = (*L)->next; 39     DCLinkList q; 40     while (p != *L) 41     { 42         q = p; 43         p = p->next; 44         free(q); 45     } 46     (*L)->next = *L; 47     (*L)->front = *L; 48     return OK; 49 } 50 Status GetElem(DCLinkList L, int  i, ElemType *e)  //查找线性表中的第i个位置的元素值，并赋值给e 51 { 52     int j = 0; 53     DCLinkList p = L->next; 54     while ((p!=L) &&( j < i)) 55     { 56         p = p->next; 57         j++; 58     } 59     if ((p == L) || (j > i)) 60         return ERROR; 61     *e = p->data; 62     return OK; 63 } 64 Status LocateElem(DCLinkList L, ElemType e) //查找线性表L中与给定值e相等的元素，如果查找成功，则返回第一个相同的元素在L中的下标；否则，返回0表示失败 65 { 66     int i = 1; 67     DCLinkList p = L->next; 68     while (p != L && p->data != e) 69     { 70         p = p->next; 71         i++; 72     } 73     if (p==L) 74         return ERROR; 75     return i; 76 } 77 Status ListInsert(DCLinkList* L, int i, ElemType e)  //在线性表L的第i个位置插入元素e 78 { 79     DCLinkList p, q; 80     p = *L; 81     int j = 1; 82     p = (*L)->next; 83     if ((*L)->next == *L) 84     { 85         if (i == 1) 86         { 87             goto ADD; 88         } 89     } 90     while ((p!= *L) && j<i)    //尾部插入时，p指向最后一个值，而j=i-1 91     { 92         p = p->next; 93         j++; 94     } 95     if ((p==*L) || j > i) 96         return ERROR; 97 ADD: 98     q = (DCLinkList)malloc(sizeof(DCNode)); 99     q->data =http://www.mamicode.com/ e;100     q->next = p->next;101     if (p->next)102         q->next->front = q;103     p->next = q;104     q->front = p;105 106     return ERROR;107 }108 Status ListDelete(DCLinkList*L, int i, ElemType* e) //删除线性表L中第i个位置元素，并用e返回其值109 {110     DCLinkList p, q;111     p = *L;112     int j = 1;113     //while (p && j<i)114     while ((p->next!=*L) && j<i)115     {116         p = p->next;117         j++;118     }119     //if (!p || j > i)120     if ((p->next == *L) || j > i)121         return ERROR;122     q = p->next;123     *e = q->data;124     p->next = q->next;125     q->next->front = p;126     free(q);127     return OK;128 }129 Status CreateListHead(DCLinkList *L, int n)130 {131     DCLinkList p;132     int i;133     (*L) = (DCLinkList)malloc(sizeof(DCNode));134     (*L)->next = *L;135     (*L)->front = *L;136     for (i = 0; i < n; i++)137     {138         p = (DCLinkList)malloc(sizeof(DCNode));139         p->data =http://www.mamicode.com/ i;140         p->next = (*L)->next;141         p->next->front = p;142         p->front = *L;143         (*L)->next = p;144     }145     return OK;146 }147 Status CreateListTail(DCLinkList *L, int n)148 {149     DCLinkList p;150     int i;151     (*L) = (DCLinkList)malloc(sizeof(DCNode));152     //(*L)->next = NULL;153     DCLinkList q = (*L);154     for (i = 0; i < n; i++)155     {156         p = (DCLinkList)malloc(sizeof(DCNode));157         p->data = http://www.mamicode.com/i + 10;158         q->next = p;159         p->front = q;160         q = p;161     }162     q->next = *L;163     (*L)->front = q;164     return OK;165 }166 Status visit(ElemType n)167 {168     printf("-> %d  ", n);169     return OK;170 }171 Status ListTraverse(DCLinkList L)172 {173     DCLinkList p = L->next;174     while (p != L)175     {176         visit(p->data);177         p = p->next;178     }179     return OK;180 }181 182 int ListLength(DCLinkList L)  //返回线性表L的长度183 {184     int i = 0;185     DCLinkList p = L->next;186     while (p != L)187     {188         i++;189         p = p->next;190     }191     return i;192 }193 194 int main()195 {196     DCLinkList L;197     Status i, j;198     char opp = ‘-1‘;199     ElemType e;200     int pos = 1;201     int k = 0;202 203     i = InitList(&L);204     printf("链表L初始化完毕，ListLength(L)=%d\n\n", ListLength(L));205 206     printf("\n1.遍历操作 \n2.插入操作  \n3.删除操作 \n4.获取结点数据\n5.查找某个数是否在链表中 \n6.头插法创建链表 \n7.尾插法创建链表 \n8.置空链表 \n0.退出 \n请选择你的操作：\n");207 208     while (opp != ‘0‘) {209         scanf_s("%c", &opp);210         switch (opp) {211         case ‘1‘:212             ListTraverse(L);213             printf("\n");214             break;215 216         case ‘2‘:217             srand((unsigned)time(NULL));218             for (j = 1; j <= 10; j++)219             {220                 i = ListInsert(&L, 1, rand() % 100);221             }222             printf("在L的表头依次插入10个随机数后：");223             ListTraverse(L);224             printf("\n");225             printf("链表L创建完毕，ListLength(L)=%d\n\n", ListLength(L));226             break;227         case ‘3‘:228             printf("要删除第几个元素？");229             scanf_s("%d", &pos);230             ListDelete(&L, pos, &e);231             printf("删除第%d个元素成功，现在链表为：\n", pos);232             ListTraverse(L);233             printf("\n");234             break;235 236         case ‘4‘:237             printf("你需要获取第几个元素？");238             scanf_s("%d", &pos);239             GetElem(L, pos, &e);240             printf("第%d个元素的值为：%d\n", pos, e);241             printf("\n");242             break;243         case ‘5‘:244             printf("输入你需要查找的数：");245             scanf_s("%d", &pos);246             k = LocateElem(L, pos);247             if (k)248                 printf("第%d个元素的值为%d\n", k, pos);249             else250                 printf("没有值为%d的元素\n", pos);251             printf("\n");252             break;253         case ‘6‘:254             CreateListHead(&L, 10);255             printf("整体创建L的元素(头插法)：\n");256             ListTraverse(L);257             printf("\n");258             break;259 260         case ‘7‘:261             CreateListTail(&L, 10);262             printf("整体创建L的元素(尾插法)：\n");263             ListTraverse(L);264             printf("\n");265             break;266 267         case ‘8‘:268             i = ClearList(&L);269             printf("\n清空L后：ListLength(L)=%d\n", ListLength(L));270             ListTraverse(L);271             printf("\n");272             break;273 274         case ‘0‘:275             exit(0);276         }277     }278 }