博客

我们最近学了数据结构链表中的尾插法，头插法，双向链表

链表的步骤

1.申请一个新的节点空间

2.给新的节点赋值信息域

3.修改这个节点的指针域，将节点连接起来

尾插法：顾名思义就是从节点的尾部进行插入，首先申请一个节点空间，给新的节点赋值信息域，然后修改这个

节点的指针域，写链表首先要判断头节点是否为空，第一步，如果节点为空，将新的节点地址复制给头节点，如果头节点

不为空，要定义一个尾节点。专门来找链表的尾巴，如果尾巴的指针域为空，就把尾巴的节点指向尾巴的下一个节点，如果

尾节点的指针域不为空，尾巴指向下一个节点,pear=prea->next;

代码如下

bool insert(pnode*pph)
{
	pnode pnew=malloc(sizeof(struct student ));
	if(NULL==pnew)
		return false;
	pnew->data=msg;
	if(NULL==*pph)
	{
		*pph=pnew;
	
	}
	else
	{
		pnode prear=*pph;
		while(pear->next!=NULL)prear=prear->next;
		prear->next=pnew;
	}
	return true;
}

头插法：顾名思义就是从节点的头部插入，首先要申请一个新的节点空间，给新的节点赋值信息域，将头指针指向这个新的节点，

在要插入节点时候，将新的节点的指针域指向头节点指向的指针域，pnew->next=*pph ，然后将这个新的节点的地址赋值给头节点

*pph=pnew;

代码如下

bool insert(pnode*pph)
{
	pnode pnew=malloc(sizeof(struct student));
	if(NULL==pnew)
		return false;
	pnew->data=msg;
	pnew->next=*pph;
	*pph=pnew;
	return true;
	

}

双向链表：就是链表即有前驱节点，又有后驱节点，首先申请一个新的节点空间，然后判断头节点是否为空，如果为空，将pnew->next=*pph，

pnew->front=NULL;最后将头节点指向新的节点,*pph=pnew, 又增加了一个节点，此时，还是判断头节点是否为口，此时不为空，pnew->next=*pph,

将新节点的指针域指向头节点指向的节点，将新节点的前驱节点指向空,pnew->front=NULL; 还是头节点指向新的节点，*pph=pnew


代码如下

bool insert(pnode *pph,dtype msg)
{
	pnode pnew=malloc(sizeof(dtype));   申请一个新的节点空间
	if(NULL==pnew)
		return false;
	pnew->data=msg;
	if(NULL!=*pph)
	{
		(*pph)->front=pnew;	
	}
	pnew->next=*pph;
	pnew->front=NULL;
	*pph=pnew;
	return true;

}

因为方便我把所有的结构体类型都重命名

代码如下

struct student;   声明
struct nd;
struct student dtype;
struct nd*     pnode;
struct student
{
	int id;
	char name[10];
};
struct nd
{
 	dtype data;   信息域
	pnode next;   指针域

};

节点的删除，利用双指针，一个头指针，一个尾巴指针，用尾巴指针找到这个 想要删除的节点，将头指针指向尾巴的下一个节点

bool delete(node*pph,int d)
{
    node front=*pph,rear=*pph;
    while(rear!=NULL && rear->data.id=d)   变量查找id
    {
             front=rear;    
             rear=rear->next;
    }
    if(NULL!=rear)
    {
        if(rear==*pph)   如果尾巴节点等于头
        {
            *pph=rear->next;
        }
        else              如果尾巴节点不等于头
        {
            front->next=rear->next;
        }
        free(rear);
        return true;
    }
    return true;
}