首页 > 代码库 > 【算法导论】学习笔记——第10章 基本数据结构
【算法导论】学习笔记——第10章 基本数据结构
基本数据结构主要包括：栈、队列、链表和有根树。
10.1 栈和队列
栈和队列都是动态集合，且在其上进行DELETE操作所移除的元素时预先设定的。在栈中，被删除的是最近插入的元素：栈实现的是一种后进先出（LIFO）策略。队列实现的是一种先进先出（FIFO）策略。
栈
栈上的INSERT操作称为压入（PUSH），无参数的DELETE操作称为弹出（POP）。栈操作的代码非常简单：
1 typedef struct { 2 int A[MAXN]; 3 int top; 4 } Stack_st; 5 6 int StackIsEmpty(Stack_st *S) { 7 if (S->top == 0) 8 return 1; 9 return 0;10 }11 12 void Push(Stack_st *S, int x) {13 if (S->top+1 < MAXN) {14 S->top = S->top + 1;15 S->A[S->top] = x;16 }17 }18 19 int Pop(Stack_st *S) {20 if ( StackIsEmpty(S) ) {21 perror("underflow\n");22 return -1;23 } else {24 --S->top;25 return S->A[S->top+1];26 }27 }
三种栈操作的执行时间都是O(1)。
队列
队列上的INSERT操作称为入队（ENQUEUE），DELETE操作称为出队（DEQUEUE）。队列操作的代码也非常简单：
1 typedef struct { 2 int A[MAXN]; 3 int head, tail; 4 int length; 5 } Queue_st; 6 7 int QueueIsEmpty(Queue_st *Q) { 8 if (Q->head == Q->tail) 9 return 1;10 return 0;11 }12 13 int QueueIsFull(Queue_st *Q) {14 if ((Q->tail+1)%Q->length == Q->head)15 return 1;16 return 0;17 }18 19 void Enqueue(Queue_st *Q, int x) {20 if (QueueIsFull(Q)) {21 perror("overflow\n");22 return ;23 }24 Q->A[Q->tail] = x;25 if (Q->tail == Q->length)26 Q->tail = 1;27 else28 ++Q->tail;29 }30 31 int Dequeue(Queue_st *Q) {32 int x;33 34 if (QueueIsEmpty(Q)) {35 perror("underflow\n");36 return -1;37 } else {38 x = Q->A[Q->head];39 if (Q->head == Q->length)40 Q->head = 1;41 else42 ++Q->head;43 return x;44 }45 }
10.2 链表
链表（linked list）是一种这样的数据结构，其中的各对象按线性顺序排列。与数组不同的是，链表的顺序是由各个对象里的指针决定的。链表主要包括搜索、插入和删除操作。双向链表的操作代码如下。
1 typedef struct Node { 2 int key; 3 struct Node *pre, *next; 4 } Node; 5 6 typedef struct { 7 Node *head; 8 } List; 9 10 Node *List_Search(List L, int k) {11 Node *p = L.head;12 while (p!=NULL && p->key!=k)13 p = p->next;14 return p;15 }16 17 void List_Insert(List *L, Node *x) {18 x->next = L->head;19 if (L->head != NULL)20 L->head->pre = x;21 L->head = x;22 x->pre = NULL;23 }24 25 void List_Delete(List *L, Node *x) {26 if (x->pre != NULL)27 x->pre->next = x->next;28 else29 L->head = x->next;30 if (x->next != NULL)31 x->next->pre = x->pre;32 free(x);33 }
哨兵(sentinel)是一个哑对象，其作用是简化边界条件的处理。使用哨兵后，相关操作如下所示。
1 typedef struct { 2 Node *nil; 3 } LList; 4 5 Node *LList_Search(LList L, int k) { 6 Node *p = L.nil->next; 7 while (p!=L.nil && p->key!=k) 8 p = p->next; 9 return p;10 }11 12 void LList_Insert(LList *L, Node *x) {13 x->next = L->nil->next;14 L->nil->next->pre = x;15 L->nil->next = x;16 x->pre = L->nil;17 }18 19 void LList_Delete(LList *L, Node *x) {20 x->pre->next = x->next;21 x->next->pre = x->pre;22 free(x);23 }
哨兵基本不能降低数据结构相关操作的渐近时间界，但可以降低常数因子。这哨兵其实就是《数据结构》里的头结点。
10.2-4 LIST_SEARCH‘过程中的每一次循环迭代都需要两个测试，一是检查x!=L.nil，另一个是检查x.key!=k试说明如何在每次迭代中省略对x!=L.nil的检查。
解：x!=L.nil主要是为了防止循环无限查找，为了省略x!=L.nil的检查，即需要在检查到尾结点可退出循环，即尾结点的下一个结点需要满足x.key==k，则进行搜索过程后，将哨兵的key值赋为k即可，代码实现如下：
1 Node *LList_Search(LList L, int k) {2 Node *p = L.nil->next;3 L.nil->key = k;4 while (p->key!=k)5 p = p->next;6 return p;7 }
10.2-6 选用合适的数据结构，支持O(1)时间的UNION操作。
解：双向循环链表（其实带不带哨兵均可，以带哨兵为例）。没什么技巧，就是把头尾结点该链的链好。
1 void LList_Union(LList *L, LList *L1, LList *L2) {2 L->nil->pre = L2->nil->pre;3 L->nil->next = L1->nil->next;4 L1->nil->pre->next = L2->nil->next;5 L2->nil->next->pre = L1->nil->pre;6 L2->nil->pre->next = L->nil;7 L1->nil->next->pre = L->nil;8 }
10.2-7
【算法导论】学习笔记——第10章 基本数据结构