#include <stdio.h>#include <malloc.h>#include <stdlib.h>#include <time.h>typedef struct _Node{ int data; struct _Node *next; }node;
/*创建一个链表*/
node *creatnode_head(int n){ node *p,*q=NULL; int i; srand(time(0)); node *r=(node *)malloc(sizeof(node)); r->next=NULL; for(int i=0;i<n;i++) { p=(node*)malloc(sizeof(node)); p->data=rand()0+1; printf("%d\n",p->data); r->next=p; p->next=q; q=p; } return r;}
node *creatnode(int n){ node *p,*q; int i; srand(time(0)); node *r=(node *)malloc(sizeof(node)); q=r; for(int i=0;i<n;i++) { p=(node*)malloc(sizeof(node)); p->data=rand()0+1; q->next=p; q=p; } q->next=NULL; return r;}/*测量链表的长度*/ int length(node *p){ int len=0; while(p->next!=NULL) { len++; p=p->next; } return len;}/*清空一个链表*/ void clear_list(node *list){ node *p,*q; if(list->next==NULL) { printf("此链表是空的：\n"); return; } p = list->next;//第一个结点 while(p) { q = p->next; free(p); p = q; } list->next = NULL; printf("此链表已经为空：\n");} /*判断一个链表是否为空*/ bool isempty(node *list){ if(list->next==NULL) { printf("此链表是空的!!!：\n"); return false; } else { printf("此链表不是空的：\n"); return true; }} /*打印链表*/ void printnode(node *p){ if(p->next==NULL) { printf("the node is empty:\n"); return; } else { p=p->next; while(p!=NULL) { printf("%d\t",p->data); p=p->next; } } printf("\n"); }/*定位到某个位置，返回值是该节点存储的数据*/ int search_node(node *head,int pos){ if(pos<0) { printf("the pos can not smaller than 0\n"); return -1; } else if(pos==0) { printf("the position is the head\n"); return -1; } else if(head->next==NULL) { printf("the node is empty\n"); return -1; } else { while(pos--) { head=head->next; if(head==NULL) { printf("the pos over the length of the node\n"); return -1; } } } return head->data; }/*定位到某个位置，返回值是该节点存储的地址*/ node *search_node1(node *head,int pos){ if(pos<0) { printf("the pos can not smaller than 0\n"); return NULL; } else if(pos==0) { printf("the position is the head\n"); return NULL; } else if(head->next==NULL) { printf("the node is empty\n"); return NULL; } else { while(pos--) { head=head->next; if(head->next==NULL) { printf("the pos over the length of the node\n"); return NULL; } } } return head; }/*删除某个节点*/ node *delete_node(node *head,int pos){ node *item=NULL; node *p=head; node *q=search_node1(head,pos-1); node *r=q->next; printf("%d\n",q->data); if(q==NULL) { printf("delete failed..."); } else { item=q->next; q->next=item->next; free(r); item=NULL; } return p;}/*在某个位置插入一个新节点*/ node *insert_node(node *head,int pos,int data){ node *p=head; head=search_node1(head,pos-1); if(head==NULL) {printf("insert failed...\n");
return p;
} node *item=(node*)malloc(sizeof(node)); item->data=data; item->next=head->next; head->next=item; return p;}/*交换函数*/ void swap(int *x,int *y){ int temp; temp=*x; *x=*y; *y=temp;}/*冒泡排序*/ node *bubbleSortList(node *list) { if(list->next == NULL) return list; node *r=list; node *p = NULL; node *head=list->next; bool isChange = 1; while(p != head->next && isChange) { node *q = head; isChange = 0;//标志当前这一轮中又没有发生元素交换，如果没有则表示数组已经有序 for(; q->next && q->next != p; q = q->next) { if(q->data > q->next->data) { swap(&q->data, &q->next->data); isChange = 1; } } p = q; } list->next=head; return r;}/*两个有序链表的合并*/ node *SortedMerge(node * a, node * b) { node * result = NULL; /*Base cases*/ if(a == NULL) return (b); else if(b == NULL) return (a); /*Pick either a or b, and recur */ if(a->data <= b->data) { result = a; result->next = SortedMerge(a->next, b); } else { result = b; result->next = SortedMerge(a, b->next); } return (result); } /*链表的逆置*/ node *reverse(node *head){ node *p,*q,*r; if(head->next==NULL) { printf("the node is empty\n"); return head; } p=head->next; q=p->next; p->next=NULL; while(q!=NULL) { r=q->next; q->next=p; p=q; q=r; } head->next=p; return head;}int main(){ int len=0; int n=0; node *head,*head1,*head2; head=creatnode(5); printf("the data of the node is:\n"); printnode(head); len=length(head); printf("the length of the node is:%d\n",len); printf("is empty?\n"); isempty(head); len=search_node(head,5); printf("the data of the pos is %d\n",len); printf("delete operation test...\n"); head=delete_node(head,3); printnode(head); printf("insert operation test...\n"); printf("please input a data:\n"); scanf("%d",&n); head=insert_node(head,3,n); printnode(head); printf("the first reverse operation test...\n"); head=reverse(head); printnode(head); printf("the sort operation test...\n"); head=bubbleSortList(head); printnode(head1); head=creatnode(5); printnode(head1); bubbleSortList(head1); printf("start merge:\n"); printf("*****\n"); printf("the first node is:\n"); printnode(head1); printf("the second node is:\n"); printnode(head); printf("*****\n"); printf("after merge:\n\n"); head2=SortedMerge(head->next,head1->next); head->next=head2; printnode(head); clear_list(head); isempty(head); return 0;}
