链表

单链表基本操作链表的创立插入节点删除节点判断是否空表查找某个元素位置销毁链表 循环链表双向链表

单链表基本操作

链表的创立

#include<stdio.h> #include<stdlib.h> #include<string.h> struct NODE{ int data; struct NODE* next; }; struct NODE* Creatlink(void); void OutPutLink(struct NODE* head); int main(void){ struct NODE* head; head=Creatlink(); OutPutLink(head); return 0; } struct NODE* Creatlink(void){ int len,i,val; struct NODE* head=malloc(sizeof*head); struct NODE* move=head; move->next=NULL; if(head==NULL){ printf("分配内存失败"); exit(-1); } printf("你要输入几个结点："); scanf("%d",&len); for(i=0;i<len;i++){ struct NODE* fresh=malloc(sizeof*fresh); if(fresh==NULL){ printf("分配内存失败"); exit(-1); } printf("请输入第%d个结点",i+1); scanf("%d",&val); fresh->data=val; move->next=fresh; fresh->next=NULL; move=fresh; } return head; } void OutPutLink(struct NODE* head){ struct NODE* move=head; while(move->next!=NULL){ printf("%d",move->next->data); move=move->next; } }

插入节点

void InsertNode(struct NODE* head){ int x,y; struct NODE* move = head->next; struct NODE* fresh = malloc(sizeof*fresh); printf("请输入你要在第几个节点后插入,插入什么："); scanf("%d%d",&x,&y); fresh->data=y; getchar(); for(int i=1;i<x;i++){ move=move->next; } fresh->next=move->next; move->next=fresh; return; }

删除节点

void DeleteNode(struct NODE* head){ int m; struct NODE* save; struct NODE* move=head; printf("请输入你要删除第几个结点："); scanf("%d",&m); for(int i=1;i<m;i++){ move=move->next; } save=move->next; move->next=move->next->next; free(save); save=NULL; return; }

判断是否空表

IsEmpty(struct NODE* head){ return head->next==NULL; }

查找某个元素位置

Find(struct NODE* head,int data){ struct NODE* move = head->next; while(move!=NULL&&move->data!=data){ move=move->next; } return move; }

销毁链表

void DestoryLink(struct NODE* head){ struct NODE* save=head; while(head!=NULL){ save=head->next; free(head); head=save; } if(NULL==head){ printf("链表已被销毁"); } }

循环链表

关于循环链表就是将尾结点的next不是指向NULL而是重新指向头结点或者首节点，这样整个链表就形成了一个圆环，无论从哪一个节点都可以顺利地遍历链表的每个元素，而单链表却只能从头结点才可以做到。

下面我们可以用一个经典案例体验下循环链表的妙处。那就是著名的约瑟夫问题。

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

上述约瑟夫环可以作为一个循环链表，将1-n分别放进一个个节点中，然后每出列一个就删除一个节点，并且打印出节点数据。

#include<stdio.h> #include<stdlib.h> #include<string.h> struct NODE{ int data; struct NODE* next; }; struct NODE* Creatlink(int n); void DeleteNode(struct NODE* head,int man,int num); int main(void){ int man,n,num; printf("请输入环内人数："); while(1){ scanf("%d",&n); getchar(); if(n<1){ printf("error!请从新输入"); }else{ break; } } printf("请输入从第几个人开始："); while(1){ scanf("%d",&man); getchar(); if(man<1||man>n){ printf("error!请从新输入"); }else{ break; } } printf("请输入报数从1到几："); while(1){ scanf("%d",&num); getchar(); if(num<1){ printf("error!请从新输入"); }else{ break; } } struct NODE* head =Creatlink(n); printf("出列顺序表：\n"); DeleteNode(head,man,num); return 0; } struct NODE* Creatlink(int n){ int len,i,val; struct NODE* head=malloc(sizeof*head); struct NODE* move=head; move->next=NULL; if(head==NULL){ printf("分配内存失败"); exit(-1); } len=n; for(i=1;i<=len;i++){ struct NODE* fresh=malloc(sizeof*fresh); if(fresh==NULL){ printf("分配内存失败"); exit(-1); } fresh->data=i; move->next=fresh; fresh->next=NULL; move=fresh; } return head; } void DeleteNode(struct NODE* head,int man,int num){ int m; struct NODE* save; struct NODE* move=head->next; for(int i=1;i<man;i++){ move=move->next; } while(move->next!=move){ for(int i=1;i<num-1;i++){ move=move->next; } save=move->next; printf("%d ",save->data); move->next=move->next->next; move=move->next; free(save); save=NULL; } printf("%d \n",move->data); free(move); move=NULL; free(head); head=NULL; return; }

双向链表

对应单链表的就有双向链表，前者只有后继元素的地址，而后者则还有前驱元素的地址，这样虽然增加了一些内存上的开支，但是也带来了很多功能和效率上的好处。比如更加有利于搜索和查找元素，而且双向链表的增加和删除操作也更加方便，安全，不会一不小心将整个链表丢失掉。

任然使用上述循环链表中的案例，将约瑟夫环问题用双向链表实现一遍。

#include<stdio.h> #include<stdlib.h> #include<string.h> struct NODE{ int data; struct NODE* next; struct NODE* prior; }; struct NODE* Creatlink(int n); void DeleteNode(struct NODE* head,int man,int num); int main(void){ int man,n,num; printf("请输入环内人数："); while(1){ scanf("%d",&n); getchar(); if(n<1){ printf("error!请从新输入"); }else{ break; } } printf("请输入从第几个人开始："); while(1){ scanf("%d",&man); getchar(); if(man<1||man>n){ printf("error!请从新输入"); }else{ break; } } printf("请输入报数从1到几："); while(1){ scanf("%d",&num); getchar(); if(num<1){ printf("error!请从新输入"); }else{ break; } } struct NODE* head =Creatlink(n); printf("出列顺序表：\n"); DeleteNode(head,man,num); return 0; } struct NODE* Creatlink(int n){ int len,i,val; struct NODE* head=malloc(sizeof*head); struct NODE* move=head; move->next=NULL; if(head==NULL){ printf("分配内存失败"); exit(-1); } len=n; for(i=1;i<=len;i++){ struct NODE* fresh=malloc(sizeof*fresh); if(fresh==NULL){ printf("分配内存失败"); exit(-1); } fresh->data=i; move->next=fresh; fresh->next=NULL; fresh->prior=move; move=fresh; } move->next=head->next;//题目要求不包含空的头结点，所以指向首节点 head->next->prior=move; return head; } void DeleteNode(struct NODE* head,int man,int num){ int m; struct NODE* save; struct NODE* move=head->next; for(int i=1;i<man;i++){ move=move->next; } while(move->next!=move){ for(int i=1;i<num;i++){ move=move->next; } save=move; printf("%d ",save->data); move->next->prior=move->prior; move->prior->next=move->next; move=move->next; free(save); save=NULL; } printf("%d \n",move->data); free(move); move=NULL; free(head); head=NULL; return; }