精华内容
下载资源
问答
  • C语言链表操作详解

    万次阅读 多人点赞 2018-12-29 19:01:55
    为什么要使用链表 在未学习链表时,我们常用的存储数据的方式无非就是数组。...而链表则可以实现以上这些数组所不具备的功能,此时引入了结构体来实现创建链表操作链表的特点: n个节点离散分配 每一个节...

    为什么要使用链表

    在未学习链表时,我们常用的存储数据的方式无非就是数组。使用数组存储数据的好处就是查询快,但是它的弊端也很明显:

    1.  使用前需声明数组的长度,一旦声明长度就不能更改
    2. 插入和删除操作需要移动大量的数组元素,效率慢
    3. 只能存储一种类型的数据.

    而链表则可以实现以上这些数组所不具备的功能,此时引入了结构体来实现创建链表的操作。

    链表的特点:

    1.  n个节点离散分配
    2. 每一个节点之间通过指针相连
    3. 每一个节点有一个前驱节点和一个后继节点
    4. 首节点没有前驱节点,尾节点没有后继节点

    首先先定义一个简单的结构体

    struct link{
           int data;          //定义数据域
           struct link *next; //定义指针域,存储直接后继的节点信息
    };

    数据域的内容可以自己指定,指针域用来存放下一个节点的地址。

    创建链表前须知

    首节点:存放第一个有效数据的节点

    头节点:在单链表的第一个结点之前附设一个结点,它没有直接前驱,称之为头结点,头结点的数据域可以不存储任何信息,指针域指向第一个节点(首节点)的地址。头结点的作用是使所有链表(包括空表)的头指针非空

    头指针:指向头节点的指针

    尾节点:存放最后一个有效数据的节点

    尾指针:指向尾节点的指针

    建立一个单向链表

    方法:定义方法向链表中添加节点来建立一个单向链表

    思路:首先定义一个结构体指针变量p,使用malloc函数为新建节点申请内存空间,让p指向这个节点(指向它刚申请的内存空间),再将其添加到链表中。此时需考虑两种情况:

    1.若单链表为空表,则将新建节点置为头节点

    //若此时只在链表中插入头节点
    struct link *p = head;
    p = (struct link *)malloc(sizeof(struct link));  //让p指向新建节点创建的内存空间
    if(p == NULL){   //新建节点申请内存失败
        exit(0);
    }
    //此时head也指向头节点的地址
    p->next = NULL;     //因为没有后续节点,所以新建节点指针域置空

    2.链表非空,则将新建节点添加到表尾

    //此时已存在头节点,再插入一个节点(首节点)
    struct link *p = NULL,*pr = head;  
    p = (struct link *)malloc(sizeof(struct link));
    if(p == NULL){
        exit(0);
    }
    if(head == NULL){
        head = p;
    }else{
        while(pr->next != NULL){     //当头节点的指针域不为NULL
          pr = pr->next;             //pr指向下一个节点的地址
      }
        pr->next = p;                //使头节点的指针域存储下一个节点的地址
    }

    完整操作

    #include <stdio.h>
    #include <stdlib.h>
    struct link *AppendNode(struct link *head);
    void DisplayNode(struct link *head);
    void DeleteMemory(struct link *head);
    //定义结构体 
    struct link{
    	int data; 				//定义数据域 
    	struct link *next; 			//定义指针域 
    }; 
    int main(){
    	int i =0;         			//定义i,记录创建的节点数 
    	char c;							
    	struct link *head = NULL;		//创建头指针,初始化为NULL 
    	printf("DO you wang to append a new node(Y or N)?");
    	scanf(" %c",&c);				
    	while(c == 'Y' || c == 'y'){	//如果确定继续添加结点 
    		head = AppendNode(head);	//通过函数获得链表的地址,AppendNode函数返回的是链表的头指针
    		                            //可以根据头指针指向的地址来获取链表中保存的数据 
    		DisplayNode(head);			//根据头指针打印链表 
    		printf("DO you want to append a new node(Y or N)?");
    		scanf(" %c",&c);
    		i++; 
    	}
    	printf("%d new nodes hava been appended!\n",i);
    	DeleteMemory(head);			//释放占用的内存 
    }
    struct link *AppendNode(struct link *head){    //声明创建节点函数 
    	struct link *p = NULL,*pr = head;      //创建p指针,初始化为NULL;创建pr指针,通过pr指针来给指针域赋值 
    	int data ;
    	p = (struct link *)malloc(sizeof(struct link)) ; //为指针p申请内存空间,必须操作,因为p是新创建的节点 
    	if(p == NULL){			//如果申请内存失败,则退出程序 
    		printf("NO enough momery to allocate!\n");
    		exit(0);
    	}
    	if(head == NULL){		//如果头指针为NULL,说明现在链表是空表 
    		head = p;								//使head指针指向p的地址(p已经通过malloc申请了内存,所以有地址) 
    	}else{										//此时链表已经有头节点 ,再一次执行了AppendNode函数 
    												//注:假如这是第二次添加节点
    	                                  //因为第一次添加头节点时,pr = head,和头指针一样指向头节点的地址 
    		while(pr->next!= NULL){		//当pr指向的地址,即此时的p的指针域不为NULL(即p不是尾节点) 
    			pr = pr->next;	//使pr指向头节点的指针域
    		}
    		pr->next = p;	//使pr的指针域指向新键节点的地址,此时的next指针域是头节点的指针域 
    	}
    	printf("Input node data:");                   
    	scanf("%d",&data);
    	p->data = data; 			//给p的数据域赋值 
    	p->next = NULL;			//新添加的节点位于表尾,所以它的指针域为NULL 
    	return head;			//返回head的地址 
    }
    void DisplayNode(struct link *head){         	//输出函数,打印链表 
    	struct link *p = head;			// 定义p指针使其指向头节点 
    	int j = 1;									//定义j记录这是第几个数值 
    	while(p != NULL){		//因为p = p->next,所以直到尾节点打印结束 
    		printf("%5d%10d\n",j,p->data);			
    		p = p->next;		//因为节点已经创建成功,所以p的指向由头节点指向下一个节点(每一个节点的指针域都指向了下一个节点) 
    		j++;	
    	}
    }
    void DeleteMemory(struct link *head){			//释放资源函数 
    	struct link *p = head,*pr = NULL;	        //定义p指针指向头节点 
    	while(p != NULL){				//当p的指针域不为NULL 
    		pr = p;									//将每一个节点的地址赋值给pr指针 
    		p = p->next;			        //使p指向下一个节点 
    		free(pr);								//释放此时pr指向节点的内存 
    	}
    }

    第二种创建链表方式-优化

    #include <stdio.h> 
    #include <stdlib.h>
    struct Stu *create(int n);
    void print(struct Stu *head);
    struct Stu{
    	int id;
    	char name[50];
    	struct Stu *next;
    };
    int main(){
    	int n;
    	struct Stu *head = NULL;   //创建头指针 
    	printf("请输入你想要创建的节点个数:\n");
    	scanf("%d",&n);
    	head = create(n);
    	print(head);
    }
    struct Stu *create(int n){
    	struct Stu *head,*node,*end;   						//定义头节点,普通节点,尾节点 
    	head = (struct Stu *)malloc(sizeof(struct Stu)); 	//给头节点申请内存 
    	end = head;        									//若是空表,则头尾地址一致 
    	for(int i=0;i<n;i++){								//利用for循环向链表中添加数据 
    		node = (struct Stu *)malloc(sizeof(struct Stu));//给普通节点申请内存空间 
    		scanf("%d %s",&node->id,node->name);	//给数据域赋值 
    		end->next = node;					//让上一个节点的数据域指向当前节点 
    		end = node;     						//end指向当前节点,最终end指向尾节点 
    	}
    	end->next = NULL;                                   //给end的指针域置空 
    	return head;                                        //返回头节点的地址 
    }
    void print(struct Stu *head){
    	struct Stu *p = head;
    	int j =1;
    	p = p->next;  //不打印头节点的数据域中的值 
    	while(p != NULL){
    		printf("%d\t%d\t%s\n",j,p->id,p->name);
    		p = p->next;
    		j++;
    	}
    }

    前插法创建链表 --逆序输出

    struct link *create(int n){
         struct link *headnode ,*node;
         headnode = (struct link *)malloc(sizeof(struct link));   //为头节点申请内存 
    	 headnode ->next = NULL;     //让头节点的指针域置空 
    	 for(int i=0;i<n;i++){ 
    	 	node = (struct link *)malloc(sizeof(struct link));  //给新建节点申请内存 
    	 	scanf("%d",&node->data);       //新建节点数据域传值 
    	 	node->next = headnode->next;   //新建节点的数据域指向头节点 == 创建尾节点 
    	 	headnode->next = node;         //将新建节点数据域传给头节点 
    	 }	
    	 return headnode;  
    }

     

    删除节点

    void deleteNode(struct Stu *head,int n){         //删除n处的节点 
    	struct  Stu *p = head,*pr = head;
    	int i =0;
    	while(i<n&&p!=NULL){       //到达指定节点,此时p指向指定节点,pr指向上一节点 
    		pr = p;            //将p的地址赋值给pr
    		p = p->next;       //p指向下一节点
    		i++;
    	}
    	if(p!=NULL){               //当p不为空时,即p不能指向尾节点之后的节点
    		pr->next = p->next;
    		free(p);
    	} else{
    		printf("节点不存在!\n"); 
    	}
    } 

    我在这着重解释一下p->next = NULL和p!=NULL的区别,因为我刚开始也经常弄错!!

    • while(p->next != NULL) 循环结束时,此时p的位置是尾节点的位置,但如果用于输出函数的判断条件,则尾节点的数据不会输出。
    • while(p!=NULL) 循环结束时, 此时p指向的位置为尾节点的下一个节点,因为没有申请内存空间,所以是一个未知的区域。

    插入节点

    void insertNode(struct Stu *head,int n){    //插入节点 
    	struct Stu *p = head,*pr;
    	pr = (struct Stu*)malloc(sizeof(struct Stu));  //让pr指向新建节点申请的内存 
    	printf("input data:\n");
    	scanf("%d %s",&pr->id,pr->name);
    	int i = 0;
        //当插入位置是尾节点时,只要在尾节点后再插入一个节点,并让尾节点的指针域指向新建节点,新建节点的指针域置空
        while(i<n&&p!=NULL){             //使p指向将要插入节点的位置 
        	p = p->next;
    		i++;
    	}
    	if(p!=NULL){            //如果p没越界 
    		pr->next = p->next; //将新建节点的地址指向将要插入节点的后一个节点的地址 
    		p->next = pr;       //使插入节点指向新建节点 
    	}else{
    		printf("节点不存在!\n");
    	}
    }

    修改节点

    void change(struct Stu *head,int n){
    	struct Stu *p = head;
    	int i = 0;
    	while(i<n && p!=NULL){      //使p指向需修改节点 
    		p = p->next;
    		i++;
    	}
    	if(p != NULL){             
    	printf("请输入修改之后的值:\n");
    	scanf("%d %s",&p->id,p->name);	
    	}else{
    		printf("节点不存在!\n");
    	} 

    链表的逆序

     

    思路:假如此时链表有两个有效节点,头节点为0号,中间的节点为1号,尾节点为2号

    1.定义三个指针pf指向链表的头节点(0号),tmp,pb初始化为NULL

    2.让pb指向pf的下一个节点(1号),并将此时头节点的指针域置空(变为尾节点)

    3.第一次while循环,让tmp指向pb(1号),然后让pb指向下一个节点,再让tmp让1号节点的指针域(tmp->next = pf)指向pf(上一个节点)(0号),再将pf指向tmp(1号)(pf = tmp)

    4.第二次while循环,让tmp指向pb(2号),然后让pb指向下一个节点,此时pb==NULL,所以这是最后一次循环,再让tmp让2号节点的指针域(tmp->next = pf)指向pf(1号),再将pf指向tmp(2号)

     5.此时链表逆序完成,让头指针指向首节点(2号),返回头指针即可

                                                                              逆序后

    STU *link_reversed_order(STU *head)
    {
        STU *pf = NULL, *pb = NULL, *tmp = NULL; 
        pf = head;  //将头节点的地址赋值给pf 
        if(head == NULL) { //如果链表为空 
            printf("链表为空,不需要逆序!\n");
            return head;
        } else if(head->next == NULL) {  //如果只有一个节点 
            printf("链表只有一个节点,不需要逆序!\n");
            return head;
        } else {
            pb = pf->next;  //pb指向pf的下一个节点 
            head->next = NULL; //头节点的指针域置空(变为尾节点) 
            while(pb != NULL)	//当pb不为空时 
            {
                tmp = pb;	//将pb的地址赋值给temp 
                pb = pb->next; //pb指向下一个节点 
                tmp->next = pf;	//pb的上一个节点的指针域指向pf 
                pf = tmp;	//让pf指向tmp 
            }
            head = pf;
            return head;
        }    
    }*/

    所有操作

    #include <stdio.h> 
    #include <stdlib.h>
    struct Stu *create(int n);
    void print(struct Stu *head);
    void deleteNode(struct Stu *head,int n);
    void insertNode(struct Stu *head,int n);
    void change(struct Stu *head,int n);
    struct Stu{
    	int id;
    	char name[50];
    	struct Stu *next;
    };
    int main(){
    	int n,j,in,cn;
    	char c;
    	struct Stu *head = NULL;   //创建头指针 
    	printf("请输入你想要创建的节点个数:\n");
    	scanf("%d",&n);
    	head = create(n);
    	print(head);
    	while(true){
    	printf("请选择你想要执行的操作:\n");
    	printf("1.插入节点\n2.删除节点\n3.修改节点\n4.退出程序\n");
    	scanf(" %c",&c);
    	if(c =='1'){
    	printf("你想要在哪插入节点:\n");
    	scanf("%d",&in);
    	insertNode(head,in);
    	print(head); 
    	}else if(c == '2'){
    	printf("你想要删除哪个节点的数据:\n");
    	scanf("%d",&j);
    	deleteNode(head,j);
    	print(head);
    	}else if(c =='3'){
    	printf("你想要修改哪个节点的数据:\n");
    	scanf("%d",&cn);
    	change(head,cn);
    	print(head); 
    	}else if(c =='4'){
    		exit(0);
    	} 		
     } 
    }
    struct Stu *create(int n){
    	struct Stu *head,*node,*end;   						//定义头节点,普通节点,尾节点 
    	head = (struct Stu *)malloc(sizeof(struct Stu)); 	//给头节点申请内存 
    	//head->id = n;										//头节点的数据域保存链表的长度 
    	end = head;        									//若是空表,则头尾地址一致 
    	for(int i=0;i<n;i++){								//利用for循环向链表中添加数据 
    		node = (struct Stu *)malloc(sizeof(struct Stu));//给普通节点申请内存空间 
    		scanf("%d %s",&node->id,node->name);			//给数据域赋值 
    		end->next = node;								//让上一个节点的数据域指向当前节点 
    		end = node;     								//end指向当前节点,最终end指向尾节点 
    	}
    	end->next = NULL;                                   //给end的指针域置空 
    	return head;                                        //返回头节点的地址 
    }
    void print(struct Stu *head){
    	struct Stu *p = head;
    	int j =1;
    	p = p->next;  //不打印头节点的数据域中的值 
    	while(p != NULL){
    		printf("%d\t%d\t%s\n",j,p->id,p->name);
    		p = p->next;
    		j++;
    	}
    }
    void deleteNode(struct Stu *head,int n){         //删除n处的节点 
    	struct  Stu *p = head,*pr = head;
    	int i =0;
    	while(i<n&&p!=NULL){       //到达指定节点,此时p指向指定节点,pr指向上一节点 
    		pr = p;
    		p = p->next;
    		i++;
    	}
    	if(p!=NULL){
    		pr->next = p->next;
    		free(p);
    	} else{
    		printf("节点不存在!\n"); 
    	}
    } 
    void insertNode(struct Stu *head,int n){    //插入节点 
    	struct Stu *p = head,*pr;
    	pr = (struct Stu*)malloc(sizeof(struct Stu));  //让pr指向新建节点申请的内存 
    	printf("input data:\n");
    	scanf("%d %s",&pr->id,pr->name);
    	int i = 0;
        //当插入位置是尾节点时,只要在尾节点后再插入一个节点,并让尾节点的指针域指向新建节点,新建节点的指针域置空
        while(i<n&&p!=NULL){             //使p指向将要插入节点的位置 
        	p = p->next;
    		i++;
    	}
    	if(p!=NULL){            //如果p没越界 
    		pr->next = p->next; //将新建节点的地址指向将要插入节点的后一个节点的地址 
    		p->next = pr;       //使插入节点指向新建节点 
    	}else{
    		printf("节点不存在!\n");
    	}
    }
    void change(struct Stu *head,int n){
    	struct Stu *p = head;
    	int i = 0;
    	while(i<n && p!=NULL){      //使p指向需修改节点 
    		p = p->next;
    		i++;
    	}
    	if(p != NULL){             
    	printf("请输入修改之后的值:\n");
    	scanf("%d %s",&p->id,p->name);	
    	}else{
    		printf("节点不存在!\n");
    	} 	 
    } 

     

     

    展开全文
  • 主要介绍了JAVA 数据结构链表操作循环链表的相关资料,需要的朋友可以参考下
  • 链表操作实例

    2016-11-02 21:44:01
    该代码为链表操作实例,包含链表创建,增加节点,删除节点,倒序节点等。
  • PHP链表操作简单示例

    2021-01-20 00:22:18
    本文实例讲述了PHP链表操作。分享给大家供大家参考,具体如下: 在php中运行数据结构,基本都是用数组模拟的,只是用一直思想而已。 今天遇到的这个问题是,两个链表进行合并。 链表合并效果图 问题描述:A链表是...
  • 链表操作,用类实现了对链表的增、删、改、查等操作。
  • 本文给大家分享了个人对于C++中链表操作的理解,并对具体实例进行了分析,是篇非常不错的学习链表操作的文章,希望大家能够喜欢
  • 链表是计算机科学里面应用最广泛的数据结构之一。这篇文章主要介绍了使用python实现链表操作,需要的朋友可以参考下
  • 易语言链表操作类源码,多种方式实现链表,单向双头链表。
  • 链表操作代码

    2013-04-16 21:23:29
    内有很多链表操作,是我做课设的时候写的,c的初学者可以看看我的代码,还是有一点帮助的
  • 使用C语言实现了基本的链表操作,为处理链式结构的数据提供支持。
  • 使用的C语言和ege库编写的链表操作演示程序源码,对于链表的几个基本操作都具有演示动画,且数据全部随机产生
  • 双循环链表操作

    2013-01-08 14:37:04
    双循环链表建立,删除,插入等各种操作,内核链表操作描述等
  • 链表操作总结

    千次阅读 2018-04-03 21:28:36
    链表操作总结(创建,遍历,就地逆置,删除偶数结点…) 1、随机产生或键盘输入一组元素,建立一个带头结点的单向链表(无序)。 2、遍历单向链表(显示)。 3、把单向链表中元素逆置(不允许申请新的结点空间)。 ...

    链表操作总结(创建,遍历,就地逆置,删除偶数结点…)

    1、随机产生或键盘输入一组元素,建立一个带头结点的单向链表(无序)。
    2、遍历单向链表(显示)。
    3、把单向链表中元素逆置(不允许申请新的结点空间)。
    4、在单向链表中删除所有的偶数元素(值为偶数)结点。
    5、编写在非递减有序链表中插入一个元素使链表元素仍有序的函数,并利用该函数建立一个非递减有序单向链表。
    6、利用算法5建立两个非递减有序单向链表,然后合并成一个非递增链表。
    7、利用算法5建立两个非递减有序单向链表,然后合并成一个非递减链表。
    8、编写一个主函数,调试上述算法。
    所用函数::
    1.创建带头节点的单向链表,输入一组元素
    2.显示单向链表
    3.逆置元素(不申请新节点)
    4.删除所有值为偶数的节点
    5.递增数列中插入元素仍有序
    6.建立两个递增的有序单向链表,合并成一个递增
    7.建立两个递减的有序单向链表,合并成一个递减

    //
    //  main.cpp
    //  Listlist
    //
    //  Created by 王子谖on 2018/4/2.
    //  Copyright © 2018 王子谖. All rights reserved.
    //
    /```
    #include <iostream>
    #include <stdlib.h>
    #include <stdio.h>
    using namespace std;
    
    /*
     实验内容:
     1、随机产生或键盘输入一组元素,建立一个带头结点的单向链表(无序)。
     2、遍历单向链表(显示)。
     3、把单向链表中元素逆置(不允许申请新的结点空间)。
     4、在单向链表中删除所有的偶数元素(值为偶数)结点。
     5、编写在非递减有序链表中插入一个元素使链表元素仍有序的函数,并利用该函数建立一个非递减有序单向链表。
     6、利用算法5建立两个非递减有序单向链表,然后合并成一个非递增链表。
     7、利用算法5建立两个非递减有序单向链表,然后合并成一个非递减链表。
     8、编写一个主函数,调试上述算法。
    所用函数::
     1.创建带头节点的单向链表,输入一组元素
     2.显示单向链表
     3.逆置元素(不申请新节点)
     4.删除所有值为偶数的节点
     5.递增数列中插入元素仍有序
     6.建立两个递增的有序单向链表,合并成一个递减
     7.建立两个递减的有序单向链表,合并成一个递增
     */
    
    
    typedef struct node
    {
        int data;
        struct node *next;
    }LNode,*LinkList;
    
    //1.创建带头节点的单向链表
    void init(LinkList &L)
    {
        L=(LinkList)malloc(sizeof(LNode));
        L->next=NULL;
    }
    //1.输入一组数,头插法
    void insert1(LinkList &L,int m)
    {
        LinkList p;
        p=(LinkList)malloc(sizeof(LNode));
        p->data=m;
        p->next=L->next;
        L->next=p;
    }
    //1.输入一组数,尾插法
    void insert2(LinkList &L,int m)
    {
        LinkList p,q;
        p=(LinkList)malloc(sizeof(LNode));
        p->data=m;
        p->next=NULL;
        q=L;
        if(L==NULL) //首节点为空
        {   L=p;  //L指向p
            p->next=NULL;
        }
        else{
            while (q->next!=NULL)
            {
                q=q->next;//到尾巴时
            }
            q->next=p; //插入结点
        }
    
    }
    //2.显示单向链表
    void print(LinkList &L)
    {
        LinkList p;
        p=(LinkList)malloc(sizeof(LNode));
        p=L->next;
        while(p)
        {   printf("%d ",p->data);
            p=p->next;
        }
        printf("\n");
    }
    //3.逆置元素(不申请新节点)
    void contrary(LinkList &L){
        LinkList p,q;
        p=(LinkList)malloc(sizeof(LNode));
        q=(LinkList)malloc(sizeof(LNode));
        p=L->next;
        L->next=NULL;//将链断开
        while (p) {
            q=p->next;//q永远在p的后一个
            p->next=L->next;//将p连在L的后面,先把尾巴连上
            L->next=p;//将p连在L的后面,再把前面接上
            p=q;//p指向下一个,即q所在的位置
        }
    }
    //4.删除所有值为偶数的节点
    void delet(LinkList &L)
    {
        LinkList p,q;
        p=(LinkList)malloc(sizeof(LNode));
        q=(LinkList)malloc(sizeof(LNode));
        p=L->next;
        q=L;
        while(p)
        {
               if((p->data)%2!=0)
                {
                     p=p->next;
                     q=q->next;
                }
               else{
                   q->next=p->next;//删除节点
                   p=p->next;
               }
        }
    }
    //5.递增数列中插入元素仍有序
    void insert3(LinkList &L,int c)
    {
        LinkList p,q,s;
        s=(LinkList)malloc(sizeof(LNode));
        p=(LinkList)malloc(sizeof(LNode));
        q=(LinkList)malloc(sizeof(LNode));
        p=L->next;
        q=L;
        s->data=c;
        while((p->data<=c)&&(p->next!=NULL))//条件是p->next!=null
        {   p=p->next;
            q=q->next;
        }
        if(p->next==NULL)//特殊考虑p指向结尾
        {
            p->next=s;
            s->next=NULL;
        }
        else{
            s->next=p;
            q->next=s;
        }
    
    }
    //6.建立两个递增的有序单向链表,合并成一个递减(建立两个递增的有序单向链表,合并成一个递增,再就地逆置元素)
    LinkList inde(LinkList &L,LinkList &J)
    {
    
        LinkList Q;
        init(Q);
        LinkList pa,pb,pc;
        pa=(LinkList)malloc(sizeof(LNode));
        pb=(LinkList)malloc(sizeof(LNode));
        pc=(LinkList)malloc(sizeof(LNode));
        pa=L->next;
        pb=J->next;
        pc=Q;
        pc->next=NULL;
        while(pa&&pb)
        {
            if(pa->data<=pb->data)
            {
                pc->next=pa;
                pc=pa;
                pa=pa->next;
            }
            else {
                pc->next=pb;
                pc=pb;
                pb=pb->next;
            }
        }
        if(pa)
        {
            pc->next=pa;
        }
        else
        {
            pc->next=pb;
        }
        free(L);
        free(J);
    
        return Q;
    }
    //7.建立两个递减的有序单向链表,合并成一个递增(建立两个递减的有序单向链表,合并成一个递减,再就地逆置元素)
    LinkList dein(LinkList &L,LinkList &J)
    {
    
        LinkList Q;
        init(Q);
        LinkList pa,pb,pc;
        pa=(LinkList)malloc(sizeof(LNode));
        pb=(LinkList)malloc(sizeof(LNode));
        pc=(LinkList)malloc(sizeof(LNode));
        pa=L->next;
        pb=J->next;
        pc=Q;
        pc->next=NULL;
        while(pa&&pb)
        {
            if(pa->data>=pb->data)
            {
                pc->next=pa;
                pc=pa;
                pa=pa->next;
            }
            else {
                pc->next=pb;
                pc=pb;
                pb=pb->next;
            }
        }
        if(pa)
        {
            pc->next=pa;
        }
        else
        {
            pc->next=pb;
        }
        free(L);
        free(J);
    
        return Q;
    }
    
    
    
    
    int main()
    {
        LinkList S;
    int number,data;
        init(S);//创建带头节点的链表
        printf("创建带头节点的链表\n");
        printf("输入插入元素的个数\n");
        scanf("%d",&number);//输入插入元素的个数
        for(int i=0;i<number;i++)
        {
            printf("尾插法,依次输入元素,以回车分隔,输入元素第%d个\n",i+1);
            scanf("%d",&data);
            //insert1(S,data);//1.头插法,输入元素
            insert2(S,data);//1.尾插法,输入元素
        }
        printf("\n显示带头节点的链表\n");
        print(S);// 2.显示单向链表
        printf("显示逆置的链表\n");
        contrary(S);//3.逆置元素(不申请新节点)
        print(S);// 2.显示单向链表
        printf("删除所有值为偶数的节点\n");
        delet(S); // 4.删除所有值为偶数的节点
        print(S);// 2.显示单向链表
    
        LinkList U;
        init(U);//创建带头节点的链表
        printf("输入插入元素的个数\n");
        scanf("%d",&number);//输入插入元素的个数
        for(int i=0;i<number;i++)
        {
            printf("尾插法,依次输入有序递增元素,以回车分隔,输入元素第%d个\n",i+1);
            scanf("%d",&data);
            //insert1(U,data);//1.头插法,输入元素
            insert2(U,data);//1.尾插法,输入元素
        }
        printf("输入要插入的元素\n");
        int k;
        scanf("%d",&k);//要插入递增数列的k
        insert3(U,k);//5.递增数列中插入元素仍有序
        print(U);// 2.显示单向链表
    
    
        LinkList V,W,Res;
        int m,n;
        init(V);//创建带头节点的链表
        init(W);//创建带头节点的链表
        printf("输入两个链表的元素个数分别为m,n\n");
        scanf("%d%d",&m,&n);//输入插入元素的个数
        printf("请输入第一个链表的元素\n");
        for(int i=0;i<m;i++)
        {
            printf("尾插法,依次输入有序递增元素,以回车分隔,输入元素第%d个\n",i+1);
            scanf("%d",&data);
            //insert1(U,data);//1.头插法,输入元素
            insert2(V,data);//1.尾插法,输入元素
        }
        printf("请输入第二个链表的元素\n");
        for(int i=0;i<n;i++)
        {
            printf("尾插法,依次输入有序递增元素,以回车分隔,输入元素第%d个\n",i+1);
            scanf("%d",&data);
            //insert1(U,data);//1.头插法,输入元素
            insert2(W,data);//1.尾插法,输入元素
        }
            Res=inde(V,W);//6.建立两个递增的有序单向链表,合并成一个递减
            contrary(Res);//3.逆置元素(不申请新节点)
            print(Res);// 2.显示单向链表
    
        LinkList E,F,Re;
        int a,b;
        init(E);//创建带头节点的链表
        init(F);//创建带头节点的链表
        printf("输入两个链表的元素个数分别为m,n\n");
        scanf("%d%d",&a,&b);//输入插入元素的个数
        printf("请输入第一个链表的元素\n");
        for(int i=0;i<a;i++)
        {
            printf("尾插法,依次输入有序递减元素,以回车分隔,输入元素第%d个\n",i+1);
            scanf("%d",&data);
            //insert1(U,data);//1.头插法,输入元素
            insert2(E,data);//1.尾插法,输入元素
        }
        printf("请输入第二个链表的元素\n");
        for(int i=0;i<b;i++)
        {
            printf("尾插法,依次输入有序递减元素,以回车分隔,输入元素第%d个\n",i+1);
            scanf("%d",&data);
            //insert1(U,data);//1.头插法,输入元素
            insert2(F,data);//1.尾插法,输入元素
        }
        Re=dein(E,F);//7.建立两个递减的有序单向链表,合并成一个递增
        contrary(Re);//3.逆置元素(不申请新节点)
        print(Re);// 2.显示单向链表
    
    
    
        return 0;
    }

    版权声明:本文为博主原创文章,未经博主允许不得转载

    展开全文
  • Js实现链表操作

    千次阅读 2020-05-13 11:57:27
    Js实现链表操作 JavaScript实现链表主要操作,包括创建链表、遍历链表、获取链表长度、获取第i个元素值、获取倒数第i个元素值、插入节点、删除节点、有序链表合并、有序链表交集。 创建链表 class Node{ ...

    Js实现链表操作

    JavaScript实现链表主要操作,包括创建链表、遍历链表、获取链表长度、获取第i个元素值、获取倒数第i个元素值、插入节点、删除节点、有序链表合并、有序链表交集。

    创建链表

    class Node{
        constructor(data){
            this.data = data;
            this.next = null;
        }
    }
    
    function createLinkList(arr){
        var L = new Node(null);
        var p = L;
        arr.forEach(v => {
            p.next = new Node(v);
            p=p.next;
        })
        return L;
    }
    
    (function(){
        var arr = [1, 3, 5, 7, 9]; // 为了方便,将数组转化为链表
        var L = createLinkList(arr);
    })
    

    遍历链表

    function traverseLinkList(L){
        var p = L.next;
        while(p){
            console.log(p.data);
            p = p.next;
        }
    }
    

    获取链表长度

    function getLinkListLength(L){
        var p = L.next;
        var n = 0;
        while(p) {
            ++n;
            p = p.next;
        };
        return n;
    }
    

    获取第i个元素值

    function getIndexValue(L, index){
        var p = L.next;
        if(index <=0 ) return null;
        var n = 0;
        while(p) {
            ++n;
            if(index === n) return p.data;
            p = p.next;
        };
        return null;
    }
    

    获取倒数第i个元素值

    function getReverseIndexValue(L, index){
        var p = L.next;
        if(index <=0 ) return null;
        var cursor = L;
        var n = 0;
        while(p) {
            ++n;
            if(n >= index) cursor = cursor.next;
            p = p.next;
        };
        if(n < index) return null;
        return cursor.data;
    }
    

    插入节点

    function insertNode(L, posistion, value){
        var p = L.next;
        var i = 0;
        while(p){
            ++i;
            if(i === posistion) {
                var saveNextP = p.next;
                p.next = new Node(value);
                p.next.next = saveNextP;
                return true;
            }
            p = p.next;
        }
        return false;
    }
    

    删除节点

    function deleteNode(L, posistion){
        var p = L.next;
        var preNode = L;
        var i = 0;
        while(p){
            ++i;
            if(i === posistion) {
                preNode.next = p.next;
                p = null;
                return true;
            }
            preNode = preNode.next;
            p = p.next;
        }
        return false;
    }
    

    有序链表合并

    function mergeLinkList(L1, L2){
        var p1 = L1.next;
        var p2 = L2.next;
        var L3 = new Node(null);
        var p3 = L3;
        while(p1 && p2){
            if(p1.data < p2.data){
                p3.next = new Node(p1.data);
                p3 = p3.next;
                p1 = p1.next;
            }else{
                p3.next = new Node(p2.data);
                p3 = p3.next;
                p2 = p2.next;
            }
        }
        while(p1) {
            p3.next = new Node(p1.data);
            p3 = p3.next;
            p1 = p1.next;
        }
        while(p2){
            p3.next = new Node(p2.data);
            p3 = p3.next;
            p2 = p2.next;
        }
        return L3;
    }
    

    有序链表交集

    function unionLinkList(L1, L2){
        var p1 = L1.next;
        var p2 = L2.next;
        var L3 = new Node(null);
        var p3 = L3;
        while(p1 && p2){
            if(p1.data === p2.data){
                p3.next = new Node(p1.data);
                p3 = p3.next;
                p1 = p1.next;
                p2 = p2.next;
            }else if(p1.data < p2.data){
                p1 = p1.next;
            }else{
                p2 = p2.next;
            }
        }
        p3.next = null;
        return L3;
    }
    

    示例

    class Node{
        constructor(data){
            this.data = data;
            this.next = null;
        }
    }
    
    
    function createLinkList(arr){
        var L = new Node(null);
        var p = L;
        arr.forEach(v => {
            p.next = new Node(v);
            p=p.next;
        })
        return L;
    }
    
    function traverseLinkList(L){
        var p = L.next;
        while(p){
            console.log(p.data);
            p = p.next;
        }
    }
    
    function getLinkListLength(L){
        var p = L.next;
        var n = 0;
        while(p) {
            ++n;
            p = p.next;
        };
        return n;
    }
    
    function getIndexValue(L, index){
        var p = L.next;
        if(index <=0 ) return null;
        var n = 0;
        while(p) {
            ++n;
            if(index === n) return p.data;
            p = p.next;
        };
        return null;
    }
    
    function getReverseIndexValue(L, index){
        var p = L.next;
        if(index <=0 ) return null;
        var cursor = L;
        var n = 0;
        while(p) {
            ++n;
            if(n >= index) cursor = cursor.next;
            p = p.next;
        };
        if(n < index) return null;
        return cursor.data;
    }
    
    function insertNode(L, posistion, value){
        var p = L.next;
        var i = 0;
        while(p){
            ++i;
            if(i === posistion) {
                var saveNextP = p.next;
                p.next = new Node(value);
                p.next.next = saveNextP;
                return true;
            }
            p = p.next;
        }
        return false;
    }
    
    function deleteNode(L, posistion){
        var p = L.next;
        var preNode = L;
        var i = 0;
        while(p){
            ++i;
            if(i === posistion) {
                preNode.next = p.next;
                p = null;
                return true;
            }
            preNode = preNode.next;
            p = p.next;
        }
        return false;
    }
    
    function mergeLinkList(L1, L2){
        var p1 = L1.next;
        var p2 = L2.next;
        var L3 = new Node(null);
        var p3 = L3;
        while(p1 && p2){
            if(p1.data < p2.data){
                p3.next = new Node(p1.data);
                p3 = p3.next;
                p1 = p1.next;
            }else{
                p3.next = new Node(p2.data);
                p3 = p3.next;
                p2 = p2.next;
            }
        }
        while(p1) {
            p3.next = new Node(p1.data);
            p3 = p3.next;
            p1 = p1.next;
        }
        while(p2){
            p3.next = new Node(p2.data);
            p3 = p3.next;
            p2 = p2.next;
        }
        return L3;
    }
    
    function unionLinkList(L1, L2){
        var p1 = L1.next;
        var p2 = L2.next;
        var L3 = new Node(null);
        var p3 = L3;
        while(p1 && p2){
            if(p1.data === p2.data){
                p3.next = new Node(p1.data);
                p3 = p3.next;
                p1 = p1.next;
                p2 = p2.next;
            }else if(p1.data < p2.data){
                p1 = p1.next;
            }else{
                p2 = p2.next;
            }
        }
        p3.next = null;
        return L3;
    }
    
    (function(){
        var arr = [1, 3, 5, 7, 9]; // 为了方便,将数组转化为链表
        console.log("创建链表");
        var L = createLinkList(arr);
        console.log(L);
        console.log("遍历链表");
        traverseLinkList(L);
        console.log("获取链表长度");
        var n = getLinkListLength(L);
        console.log(n);
        console.log("获取链表第2个元素值");
        var v = getIndexValue(L, 2);
        console.log(v);
        console.log("获取链表倒数第2个元素值");
        var v = getReverseIndexValue(L, 2);
        console.log(v);
        console.log("在第1个节点后插入值为2的节点");
        insertNode(L, 1, 2);
        traverseLinkList(L);
        console.log("删除第2个节点");
        deleteNode(L, 2);
        traverseLinkList(L);
        console.log("创建两个有序链表");
        console.log("L1");
        var L1 = createLinkList([1, 5, 7, 10, 30]);
        traverseLinkList(L1);
        console.log("L2");
        var L2 = createLinkList([1, 3, 7, 9, 20, 100]);
        traverseLinkList(L2);
        console.log("合并有序链表,不改变原链表,返回一个新链表");
        var L3 = mergeLinkList(L1, L2);
        traverseLinkList(L3);
        console.log("取有序链表交集,不改变原链表,返回一个新链表");
        var L3 = unionLinkList(L1, L2);
        traverseLinkList(L3);
    })();
    

    每日一题

    https://github.com/WindrunnerMax/EveryDay
    
    展开全文
  • 单向链表操作类模板实现代码,代码内包含结点类、链表操作类的实现以及主测试函数等;其中链表操作包含结点插入、删除、获取等;
  • C语言链表操作

    2018-04-12 21:12:35
    通过c语言实现了链表的基础操作,有创建链表,添加节点,删除节点,链表中元素的比较,计算链表的长度等操作
  • 数据结构——链表操作合集,大部分链表操作都在这里了
  • 利用链表操作成员函数insertlist,deletelist.outputlist,形成以下的简单链表操作程序。
  • 主要介绍了Java 数据结构链表操作的相关资料,并附实例代码,需要的朋友可以参考下
  • 大连理工 数据结构上机 链表操作
  • 【Python学习】【数据结构】之链表(python变量标识本质、链表操作)链表Python变量标识本质链表操作 链表 一个简单的链表形式如下: 一个节点分为数据区和链接区,数据区存储数据好说,而链接区需要的是存储地址,...
  • 链表基础学习,基本的知识学习
  • 数据结构线性链表操作 链表结点的增添 删除
  • C语言实现 链表操作

    2010-11-06 13:18:49
    C语言实现 链表操作,链表 建立 输出 删除 插入,整个程序代码,看完后会让你对链表操作有更深的体悟
  • Lua语言 链表操作实现

    2015-07-16 11:50:52
    Lua语言 链表操作实现。 如果对代码有疑问,欢迎随时联系我!
  • C语言学习,链表操作小结! 写更多的代码,用链表、用链表! 不过瘾!
  • C++ 链表操作大全

    2011-03-30 17:35:15
    C++链表操作大全:如何创建链表,删除节点,添加节点等
  • c++模板实现双向链表操作如逆序建立双向链表,插入结点等。
  • 用模板实现链表的建立删除等操作,可以根据具体情况稍作修改即可实现链表操作,或直接使用,我在链表的学习和类模板的学习和以后的编程时这种链表构造思想觉得挺好的,有点面向对象的意思……粗浅的理解呵呵!

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 499,980
精华内容 199,992
关键字:

链表操作