链表

约 118 个字 57 行代码 预计阅读时间 1 分钟

一、代码模板

1. 结构体定义

//结构体定义
typedef struct node *PtrToNode;
struct node{
    int element;
    PtrToNode next;
};
typedef PtrToNode List;//List代表链表
typedef PtrToNode Position;//Position代表特定位置

2. 函数实现

//我们设计带头节点的链表，减少对头节点的判断
int IsEmpty(List L){
    if(L->next==NULL){
        return 0;
    }
    else{
        return 1;
    }
}
//最后一项
int IsLast(Position P){
    if(P->next==NULL){
        return 1;
    }
    else{
        return 1;
    }
}
//查找
Position Find(int x,List L){
    Position P=L;
    while(P!=NULL&&P->element!=x){
        P=P->next;
    }
    return P;
}
//查找前一项
Position FindPrevious(int x,List L){
    Position P=L;
    while(P->next!=NULL&&P->next->element!=x){
        P=P->next;
    }
    return P;
}
//在P后插入
void Insert(int x, List L, Position P){
    //先创建新节点
    Position tmp=(PtrToNode)malloc(sizeof(struct node));
    tmp->element=x;
    tmp->next=P->next;
    P->next=tmp;
}

List Init(int x, List L){
    Position p=(PtrToNode)malloc(sizeof(struct node));
    p->element=-1;
    p->next=NULL;
    return p;
}

二、理论题

1. For a sequentially stored linear list of length \(N\), the time complexities for deleting the first element and inserting the last element are \(O(1)\) and \(O(N)\), respectively.

Answer

F.
a sequentially stored linear list 是线性表，不是链表，英文翻译别看错了……
对于线性表，第一个元素通常需要先把剩余的N个元素后移，所以是\(O(N)\). 最后一个元素往往是直接插入， \(O(1)\).

Comments