/**********双向链表节点**********/
typedef struct student
{
int num;
float score;
struct student *prior;
struct student *next;
}TYPE;
int nod_num; //节点数
#define LEN sizeof(TYPE) //节点长度
/*=================================================
函数功能: 创建双向链表
返 回 值: 双向链表的头指针
=================================================*/
TYPE* create_link(void)
{
TYPE *head=NULL;
TYPE *p1,*p2;
nod_num = 0;
p1 = p2 = (TYPE *)malloc(LEN);
printf("input the %d node--num,score!/n",(nod_num+1));
scanf("%d,%f",&(p1->num),&(p1->score));
while(p1->num != 0)
{
nod_num++;
if(nod_num == 1)
{
head = p1;
head->prior = NULL; //首节点的两个指针为NULL
head->next = NULL;
}
else
{
p1->prior = p2;
p2->next = p1;
}
p2 = p1;
p1 = (TYPE *)malloc(LEN);
printf("input the %d node--num,score!/n",(nod_num+1));
scanf("%d,%f",&(p1->num),&(p1->score));
}
p2->next = NULL;
return head;
}
/*===================================================
函数功能: 链表输出
特别说明: 链表的正向输出(从链表头遍历到链表尾)
===================================================*/
void NextPrint(TYPE *head)
{
TYPE *p = head;
if(p != NULL)
{
do
{
printf("num=%d,score=%f/n",p->num,p->score);
p = p->next;
}
while(p != NULL);
}
}
/*===================================================
函数功能: 链表输出
特别说明: 链表的反向输出(从链表尾遍历到链表头)
===================================================*/
void PriorPrint(TYPE *head)
{
TYPE *p = head;
if(p != NULL)
{
while(p->next != NULL)
p = p->next;
while(p != NULL)
{
printf("num=%d,score=%f/n",p->num,p->score);
p = p->prior;
}
}
}
/*=============================================
函数功能: 删除给定序号所指向的节点
函数参数: head 链表的首地址
num 所需删除的节点
返 回 值: 删除指定节点后的新链表首址
=============================================*/
TYPE* del_link(TYPE *head,int num)
{
TYPE *pf;
TYPE *pb = head;
if(head == NULL)
{
printf("/nempty list/n");
return NULL;
}
while((pb->num != num)&&(pb->next != NULL))
{
pf = pb;
pb = pb->next;
}
if(pb->num == num)
{
if(pb == head) //判断是否是第一个节点
{
if(pb->next == NULL) //如果只有一个节点
{
free(pb);
head = NULL;
return NULL;
}
pb->next->prior = NULL;
head = pb->next;
}
else if(NULL == pb->next) //判断是否是最后一个节点
{
pf->next = NULL;
}
else //中间某个节点
{
pf->next = pb->next;
pb->next->prior = pf;
}
free(pb);
printf("this node is deleted!/n");
}
else
printf("the node not been found!/n");
return head;
}
/*=============================================
函数功能: 将新申请的节点加入到指定链表中
函数参数: head 链表的首地址
ins 待插入的节点
返 回 值: 插入指定节点后的新链表首址
=============================================*/
TYPE *insert_link(TYPE *head,TYPE *ins)
{
TYPE *pb = head;
TYPE *pf;
if(head == NULL)
{
printf("/nempty list/n");
return NULL;
}
while((ins->num > pb->num)&&(pb->next != NULL))
{
pf=pb;
pb=pb->next;
}
if(ins->num <= pb->num)
{
if(pb==head)
{
ins->next = pb;
ins->prior = head->prior;
pb->prior = ins;
head = ins;
}
else
{
pf->next = ins;
pb->prior = ins;
ins->next = pb;
ins->prior = pf;
}
}
else
{
pb->next = ins;
ins->next = NULL;
ins->prior = pb;
}
return head;
}
/*=============================================
函数功能: 搜索给定序号所指向的节点
函数参数: head 链表的首地址
num 按所需进行节点搜索
返 回 值: 搜索到的节点首址
=============================================*/
TYPE *search_link(TYPE *head,int num)
{
TYPE *pb = head;
if(NULL == head)
{
return head;
}
while((pb->num != num)&&(pb->next != NULL))
{
pb = pb->next;
}
if(pb->num == num)
{
return pb;
}
else
{
return head;
}
}
/******************测试函数*******************/
int main(int argc,char *argv[])
{
TYPE *head;
TYPE *temp;
TYPE *ins;
TYPE *target;
/***创建链表***/
printf("create test!/n");
head = create_link();
/***遍历链表***/
printf("print test!/n");
printf("reserse print/n");
PriorPrint(head);
printf("normal print/n");
NextPrint(head);
/***删除链表***/
printf("delete test!/n");
temp = del_link(head,102);
NextPrint(temp);
/***插入链表***/
printf("insert test!/n");
ins = (TYPE *)malloc(LEN);
printf("insert Number and Score:/n");
scanf("%d,%f",&(ins->num),&(ins->score));
head = insert_link(head,ins);
NextPrint(head);
/***查寻链表***/
target = search_link(head,102);
NextPrint(target);
return 0;
}