数据结构和算法之基于链表的栈和队列、多文件和模块分层设计、函数指针

1、准备知识
1.1 写通用的 链表函数库

     typedef int INT32;

软件设计的要求：

1、将软件分为2层：
应用层----main.cpp            ----高层 模块
链表层----list.h  list.cpp    ----底层 模块

2、封装
即：链表模块 通过list.h，对外公开一些数据类型、函数，则调用者(如main.cpp文件)只能调用这些 数据类型和函数；而list.cpp中，还有一些函数可能
是链表模块自己调用的，则不需要公开它们的函数原型，这样main.cpp就无法调用它们了----相当于被隐藏了。

//main.cpp
#include
#include
#include
#include "list.h"
struct Student
{
    int number;
    char *name;
};

void print_student(void *data)
{
    struct Student *p=(struct Student *)data;
    printf("number is %d\tname is %s\n",p->number,p->name);
    return;
}

int main()
{
    struct Student stu[3]={1001,"zhangsan",1002,"lisi",1003,"wangwu"};
    struct Node *head=link_create();
    link_add(&head,(void *)&stu[0]);
    link_add(&head,(void *)&stu[1]);
    link_add(&head,(void *)&stu[2]);
    link_foreach(head,print_student);

    return 0;
}

//list.h
struct Node;

typedef void (*pfun)(void *data);     //将函数原型中的 函数 括起来，再加*-->函数指针变量;前面加typedef则变量-->类型
struct Node * link_create();
void link_add(struct Node **head,void *data);
void link_foreach(struct Node *head, pfun print_student);            //pfun函数指针类型

//list.cpp
#include
#include
#include

#include "list.h"

struct Node
{
    void *data;
    struct Node *next;
};

struct Node * link_create()
{
    struct Node * head=NULL;

    return head;
}

void link_add(struct Node **head,void *data)
{
     struct Node *p=(struct Node *)malloc(sizeof(struct Node));
     struct Node *p2;
     p->data=data;
     p->next=NULL;
     if(*head==NULL)
     {
         *head=p;
     }
     else
     {
        p2=*head;
         while(p2->next!=NULL)
        {
            p2=p2->next;
        }
         p2->next=p;
     }
    return;
}

void link_foreach(struct Node *head, pfun print_student)
{
    struct Node *p=head;
    if(head==NULL)
    {
        return;
    }
    else
    {
        while(p!=NULL)
        {
            //printf("%d  %s\n",p->number,p->name);
            print_student(p->data);
            p=p->next;
        }

    }
    return;
}

函数指针：

#include
#include
#include

typedef int (*pfun)(int a,int b);    //函数原型(pfun就是函数名)------>括起来加*(函数指针 变量)--------->加typedef（函数指针 类型）

int sum_bmd(int a,int b)
{
    return a+b;
}

int main()
{
    int a=10;
    int b=20;

    pfun m;
    m=sum_bmd;

    int result=m(a,b);
    printf("%d\n",result);

    //typedef int INT32;

    return 0;
}

函数指针使用原则1：尽量不用；迫不得已才用

队列：
1 概念
队列
公交车站排队(像链表)------------加了护栏--------->队列

链表的操作：建立空链表  追加节点  删除第1个节点   求链表长度    返回头节点的值   销毁链表   前插节点   中间插节点  删除中间节点
队列的操作：建立空队列  进队      出队            求队列长度    返回队首里的值   销毁队列

栈
1 概念
"abcdefgh"-----》反过来输出   ------ 用栈

链表的操作：建立空链表  前插节点  删除第1个节点   求链表长度    返回头节点的值   销毁链表   前插节点   中间插节点  删除中间节点
栈的操作：  建立空栈    进栈      出栈            求栈长度      返回栈顶里的值   销毁栈

队列代码：
//main.cpp
#include
#include
#include
#include "queue.h"
struct Student
{
    int number;
    char *name;
};

int main()
{
    struct Student stu[3]={1001,"zhangsan",1002,"lisi",1003,"wangwu"};
    struct Node*head=queue_create();
    queue_push(&head,(void *)&stu[0]);
    queue_push(&head,(void *)&stu[1]);
    queue_push(&head,(void *)&stu[2]);
    void *data=queue_top(head);
    struct Student *stuu=(struct Student *)data;
    printf("%d   %s\n",stuu->number,stuu->name);

    return 0;
}

//queue.h
#include "list.h"
struct Node* queue_create();
void queue_push(struct Node**head,void *data);
void *queue_top(struct Node *head);

//queue.cpp
#include "queue.h"

struct Node* queue_create()
{
    return link_create();
}

void queue_push(struct Node**head,void *data)
{
    link_add(head,data);
    return;
}

void *queue_top(struct Node *head)
{
    return link_top(head);
}

//list.h
struct Node;

typedef void (*pfun)(void *data);     //将函数原型中的 函数 括起来，再加*-->函数指针变量;前面加typedef则变量-->类型

struct Node * link_create();
void link_add(struct Node **head,void *data);
void link_foreach(struct Node *head, pfun print_student);            //pfun函数指针类型

    
void *link_top(struct Node *head);

//list.cpp
#include
#include
#include
#include "list.h"

struct Node
{
    void *data;
    struct Node *next;
};

struct Node * link_create()
{
    struct Node * head=NULL;

    return head;
}

void link_add(struct Node **head,void *data)
{
     struct Node *p=(struct Node *)malloc(sizeof(struct Node));
     struct Node *p2;
     p->data=data;
     p->next=NULL;
     if(*head==NULL)
     {
         *head=p;
     }
     else
     {
        p2=*head;
         while(p2->next!=NULL)
        {
            p2=p2->next;
        }
         p2->next=p;
     }
    return;
}

void link_foreach(struct Node *head, pfun print_student)
{
    struct Node *p=head;
    if(head==NULL)
    {
        return;
    }
    else
    {
        while(p!=NULL)
        {
            //printf("%d  %s\n",p->number,p->name);
            print_student(p->data);
            p=p->next;
        }

    }
    return;
}

void *link_top(struct Node *head)
{
    if(head==NULL)
    {
        return NULL;
    }
    else
    {
        return head->data;
    }
}

栈
1 概念
"abcdefgh"-----》反过来输出   ------ 用栈

链表的操作：建立空链表  前插节点  删除第1个节点   求链表长度    返回头节点的值   销毁链表   前插节点   中间插节点  删除中间节点
栈的操作：  建立空栈    进栈      出栈            求栈长度      返回栈顶里的值   销毁栈

栈操作的代码：----不全，只有main函数里的调用。以后，需要增加stack.h和stack.cpp进行完善
//main.cpp
#include
#include
#include
#include "stack.h"
struct Student
{
    int number;
    char *name;
};

int main()
{
    struct Student stu[3]={1001,"zhangsan",1002,"lisi",1003,"wangwu"};
    struct Node *head=stack_create();
    stack_push(&head,(void *)&stu[0]);
    stack_push(&head,(void *)&stu[1]);
    stack_push(&head,(void *)&stu[2]);
    void *data=stack_top(head);
    struct Student *stuu=(struct Student *)data;
    printf("%d   %s\n",stuu->number,stuu->name);

    return 0;
}