精华内容
下载资源
问答
  • C语言链表节点排序

    千次阅读 2019-05-07 19:54:45
    初次用到链表排序还是在C语言课程设计上,当时想着要把代码发到CSDN上,结果一拖再拖到现在。 我的课程设计项目为“学生成绩管理系统”,所用链表为双向链表链表。 涉及到成绩管理则避免不了成绩的排序。 结构体中...

    初次用到链表的排序还是在C语言课程设计上,当时想着要把代码发到CSDN上,结果一拖再拖到现在。

    我的课程设计项目为“学生成绩管理系统”,所用链表为双向链表链表。
    涉及到成绩管理则避免不了成绩的排序。
    结构体中的项目包括:

    1. 学生成绩;
    2. 学生姓名;
    3. 学生学号;
    4. 结构体的头指针与尾指针;
      先创建结构体:
    #include"stdio.h"
    #include"stdlib.h"
    #include"string.h"
    struct student
    {
    	struct student *ahead;
    	float grade[10];
    	char name[10];
    	char x[10];
    	struct student *next;
    }*head, *end, *New, *get, *stu;
    

    设置head指针和end指针。head指向头结点,end始终指向尾节点。
    输入数据:

    int input(int N, char **G)//数据输入
    //变量说明:“N”为考试的科目数量,此处**G为字符串指针数组,其中存储着考试科目。
    {
    	int i, c = 1, icount = 0, s[10], j, k, d;
    	char r[10];
    	for (j = 0; j < 10; j++)
    		s[j] = 0;
    	while (c)
    	{
    		New = (struct student *)malloc(sizeof(struct student));
    		printf("\t\t输入该名学生姓名(结束请按‘0’):");
    		scanf("%s", New->name);
    		if (New->name[0] != 48)
    		{
    			printf("\t\t输入该名学生学号:");
    			scanf("%s", r);
    			icount++;
    			strcpy(New->x, r);
    			New->grade[N] = 0;
    			for (i = 0; i < N; i++)
    			{
    				printf("\t\t%s成绩:", G[i]);
    				scanf("%f", &New->grade[i]);
    				if (New->grade[i] < 60)
    					s[i]++;
    				New->grade[N] = New->grade[N] + New->grade[i];
    			}
    			strcpy(New->mima, "1234");
    			end->next = New;
    			New->ahead = end;
    			end = New;
    			end->next = NULL;
    		}
    	}
    	else
    	{
    		c = 0;
    	}
    }
    

    链表已经创建完成,现在只需要向其中添加数据,下一步祭出我屌炸天 的链表节点排序代码?
    此代码运用简单选择排序的排序方法。即,先比较两个节点中数据的大小,并两个选中较大或较小的一个。并让选中的节点与下一个节点中的数据比较直到最后一个节点。比较完毕后将最小的节点接到链表的最后。
    当然,开始排序之前,我创建了一个空节点让其存储成绩的数组的每一个元素都等于“-1”将其接到了链表的最后作为新的有序链表与旧的无序链表的边界。在排序完毕后程序自动将此空节点删除。得到的就是新的有序数组。

    1.排序前的准备阶段(假设此处为升序排序)

    主要步骤为:

    1. 创建三个结构体指针“ *min”、“*xunow”、“ *uend”;
    2. uend就是我添加的边界空指针;
    int paixu(int N)//成绩排序
    {
    	int i;//在程序的后便会让用户选择升序还是降序排序,变量i的作用是根据i的值选择排序方式。若i为1则降序排列,0则升序排列
    	struct student *min, *xunow, *uend;
    	uend = (struct student *)malloc(sizeof(struct student));
    	uend->grade[0] = -1;
    	uend->next = NULL;
    	uend->ahead = end;
    	end->next = uend;
    

    2.排序执行阶段

    上一步中创建的三个结构体指针已经用掉了一个,在这一步中“min”代表比较值最小的节点。"xunow"表示当前与min节点比较的节点。

    1. 通过简单选择排序找出旧链表中的最小值节点;
    2. 将此最小值节点接到链表的最后;
    printf("\n\t\t升序排序(0)     降序排序(1)\n\t\t");
    	scanf("%d", &i);
    	for (min = head->next; min->next->grade[0] != -1; min = head->next)
    	{
    		xunow = min->next;
    		if (i == 0)
    		{
    			do
    			{
    				if (xunow->grade[0] < min->grade[0])
    				{
    					min = xunow;
    				}
    				xunow = xunow->next;
    			} while (xunow->next->grade[0] != -1 && xunow->grade[0] != -1 && min->next->grade[0] != -1);
    			min->ahead->next = min->next;
    			min->next->ahead = min->ahead;
    			min->ahead = uend;
    			uend->next = min;
    			uend = min;
    		}
    		else
    		{
    			do
    			{
    				if (xunow->grade[0] > min->grade[0])
    				{
    					min = xunow;
    				}
    				xunow = xunow->next;
    			} while ( xunow->grade[0] != -1 && min->next->grade[0] != -1);
    			min->ahead->next = min->next;
    			min->next->ahead = min->ahead;
    			min->ahead = uend;
    			uend->next = min;
    			uend = min;
    		}
    		
    	}
    

    3.排序完成收尾阶段

    在执行完上步代码后,表明排序基本完成。按照步骤,此时边界空节点的旧链表一侧还有最后一个具有有效数据的节点,即存储最大数据的节点。现在只需要将此节点与边界节点一起转移到整个链表的最后再删除边界节点,就能最终完成链表的排序。

        min = head->next;
    	xunow = min->next;
    	head->next = xunow->next;
    	xunow->next->ahead = head;
    	xunow->next = NULL;
    	min->ahead = uend;
    	uend->next = min;
    	uend = xunow;
    	end = uend->ahead;
    	uend->ahead->next = NULL;
    	free(uend);
    	return 0;
    }
    

    这就是自己在本学期的课程设计中,灵光一现敲出的链表节点排序代码。虽然不够简洁但不管怎么样这段代码还是实现了功能,即节点排序。

    展开全文
  • 链表节点排序算法,采用(冒泡排序)。 定义一个指针end,end最开始时赋值为空,再经过一次比较后,找到一个最大值,将该最大值的指针赋给end;每次循环找到该次循环中的最大值,都将其指针赋值给end,等于说end每次...

    对链表排序有两种方法:
    (1)比较了两个节点的大小后,对指针进行改变,从而交换节点的顺序;
    (2)比较了两个节点的大小后,只交换数据域,而不改变指针,从而交换节点的顺序。
    第二种办法比较简单,本文主要对第二种方法进行讲解。
    链表节点排序算法,采用(冒泡排序)。
    定义一个指针end,end最开始时赋值为空,再经过一次比较后,找到一个最大值,将该最大值的指针赋给end;每次循环找到该次循环中的最大值,都将其指针赋值给end,等于说end每次循环结束,都会向前移动一个节点,这样就可以根据end和头节点是否相等作为排序结束条件,因为end指向的节点及其后面的节点中的数据肯定是大于end之前的,所以没有必要比较,因此每次循环根据是否到达end作为该次循环结束条件。
    最开始: 定义一个指针end,end最开始时赋值为空。在这里插入图片描述
    第一次比较:找到一个最大值,将该最大值的指针赋给end;end就指向了第一次找到的最大值。
    在这里插入图片描述

    第n次比较:每次循环找到该次循环比较中的最大值,都将其指针赋值给end。
    在这里插入图片描述

    最后一次循环:每次循环结束,end都会向前移动一个节点,这样就可以根据end和头节点是否相等作为整个排序结束的条件。
    在这里插入图片描述
    程序源码:
    //排序源码

    link_node_t* bubblesort(link_node_t* head)     //head是有头链表
    {  
        head = head->next;                  
        if (head == NULL) return NULL;            
        //定义一个尾,初值为空,以后为每次的最大值  
        link_node_t* end = NULL;  
        while (end != head)  
        {  
            //p和pnext一前一后
            link_node_t* p = head;               //p在前
            link_node_t* pnext = head->next;     //pnext在后  
            while (pnext != end)  
            {  
                //比较相邻的节点数据
                if (p->size < pnext->size)          
                {  
                    //数据交换
                    swapS(p->data, pnext->data);      //交换函数名(字符串)
                    swapI(&p->size, &pnext->size);   //交换数据(整型)
                }  
                //p和pnext同时向后移动一个节点
                p = p->next;  
                pnext = pnext->next;  
            }  
            //该次循环结束,找到的该次循环中的最大值。
            end = p;  
        }  
        return head;  
    } 
    

    数据交换程序

    这里封装两个交换函数,一个是对字浮串进行交换,一个是对整型进行交换。
    void swapI(int* a, int* b)  
    {  
        int temp = 0;  
        temp = *a;  
        *a = *b;  
        *b = temp;  
    }  
    void swapS(char* arr, char* brr)  
    {  
        char temp[N] = {0};  
        strcpy(temp,arr);  
        strcpy(arr,brr);  
        strcpy(brr,temp);  
    } 
    
    展开全文
  • 根据成绩高低进行链表节点排序,一个比较简单的功能的实现,初学者可能会遇到单个的成绩排序可以解决,但是需要把结点中的其他数据随着成绩的顺序,而保持不遍。可能有点困难或者没有思路。一下可以提供一个参考。
  • 如下链表的增删改查,并没完善,代码有待优化,这牵涉算法。我的时间似乎挤得好满,抽不出时间来优化,基础也薄弱,过段时间基础好点了来改,参考的同道谅解下。 #include &amp;amp;amp;amp;amp;amp;amp;amp;...

    链表的增删改查,这儿加了链表节点的排序问题,希望对初学者有帮助。
    代码如下:

    #include "pch.h"
    #include <iostream>
    #include<stdlib.h>
      //链表的增删改查
    typedef int DATA;
    struct LinkList
    {
    	DATA data;
    	LinkList* next;
    };
    LinkList* pHead = NULL;
      //建立链表,添加节点
    void Append(DATA data)
    {
    	LinkList* p1 = pHead;
    	LinkList* news = (LinkList*)malloc(sizeof(LinkList));
    	if (news != NULL)
    	{
    		news->data =data;
    		news->next = pHead;
    		pHead = news;
    	}
    	else
    	{
    		printf("没有申请成功!");
    	}
    }
      //记录链表长度,如果没有特殊要求可以不必记录链表长度
    int listLen()
    {
    	int nlength = 0;
    	LinkList* p = pHead;
    	while (p)
    	{
    		nlength++;
    		p = p->next;
    	}
    	return nlength;
    }
      //在链表中插入节点
    int InsertNode(DATA data, DATA data1)//InsertNode(插入的位置,要插入的数据)
    {	
    	LinkList* p = pHead;
    	while (p)
    	{
    		if (p->data == data)
    		{
    			LinkList* newsNode = (LinkList*)malloc(sizeof(LinkList));
    			newsNode->data = data1;
    			newsNode->next = p->next;
    			p->next = newsNode;
    			return 1;
    		}
    		p = p->next;
    	}
    	return 0;
    }	
    
       //删除节点
    int deleteNode(int data)
    {
    	LinkList* p = pHead;
    	LinkList* p1 = NULL;
    	if (pHead->data== data)
    	{
    		pHead = pHead->next;
    		free(p);
    		return 1;
    	}
    	while (p)
    	{	
    		if (p->data == data)
    		{
    			p1->next = p->next;
    			free(p);
    			return 1;
    		}
    		p1 = p;//保留节点
    		p = p->next;//下一个节点
    	}
    	return 0;
    }
      //修改节点里的值
    int modify(DATA data, DATA ndata)//modify(源数据,要赋值的数据)
    {
    	LinkList* p = pHead;
    	while(p)
    	{
    		if (p->data==data)
    		{
    			p->data = ndata;
    			return 1;
    		}
    		p = p->next;
    	}
    	return 0;
    }
      //查询节点,指定数据查找
    int contentNode(DATA data)
    {
    	LinkList* p = pHead;
    	while (p)
    	{
    		if (p->data==data)
    		{
    			printf("位置在:%p 值为:%d", p, p->data);
    			return 1;
    		}
    		p = p->next;
    	}
    	return 0;
    }
    
      //对链表节点里的值,在这儿就是数字,进行从小到大排序。可能不太好理解,可以用印象笔记圈点画图分析,只要理解p1和p2的指针指向的变化,就能理解这个排序
    void orderBy()
    {
    	LinkList* p = pHead;	
    	while (p)
    	{
    		LinkList* p1 = p->next;
    		LinkList* p2 = p;	
    		while (p1)
    		{	
    			if (p2->data > p1->data)
    			{
    				p2 = p1;
    			}
    			p1 = p1->next;
    		}					
    		if (p2!=p)
    		{
    			DATA temp = p->data;
    			p->data = p2->data;
    			p2->data = temp;
    		}
    		p = p->next;
    	}
    }
    
      //打印链表信息
    void Print()
    {
    	LinkList* p = pHead;
    	while (p)
    	{		
    		printf("\n链表的值:%d 地址:%p 下一个地址:%p\n", p->data, p,p->next);
    		p=p->next;
    	}	
    }
    int main()
    {
    	Append(5);
    	Append(4);
    	Append(3);
    	Append(2);
    	Append(1);
    	Append(33);
    	Append(49);
    
    	//修改前
    	Print();
    
    	//修改后
    	//modify(33,500);
    	//Print();
    	//printf("链表的长度 %d\n",listLen());	
    	InsertNode(33, 1000);//插入一个节点
    	//deleteNode(33);//删除一个节点
    	//contentNode(33);//查询数据
    	Print();	
    	system("pause");
    }
    
    展开全文
  • 给定一个单项链表,要求实现一个算法,把链表分成两部分,前一部分全是下标为偶数的节点,后一部分全是下标为奇数的节点。不能分配新的内存空间,在操作队列时,不可更改节点内容,只能更改节点的next指针。

    更详细的讲解和代码调试演示过程,请参看视频
    如何进入google,算法面试技能全面提升指南

    给定一个单项链表,要求实现一个算法,把链表分成两部分,前一部分全是下标为偶数的节点,后一部分全是下标为奇数的节点,例如给定链表为下图的第一个队列,要求编写一个算法,将链表转换为第二个队列:

    这里写图片描述

    要求算法不能分配多余的内存,同时,在操作链表是,不能更改节点内部的内容,只能更改节点的next 指针。

    如果允许分配新内存,那么我们可以先把奇数下标的节点存成一个队列,把偶数下标的节点存成另一个队列,然后把两队列收尾连接即可。但限制条件是不能分配新内存,因此问题的解决需要一点小技巧。

    我们可以这么做,用一个指针evenHead,专门指向偶下标节点,用另一个指针,oddHead指向奇下标节点。我们注意到,偶下标节点的下一个节点正好是奇下标节点,同时奇下标节点的下一个节点正好是偶下标节点。因此,如果我们把 evenHead.nex 指向 oddHead.next, oddHead.next 指向evenHead.next ,那么,我们就能实现偶下标节点连在一起,奇下标节点连在一起的效果,例如:

    这里写图片描述

    evenHead 指向节点0,oddHead指向节点1, oddHead.next 指向节点2,如果把evenHead的next指针设置成oddHead的next, 那相当于把节点0和2连在一起,然后把evenHead挪到它的next指针指向的节点:

    这里写图片描述

    此时evenHead的next指向的是节点3,正好是一个奇下标节点,此时把oddHead的next指向evenHead.next那么就可以实现奇数节点连成一体了:

    这里写图片描述

    将上面操作循环下去,直到遍历完整个队列,那么我们的目标就达到了。这个算法没有分配新内存,同时只需对整个链表遍历一次足够,因此算法复杂度是O(n),空间复杂度是O(1).

    实现代码如下:

    
    public class EvenOddListSorter {
        private Node listHead;
        private Node evenHead, oddHead;
    
        public EvenOddListSorter(Node head) {
            this.listHead = head;
        }
    
    
        public Node sort() {
            if (listHead == null || listHead.next == null) {
                return listHead;
            }
    
            evenHead = listHead;
            oddHead = listHead.next;
            Node node = oddHead;
    
            while (evenHead.next != null && oddHead.next != null) {
                if (oddHead.next != null) {
                    evenHead.next = oddHead.next;
                    evenHead = evenHead.next;
                }
    
                if (evenHead.next != null) {
                    oddHead.next  = evenHead.next;
                    oddHead = oddHead.next;
                }
            }
    
            evenHead.next = node;
            return listHead;
        }
    }
    

    sort函数所实现的正好是我们前面所描述的逻辑。主函数实现如下:

    public class LinkList {
        public static void main(String[] args) {
            ListUtility util1 = new ListUtility();
            Node head = util1.createList(10);
            EvenOddListSorter sorter = new EvenOddListSorter(head);
            head = sorter.sort();
            util1.printList(head);
        }
    }

    我们先构造一个长度为10的队列,然后对其进行节点的奇偶排序,最后打印出的结果如下:

    0 -> 2 -> 4 -> 6 -> 8 -> 1 -> 3 -> 5 -> 7 -> 9 -> null

    由此可见,我们算法的实现是正确的。更详细的代码讲解和调试,请参看视频。

    更多技术信息,包括操作系统,编译器,面试算法,机器学习,人工智能,请关照我的公众号:
    这里写图片描述

    展开全文
  • 单向链表节点的移动(排序

    千次阅读 2018-02-23 09:45:54
    在本篇文章中,主要通过举例的方式来帮大家理解单向链表节点的移动。本篇文章中创建节点用如下表示typdef struct node{ int date;//定义数据域 struct node * next;//定义指针域 } ElemSN; 例一:设head指向一...
  • 通过给链表排序,交换节点时,明明已经交换数据域,后面还得交换next指针:typedef struct Node ...//链表节点排序 int NodeSort(Node *pHead) { if (pHead == NULL) { return -1; } Node *pPre =
  • 删除链表节点

    千次阅读 2018-11-19 14:18:09
    问题一:在O(1)时间内删除链表节点。给定单向链表的头指针和一个节点指针,定义一个函数在O(1)时间内删除该节点。链表节点定义如下: struct ListNode { int m_nValue; ListNode *m_pNext; }; 解题思路:在单向...
  • 链表排序

    多人点赞 热门讨论 2021-09-11 12:29:42
    148. 排序链表链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。 进阶: 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗? 示例 1: 输入:head = [4,2,1,3] 输出:[1...
  • 链表的各种操作 删除节点 增加节点 排序 查询 C语言
  • 链表插入排序

    千次阅读 2016-04-26 22:11:16
    题目描述:用插入排序链表排序 样例:Given 1->3->2->0->null, return 0->1->2->3->null 之前,在我的博文“将排序链表转换为二分查找树”(详见:点击打开链接)中已经介绍了链表的快慢指针法,以及“摘链”...
  • c语言单链表节点排序

    千次阅读 2019-10-11 23:14:23
    c语言中的链表节点排序,然后查过网上一些源码,有很多就没有实现这个功能,有的只是单个数据修改而已,所以刚巧从书中找到一个案例,就分享一波 源码: void sort(Stu head){ Stu p,q,r,t; int flag = 1; while...
  • LintCode 链表插入排序

    千次阅读 2017-03-27 22:28:14
    1.描述 用插入排序链表排序 样例 Given 1->3->2->0->null, return 0->1->2->3->null 2.分析 插入排序是十分常见的排序方式之一,类似于数组的插入排序,此题...中的节点分别插入到dummy链表中完成对head链表排序
  • 1.0.快速排序_数组 快速排序 1.快速排序_链表 2.0:链表值相邻节点交换: 链表值相邻节点交换 2.0:数组冒泡排序 数组_冒泡排序 2.冒泡排序_链表链表冒泡排序 ...
  • 双向链表排序

    2020-03-03 20:35:49
    用单个指针单一方向进行排序,利用选择法排序的方法进行排序,对于链表排序的关键在于要和数组的排序方法一一对应,由于链表并不知道有多少个节点,也即不知道要进行多少次循环,所以对于数组中的惯用for循环就不...
  • 归并排序(算法交换链表节点,时间复杂度O(nlogn),不考虑递归栈空间的话空间复杂度是O(1)) 本文地址 首先用快慢指针的方法找到链表中间节点,然后递归的对两个子链表排序,把两个排好序的子链表合并成一条...
  • 利用归并排序,我们可以将时间复杂度降至O(nlogn), 并且我们是对链表进行排序,可以通过修改引用来更改节点顺序,无需像数组一样开辟而外的空间。 利用递归实现链表的归并排序有两个环节: 分割cut环节: 我们可以...
  • C#单向链表排序

    2019-10-06 18:43:37
    C#的单向链表排序一、创建无序单向链表二、排序方法(按节点的值从小到大排序)1、暴力排序2、插入排序 一、创建无序单向链表 首先,要创建一些无序的单向链表用于测试。 public class ListNode { public int val...
  • /************************************************************...* 面试题18: 删除链表节点 * 题目二:删除链表中重复的节点,在一个排序的链表中如何删除重复的节点。 * * 分析:从头遍历整个链表,如果当前节点...
  • 173链表插入排序

    2017-07-10 21:25:46
    对于链表而言,要依次从待排序链表中取出一个节点插入到已经排好序的链表中,也就是说,在单链表插入排序的过程中,原链表会截断成两部分,一部分是原链表中已经排好序的节点,另一部分是原链表中未排序节点,...
  • 16_链表的定义 定义:  n个节点离散分配;彼此通过指针相连;每个节点只有一个后续节点,首节点没有前驱节点,尾节点没有后续节点。 ... 首节点:第一个有效...加头节点的目主要是为了方便对链表的操作。 头指针
  • 链表排序算法

    万次阅读 多人点赞 2018-04-18 10:34:09
    排序算法概述盗个图转自:https://www.cnblogs.com/onepixel/articles/7674659.html排序算法复杂度由于是链表排序,首先定义链表节点数据结构common.htypedef struct Node LNode; struct Node { int data; LNode ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 113,192
精华内容 45,276
关键字:

链表节点排序