东莞市有几个区_中国建筑有限公司西南分公司网页设计_站长工具端口查询_上海关键词seo

单链表练习

1.判断是否成环

快慢指针,如果能相遇就成环.

/******************** 功能：判断链表是否有环；* 参数：phead* 返回值：有：1*      无：0；* ******************/
int is_loop(link_node *phead)
{if(NULL == phead){printf("phead = NULL;");return 0;}link_node *p = phead, *q =phead; while(NULL != p){p=p->pnext;if(p ==q){return 1;}if(p != NULL){p=p->pnext;            if(p ==q){return 1;}q = q->pnext;if(p ==q){return 1;}}}return 0;}

2.实现约瑟夫环

快慢指针,慢指针指向快指针前一个结点,方便删除节点

linl_node *joseph_loop (link_node *phead)
{if(NULL == phead){printf("phead = NULL;");return 0;}if(is_empty_link(phead)){return 0;}link_node *p = phead->pnext, *q =phead;while(p!=q){data_type i;for(i=0;i<2;++i){p = p->pnext;q = q->pnext;}link_node * k =p;q->pnext=p->pnext;p=p->pnext;free(k);}return q;}

双向链表的操作

.h文件

#ifndef __DOULINK_H__
#define __DOULINK_H__typedef struct stu
{int id;char name[32];int score;
}data_type;typedef struct node
{data_type data;struct node *ppre;struct node *pnext;
}dou_node;extern dou_node *creat_doulink();
extern int is_empty_link(dou_node *phead);
extern int insert_head_doulink(dou_node *phead ,data_type data);
extern int doulink_for_each(dou_node *phead,int num);
extern int insert_tail_doulink(dou_node *phead ,data_type data);
extern int delete_head_doulink(dou_node *phead);
extern int delete_tail_doulink(dou_node *phead);
extern dou_node * find_doulink(dou_node *phead,char *name);
extern int change_doulink(dou_node *phead,char *oldname,char *newname);
extern int destroy_doulink(dou_node *phead);
#endif

main.c

#include<stdio.h>
#include"doulink.h"
int main()
{data_type s[6]={{1,"zhang san",89},{2,"li si",97},{3,"wang ma zi",86},{4,"zhao wu",97},{5,"li liu",94},{6,"xu heng",100}};dou_node *phead = creat_doulink();
if(phead == NULL)
{return -1;
}insert_head_doulink(phead ,s[3]);
insert_head_doulink(phead ,s[2]);
insert_head_doulink(phead ,s[1]);
insert_head_doulink(phead ,s[0]);
insert_tail_doulink(phead ,s[4]);
insert_tail_doulink(phead ,s[5]);delete_head_doulink(phead);
#if 0
delete_head_doulink(phead);
delete_head_doulink(phead);
delete_head_doulink(phead);
delete_head_doulink(phead);
delete_head_doulink(phead);
#endifdelete_tail_doulink(phead);
#if 0
delete_tail_doulink(phead);
delete_tail_doulink(phead);
delete_tail_doulink(phead);
delete_tail_doulink(phead);
delete_tail_doulink(phead);
#endif
//dou_node *p = find_doulink(phead,"li si");
change_doulink(phead,"li si","wang er");
//printf("id=%d name=%s score=%d\n",p->data.id,p->data.name,p->data.score);doulink_for_each(phead,1);
doulink_for_each(phead,0);
destroy_doulink(phead);
}

1.创建

/**********************************功能：创建一个有头的双向链表*返回值：*		成功：返回头结点地址*		失败：NULL* *****************************/
dou_node *creat_doulink()
{dou_node *phead =NULL;phead = malloc(sizeof(dou_node));if(phead == NULL){printf("malloc fail!");return NULL;}phead->ppre = NULL;phead->pnext = NULL;return phead;
}

2.头插和尾插以及正反遍历

头插注意分两种情况(因为要通过后一个节点(ppre)访问)

/***************************** 功能：头插* 参数：phead以及插入的data；* 返回：成功0失败-1；* *************************/int insert_head_doulink(dou_node *phead ,data_type data)
{if(NULL == phead){printf("phea is NULL");return -1;}dou_node *pinsert = malloc(sizeof(dou_node));if(NULL == pinsert){printf("malloc faill");return -1;}pinsert->data = data;pinsert->ppre = NULL;pinsert->pnext = NULL;if (is_empty_link(phead)){phead->pnext =pinsert;pinsert->ppre = phead;}else{pinsert->pnext = phead->pnext;pinsert->ppre = phead;phead->pnext->ppre=pinsert;phead->pnext = pinsert;}return 0;
}

尾插:和单链表区别不大,先找到最后一个节点,然后插入,多个ppre

/***************************** 功能：尾插* 参数：phead以及插入的data；* 返回：成功0失败-1；* *************************/int insert_tail_doulink(dou_node *phead ,data_type data)
{if(NULL == phead){printf("phea is NULL");return -1;}dou_node *pinsert = NULL;pinsert = malloc(sizeof(dou_node));pinsert->data = data;pinsert->ppre = NULL;pinsert->pnext = NULL;dou_node *p = phead;//区别phead与phead->pnextwhile(NULL != p->pnext){p = p->pnext;}p->pnext = pinsert;pinsert->ppre = p;return 0;
}

正反遍历:
正向同单链表,反向先便利到最后一个节点,从后往前打印,直到指向头节点,头节点的特点是p->ppre=NULL,作为循环及截止条件;

/******************* 功能:正反遍历* 参数：phead，1（正）* 返回成功0；* ***********/int doulink_for_each(dou_node *phead,int num)
{if(NULL == phead){printf("phea is NULL");return -1;}if(num ==1)//正{dou_node *p = phead->pnext;while(NULL != p){printf("id=%d  name=%s  score=%d\n",p->data.id,p->data.name,p->data.score);p =p->pnext; }printf("\n");return 0;}else{dou_node *p = phead;//这样不用判空while(p->pnext != NULL)//找到最后一个{p = p->pnext;}while(NULL != p->ppre)//打印完成直到头节点{printf("id=%d  name=%s  score=%d\n",p->data.id,p->data.name,p->data.score);p =p->ppre; }printf("\n");return 0;}}

3.头删和尾删

注意,头尾删先判空

头:区别与单链,同头插,分两种情况(为什莫要分两钟情况呢,因为只有一个只有结点的时候,后节点是NULL,不能访问NULL->ppre),删的时候先保存节点;

/***************************** 功能：头删* 参数：phead；* 返回：成功0失败-1；* *************************/int delete_head_doulink(dou_node *phead)
{if(NULL == phead){printf("phea is NULL");return -1;}if(is_empty_link(phead)){return -1;}if(phead->pnext->pnext == NULL){free(phead->pnext);phead->pnext = NULL;}else{dou_node *pdel = phead->pnext;phead->pnext = pdel->pnext;pdel->pnext->ppre = phead;free(pdel);}return 0;
}

尾: 区别单向链表,双向链表可以让指针停在要删的地方。因为双向可以访问到前一个指针

/****************************2* 功能：尾删* 参数：phead；* 返回：成功0失败-1；* *************************/int delete_tail_doulink(dou_node *phead)
{if(NULL == phead){printf("phea is NULL");return -1;}dou_node *p = phead->pnext;if(is_empty_link(phead)){return -1;}while(p->pnext != NULL){p = p->pnext;}p->ppre->pnext = NULL;//双向链表可以让指针停在要删的地方。free(p);return 0;
}

4.查找,删除,销毁

查找:同单链查找

/***************************** 功能：查找（通过姓名）* 参数：phead；data.name.* 返回：成功返回地址，失败NULL；* *************************/dou_node * find_doulink(dou_node *phead,char *name)
{dou_node *p = phead->pnext;while(NULL != p){if(strcmp(p->data.name,name)==0){return p;}p = p->pnext;}return NULL;
}

修改:同单

/***************************** 功能：修改（通过姓名）* 参数：phead；oldname; newname* 返回：成功0，失1；* *************************/int change_doulink(dou_node *phead,char *oldname,char *newname)
{dou_node *p = phead->pnext;while(NULL != p){if(strcmp(p->data.name,oldname)==0){strcpy(p->data.name,newname);return 0;}p = p->pnext;}return 1;
}

销毁:同单

/***************************** 功能：销毁* 参数：phead；* 返回：成功0，* *************************/int destroy_doulink(dou_node *phead)
{dou_node *pdel=phead->pnext;while(NULL != pdel){dou_node *p = pdel->pnext;free(pdel);pdel = p;}free(phead);return 0;
}

或者通过头删

void destroy_doulink(Dou_Node *phead)
{	if (NULL == phead){printf("phead is null\n");return ;}while (!is_empty_doulink(phead)){delete_head_doulink(phead);}free(phead);
}