gpt4 book ai didi

c - 双链表插入排序

转载 作者:行者123 更新时间:2023-11-30 14:21:25 25 4
gpt4 key购买 nike

我一直在为双向链表开发一组函数,其中一个我遇到的问题是将元素插入到列表中,但保持列表按排序顺序排列。因此,如果我有一个 {3, 4, 6} 列表并插入 5,那么该列表将变为 {3, 4, 5, 6}

我昨晚重写完最新的代码,请评论告诉我是否有更好的方法,我把头文件和c文件都贴出来了。我想指出的一件事是,我不使用指向当前节点的指针,而仅在插入函数中创建一个指针,该指针创建一个具有临时放置的新节点。

列表.H

/* custom types */

typedef struct node
{
int val;
struct node * next;
struct node * prev;
}Node;

typedef struct list
{
Node * head;
Node * tail;
}List;

/* function prototypes */

/* operation: creates a list */
/* pre: set equal to a pointer to a list*/
/* post: list is initialized to empty */
List* NewList();

/* operation: Insert a number into a list sorted */
/* pre: plist points to a list, num is an int */
/* post: number inserted and the list is sorted */
void Insert(List * plist, int x);

列表.C

/* c file for implentation of functions for the custome type list */
/* specifically made for dueling lists by, Ryan Foreman */

#include "List.h"
#include <stdlib.h> /* for exit and malloc */
#include <stdio.h>

List* NewList()
{
List * plist = (List *) malloc(sizeof(List));
plist->head = NULL;
plist->tail = NULL;
return plist;
}

void Insert(List * plist, int x)
{
/* create temp Node p then point to head to start traversing */
Node * p = (Node *) malloc(sizeof(Node));
p->val = x;

/* if the first element */
if ( plist->head == NULL) {
plist->head = p;
plist->tail = p;
}
/* if inserting into begining */
else if ( p->val < plist->head->val ) {
p->next = plist->head;
plist->head->prev = p;
plist->head = p;
}

else {
p->next = plist->head;
int found = 0;
/* find if there is a number bigger than passed val */
while((p->next != NULL) && ( found == 0)) {
if(p->val < p->next->val)
found = 1;
else {
p->next = p->next->next;
}
}
/* if in the middle of the list */
if(found == 1)
{
p->prev = p->next->prev;
p->next->prev = p;
}
/* if tail */
else {
plist->tail->next = p;
p->prev = plist->tail;
plist->tail = p;
}
}
}

感谢您对代码的任何意见,欢迎提出任何意见

最佳答案

关于您的 C' 使用情况的一些评论。

  • 在 C 中,从指向 void 的指针转换为指向对象的指针是不必要的。
  • 检查此类库中的 malloc 返回可能是个好主意。

关于c - 双链表插入排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14714921/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com