首页 > 代码库 > 链表讲解和基本操作练习附代码
链表讲解和基本操作练习附代码
以下都是单链表的基本操作,我都写了一遍,链表时间长不写一定会陌生,留给自己以后忘了看一眼,顺便给想学习链表的同学一点提示吧
首先先写头文件head.h,这里都是我定义好的函数分别有
这里的所有例子都是有头结点的链表,都是单链表操作
1)头插发建表 2)尾插法建表 3)打印链表 4)对链表赋值的时候进行插入排序 5)将链表翻转 6)找到链表倒数第n个元素 7)将两个链表连在一起 8)使单链表变成环链表
9)判断链表是否有环 10)将现有的链表排序进行插入排序(与4)不同,4)是在建立链表的时候进行排序,) 11)删除链表重复元素 12)判断链表是否有交点,并输出 13)使两个链表有交点
#ifndef _LINK_H_ #define _LINK_H_ #include<iostream> #include<stdio.h> #include<time.h> #define out using namespace std; struct node_stu{ int num; node_stu *next; }; void link_init_tail(node_stu **head,int size); void link_init_head(node_stu **head,int size); void print_link(node_stu *head); void link_init_sort_insert(node_stu **head,int size); void turn_link(node_stu **head); int find_back_num(node_stu *head,int n); int find_back_num(node_stu *head); void unite_links(node_stu **head1,node_stu **head2); void make_link_into_circle(node_stu **head); int judge_circle(node_stu *head); void sort_link(node_stu **head); void delete_repetition(node_stu** head); int count_intersection(node_stu *head1,node_stu *head2,node_stu** node_intersection); void make_intersection_link(node_stu** head1,node_stu** head2,int ,int ); #endif
1)头插发建表
#include"head.h" void link_init_head(node_stu **head,int size){ *head=(node_stu*)calloc(1,sizeof(node_stu)); node_stu *p=*head; p->next=NULL; for(int i=0;i<size;i++){ node_stu *temp=(node_stu*)calloc(1,sizeof(node_stu)); temp->num=rand()%100;; temp->next=p->next; p->next=temp; } }
2)尾插法建表
#include"head.h" void link_init(node_stu **head,int size){ node_stu *p; *head=(node_stu *)calloc(1,sizeof(node_stu)); p=*head; p->next=NULL; for(int i=0;i<size;i++){ p->next=(node_stu *)calloc(1,sizeof(node_stu)); p=p->next; p->num=rand()%100; p->next=NULL; } }
3)打印链表
#include"head.h" void print_link(node_stu* head){ while(head->next!=NULL){ head=head->next; cout<<head->num<<" "; } cout<<endl; }
4)对链表赋值的时候进行插入排序
<pre class="cpp" name="code">#include"head.h" void link_init_sort_insert(node_stu **head,int size){ *head=(node_stu*)calloc(1,sizeof(node_stu));//定义头指针 node_stu *p=*head,*pre=*head;//定义指针p和前指针pre (*head)->next=NULL;//初始化头指针 (*head)->num=-1; for(int i=0;i<size;i++){ p=*head; node_stu *temp=(node_stu*)calloc(1,sizeof(node_stu)); temp->num=rand()%100;//定义节点并且赋予随机数 cout<<temp->num<<" "; temp->next=NULL; pre=p; int flag_mid=0;//标记在中间进行插入 while(p->next!=NULL){ pre=p; p=p->next;//p在前面探路,pre紧随其后,然后temp找到合适位置就插在pre和p适当的位置 if((temp->num)>=(pre->num) && (temp->num)<=(p->num)){ flag_mid=1; break; } } if(flag_mid!=1)//在头插入或者在未插入 p->next=temp; else { pre->next=temp;//在pre和p中间插入 temp->next=p; } } }
5)将链表翻转
#include"head.h" void turn_link(node_stu **head){ // node_stu *newhead=(node_stu*)calloc(1,sizeof(node_stu)); // newhead->next=NULL;将链表逆序 node_stu *p=*head; p=p->next; (*head)->next=NULL; while(p!=0){ node_stu *temp=(node_stu*)calloc(1,sizeof(node_stu));//定义一个临时结构体节点 temp=p; p=p->next; temp->next=NULL;//从链表头部中截取一个节点 temp->next=(*head)->next;//将这个节点(头插法)插到表头中 (*head)->next=temp; } }
6)找到链表第n个元素
#include"head.h" int find_back_num(node_stu *head,int n){ node_stu *pre; pre=head; // 至楼顶两个指针,一个head一个pre,中间间隔n n--; while(n--) pre=pre->next; while(pre->next!=NULL){//当pre到头的时候head就是倒数第n个 pre=pre->next; head=head->next; } return head->num; }
7)将两个链表连接在一起
<pre class="cpp" name="code">#include"head.h" void unite_links(node_stu **head1,node_stu **head2){//将两个链表结合 node_stu *p; p=(*head1); while(p->next!=NULL) p=p->next; p->next=(*head2)->next; // delete (node_stu*) head2; }
8)将链表变成循环链表
<pre class="cpp" name="code">#include"head.h" void make_link_into_circle(node_stu **head){//是head链表变成有环的 node_stu *p; p=(*head); while(p->next!=NULL) p=p->next; p->next=(*head)->next; }
9)判断链表是否有环
<pre class="cpp" name="code">#include"head.h" int judge_circle(node_stu *head){ node_stu *p; p=head->next; head=head->next; while(head!=NULL){ head=head->next; if(head==p) return 1; } return 0; }
10)将链表进行插入排序
主要思想是,将链表的一个点摘下来,在用原链表的头作为新的头在进行插入排序
<pre class="cpp" name="code">#include"head.h" void sort_link(node_stu **head){//对链表进行排序 node_stu *pre,*find_p,*original_p,*sort_p; // sort_p=(*head)->next->next; original_p=(*head)->next;//记录原始字符串的位置 (*head)->next=NULL;//将头结点next赋NULL,这个作为一个新的字符串开始 find_p=(*head);//找到字节在新的字符串中应该放的位置,与pre相对应,find_p在左,pre在右 while(original_p!=NULL){// sort_p=original_p;//需要加入新的排序字符串的节点 original_p=original_p->next;//记录原始字符串的位置向后移 sort_p->next=NULL;//将sort—p隔离出来 find_p=(*head);//每次都从新的头结点开始找 int flag_mid=0;//标记在中间进行插入 while(find_p->next!=NULL){// pre=find_p;// find_p=find_p->next;//pre 与find_p 一前一后,寻找插入值 if((sort_p->num)>=(pre->num) && (sort_p->num)<=(find_p->num)){// flag_mid=1;// break; } } if(flag_mid!=1)//在头插入或者在未插入 find_p->next=sort_p; else { pre->next=sort_p;//在中间插入 sort_p->next=find_p; } } } 11)删除链表中重复元素
<pre class="cpp" name="code">#include"head.h" void delete_repetition(node_stu** head){ node_stu *end,*first,*temp; end=(*head)->next; first=end->next; while(first!=NULL){ if(end->num==first->num){//遇到相同的就删 temp=end->next; end->next=first->next; first=first->next; delete (node_stu *) temp; } first=first->next; end=end->next; } }
12)判断两个链表是否有交点,并输出交点
#include"head.h" int count_intersection(node_stu *head1,node_stu *head2,node_stu** node_intersection){ int len1=0,len2=0,len; node_stu *p1,*p2; p1=head1; p2=head2; while(p1->next!=NULL){//计算p1有多长 len1++; p1=p1->next; } while(p2->next!=NULL){//计算p2有多长 len2++; p2=p2->next; } len=len1>len2?len2:len1; p1=head1; p2=head2; while(len--)//取最小值然后找到p1倒数len个节点是什么 p1=p1->next; while(p1->next!=NULL){ p1=p1->next; head1=head1->next; } len=len1>len2?len2:len1; while(len--)//取最小值然后找到p2倒数len个节点是什么 p2=p2->next; while(p2->next!=NULL){ p2=p2->next; head2=head2->next; } while(head1->next!=NULL){//在同时p1,p2为倒数len时,开始向后比较,看是否有交点 head1=head1->next; head2=head2->next; if(head1==head2){ *node_intersection=head1;//返回交点 return 1; } } return 0; }
13)使两个链表相交
#include"head.h" void make_intersection_link(node_stu** head1,node_stu** head2,int n,int m){//m新生成的,n是head1链表,输入的n是想让第n个节点为head1的交点,让m为head2的交点 node_stu *p,*p1; *head2=(node_stu *)calloc(1,sizeof(node_stu)); p=*head2; p->next=NULL; for(int i=0;i<m;i++){ p->next=(node_stu *)calloc(1,sizeof(node_stu)); p=p->next; p->num=rand()%100; p->next=NULL; } p1=*head1;//这里链表head1是之前就建好的 while(n--)//将head1自增到n, p1=p1->next; p->next=p1;//然后与新生成的head2的第m个位置指向head1的第n个位置 }
我写的主函数用来测试各个函数
<pre class="cpp" name="code">#include"head.h" int main(int argc,char *argv[]){ srand(time(NULL)); node_stu *head=NULL; node_stu *head2=NULL; node_stu *head3=NULL; node_stu *node_intersection=NULL; int intersection_a,intersection_b; int size,n; while(~scanf("%d",&size)){ //头插发 // link_init_tail(&head,size); //尾插法 // link_init_head(&head,size); printf("插入后排序:\n"); link_init_sort_insert(&head,size);//插入是排序 cout<<endl; print_link(head);//打印字符串 printf("链表翻转:\n"); turn_link(&head);//链表翻转 print_link(head);// printf("输出去倒数第几个元素:"); while(scanf("%d",&n),(n>size || n<=0)) printf("输入的数范围不对,请重新输入\n");//, printf("%d\n",find_back_num(head,n));// printf("输出链表中间元素:\n"); cout<<find_back_num(head)<<endl;// printf("输出两个字符串:\n"); print_link(head); link_init_head(&head2,size);///
print_link(head2); printf("合并之后:\n"); unite_links(&head,&head2);// print_link(head); /***
// printf("判断链表是否有环\n"); // print_link(head2); // make_link_into_circle(&head2);//是链表编程有环链表 // if(judge_circle(head2)) // printf("有环\n"); // else // printf("无环\n"); */ /*****/ printf("将链表排序\n"); sort_link(&head); print_link(head); /**/ printf("删除重复元素\n"); delete_repetition(&head);///////////////////////// print_link(head); printf("判断两个链表是否有环,如果有输出环\n"); printf("制造两个有交点的链表,输入想让head链表第几个节点成为交点,同时新生成的链表第几个成为交点;"); scanf("%d %d",&intersection_a,&intersection_b); make_intersection_link(&head,&head2,intersection_a,intersection_b); // link_init_head(&head2,size); if(count_intersection(head,head2,&node_intersection)){ printf("有\n"); cout<<node_intersection->num<<endl; } else printf("无\n"); } system("pause"); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。