假设每个元素的查询概率相同，1/n
2、 顺序表插入元素：
插入元素key到a[i]
for(j=n-1;j>=i;j--)a[j+1]=a[j]; //从后向前移动元素 a[i]=key;
插入最好复杂度：O(1)，插在最后元素a[n-1]之后 插入最坏复杂度: O(n)，插在第一个元素a[0]之前
插入每个元素移动次数之和 插入平均复杂度=------------------------- 元素个数
0+ 1 + 2 + 3 +... +n
= --------------------------- n+1
n*(n+1)/2 n
=------------- =----- =0.5n=O(n) n+1 2
= （每个位置被插入的移动次数* 该位置被插入的概率）之和
= 第1个位置被插入的移动次数*该位置插入概率 + 第2个位置被插入的移动次数*该位置插入概率 +...+
+ 第n+1个位置被插入的移动次数*该位置插入概率
1 1 1
=n*------ + (n-1)*---- + ...+ 0* ---- =O(n) n+1 n+1 n+1
假设每个位置被插入的概率相同，1/(n+1)
插入在位置k之后 k=0,1,2,...,n
k=0，插入在位置1 table[0] k=1，插入在位置2 table[1] k=2，插入在位置3 table[2] ...
k=n，插入在位置n+1 table[n]
因此 table[k]=x 是正确的
3、 顺序表 删除元素： 删除元素a[i]
for(j=i;j 删除最好复杂度：O(1)，删除最后一个a[n-1] 删除最坏复杂度: O(n)，删除第一个a[0] 删除每个元素移动次数之和 删除平均复杂度=-------------------------=O(n) 元素个数 0+1+...+(n-1) n*(n-1)/2 n-1 =----------------= --------------- =------- = O(n) n n 2 注意： 平均！=最坏 涉及题目： 08年 13 07年 4,11,22,28 06年 一(5) 05年 一(2)，二(7)，四(2) 二、链表 1、 链表类型：单链表，循环单链表 双链表，循环双链表 头指针:一定要有 不是循环链表，一定要有头指针 是循环链表，头指针/尾指针：要有一个。 头结点：可有（简单）可无（麻烦）， 是否有头结点影响到算法的具体实现 2、类型定义代码 typedef struct node *link; //指针类型定义 typedef struct node{//链表实现 ListItem element; link next; }Node;//链表结点类型定义 ┏━━━━┳━━━━┓ ┃element ┃ next ┃ ┗━━━━┻━━━━┛ link first; //头指针 first ┏━━┓ ┗━━┛ ↓ ┏━┳┓ ┏━┳┓ ┏━┳┓ ┏━┳━┓ ┃ ┃┃ → ┃ ┃┃ →┃ ┃┃ ...→ ┃ ┃^ ┃ ┗━┻┛ ┗━┻┛ ┗━┻┛ ┗━┻━┛ 3、创建链表，略去 malloc(n): 在内存中分配一片连续空间，长度是n个字节 将首字节地址返回。 4、遍历链表 int ListLength(link L){ int len=0; link p; p=L; while(p!=NULL){ len++; p=p->next; } return len; } 调用 length=ListLength(first); 遍历程序写法： link p; p=first; while(p!=NULL){ p=p->next; } 5、链表插入p26, 假定将新节点x插入到节点i之后。 5.1、最简单情况：节点i用指向它的指针p来表示。 新节点x用指向它的指针q来表示。 指针调整代码是： q->next=p->next; p->next=q; 插入前 p ┏━━┓ ┗━━┛ ↓ ┏━┳┓ ┏━┳┓ ┃ i┃┃ → ┃ ┃┃ →... ┗━┻┛ ┗━┻┛ ┏━┳┓ ┃ x┃┃ ┗━┻┛ ↑ ┏━━┓ q ┗━━┛ 插入后 p ┏━━┓ ┗━━┛ ↓ ┏━┳┓ ┏━┳┓ ┃ i┃┃-╳→┃ ┃┃ →... ┗━┻┛ ┗━┻┛ ↓ ↗ ┏━┳┓╱ ┃ x┃┃ ┗━┻┛ ↑ ┏━━┓ q ┗━━┛ 5.2、如果节点i需要通过扫描得到， 假定位置是第i个节点（从1开始） 需要链表遍历 int k; link p; p=first; k=1; while(p!=0 && k 5.3 如果需要建立存储待插入元素x的新结点 link q; q=(link)malloc(sizeof(Node)); q->element=x; 5.4 插入在链表最开头。 q->next=first; first=q; 5.5 空表插入。（创建链表） if(first==NULL){ first=q; q->next=NULL; } 6、 节点删除 将节点i删除,p是指向i节点指针变量 6.1、最简单情况：q是指向i的前驱节点指针变量 指针调整代码是： q->next=p->next; free(p); 或者 q->next=q->next->next 删除前 q ┏━━┓ ┗━━┛ ↓ ┏━┳┓ ┏━┳┓ ┏━━┳┓ ┃ ┃┃ → ┃i ┃┃→┃i+1 ┃┃ →... ┗━┻┛ ┗━┻┛ ┗━━┻┛ ↑ ┏━━┓ p ┗━━┛ 删除后 q ┏━━┓ ┗━━┛ ↓ ┌→——————→┐ ┏━┳┓ ┏━┳┓ ┏━━┳┓ ┃ ┃┃ ┃i ┃┃→┃i+1 ┃┃ →... ┗━┻┛ ┗━┻┛ ┗━━┻┛ ↑(回收) ┏━━┓ p ┗━━┛ 6.2、 i是链表最开头的节点。 first=first->next; 6.3、 如果节点i需要通过扫描得到， 假定位置是第i个节点（从1开始） 找到指向第i-1个结点的指针q q=first; for(k=1; k 涉及题目： 08年 6,25 07年 5,19,20 06年 一(1,6)，二(18,19) 05年 一(1,12)， 第三章 堆栈 Stack 堆栈是特殊的线性表，只能在堆栈顶插入删除元素。 一、用链表实现，进出栈时插入删除结点， 不存在取之不尽的问题，注意尽量 地减少进出栈的时间复杂度，栈顶设在 链表开头。 二、用数组data实现，长度为n， 存在取之不尽的问题 因此设置栈顶指针。 栈顶指针top：int,存储栈顶元素的下标 指向非空位置，除非栈为空。 如果空栈，top=-1 如果满栈，top=n-1 进栈：将元素x进栈 如果栈满，无法进栈 否则： data[++top]=x 先调整top， 然后放置元素x 出栈：将栈顶出栈，放置在x中 如果栈空，无法出栈 否则： x=data[top--] 先取走元素，存入x 再调整top data数组 ┏━━━┓ ┃ ┃ n-1 ┣━━━┫ ┃ ... ┃ ┣━━━┫ ┃ ┃ 1 ┣━━━┫ ┃ ┃ 0 ┗━━━┛ -1 top=-1 涉及题目： 08年 1 07年 2,3 06年 一(9) 05年 一(4)，三(4) 第四章 队列 Queue 队列是特殊的线性表，只能在队尾插入元素，在队头删除元素。 一、用链表实现，进出队时插入删除结点， 注意尽量减少进出队的时间复杂度O(1)， 设置两个指针，队头指针和队尾指针， 二、用数组实现，长度为n，循环队列 （充分利用数组空间） 循环队列方案1 1、maxsize=n,数组长度是n 2、队头指针front（整型，存数组下标）， 指向空位置，无论队是否为空 3、队尾指针rear（整型，存数组下标）， 指向非空位置，除非队空 4、队空：rear==front, 初始化front=rear=0,0个元素。 5、队满：(rear+1)%n==front, 牺牲一个单元,队满只储存n-1个元素