10.2-5 环形链表实现字典操作INSERT、DELETE、SEARCH

一、题目

用环形链表来实现字典操作INSERT、DELETE、SEARCH，并给出它们的运行时间

二、代码

//List.h
#include <string>
using namespace std;
//链表结点
struct node
{
    node *next;
    int key;
    node(int x):next(NULL),key(x){}
};
//链表
struct list
{
    node *Head;//头结点，作为哨兵
    list():Head(){Head = new node(0);Head->next = Head;};
};
//插入
void Insert(list *L, int x)
{
    //构造一个新的结点
    node *A = new node(x);
    //找到应当插入的位置
    node *p = L->Head->next, *q = L->Head;
    while(p != L->Head && p->key < x)
    {
        q = p;
        p = p->next;
    }
    //插入结点
    q->next = A;
    A->next = p;
}
//删除
int Delete(list *L, node *A)
{
    //找到结点的前一个结点，因为是单链表，要循环整个链表直到找到这个结点的前一个结点
    node *p = L->Head->next, *q = L->Head;
    while(p != L->Head && p != A)
    {
        q = p;
        p = p->next;
    }
    //没找到
    if(p == L->Head)
    {
        cout<<"error:not found"<<endl;
        return -1;
    }
    //找到了，修改指针
    int ret = p->key;
    q->next = A->next;
    delete A;
    return ret;
}
//查找值为x的指针
node* Search(list *L, int x)
{
    //遍历整个链表查找这个结点
    node *p = L->Head->next;
    while(p != L->Head && p->key  < x)
        p = p->next;
    //没找到，返回NULL
    if(p == L->Head || p->key > x)
    {
        cout<<"error:not found"<<endl;
        return NULL;
    }
    //找到了，返回结点
    return p;
}
//打印
void Print(list *L)
{
    node *p = L->Head->next;
    while(p != L->Head)
    {
        cout<<p->key<<' ';
        p = p->next;
    }
    cout<<endl;
}

三、测试

#include <iostream>
#include <string>
#include "List.h"
using namespace std;
//测试
int main()
{
    list *L = new list;
    int x;
    string str;
    while(1)
    {
        cin>>str;
        if(str == "I")
        {
            cin>>x;
            Insert(L, x);
        }
        else if(str == "D")
        {
            cin>>x;
            node *A = Search(L, x);
            if(A)
                Delete(L, A);
        }
        else if(str == "P")
            Print(L);
    }
    return 0;
}