当前位置: 编程技术>c/c++/嵌入式
C数据结构之双链表详细示例分析
来源: 互联网 发布时间:2014-10-18
本文导语: 代码如下: typedef struct node{ struct node *prior; struct node *next; int num;}NODE;/*******双向链表的初始化********/NODE *Init_link(void){ int i; NODE *phead,*pb,*pi; phead = (NODE *)malloc(sizeof(NODE)); printf("please...
代码如下:
typedef struct node
{
struct node *prior;
struct node *next;
int num;
}NODE;
/*******双向链表的初始化********/
NODE *Init_link(void)
{
int i;
NODE *phead,*pb,*pi;
phead = (NODE *)malloc(sizeof(NODE));
printf("please input num:n");
scanf("%d",&(phead->num));
phead->prior = NULL;
phead->next = NULL;
pb = phead;
for(i=0; inum));
pi->next = NULL;
pb->next = pi;
pi->prior = pb;
pb = pi;
}
return phead;
}
/******链表的输出******/
void print_link(NODE *phead)
{
while(phead != NULL)
{
printf(" %d,",phead->num);
phead = phead->next;
}
printf("n");
}
/******链表的逆序******/
NODE *reverse_link(NODE *phead)
{
NODE *pb,*pf,*temp;
pb = phead;
pf = pb->next;
while(pf != NULL)
{
temp = pf->next;
pf->next = pb;
pb->prior = pf;
pb = pf;
pf = temp;
}
// phead->prior = pf->prior;
phead->next = NULL;
phead = pb;
return phead;
}
/*****链表的排序*****/
NODE *Order_link(NODE *phead)
{
NODE *pb,*pf,*ptr,temp;
pb = phead;
while(pb->next != NULL)
{
pf = pb->next;
while(pf != NULL)
{
if(pb->num > pf->num)
{
temp = *pb;
*pb = *pf;
*pf = temp;
ptr = pb->next;
pb->next = pf->next;
pf->next = ptr;
ptr = pb->prior;
pb->prior = pf->prior;
pf->prior = ptr;
}
pf = pf->next;
}
pb = pb->next;
}
return phead;
}
/******链表的有序插入*****/
NODE *insert_link(NODE *phead,NODE *pi)
{
NODE *pb,*pf;
pb = phead;
if(pi == NULL)
return phead;
if(phead == NULL)
{
phead = pi;
pi->prior = NULL;
pi->next =NULL;
}
else
{
while( (pi->num > pb->num)&&(pb->next!=NULL))
{
pf = pb;
pb = pb->next;
}
if(pi->num num)
{
if(pb == phead)
{
pi->next = phead;
pi->prior = NULL;
phead->prior = pi;
phead = pi;
}
else
{
pi->next = pb;
pb->prior = pi;
pi->prior = pf;
pf->next = pi;
}
}
else
{
pi->next = NULL;
pi->prior = pb;
pb->next = pi;
}
}
return phead;
}
/******链表的删除*****/
NODE *delete_link(NODE *phead, NODE *pi)
{
NODE *pb,*pf;
pb = phead;
while(pb != NULL)
{
if(pb == pi)
{
if(pb == phead)
phead = phead->next;
else if(pb->next == NULL)
pf->next = NULL;
else
{
pf->next = pb->next;
//pb->next->prior = pf;
}
}
pf = pb;
pb = pb->next;
}
return phead;
}
/*******链表的释放******/
void free_link(NODE *phead)
{
NODE *pb;
while(phead != NULL)
{
pb = phead->next;
free(phead);
phead = pb;
}
printf("released link success!n");
}
/*******测试程序******/
int main(void)
{
NODE *phead,*pi;
phead = Init_link();
printf("init link:n");
print_link(phead);
pi = (NODE *)malloc(sizeof(NODE));
printf("plaese input insert num:");
scanf("%d",&(pi->num));
phead = insert_link(phead,pi);
printf("after insert link:n");
print_link(phead);
phead = Order_link(phead);
printf("after sort link:n");
print_link(phead);
printf("after reverse link:n");
phead = reverse_link(phead);
print_link(phead);
phead = delete_link(phead, pi);
printf("after delete link:n");
print_link(phead);
free_link(phead);
return 0;
}