# 链表练习题

2018-01-27 19:12:07来源:cnblogs.com作者:你好，bigshot人点击

1、单链表，双链表的创建。
2、单链表和双链表的打印。
3、单链表的插入，删除。
4、双链表的插入和删除。
5、单链表的逆置。
6、单链表节点的个数。
7、单链表，双链表的查找。

`  1 //链表相关问题  2   3 typedef int DataType;  4 typedef struct LinkNode  //单链表结构  5 {  6     struct LinkNode* next;  7     DataType data;  8 }LinkNode;  9  10 LinkNode *CreateNode(DataType x) //创建单链表节点 11 { 12     LinkNode *tmp = (LinkNode *)malloc(sizeof(LinkNode)); 13     if (NULL == tmp) 14     { 15         printf("分配内存失败！/n"); 16         return NULL; 17     } 18     tmp->next=NULL; 19     tmp->data=x; 20     return tmp; 21 } 22  23 void PrintLinkList(LinkNode *phead)  //单链表打印 24 { 25     while (phead) 26     { 27         printf("%d ",phead->data); 28         phead = phead->next; 29     } 30     printf("/n"); 31 } 32  33 void InsertLinkList(LinkNode **phead,LinkNode *pos,DataType x)  //单链表插入 34 { 35     LinkNode *newNode,*tmp = *phead; 36     assert(phead); 37     if (NULL==*phead) 38     { 39         *phead = CreateNode(x); 40         return; 41     } 42     while(*phead != pos) 43     { 44         tmp = *phead; 45         *phead = (*phead)->next; 46     } 47     newNode = CreateNode(x); 48     newNode->next = tmp->next; 49     tmp->next = newNode; 50 } 51  52 size_t ListNodeCount(LinkNode* phead) //计算单链表的节点数 53 { 54     size_t count = 0; 55     while (phead) 56     { 57         count++; 58         phead = phead->next; 59     } 60     return count; 61 } 62  63 LinkNode *LinkListSearch(LinkNode *phead,DataType x)  //在单链表中查找一个数 64 { 65     while(phead) 66     { 67         if (phead->data == x) 68             return phead; 69         phead = phead->next; 70     } 71     return NULL; 72 } 73  74 LinkNode *ReverseLinkList(LinkNode *phead)  //单链表的逆置 75 { 76     LinkNode *first = phead; 77     LinkNode *cur = first->next; 78     first->next=NULL; 79  80     while (cur) 81     { 82         LinkNode *tmp = cur->next; 83         cur->next = first; 84         first = cur; 85         cur = tmp; 86     } 87     return first; 88 } 89  90 size_t RemoveLinkList(LinkNode **phead,LinkNode *pos)  //单链表任意节点删除 91 { 92     LinkNode *first = *phead; 93     while (first) 94     { 95         if (*phead == pos) //删头节点 96         { 97             *phead = first->next; 98             free(pos); 99             pos = NULL;100             return 1;101         }102         else if (first->next == pos) //非头节点情况103         {104             first->next = pos->next;105             free(pos);106             pos = NULL;107             return 1;108         }109         first = first->next;110     }111     return 0;112 }113 114 typedef struct DoubleLinkList  //双链表结构115 {116     DataType data;117     struct DoubleLinkList *prev;118     struct DoubleLinkList *next;119 }DoubleList;120 121 DoubleList *CreateDoubleList(DataType x) //创建双链表节点122 {123     DoubleList *newNode = (DoubleList *)malloc(sizeof(DoubleList));124     assert(newNode);125     newNode->next = NULL;126     newNode->prev = NULL;127     newNode->data = x;128     return newNode;129 }130 131 void PrintDoubleList(DoubleList *phead)  //打印双链表132 {133     DoubleList *tmp = phead;134     while (tmp)135     {136         printf("%d ",tmp->data);137         tmp = tmp->next;138         if (tmp == phead)139             break;140     }141     printf("/n");142 }143 144 DoubleList *DoubleListSearch(DoubleList *phead,DataType x)  //双链表查找145 {146     DoubleList *tmp = phead;147     while (phead)148     {149         if (phead->data == x)150             return phead;151         if (tmp == phead->next)152             break;153         phead = phead->next;154     }155     return NULL;156 }157 158 void DoubleListInsert(DoubleList **phead, DataType x) //双链表的头插159 {160     DoubleList *tmp = (*phead);161     DoubleList *newNode = CreateDoubleList(x);162 163     if (NULL == *phead)164     {165         *phead = newNode;166         (*phead)->next = *phead;167         (*phead)->prev = *phead;168     }169     else 170     {171         newNode->next = (*phead)->next;172         (*phead)->next = newNode;173         newNode->prev = *phead;174         newNode->next->prev = newNode;175     }176 }177 178 179 size_t RemoveDoubleListNode(DoubleList **phead,DataType x)  //删除双链表节点180 {181     DoubleList *tmp = *phead;182     while (*phead)183     {184         if (tmp->data == x)185         {186             tmp->prev->next = tmp->next;187             tmp->next->prev = tmp->prev;188             if (tmp->data == (*phead)->data)189                *phead = tmp->next;190             if ((*phead)->next == *phead)191             {192                 free(*phead);193                 *phead = NULL;194             }195             free(tmp);196             tmp = NULL;197             return 1;198         }199         if (*phead == tmp->next)200             break;201         tmp = tmp->next;202     }203     return 0;204 }`