鏈表的代碼實現

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;  
}