第九单元 基本数据结构

9.1 线性表（顺序结构）

线性表可以用普通的一维数组存储。
你可以让线性表可以完成以下操作（代码实现很简单，这里不再赘述）：
1. 返回元素个数。
2. 判断线性表是否为空。
3. 得到位置为 p 的元素。
4. 查找某个元素。
5. 插入、删除某个元素：务必谨慎使用，因为它们涉及大量元素的移动。

9.2 线性表（链式结构）

(1) 单链表!

1. 定义：下面有一个空链表，表头叫 head，并且表内没有任何元素。

struct node
{
int value;
node *next;
} arr[MAX];
int top=-1;
node *head = NULL;

2. 内存分配：在竞赛中不要用 new，也不要用 malloc、calloc——像下面一样做吧。

#define NEW(p) p=&arr[++top];p->value=0;p->next=NULL
node *p;
NEW(head); // 初始化表头
NEW(p); // 新建结点

 

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中的下标
} 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 函数。

#define NEW(p) p=arr+(++top);p->value=0;p->next=NULL;p->prev=NULL
node *p;
NEW(head); // 初始化表头
NEW(p); // 新建结点

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;
}