チェーンテーブル情報分類問題
チェーンテーブル情報分類問題は主に元のチェーンテーブルの中の要素を順次検出して分類して新しいチェーンテーブルに挿入して分類を実現し、元のチェーンテーブルの中の要素を取り出して他のチェーンテーブルに挿入すると同時に要素を削除し、このように残りは別の要素であり、このような空間複雑度は最低とは言えないが、分類して保存する点から言えば、空間複雑度は低いはずだ.もちろんこのようにするのは時間の複雑さを犠牲にした前提の下でです;(やはり細部が重要ですね.j++を書き忘れたことで、チェーンテーブル削除関数が間違っているのではないかと疑っていました.もちろん、もう一つのポイントも無視しやすいです.ノードを削除するたびに、ノードを元の位置に戻す必要があります.ここでは、前駆ノードを使用してこの問題を実現しました.)
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
using namespace std;
typedef struct Node
{
char data;
Node *next;
}Linklist;
int Check(char e)//
{
if (e >= 'a' && e <= 'z' || e > 'A' && e <= 'Z')
return 1;
else if (e >= '0' && e <= '9')
return 0;
else
return -1;
}
void Deleted(Linklist *&A, int i)//
{
Linklist *p = A, *q;
int j = 0;
while (j != i)
{
p = p->next;
j++;
}
q = p->next;
p->next = q->next;
free(q);
}
void Insert(Linklist *&L, char e)//
{
Linklist *t, *p = L;
t = (Linklist *)malloc(sizeof(Linklist));
t->data = e;
while (p->next != NULL)
p = p->next;
p->next = t;
t->next = NULL;
}
void Displist(Linklist *L)//
{
Linklist *p = L->next;
while (p != NULL)
{
cout << p->data;
p = p->next;
}
}
int main()
{
char w[100];
int i;
Linklist *A, *B, *C, *p, *q, *t;
cin >> w;
A = (Linklist *)malloc(sizeof(Linklist));
A->next = NULL;
p = A;
for (i = 0;i < strlen(w);i++)
{
t = (Linklist *)malloc(sizeof(Linklist));
t->data = w[i];
p->next = t;
p = t;
}
p->next = NULL;
B = (Linklist *)malloc(sizeof(Linklist));
B->next = NULL;
C = (Linklist *)malloc(sizeof(Linklist));
C->next = NULL;
i = 0;
p = A;
q = p->next;
while (q != NULL)
{
if (Check(q->data) == 0)
{
Insert(B, q->data);
Deleted(A, i);
q = p->next;
}
else if (Check(q->data) == 1)
{
Insert(C, q->data);
Deleted(A, i);
q = p->next;
}
else
{
p = p->next;
q = q->next;
i++;
}
}
Displist(B);
cout << endl;
Displist(C);
cout << endl;
Displist(A);
cout << endl;
return 0;
}