精华内容
下载资源
问答
  • 利用了双向循环链表实现了快速排序算法
  • 双向循环链表排序

    千次阅读 2018-09-21 18:39:07
    //排序 void sort(dlist_t head) { dlist_t tmp = head->next,p = NULL,q = NULL; //将链表置空 head->next = head; head->prev = head; while(tmp!=head){ //保存原链表中tmp的下一个...
    //排序
    void sort(dlist_t head)
    {
        dlist_t tmp = head->next,p = NULL,q = NULL;
    
        //将链表置空
        head->next = head;
        head->prev = head;
    
        while(tmp!=head){
            //保存原链表中tmp的下一个节点
            q = tmp->next;
            
            //找到tmp插入的位置
            for(p=head->prev;p!=head&&p->data>tmp->data;p=p->prev);
            //将tmp插入到p之后
            tmp->prev = p;
            tmp->next = p->next;
            p->next->prev = tmp;
            p->next = tmp;
    
            //将tmp指向要插入的下一个节点
            tmp = q;
        }
        
    }

     

    展开全文
  • 二.双向循环链表 1.概念 双向循环链表的节点包含一个数据...双向循环链表的插入和删除操作比单向链表复杂,查找和修改和单向链表的算法一样 2.排序 对于链表的排序一般使用插入法排序 (1)取出一个元素,自然有序 ...

    二.双向循环链表

    1.概念

    双向循环链表的节点包含一个数据域,两个指针域,一个指针域指向上一个节点,另一个指针域指向下一个节点

    这样双向循环链表构成了两个相反方向遍历的圆环

    双向循环链表与单链表相比,提高了访问的效率,也付出了多维护一个指针的代价

    双向循环链表的插入和删除操作比单向链表复杂,查找和修改和单向链表的算法一样

    #include <stdio.h>
    #include <stdlib.h>
    #include “dlist.h”

    //创建空链表
    dlist_t create_emptydlist()
    {
    //构造头节点
    dlist_t head = (dlist_t)malloc(sizeof(dlist));
    if(head){
    head->data = -1;
    //头节点的前置和后置都指向自己表示空链表
    head->prev = head;
    head->next = head;
    }

    return head;
    

    }

    //按值删除,返回删除元素个数
    int delete_by_value(dlist_t head,T dt)
    {
    int i = 0;
    dlist_t tmp = NULL;

    while(tmp = search_by_value(head,dt)){
        //要删除节点的后一个节点的前置指针指向要删除节点的前一个节点
        tmp->next->prev = tmp->prev;
        //要删除节点的前一个节点的后置指针指向要删除节点的后一个节点
        tmp->prev->next = tmp->next;
        //释放要删除的节点
        free(tmp);
        tmp = NULL;
        i++;
    }
    
    return i;
    

    }

    //按值查找
    dlist_t search_by_value(dlist_t head,T dt)
    {
    //略过无效头节点
    dlist_t tmp = head->next;

    while(tmp!=head){
        if(tmp->data==dt)
            return tmp;
        tmp = tmp->next;
    }
    
    return NULL;
    

    }

    //按位置删除
    int delete_by_pos(dlist_t head,int pos)
    {
    //先查找链表,找到要删除的节点
    dlist_t tmp = search_by_pos(head,pos);

    //如果找到了就删掉,没找到就返回错误
    if(tmp){
        //要删除节点的后一个节点的前置指针指向要删除节点的前一个节点
        tmp->next->prev = tmp->prev;
        //要删除节点的前一个节点的后置指针指向要删除节点的后一个节点
        tmp->prev->next = tmp->next;
        //释放要删除的节点
        free(tmp);
        tmp = NULL;
    
        return 0;
    }
    
    //没有找到节点,返回-1
    return -1;
    

    }

    //按位置查找
    dlist_t search_by_pos(dlist_t head,int pos)
    {
    int i = 1;
    dlist_t tmp = head->next;

    //遍历到头节点为止
    while(tmp!=head){
        if(i==pos)
            return tmp;
        tmp = tmp->next;
        i++;
    }
    
    //回到头节点,谁没有符合编号的节点
    return NULL;
    

    }

    //从指定位置之后插入节点
    dlist_t insert(dlist_t p,T dt)
    {
    if(!p)
    return NULL;

    //构造新节点
    dlist_t newnode = (dlist_t)malloc(sizeof(dlist));
    if(newnode){
        newnode->data = dt;
        //将新节点的前置指向p,后置指向p的下一个节点
        newnode->prev = p;
        newnode->next = p->next;
        //将p的后置指向新节点,将P的下一个节点的前置指向新节点
        p->next->prev = newnode;
        p->next = newnode;
        
    }
    
    return newnode;
    

    }

    //排序
    void sort(dlist_t head)
    {
    dlist_t tmp = head->next,p = NULL,q = NULL;

    //将链表置空
    head->next = head;
    head->prev = head;
    
    while(tmp!=head){
        //保存原链表中tmp的下一个节点
        q = tmp->next;
        
        //找到tmp插入的位置
        for(p=head->prev;p!=head&&p->data>tmp->data;p=p->prev);
        //将tmp插入到p之后
        tmp->prev = p;
        tmp->next = p->next;
        p->next->prev = tmp;
        p->next = tmp;
    
        //将tmp指向要插入的下一个节点
        tmp = q;
    }
    

    }

    //销毁链表
    void destory_dlist(dlist_t *phead)
    {
    dlist_t head = (*phead)->next,p = NULL;

    while(head!=*phead){
        p = head;
        head = head->next;
        free(p);
    }
    free(head);
    
    *phead = NULL;
    p = NULL;   
    

    }

    //遍历
    void travel(dlist_t head)
    {
    //略过无效头节点
    dlist_t tmp = head->next;

    while(tmp!=head){
        printf("%d ",tmp->data);
        tmp = tmp->next;
    }
    printf("\n");
    

    }

    双向循环链表(https://download.csdn.net/download/qq_41256954/11079083)

    展开全文
  • C++双向循环链表实现基数排序算法

    千次阅读 2015-04-21 21:26:40
    文件: baseSort.h baseSort.cpp 命令: g++ baseSort.cpp -o baseSort /*baseSort.h*/ /* * the head file of baseSort * */ #include #include #include #include using namespace std;... s

    文件: baseSort.h  baseSort.cpp

    命令: g++ baseSort.cpp -o baseSort

    /*baseSort.h*/

    /*
     * the head file of baseSort
     * */
    #include<math.h>
    #include<stdio.h>
    #include<stdlib.h>
    #include<iostream>
    using namespace std;
    
    typedef struct node
    {
    	struct node *prior;
    	struct node *next;
    	long long key;
    }DNode;
    
    
    
    //function power:1000 == power(10,3);
    double power(int m,int n)
    {
    	if(n <= 0)
    	{
    		cout<<"paramater error!\n";
    		exit(0);
    	}
    	double tmp=1;
    	while(n > 0)
    	{
    		tmp =tmp * m;
    		n--;
    	}
    	return tmp;
    }
    
    
    template<class Type>
    void radix_sort(Type *L,int k)
    {
    	Type *Lhead[10],*p;
    	int i,j;
    	for(i=0;i<10;i++)
    		Lhead[i] = new Type;
    	for(i=0;i<k;i++)
    	{
    		for(j=0;j<10;j++)
    		{
    			Lhead[j]->prior = Lhead[j]->next = Lhead[j];
    		}
    			while(L->next != L)
    			{
    				p = del_entry(L);
    				j = get_digital(p,i);
    				add_entry(Lhead[j],p);
    			}
    			for(j=0;j<10;j++)
    				append(L,Lhead[j]);
    	}
    
    	for(i=0;i<10;i++)		
    		delete(Lhead[i]);
    }
    
    template<class Type>
    Type *del_entry(Type *L)
    {
    	Type *p;
    	p = L->next;
    	if(p != L)
    	{
    		p->prior->next = p->next;
    		p->next->prior = p->prior;
    	}
    	else
    		p = NULL;
    	return p;
    }
    
    
    template<class Type>
    void add_entry(Type *L, Type *p)
    {
    	p->prior = L->prior;
    	p->next = L;
    	L->prior->next = p;
    	L->prior = p;
    }
    
    template<class Type>
    int get_digital(Type *p,int i)
    {
    	long long key;
    	key = p->key;
    	if(i != 0)
    		key = key / power(10,i);
    	return key % 10;
    }
    
    
    template<class Type>
    void append(Type *L,Type *L1)
    {
    	if(L1->next != L1)
    	{
    		L->prior->next = L1->next;
    		L1->next->prior = L->prior;
    		L1->prior->next =L;
    		L->prior = L1->prior;
    	}
    }
    
    
    void Create_DLink(DNode * &head)
    {
    	int x;
    	DNode *p,*s;
    	s = (DNode *)malloc(sizeof(DNode));
    	if(s == NULL)
    		cout<<"failed to malloc memory for DNode\n";
    	s->key =0;
    	s->prior = s;
    	s->next = s;
    	head = s;
    	cout<< "please input the data of the node"<<endl;
    	cin>>x;
    	while(x != 0)
    	{
    		p = (DNode *)malloc(sizeof(DNode));
    		if(p == NULL)
    		{
    			cout<<"failed to malloc memory!"<<endl;
    			exit(0);
    		}
    
    		p->key = x;
    		head->prior->next = p;
    		p->prior = head->prior;
    		p->next = head;
    		head->prior = p;
    
    		cin>>x;
    	}
    }
    
    
    void PrintLink(DNode *head)
    {
    	if(head->next== NULL)
    	{
    		cout<<"The list is NULL"<<endl;
    		return ;
    
    	}
    	DNode *p;
    	p = head->next;
    	while(p!=head)
    	{
    		cout<<p->key<<" ";
    		p = p->next;
    	}
    	cout<<endl;
    }
    


    /* baseSort.cpp* /

    #include "baseSort.h"
    
    int main(void)
    {
     DNode *L;
    
     int number = 0;
    
      Create_DLink(L);
    
     PrintLink(L);
     
     cout<<"please input base number:";
     cin>>number;
     radix_sort(L,number);
     cout<<"after the radix_sort:\n";
    
     PrintLink(L);
     return 0;
    }
    


    展开全文
  • 今天分别对单链表和双向链表添加循环,使之分别成为循环单链表、循环双向链表。 本次实现,均使用了哨兵结点,也即在创建链表之前的初始化部分,已经自动创建了一个内容为None的节点,这样做的目的是为了在后续插入...

     单链表以及双向链表的实现可参考之前文章:

    数据结构与算法(二):Python 单向链表及其排序

    数据结构与算法(三):Python实现双向链表并遍历

    今天分别对单链表和双向链表添加循环,使之分别成为循环单链表循环双向链表

    本次实现,均使用了哨兵结点,也即在创建链表之前的初始化部分,已经自动创建了一个内容为None的节点,这样做的目的是为了在后续插入其他结点时,可以不用考虑原链表为空的边界条件。 

    废话少说,直接上码:

    一、循环单链表

    class Node(object):
        def __init__(self, data, next=None):
            self.data = data
            self.next = next
    
    class CircleSinglyLinkedList(object):
        def __init__(self):
            """
            初始化循环单链表时,创建了一个哨兵结点,使得后续插入结点不用考虑边界
            """
            self.headNode = Node(None)
            self.headNode.next = self.headNode
            self.length = 0
        
        def crt_from_list(self, L):
            """
            尾插法:每次在尾部插入一个结点
            """
            h = self.headNode
            for l in L:
                h.next = Node(l, next=self.headNode)
                h = h.next
                self.length += 1
            
                
        def lineprint(self):
            if self.headNode == self.headNode.next:
                print("NULL")
                return
            p = self.headNode.next
            print(p.data)
            while p.next != self.headNode:
                print(p.next.data)
                p = p.next
    
    if __name__ == "__main__":
        cll = CircleSinglyLinkedList()
        cll.crt_from_list([0,'a',2])
        print('循环单链表遍历:')
        cll.lineprint()

    二、循环双向链表

    class BiNode(object):
        """双向链表的node类
        """
        def __init__(self, data, next=None, previous=None):
            self.data = data
            self.next = next
            self.previous = previous
    
    class CircleBiLinkedList(object):
        def __init__(self):
            """
            初始化时,创建一个哨兵结点
            """
            self.headNode = BiNode(None)
            self.headNode.next = self.headNode
            self.headNode.previous = self.headNode
            self.length = 0
        def crtFromList(self, L):
            """从一个列表L创建一个循环双向链表
            """
            h = self.headNode
            for l in L:
                h.next = BiNode(l, next=self.headNode, previous=h)
                self.headNode.previous = h.next
                h = h.next
        
        def cbprint(self, mode = 'forward'):
            """循环双向遍历链表
            mode:遍历方式,包括从前往后('forward'/0)、从后往前('backward'/1)
            """
            if mode == 'forward' or mode == 0:
                p = self.headNode.next
                while p != self.headNode:
                    print(p.data)
                    p = p.next
            elif mode == 'backward' or mode == 1:
                p = self.headNode.previous
                while p != self.headNode:
                    print(p.data)
                    p = p.previous
    
    if __name__ == "__main__":
        print("循环双向链表遍历:")
        cb = CircleBiLinkedList()
        print("从前往后:")
        cb.crtFromList(['a','b','c'])
        cb.cbprint(mode='forward')  
        print("从后往前:")
        cb.cbprint(mode='backward')  

     

    展开全文
  • 双向循环链表的冒泡排序

    千次阅读 2017-11-28 21:15:58
    以内核链表为例,进行冒泡排序
  • 双向循环链表的插入排序

    千次阅读 2017-11-30 21:55:53
    前两篇博文,我讨论了链表的冒泡排序和选择排序(以Linux内核链表为例),这篇文章,我想说说插入排序
  • 双向循环链表的选择排序

    千次阅读 2017-11-30 20:55:45
    以Linux内核链表为例,进行选择排序
  • 双向循环链表

    2015-09-04 21:23:41
    实现双向循环链表,包括创建,插入,删除,查找,求长度,按内容排序,销毁所有记录等功能
  • 双向循环链表的频度自学习算法

    千次阅读 2018-02-09 11:36:41
    设有一个双向循环链表,每个结点中除有prior,data,next三个域以外,还增设了一个访问频度域freq。在链表被启用之前,freq域的值均被初始化为零,而每当对链表进行一次Locate(L,x)的操作之后,被访问的结点(即...
  • 带头结点的双向循环链表

    千次阅读 2020-08-07 11:44:14
    1.双向循环链表的节点中有一个数据域,两个指针域,其一指向直接后继,另一指向直接前驱。 2.带头节点的双向循环链表如图所示: 3.删除节点时的指针变化 4.插入一个节点时的指针变化 #ifndef _DCLIST_H_ #define...
  • C语言双向循环链表

    2021-08-07 20:03:39
    在C语言中,链表分为单向链表双向链表,单向链表只能朝一个方向遍历,中间的一个节点只能由上一个节点推出,只能往前推,无法往后推,关于单向链表的介绍可以点击单向链表介绍。 这次介绍双向链表,既然叫双向就...
  • 解剖双向循环链表!!!
  • 若是不清楚链表的结构,该篇文章不适合观看,这里只做文字说明,没有链表结构的图示
  • 算法与数据结构之双向循环链表
  • 这一篇主要讲述双向链表和双向循环链表。 双向链表: 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地...
  • 双向循环链表的实现

    2017-03-22 16:59:40
    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有...一般我们都构造双向循环链表。 #include using namespace std; // 数据类型结构体 typedef int ElemType; // 双向循环链表结构体 type
  • 双向循环链表list

    2014-09-29 10:57:22
    双向循环链表list  list是双向循环链表,,每一个元素都知道前面一个元素和后面一个元素。在STL中,list和vector一样,是两个常被使用的容器。和vector不一样的是,list不支持对元素的任意存取。list中提供的...
  • 双向动态链表才是关键,直接看例子和图示既就可以,主要是自己会画图,然后根据图来写代码 dlist.h //头文件 #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; typedef struct _node {  int ...
  • 循环链表增删改查等多功能实现及相关面试题(下)链表双向循环链表的实现链表面试题(下)1. 合并两个有序链表2.链表分割3.环形链表4.环形链表25.复制带随机指针的链表6.对链表进行插入排序7.删除链表中重复的结点8....
  • 设有一个双向循环链表,每个结点中除有prior, data和next三个域外,还增设了一个访问频度域freq。在链表启用之前,频度域freq的值均初始化为零,而每当对链表进行一次locate(L,x)的操作后,被访问的结点(即元素值...
  • 【问题描述】输入n个整数,创建一个双向循环链表进行存储。这些整数从第二个开始,递增有序(设a2<a3<...<an) (ai为第i个整数)。试编写程序,创建双向循环链表,依次将输入的整数存储在该链表的各节点中。...
  • 双向循环链表>0前移,<0 后移 题目 已知带头几点的双向循环链表头结点为list,除头结点外每个结点的数据域为整型,请写一算法,将链表中所有数据域大于0的结点放在小于0的前面。若链表中除头结点以外其他的为...
  • 之前也写过一篇C语言实现简单的双向循环链表,现在使用C++再来扩展一下内容。除了节点的插入、删除,还增加了一些链表的其他操作,包括节点修改、节点替换、节点查找、值查找、值排序等等。内容还是挺丰富的,废话不...
  • 基于双向循环链表实现的学生管理系统,包括初始化,插入,删除,查抄,保存,自动按照姓名排序功能,退出并保存功能。
  • 双向循环链表库函数可以直接使用,只需要根据库函数的头文件中的链表类型和节点类型来创建数据就可以。分为 DoubleList.h 和 DoubleList.c 两个文件。需要把两个文件放到同一目录下编译。 DoubleList.h ...
  • 表的介绍都在前面单向循环链表的基础上展开 基本构造(特点): ...// 将此链表设置为双向循环链表 if(head->nodeNumber != 0) { head->last->next = head->first; head->first->prev = ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 29,998
精华内容 11,999
关键字:

双向循环链表排序算法