This blog has been shut down permanently.

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  13 随笔 :: 0 文章 :: 25 评论 :: 0 Trackbacks

最开始用了很原始的数据初始化方法,多谢dskit指点,现在已经改正为哈希字典了。因为在创建新节点的时候浪费时间比较严重,所以如果改成用向量会更好一些。

#include<stdio.h>
#include
<stdlib.h>
int map[25]= {2223334445556667077888999};
typedef 
struct LNode{
    
int data[8];
    
struct LNode *next;
}
;
int main()
{
    
int row,c,tag,i,j,n,temp[7];//输入次数
    n=0;//电话号码个数
    LNode *head=0//指向链表头节点
    LNode *front= 0//指向当前节点的前一位置
    LNode *tail= 0//指向当前遍历到的节点
    scanf("%d\n",&row);
    
if(row<=0&&row>100000return 0;
    
for(i=0; i<row; i++)//将有效输入存入temp数组
    {
       
for(j=0; (c= getchar())&&(c!='\n')&&(j<7); )
       
{
           
if(c!='-')
           
{
               
if(c>='A'&&c<='Y')temp[j++]= map[c-'A'];
               
else if(c>='0'&&c<='9')temp[j++]= c-'0';
           }

       }

       
if(n==0//新建第一节点
       {
           LNode 
*p= (LNode *)malloc(sizeof(LNode));
           
for(int j=0; j<7; j++)
               p
->data[j]= temp[j];
           p
->data[7]= 1;
           p
->next= 0;
           head
= p;
           n
++;
           
continue;
       }

       
else //新建非第一节点
       {
           tag
= -1;
           
for(front= head,tail= head; tail!= 0; front= tail,tail= tail->next)
           
{
                
for(j=0; j<7; j++)
                
{
                    
if(tail->data[j]>temp[j])   //找到的目标节点值大于temp
                    {
                        
if(front==tail){tag=2;break;}
                        
else {tag=3;break;}
                    }

                    
else if(tail->data[j]<temp[j])  //目标节点值小于temp
                    {
                        
if(tail->next==0){tag= 0;break;}
                        
else break;
                    }

                    
else if(j==6&&tail->data[j]==temp[j]){tag=1;tail->data[7]+=1;break;} //目标节点值等于temp
                }

                
if(tag==-1)continue;      //未找到插入点
                else if(tag==1)break;     //目标节点值等于temp
                else if(tag==0)           //目标节点值小于temp
                {
                    LNode 
*p= (LNode *)malloc(sizeof(LNode));
                    
for(j=0; j<7; j++)
                        p
->data[j]= temp[j];
                    p
->data[7]= 1;
                    p
->next= 0;
                    tail
->next= p;
                    n
++;
                    
break;
                }

                
else if(tag==2)   //找到的目标节点值大于temp,目标节点为头结点
                {
                    LNode 
*p= (LNode *)malloc(sizeof(LNode));
                    
for(j=0; j<7; j++)
                        p
->data[j]= temp[j];
                    p
->data[7]= 1;
                    p
->next= head;
                    head
= p;
                    n
++;
                    
break;
                }

                
else if(tag==3)   //找到的目标节点值大于temp,目标节点非头结点
                {
                    LNode 
*p= (LNode *)malloc(sizeof(LNode));
                    
for(j=0; j<7; j++)
                       p
->data[j]= temp[j];
                    p
->data[7]= 1;
                    p
->next= tail;
                    front
->next= p;
                    n
++;
                    
break;
                }

            }

        }

    }

    tag
= 0;
    
for(tail= head; tail!=0; tail= tail->next)    //遍历链表输出
    {
        
if(tail->data[7]>1)
        
{
            tag
= 1;
            
for(i=0; i<8; i++)
            
{
                
if(i==3)printf("-");
                
if(i==7)printf(" ");
                printf(
"%d",tail->data[i]);
            }

            printf(
"\n");
        }

    }

    
if(tag==0)printf("No duplicates.");
}
posted on 2009-11-11 00:44 iZ 阅读(1852) 评论(4)  编辑 收藏 引用

评论

# re: POJ1002链表算法 2009-11-11 21:54 梦芭莎
不错,收藏一下算法,省得自己写  回复  更多评论
  

# re: POJ1002链表算法 2009-11-12 15:18 凡客诚品官方网
收藏了!!  回复  更多评论
  

# re: POJ1002链表算法 2009-11-15 21:51 iSsay
其实可以优化的地方很多,就是不知道该怎么改了  回复  更多评论
  

# re: POJ1002链表算法[未登录] 2009-11-16 22:44 dskit
#include<iostream>
using std::cin;
using std::cout;
using std::endl;

#ifdef DEBUG
#include<string>
using std::string;
using std::freopen;
string input_file_name = __FILE__;
#endif

//here add other file need to included, and declare namespace need to use.
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
using namespace std;
//here declare global variables;
char dictionary[26] = {2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 0, 7, 7, 8, 8, 8, 9, 9, 9, 0};
char no[50];
char oarray[10];
bool flag;

struct Trie_node
{
int count;
Trie_node* next[10];
};

Trie_node root;

Trie_node node_pool[200002];
int index;
Trie_node* p;

void insert(char* s)
{
p = &root;
while(*s != '\0')
{
if(p->next[*s - '0'] == NULL)
p->next[*s - '0'] = &node_pool[index++];
p = p->next[*s - '0'];
++s;
}

++p->count;
}

void inline travel(Trie_node* node, int c)
{
for(int i = 0; i < 10; ++i)
{

if(node->next[i] == NULL)
continue;

oarray[c] = (char)(i + '0');

if(c >= 6)
{
if(node->next[i]->count > 1)
{
flag = true;
printf("%c%c%c-%c%c%c%c %d\n", oarray[0], oarray[1],
oarray[2], oarray[3],
oarray[4], oarray[5],
oarray[6], node->next[i]->count);
}
}
else
{
travel(node->next[i], c + 1);
}
}

}


//here add funtions.
void inline format_number(char* no)
{
//int len = strlen(no);
//printf("%s\n", no);
int count = 0;
int sum = 0;
for(int i = 0; no[i] != '\0'; ++i)
{
++sum;
if(no[i] >= 'A' && no[i] <= 'Z')
{
no[i] = '0' + dictionary[no[i] - 'A'];
}
else if(no[i] == '-')
{
++count;
}

if(no[i] != '-')
no[i - count] = no[i];

}
no[sum - count] = '\0';
//printf("%s\n", no);
}

int main(int argc, char* argv[])
{
#ifdef DEBUG
if(!freopen((input_file_name.substr(0, input_file_name.size() - 4) + ".in").c_str(), "r", stdin))
{ cout << "input data error, not found input file." << endl; return -1; }
#endif

//here add code for solve problem.
int n = 0;
//input
scanf("%d", &n);
flag = false;
index = 0;
getchar();
for(int i = 0; i < n; ++i)
{
gets(no);
//puts(no);
format_number(no);
insert(no);
}

travel(&root, 0);

if(!flag)
{
printf("No duplicates.\n");
}

return 0;
}
  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理