0
큐에 대한 다음 코드를 링크 된 목록으로 구현했습니다. 이제 연결된 목록으로 대기열 배열로 해시 테이블을 가져 오려고합니다. 그것은 삭제 후 삽입 할 때까지 잘 작동합니다.대기열의 해시 테이블에 연결된 목록으로 오류 삽입?
대기열은 연결된 목록으로 구현됩니다. 그래서 제거하고 싶을 때 head 요소를 지우고 insert에 꼬리를 사용합니다.
해시 테이블을 만들려면 삽입 된 순서대로 다른 연결된 키 목록을 유지해야합니다. 삭제는 먼저이 키를 제거하고 개별 연결된 목록으로 이동하여 헤드를 제거하고 헤드를 업데이트하는 것으로 시작됩니다.
#include<stdio.h>
#include<stdlib.h>
struct Node{
int value;
struct Node *next;
struct Node* head;
struct Node* tail;
};
struct Node* lruhashtable[10];
struct Node* trackHead;
struct Node* trackTail;
void insert(int page)
{
if(trackHead==NULL)
{
trackHead=malloc(sizeof(struct Node));
trackHead->value=(page-1)%10;
trackHead->next=NULL;
trackTail=trackHead;
}
else
{
struct Node* temp=malloc(sizeof(struct Node));
temp->value=(page-1)%10;
temp->next=NULL;
trackTail->next=temp;
trackTail=temp;
}
}
void hashEntry(int page)
{
struct Node** iter;
iter=&lruhashtable[(page-1)%10];
for(;*iter;iter=&(*iter)->next);
*iter = malloc(sizeof **iter);
(*iter)->value = page;
(*iter)->next = NULL;
if((*iter)->head==NULL)
{
(*iter)->head=*iter;
(*iter)->tail= (*iter)->head;
}
else
{
(*iter)->tail->next=*iter;
(*iter)->tail=*iter;
}
insert(page);
}
void deleteInHashEntry()
{
int pageToDelete=delete();
struct Node** iter;
iter=&lruhashtable[pageToDelete];
if((*iter)->head!=NULL)
{
struct Node* curr=(*iter)->head;
(*iter)=curr->next;
if((*iter)!=NULL)
(*iter)->head=*iter;
free(curr);
}
else
{
(*iter)->tail=NULL;
}
}
void print()
{
int i;
struct Node **iter;
for(i=0;i<10;i++)
{
iter=&lruhashtable[i];
for(;*iter;iter=&(*iter)->next)
{
printf("%d%s%d\n",(*iter)->value,"--",i);
}
}
}
int delete()
{
int page=-1;
if(trackHead!=NULL)
{
struct Node*current=trackHead;
page=current->value;
trackHead=current->next;
free(current);
}
else
{
trackTail=NULL;
}
return page;
}
void printTrack()
{
struct Node* temp=trackHead;
while(temp!=NULL)
{
printf("%d",temp->value);
printf("\n");
temp=temp->next;
}
}
int main()
{
hashEntry(1);
hashEntry(11);
hashEntry(2);
hashEntry(3);
hashEntry(22);
hashEntry(4);
hashEntry(33);
print();
printTrack();
deleteInHashEntry();
print();
printTrack();
deleteInHashEntry();
print();
printTrack();
deleteInHashEntry();
print();
printTrack();
hashEntry(1);
hashEntry(11);
hashEntry(22);
deleteInHashEntry();
deleteInHashEntry();
deleteInHashEntry();
deleteInHashEntry();
deleteInHashEntry();
deleteInHashEntry();
deleteInHashEntry();
return 0;
}