精华内容
下载资源
问答
  • 介绍c语言链表的使用方法,方便使用学习
  • c语言链表

    2019-09-22 20:11:20
    本周对链表的使用有了更深的理解,具体在链表的创建,求链表的长度。 创建 之前对链表的创建停留在一种很低端的创建方法,经过这周学习了解到有头插和尾插之分,。头插是从头链表的头部插入,尾插是从链表的尾部插入...


    本周对链表的使用有了更深的理解,具体在链表的创建,求链表的长度。

    创建

    之前对链表的创建停留在一种很低端的创建方法,经过这周学习了解到有头插和尾插之分,。头插是从头链表的头部插入,尾插是从链表的尾部插入。
    具体代码如下:
    头插:

    #include<stdio.h>
    #include<stdlib.h>
    typedef struct node{
     int data;
    struct node* next;
    }LNode,*LinkList;
    Linklist create(int i){ 
    LNode *pnew,*head,*p=head;
    head=(LinkList) malloc  sizeof(LNode);
    head->next=NULL;
    int j;
    for(j=0;j<i;j++){
    pnew=(LinkList) malloc  sizeof(LNode);
    scanf("%d",&pnew->data);
    pnew->next=p->next;
    p->next=pnew;
    }
    return head;
    }
    

    尾插:

    typedef struct node{
    int data;
    struct node* next;
    }LNode,*LinkList;
    
    LinkList create(int i){
    int j=0;
    LinkList Head=(LinkList)malloc(sizeof(LNode));
    Head->next=NULL;
    LNode *s,*p=Head;
    while(j++<i){
    	s=(LinkList)malloc(sizeof(LNode));
    	scanf("(%d,%d)",&s->i,&s->j);
    	s->next=NULL;
    	p->next=s;
    	p=s;
      }
    return Head;
    } 
    

    求链表长度

    int length(LinkList head){
    int i=0;
    LNode* p=head;
    while(p->next!=NULL){
    	i++;
    	p=p->next;
    }
    return i;
    }
    

    我用多项式实现了多项式的相乘
    代码:

    #include<stdio.h>
    #include<stdlib.h>
    typedef struct node{
    int i;
    int j;
    struct node* next;
    }LNode,*LinkList;
    
    LinkList create(int i){
    int j=0;
    LinkList Head=(LinkList)malloc(sizeof(LNode));
    Head->next=NULL;
    LNode *s,*p=Head;
    while(j++<i){
        s=(LinkList)malloc(sizeof(LNode));
        scanf("(%d,%d)",&s->i,&s->j);
        s->next=NULL;
        p->next=s;
        p=s;
      }
    return Head;
    } 
    
    //打印 
    void print(LinkList Head){
    LNode *q=Head->next;
    int index1=0;
    while(q!=NULL){
        if(q->i!=0){
            index1=1;
            break;
        }
        if(q->next!=NULL){
            q=q->next;
        }else{
            break;
        }
    }
    if(index1!=1){
        printf("0");
    }
    int index=0;
    while(q!=NULL){
        //系数为0时 
        //第一个数字 
        //系数为0时 
        if(q->i==0){
            printf("");
        }
        //系数为1时 
        if(q->i==1){
            if(q->j==0&&index==0){
            printf("1");
         } 
            if(q->j==0&&index!=0){
            printf("+1");
         } 
         if(q->j==1&&index==0){
            printf("X");
         }
         if(q->j==1&&index!=0){
            printf("+X");
         }
         if(q->j!=1&&index==0){
            printf("X^%d",q->j);
            }
        if(q->j!=1&&index!=0){
            printf("+X^%d",q->j);
            }
        } 
         
        //系数为-1时 
        if(q->i==-1){
            if(q->j==0){
            printf("-1");
         } 
         if(q->j==1){
            printf("-X");
         }
         if(q->j!=1&&q->j!=0){
            printf("-X^%d",q->j);
            }
        } 
        //系数非0非1非-1时 
        if(q->i!=0&&q->i!=1&&q->i!=-1){
            if(q->j==0&&index==0){
                printf("%d",q->i);
            }
            if(q->j==0&&index!=0){
                printf("%+d",q->i);
            }
            if(q->j==1&&index==0){
                printf("%dX",q->i);
            }
             if(q->j==1&&index!=0){
                printf("%+dX",q->i);
            }
            if(q->j!=0&&q->j!=1&&index==0){
                printf("%dX^%d",q->i,q->j);
            }
            if(q->j!=0&&q->j!=1&&index!=0){
                printf("%+dX^%d",q->i,q->j);
            }
        }
        q=q->next;
        index=1;
     }
    }
    
    //链表的长度 
    int length(LinkList head){
    int i=0;
    LNode* p=head;
    while(p->next!=NULL){
        i++;
        p=p->next;
    }
    return i;
    }
    //乘法 
    LinkList mul(LinkList head1,LinkList head2){
    LinkList head,head4;//头指针
    head4=(LinkList)malloc(sizeof(LNode));
    head=(LinkList)malloc(sizeof(LNode));
    head->next=head->next=NULL;
    LNode *p=head,*pnew,*m=head1->next,*n=head2->next,*q=head4,*temp;
    int i,j;
    //创建一个新链表用来存储相乘后的数据 
    temp=n;
    for(i=0;i<(length(head1));i++){
    n=temp;
    for(j=0;j<(length(head2));j++){
      pnew=(LinkList)malloc(sizeof(LNode));
      pnew->i=(m->i)*(n->i);
      pnew->j=(m->j)+(n->j);
      pnew->next=NULL;
      p->next=pnew;
      p=pnew;
      if(n->next!=NULL){
        n=n->next;
      }else{
        break;
       }
    }
      if(m->next!=NULL){
        m=m->next;
      }else{
        break;
      }
    }
    //创建一个链表用来表示最终结果 
    pnew=(LinkList)malloc(sizeof(LNode));
    p=head->next;
    pnew->i=p->i;
    pnew->j=p->j;
    pnew->next=NULL;
    q->next=pnew;
    q=pnew;
    if(p->next!=NULL){
    p=p->next;
    }else{
    return head4;
    }
    temp=p;
    for(i=1;i<length(head);i++){
    //对指数相同的数据进行合并 
    while(p!=NULL){
        if(p->j==q->j){
            q->i=(p->i)+(q->i);
            p->i=0;
      }
        if(p->next!=NULL){
            p=p->next;
         }else{
            break; 
         }
    }
        p=temp; 
        //将新指数加到链表中 
        if(p->i!=0){
        pnew=(LinkList)malloc(sizeof(LNode));
        pnew->i=p->i;
        pnew->j=p->j;
        pnew->next=NULL;
        q->next=pnew;
        q=pnew; 
        if(p->next!=NULL){
            p=p->next;
         }else{
            return head4;
         }
     }else{
        if(p->next!=NULL){
            p=p->next;
         }else{
            return head4;
         }
      } 
      temp=p;
    }
     return head4;
    }
    
    //排序
    LinkList sort(LinkList head){
    LinkList head1=(LinkList)malloc(sizeof(LNode));
    LNode *num,*q=head->next->next;
    int i,j,temp;
    for(i=0;i<length(head);i++){
     num=head->next;
     q=head->next->next;
    for(j=0;j<length(head)-i;j++){
        if((num->j)>(q->j)){
            temp=num->j;
            num->j=q->j;
            q->j=temp;
            temp=num->i;
            num->i=q->i;
            q->i=temp;
          }
          if(num->next){
            num=num->next;
          }else{
            break;
          }
          if(q->next){
            q=q->next;
          }else{
            break;
          }
      }
    }
     return head;
    } 
    
    int main(){
    int i,j;
    scanf("%d",&i);
    getchar();
    LinkList head1=create(i);
    scanf("%d",&j);
    getchar();
    LinkList head2=create(j);
    LinkList head=mul(head1,head2);
    LinkList head3=sort(head);
    print(head3);
    } 
    
    展开全文
  • C语言 链表数据排序

    千次阅读 2021-02-25 22:04:49
    C语言使用链表时,有些时候会对链表数据进行排序。下边介绍使用链表时可用排序方法,冒泡排序和选择排序。 此链表排序仅对链表数据进行排序,如果想进行对整个结构体排序,也就是利用数据顺序来调整节点...

    C语言使用链表时,有些时候会对链表中的数据进行排序。下边介绍使用链表时可用的排序方法,冒泡排序和选择排序。

    此链表排序仅对链表中的数据进行排序,如果想进行对整个结构体的排序,也就是利用数据顺序来调整节点中的信息,需要对节点进行交换,但与此方法不同,望读者周知。

    测试排序代码请先参考下边完整的测试代码。
    编程环境:Visual C++ 6.0.

    冒泡排序

    NODE* bubblesort(NODE* Head) 
    {
        NODE *pfirst=NULL,*psecond=NULL,*pend=NULL;
        pfirst=Head;
    	psecond=Head;
    	int temp;
        while(pfirst != pend)          //外循环
    	{							   //pfirst != pend 很有意思
            while(pfirst->next != pend)//内循环
    		{
                if(pfirst->date > pfirst->next->date)
    			{
                    temp=pfirst->date;  
                    pfirst->date=pfirst->next->date;
                    pfirst->next->date=temp;
                }
                   pfirst=pfirst->next;
            }
            pend=pfirst;//减少最后的已排好的循环
            pfirst=Head;
        }
        return Head;
    }
    

    选择排序

    /*链表的选择排序*/
    
    NODE* selectsort(NODE* head) 
    {
    	NODE *pfirst=NULL,*psecond=NULL,*pend=NULL;
        pfirst=head;
    	psecond=head;
    	int temp;
        while(pfirst != pend)          //外循环
    	{
            while(pfirst->next != pend)//内循环
    		{
                if(psecond->date > pfirst->next->date)
    			{
                    temp=psecond->date;  
                    psecond->date=pfirst->next->date;
                    pfirst->next->date=temp;
                }
                   pfirst=pfirst->next;
            }
    		psecond=psecond->next;
            pfirst=psecond;
        }
    	return head;
    } 
    
    

    测试代码

    /*
     *链表排序 Writen by YU
     */
    #include<stdio.h>
    #include<stdlib.h>
    
    /*结果输出查看*/
    void endscan()
    {
    	printf("\n点击回车继续...");
    	fflush(stdin);
    	getchar();
    }
    
    /*结构体*/
    struct node
    {
        int date;
        struct node *next;
    };
    
    typedef struct node NODE;  //把struct node 定义为 NODE
    int count = 0;
    
    /*创建链表并输入数据*/
    NODE* creat()
    {
        NODE *pHead=NULL,*pNew,*pEnd;
    
        printf("输入数据,当输入0时停止\n");
    
        pNew=(NODE*)malloc(sizeof(NODE));
        scanf("%d",&pNew->date);
        while(pNew->date != 0)
    	{
            count++;
            if(count == 1) //如果为头节点
    		{
                pNew->next = NULL;
                pEnd = pNew;
                pHead = pNew;
            }
    		else           //如果不是头结点
    		{
                pNew->next=NULL;
                pEnd->next=pNew;
                pEnd=pNew;
            }
                pNew=(NODE*)malloc(sizeof(NODE));
                scanf("%d",&pNew->date);
        }
            free(pNew);
        return pHead;
    }
    
    /*输出链表*/
    void print(NODE* Head)
    {
        NODE* p=Head;
        while(p!=NULL)
    	{
            printf("%d ",p->date);
            p=p->next;
        }
    }
    
    /*链表的冒泡排序*/
    NODE* bubblesort(NODE* Head) 
    {
        NODE *pfirst=NULL,*psecond=NULL,*pend=NULL;
        pfirst=Head;
    	psecond=Head;
    	int temp;
        while(pfirst != pend)          //外循环
    	{							   //pfirst != pend 很有意思
            while(pfirst->next != pend)//内循环
    		{
                if(pfirst->date > pfirst->next->date)
    			{
                    temp=pfirst->date;  
                    pfirst->date=pfirst->next->date;
                    pfirst->next->date=temp;
                }
                   pfirst=pfirst->next;
            }
            pend=pfirst;//减少最后的已排好的循环
            pfirst=Head;
        }
        return Head;
    }
    
    /*链表的选择排序*/
    
    NODE* selectsort(NODE* head) 
    {
    	NODE *pfirst=NULL,*psecond=NULL,*pend=NULL;
        pfirst=head;
    	psecond=head;
    	int temp;
        while(pfirst != pend)          //外循环
    	{
            while(pfirst->next != pend)//内循环
    		{
                if(psecond->date > pfirst->next->date)
    			{
                    temp=psecond->date;  
                    psecond->date=pfirst->next->date;
                    pfirst->next->date=temp;
                }
                   pfirst=pfirst->next;
            }
    		psecond=psecond->next;
            pfirst=psecond;
        }
    	return head;
    } 
    
    int main()
    {
        NODE* pHead=NULL;
        pHead=creat();
        printf("排序前:\n");
        print(pHead);
    //	pHead=bubblesort(pHead); //冒泡排序
    	pHead=selectsort(pHead); //选择排序
        printf("\n排序后:\n");
        print(pHead);
    	endscan();
        return 0;
    }
    
    展开全文
  • C语言链表讲解

    2020-05-06 17:51:08
    数组是大家在学习C语言中学到第一种数据存储方法,其可以存储各种类型数据,那么为什么还要使用链表来储存数据呢?这里首先先讲解一下两者特性; 数组特性,在于可以方便遍历查找需要数据。在查询数组...

    一、C语言中有了数组为什么还要使用链表

    链表和数组作为算法中的两个基本数据结构,在程序设计过程中经常用到。数组是大家在学习C语言中学到的第一种数据存储方法,其可以存储各种类型的数据,那么为什么还要使用链表来储存数据呢?这里首先先讲解一下两者的特性;

    数组的特性,在于可以方便的遍历查找需要的数据。在查询数组指定位置(如查询数组中的第4个数据)的操作中,只需要进行1次操作即可,时间复杂度为O(1)。但是,这种时间上的便利性,是因为数组在内存中占用了连续的空间,在进行类似的查找或者遍历时,本质是指针在内存中的定向偏移。然而,当需要对数组成员进行添加和删除的操作时,数组内完成这类操作的时间复杂度则变成了O(n)

    链表的特性,使其在某些操作上比数组更加高效。例如当进行插入和删除操作时,链表操作的时间复杂度仅为O(1)。另外,因为链表在内存中不是连续存储的,所以可以充分利用内存中的碎片空间。除此之外,链表还是很多算法的基础,最常见的哈希表就是基于链表来实现的。基于以上原因,我们可以看到,链表在程序设计过程中是非常重要的。

    使用链表可以解决数组的一些缺点:
    1、解决数组无法存储多种数据类型的问题。
    2、解决数组中,元素个数无法改变的限制(C99的变长数组,C++也有变长数组可以实现)。
    3、数组进行遍历时效率还可以,当需要对数组成员进行添加和删除的操作时,数组内完成这类操作则很耗时间,效率也不高,对于插入和删除操作也是如此,而链表可以很好的解决这一问题。
    4、链表在内存中不是连续存储的,所以可以充分利用内存中的碎片空间。
    在这里插入图片描述
    基于以上的特性,所以根据不同需求,从而选择使用链表或数组能够更好的完成任务。说到链表,可能有些人还对其概念不是很了解。我们可以将一条链表想象成环环相扣的结点,就如平常所见到的锁链一样。链表内包含很多结点(当然也可以包含零个结点)。其中每个结点的数据空间一般会包含一据结构(用于存放各种类型的数据)以及一个指针,该指针一般称为next,用来指向下一个结点的位置。由于下一个结点也是链表类型,所以next的指针也要定义为链表类型。

    二、链表的结构:

    在这里插入图片描述
    从这幅图我们得出以下信息:
    这个简单链表的构成:
    头指针(Header),若干个节点(节点包括了数据域和指针域),最后一个节点要指向空。
    实现原理:头指针指向链表的第一个节点,然后第一个节点中的指针指向下一个节点,然后依次指到最后一个节点,这样就构成了一条链表。

    接下来看看链表的数据结构:

    typedef struct Linklist
    {
      char elem;  //代表数据域
      struct Linklist * next;  //代表指针域,指向直接后继元素
    }link;
    

    头结点、头指针和首元结点
    头结点: 有时,在链表的第一个结点之前会额外增设一个结点,结点的数据域一般不存放数据(有些情况下也可以存放链表的长度等信息),此结点被称为头结点。若头结点的指针域为空(NULL),表明链表是空表。头结点对于链表来说,不是必须的,在处理某些问题时,给链表添加头结点会使问题变得简单。
    首元结点: 链表中第一个元素所在的结点,它是头结点后边的第一个结点。
    头指针: 永远指向链表中第一个结点的位置(如果链表有头结点,头指针指向头结点;否则,头指针指向首元结点)。
    头结点和头指针的区别: 头指针是一个指针,头指针指向链表的头结点或者首元结点;头结点是一个实际存在的结点,它包含有数据域和指针域。两者在程序中的直接体现就是:头指针只声明而没有分配存储空间,头结点进行了声明并分配了一个结点的实际物理内存。
    在这里插入图片描述
    头结点一般不含数据,故可简化为下图所示:
    在这里插入图片描述
    单链表中可以没有头结点,但是不能没有头指针!

    三、链表的具体实现

    万事开头难,初始化链表首先要做的就是创建链表的头结点或者首元结点。创建的同时,要保证有一个指针永远指向的是链表的表头,这样做不至于丢失链表。
    例如创建一个链表(1,2,3,4):

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Linklist
    {
    	char elem;//代表数据域
    	struct Linklist * next;//代表指针域,指向直接后继元素
    }link;
    
    link * initLink()
    {
    	link * head_node = (link*)malloc(sizeof(link));//创建一个头结点
    	link * ptr = head_node;//声明一个指针指向头结点,用于遍历链表,此时这个指针就是头指针,后面会变换
    	ptr->next = NULL;//设置指向,防止其随意指向单元导致错误
    					  
    	for (int i = 1; i<5; i++)//生成链表
    	{
    		link *node = (link*)malloc(sizeof(link));
    		node->elem = i;
    		node->next = NULL;
    		ptr->next = node;
    		ptr = ptr->next;
    	}
    	return head_node;
    }
    
    void display(link *head_node)
    {
    	link* temp = head_node;//将temp指针重新指向头结点
    				   //只要temp指针指向的结点的next不是Null,就执行输出语句。
    	while (temp->next)
    	{
    		temp = temp->next;
    		printf("%d", temp->elem);
    	}
    	printf("\n");
    	system("pause");
    }
    
    int main()
    {
    
    	//初始化链表(1,2,3,4)
    
    	printf("初始化链表为:\n");
    
    	link *list = initLink();
    	display(list);
    	return 0;
    }
    

    具体运行流程如下图所示:
    在这里插入图片描述

    定位元素位置与查询某位置处的元素

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Linklist
    {
    	char elem;//代表数据域
    	struct Linklist * next;//代表指针域,指向直接后继元素
    }link;
    
    link * initLink()
    {
    	link * head_node = (link*)malloc(sizeof(link));//创建一个头结点
    	link * ptr = head_node;//声明一个指针指向头结点,用于遍历链表,此时这个指针就是头指针,后面会变换
    	ptr->next = NULL;//设置指向,防止其随意指向单元导致错误
    					  
    	for (int i = 2; i<6; i++)//生成链表
    	{
    		link *node = (link*)malloc(sizeof(link));
    		node->elem = i;
    		node->next = NULL;
    		ptr->next = node;
    		ptr = ptr->next;
    	}
    	return head_node;
    }
    
    void display(link *head_node)
    {
    	link* temp = head_node;//将temp指针重新指向头结点
    				   //只要temp指针指向的结点的next不是Null,就执行输出语句。
    	while (temp->next)
    	{
    		temp = temp->next;
    		printf("%d", temp->elem);
    	}
    	printf("\n");
    	system("pause");
    }
    
    //定位该数据在链表中的位置
    int localateElem(link * p, int elem)
    {
    	link *t = p;
    	int i = 1;
    	while (t->next)
    	{
    		t = t->next;
    		printf("t->elem = %d\n", t->elem);
    		if (t->elem == elem)
    		{
    			return i;
    		}
    		i++;
    	}
    	return -1;
    }
    
    int selectElem(link * p, int elem)
    {
    
    	link *t = p;
    	int i = 1;
    	while (i < elem)
    	{
    		t = t->next;
    		i++;
    	}
    	t = t->next;
    	//printf("%d号位置的元素为%d\n",elem,t->elem);
    	return t->elem;
    
    }
    
    int main()
    {
    
    	//初始化链表(1,2,3,4)
    
    	printf("初始化链表为:\n");
    	link *list = initLink();
    	display(list);
    
    	printf("查找元素2的位置为:\n");
    	int address = localateElem(list, 2);
    	if (address == -1)
    		printf("没有该元素\n");
    	else
    		printf("元素2的位置为:%d\n", address);
    
    	int data = selectElem(list, 2);
    	printf("2号位置的元素为%d\n",data);
    	display(list);
    
    	return 0;
    }
    

    链表插入、删除和替换操作

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Linklist
    {
    	char elem;//代表数据域
    	struct Linklist * next;//代表指针域,指向直接后继元素
    }link;
    
    link * initLink()
    {
    	link * head_node = (link*)malloc(sizeof(link));//创建一个头结点
    	link * ptr = head_node;//声明一个指针指向头结点,用于遍历链表,此时这个指针就是头指针,后面会变换
    	ptr->next = NULL;//设置指向,防止其随意指向单元导致错误
    					  
    	for (int i = 2; i<6; i++)//生成链表
    	{
    		link *node = (link*)malloc(sizeof(link));
    		node->elem = i;
    		node->next = NULL;
    		ptr->next = node;
    		ptr = ptr->next;
    	}
    	return head_node;
    }
    
    void display(link *p)
    {
    	link* temp = p;//将temp指针重新指向头结点
    				   //只要temp指针指向的结点的next不是Null,就执行输出语句。
    	while (temp->next)
    	{
    		temp = temp->next;
    		printf("%d", temp->elem);
    	}
    	printf("\n");
    	
    }
    
    //定位该数据在链表中的位置
    int localateElem(link * p, int elem)
    {
    	link *t = p;
    	int i = 1;
    	while (t->next)
    	{
    		t = t->next;
    		printf("t->elem = %d\n", t->elem);
    		if (t->elem == elem)
    		{
    			return i;
    		}
    		i++;
    	}
    	return -1;
    }
    
    int selectElem(link * p, int elem)
    {
    
    	link *t = p;
    	int i = 1;
    	while (i < elem)
    	{
    		t = t->next;
    		i++;
    	}
    	t = t->next;
    	//printf("%d号位置的元素为%d\n",elem,t->elem);
    	return t->elem;
    
    }
    
    link *insertElem(link * p, int elem, int add)
    {
    
    	link * temp = p;//创建临时结点temp
    
        //首先找到要插入位置的上一个结点
    	for (int i = 1; i<add; i++)
    	{
    		if (temp == NULL)
    		{
    			printf("插入位置无效\n");
    			return p;
    		}
    		temp = temp->next;
    	}
    
    	//创建插入结点c
    	link * c = (link*)malloc(sizeof(link));
    	c->elem = elem;
    	//向链表中插入结点
    	c->next = temp->next;
    	temp->next = c;
    
    	return p;
    
    }
    
    
    link * delElem(link * p, int add)
    {
    
    	link * temp = p;
    	//遍历到被删除结点的上一个结点
    
    	for (int i = 1; i<add; i++)
    	{
    
    		temp = temp->next;
    
    	}
    
    	link * del = temp->next;//单独设置一个指针指向被删除结点,以防丢失
    
    	temp->next = temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域
    
    	free(del);//手动释放该结点,防止内存泄漏
    
    	return p;
    
    }
    
    link *amendElem(link * p, int add, int newElem)
    {
    
    	link * temp = p;
    
    	temp = temp->next;//tamp指向首元结点
    
    					  //temp指向被删除结点
    
    	for (int i = 1; i<add; i++)
    	{
    
    		temp = temp->next;
    
    	}
    
    	temp->elem = newElem;
    
    	return p;
    
    }
    
    int main()
    {
    
    	//初始化链表(1,2,3,4)
    
    	printf("初始化链表为:\n");
    	link *list = initLink();
    	display(list);
    
    	printf("查找元素2的位置为:\n");
    	int address = localateElem(list, 2);
    	if (address == -1)
    		printf("没有该元素\n");
    	else
    		printf("元素2的位置为:%d\n", address);
    
    	int data = selectElem(list, 2);
    	printf("2号位置的元素为%d\n",data);
    
    	printf("在第4的位置插入元素6:\n");
    	list = insertElem(list, 6, 4);
    	display(list);
    
    	printf("删除元素3:\n");
    	list = delElem(list, 3);
    	display(list);
    
    	printf("更改第3的位置的数据为7:\n");
    	list = amendElem(list, 3, 7);
    	display(list);
    
    	system("pause");
    
    	return 0;
    }
    

    插入操作流程
    在这里插入图片描述
    删除操作流程
    在这里插入图片描述
    链表有很多类型,这里仅以单链表来讲解。

    展开全文
  • 小编想问大家一个问题,就是如果我们...原始方法:就刚刚小编所提出的问题,也许会有朋友想到了一个非常原始的方法,那就是将链表的数据结构进行改变,然后给每一个节点添加一个名为bool的变量,在还没有进行测试...

    小编想问大家一个问题,就是如果我们需要进行测试一个单向链表是否存在环,应该使用什么方法才是最好的呢?如果大家还不知道有什么方法的话,那就接着往下面看哟!因为今天小编就要为大家介绍一下:在C语言中单向链表环测试并返回环起始节点的实现方法。

    原始方法:

    就刚刚小编所提出的问题,也许会有朋友想到了一个非常原始的方法,那就是将链表的数据结构进行改变,然后给每一个节点添加一个名为bool的变量,在还没有进行测试的时候,我们全部都初始化成为false值,接着遍历链表,每当我们访问到一个节点的时候,首先要做的就是测试其bool成员来确定这个节点是否已经被我们访问过了。假如说我们所测试出来的值是为true的话,那么就代表着访问过,就是有环的意思。否则的话,就设置bool成员为true的值,表示访问过的意思,接下来我们还要继续进行测试。

    假如我们在不改变数据结构的情况下,我们还有以下一种的解决方案。具体是哪种解决方案呢?请大家留意下面的教程:

    第一步:测试是否有环

    第一种解决的方案就是先测试一下是否有环。首先我们可以先构建出两个迭代器来进行遍历链表,有一个迭代器每一次移动一个节点,另外一个迭代器则每一次移动两个节点。假如说这两个一快一慢的土鳖迭代器相遇了的话,那就可以证明一件事情,那就是他们两个迭代器在某一个时刻都已经到了同一个节点。这样子的话,我们可以非常的肯定的确是有环存在的。其实最直观的理解就是把这两个土鳖迭代器一快一慢的在长度400米环形跑道上各自选择一个位置,接着同一时间顺时针做死了跑,那么这样子的话,这两个土鳖迭代器总可以相遇的。那么有人就会问小编,到底是为什么呢?原因就是因为有一个迭代器会比另外一个迭代器速度要快。

    假如有一些朋友是需要进行严谨证明的话,那么我们还可以这样来理解。具体的理解如下:首先我们想象着在某一个迭代的时刻,这两个土鳖迭代器(在接下来的教程中,小编会将其简单称为土鳖,因为这样会更有亲切感,哈哈)都进入了环,一个土鳖距离环的起始点为i,然而另外一个土鳖距离环起始点为j。这个想象是一定有成立的时刻,因为在跑着跑着的时候,这两个土鳖总会进入环,而且一旦进入了环那就再也出不来了,只可以做死了跑。

    接下来我们再大胆的进行假设一下这两个土鳖又相互跑了一会儿,他们居然相遇了,有一个土鳖跑了x步,另外一个土鳖则跑了2x步。假如说这个环一共是长n米的话,换句话来说,也就是速度慢的土鳖需要跑n步才可以跑完一圈。接下来我们就可以得出i+x以及j+2x对于n同余,就说明了一件事,那就是:i+x以及j+2x除以n的余数是一模一样的,可以写成同余等式就是(i+x)=j+2x(modn)。然后我们就可以根据同余加减法性质,让上面的表达式来减去x=x(modm),就可以得到以下的表达式:i=(j+x)(modm)。在这个表达式中,大家可以看到因为x是一个未知数,因此在上面的表达式是一个同余方程,另外的字母i、j通通都是普通整数,非常明显其实这个方程是有解的。就比如说:表达式2=(1+x)(mod5)的一个简单解就是数字1。因此这两个土鳖跑着跑着就一定会相遇的。换句话来说,就是我们上面所检测环的算法是可行的方法,不会发生死循环的情况。

    第二步:获取环起始点

    好了,基于问题一的分析,我们就可以知道了一件事,那就是速度快的土鳖以及速度慢的土鳖一定会在某一个节点进行相遇的。现在我们就把这个点(相遇的节点)假设成为cross,同一时间我们也将环起始点假设成为start。在这里,有一个十分显然的事实,那就是当两个土鳖相遇的时候,速度慢的土鳖所跑过的路径是速度快土鳖的一半。这样子的话,他们两个在相遇之前,当速度慢土鳖跑了一半时,速度快土鳖就已经经过了相遇点(跨越又或者是落脚)。这样子的话,当速度慢土鳖跑完后半段时,速度快土鳖就已经从相遇的地方开始又跑了一模一样的路程到达了相遇的地点。这个路程的长度就是相等于速度慢土鳖一共跑的长度。

    那么现在最神奇的地方要来了,那就是假如说速度慢土鳖从头开始跑时,有另外一个速度慢土鳖从相遇的地方cross开始跑,那么这两个土鳖也一定会在相遇的地方进行相遇,接着我们就将这两个土鳖称为分别为A以及B。当B土鳖走的路程以及速度快土鳖后半段时间走过的路程是完全一模一样的,唯一一个的区别就是他稍微慢了一点而已。

    那么现在第二个最神奇的地方又要来了,大家都已经知道速度慢土鳖A以及B土鳖的速度是一模一样的,那么这两个土鳖在相遇地点之前的节奏也是一模一样的,换句话来说,就是他们在相遇地点之前就已经开始相遇了,而且还是以完全一样的速度相伴走到了相遇的地方cross。那么这两个土鳖究竟是从什么时候相遇开始这一段快乐旅程的呢?有人知道答案吗》没错,就是从环起始点start开始相遇的。在这里,我们可以让速度慢土鳖A以及B土鳖从相遇地方倒退,这样我们就可以理解到为什么他们会在start点进行相遇了。

    好了,现在我们就已经有了解决方案了,具体的解决方案如下:先让速度慢土鳖A从链表头start开始跑,让另外一个速度慢土鳖从相遇点cross开始跑。有人知道这两个土鳖第一次相遇的地方是哪里吗?正确答案就是——环起始点。

    最后,为了可以更加方便大家深入的理解,小编在这里特意给大家带来了C++的代码。具体编程代码,如下图:

    5403007f8477b58b4508cff23314bb84.png

    c0a580a590071af4861662eb325330bb.png

    7b729ac3aeb2250b200f57dc024dee2f.png

    d89804acd3b2113bed9e6fddf9e837d4.png

    小编结语:

    在这篇教程中,小编主要是向大家介绍一下在C语言中单向链表环测试并返回环起始节点的实现方法。教程的确是有一点点长,但是总的来说,还是比较详细的,所以大家一定要有点耐心的去看哟!不要半途而废了。

    课课家会一直更新编程语言的教程,请继续关注我们的网站:课课家教育。谢谢!

    展开全文
  • 1,先建立结构体 ...2,建立创建循环链表的函数 struct node* creat(){ struct *head;*now,*pre; //分别为头节点,当前节点,前驱节点 for(int i = 0;i<=n;i++){ now = (struct node*)malloc(sizeof(node...
  • 语言程序设计实验报告 实验八链表程序设计 实验目的 1掌握链表的概念定义和使用 2掌握链表中结点的建立插入删除方法 实验内容及步骤 1下列程序中子函数 insertup headnewp实现将一个 newp 所指新结点按升序插入到...
  • C语言链表学习笔记

    2017-04-13 14:17:10
    问题引入:预先无法知道数组大小,不能分配一块连续内存用动态存储的方法可以很...而使用动态分配时,每个结点之间可以是不连续(结点内是连续)。结点之间联系可以用指针实现。 即在结点结构中定义一个成员
  • typedef struct _node{ int data;...//尾插法:创建一个递增有序单链表 _node* last_create() { _node *head = (_node*)malloc(sizeof(_node)); head->data = 10;//带头结点,头结点dat...
  • C语言中学到有用的使用方法链表操作 头插法: #include <stdio.h> #include <stdlib.h> typedef struct linkNode { int num; struct linkNode *node; }linkNode; linkNode firstNode; void ...
  • 主要介绍了C语言基于循环链表解决约瑟夫环问题的方法,简单描述了约瑟夫环问题并结合实例形式分析了C语言使用循环链表解决约瑟夫环问题具体操作技巧,需要朋友可以参考下
  • 题目:反转一个单链表。 示例: 输入: 1->2->3->4->...今天复习这个题时候使用的是头插法,因为头插法精准而优雅,代码还简单。但这道题给我几个启示: ①用自己最擅长的方法解...
  • C语言的链表基本操作

    2011-03-19 16:23:17
    但我们未学习链表的时候,如果要存储数量比较多的同类型或同结构的数据的时候,总是使用一个数组。比如说我们要存储一个班级学生的某科分数,总是定义一个float型(存在0.5分)数组: float score[30]; 但是,在使用...
  • C语言静态链表

    2017-12-29 10:57:58
    C语言中用指针可以实现线性单链表,而有些语言不支持指针,我们可以利用两个并行数组或者结构体数组来模拟指针,这样子的链表称之为静态链表。 下面,我给出了C语言实现方法,并给出了基本操作函数,以及...
  • C语言实现链表

    2020-03-13 00:32:51
    在此记录一下自己在学习链表过程中总结的一些链表的构建方法 最常见的 #include<stdio.h> #include<stdlib.h>//不要忘记,malloc要使用 //创立节点 typedef struct ListNode { int data; struct ...
  • c语言 堆和链表 定义 理解 与使用 方法
  • 最近有时间看了数据结构的双向链表,其实和单向链表的规则是一样的,只不过在定义节点的时候比单向链表多定义i一个指向前一个节点的指针就可以了,在插入节点和删除节点的时候要注意,画图是最好的方法。 双向使用...
  • void merge (LNode *C,int x) //删除链表中单个结点 {LNode *p,*q; p=c; /*查找部分开始*/ while(*p.next!...如果说只是方法体内形参发生了改变,链表C本身没有发生改变,那最终链表怎么会有删除效果。
  • 由于C语言数组的功能比较单一,很多时候都不能满足数据存储的需求,因此会经常性的使用到链表。在这总结一点链表的常用功能,都是我学习总结后,自己编写的,欢迎评论讨论。 首先建立一个链表,我这为了省事用了一个...
  • 基本的伪代码的使用和理解,顺序链表的算法掌握和提示 学习时间: 看掌握情况 学习产出: 1.伪代码的一些基本定义: //函数结果状态代码 #define TRUE 1 #define false 0 #define OK 1 #define ERROR 0 #define ...
  • C语言单链表和双链表的创建和输出

    千次阅读 2016-05-12 12:04:09
    本文将描述C语言实现单向链表和双向链表的创建、输出操作方法。单向链表 单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表...
  • 3.1静态链表的优缺点 优点: 在插入和删除操作时,只需要修改游标,不需要移动元素,从而改进了在顺序储存结构中的插入和删除操作需要移动大量元素的缺点。 缺点: 没有解决连续存储分配(数组)带来的表长度难以...
  • 学习次内容前需掌握结构体和指针的使用方法,此链表为最基础的静态链表。 #include <stdio.h> struct Student{ int num; float score; struct Student *next; }; int main() { struct Student a, b, c, *...
  • C语言之合并链表

    2019-05-05 16:10:03
    对于插入方法我选择是头插法并且这次首次使用头指针下一个指向才存有数据的方法. struct Data { int number; struct Data *next; }; void Create(struct Data *pHead) { struct Data *p1, *t; int...
  • 其中包括一个链表所必须数据和操作链表所必须的方法,再定义一个接口用于创建链表使用指针原因是防止局部变量被释放掉。 typedef struct node_t Node; struct node_t { void *data; Node *next; }; typedef...
  • 静态链表和动态链表的区别: 静态链表要预先申请一整块足够内存的空间,其能存储的元素个数在创建的那一刻就不能再更改了。 动态链表:之前实现的单链表,双链表,循环链表都属于动态链表,可以在使用过程中动态...
  • 下面代码是链表的两种实现方式,其中方式一就是按照数据结构书中对链表的实现过程,而方式二是根据linux内核中关于链表的实现。两者的最大区别是方式一中数据是存储在链表结构中的,而方式二中,是在数据结构中包含...
  • 1、演示三种动态内存(堆空间)的申请和使用方法; 2、讲解链表的原理并演示链表节点插入的代码编写方法;

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 542
精华内容 216
关键字:

c语言链表的使用方法

c语言 订阅