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