精华内容
下载资源
问答
  • 使用双向链表实现快速排序C语言,有详细注释
  • //保存P的前一个节点,在P=NULL的时候,P的前一个节点就代表是这个链表的最大值,如果data还大于目前最大值,则把data的节点设置为最大值 while (p!=NULL&&data > p->data) { pPrev = p; p = p->next; } ...
    #include<stdio.h>
    #include<stdlib.h>
    
    typedef struct Node* NodePtr;
    
    typedef struct Node
    {
    	int data;
    	NodePtr prev;
    	NodePtr next;
    } Node;
    
    void putPrev(int data, NodePtr head) {
    	NodePtr node = (NodePtr)malloc(sizeof(Node));
    	if (node==NULL)
    	{
    		printf("node==NUll");
    		return;
    	}
    	node->data = data;
    	node->next = NULL;
    	node->prev = NULL;
    	NodePtr p = head;
    	while (p->prev!=NULL)
    	{
    		p = p->prev;
    	}
    	node->next = p;
    	p->prev = node;
    }
    
    void putNext(int data, NodePtr head) {
    	NodePtr node = (NodePtr)malloc(sizeof(Node));
    	if (node == NULL)
    	{
    		printf("node==NUll");
    		return;
    	}
    	node->data = data;
    	node->next = NULL;
    	node->prev = NULL;
    	NodePtr p = head;
    	while (p->next != NULL)
    	{
    		p = p->next;
    	}
    	node->prev = p;
    	p->next = node;
    }
    
    //插入并排序
    void putBySort(int data, NodePtr head) {
    
    	NodePtr node = (NodePtr)malloc(sizeof(Node));
    	if (node == NULL)
    	{
    		printf("node==NUll");
    		return;
    	}
    	node->data = data;
    	node->next = NULL;
    	node->prev = NULL;
    	NodePtr p = head;
    	if (data>p->data)
    	{
    		NodePtr pPrev = p;//保存P的前一个节点,在P=NULL的时候,P的前一个节点就代表是这个链表的最大值,如果data还大于目前最大值,则把data的节点设置为最大值
    		while (p!=NULL&&data > p->data) {
    			pPrev = p;
    			p = p->next;
    		}
    		if (p == NULL)
    		{
    			pPrev->next = node;
    			node->prev = pPrev;
    		}
    		else {
    			pPrev->next = node;
    			node->prev = pPrev;
    			node->next = p;
    			p->prev = node;
    		}
    		
    	}
    	else {
    		NodePtr pNext = p;//保存P的后一个节点,在P=NULL的时候,P的后一个节点就代表是这个链表的最小值,如果data还小于目前最小值,则把data的节点设置为最大值
    		while (p != NULL&&data < p->data) {
    			pNext = p;
    			p = p->prev;
    		}
    		if (p == NULL)
    		{
    			pNext->prev = node;
    			node->next = pNext;
    		}
    		else {
    			pNext->prev = node;
    			node->next = pNext;
    			node->prev = p;
    			p->next = node;
    		}
    	}
    }
    
    //冒泡排序
    void sort(NodePtr head) {
    
    	NodePtr p = head;
    	NodePtr pNext = p->next;
    
    	if (pNext == NULL)//只有一个参数
    	{
    		return;
    	}
    	if (pNext->next ==NULL && p->data > pNext->data)//只有两个参数
    	{
    		p->next = NULL;
    		p->prev = pNext;
    		pNext->next = p;
    		pNext->prev = NULL;
    		return;
    	}
    	NodePtr q;
    	int tmp;
    	for (; p->next!=NULL; p=p->next)
    	{
    		for (q=p->next; q!=NULL; q = q->next)
    		{
    			if (q->data < p->data)
    			{
    				tmp = q->data;
    				q->data = p->data;
    				p->data = tmp;
    			}
    		}
    	}
    }
    
    
    //查
    NodePtr getNode(int position, NodePtr head) {
    	NodePtr p = head;
    	int i = 0;
    	for (; p != NULL; p = p->next) {
    		i++;
    		if (i == position)
    		{
    			break;
    		}
    	}
    	return p;
    }
    
    //增
    void insertNode(int data, int position,NodePtr head) {
    	
    	NodePtr node = (NodePtr)malloc(sizeof(Node));
    	node->data = data;
    	node->next = NULL;
    	node->prev = NULL;
    
    	NodePtr p = getNode(position, head);
    	NodePtr pNext = p->next;
    	NodePtr pPrev = p->prev;
    	pPrev->next = node;
    	node->prev = pPrev;
    	node->next = p;
    	p->prev = node;
    }
    
    //删除节点
    void deleteNode(int position, NodePtr head) {
    	NodePtr p = getNode(position, head);
    	NodePtr pNext = p->next;
    	NodePtr pPrev = p->prev;
    	pPrev->next = pNext;
    	pNext->prev = pPrev;
    	p->next = NULL;
    	p->prev = NULL;
    	p->data = 0;
    }
    
    //改
    void modifyNode(int data,int position, NodePtr head) {
    	NodePtr p = getNode(position, head);
    	p->data = data;
    }
    
    //打印链表
    void printNode(NodePtr list) {
    	//找到最前面的节点
    	NodePtr nodePrev = list;
    	while (nodePrev->prev != NULL)
    	{
    		nodePrev = nodePrev->prev;
    	}
    	NodePtr node = nodePrev;
    	while (node != NULL)
    	{
    		printf("%d ", node->data);
    		node = node->next;
    		if (node!=NULL)
    		{
    			printf(",");
    		}
    	}
    	printf("\n");
    }
    
    void main() {
    
    	int i = 0;
    	NodePtr list= (NodePtr)malloc(sizeof(Node));
    	list->data = 10;
    	list->next = NULL;
    	list->prev = NULL;
    
    	int intArr[] = {5,1,20,15,22,11,19,50,18,40,45,30,65};
    	int length = sizeof(intArr) / sizeof(intArr[0]);
    
    	//插入的时候排序
    	/*for (i = 0; i < length; i++)
    	{
    		putBySort(intArr[i], list);
    	}*/
    
    	//插入数据
    	for (i = 0; i < length; i++)
    	{
    		putNext(intArr[i], list);
    	}
    
    	//首次插入数据后
    	printf("首次插入数据后:\n");
    	printNode(list);
    
    	//增
    	int position = 5;
    	int addNum = 6;
    	insertNode(addNum, position, list);
    	//添加数字后
    	printf("在第%d位插入数据%d后:\n",position,addNum);
    	printNode(list);
    
    	//删
    	position = 10;
    	deleteNode(position, list);
    	printf("删除第%d位数据后:\n", position);
    	printNode(list);
    
    	//改
    	position = 4;
    	int modifyNum = 12;
    	modifyNode(modifyNum, position, list);
    	printf("将第%d位数据改为%d后:\n", position,modifyNum);
    	printNode(list);
    
    	//查
    	position = 9;
    	NodePtr p = getNode(position,list);
    	printf("第%d位数据为%d。\n", position, p->data);
    
    	//冒泡排序
    	sort(list);
    	printf("冒泡排序后:\n");
    	printNode(list);
    
    	system("pause");
    }


    展开全文
  • 双向链表C语言实现

    2018-12-13 13:36:34
    通过双向链表实现按照ID序列插入,可以排序实现插入、删除、更新、修改;
  • 数据结构之C语言实现双向链表

    千次阅读 多人点赞 2018-07-07 12:17:29
    C语言实现双向链表 双向链表主要实现以下功能: 双向链表创建 节点头插 节点尾插 指定位置插入节点 节点删除 链表排序 链表求长 /********************************************************************...

    C语言实现双向链表

    双向链表主要实现以下功能:

    • 双向链表创建
    • 节点头插
    • 节点尾插
    • 指定位置插入节点
    • 节点删除
    • 链表排序
    • 链表求长
    /****************************************************************************************************** 
     *   function:自定义一个双向链表,并完成一些双向链表的操作:创建链表、数据插入、数据删除、链表排序 
     *   author:yahai.zhang 
     *   time: 2018.7.15
     *   File Name:DList.c
     ******************************************************************************************************/ 
    
    #include <stdio.h>
    
     /* 定义数据结构 */
    struct DouLinkNode {
        int data ;               //链表中存放的数据,可以自定义数据结构 
        struct DouLinkNode *pre ,*next;
    };
    
    /* 双向链表创建 */ 
    struct DouLinkNode *create(int n)
    {   
        int x;
        struct DouLinkNode *head = (struct DouLinkNode *)malloc(sizeof(struct DouLinkNode));
        struct DouLinkNode *p,*s;
        p = head;
        p->pre = NULL;
        while(n) {
            s = (struct DouLinkNode*)malloc(sizeof(struct DouLinkNode));
            printf("input data of the node:data=");
            scanf("%d",&x);
            s->data = x;
            p->next = s;
            s->pre = p;
            p = s;
            n--;
        }
        s->next = NULL;
        return head;
    }
    
     /* 双向链表打印 */
    void display(struct DouLinkNode *head)
    {
        struct DouLinkNode *p = head->next;
        while(p->next) {
            printf("%d <---> ",p->data);
            p = p->next;
        }
        printf("%d \n",p->data);
    }
    
    /* 链表头插节点 */
    void insertListHead(struct DouLinkNode *pList, int data)
    {
        struct DouLinkNode *pNode = (struct DouLinkNode *)malloc(sizeof(struct DouLinkNode));
        pNode->data = data;
        pNode->next = pList->next;
        pNode->pre = pList;
        if (NULL != pNode->next) {
            pNode->next->pre = pNode;
        }
        pList->next = pNode;
    }
    
    /* 链表尾插节点 */ 
    void insertListTail(struct DouLinkNode *pList, int data)
    {
        struct DouLinkNode *pNode = (struct DouLinkNode *)malloc(sizeof(struct DouLinkNode));
        pNode->data = data;
        struct DouLinkNode *pCur = pList; 
        while(NULL != pCur->next) {
            pCur = pCur->next;
        }
        pCur->next = pNode;
        pNode->pre = pCur;
        pNode->next = NULL;
    }
    
    /* 在链表的指定位置插入节点: index = 0 ---> 头插; index = length ---> 尾插 */
    int insertList(struct DouLinkNode *pList, int data, int index)
    {
        struct DouLinkNode *pCur = pList; 
        int len =  get_List_Length(pCur);
        if(index > len) {
            return -1;
        } else if (index == 0) {
            insertListHead(pList, data);
            return 0;
        } else if(index == len) {
            insertListTail(pList, data);
            return 0;
        }
    
        struct DouLinkNode *pNode = (struct DouLinkNode *)malloc(sizeof(struct DouLinkNode));
        pNode->data = data;
        pCur = pList;
        int i = 0;
        while( index--) {
            pCur = pCur->next;
        }
        pNode->next = pCur->next;
        pCur->next = pNode;
        pNode->pre = pCur;
        pNode->next->pre = pNode;   
    }
    
    /* 删除链表中的指定值 */
    int deleteListNode(struct DouLinkNode *pList, int key)
    {
        struct DouLinkNode *pPre = pList;
        struct DouLinkNode *pCur = pList->next;
        int count = 0; //记录删除节点个数 
        while(NULL!=pCur) {
            if(pCur->data == key) {
                if(NULL != pCur->next) {
                    pCur->next->pre = pCur->pre;
                }
                pCur->pre->next = pCur->next;
                pPre = pCur; 
                pCur = pCur->next;
                free(pPre);
                count ++;
            } else {
                pPre = pCur;
                pCur = pCur->next;
            }
        }
        return count; 
    }
    
    /* 链表求长 */
    int get_List_Length(struct DouLinkNode *head)
    {
        struct DouLinkNode *p;
        int len = 0;
        p = head;
        for (p; p->next!=NULL; p=p->next) {
            len++;
        }
        return len;
    }
    
    /* 双向链表排序 */
    struct DouLinkNode *sort(struct DouLinkNode *head)
    {
        struct DouLinkNode *p,*s,*min;
        int tmp;
    
        for(p = head->next ;p->next!=NULL ;p=p->next) {
            min = p ;
            for(s= p->next ; s!=NULL ;s=s->next) {
                if(s->data <min->data)
                    min = s;               //找到每次排序中最小的节点,然后记住这个节点
            } if(min != p) {               //把这个节点与前面的节点的数据进行交换,把最小的数据放在前面的节点内。
                tmp = min->data;
                min->data = p->data;
                p->data = tmp;
            }
        }
        return head;
    }
    
    int main()
    {
        struct DouLinkNode  *head,*head1;
        int n;
        int data;
        printf("input n:");
        scanf("%d",&n);
        head = create(n);
        display(head);
        printf("insert node from head: data=");
        scanf("%d", &data);
        insertListHead(head, data);
        display(head);
        printf("insert node from tail: data=");
        scanf("%d", &data);
        insertListTail(head, data);
        display(head);
        printf("insert the data(100) into the list:\n");
        insertList(head, 100, 4);
        display(head);
        printf("please input the data you want to delete: data=");
        scanf("%d", &data);
        int k = deleteListNode(head, data);
        printf("success! delete nodes:%d\n", k);
        display(head);
        printf("the list length:%d\n", get_List_Length(head));
        printf("sort the list:\n");
        head1 = sort(head);
        display(head1);
    
        return 0;
    }
    

    运行结果如下所示:

    实验目标

    图1 运行结果

    展开全文
  • 双向链表的几种插入,删除,指定位置输出 双向链表的长相 双向链表由前驱指针和后项指针还有数据域组成,把节点之间的前后指针相连接形成链表 双向链表节点的封装 双向链表与单链表相比,仅多了一个前驱指针 ...

    双向链表的几种插入,删除,指定位置输出

    双向链表的长相

     双向链表由前驱指针和后项指针还有数据域组成,把节点之间的前后指针相连接形成链表

    双向链表节点的封装

    双向链表与单链表相比,仅多了一个前驱指针

    typedef struct Node {
        int data;//内容
        struct Node* frontNode;//前驱指针
        struct Node* nextNode;//后项指针
    }*LPNODE;

    双向链表的特点在于可以从左到右,也可以从右到左输出链表,因此需要一个头节点和尾节点分别指向链表的头和尾,实现链表的顺序或逆序打印

    封装链表

    typedef struct List {
        struct Node* HeadNode;//头节点
        struct Node* TailNode;//尾节点
        int curSize;//万金油参数
    }*LPLIST;

    万金油参数负责记录节点个数,方便后续条件判断

    创建头节点和尾节点

    这里主要是起到了封装头节点和尾节点的作用,函数初始化节点,返回相应节点

    LPNODE CreateHeadNode() {
        LPNODE headNode = (LPNODE)malloc(sizeof(Node));//动态申请一个节点大小的内存
        assert(headNode);//判空
        headNode->frontNode = NULL;
        headNode->nextNode = NULL;
        return headNode;
    }
    LPNODE CreateTailNode() {
        LPNODE tailNode = (LPNODE)malloc(sizeof(Node));
        assert(tailNode);
        tailNode->frontNode = NULL;
        tailNode->nextNode = NULL;
        return tailNode;
    }

    判空是因为内存可能会申请失败,返回NULL。该函数是为了避免因赋值到空指针而影响到后续指针的操作。

    创建新节点

    LPNODE CreateNode(int data) {
        LPNODE newNode = (LPNODE)malloc(sizeof(Node));
        assert(newNode);
        newNode->data = data;//和头节点,尾节点不同,所要插入的节点是要初始化data的
        newNode->frontNode = NULL;
        newNode->nextNode = NULL;
        return newNode;
    }

    创建的newNode目的是方便后续新节点的创建

    创建链表,初始化数据

    LPLIST CreateList() {
        LPLIST list = (LPLIST)malloc(sizeof(List));//申请一个List大小的内存
        assert(list);//判空
        list->curSize = 0;//当前节点为0
        list->HeadNode = CreateHeadNode();//初始化头节点
        list->TailNode =CreateTailNode();//初始化尾节点
        return list;
    }

    头插法

    这里的要点就是,当节点为0时,头节点的下一个节点是NULL,如果要按再次插入的话,必须要求头节点的下一个节点的前驱指针指向新节点,这里会因为该节点是NULL而不能人为操作空指针而引发中断

    尾节点指向最后的节点,因为头插法是一直往中间插的,尾节点在末尾的位置一直没有发生改变

     代码如下:

    void insertByHead(LPLIST list, int data) {
        LPNODE newNode = CreateNode(data);
        if(list->curSize==0)//当没有节点时
            list->TailNode = newNode;//为节点指向新节点
        else {
            newNode->nextNode = list->HeadNode->nextNode;//新节点的后项指针指向头节点的下一个
            list->HeadNode->nextNode->frontNode = newNode;//新节点的前驱指针指向新节点
        }
        list->HeadNode->nextNode = newNode;//头节点的后项指针指向新节点
        newNode->frontNode = list->HeadNode;//新节点的前驱指针指向头节点
        list->curSize++;//每插入一个,增加一个节点数目
    }

    尾插法

    尾插法的要点和头插法类似,也是因为当节点为0时,后项指针会为空

    此外,每插入的新节点就是尾节点,尾节点的指向要改变

    代码如下: 

    void insertByTail(LPLIST list, int data) {
        LPNODE newNode = CreateNode(data);
        if (list->curSize == 0)//节点为空时
            list->HeadNode =newNode;
        else {
            list->TailNode->nextNode = newNode;//直接插在后面
            newNode->frontNode = list->TailNode;
        }
        list->TailNode = newNode;//改变尾节点
        list->curSize++;
    }

    指定位置插入

    思路:准备一个指针在前,一个指针在后,两个指针齐头并进,当后面的指针指向指定位置时,把数据插入到两个指针中间

    这里的要点是如果没有找到指定数据,要把数据插入到链表后面,同时尾节点发生改变

    代码如下:

    void insertByAppoint(LPLIST list, int data, int posData) {
        LPNODE LeftNode = list->HeadNode->nextNode;//左指针
        LPNODE curNode = list->HeadNode->nextNode;//当前指针
        while (curNode != NULL && curNode->data != posData) {//没有找到就一直找,找到CurNode为空
            LeftNode = curNode;//移动左指针
            curNode = curNode->nextNode;//移动当前指针
        }
        LPNODE newNode = CreateNode(data);//创建新节点
        //后面就是插入中间的操作
        LeftNode->nextNode = newNode;
        newNode->frontNode = LeftNode;
        if (curNode == NULL)//尾节点改变
            list->TailNode = newNode;
        if (curNode != NULL) {
            newNode->nextNode = curNode;
            curNode->frontNode = newNode;
        }
        list->curSize++;//节点个数增加
    }

    节点删除

    这里的思路和上面类似,准备两个指针,一个在前,一个在后,齐头并进。当找到需要删除的节点的位置停止移动,把后面指针的下一个节点和前指针指向的节点连接起来,最后释放后指针所指向节点的内存

    代码如下:

    void DeleteByAppoint(LPLIST list, int posData) {
        LPNODE frontNode = list->HeadNode;//前指针
        LPNODE curNode = list->HeadNode;//当前指针
        while (curNode != NULL && curNode->data != posData) {
            frontNode = curNode;
            curNode = curNode->nextNode;
        }
        if (curNode == NULL)//如果找不到就返回
            return;
        //连接curNode前后位置的节点
        frontNode->nextNode = curNode->nextNode;
        curNode->nextNode->frontNode = frontNode;
        free(curNode);//释放内存
        curNode = NULL;
        list->curSize--;//删除一个,节点少一个
    }

    链表的有序插入

    准备一堆乱序的数据,通过有序插入,可以返还有序的链表

    思路:按顺序一个个插入,当找到下一个节点的数值比所要插入节点中的数值大或者小时,插入该节点前面,形成从小到大或者从大到小的排序,没有找到就插在后面

    要点:

    1.如果要插入到最后面,就不需要把后项指针的前驱指针指向前面的节点,因为误操作空指针会引发程序中断

    2.新节点当插入到最后的位置时,尾节点要发生改变

    代码如下:

    void insertBySqList(LPLIST list, int Mydata) {
        LPNODE frontNode = list->HeadNode;//前指针
        LPNODE PosNode = list->HeadNode->nextNode;//指定位置指针
        while (PosNode != NULL && PosNode->data < Mydata) {
            frontNode = PosNode;//移动
            PosNode = PosNode->nextNode;//移动
        }
        LPNODE newNode = CreateNode(Mydata);//新节点创建
        frontNode->nextNode = newNode;
        newNode->frontNode = frontNode;
        if (PosNode == NULL)//改变尾节点
            list->TailNode = newNode;
        if (PosNode != NULL) {
            PosNode->frontNode = newNode;
            newNode->nextNode = PosNode;
        }
        list->curSize++;
    }

    打印链表

    可以从头到尾打印,也可以从尾到头打印

    1.从头到尾

    void printListByHead(LPLIST list) {
        printf("头输出:\t");
        LPNODE pMove = list->HeadNode->nextNode;
        while (pMove) {
            printf("%d\t", pMove->data);
            pMove = pMove->nextNode;
        }
        printf("\n");
    }

    2.从尾到头

    void printListByTail(LPLIST list) {
        printf("尾输出:\t");
        LPNODE pMove = list->TailNode;
        while (pMove!=list->HeadNode) {
            printf("%d\t", pMove->data);
            pMove = pMove->frontNode;
        }
        printf("\n");
    }

    测试代码:

    为了控制台输出数据的美观,我增加了一些换行符和文字修饰

    代码如下:

    int main() {
        LPLIST list = CreateList();
        printf("\n尾插法\n");
        for (int i = 0; i < 5; i++)
            insertByTail(list, i);
        printListByHead(list);
        printListByTail(list);
        printf("删除指定数据的");
        DeleteByAppoint(list, 3);
        printListByHead(list);
        LPLIST list2 = CreateList();
        printf("\n头插法\n");
        for (int i = 0; i < 5; i++)
            insertByHead(list2, i);
        printListByHead(list2);
        printListByTail(list2);
        printf("删除指定数据的");
        DeleteByAppoint(list2, 2);
        printListByTail(list2);
        printf("插入指定数据的");
        insertByAppoint(list2, 100, 2);
        printListByTail(list2);
        printf("插入指定数据的");
        printListByHead(list2);
        LPLIST list3 = CreateList();
        int array[] = { 3,5,9,7,2,6 };
        printf("有序链表构建的");
        for(int i=0;i<6;i++)
        insertBySqList(list3, array[i]);
        printListByTail(list3);
        printf("有序链表构建的");
        printListByHead(list3);
        return 0;
    }

    运行效果如下:

     

    展开全文
  • 实现双向链表中删除一个指定元素。  4.在非递减有序双向链表实现插入元素e仍有序算法。  5.判断双向链表中元素是否对称若对称返回1否则返回0。  6.设元素为正整型,实现算法把所有奇数排列在偶数之前。  ...
  • 利用了双向循环链表实现了快速排序算法
  • 之前一直想用双向链表来快排,想像数组快排一样给第一个数组下标(第一个有值节点的指针)和最后一个数组下标(最后一个有值节点指针),结果运行时经常有问题,程序有时会出错,于是纸上演算了几次发现会访问到未知的内存. ...

    之前一直想用双向链表来快排,想像数组快排一样给第一个数组下标(第一个有值节点的指针)和最后一个数组下标(最后一个有值节点指针),结果运行时经常有问题,程序有时会出错,于是纸上演算了几次发现会访问到未知的内存.

    因为当low和high在最左侧或者最右侧相同时,再经过一次调用时

    Box_Qsort(i,low->prev); 
    Box_Qsort(low->next,j);
    

    可以发现因为最后一个有值节点的next为NULL,当此时low为NULL,

    Box *key = (Box *)malloc(sizeof(Box));//保存节点数据 
    key->num = low->num;
    

    low->num不存在,所以会导致程序异常.
    而这样解决方法我认为就是给最后一个节点再连接一个节点,这样就没有问题了,一切正常
    不过要注意在展示链表时不要展示了多加的那个节点

    傻了,直接前面加一个判断就行了…

    void Box_Print(Box *box_head)//显示双向链表内容 
    {
    	Box *p = box_head->next;
    	while(p)
    	{
    		printf("%d ",p->num);
    		p=p->next;
    	}
    	printf("\n");
    }
    

    以下是完整代码的展示:

    #include<stdio.h>
    #include<stdlib.h> 
    typedef struct _Box //结构体 
    {
    	struct _Box *prev;
    	int num;
    	struct _Box *next;
    } Box;
    Box *Box_Creathead()//创建一个头节点 
    {
    	Box *p = (Box*)malloc(sizeof(Box));
    	p->prev = NULL;
    	p->next = NULL;
    	return p;
    }
    void Box_Add(Box *box_head)//头插法创建双向链表 
    {
    	int num;
    	while(scanf("%d",&num)==1)
    	{
    		Box *p = (Box*)malloc(sizeof(Box));
    		p->num = num;
    		p->next = box_head->next;
    		p->prev = box_head;
    		if(box_head->next)
    		{
    			box_head->next->prev = p;
    		}
    		box_head->next = p;
    	}
    	
    }
    void Box_Qsort(Box *low,Box *high)//快排核心内容 
    {
    	Box *i = low;
    	Box *j = high;
    	Box *key = (Box *)malloc(sizeof(Box));//保存节点数据 
    	if(low == NULL)
    	{
    		return;
    	}
    	key->num = low->num;
    	if(low==high||low->prev==high)
    	{
    		return;
    	}
    	while(low!=high&&low->prev!=high)
    	{
    		for(;low!=high&&low->prev!=high&&key->num<=high->num;high=high->prev);
    		if(key->num>high->num)
    		{
    			low->num = high->num;
    		}
    		for(;low!=high&&low->prev!=high&&key->num>=low->num;low=low->next);
    		if(key->num<low->num)
    		{
    			high->num = low->num;
    		}
    	}
    	low->num = key->num;
    	Box_Qsort(i,low->prev);//这里因为有了头节点所以不用考虑 
    	Box_Qsort(low->next,j);//如果不给最后一个有值的节点接一个节点,就会访问到不确定的内存 
    }
    void Box_Print(Box *box_head)//显示双向链表内容 
    {
    	Box *p = box_head->next;
    	while(p->next)
    	{
    		printf("%d ",p->num);
    		p=p->next;
    	}
    	printf("\n");
    }
    Box* Box_FindBase(Box *box_head)//找到链表最后一个节点
    {
        Box* p = box_head->next;
        if(!p)
        {
        	return box_head;
    	}
    	while(p->next)
    	{
    		p=p->next;
    	}
    	return p;
    }
    //没用..
    void Box_CreatBase(Box *high)//为最后一个节点接一个空的节点 
    {
    	Box *p = (Box*)malloc(sizeof(Box));
    	p->next = NULL;
    	p->prev = high;
    	high->next = p;
    }
    int main()
    {
    	Box *box_head = Box_Creathead();//头节点 
    	Box_Add(box_head);//添加数据 
    	Box *low = box_head->next;//第一个有数据的节点 
    	Box *high = Box_FindBase(box_head);//最后一个有数据的点 
    	//Box_CreatBase(high);//为最后一个有数据的节点接一个节点 
    	Box_Print(box_head);//展示没有排序前的链表(因为是头插法,所以是反着输出的) 
    	Box_Qsort(low,high);//排序 
    	Box_Print(box_head);//展示经过排序后的内容
    	return 0; 
    }
    

    展示下运行结果:
    在这里插入图片描述
    在这里插入图片描述

    这个是普通数组的快排代码的展示:

    #include<stdio.h>//从小到大
    void Qs(int*a,int low,int high)
    {
        int i=low;
        int j=high;
        int key=a[low];  //关键点
        if(low>=high)
    	    return;
        while(low<high){
            for(;low<high&&key<=a[high];high--);  //从右边找 
            if(key>a[high]){  //找到比key小的了 
                a[low]=a[high];
            }
            for(;low<high&&key>=a[low];low++);  //从左往右找 
            if(key<a[low]){  //找到了 
                a[high]=a[low];
            }
        }
    	a[low]=key;
    	Qs(a,i,low-1);
    	Qs(a,low+1,j);
    }
    int main(void)
    {
    	int n;
    	scanf("%d",&n);
    	int i;
    	int a[n];
    	for(i=0;i<n;i++)
    		scanf("%d",&a[i]);
    	Qs(a,0,n-1);
    	for(i=0;i<n;i++)
    	{
    		printf("%d ",a[i]);
    	}
    } 
    

    如果有错误请您一定指出,我洗耳恭听!

    展开全文
  • 本程序主要实现c语言链表冒泡排序的功能,代码如下,需要者可以自取。(你电同学可以借鉴排序功能,但最好还是看懂后自己写) 难点分析:第一个交换需要引出前驱和最后一个的交换需要引出后继节点。 #include <...
  • 双向链表c语言实现

    2019-12-17 23:33:27
    双向链表c语言实现 引入 上一篇最后总结了单向链表的缺点,所以引入了双向链表。我认为双向链表相对于单向链表最大的优势就是省脑子,不需要再另有一个指针时时在前面。 单向链表 代码实现 问题描述 Write a ...
  • C语言】双链表实现与冒泡排序

    千次阅读 2019-07-28 12:16:58
    C语言】双链表实现与冒泡排序 基于C语言,不做标题党,LInux下GCC通过编译,大致流程(底部附图,源码): 新建双链表(节点数自定义),对节点data域用随机数种子进行随机赋值,并对该链表进行冒泡排序。 ...
  • C语言开发的双向冒泡排序算法,具体内容详见代码。
  • 熟悉C++的STL(标准模板库)的人都知道list底层是一个双向链表,支持通用类型数据的存储,使用起来非常方便,但对于C语言开发者来说,并没有这么方便的工具,所以在这里记录一下自己实现的通用数据类型双向链表,提供...
  • C语言笔试经典之双向链表实现

    千次阅读 2018-01-03 10:46:51
    C语言笔试经典之双向链表实现1、节点定义typedef struct DListElement_ { void * data; struct DListElement_ *prev; struct DListElement_ *next; }DListElement;2、链表定义typedef struct DList_ { int ...
  • 主要介绍了C语言实现的双链表功能,结合完整实例形式分析了基于C语言实现的双链表定义、添加、删除、排序等相关操作实现技巧,需要的朋友可以参考下
  • C语言实现双向链表

    2020-01-13 14:21:54
    创建空链表 dlist_t create_emptydlist() { //申请空间 dlist_t head = (dlist_t)malloc(sizeof(dnode_t)); if(head) { //head->data = -1; //空链表头节点的前置和后置指针都指向自己 head->pr...
  • 1. 双向链表的定义 【百度百科】 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和...
  • 输入一棵二元查找树,将该二元查找树转换成一个排序双向链表 要求不能创建任何新的节点,只调整指针的指向 微软面试题
  • 代码实现 /* head 和 tail 的指针的排序的时候,都有可能发生变化,所以这里使用二级指针 */ int quickSortDoubList(st_doubNode** phead, st_doubNode ** ptail){ if(NULL == phead || NULL == *phead || NULL =...
  • 双向循环链表库函数可以直接使用,只需要根据库函数的头文件中的链表类型和节点类型来创建数据就可以。分为 DoubleList.h 和 DoubleList.c 两个文件。需要把两个文件放到同一目录下编译。 DoubleList.h ...
  • 基数排序
  • 双向链表实现快速排序的递归算法 输入的形式:元素个数、元素都为整型。 输入值范围:元素个数为非负正整数,需要排序的元素都为整型。 输出的形式:排序前的元素序列和排序后的元素序列。 程序的功能:对用户...
  • C语言之链表:单向链表,循环链表,双向链表 提起链式存储结构,其与数组是两个非常基础的数据结构,每当提到链式存储结构时,一般情况下我们都会将其与数组放到一块儿来比较。 对于数组与链表,从结构上来看,数组...
  • 不太容易实现,因为链表这种数据结构会遇到很多边界问题,需要比较复杂的判断边界的操作,要是笔试遇到这种题,自求多福??? #include <stdio.h> #include<malloc.h> typedef struct n{ int data; ...
  • C语言实现链表之双向链表(十四)链表打印  上一篇文章给出了获取数据对应的结点的函数,本篇文章将给出链表打印。 /*============================================================================== * ...
  • 若最后一个元素不存在,此时双向链表尚未建立,因此将当前结点设为双向链表头结点 40 { 41 pHead= pCurrent; 42 } 43 else // 使双向链表中最后一个结点的右指针指向当前结点 44 { 45 pIndex->...
  • C语言实现双向循环链表 题目:要求实现根据要求的数字,使26个字母排序发生变化,例如数字为3,输出结果: DEFGHIJKLMNOPQRSTUVWXYZABC 同时支持负数,如-3 XYZABCDEFGHIJKLMNOPQRSTUVW 代码 /* * @Author: xgh * ...
  • C语言实现链表之双向链表(十五)测试用例  上一篇文章给出了最后的两个函数,即链表打印和排序,这篇文章将给出所有函数的测试用例,即ListTestTop.c文件。 /* ********************************************...
  • 之前也写过一篇C语言实现简单的双向循环链表,现在使用C++再来扩展一下内容。除了节点的插入、删除,还增加了一些链表的其他操作,包括节点修改、节点替换、节点查找、值查找、值排序等等。内容还是挺丰富的,废话不...
  • C语言实现双向列表的创建,删除,添加节点,删除节点,插入节点,遍历节点,打印节点,并结合插入排序法实现了基于双向链表的升序排序

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,299
精华内容 3,719
关键字:

双向链表排序c语言实现

c语言 订阅