目录
review
Chapter 1 Introdution
Chapter 2 Algorithm Analysis
一、运行时间估计
Chapter 3 Lists, Stacks, and Queues 表 栈 队列
一、表 Lists
二、栈 stack LIFO(后进先出)
数据结构：数据集data set +关系relation + 操作operations
算法+数据结构=程序
逻辑描述+物理操作
T(N)=O(f(N)) 存在正常数 c 和 n0 使得当 N ≧ n0 时 T(N) ≦ cf(N)
T(N)=Ω(g(N)) 存在正常数 c 和 n0 使得当 N ≧ n0 时 T(N) ≧ cg(N)
T(N)=Θ(h(N)) 当且仅当T(N) =O(h(N)) 且 T(N) = Ω(h(N))
T(N)=o(p(N)) 若 T(N) = O(p(N)) 且 T(N) ≠ Θ(p(N))
some rules
1、若 𝑇_1 (𝑁)=𝑂(𝑓(𝑁)) 且 𝑇_2 (𝑁)=𝑂(𝑔(𝑁)), 那么
(a) 𝑇_1 (𝑁)+𝑇_2 (𝑁)=max(𝑂(𝑓(𝑁), 𝑂(𝑔(𝑁))),
(b) 𝑇_1 (𝑁)∗𝑇_2 (𝑁)=𝑂(𝑓(𝑁)∗𝑔(𝑁))
2、若𝑇(𝑁) 是 k 次多项式(polynomial), 那么 𝑇(𝑁)=Θ(𝑁^𝑘)
3、对任意常数 k 有〖𝑙𝑜𝑔𝑁〗^𝑘 =𝑂(𝑁) .
this tell us that logarithms(对数) grow very slowly
1.表的简单数组实现
缺点：MaxSize 需要估计，通常需要估计得大一些，浪费大量空间，特别是存在未知大小的表；
插入 Insertion 和Deletion 需要O(N) 时间，同时涉及大量数据移动；
优点：PrintList 和 Find 以线性时间执行，FindKth 花费常数时间
2.链表 linked list (指针实现)
链表由一系列不必在内存中相连的结构组成，每个结构均含有表元素和指向包含该元素后继元的结构的指针 Next ，最后一个单元的 Next 指向 NULL(0);
链表的类型声明
struct Node; typedef struct Node *PtrToNode; typedef PtrToNode List; typedef PtrToNode Position; struct Node { ElementType Element; Positon Next; };
测试链表是否为空
// return true if is empty int IsEmpty(List L) { return L->Next == NULL; }
测试当前位置是否为链表末尾
//return true if P is the last position in list L int IsLast(Position P, List L) { return P->Next == NULL; }
Find 例程 查找
//return position of X in L; NULL if not find Position Find(ElementType X, List L) { Position P; P = L->Next; while( P != NULL && P->Element != X) { P = P->Next; } return P; }Delete 删除例程 O(1) time（需调用 FindPrevious 找到含有X的表元的前驱元P）
void Delete(ElementType X, List L) { Position P, TmpCell; P = FindPrevious( X, L ); if(!IsLast( P, L))// if p is the last->not find, else find { TmpCell = P->Next; P->Next = TmpCell->Next; free(TmpCell); } } Position FindPrevious(Element X,List L) { Position P; P = L; while(P->Next != NULL && P->Next->Element != X) { P = P->Next; } return P; }插入例程 O(1) time
//insert after legal position P (use FindPrevious) void Insert( ElemrntType X, List L, Position P) { Position TmpCell = malloc(sizeof(struct Node)); if( TmpCell == NULL) { return;//error } TmpCell->Element = X; TmpCell->Next = P->Next; P->Next = TmpCell; }双链表
在数据结构上加上一个域，使它包含前一个单元的指针即可。
循环链表
让最后的单元反过来指向第一个单元
特点
1.数据存储在一组结构体中。每个结构体包含有数据及指向下一个结构体的指针。
2.一个新的结构体可通过调用 malloc 而从系统全局内存（global memory）得到，并通过调用 free 被释放
3.链表的游标实现
链表游标实现的声明
typedef int PtrToNode; typedef PtrToNode List; typedef PtrToNode Position; struct Node{ ElementType Element; Position Next; }; struct Node CursorSpace[SpaceSize];CursorAlloc & CursorFree
static Position CursorAlloc(void) { Position P; P = CursorSpace[P].Next = CursorSpace[0].Next; return P; } static void CursorFree(Position P) { CursorSpace[P].Next = CursorSpce[0].Next; CursorSpace[0].Next = P; }测试是否为空-游标实现
// return true if empty int IsEmpty(List L) { return CursorSpace[L].Next == 0; }测试 P 是否为链表末尾-游标实现
//return true if p is the last position of list l int IsLast(Position P, List L) { return CuesorSpace[P].Next == 0; }Find, Delete, Insert 游标实现
Position Find(Element X, List L) { Position P; P = CursorSpace[L].Next; while(P && CursorSpace[P].Element != X) { P = CursorSpace[P].Next; } return P; } void Delete(ElementType X, List L) { Position P, TmpCell; p = FindPrevious( X , L ); if(!IsLast(P, L)) { TmpCell = CursorSpace[P].Next; CursorSpace[P].Next = CursorSpace[TmpCell].Next; CursorFree(TmpCell); } } void Insert(ElementType X, List L, Position P) { Position TmpCell = CursorAlloc(); if(TmpCell == 0) { return;//error, out of space; } CursorSpace[TmpCell].Element = X; CursorSpace[TmpCell].Next = CursorSpace[P].Next; CursorSpace[P].Next = TmpCell; }链表的应用
1.多项式 the polynomial ADT
数组实现
零多项式
加法
乘法
链表实现
其余同上
2.基数排序 radix sort
桶排序 bucket sort
有 N 个整数，范围从1到 M ，留置一个数组 count ，大小为 M ，并初始化为 0.于是，count 有 M 个桶，开始时为空，当A_i 被读入时，count[A_I] +1.在所有输入被读完后扫描数组count 打印输出排好序的表，花费时间O(M+N)
基数排序是桶排序的推广（x进制就有x个桶）
使用多趟桶排序，最低有效位优先
1.按照最低位优先进行桶式排序
2.按照第一步得到的顺序按照次低位优先进行第二次桶排序；多于一个数进入同一个桶时按输入顺序放进去
......
最后一步按照最高位排，没有这一位的为0。
3.多重表 Multilists
eg:一所有40000名学生和2500门课程的大学需要生成两种报告。第一个报告列出每个班的注册者，第二个报告列出每个学生注册的班级。
类型声明
题目
1.given a linked list with a header node, delete the maximum value node
试编写在带头结点的单链表中删除一个最大值结点的高效算法
typedef struct NODE * pLinkList; struct NODE { int data; struct NODE * link; }; void delete_max(pLinkList list){ if (!list->link){ return; } pLinkList ptr_max, ptr_cur; ptr_max = list; ptr_cur = list->link; while (ptr_cur->link){ if (ptr_cur->link->data > ptr_max->link->data){ ptr_max = ptr_cur; } ptr_cur = ptr_cur->link; } ptr_cur = ptr_max->link; ptr_max->link = ptr_cur->link; free(ptr_cur); }
2.已知一个带有表头结点的单链表，结点结构为，假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。
typedef struct NODE * pLinkList; struct NODE{ int data; struct NODE * link; }; int SearchRevk(pLinkList list, int k){ pLinkList p, q; int count; p = q = list->link; count = 0; while ( p != NULL ){ //倒数第k个为正数第n-k+1个，即n-(k-1) if ( count < k-1 ){ count++; } else {//移动k-1次之后q开始动 q = q->link; } p = p->link; } if ( count == k ){ printf("%d\n", q->data); return 1; } else { return 0; } }
1.数组实现
struct StackRecord { int Capacity ; /* size of stack */ int TopOfStack; /* the top pointer */ /* ++ for push, -- for pop, -1 for empty stack */ ElementType *Array; /* array for stack elements */ } ; typedef struct StackRecord *Stack;创建空栈
释放栈S
判断是否栈满
Push操作
Pop
Top
2.链表实现
