通用链表复习（可以随便组合应付数据结构前几章题目） - C语言论坛

楼主
问题点数：0 回复次数：0
通用链表复习（可以随便组合应付数据结构前几章题目）
程序代码：
List.h
#ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED
///                    小鱼儿通用链表复习
typedef struct tagListNode
{
    void *data;
    struct tagListNode *pre; //指向前一个结点
    struct tagListNode *next; //指向后一个结点
}ListNode,*pListNode;

//链表私有的数据，不需要用户知道是什么样子
typedef struct tagListPrivate
{
    pListNode pHead; //指向线性表的头
    pListNode pTail; //指向线性表的尾
    int num; //总共的个数
    int DataSize; //存放数据的大小。用于判断是否为同一类数据
}ListPri,*pListPri;

typedef struct tagList
{
    void *LpInfo;//不要用户直接操作,隐藏数据
}List,*pList;

//比较函数指针这样就可以增加程序的通用性了
/// 判断数据是否相等 返回 0 不相等 1 想等
typedef int (*pCompare)(void *data1,void *data2);
/// 函数指针 由用户写显示功能
typedef void (*pShow)(void *data);
pList CreateList(int Size);
void ListDestroy(pList list);
int ListAdd(pList list,void *data);
int ListDele(pList list,void *data,pCompare CompareFun);
//2个线性表相加, flag :0 直接相加 1:只相加不同的部分
pList ListAddList(pList list1,pList list2);
//排序List 0:从小到大 1:从大到小
int ListSort(pList list,int flag,pCompare compare);

//显示链表的内容
void ListShow(pList list,pShow show);

//删除List 中相同的数据
void ListNotSome(pList list,pCompare compare);



int DestroyList(pList list);




#endif // LIST_H_INCLUDED

List.c
#include "List.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

pList CreateList(int Size)
{
    pList list;
    if(!Size)
    {
        puts("非法数据");
        return NULL;
    }
    else
    {
        list = (pList)malloc(sizeof(List));
        if(NULL == list)
        {
            puts("内存分配失败");
            return 0;
        }
        else
        {
            pListPri Lpr = (pListPri)malloc(sizeof(ListPri));
            if(NULL == Lpr)
            {
                free(list);
                puts("内存分配失败");
                return 0;
            }
            list->LpInfo = Lpr;
            ((pListPri)(list->LpInfo))->DataSize = Size;
            ((pListPri)(list->LpInfo))->num = 0;
            ((pListPri)(list->LpInfo))->pHead = NULL;
            ((pListPri)(list->LpInfo))->pTail = NULL;
        }
    }
    return list;
}

int ListAdd(pList list,void *data)
{
    pListPri pLpr = NULL;
    pListNode node = NULL;
    void *NodeData = NULL;
    int size;
    if(NULL == list)
    {
        puts("链表未创建");
        return 0;
    }

    if(NULL == data)
    {
        puts("数据非法");
        return 0;
    }
    else
    {
        node = (pListNode)malloc(sizeof(ListNode));
        if(NULL == node)
        {
            puts("内存分配失败");
            return 0;
        }
        pLpr =(pListPri)(list->LpInfo);
        size = pLpr->DataSize;
        NodeData = malloc(size);
        if(NULL == NodeData)
        {
            puts("内存分配失败");
            free(node);
            return 0;
        }

        memcpy(NodeData,data,size);
        node->data = NodeData;
        node->next = NULL;
        node->pre  = NULL;
        pLpr->num++;
        if(NULL == pLpr->pHead)
        {
            pLpr->pHead = node;
            pLpr->pTail = pLpr->pHead;
        }
        else
        {

        }
        pLpr->pTail->next = node;
        node->pre = pLpr->pTail;
        pLpr->pTail = node;
    }
    return 1;
}

void ListShow(pList list,pShow show)
{
    pListNode CurPtr;
    pListPri pLpr;
    if(NULL == show)
    {
        puts("非法指针");
        return;
    }

    if(NULL == list || NULL == list->LpInfo)
    {
puts("非法指针");
        return;
    }

    pLpr = (pListPri)(list->LpInfo);
    CurPtr = pLpr->pHead;
    while(CurPtr != NULL)
    {
        show(CurPtr->data);
        CurPtr = CurPtr->next;
    }
}

int ListDele(pList list,void *data,pCompare CompareFun)
{
    pListNode CurPtr;
    pListNode PrePtr;
    pListNode NextPtr;
    pListNode temp;
    pListPri pLpr;
    int flag = 0;
    if(NULL == data || NULL == CompareFun ||NULL == list)
    {
        puts("非法指针");
        return 0;
    }
    pLpr = (pListPri)list->LpInfo;
    CurPtr = pLpr->pHead;
    if(CompareFun(pLpr->pHead->data,data))
    {
        //PrePtr = CurPtr->pre;
        NextPtr = CurPtr->next;
        NextPtr->pre = NULL;
        pLpr->pHead = NextPtr;
        pLpr->num--;
        free(CurPtr->data); //不要忘记释放数据
        free(CurPtr); //释放的是头结点
        return 1;
    }

    if(CompareFun(pLpr->pTail->data,data))
    {
        CurPtr = pLpr->pTail->pre;
        temp = pLpr->pTail;
        CurPtr->next = NULL;
        pLpr->pTail = CurPtr;
        free(temp);
        return 1;
    }

     CurPtr = pLpr->pHead;
    while(NULL != CurPtr)
    {
        if(CompareFun(CurPtr->data,data))
        {
            PrePtr = CurPtr->pre;
            NextPtr = CurPtr->next;
            //(CurPtr->pre)->next = CurPtr->next;
            NextPtr->pre = PrePtr;
            //CurPtr->next->pre = CurPtr->pre;
            PrePtr->next = NextPtr;
            free(CurPtr->data); //要释放数据否者会内存泄漏
            free(CurPtr);
            return 1;
        }
        CurPtr = CurPtr->next;
    }
    return 0;

}

int ListSort(pList list,int flag,pCompare compare)
{
    pListNode CurPtr = NULL;
    pListNode PrePtr = NULL;
    pListNode NextPtr = NULL;
    pListNode temp = NULL;
    pListNode node = NULL;
    pListPri pLpr;
    void *tempData;
    if(NULL == list)
    {
        puts("非法链表");
        return 0;
    }

    pLpr = (pListPri)list->LpInfo;
    CurPtr = pLpr->pHead;
if(pLpr->num == 1)
{
return 1;
}
    for(;CurPtr;CurPtr=CurPtr->next)
    {
        node = CurPtr;
        for(temp= CurPtr->next;temp;temp=temp->next)
        {
            if(flag)
            {
                //返回1 为大于 从小到大排列
                if(compare(node->data,temp->data))
                {
                    tempData = node->data;
                    node->data = temp->data;
                    temp->data = tempData;
                }
            }
            else
            {
                //从大到小排列
                if(!compare(node->data,temp->data))
                {
                    tempData = node->data;
                    node->data = temp->data;
                    temp->data = tempData;
                }
            }
        }
        CurPtr->data = node->data;

    }
return 1;
}

pList ListAddList(pList list1,pList list2)
{
    pListPri pLpr;
    pListNode CurPtr;
    pList list;
    if(NULL == list1 || NULL == list2)
    {
        puts("非法链表");
        return 0;
    }
    pLpr = (pListPri)list1->LpInfo;
    if(NULL == pLpr)
    {
        puts("非法链表");
        return 0;
    }

    pLpr = (pListPri)list2->LpInfo;
    if(NULL == pLpr)
    {
        puts("非法链表");
        return 0;
    }

    pLpr = (pListPri)list1->LpInfo;
    list = CreateList(pLpr->DataSize);
        CurPtr = pLpr->pHead;
        while(CurPtr)
        {
            ListAdd(list,CurPtr->data);
            CurPtr = CurPtr->next;
        }

        pLpr = (pListPri)list2->LpInfo;
        CurPtr = pLpr->pHead;
        while(CurPtr)
        {
            ListAdd(list,CurPtr->data);
            CurPtr = CurPtr->next;
        }
        return list;

}

void ListNotSome(pList list,pCompare compare)
{
    pListNode CurPtr;
    pListNode PrePtr;

    pListNode NextPtr;
    pListNode temp = NULL,t;
    pListPri pLpr;
    void *ListData =NULL;
    pLpr = (pListPri)list->LpInfo;

    if(NULL == list || NULL == pLpr )
    {
        puts("非法链表");
        return;
    }
    CurPtr = pLpr->pHead;
    //temp =CurPtr->next;

    if(temp)
    {
        for(;CurPtr&&CurPtr!=pLpr->pTail;CurPtr = CurPtr->next)
        {
            for(temp = CurPtr->next;temp;)
            {
                if(compare(CurPtr->data,temp->data))
                {
                    if(compare(temp->data,pLpr->pTail))
                    {
                        PrePtr = pLpr->pTail->pre;
                        PrePtr->next = NULL;
                        pLpr->pTail = PrePtr;
                        t = temp;
                        temp = temp->next;
                        free(t->data);
                        free(t);
                        continue;
                    }
                    else
                    {
                        PrePtr = temp->pre;
                        NextPtr = temp->next;
                        PrePtr->next = NextPtr;
if(NextPtr!=NULL)
                        NextPtr->pre = PrePtr;
                        t = temp;
                        temp = temp->next;
                        free(t->data);
                        free(t);
                        continue;
                    }
                }
                temp = temp->next;
            }
        }
    }
}


void ListDestroy(pList list)
{
pListNode CurPtr;
pListNode PretPtr;
pListNode temp;
pListPri pLpr;
if(NULL == list)
{
puts("非法指针");
}
   pLpr = (pListPri)list->LpInfo;
   CurPtr = pLpr->pHead;
   while(CurPtr)
   {
  PretPtr = CurPtr;
  free(CurPtr->data);
  CurPtr = CurPtr->next;
  free(PretPtr);
   }
   free(list->LpInfo);
   free(list);
   list->LpInfo =NULL;
}

main.c

#include <stdio.h>
#include <stdlib.h>
#include "List.h"

void show(void *data)
{
    printf(" %d ",*(int *)data);
}

int compare(void *data1,void *data2)
{
    int n1 = *(int *)(data1);
    int n2 = *(int *)(data2);

    if(n1 == n2)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

int compare1(void *data1,void *data2)
{
    int n1 = *(int *)(data1);
    int n2 = *(int *)(data2);
    if(n1>=n2)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
int main()
{

int data1[] ={1,34,56,45,324,652,56,23,65,234,64,34};
int data2[] ={1,34,6,3,56,23,675,34,768,34,787,45,34576,45,234};
int i=0,j=0;
pList list1;
pList list2;
pList list3;
list1 = CreateList(sizeof(int));
list2 = CreateList(sizeof(int));
for(;i<2;i++)
{
ListAdd(list1,&data1[i]);
}

for(;j<15;j++)
{
ListAdd(list2,&data2[j]);
}
    puts("");
   // ListNotSome(list1,compare);
ListShow(list2,show);
puts("");
    ListShow(list1,show);
list3 = ListAddList(list1,list2);
puts("");
ListSort(list3,1,compare1);
//ListNotSome(list3,compare);
ListShow(list3,show);
ListDestroy(list3);
ListShow(list3,show);
    return 0;
}
这个通用链表是从我Hellovfp 师傅学到了。。
通过这里例子可以看出数据结构之美。。。。。。。
好数据结构可以是程序简明，效率高，算法难度下降。。。。

本来是发到自己空间，发着发着就想念HelloVfp 好久没有来论坛了。。。
蛮想他的，如是又发会坛子来表达思念呵呵。。。。
搜索更多相关主题的帖子: 通用　