- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我已经编写了这段代码,一般来说效果很好,但是当我们到达 i == 74
列表元素为 4 - 11 - 18 - 4 - 10 - 18 - 17 - 22 - 14 - 29
和 swapNodes()
函数必须用键 18 交换两个节点,但是相反,我得到这些元素:4 - 18 - 4 - 10 - 18 - 17 - 22 - 14 - 29
。我尝试使用“交换”之前的确切值初始化列表,然后尝试交换这两个节点,一切都按预期进行。
PS:如果有人能帮助我用更少的行数编写 swapNodes()
函数,我将不胜感激,但目前这不是必需的。
typedef struct _node{
int key;
struct _node *next;
struct _node *prev;
}node;
node* createNode(int key){
node* a = (node*)malloc(sizeof(struct _node));
a->key = key;
a->next = NULL;
a->prev = NULL;
return a;
}
void printList(node* head){
while (head != NULL){
printf("%d", head->key);
if(head->next != NULL) printf(" - ");
head = head->next;
}
printf("\n");
}
void fillList(node** head, int dim){
int i;
for(i=0; i<dim; i++)
listInsert(head, createNode(rand()%30));
}
//findes a node given an index, the indices start from 1
node** findNode(node** head, int index){
int i;
for(i=1; i<index; i++)
head = &(*head)->next;
if(head != NULL) return head;
else return NULL;
}
void listInsert(node** head, node* node){
if((*head) == NULL){
(*head) = node;
return;
}
node->next = (*head);
(*head)->prev = node;
(*head) = node;
}
int main(){
node* list = NULL;
fillList(&list, 10);
int i, a, b;
for(i=0; i<100; i++){
printList(list);
a = rand()%10 +1;
b = rand()%10 +1;
swapNodes(&list, *findNode(&list, a), *findNode(&list, b));
printList(list);
printf("\n");
}
return 0;
}
<小时/>
编辑:
我设法重写了 swapNodes()
函数,但这次在 main 中执行相同的行,我在 i==15
的列表中得到了一个循环,a==4
和 b==2
。同样,如果我尝试手动交换任何节点,该功能工作正常。
void swapNodes(node** head, node* a, node* b){
node* aPrev = a->prev;
node* aNext = a->next;
node* bPrev = b->prev;
node* bNext = b->next;
if(a == b) return;
if(a->prev == b ||
(b->prev == NULL && a->next == NULL) ||
(b->prev == NULL && b->next == a) ||
a->next == NULL) return swapNodes(head, b, a);
if(a->prev == NULL)
(*head) = b;
else if(b->prev == NULL)
(*head) = a;
if(a->next == b){
if(aPrev != NULL) aPrev->next = b;
b->prev = aPrev;
b->next = a;
bNext->prev = a;
a->prev = b;
a->next = bNext;
}else{
b->next = aNext;
a->next = bNext;
if(a->prev != NULL)
aPrev->next = b;
if(b->prev != NULL)
bPrev->next = a;
if(a->next != NULL)
aNext->prev = b;
if(bNext != NULL)
bNext->prev = a;
if(b != NULL)
b->prev = aPrev;
if(a != NULL)
a->prev = bPrev;
}
}
最佳答案
按照 @ggorlen 给我的想法,我重写了 swapNodes()
函数,添加了一些新函数,最后它完美地工作了。为了在提取节点之前跟踪节点的位置,我创建了一个 struct ,其中包含从 findIndex() 函数返回的索引和节点本身。我还更改了 findNode()
函数,使其返回 node*
类型的变量,而不是 node**
类型。当然,这不是很有效,但我会凑合的。
typedef struct _extractedNode{
struct _node* node;
int index;
}extractedNode;
int findIndex(node* head, node* node){
int i=1;
node* temp = head;
while(node != temp){
temp = temp->next;
i++;
}
return i;
}
extractedNode extractNode(node** head, node* node){
extractedNode extracted;
extracted.index = 0;
if(node == NULL){
printf("extractNode(): il nodo non esiste!\n");
extracted.node = NULL;
extracted.index = -1;
}else{
node* prev = node->prev;
node* next = node->next;
if(prev == NULL){
(*head) = next;
extracted.index = 1;
}
if(extracted.index != 1)
extracted.index = findIndex(*head, node);
if(prev != NULL)
prev->next = next;
if(next != NULL)
next->prev = prev;
node->next = NULL;
node->prev = NULL;
extracted.node = node;
}
return extracted;
}
void listInsertAsIndex(node** head, int index, node* node){
if(index <= 0) return;
if(index == 1) return listInsert(head, node);
else{
node* prev = findNode(*head, index-1);
node* next = prev->next;
prev->next = node;
node->prev = prev;
if(next != NULL){
node->next = next;
next->prev = node;
}
}
}
void swapNodes(node** head, node* a, node* b){
if(a == b) return;
extractedNode aX, bX;
if(a->prev == NULL && a->next == b){
aX = extractNode(head, a);
listInsertAsIndex(head, 2, aX.node);
}else if(b->prev == NULL && b->next == a){
bX = extractNode(head, b);
listInsertAsIndex(head, 2, bX.node);
}else if(a->next == b){
aX = extractNode(head, a);
listInsertAsIndex(head, aX.index +1, aX.node);
}else if(b->next == a){
bX = extractNode(head, b);
listInsertAsIndex(head, bX.index +1, bX.node);
}else{
aX = extractNode(head, a);
bX = extractNode(head, b);
if(aX.index < bX.index){
listInsertAsIndex(head, aX.index, bX.node);
listInsertAsIndex(head, bX.index +1, aX.node);
}else{
listInsertAsIndex(head, bX.index, aX.node);
listInsertAsIndex(head, aX.index, bX.node);
}
}
}
关于c - 双链表: swapping function doesn't always work,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59216399/
我的问题很简单。执行以下操作是否安全? 不需要任何道德建议,例如“不要将函数命名为 swap()!”或者随便什么,拜托! file1.hpp //header guards here #include
我很好奇,所以我检查了swap的源代码! clojure 存储库上的函数,如下所示: (defn swap! "Atomically swaps the value of atom to be:
我正在实现一个与 std::array 具有类似接口(interface)的类,它同时具有 member swap()和 non-member swap() . 由于我希望我的类模仿标准容器,因此我想
这个问题在这里已经有了答案: Rationale behind member function swap (1 个回答) 关闭 4 年前。 如果Coll是标准容器类型,a和b是Coll的实例;那么,
int a=5; b=7; int *pa=&a, *pb=&b; 交换 a 和 b 的值与交换指针的值有何不同,即 pa和 pb (不是 *pa 和 *pb )?两种情况下的结果不一样吗? 我们什么
好的,这是程序,绝对正确 #include using namespace std; template void Swap(T &a , T &b); int main(){ int i
std::swap() 函数是否可以在具有各种不同对象作为变量成员的类中正常工作?特别是,如果其中一些成员是智能指针? class test { ... std::shared_ptr
我正在尝试实现 copy-and-swap idiom在我的自定义 Matrix 类中,我按照链接问题中建议的方式执行 swap() 时遇到了一些麻烦: (我使用的编译器是MS VS2010 IDE的
我知道 ADL 是什么,我知道在 C++ 中,内部作用域函数隐藏外部作用域函数。也就是说,名称不会跨范围重载。所以函数重载需要在相同的范围内完成。 现在我的问题是,对于这个通用代码片段: #inclu
给定两个 std::vector v1, v2。 我想知道使用 std::swap(v1, v2) 比 v1.swap(v2) 有什么好处。 我已经实现了一个关于性能观点的简单测试代码(我不确定它是否
std::string 有一个成员函数 swap,这是交换两个大字符串的有效方法。 既然我们有了 move 语义,那么,给定两个大字符串 s1 和 s2,以下代码 s1.swap(s2); 在效率方面
同时使用 copy-and-swap idiom在一个具有常量引用作为成员的类中, 出现上述错误。 示例代码: #include #include using std::reference_wra
背景 考虑以下代码: #include namespace ns { struct foo { foo() : i(0) {} int i;
我们有: vector f(int); vector v; 这个有效: f(x).swap(v); 这不是: v.swap(f(x)); 为什么? 最佳答案 swap()对 vector 进行非常量引
我已在 Azure 中配置了一个生产和暂存槽,每个槽都使用自己的 SQL Azure 数据库。 每个连接字符串都配置为“粘性”。 但是,当我将生产槽(目标)与暂存槽(源)交换时,我收到以下警告。 这条
我有以下代码: char swap(char reg, char* mem) { std::swap(reg, *mem); return reg; } 我希望这可以编译为: swap
我使用 xor-swap 的插入排序不工作,但没有 xor-swap 它工作正常。如何修复我的异或交换插入排序算法? 没有异或交换的插入排序 - //sorts the given array in
关闭。这个问题是not reproducible or was caused by typos .它目前不接受答案。 这个问题是由于错别字或无法再重现的问题引起的。虽然类似的问题可能是on-topi
我正在实现 copy-and-swap idiom对于我设计的一个小型非拥有内存引用对象的 operator=。当 MemRef 引用我信任其生命周期的一 block 缓冲区时,_ptr 指向缓冲区,
我有两个问题,第二个是可选的。首先,在下面的程序(一个简单的卡片程序的原型(prototype))中,我得到以下错误: (29): error C2660: 'shuffle' : function
我是一名优秀的程序员,十分优秀!