day-21 内核链表以及栈

1.昨日作业

1.删除指定节点

找到删除就完事了，双向可以停在删除处。

/****************************
 * 功能：删除指定结点（通过姓名）
 * 参数：phead；oldname; 
 * 返回：成功0，失-1；
 * *************************/

int delete_specified_node(dou_node *phead,char *oldname)
{
    if(NULL == phead)
    {
        printf("phea is NULL");
            return -1;
    }
    dou_node *p = phead->pnext;
    while(NULL != p)
    {
        if(strcmp(p->data.name,oldname)==0)
        {
            dou_node *q = p->pnext;
            p->ppre->pnext = q;
            q->ppre = p->ppre;
            free(p);
            return 0;
        }
        p = p->pnext;
    }
    return -1;
}

2.内核链表

内核链表将节点以及要储存的数据分离开来，节点的操作函数不因数据类型的改变而需要重写。

1.klist.h

声明节点的类型，以及节点操作的函数

#ifndef __KLIST_H__
#define __KLIST_H__

typedef struct knode
{
    struct knode *ppre;
    struct knode *pnext;
}Knode;

extern Knode * creat_klist();
extern int insert_head_klist(Knode *phead ,Knode *pinsert);
extern void list_for_each(Knode *phead,void (*pfun)(Knode *));

extern int delete_tail_klist(Knode*phead);
extern int delete_head_klist(Knode*phead);
extern void destroy_klist(Knode * phead);
extern int insert_tail_klist(Knode *phead,Knode *pinsert);
#endif

2.flight.h

声明数据结构体类型，

##ifndef __FLIGHT_H__
#define __FLIGHT_H__

#include "klist.h"

struct passager
{
    Knode node;
    char name[32];
    int flt_num;
    int sit_num;
    char hea_card;
};

extern struct passager* creat_passager(char *name,int flt_num, int sit_num,char hea_card);
extern void print_passager(Knode *p);
#endif

2 .klist.c

1.创建节点

Knode *creat_klist()
{
    Knode *phead = NULL;
    phead = malloc(sizeof(Knode));
    if(NULL == phead)
    {
        printf("malloc fail\n");
        return NULL;
    }

    phead->ppre = NULL;
    phead->pnext = NULL;
    return phead;
}

2.前插

逻辑同双向链表的前插，但是呢插得是数据中的节点，故在main函数中应先定义数据结构体变量，定义的时候不用管节点成员。传参传结构体成员如下所示

	struct passager *p1 = creat_passager("zhangsan",2024,1,'r');    
    struct passager *p2 = creat_passager("lisi",2024,2,'g');
    struct passager *p3 = creat_passager("wanger",2024,3,'y');
    
    insert_tail_klist(phead,&(p1->node));
    insert_tail_klist(phead,&(p2->node));
    insert_tail_klist(phead,&(p3->node));

插入分两种情况，空的和非空

int insert_head_klist(Knode *phead , Knode *pinsert)
{
    pinsert->pnext = phead->pnext;
    if(phead->pnext != NULL)
    {
        phead->pnext->ppre = pinsert;
    }
    pinsert->ppre = phead;
    phead->pnext = pinsert;
    return 0;
}

3.后插

后插特殊部分和前插一样，但是有个细节是查完之后pinsert->pnext = NULL;

int insert_klist_tail(KNode *phead, KNode *pnode)
{
	if (NULL == phead || NULL == pnode)
		return -1;
	

	KNode *p = phead;
	while (p->pnext != NULL)
	{
		p = p->pnext;
	}
	
	p->pnext = pnode;
	pnode->ppre = p;
	pnode->pnext = NULL;
	
	return 0;
}

4.遍历（重重重点）

达到低耦合的效果

第一种

通过函数指针形成回调函数 。达到不同的数据类型也可以通过一个遍历函数完成便利，只需要传递不同的函数指针就行。

void list_for_each(Knode *phead, void (*pfun)(Knode *))
{
    if(phead ==NULL || NULL == pfun)
        return;
    Knode *p = phead->pnext;

    while(NULL  !=p)
    {
        pfun(p);
        p = p->pnext;
    }
    printf("\n");

}

回调函数
先强转在访问

void print_passager(Knode *pnode)
{
    struct passager *p = (struct passager *)pnode;
    printf("%s %d %d %c\n",p->name,p->flt_num,p->sit_num,p->hea_card);

}

main函数调用

list_for_each(phead,print_passager);

第二种

通过带参宏的形式，去访问结构体成员
.h中声明

#define klist_for_each(pos, head)                                        \
	for (pos = (head)->pnext; pos != NULL; pos = pos->pnext)

main’函数中直接使用，先强转随便访问结构体；

klist_for_each(ptmp, phead)
{
	struct passager *p = (struct passager *)ptmp;
	
}

5.删除销毁等同双向，本质是双向链表，把节点放在结构体首个成员。结构体地址等于节点地址。

3.栈

1.系统栈和数据结构中的栈的区别