数据结构笔记二(20120819)
/* * * wuxiuwen * 20120821 * 双向链表的创建,删除节点,插入节点,链表排序,节点的倒序输出, * */ #include<stdio.h> #include<stdlib.h> typedef struct node { int data; struct node *next; struct node *front; }DNode; void creatlist(DNode **); void outputlist(DNode *); void freelist(DNode **); DNode *Getnode(int); DNode *insertlist_node(DNode *,DNode *); DNode *rm_listnode(DNode *,DNode *); DNode *sort_listnode(DNode *); DNode *reverse_list(DNode *); int main() { DNode *head =NULL; DNode *pnew=NULL; creatlist(&head); printf("创建的节点是:\n"); outputlist(head); printf("排序结果如下:\n"); head = sort_listnode(head); outputlist(head); pnew = Getnode(5); printf("插入data为%d到有序序列为:\n",5); head = insertlist_node(head,pnew); outputlist(head); printf("删除增加的节点:\n"); head = rm_listnode(head,pnew); outputlist(head); /* head = reverse_list(head); printf("倒序输出链表为:\n"); outputlist(head); */ freelist(&head); return 0; } DNode *reverse_list(DNode *head) { DNode *headnew =NULL; DNode *p1 = NULL; DNode *p2 = NULL; DNode *p3 = NULL; headnew = (DNode *)malloc(sizeof(DNode)); headnew->next =headnew->front =NULL; p2 = headnew; head = head ->next; if(head ==NULL) { return head; } while(head !=NULL) { p1 = head ; head = head ->next; } headnew = headnew->next; while(p1 != NULL) { p3 = p1; p3 ->next = NULL; p3 ->front = NULL; p1 = p1->front; p2->front = headnew; p2->next = NULL; headnew->next=p2; } return p2; } DNode *sort_listnode(DNode *head) { DNode *p1=NULL; DNode *p2=NULL; DNode *headnew = NULL; headnew = (DNode *)malloc(sizeof(DNode)); headnew->next =headnew->front =NULL; p2 = headnew; head = head ->next; while(head !=NULL) { p1 = head; head = head ->next; p1 ->next = NULL; headnew = insertlist_node(headnew,p1); } return p2; } DNode *rm_listnode(DNode *head,DNode *pdel) {//查询链表中有这个节点pdel,有的话删除掉 DNode *p = head; if(head ==NULL && head ->next ==NULL) { return head; } while(p !=NULL && p!=pdel) { p=p->next; } if(p ==NULL && p !=pdel) { printf("no!"); return head; } if(p == pdel && p ->next==NULL) { p->front->next =NULL; } if(p == pdel && p->next!=NULL) { p->front->next=p->next; p->next->front=p->front; } free(pdel); return head; } DNode *insertlist_node(DNode *head,DNode *pnew) //插入的队列是从小到大的有序序列 { DNode *p1=head; DNode *p2=NULL; head = head ->next; if(head ==NULL) { pnew ->front = p1; pnew ->next = NULL; p1->next=pnew; return p1; } while(head != NULL) { if(head->data < pnew->data) { p2 =head; head = head->next; } else break; } if(head==NULL) { pnew->front=p2; pnew->next = NULL; p2->next = pnew; } if(head != NULL && head->data >= pnew->data) { pnew->front = p2; pnew->next = head; p2->next = pnew; head->front=pnew; } return p1; } DNode *Getnode(int num) { DNode *p=(DNode *)malloc(sizeof(DNode)); p->data = num; p->next =NULL; return p; } void creatlist(DNode **phead) { DNode *pnew=NULL; int num; DNode *pend =NULL; DNode **head; *phead = (DNode *)malloc(sizeof(DNode)); (*phead)->next =(*phead)->front =NULL; head = &((*phead)->next); scanf("%d",&num); while(num !=0) { pnew = Getnode(num); if(*head ==NULL) { *head = pend = pnew; pnew->front = *phead; } else { pend->next = pnew; pnew->front = pend; pend = pnew; } scanf("%d",&num); } } void outputlist(DNode *head) { DNode *p = NULL; head = head ->next; while(head !=NULL) { printf("%d ",head->data); p = head; head = head ->next; } /* printf("\n*******逆向输出******\n"); while(p->front !=NULL) { printf("%d ",p->data); p = p->front; } */ printf("\n"); } void freelist(DNode **head) { DNode *pdel =NULL; printf("\n释放空间的链表为:\n"); while(*head !=NULL) { pdel = *head; *head = (*head)->next; printf("%d ",pdel ->data); free(pdel); } printf("\n"); }
*********************************************************************************************************
程序运行结果:
[root@localhost wuxiuwen]# ./a.out
2 6 9 0
创建的节点是:
2 6 9
排序结果如下:
2 6 9
插入data为5到有序序列为:
2 5 6 9
删除增加的节点:
2 6 9
释放空间的链表为:
0 2 6 9
[root@localhost wuxiuwen]#
****************************************************************************************************************