精华内容
下载资源
问答
  • 双向链表排序

    万次阅读 2018-07-17 20:52:18
    双向链表的结构体,包括一个前驱节点的指针、一个后继节点的指针以及一个存储数据的data域,initList函数初始化单节点的双链表,addList函数采用头插入方法添加一个节点到双链表中,sort函数实现了对双链表的排序,...

    双向链表的结构体,包括一个前驱节点的指针、一个后继节点的指针以及一个存储数据的data域,initList函数初始化单节点的双链表,addList函数采用头插入方法添加一个节点到双链表中,sort函数实现了对双链表的排序,采用头插入方式建成的双链表的头结点(存储65535的那个节点)必然在末尾(其实双链表没有首尾之说,只是把它当作末尾),排序的时候,1.首先从该节点处,每次查找前驱节点,并记录data获取链表中data最大的节点,并记录指向这个节点的指针和其值。2.将此节点采用头插入的方式插入到链表中(注意要先删除这个节点在链表中的位置)3.再次从头节点处,通过前驱节点遍历整个链表(此时要去掉第一次找到的最大值)找到最大值。

    typedef struct node{
        int data;
        struct node *prior,*next;
    }Link;

     

    void initList(Link *head){//初始化头结点

        head->next = head;
        head->prior = head;
        head->data = 65535;
    }

    void addList(Link *head,int data){//创建链表

        Link *tmp;
        tmp = (Link *)malloc(sizeof(Link));
        tmp->data = data;
        tmp->next = head->next;
        head->next->prior = tmp;
        head->next = tmp;
        tmp->prior= head;
    }

     

    void sort(Link *head){

    Link *p,*tmp,*flag;

    int max;

    p = (Link *)malloc(sizeof(Link));

    tmp = (Link *)malloc(sizeof(Link));

    flag = (Link *)malloc(sizeof(Link));

    tmp  = head->prior;

    max = tmp->data;

    flag = tmp;

    p = tmp->prior;

    while(p->data != 65535){//找到值最大的节点并且标记

    if(p->data > max){

    max = p->data;

    flag = p;

    flag->data = max;

    }

    p = p->prior;

    }

    if(flag->data!=head->next->data)

    {//交换最大值点到头节点后

    flag->prior->next = flag->next;

    flag->next->prior = flag->prior;

    flag->next = head->next;

    flag->prior = head;

    head->next->prior = flag;

    head->next = flag;

    }

    while(head->prior->data != flag->data){

    tmp = head->prior;//重新寻找时总是从表尾,也就是头结点的前驱开始。

    p = tmp->prior;   //从后往前寻找

    while(p->data != flag->data){//找到要交换的节点

    if(p->data > tmp->data){

    tmp = p;

    }

    p = p->prior;

    }

    {//交换两个节点

    tmp->prior->next = tmp->next;

    tmp->next->prior = tmp->prior;

    tmp->next = head->next;

    tmp->prior = head;

    head->next->prior = tmp;

    head->next = tmp;

    }

    }

    }

    主函数的调用代码就比较简单了。

    int _tmain(int argc, _TCHAR* argv[])
    {
        Link *head,*p;

        head =(Link *)malloc(sizeof(Link));

        p =(Link *)malloc(sizeof(Link));

        int i;

        int a[15]={7,4,2,7,5,8,6,3,2,4,5,7,98,3,4};

        initList(head);

        for(i=0;i<15;i++){

            addList(head,a[i]);

        }

        p = head->next;

        while(p->data!=65535){

            printf("%d<-->",p->data);    

            p = p->next;

        }

        printf("\n");

        sort(head);

        p = head->next;

        while(p->data!=65535){

            printf("%d<-->",p->data);    

            p = p->next;

        }

        printf("\n");
        getchar();
    }

    展开全文
  • 经典的双向链表排序算法。涵盖创建,删除,排序,获取,增加等
  • 用双向起泡排序法对带头结点的双向链表按升序进行排序
  • (四)C++双向链表排序

    千次阅读 2018-11-09 16:40:10
    C++双向链表排序 建立一个长度为n的带头结点的双向链表,使得该链表中的数据元素递增有序排列。(必须使用双向链表完成,数据类型为整型。) 输入 第一行:双向表的长度; 第二行:链表中的数据元素。 输出 ...

                                           C++双向链表排序

    建立一个长度为n的带头结点的双向链表,使得该链表中的数据元素递增有序排列。(必须使用双向链表完成,数据类型为整型。)

    输入

    第一行:双向表的长度; 
    第二行:链表中的数据元素。

    输出

    输出双向链表中的数据元素的值。

    样例输入

    10
    2 4 6 3 5 8 10 21 12 9
    

    样例输出

    2 3 4 5 6 8 9 10 12 21
    // 10双向链表的操作问题.cpp: 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include <iostream>
    using namespace std;
    typedef int ElemType;
    class List {
    	public:
    		List();
    		List(int data);
    		void Create_List(int len);
    		void Sort();
    		void Output();
    		~List();
    	private:
    		ElemType Data;
    		List *Prior;
    		List *Next;
    };
    List::List() {
    	this->Prior = NULL;
    	this->Next = NULL;
    }
    List::List(int data) {
    	this->Data = data;
    }
    void List::Create_List(int len) {
    	List *L,*Node;
    	int data;
    	int i=0;
    	L = this;
    	this->Data = len;
    	while (i<len)
    	{
    		cin >> data;
    		Node = new List(data);
    		L->Next = Node;
    		Node->Prior = L;
    		L = Node;
    		i++;
    	}
    	L->Next = NULL;
    }
    void List::Sort() {
    	List *Node;
    	int Temp;
    	int i, j;
    	for (i = 0; i < this->Data;i++) {
    		Node = this->Next;
    		for (j = 0; j < this->Data - i - 1;j++) {
    			if (Node->Data > Node->Next->Data) {
    				Temp = Node->Data;
    				Node->Data = Node->Next->Data;
    				Node->Next->Data = Temp;
    			}
    			Node = Node->Next;
    		}
    	}
    }
    void List::Output() {
    	List *L = this->Next;
    	while (L) {
    		cout << L->Data << " ";
    		L = L->Next;
    	}
    }
    List::~List() {
    	if (this->Next) {
    		delete this->Next;
    	}
    }
    int main()
    {
    	int Len;
    	List *Head = new List;
    	cin >> Len;
    	Head->Create_List(Len);
    	Head->Sort();
    	Head->Output();
    	delete Head;//养成好习惯
        return 0;
    }
    
    

     

    展开全文
  • 一个双向链表排序问题

    千次阅读 2019-05-05 11:37:07
    一个双向链表排序问题: 题目: 建立一个长度为n的带头结点的双向链表,使得该链表中的数据元素递增有序排列。(必须使用双向链表完成,数据类型为整型。) 思路: 根据题目建立好该双向链表(尾插法),然后用个...

    一个双向链表排序问题:

    题目:

    建立一个长度为n的带头结点的双向链表,使得该链表中的数据元素递增有序排列。(必须使用双向链表完成,数据类型为整型。)

    思路:
    根据题目建立好该双向链表(尾插法),然后用个指针依次查找,先从第一个节点往后走,找出最大节点max,再将max和最后一个元素交换,第一遍结束(即奇数遍正向查找);第二遍,从最后一个节点开始倒着往前找,找到最小节点min,与第一个节点交换,第二遍结束(即偶数遍反向查找);第三遍,再从指针此刻的位置即第2个节点往后找,找到第二大节点,与倒数第二个节点交换;第四遍,倒着往前找,。。。。依次循环,做n-1次。

    typedef int DataType;
    typedef struct node
    {
    	DataType data;
    	struct node *prior;//前域
    	struct node *next;//后继
    }Node;//双向链表的创建
    
    void Create(Node *&L,DataType a[],int n)
    {
    	int i;
    	Node *s,*r;
    	L=(Node*)malloc(sizeof(Node));
    	r=L;
    	for(i=0;i<n;i++)
    	{
    		s=(Node*)malloc(sizeof(Node));
    		s->data=a[i];
    		r->next=s;
    		s->prior=r;
    		r=s;
    	}
    	r->next=NULL;	
    }//尾插法创建双链表
    
    void Sort(Node *&L,int n)//排序
    {
    	int i,j,temp;
    	int count=n;
    	Node *p=L; 
    	Node *min,*max; 
    	p=p->next;
    	for(i=1;i<count;i++)
    	{	
    		if(i%2!=0)//第奇数遍反向
    		{
    			min=p;		
    			for(j=0;j<n-1;j++)
    			{
    				p=p->next;
    				if(p->data<min->data)
    				{
    					temp=min->data;
    					min->data=p->data;
    					p->data=temp;
    				}
    			}
    			n--;
    		}
    		else//第偶数遍正向
    		{
    			max=p;
    			for(j=1;j<n;j++)
    			{
    				p=p->prior;
    				if(p->data>max->data)
    				{
    					temp=max->data;
    					max->data=p->data;
    					p->data=temp;
    				}
    			}
    			n--;
    		}
    	}
    }
    
    //就是来回折返查找。
    
    展开全文
  • 1. 双向链表的定义 【百度百科】 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和...

    1. 双向链表的定义


    【百度百科】

    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。

    • 链表中的每个节点的成员由两部分组成:
      1. 数据域:专门用来保存各个成员的信息数据。
      2. 指针域:专门用来与其他节点链接。

    2. 结构体中的两个重要指针


    直接后继 & 直接前驱
    • 直接后继:我个人习惯称之为后向指针,也习惯定义为pnext,该指针指向下一个节点,如果该节点为尾节点,那么pnext指向NULL

    • 直接前驱:同样我习惯称之为后向指针,也习惯定义为prev,该指针指向前一个节点,如果该节点为头节点,那么prev指向NULL


    3. 双向链表中节点的成员排序(冒泡排序)


    在排序之前我们需要明确一点:<明确我们操作的链表的头节点的数据域是否写有数据>

    因为有时候程序员写代码时为了链表方便操作会专门创建一个表头(头结点),即不存放数据的表头。


    3.1头节点数据域为空

    接下来我们来看几段代码:

    typedef struct student
    {
    	int num;
    	char name[20];
    	float score;
    	struct student *prev;
    	struct student *pnext;
    }STU,*PSTU;
    //1.首先我们定义一个结构体,有数据域(前三个)和指针域(后两个)两部分
    //2.将结构体和结构体指针分别重命名为STU,PSTU
    

    冒泡排序代码如下:

    #incldue <stdio.h>
    
    PSTU score_sort(PSTU head)				  //函数返回值为头指针,形参也为头指针
    {
    	int i=0,j=0;
    	int n=num_of_stu(head);              //调用统计节点个数的函数
    	PSTU p=head;                         //定义两个临时指针来进行数据处理
    	PSTU pn=head;                        //p和pn总是两个相邻的节点,且pn在p之后
    
       //****冒泡排序****//
    	for(i=0;i<n;i++)
    	{
    		p=head->pnext;
    		pn=p->pnext;
    		for(j=0;j<n-1-i;j++)
    		{
    			if(p->score < pn->score)          //判断,条件成立之后交换位置
    			{
    				if(pn->pnext==NULL)           //判断是否为尾节点
    				{
    					//**交换位置代码**//
    					p->pnext=pn->pnext;
    					pn->prev=p->prev;
    					pn->pnext=p;
    					p->prev->pnext=pn;
    					p->prev=pn;
    					//**位置交换结束**//
    				}
    				else
    				{
    					//**交换位置代码**//
    					p->pnext=pn->pnext;
    					pn->prev=p->prev;
    					pn->pnext=p;
    					p->prev->pnext=pn;
    		//下一行请注意//	
    					pn->pnext->prev=p;
    					p->prev=pn;
    					//**位置交换结束**//
    					pn=p->pnext;      //位置交换结束之后进行指针偏移,pn指向p的下一个节点
    				}
    			else                                       //条件不成立
    			{
    				p=p->pnext;
    				pn=p->pnext;
    					//如果未发生位置交换,则两个指针都要发生偏移
    			}
    		}
    	}
    	return head;		
    }
    

    重点:
    在上一段代码中一定要注意我在代码前面注释的那一行,并且要与不是尾结点的情况对比来看,你会发现少了一行代码, pn->pnext->prev=p,我先解释一下这一行代码是什么意思,从上面的代码可以看出两个临时指针的位置关系为p总是在Pn的前面,那也就是说满足交换位置条件之后进行位置交换,交换之后两个临时指针位置就随之交换,在交换的过程中,假如有尾结点,那么pn的后向指针指向NULL,随之 pn->pnext->prev 就会出现段错误


    3.2头节点数据域不为空(一般不建议)

    这种方式在数据处理上面会比较麻烦,一旦头结点的数据发生位置交换(比如排序,插入结点,删除结点等),那么在函数的封装是就要考虑将新的头结点返回。

    接下来我们来看几段代码:

    typedef struct student
    {
    	int num;
    	char name[20];
    	float score;
    	struct student *prev;
    	struct student *pnext;
    }STU,*PSTU;
    //1.首先我们定义一个结构体,有数据域(前三个)和指针域(后两个)两部分
    //2.将结构体和结构体指针分别重命名为STU,PSTU
    

    冒泡排序部分核心代码如下:

    #incldue <stdio.h>
    
    PSTU score_sort(PSTU head)				  //函数返回值为头指针,形参也为头指针
    {
    	int i=0,j=0;
    	int n=num_of_stu(head);              //调用统计节点个数的函数
    	PSTU p=head;                         //定义两个临时指针来进行数据处理
    	PSTU p1=head;                        //p和pn总是两个相邻的节点,且pn在p之后
    
       //****冒泡排序****//
    	for(i=0;i<n;i++)
    	{
    		p=head->pnext;
    		pn=p->pnext;
    		for(j=0;j<n-1-i;j++)
    		{
    			if(p->score < pn->score)          //判断,条件成立之后交换位置
    			{
    				if(j==0)//***重点参考                //判断头结点是否会参与位置交换
    				{
    					head=p1;
    					p->pnext=p1->pnext;
    					p1->prev=p->prev;
    					p1->pnext=p;
    					p1->pnext->prev=p;
    					p->prev=p1;
    					
    					p1=p->pnext;
    				}
    				 ......//中间省略部分代码//......
    				else
    				{
    					//**交换位置代码**//
    					p->pnext=pn->pnext;
    					pn->prev=p->prev;
    					pn->pnext=p;
    					p->prev->pnext=pn;
    		//下一行请注意//	
    					pn->pnext->prev=p;
    					p->prev=pn;
    					//**位置交换结束**//
    					pn=p->pnext;         //位置交换结束之后进行指针偏移,pn指向p的下一个节点
    				}
    			else                                       //条件不成立
    			{
    				p=p->pnext;
    				pn=p->pnext;
    					//如果未发生位置交换,则两个指针都要发生偏移
    			}
    		}
    	}
    	return head;		
    }
    

    重点:
    在看上面的代码时我们需要与3.1节的内容对比来看,因为3.2节的中要单独考虑的情况有四种:

    • 头结点发生改变:
      重点要考虑头指针的的前向指针为NULL;
    • 尾结点发生改变:
      重点要考虑尾结点的的后向向指针为NULL;
    • 有且仅有两个结点(即头结点和尾结点):
      重点要考虑头指针的的前向指针为NULL且尾结点的的后向向指针为NULL;
    • 发生位置交换的结点不包含头结点和尾结点:
      这种情况下交换位置的6行代码都不能少;
    以上就是就是本次的所有内容,朋友如若发现问题,随时欢迎交流,希望能帮到你!!!
    展开全文
  • 双向链表排序,插入、删除

    千次阅读 2016-04-16 02:39:36
    双向链表排序,插入删除
  • 构建双向循环链表 利用快速排序法实现 链表排序 #include #include #define LEN sizeof(List) typedef struct ListNode { int num; int data; struct ListNode *pri; struct ListNode *next; }List; List *...
  • 双向链表的访问,双向链表排序 题目 已知不带头结点的双向链表第一个节点的指针为list,链节点除了数据域和分别指向该结点的前驱结点和后继结点的指针域外,还设置记录该节点访问次数频度域freq(初始值为0),请...
  • 排序树 变成双向链表

    2014-09-14 20:58:08
    排序树 变成双向链表排序
  • 主要介绍了C#双向链表LinkedList排序实现方法,涉及C#双向链表的定义与排序技巧,具有一定参考借鉴价值,需要的朋友可以参考下
  • 双向链表排序

    2020-03-03 20:35:49
    对于链表排序的关键在于要和数组的排序方法一一对应,由于链表并不知道有多少个节点,也即不知道要进行多少次循环,所以对于数组中的惯用for循环就不适用了,链表中需要用到的是while循环,而对于双向链表而言循环...
  • 双向链表

    2019-05-25 18:59:00
    /* 1:创建双向链表 2:遍历双向链表 3:双向链表长度获取 ... 7:双向链表排序 8:双向链表销毁 9:双向链表判空 */ #include<iostream> using namespace std; typedef struct node{ ...
  • 主要介绍了PHP基于双向链表排序操作实现的会员排名功能,结合实例形式分析了php双向链表的功能、定义及基于双向链表排序操作相关实现技巧,需要的朋友可以参考下
  • 设计算法,在带头结点的双向链表上,实现冒泡排序
  • * 把二元查找树转变成排序双向链表 - by Chimomo * * 【思路】按照二叉树的中序遍历正好是按从小到大地顺序遍历全部节点。在遍历的过程中,更改它的逻辑结构。 */ #include &lt;iostream&gt; ...
  • 基于双向链表的双向冒泡排序法 发布时间: 2018年11月26日 10:09 时间限制: 1000ms 内存限制: 128M 习题集源码中出现了temp->next->prior = p;本人推断这里缺少预先的对temp->next==NULL这种情况的判定,...
  • 双向链表的归并排序

    千次阅读 2016-04-17 19:59:25
    双向链表的归并排序双向链表的归并排序 方法一在Merge函数中使用数组 方法二改变指针指向归并排序分为两个部分: MergeSort 和 MergeMergeSort 是一个递归函数,在这个函数里面把待排序的数组或链表分段,直到每段的...
  • 双向链表(4) - 排序二叉树转换为循环双向链表
  • 基数排序(radix sort)又称桶排序(bucket sort),相对于常见的比较排序,基数排序是一种分配式排序,需要将关键字...为了尽可能少的消耗复制时占用的空间,桶的数据结构选择链表,为了构造队列,选择使用双向列表。
  • // 按排序插入节点 public void addByOrder(Node2 node) { // 头节点不能动,通过辅助指针来找到添加的位置 Node2 temp = head; boolean flag = false; // 标志添加的编号是否存在 while (true) { if ...
  • 295基于双向链表的双向冒泡排序法 描述 有n个记录存储在带头结点的双向链表中,利用双向冒泡排序法对其按上升序进行排序,请写出这种排序的算法。(注:双向冒泡排序即相邻两趟排序向相反方向冒泡)。 输入 多组...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 71,244
精华内容 28,497
关键字:

双向链表排序