单向链表_单向链表反转 - CSDN
单向链表 订阅
单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表,因为链表是由一个个结点组装起来的;其中每个结点都有指针成员变量指向列表中的下一个结点;链表是由结点构成,head指针指向第一个成为表头结点,而终止于最后一个指向NULL的指针。 展开全文
单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表,因为链表是由一个个结点组装起来的;其中每个结点都有指针成员变量指向列表中的下一个结点;链表是由结点构成,head指针指向第一个成为表头结点,而终止于最后一个指向NULL的指针。
信息
外文名
One-way LinkedList
定    义
链表的一种
特    点
链表的链接方向是单向的
中文名
单向链表
目    的
学习单向链表
单向链表链表的优点
相比较普通的线性结构,链表结构的可以总结一下: (1)单个结点创建非常方便,普通的线性内存通常在创建的时候就需要设定数据的大小(2)结点的删除非常方便,不需要像线性结构那样移动剩下的数据(3)结点的访问方便,可以通过循环或者递归的方法访问到任意数据,但是平均的访问效率低于线性表
收起全文
精华内容
参与话题
  • 一个简单结点的结构体表示为: struct note { int data; /*数据成员可以是多个不同类型的数据*/ ...一个简单的单向链表的图示 1.链表是结构、指针相结合的-种应用,它是由头、中间、...

    一个简单结点的结构体表示为:

        struct note

        {

           int  data;              /*数据成员可以是多个不同类型的数据*/

           struct  note  *next;      /*指针变量成员只能是-个*/

        };

     

    一个简单的单向链表的图示

     

    1.链表是结构、指针相结合的-种应用,它是由头、中间、尾多个链环组成的单方向可伸缩的链表,链表上的链环我们称之为结点。

    2.每个结点的数据可用-个结构体表示,该结构体由两部分成员组成:数据成员与结构指针变量成员。

    3.数据成员存放用户所需数据,而结构指针变量成员则用来连接(指向)下-个结点,由于每-个结构指针变量成员都指向相同的结构体,所以该指针变量称为结构指针变量。

    4.链表的长度是动态的,当需要建立-个结点,就向系统申请动态分配-个存储空间,如此不断地有新结点产生,直到结构指针变量指向为空(NULL)。申请动态分配-个存储空间的表示形式为:

               (struct  note*)malloc(sizeof(struct  note))

     

    链表的建立

       在链表建立过程中,首先要建立第一个结点,然后不断地

    在其尾部增加新结点,直到不需再有新结点,即尾指针指向

    NULL为止。

     设有结构指针变量   struct note *p,*p1,*head;

          head:用来标志链表头;

      p:在链表建立过程中,p总是不断先接受系统动态分配的新结点地址。

      p1->next:存储新结点的地址。

     

    链表建立的步骤:

    第一步:建立第一个结点

    struct   node

    {

        int   data;

        struct   node  *next;

     };

    struct   note   *p,*p1,*head;

    head=p1=p=(struct  node  *)malloc(sizeof(struct node);

     

    第二步:

          给第-个结点成员data赋值并产生第二个结点

    scanf(“%d”,&p->data);  /*输入10*/

    p=(struct  node  *)malloc(sizeof(struct node);

     

    第三步:将第-个结点与第二个结点连接起来

    p1-> next=p;

     

    第四步:产生第三个结点

    p1=p;

    scanf(“%d”,&p->data);/*输入8*/

    p=(struct  node  *)malloc(sizeof(struct node);

    以后步骤都是重复第三、四步,直到给出-个结束条件,不再建新的结点时,要有

       p->next=NULL;它表示尾结点。

     

     

     

    代码

     

    #include <stdio.h>  
    #include<stdlib.h>  
    #define  LEN  sizeof(struct node)  
    struct node  
    {  
    int data;  
    struct node  *next;  
    };  
    main()  
    {     struct  node  *p, *pl,* head;  
              head=p=(struct node * )malloc(LEN);  
              scanf("%d",&p->data);/*头结点的数据成员*/  
              while(p->data!=0)   /*给出0结束条件,退出循环*/  
              {    pl=p;  
                   p=(struct node * )malloc(LEN);  
                      scanf("%d",&p->data);/*中间结点数据成员*/  
                      pl->next=p;/*中间结点的指针成员值*/  
              }  
              p-> next=NULL;/*尾结点的指针成员值*/  
              p=head;/*链表显示*/  
              printf("链表数据成员是:");  
              while(p->next!=NULL)  
              {  
              printf("%d",p->data);  
              p=p->next;  
              }  
              printf("%d\n",p->data);  
    }  

     

     

     

     

    转自https://blog.csdn.net/21aspnet/article/details/160019

    展开全文
  • C语言单向链表的基本操作

    千次阅读 2018-06-27 19:48:43
    指针域数据域:存储需要保存的数据指针域:各个节点之间的连接连续性:链表在逻辑上是连续的,但物理上未必连续链表主要有单向链表,双向链表,循环链表链表操作:对于链表的操作一般包括增加,删除,修改,查找下...

        掌握结构体,指针后,链表作为两种形式的集合,将C语言的作用发挥到巨大。

    链表知识123

    链表是线性表,包括两个部分:数据域&指针域

    数据域:存储需要保存的数据

    指针域:各个节点之间的连接

    连续性:链表在逻辑上是连续的,但物理上未必连续

    链表主要有单向链表,双向链表,循环链表



    链表操作:对于链表的操作一般包括增加,删除,修改,查找

    下面对单向链表进行举例操作:

    操作环境:keil v4,串口软件,有硬件支持

    构建结构体:

    typedef struct list {
    int id;                    //元素id,方便数据查找
    char data[20];        //数据域
    struct list *next;    //指向下一个链表头指针
    }LIST;


    //定义全局变量,实现每个元素的id不同

    static LIST *list_head = NULL;


    //定义链表头结点:

    static int list_id = 0;


    /*

    *功能:增加链表元素

    *输入:**head -> 链表头

    *                list  -> 增加的链表

    *输出:无

    **/

    static void List_Add(LIST **head, LIST *list)
    {
    LIST *temp; //临时变量,指向*head

    if(NULL == *head) //如果链表头为空,则将list保存到list_head
    {
    *head = list;
    (*head)->next = NULL;
    }
    else
    {
    temp = *head; //temp保存*head

    while(temp) //轮询
    {
    if(NULL == temp->next) //尾插
    {
    temp->next = list;
    list->next = NULL; //next清空,供下一个元素尾插
    }
    temp = temp->next;
    }
    }

    }



    /*

    *功能:删除指定id位置的元素

    *输入:**head -> 链表头

    *                id   -> 指点id

    *输出:0 -> 成功

    *         -1 -> 失败

    **/

    static int List_Del(LIST **head, int id)
    {
    LIST *temp, *p;

    temp = *head;

    if(NULL == temp) //链表为空
    {
    printf("list is empty \r\n");
    return -1; 
    }
    else
    {
    if(id == temp->id) //删除链表头
    {
    *head = temp->next;
    return 0;
    }
    else
    {
    while(temp->next) //轮询
    {
    p = temp;
    temp = temp->next;

    if(id == temp->id)
    {
    p->next = temp->next;
    return 0;
    }
    }
    return -1;
    }
    }
    }



    /*

    *功能:修改指定id位置的元素

    *输入:**head -> 链表头

    *                id   -> 指点id

    *       *content -> 修改内容

    *输出:0 -> 成功

    *         -1 -> 失败

    **/

    static int List_Chg(LIST **head, int id, char *content)
    {
    LIST *temp;

    temp = *head;         //temp保存*head

    while(temp) //轮询
    {
    if(id == temp->id)
    {
    memset(temp->data, 0, sizeof(temp->data));
    sprintf(temp->data, "%s", content);
    temp->data[strlen(content)] = '\0';
    return 0;
    }
    temp = temp->next;
    }
    return -1;

    }



    /*

    *功能:寻找指定id位置的元素

    *输入:**head -> 链表头

    *                id   -> 指点id

    *输出:0 -> 成功

    *         -1 -> 失败

    **/

    static int List_Query(LIST **head, int id)
    {
    LIST *temp;

    temp = *head;

    if(NULL == temp)                        //链表为空
    {
    printf("list is empty\r\n");
    return -1;
    }
    else
    {
    while(temp)                          //轮询
    {
    if(id == temp->id)        //找到指定元素
    {
    printf("list %d : %s\r\n", temp->id, temp->data);
    return 0;
    }
    temp = temp->next;
    }
    printf("no finding\r\n");
    return -1;
    }

    }



    /*

    *功能:打印链表

    *输入:**head -> 链表头

    *输出:无

    **/

    static void List_Printf(LIST **head)
    {
    LIST *temp;

    temp = *head;

    printf("list information\r\n");

    while(temp)                            //轮询
    {
    printf("list %d : %s\r\n", temp->id, temp->data);
    temp = temp->next;
    }

    }


    int main(void)
    {
    int i;
    LIST *lists = NULL;
    LIST temp_list;

    lists = malloc(sizeof(LIST)*10);

    /*******************************单向链表操作************************************/

    //执行一:循环加入10个链表元素
    for(i = 0; i < 10; i++)
    {
    lists[i].id = list_id++; //id循环赋值
    sprintf(lists[i].data, "TECH-PRO - %d", i);         //data循环赋值
    List_Add(&list_head, &lists[i]); //将数据加入链表
    }
    List_Printf(&list_head); //打印链表数据

    //执行二:增加一个结构体到链表
    temp_list.id = list_id++; //id赋值
    sprintf(temp_list.data, "temp_list");                         //data赋值
    List_Add(&list_head, &temp_list);                 //将结构体数据加入链表中
    List_Printf(&list_head); //打印链表数据

    //执行三:删除指定元素
    List_Del(&list_head, 0); //删除指定元素链表
    List_Del(&list_head, 2); //删除指定元素链表
    List_Del(&list_head, 5); //删除指定元素链表
    List_Del(&list_head, 9); //删除指定元素链表
    List_Printf(&list_head); //打印链表数据

    //执行四:改变指定元素数据
    List_Chg(&list_head, 4, "bug");         //改变id为4的元素数据
    List_Printf(&list_head); //打印链表数据

    //执行五:寻找指定元素
    List_Query(&list_head, 3);                                                //寻找id为3的元素数据
    List_Printf(&list_head);                                                     //打印链表数据

    /*****************************************************************************/
    return 0;

    }


    执行每一步功能操作,可单独处理

    执行一效果:



    执行二效果:



    执行三效果:


    执行四效果:



    执行五效果:


    展开全文
  • 单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)和一个链接域。这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值。 表元素域elem用来存放具体...

    单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)和一个链接域。这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值。

    • 表元素域elem用来存放具体的数据。
    • 链接域next用来存放下一个节点的位置(python中的标识)
    • 变量p指向链表的头节点(首节点)的位置,从p出发能找到表中的任意节点。

    节点实现

    class SingleNode(object):
    
    	def __init__(self,item):
    		self.item = item   # 存放数据元素
    		self.next = None
    

    功能实现

    class SingleLinkList(object):
    	def __init__(self):
    		self._head = None
    
    	def is_empty(self):
    	"""判断链表是否为空"""
    		return self._head == None
    
    	def length(self):
    	"""链表长度"""
    		cur = self._head
    		count = 0
    		while cur != None:
    			count += 1
    			cur = cur.next
    		return count
    
    	def travel(self):
    	"""遍历链表"""
    		cur = self._head
    		while cur != None:
    			print cur.item,
    			cur = cur.next
    		print ""
    		
    	def add(self, item):
    		"""头部添加元素"""
    		node = SingleNode(item)
    		if self.is_empty():
    			self._head = node
    		else:
    			cur = self._head
    		while cur.next != None:
    			cur = cur.next
    		cur.next = node
    
    	def insert(self, pos, item):
    		if pos <= 0:
    			self.add(item)
    		elif pos > (self.length() - 1):
    			self.append(item)
    		else:
    			node = SingNode(item)
    			count = 0
    			pre = self._head
    			while count < (pos-1):
    				count += 1
    				pre = pre.next
    			node.next = pre.next
    
    	def remove(self, item):
    		"""删除节点"""
    		cur = self._head
    		pre = None
    		while cur != Node:
    			if cur.item == item:
    				if not pre:
    					self._head = cur.next
    				else:
    					pre.next = cur.next
    				break
    			else:
    				pre = cur
    				cur = cur.next
    
    	def search(self, item):
    		cur = self._head
    		while cur != None:
    			if cur.item == item:
    				return True
    			cur = cur.next
    		return False
    		
    

    操作测试

    if __name__ == "__main__":
        ll = SingleLinkList()
        ll.add(1)
        ll.add(2)
        ll.append(3)
        ll.insert(2, 4)
        print "length:",ll.length()
        ll.travel()
        print ll.search(3)
        print ll.search(5)
        ll.remove(1)
        print "length:",ll.length()
        ll.travel()
    
    展开全文
  • (C/C++)初识单向链表

    千次阅读 多人点赞 2019-12-28 02:14:59
    (C/C++)初识单向链表 版权声明:本文为博主原创文章,未经博主允许不得转载。 第一次写博客,如果写得不好请谅解,欢迎大佬们一起交流讨论。 在我初学链表的时候,会觉得书上讲解十分抽象,理解到头炸,在通过...

    (C/C++)初识单向链表

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


    第一次写博客,如果写得不好请谅解,欢迎大佬们一起交流讨论。
    在我初学链表的时候,会觉得书上讲解十分抽象,理解到头炸,在通过做题的方式后,对链表又产生了新的认识和看法,使用链表的方式更加灵活了,通过这篇文章与大家分享一下单向链表的一些知识。
    本文章主要讲单向链表:

    • 创建
    • 输出
    • 排序
    • 插入
    • 删除
    • 清空

    链表是一种重要的数据结构,它是动态地进行储存分配的一种结构,并且链表必须用指针变量才能实现(重点!)。

    首先,建立动态链表

    建立动态链表,就是在程序运行中根据需求向系统申请储存空间,类似int *m = new int[n]的方式构造动态数组,概念是一种从无到有地建立新节点,并将各节点连接形成链表。

    这篇文章以成员为id和成绩作为例子,通过C++实现。
    环境:Code::Blocks_16.1 && VS2017

    题目
    第1~n行每行都是两个整数,第一个是 id(唯一的),第二个是 score;第n+1行只有一个数字,0(n可能是0)。
    这里的id输入是未排好序的整数
    节点的声明:

    struct Node {
           int id;
           int score;
           struct Node *next;	//此处*next表示尾巴 
     }*list_head;//设list_head,为全局变量的指针
    
    

    第二,接下来要讲如何实现建立动态链表,先放代码再继续讲解。

    void scan()	//创建链表
    {
        int id;
        Node *list_temp;		//过渡指针,负责将各节点连接
        list_head = NULL;		//作为头部,还没有输入,此时为NULL
    list_temp = list_head;	//将过渡指针指向头部,即从第一个节点开始
    cout <<  “请输入id和score:<< endl; 
        while(cin >> id,id)	//判断输入id是否非0
        {
            Node *list_body = new Node();		
            //申请空间,这里的括号可以删除,但为了增加程序的可读性,建议保留
            list_body->id = id;
            cin >> list_body->score;
            list_body->next = NULL;
    /*以上是成员赋值,因为是单向链表的使用,所以next必须为NULL*/
            if(list_head == NULL)	
            //如果新节点是第一个节点,则将这个节点连接到头部list_head,即指针list_head为链表的头地址
                list_head = list_body;
            else	//此时不是第一个节点,使用过渡指针list_temp将节点与新节点连接
                list_temp->next = list_body;
            list_temp = list_body;	//过渡指针移动至新节点
        }
    }
    

    假如把链表比作串烤串,那么一开始的链表就是一根竹签(list_head = NULL)

    这里写图片描述

    之后每串入一块肉(body),就是new了一个新节点,并且这串肉首尾相连,竹签从肉出去的地方就是它的尾部(next),当没有下一个肉串入时,next = NULL
    (list_body_1->next = list_body_2; list_body_2->next = list_body_3; …; list_body_n-1->next = list_body_n; 注意!list_body_n->next = NULL

    这里写图片描述

    这里写图片描述

    看上去将“肉”串在一起用编程实现很困难,其实只要通过指针list_temp就可以实现将各块“肉”首尾相连,这里我将指针list_temp称为过渡指针

    指针list_temp是通过,将新节点的地址复制给next来实现节点连接,这块的知识我自己学都觉得很抽象,得通过图文结合来理解,建立起框架。

    指针list_temp是不停变换的,每次连接好节点后,便会移动至新节点的位置,不改变其他变量,确保不会指针漂移

    这里写图片描述

    n个相连的body(节点)形成单向链表,list_head是第一个body的地址,每个body的next指向的是下一个body的地址,除了最后一个body指向的是NULL(因为后面已经没有body),其实就是串烤肉这么简单。

    第三,链表的输出,这部分比较简单。

    代码部分:

    /*通过过渡指针list_temp从head位置到链表结尾,移动至每个节点来实现输出成员*/
    void print_list()
    {
        Node *list_temp = list_head;
        cout << "*** LISTING ***" << endl;
        while(list_temp != NULL)	//判断当前位置是否存在节点
        {
             cout << "id:" << list_temp->id << '\t' << "score:" << list_temp->score << endl;
            list_temp = list_temp->next;
        }
        cout << "*** END OF FILE ***" << endl;
    }
    

    这里写图片描述

    这里可以理解为吃烤串,不过正常的吃烤串是从竹签尖的那端开始吃,而这里的“吃烤串”是从竹签底端的肉(list_temphead)开始往上吃(即往list_temp的箭头方向移动)

    第四,链表的冒泡排序

    对于刚入门的菜鸟,先了解使用冒泡法排序链表,感兴趣的可以去了解快排归并排序

    void cmp_list() //升序冒泡排序
    {
        Node *list_temp = NULL; //控制外循环,指向需要排序的第一个节点
        Node *list_end = NULL;  //控制内循环,指向需要排序的最后一个节点
        list_temp = list_head;  //指向表头
        while(list_temp != list_end)
        {
            while(list_temp->next != list_end)
            {
                /*这里的数据交换根据实际情况,但原理相同*/
                if(list_temp->id > list_temp->next ->id )   //当前节点的id与下一个节点的id比较
                {
                    //用整数cache_id和cache_score分别记录当前的位置的id和score
                    int cache_id = list_temp->id;
                    int cache_score = list_temp->score;
                    //下面的代码是交换两个链表的数据
                    list_temp->id = list_temp->next->id;
                    list_temp->score = list_temp->next->score;
                    list_temp->next->id = cache_id;
                    list_temp->next->score = cache_score;
                }
                list_temp = list_temp->next ;
            }
            list_end = list_temp;   //将当前排序的最后一个节点向前挪动一个位置
            list_temp = list_head;  //重新指向表头
        }
    }
    
    
    

    只要能理解数组的冒泡法,相信也能理解链表的冒泡排序,因为原理是相同的。这段代码已经做过优化处理,链表无节点和只有一个节点的情况也考虑到了。

    第五,链表数据的插入

    void add_point()
    {
        cout << "请输入新数据:" << endl;
        Node *list_temp = list_head;
        Node *new_body = new Node();
        /*成员赋值*/
        cin >> new_body->id >> new_body->score;
        new_body->next = NULL;
    
        /*if里的思想是:如果当前是空链表或新数据比第一个数小,则这样写
          else里的思想是:当前链表已经升序排序过,所以满足插入的条件是出现数据比现在的值大或全部id都小于新id
        */
        if(list_temp == NULL || new_body->id < list_temp->id)
        {
            new_body->next = list_temp;
            list_head = new_body;
        }
        else
        {
            while(list_temp->next != NULL && list_temp->id < new_body->id )
            {
                if(list_temp->next->id > new_body->id)
                    break;
                list_temp = list_temp->next;
            }
            new_body->next = list_temp->next;
            list_temp->next = new_body;
        }
    }
    

    链表排序后的插入我认为不好写,这段代码是我经过不断优化的最终写法,也有更简单的方法,那就是在链表尾部添加新数据,接着再次调用排序(例如冒泡法)。
    链表插入的简单思想就是插入作为第一个节点,还是不是作为第一个节点插入。事实上,用双向链表来做插入更简单。

    第六,链表的节点删除

    void delete_point()
    {
        int id;
        cout << "请输入要删除的id:" << endl;
        cin >> id;
        Node *list_temp = list_head, *cache = NULL;
        if(list_head != NULL)
        {
            if(id == list_temp->id)  //删除第一个节点
            {
                cache = list_temp->next;
                delete (list_temp);
                list_temp = NULL;
                list_head = cache;
            }
            else    //删除其他节点
            {
                while(list_temp->next != NULL && id != list_temp->id)
                {
                    cache = list_temp;
                    list_temp = list_temp->next;
                }
                if(id == list_temp->id)
                {
                    cache->next = list_temp->next;
                    delete (list_temp);
                    list_temp = NULL;
                }
            }
        }
    }
    
    

    链表的节点删除就是通过搜索来删除数据,主要是要考虑,当前符合的数据是链表的第一个节点还是其他节点,如果是第一个节点的话,那么就必须得修改list_head的位置。

    第七,链表的清空

    void delete_all()
    {
        if(list_head != NULL)
        {
            Node *list_temp = NULL, *cache = NULL;
            list_temp = list_head;
            while(list_temp != NULL)
            {
                cache= list_temp->next;
                delete(list_temp);
                list_temp = NULL;
                list_temp = cache;
            }
        }
        cout << "链表已清空:" << endl;
    }
    

    链表的清空非常简单,并且链表的清空是必须的!!一定要防止内存泄漏。每次删除,建议令该节点等于NULL,防止出现小问题。

    下面放完整的代码:

    #include <iostream>
    using namespace std;
    struct Node
    {
        int id;
        int score;
        struct Node *next;	//此处*next表示尾巴
    }*list_head;//设list_head,为全局变量的指针
    
    
    void scan_list();    //链表的输入
    void print_list();    //链表的输出
    void cmp_list();     //链表的排序
    void add_point();     //链表节点的添加
    void delete_point();     //链表节点的删除
    void delete_all();      //链表的清空
    
    int main()
    {
        scan_list();
        cout << "链表的创建:" << endl;
        print_list();
        cmp_list();
        cout << "链表的排序:" << endl;
        print_list();
        add_point();
        cout << "链表的添加:" << endl;
        print_list();
        delete_point();
        cout << "链表的删除:" << endl;
        print_list();
        delete_all();
        return 0;
    }
    
    void scan_list()
    {
        int id;
        Node *list_temp = NULL;		//过渡指针,负责将各节点连接
        list_head = NULL;		//作为头部,还没有输入,此时为NULL
        list_temp = list_head;	//将过渡指针指向头部,即从第一个节点开始
        cout << "请输入id和score:" << endl;
        while(cin >> id,id)	//判断输入id是否非0
        {
            Node *list_body = new Node();		//申请空间,这里的括号可以删除,但为了增加程序的可读性,建议保留
            list_body->id = id;
            cin >> list_body->score;
            list_body->next = NULL;
            /*以上是成员赋值,因为是单向链表的使用,所以next必须为NULL*/
            if(list_head == NULL)	//如果新节点是第一个节点,则将这个节点连接到头部list_head,即指针list_head为链表的头地址
                list_head = list_body;
            else	//此时不是第一个节点,使用过渡指针list_temp将节点与新节点连接
                list_temp->next = list_body;
            list_temp = list_body;	//过渡指针移动至新节点
        }
    }
    
    void print_list()
    {
        Node *list_temp = list_head;
        cout << "*** LISTING ***" << endl;
        while(list_temp != NULL)	//判断当前位置是否存在节点
        {
            cout << "id:" << list_temp->id << '\t' << "score:" << list_temp->score << endl;
            list_temp = list_temp->next;
        }
        cout << "*** END OF FILE ***" << endl;
    }
    
    void cmp_list() //升序冒泡排序
    {
        Node *list_temp = NULL; //控制外循环,指向需要排序的第一个节点
        Node *list_end = NULL;  //控制内循环,指向需要排序的最后一个节点
        list_temp = list_head;  //指向表头
        while(list_temp != list_end)
        {
            while(list_temp->next != list_end)
            {
                /*这里的数据交换根据实际情况,但原理相同*/
                if(list_temp->id > list_temp->next ->id )   //当前节点的id与下一个节点的id比较
                {
                    //用整数cache_id和cache_score分别记录当前的位置的id和score
                    int cache_id = list_temp->id;
                    int cache_score = list_temp->score;
                    //下面的代码是交换两个链表的数据
                    list_temp->id = list_temp->next->id;
                    list_temp->score = list_temp->next->score;
                    list_temp->next->id = cache_id;
                    list_temp->next->score = cache_score;
                }
                list_temp = list_temp->next ;
            }
            list_end = list_temp;   //将当前排序的最后一个节点向前挪动一个位置
            list_temp = list_head;  //重新指向表头
        }
    }
    
    void add_point()
    {
        cout << "请输入新数据:" << endl;
        Node *list_temp = list_head;
        Node *new_body = new Node();
        /*成员赋值*/
        cin >> new_body->id >> new_body->score;
        new_body->next = NULL;
    
        /*if里的思想是:如果当前是空链表或新数据比第一个数小,则这样写
          else里的思想是:当前链表已经升序排序过,所以满足插入的条件是出现数据比现在的值大或全部id都小于新id
        */
        if(list_temp == NULL || new_body->id < list_temp->id)
        {
            new_body->next = list_temp;
            list_head = new_body;
        }
        else
        {
            while(list_temp->next != NULL && list_temp->id < new_body->id )
            {
                if(list_temp->next->id > new_body->id)
                    break;
                list_temp = list_temp->next;
            }
            new_body->next = list_temp->next;
            list_temp->next = new_body;
        }
    }
    
    void delete_point()
    {
        int id;
        cout << "请输入要删除的id:" << endl;
        cin >> id;
        Node *list_temp = list_head, *cache = NULL;
        if(list_head != NULL)
        {
            if(id == list_temp->id)  //删除第一个节点
            {
                cache = list_temp->next;
                delete (list_temp);
                list_temp = NULL;
                list_head = cache;
            }
            else    //删除其他节点
            {
                while(list_temp->next != NULL && id != list_temp->id)
                {
                    cache = list_temp;
                    list_temp = list_temp->next;
                }
                if(id == list_temp->id)
                {
                    cache->next = list_temp->next;
                    delete (list_temp);
                    list_temp = NULL;
                }
            }
        }
    }
    
    void delete_all()
    {
        if(list_head != NULL)
        {
            Node *list_temp = NULL, *cache = NULL;
            list_temp = list_head;
            while(list_temp != NULL)
            {
                cache= list_temp->next;
                delete(list_temp);
                list_temp = NULL;
                list_temp = cache;
            }
        }
        cout << "链表已清空:" << endl;
    }
    

    我希望我的这篇博客对链表初学者可以为提供思路,注意,链表是C++/C里很重要的一个部分,还请大家看我的代码不仅仅是复制黏贴那么简单。我的代码或许还存在一些bug或可以完善的地方,欢迎大佬们指点与讨论。


    展开全文
  • 单向链表详解

    2018-08-03 16:50:47
    #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; #define T 1 #define F 0 typedef int Elementtype; //重命名int为Elementtype typedef int Status; //重命名int为Status,作为...struct Node ...
  • 链表--单向链表的基本方法

    千次阅读 2018-07-26 20:28:07
    首先,我们来思考,为什么要使用链表? 相对于数组来说: 优点: 通过索引(数组下标)可以很快地访问数组元素; 缺点:插入/删除元素需要对数组进行调整, 效率低; 而链表: 优点:插入/删除速度很快,而且不用对...
  • 单向循环链表的简单实现

    万次阅读 多人点赞 2017-07-15 20:56:45
     在单向链表中,头指针是相当重要的,因为单向链表的操作都需要头指针,所以如果头指针丢失或者破坏,那么整个链表都会遗失,并且浪费链表内存空间。 单向循环链表的构成:  如果把单链表的最后一个节点的...
  • 7.3 单向链表

    2020-10-14 20:49:53
    7.3 单向链表 链表的基本操作 判断链表是否为空 插入节点 删除节点 遍历 代码 /************************************* * 文件名称:s_list.c * 实现功能:单链表的基本操作:添加、删除、遍历 * 作 者:王 利 涛 ...
  • 单向链表的简单使用

    千次阅读 2016-10-27 19:39:58
    一、单向链表的概念  单向链表是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始。链表是使用指针进行构造的列表,并且是由一个个结点组装起来的,因此又称为结点列表。其中每...
  • 单向链表

    2020-10-06 17:48:25
    单向链表 这个是数据结构中最为基础的两大结构之一,后面的栈和队列都会用到单向链表作为底层,所以学好了单向链表你就成功了一大半了! 1,链表都必须的东西----节点对象node public class Node { private Object data...
  • 链表介绍 链表是以节点的方式来存储,是链式存储 每个节点包含 data 域, next 域:指向下一个节点. 如图:发现链表的各个节点不一定是连续存储. 链表分带头节点的链表和没有头节点的链表,根据实际的需求来确定 ...
  • 前段时间学习
  • 单向链表:只有一个指向下一个节点的指针。 优点:单向链表增加删除节点简单。遍历时候不会死循环; 缺点:只能从头到尾遍历。只能找到后继,无法找到前驱,也就是只能前进。 适用于节点的增加删除。 双向链表...
  • 浅谈单链表与双链表的区别

    万次阅读 多人点赞 2018-11-13 17:18:25
    昨天面试官面试的时候问了我一道关于链表的问题:情境如下 面试官:请说一下链表跟数组的区别? 我:数组静态分配内存,链表动态分配内存;数组在内存中连续,链表不连续;数组利用下标定位,时间复杂度为O(1),...
  • 单向链表反转(倒置)问题

    万次阅读 多人点赞 2017-03-14 21:42:31
    今天遇到单向链表的反转的问题,于是静下心来好好想了一番。 解题思路如下图:假设当前创建好的链表如下:首先让头节点与第一个元素节点断开,但是要注意在断开之前需要用p指针指向第一个元素节点来保存第一个元素...
  • 主要是单向链表,单向循环链表,双向链表,双向循环链表四个部分,每个部分都包括了初始化,创建,插入,删除的基本操作,并总结了各个操作的核心代码。抽空可以看看Linux内核自带的链表(list.h)写法,增进学习。...
  • 单向链表的实现C++

    千次阅读 多人点赞 2018-04-15 11:34:07
    原因是单向列表中的数据结构包含的只有下一个数据的指针,这样就说明了,单向链表是不可逆向进行操作。所有的操作都需要正向去操作。这时我们必须要知道第一个数据的地址,才能从第一个数据往后访问其他数据。(2)...
  • 昨天写了单向链表的代码,今天上午把单向循环链表的程序给敲完了。链表的相关操作一样的,包含链表的创建、判断链表是否为空、计算链表长度、向链表中插入节点、从链表中删除节点、删除整个链表释放内存。如果单向...
  • 7-1 单向链表4 (10 分)定义单向链表:输入若干个正整数(输入-1为结束标志),要求按输入数据的逆序并输出。 输入输出示例:括号内为说明 输入样例: 1 2 3 4 5 6 7 -1 输出样例: 7 6 5 4 3 2 1 c++编译器 #include&...
  • 在牛客网上刷题的过程遇到很多链表的问题,所以自己又结合着传智播客上的视频把链表整理了一下,本文是在上文的基础上操作的,c++之链表篇1:单向链表的创建,打印,删除,插入,销毁等基本操作的。 本文中的单链表...
1 2 3 4 5 ... 20
收藏数 59,842
精华内容 23,936
关键字:

单向链表