用位置号打印C链表中的重复条目
Print duplicate entries in C linked list with location number
我正在尝试打印链表中出现的所有重复项，但无法打印最后一个。
我还尝试将最后一个重复字符串 ptr1->name 存储在一个临时变量中并在 while 循环结束后打印它，但它不适用于不同的一对值，只有最后一个，我也不能找到一种方法来打印最后一个重复字符串的位置。
如果没有更好的方法来打印最后重复的字符串，我如何才能只忽略第一次出现的字符串？
示例：
列表：
1 7001 桑贾纳
2 7014 艾西瓦娅
3 7025 兰吉特
4 7017 导师
5 7101 迪克夏
6 7023 印度
7 7017 导师
8 7001 桑贾纳
9 7017 导师
10 7016 基兰
11 7020 拉吉尼
12 7020 拉吉尼
所需输出：
1 7001 桑贾纳
4 7017 导师
7 7017 古鲁达 -- Dup
8 7001 Sanjana -- 重复
9 7017 古鲁达 -- Dup
11 7020 拉吉尼
12 7020 拉吉尼 -- Dup
Edit:
Found Solution with help of @peal-mazumder
解法：
void duplicate(void){
int count = 0;
int loc1 = 0; // 1st Pointer location
int loc2 = 0; // 2nd Pointer location
struct node * ptr1, * ptr2;
bool vis[5000] = {false};
ptr1 = root;
while (ptr1!=NULL){
loc1++;
// if node is already marked for duplicate it will skip compare and move to next node.
if (vis[loc1]) {
ptr1 = ptr1->link;
continue;
}
ptr2 = ptr1->link;
loc2 = loc1;
while(ptr2!=NULL){
loc2++;
if ((ptr1->num == ptr2->num) && !(strcmpi(ptr1->name, ptr2->name))){
count++;
if (count == 1) printf("Duplicate Search Results: \n");
// delete below if statement if original not to be printed.
if (!vis[loc1]) printf(" %d--> %02d %s\n",loc1, ptr1->num, ptr1->name); // print original
printf(" %d--> %02d %s --> Dup\n", loc2, ptr2->num, ptr2->name); // print duplicate
vis[loc2] = true; // marked for duplicate.
vis[loc1] = true; // not required if original not to be printed.
}
ptr2 = ptr2->link;
}
ptr1 = ptr1->link;
}
if (!count) {
printf("No duplicates found in the list!\n");
}else{
printf("Total (%d) duplicates.\n", count);
}
}
输出：
1--> 7001 Sanjana
8--> 7001 Sanjana --> Dup
4--> 7017 Gurudas
7--> 7017 Gurudas --> Dup
9--> 7017 Gurudas --> Dup
11--> 7020 Rajni
12--> 7020 Rajni --> Dup
Total (4) duplicates.
8 --> 7001 Sanjana
9 --> 7017 Gurudas
12 --> 7020 Rajni
Total (3) duplicates.
如果您正在尝试打印类似的内容，请检查下面的代码，否则请在您的描述中为给定的示例案例添加所需的输出。
struct node {
int num;
char name[20];
struct node* link;
} * root;
// function
void duplicate(void){
int count = 0;
int loc = 0; // Location in the list.
struct node * ptr1, * ptr2;
bool vis[200000] = {false};
ptr1 = root; // root is global pointer variable.
while (ptr1->link!=NULL) {
loc++;
if(vis[ptr1->num]) { // if i already processed for same num value then we don't need to check duplicate for this again.
ptr1 = ptr1->link;
continue;
}
vis[ptr1->num] = true;
ptr2 = ptr1->link;
int Ptr2Location = loc + 1, lastDupLocation = 0;
struct node *temp; // to store last duplicate node
while(ptr2 != NULL) {
if ((ptr1->num == ptr2->num) && !(strcmpi(ptr1->name, ptr2->name))){
temp = ptr2;
lastDupLocation = Ptr2Location;
}
Ptr2Location++;
ptr2 = ptr2->link;
}
if(lastDupLocation)
printf(" %d --> %02d %s\n", lastDupLocation, temp->num, temp->name), count++;
ptr1 = ptr1->link;
}
if (!count) {
printf("No duplicates found in the list!\n");
}else {
printf("\nTotal (%d) duplicates.\n", count);
}
}
void insert(int num, char str[20], int len)
{
if(root == NULL) { //If the list is empty
root = new node();
root->num = num;
strcpy(root->name, str);
root->link = NULL;
}
else{
node* current_node = root; //make a copy of root node
while(current_node->link!=NULL) //Find the last node
{
current_node=current_node->link; //go to next address
}
node *newnode = new node(); //create a new node
newnode->num = num;
strcpy(newnode->name, str);
newnode->link = NULL;
current_node->link=newnode; //link the last node with new node
}
}
int main()
{
int num, n, i;
cin>>n;
char name[20];
for (i = 0; i<n; i++)
{
scanf("%d %s", &num, name);
insert(num, name, strlen(name));
}
duplicate();
return 0;
}
You can sort this according to their location by storing these values in a data structure or a structure.
1 --> 7001 Sanjana
8 --> 7001 Sanjana
4 --> 7017 Gurudas
7 --> 7017 Gurudas
9 --> 7017 Gurudas
11 --> 7020 Rajni
12 --> 7020 Rajni
Code
void duplicate(void){
int count = 0;
int loc = 0; // Location in the list.
struct node * ptr1, * ptr2;
bool vis[200000] = {false};
ptr1 = root; // root is global pointer variable.
while (ptr1->link!=NULL) {
loc++;
if(vis[ptr1->num]) { // if i already processed for same num value then we don't need to check duplicate for this again.
ptr1 = ptr1->link;
continue;
}
ptr2 = ptr1->link;
int Ptr2Location = loc + 1;
while(ptr2 != NULL) {
if ((ptr1->num == ptr2->num) && !(strcmpi(ptr1->name, ptr2->name))){
if(!vis[ptr1->num])
printf(" %d --> %02d %s\n", loc, ptr1->num, ptr1->name), count++;
printf(" %d --> %02d %s\n", Ptr2Location, ptr2->num, ptr2->name);
vis[ptr1->num] = true;
}
Ptr2Location++;
ptr2 = ptr2->link;
}
ptr1 = ptr1->link;
}
}
不太实用的答案
duplicate 是一个 O(n^2) 函数；也就是说，一个循环遍历 ptr1，并且对于每个值，嵌套循环遍历 ptr2。这在 linked-list.
中很常见
一种更有效的方法是散列法，即将密钥转换成称为散列[code]的数字。此特定数据的hash table stores the records by their hash. Seeing this data, I would assume that name depends on num, so num can be your key. If there is guarantee that num falls in, say, 7000 -- 7099, one could have a collision-free perfect hash funcion，H(x) = x.num - 7000； O(n)速度。
例如，H(1 7001 Sanjana) = 1 -> 将记录存储在 table[1]。到达 H(8 7001 Sanjana) = 1； table[1] 已被占用，因此立即知道它是重复的。
但为什么还要为数据烦恼呢？如果一个人不介意 false-positives 的（小）机会和概率 Bloom filter，则可以有 O(n) run-time 和 O(1) space 要求.
#include <stdio.h>
#include <errno.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
/* Define a maximum name length and have the C pre-processor encode this in a
string automatically. */
#define NAME_LENGTH 31
#define QUOTE(n) XQUOTE(n)
#define XQUOTE(n) #n
/** < */
static uint32_t hash(uint32_t x) {
x = ((x >> 16) ^ x) * 0x45d9f3b;
x = ((x >> 16) ^ x) * 0x45d9f3b;
x = (x >> 16) ^ x;
return x;
}
/** Thomas Wang's 32 bit Mix Function. */
static uint32_t inthash(uint32_t key) {
key += ~(key << 15);
key ^= (key >> 10);
key += (key << 3);
key ^= (key >> 6);
key += ~(key << 11);
key ^= (key >> 16);
return key;
}
/** <https://nullprogram.com/blog/2018/07/31/> */
static uint32_t lowbias32(uint32_t x) {
x ^= x >> 16;
x *= 0x7feb352dU;
x ^= x >> 15;
x *= 0x846ca68bU;
x ^= x >> 16;
return x;
}
int main(void) {
uint64_t bloom = 0;
size_t scans = 0, count = 0;
unsigned no, id;
char name[NAME_LENGTH + 1], lf;
loop:
switch(scanf("%u %u %" QUOTE(NAME_LENGTH) "s%c", &no, &id, name, &lf)) {
case EOF: if(feof(stdin)) break; else goto catch;
case 0: case 1: case 2: case 3: errno = EILSEQ; goto catch;
case 4:
if(lf != '\n') { errno = EILSEQ; goto catch; }
else {
const uint32_t x = (uint32_t)id;
const uint64_t xvect = (1 << (hash(x) & 63))
| (1 << (inthash(x) & 63)) | (1 << (lowbias32(x)));
if((bloom & xvect) == xvect) // print (possible) duplicate
printf(" %u %u %s --> (possible) Dup\n", no, id, name), count++;
else // marked for duplicate
bloom |= xvect;
}
scans++;
goto loop;
}
if (!count) {
printf("No duplicates found in the %zu list!\n", scans);
}else{
printf("Total %zu/%zu (possible) duplicates.\n", count, scans);
}
return EXIT_SUCCESS;
catch:
fprintf(stderr, "While scanning record %zu: %s.\n", scans, strerror(errno));
return EXIT_FAILURE;
}
7 7017 Gurudas --> (possible) Dup
8 7001 Sanjana --> (possible) Dup
9 7017 Gurudas --> (possible) Dup
12 7020 Rajni --> (possible) Dup
Total 4/12 (possible) duplicates.
我正在尝试打印链表中出现的所有重复项，但无法打印最后一个。
我还尝试将最后一个重复字符串 ptr1->name 存储在一个临时变量中并在 while 循环结束后打印它，但它不适用于不同的一对值，只有最后一个，我也不能找到一种方法来打印最后一个重复字符串的位置。
如果没有更好的方法来打印最后重复的字符串，我如何才能只忽略第一次出现的字符串？
示例：
列表：
1 7001 桑贾纳
2 7014 艾西瓦娅
3 7025 兰吉特
4 7017 导师
5 7101 迪克夏
6 7023 印度
7 7017 导师
8 7001 桑贾纳
9 7017 导师
10 7016 基兰
11 7020 拉吉尼
12 7020 拉吉尼
所需输出：
1 7001 桑贾纳
4 7017 导师
7 7017 古鲁达 -- Dup
8 7001 Sanjana -- 重复
9 7017 古鲁达 -- Dup
11 7020 拉吉尼
12 7020 拉吉尼 -- Dup
Edit:
Found Solution with help of @peal-mazumder
解法：
void duplicate(void){
int count = 0;
int loc1 = 0; // 1st Pointer location
int loc2 = 0; // 2nd Pointer location
struct node * ptr1, * ptr2;
bool vis[5000] = {false};
ptr1 = root;
while (ptr1!=NULL){
loc1++;
// if node is already marked for duplicate it will skip compare and move to next node.
if (vis[loc1]) {
ptr1 = ptr1->link;
continue;
}
ptr2 = ptr1->link;
loc2 = loc1;
while(ptr2!=NULL){
loc2++;
if ((ptr1->num == ptr2->num) && !(strcmpi(ptr1->name, ptr2->name))){
count++;
if (count == 1) printf("Duplicate Search Results: \n");
// delete below if statement if original not to be printed.
if (!vis[loc1]) printf(" %d--> %02d %s\n",loc1, ptr1->num, ptr1->name); // print original
printf(" %d--> %02d %s --> Dup\n", loc2, ptr2->num, ptr2->name); // print duplicate
vis[loc2] = true; // marked for duplicate.
vis[loc1] = true; // not required if original not to be printed.
}
ptr2 = ptr2->link;
}
ptr1 = ptr1->link;
}
if (!count) {
printf("No duplicates found in the list!\n");
}else{
printf("Total (%d) duplicates.\n", count);
}
}
输出：
1--> 7001 Sanjana
8--> 7001 Sanjana --> Dup
4--> 7017 Gurudas
7--> 7017 Gurudas --> Dup
9--> 7017 Gurudas --> Dup
11--> 7020 Rajni
12--> 7020 Rajni --> Dup
Total (4) duplicates.
8 --> 7001 Sanjana
9 --> 7017 Gurudas
12 --> 7020 Rajni
Total (3) duplicates.
如果您正在尝试打印类似的内容，请检查下面的代码，否则请在您的描述中为给定的示例案例添加所需的输出。
struct node {
int num;
char name[20];
struct node* link;
} * root;
// function
void duplicate(void){
int count = 0;
int loc = 0; // Location in the list.
struct node * ptr1, * ptr2;
bool vis[200000] = {false};
ptr1 = root; // root is global pointer variable.
while (ptr1->link!=NULL) {
loc++;
if(vis[ptr1->num]) { // if i already processed for same num value then we don't need to check duplicate for this again.
ptr1 = ptr1->link;
continue;
}
vis[ptr1->num] = true;
ptr2 = ptr1->link;
int Ptr2Location = loc + 1, lastDupLocation = 0;
struct node *temp; // to store last duplicate node
while(ptr2 != NULL) {
if ((ptr1->num == ptr2->num) && !(strcmpi(ptr1->name, ptr2->name))){
temp = ptr2;
lastDupLocation = Ptr2Location;
}
Ptr2Location++;
ptr2 = ptr2->link;
}
if(lastDupLocation)
printf(" %d --> %02d %s\n", lastDupLocation, temp->num, temp->name), count++;
ptr1 = ptr1->link;
}
if (!count) {
printf("No duplicates found in the list!\n");
}else {
printf("\nTotal (%d) duplicates.\n", count);
}
}
void insert(int num, char str[20], int len)
{
if(root == NULL) { //If the list is empty
root = new node();
root->num = num;
strcpy(root->name, str);
root->link = NULL;
}
else{
node* current_node = root; //make a copy of root node
while(current_node->link!=NULL) //Find the last node
{
current_node=current_node->link; //go to next address
}
node *newnode = new node(); //create a new node
newnode->num = num;
strcpy(newnode->name, str);
newnode->link = NULL;
current_node->link=newnode; //link the last node with new node
}
}
int main()
{
int num, n, i;
cin>>n;
char name[20];
for (i = 0; i<n; i++)
{
scanf("%d %s", &num, name);
insert(num, name, strlen(name));
}
duplicate();
return 0;
}
You can sort this according to their location by storing these values in a data structure or a structure.
1 --> 7001 Sanjana
8 --> 7001 Sanjana
4 --> 7017 Gurudas
7 --> 7017 Gurudas
9 --> 7017 Gurudas
11 --> 7020 Rajni
12 --> 7020 Rajni
Code
void duplicate(void){
int count = 0;
int loc = 0; // Location in the list.
struct node * ptr1, * ptr2;
bool vis[200000] = {false};
ptr1 = root; // root is global pointer variable.
while (ptr1->link!=NULL) {
loc++;
if(vis[ptr1->num]) { // if i already processed for same num value then we don't need to check duplicate for this again.
ptr1 = ptr1->link;
continue;
}
ptr2 = ptr1->link;
int Ptr2Location = loc + 1;
while(ptr2 != NULL) {
if ((ptr1->num == ptr2->num) && !(strcmpi(ptr1->name, ptr2->name))){
if(!vis[ptr1->num])
printf(" %d --> %02d %s\n", loc, ptr1->num, ptr1->name), count++;
printf(" %d --> %02d %s\n", Ptr2Location, ptr2->num, ptr2->name);
vis[ptr1->num] = true;
}
Ptr2Location++;
ptr2 = ptr2->link;
}
ptr1 = ptr1->link;
}
}
不太实用的答案
duplicate 是一个 O(n^2) 函数；也就是说，一个循环遍历 ptr1，并且对于每个值，嵌套循环遍历 ptr2。这在 linked-list.
一种更有效的方法是散列法，即将密钥转换成称为散列[code]的数字。此特定数据的hash table stores the records by their hash. Seeing this data, I would assume that name depends on num, so num can be your key. If there is guarantee that num falls in, say, 7000 -- 7099, one could have a collision-free perfect hash funcion，H(x) = x.num - 7000； O(n)速度。
例如，H(1 7001 Sanjana) = 1 -> 将记录存储在 table[1]。到达 H(8 7001 Sanjana) = 1； table[1] 已被占用，因此立即知道它是重复的。
但为什么还要为数据烦恼呢？如果一个人不介意 false-positives 的（小）机会和概率 Bloom filter，则可以有 O(n) run-time 和 O(1) space 要求.
#include <stdio.h>
#include <errno.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
/* Define a maximum name length and have the C pre-processor encode this in a
string automatically. */
#define NAME_LENGTH 31
#define QUOTE(n) XQUOTE(n)
#define XQUOTE(n) #n
/** < */
static uint32_t hash(uint32_t x) {
x = ((x >> 16) ^ x) * 0x45d9f3b;
x = ((x >> 16) ^ x) * 0x45d9f3b;
x = (x >> 16) ^ x;
return x;
}
/** Thomas Wang's 32 bit Mix Function. */
static uint32_t inthash(uint32_t key) {
key += ~(key << 15);
key ^= (key >> 10);
key += (key << 3);
key ^= (key >> 6);
key += ~(key << 11);
key ^= (key >> 16);
return key;
}
/** <https://nullprogram.com/blog/2018/07/31/> */
static uint32_t lowbias32(uint32_t x) {
x ^= x >> 16;
x *= 0x7feb352dU;
x ^= x >> 15;
x *= 0x846ca68bU;
x ^= x >> 16;
return x;
}
int main(void) {
uint64_t bloom = 0;
size_t scans = 0, count = 0;
unsigned no, id;
char name[NAME_LENGTH + 1], lf;
loop:
switch(scanf("%u %u %" QUOTE(NAME_LENGTH) "s%c", &no, &id, name, &lf)) {
case EOF: if(feof(stdin)) break; else goto catch;
case 0: case 1: case 2: case 3: errno = EILSEQ; goto catch;
case 4:
if(lf != '\n') { errno = EILSEQ; goto catch; }
else {
const uint32_t x = (uint32_t)id;
const uint64_t xvect = (1 << (hash(x) & 63))
| (1 << (inthash(x) & 63)) | (1 << (lowbias32(x)));
if((bloom & xvect) == xvect) // print (possible) duplicate
printf(" %u %u %s --> (possible) Dup\n", no, id, name), count++;
else // marked for duplicate
bloom |= xvect;
}
scans++;
goto loop;
}
if (!count) {
printf("No duplicates found in the %zu list!\n", scans);
}else{
printf("Total %zu/%zu (possible) duplicates.\n", count, scans);
}
return EXIT_SUCCESS;
catch:
fprintf(stderr, "While scanning record %zu: %s.\n", scans, strerror(errno));
return EXIT_FAILURE;
}
7 7017 Gurudas --> (possible) Dup 8 7001 Sanjana --> (possible) Dup 9 7017 Gurudas --> (possible) Dup 12 7020 Rajni --> (possible) Dup Total 4/12 (possible) duplicates.