链表的代码实现

linklist.h

#ifndef __LINKLIST_H__ #define __LINKLIST_H__ #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int DataType; typedef struct LinkNode { DataType data; struct LinkNode* next; }LinkNode,*pLinkNode; typedef struct LinkList { LinkNode* pHead; }LinkList,*pLinkList; void InitLinkList(pLinkList list);   void DestoryList(pLinkList list);   void PushBack(pLinkList list , DataType x);   void PopBack(pLinkList list);   void PushFront(pLinkList list , DataType x);   void PopFront(pLinkList list);   void PrintList(pLinkList list);   pLinkNode Find(pLinkList list,DataType x);   void Insert(pLinkList list, pLinkNode pos, DataType x);   void Remove(pLinkList list, DataType x);   void RemoveAll(pLinkList list, DataType x);   void Erase(pLinkList list,pLinkNode pos);   void BubbleSort(pLinkList list);   void SelectSort(pLinkList list);   void InsertSort(pLinkList list);   #endif    //__LINKLIST_H__

linkllist.c

#include"linklist.h"      void CreateNode(pLinkNode *newNode, DataType x)  //创建节点 {              *newNode = (pLinkNode)malloc(sizeof(LinkNode));       if (NULL == *newNode)       {           printf("out of memory\n");           exit(EXIT_FAILURE);       }       (*newNode)->data = x;       (*newNode)->next = NULL;   }   void InitLinkList(pLinkList list)  //初始化 {   list->pHead = NULL;      assert(list);    }      void DestoryList(pLinkList list)   {       assert(list);       if (NULL==list->pHead)            //链表为空直接返回       {           return;       }       else       {           pLinkNode cur = list->pHead;     //cur指向第一个结点           while (cur != NULL)                    {               list->pHead = cur->next;    //pHead指向cur的下一个结点，当cur是最后一个结点时，pHead指向空               free(cur);               cur = list->pHead;          //cur指向当前第一个结点,当链表为空时，cur指向空           }       }      }      void PushBack(pLinkList list, DataType x)   {   pLinkNode newNode = NULL;     assert(list);         CreateNode(&newNode,x);       if (NULL == (list->pHead))             //如果是空链表，直接插入头指针之后       {           list->pHead = newNode;       }       else       {           pLinkNode cur = list->pHead;           while (NULL != (cur->next))            //找到最后一个结点cur           {               cur = cur->next;           }           cur->next = newNode;       }   }      void PopBack(pLinkList list)   {       assert(list);       if (NULL == list->pHead)       {           return;       }       else       {           pLinkNode cur = list->pHead;           if (NULL == cur->next)                 //如果只有一个结点           {               free(cur);               list->pHead= NULL;           }           else           {               while (NULL != cur->next->next)         //大于一个结点，先找到倒数第二个结点               {                   cur = cur->next;               }               free(cur->next);               cur->next= NULL;           }       }   }      void PushFront(pLinkList list, DataType x)           {   pLinkNode newNode = NULL;      assert(list);       CreateNode(&newNode, x);       newNode->next =list->pHead;           //newNode的指针域先指向第一个结点       list->pHead= newNode;                 //头指针指向newNode   }      void PopFront(pLinkList list)   {  pLinkNode cur = list->pHead;             //cur指向第一个结点     assert(list);       if (NULL == list->pHead)              //空链表       {           return;       }       list->pHead = cur->next;             //指向第一个结点的指针域       free(cur);       cur = NULL;   }      void PrintList(pLinkList list)   {   pLinkNode cur = list->pHead;     assert(list);        while (NULL != cur)       {           printf("%d->", cur->data);           cur = cur->next;       }       printf("over\n");   }      pLinkNode Find(pLinkList list, DataType x)   {   pLinkNode cur = list->pHead;     assert(list);       while (NULL != cur)       {           if (cur->data == x)           {               break;           }           cur = cur->next;       }       return cur;                 }      void Insert(pLinkList list, pLinkNode pos, DataType x)  //在pos后面插入元素   {   pLinkNode cur = list->pHead; pLinkNode newNode = NULL;     assert(list);       CreateNode(&newNode, x);       while (NULL != cur)                                  //先找到这个位置       {           if (cur == pos)           {               break;           }           cur = cur->next;       }       if (NULL != cur)       {           newNode->next=cur->next;           cur->next = newNode;       }       else       {           printf("没有这个结点\n");       }          }      void Remove(pLinkList list, DataType x)   {   pLinkNode cur = list->pHead;       pLinkNode p = list->pHead;      assert(list);       if (NULL == list->pHead)              //空链表直接返回       {           return;       }       if (NULL == cur->next)                 //如果只有一个结点       {           if (cur->data == x)           {               list->pHead = cur->next;               free(cur);               return;           }       }       else       {           if (cur->data == x)                   //先判断第一个结点是不是要删除的结点           {               list->pHead = cur->next;               free(cur);               return;           }           cur = cur->next;           while (NULL != cur)           {               if (cur->data == x)               {                   p->next = cur->next;   //p结点的指针域指向要删除结点的指针域                   free(cur);                   return;               }               p = cur;               cur = cur->next;           }       }   }      void RemoveAll(pLinkList list, DataType x)   {   pLinkNode cur = list->pHead;       pLinkNode p = NULL;       assert(list);       if (NULL == list->pHead)       {           return;       }       while (NULL != cur)       {           if (NULL == list->pHead->next)          //如果要只有一个结点           {               if (cur->data == x)                 //如果是则删除               {                   list->pHead = cur->next;                   free(cur);                   return;               }           }           else if (list->pHead->data == x)         //判断是不是第一个结点，是则删除，继续判断           {                   list->pHead = cur->next;                   free(cur);                   cur = list->pHead;           }           else           {               break;           }       }       //要删除的结点在第一个结点之后       cur = cur->next;       p = list->pHead ;       while (NULL != cur)       {           if (cur->data == x)           {               p->next = cur->next;           //p结点的指针域指向要删除结点的指针域               free(cur);               cur = p;           }           p = cur;           cur = cur->next;       }   }      void Erase(pLinkList list, pLinkNode pos)   //删除pos后面的结点   {   pLinkNode cur = list->pHead;       pLinkNode p = list->pHead;     assert(list);        if (NULL == cur)       {           return;       }       if (NULL == cur->next)                  //如果只有一个结点       {           if (cur == pos)           {               free(cur);               list->pHead = NULL;           }       }       else       {           if (cur == pos)                        //如果是第一个结点           {               list->pHead = cur->next;               free(cur);               return;           }           cur = cur->next;           while (NULL != cur)           {               if (cur == pos)               {                   p->next = cur->next;                   free(cur);                   return;               }               p= cur;               cur = cur->next;           }       }   }      void BubbleSort(pLinkList list)   {   pLinkNode cur = list->pHead;       pLinkNode p1= list->pHead;       int flag = 0;       DataType tmp=0; pLinkNode p2 = list->pHead->next;         assert(list);       if (NULL == list->pHead)       {           return;       }       if (NULL == cur->next)       {           return;       }       cur = cur->next;       while (NULL!=cur)       {           flag = 1;           while (NULL != p2)           {               if (p1->data > p2->data)               {                   tmp = p1->data;                   p1->data = p2->data;                   p2->data = tmp;                   flag = 0;               }               p2 = p2->next;               p1 = p1->next;           }           if (flag)           {               break;           }           p1 = list->pHead;           p2 = list->pHead->next;           cur = cur->next;       }   }

 test.c

#include"linklist.h"   void Menu()   {       printf("**********************************\n");       printf("*0.Quit           1.InitLinkList *\n");       printf("*2.PushBack       3.PopBack      *\n");       printf("*4.PushFront      5.PopFront     *\n");       printf("*6.PrintList      7.Find         *\n");       printf("*8.Insert         9.Remove       *\n");       printf("*10.RemoveAll     11.Erase       *\n");       printf("*12.BubbleSort    \n");       printf("**********************************\n\n");       printf("请选择: ");   }      void test()   {       LinkList list;       DataType x = 0;       pLinkNode pos = NULL;       int n = -1;       while (1)       {           Menu();           scanf("%d", &n);           switch (n)           {           case 0:               DestoryList(&list);               exit(1);               break;           case 1:               InitLinkList(&list);               break;           case 2:               printf("请输入：");               scanf("%d",&x);               PushBack(&list,x);               break;           case 3:               PopBack(&list);               break;           case 4:               printf("请输入：");               scanf("%d", &x);               PushFront(&list,x);               break;           case 5:               PopFront(&list);               break;           case 6:               PrintList(&list);               break;           case 7:               printf("请输入：");               scanf("%d", &x);               pos=Find(&list,x);               printf("查找成功\n");               break;           case 8:               printf("请输入元素：");               scanf("%d", &x);               Insert(&list,pos,x);               break;           case 9:               printf("请输入：");               scanf("%d", &x);               Remove(&list,x);               break;           case 10:               printf("请输入：");               scanf("%d", &x);               RemoveAll(&list,x);               break;           case 11:               Erase(&list,pos);               break;           case 12:               BubbleSort(&list);               break;           default:               printf("选择无效,请重新选择\n");               break;           }       }   }      int main()   {       test();       system("pause");       return 0;   }