(1) 单链表! 1. 定义:下面有一个空链表,表头叫head,并且表内没有任何元素。 struct node { int value; node *next; } arr[MAX]; int top=-1; node *head = NULL; 2. 内存分配:在竞赛中不要用new,也不要用malloc、calloc——像下面一样做吧。 | p=&arr[++top];p->value=0;p->next=NULL | | | | |
3. 插入:把q插入到p的后面。时间复杂度O(1)。 if (p!=NULL && q!=NULL) { q->next=p->next; p->next=q; } | | | |
4. 删除:把p的下一元素删除。时间复杂度O(1)。 if (p!=NULL && p->next!=NULL) | | { node *q=p->next; p->next=q->next; // delete(q); } | |
5. 查找或遍历:时间复杂度O(n)。 node *p=first; while (p!=NULL) { // 处理value // cout<<p->value<<'\t'; p=p->next; } (2) 静态链表 指针的作用就是存储地址。如果我们找到了替代品,就可以放弃指针了。 需要把上面的定义改一下: struct node { int value; int next; } arr[MAX]; | | |
(3) 循环链表 和单链表有一个重大区别:单链表最后一个元素的next指向NULL,而循环链表最后一个元素的next 指向first。 遍历时要留心,不要让程序陷入死循环。 一个小技巧:如果维护一个表尾指针last,那么就可以在O(1)的时间内查找最后一个元素。同时可以防止遍历时陷入死循环。 (4) 双链表 1. 定义:下面有一个空链表,表头叫first。 struct node { int value; node *next, *prev; } arr[MAX]; int top=-1; node *first = NULL; // 根据实际需要可以维护一个表尾指针last。 |
2. 内存分配:最好不要使用new运算符或malloc、calloc函数。 | p=arr+(++top);p->value=0;p->next=NULL;p->prev=NULL | | | | |
3. 插入:把q插入到p的后面。时间复杂度O(1)。 if (p==NULL||q==NULL) { q->prev=p; q->next=p->next; q->next->prev=q; p->next=q; } | | | |
4. 删除:把p的下一元素删除。时间复杂度O(1)。 if (p==NULL||p->next==NULL) { | | | node *q=p->next; p->next=q->next; q->next->prev=p; // delete(q); } | | | | |
5. 查找或遍历:从两个方向开始都是可以的。 (5) 将元素插入到有序链表中* void insert(const node *head, node *p) { node *x, *y; y=head; do { x=y; y=x->next; } while ((y!=NULL) && (y->value < p->value); x->next=p; p->next=y; } |
|