数据结构课堂笔记
数据结构课堂上的知识总结
顺序线性表
定义
/*
* 宏定义表初始长度,重新分配内存块增加的长度
* 定义Sqlist结构体其中包含指向队头元素的指针,表长度,表大小
* size是静态的,表示当前表的容量是多少,在重新分配内存块的时候才会被更改
* length是动态的,表示当前表中有多少元素,在插入新的元素的时候会被修改
* Sqlist表示顺序线性表
*/
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct{
ElemType *elem;
int length;
int size;
}Sqlist;
初始化
/*
* 传入一个Sqlist的结构体实例,通过引用的方式进行接收
* 首先使用malloc为顺序线性表分配空间
* 然后进行判断:是否成功分配空间，若未成功分配则退出
* 最后对length和size进行赋值
* 函数运行成功,返回OK状态
*/
Status InitList_sq(Sqlist &L)
{
L.elem=(ElemType *)malloc(List_INIT_SIZE*sizeof(ElemType));
if(!L.elem)
{
exit(OVERFLOW);
}
L.length=0;
L.size=LIST_INIT_SIZE;
return OK;
}
清空线性表
// 直接将长度设置为0即可,以后再插入的时候覆盖旧元素
Status ClearList_Sq(SqList &L)
{
L.length=0;
return OK;
}
销毁线性表
// 针对数组而言,free指向队头的指针即可释放空间
Status DestroyList_Sq(SqList &L)
{
// 可替换为free(*(L.elem[0]))
free(L.elem);
return OK;
}
插入
/*
* 通过引用的方式接收Sqlist结构体实例,插入的位置,插入元素的值
* 首先对i的合法性进行判断:i的最小值为1,最大值为L.length+1
* 接着对L的合法性进行判断:L.length不能大于L.size
* 若L不合法则需要重新分配内存空间
* 若成功分配则更新L.elem即顺序线性表的表头指针和L.size即原size加上新分配的内存大小
* 运行到第25行,所有的异常情况已被排除或修正,此时将q赋值为需要插入的位置的地址
* 需要注意的是:由于顺序线性表是通过指针创建的故其编号从0开始
* 将线性表中的元素向后移动一位,这里需要注意的是:由于是将元素从前向后移动,故需要从后往前遍历
* 移动结束后,将e赋值给q所指向的位置,更新length
* 函数运行成功,返回OK状态
*/
Status ListInsert_Sq(Sqlist &L,int i,ElemType e)
{
if(i<1 || i>L.length+1)
{
return ERROR;
}
if(L.length>=L.size)
{
newbase=(ElemType *)realloc(L.elem,(L.size+LISTINCREMENT)*sizeof(ElemType));
if(!newbase)
{
exit(OVERFLOW);
}
L.elem=newbase;
L.size+=LISTINCREMENT;
}
q=&(L.elem[i-1]);
for(p=&(L.elem[L.length-1]);p>=q;p--)
{
*(p+1)=*(p);
}
*q=e;
++L.length;
return OK;
}
删除
/*
* 通过引用的方式接收Sqlist的实例,需要删除的位置的标号,通过引用的方式接收e
* 为什么要通过引用的方式接收e呢？
* 举例来讲,如果我们通过如下的方式调用ListDelete_Sq函数
* `int e;ListDelete_Sq(L,i,e);cout<<"e"<<endl;`
* 通过运行上一行代码,就可以实现删除L所描述的线性表中的第i个元素,并输出删除的这个元素的值
* 回归正题
* 首先对i的值进行检查,删除一个线性表中的元素,其标号取值一定属于[1,L.length]
* 若不符合上一行的要求,则返回ERROR表示出现错误
* 接着处理e,将要删除的元素的值赋给e
* 然后将删除的位置之后的元素向前一位
* 这里需要注意的是:由于是向前一位,故在遍历的时候需要从前往后遍历
*/
Status ListDelete_Sq(SqList &L,int i,ElemType &e)
{
if(i<1 || i>L.length)
{
return ERROR;
}
p=&(L.elem[i-1]);
e=*p;
q=L.elem[L.length-1];
for(p++;p<=q;p++)
{
*(p-1)=*(p);
}
L.length--;
return OK;
}
查找
/*
* 输入顺序线性表,待查找的值,函数做参数(不需要背,考试的时候直接用==就可以)
* 由于不需要对线性表进行修改,故不需要用引用的方式输入顺序线性表
* 遍历线性表,若当前元素不等于e,则继续查找,若等于则跳出循环
* 判断i的值
* 如果i的值属于[1,L.length]则说明L.elem[i-1]==e,即查找成功且线性表中第i个元素的值为e,返回i
* 如果i的值不在这个范围内,则说明遍历了一遍顺序线性表后,没有查找到指定的值,说明顺序线性表中不存在这个值,返回0
*/
int LocateElem_Sq(Sqlist L,ElemType e,Status(*compare)(ElemType,ElemType))
{
i=1;
p=L.elem;
while(i<=L.length && !(*compare)(*p++,e))i++;
if(i<=L.length)
{
return i;
}
return 0;
}
例题：
两个线性表La,Lb，分别表示集合A和集合B，求新集合A = A∪B（顺序存储结构存储）
// 由于是顺序线性表故函数名中需要标注sq以此与链表区分
// 由于将La作为新的线性表,有对La的修改操作,故需要引用La
// 由于Lb仅需要做值传递,故不需要对Lb进行引用
void union_sq ( SqList &La , SqList Lb )
{
La_len=La.length;Lb_len=Lb.length;
// 遍历Lb
for(i=1;i<=Lb_len;i++)
{
// 获取Lb中第i个元素的值
e = Lb.elem[i-1];
// 如果La中不存在这个元素,那么就在La中加入这个元素
if (!LocateElem_Sq(La,e,equal))
// 此处不严谨,若La_len的值超过La.size就会造成溢出
La.elem[La_len++]=e;
}
// 更新La的长度
La.length=La_len;
}
已知线性表LA和LB的数据元素按值有序排列，要求归并为一个线性表LC，且LC中数据元素仍按值有序， LA、LB、 LC均为顺序存储结构存储。
void MergeList_Sq(Sqlist La,Sqlist Lb,Sqlist Lc)
{
// pa,pb为遍历La,Lb所描述的顺序线性表的指针
pa=La.elem;
pb=Lb.elem;
// 定义Lc的长度和大小
Lc.size=Lc.length=La.length+Lb.length;
// 为Lc开辟内存空间
pc=Lc.elem=(ElemType *)malloc(Lc.size*sizeof(ElemType));
// 若开辟失败则退出
if(!Lc.elem)
{
exit(OVERFLOW);
}
// 定义La和Lb所描述的线性表的最后一个元素,作为遍历的限定条件
pa_last=La.elem[La.length-1];
pb_last=Lb.elem[Lb.length-1];
// 双指针,把pa和pb指的元素中小的那一个加入到Lc所描述的线性表中
while(pa<=pa_lase && pb<=pb_lase)
{
switch{
case *pa<*pb:*(pc++)=*(pa++);break;
case *pa==*pb:*(pc++)=(*pa++);*(pc++)=(*pb++);break;
case *pa>*pb:*(pc++)=*(pb++);break;
}
}
// 若Lb所描述的线性表先结束则将La中剩下的元素加入到Lc中
while(pa<=pa_lase)
{
*(pc++)=*(pa++);
}
// 若La所描述的线性表先结束则将Lb中剩下的元素加入到Lc中
while(pb<=pb_lase)
{
*(pc++)=*(pb++);
}
}
链表线性表
定义
/*
* 定义LNode结构体其中包含此节点存储的数据和指向下一个节点的指针
* LinkList是指向链表表头的指针
* 注意:在Init中,必须将LinkList指向malloc所生成的节点,否则不能使用LinkList,因为这是一个野指针
*/
typedef struct LNode {
ElemType data ;
struct LNode * next ;
} LNode , * LinkList ;
初始化
// 链表头的LinkList所指向的表头元素是不存储数据的,其真正有用的仅为next
Status InitList_L(LinkList &L)
{
L=(LNode *)malloc(sizeof(LNode));
if(!L)
{
// 何时是return OVERFLOW何时是exit(OVERFLOW)?
return OVERFLOW;
}
L->next=NULL;
return OK;
}
销毁链表线性表
// 链表的表头也被释放掉了
Status DestroyList_L(LinkList &L)
{
p=L;
q=p->next;
// q表示p的下一个节点,每一次释放的都是p,当下一个节点是NULL时跳出循环,此时p指向的空间还未被释放
while(q!=NULL)
{
free(p);
p=q;
q=q->next;
}
// 释放p所指向的空间
free p;
return OK;
}
按元素值查找
int LocateElem_L(LinkList L,ElemType e)
{
// 等价于(*L).next
p=L->next;
// 计数
n=1;
// 若p所指不为空,且p所指向的元素的值不等于e
// 两个条件不能调换顺序,因为只有p所指不为空才存在p->data否则会发生错误
while(p!=NULL && p->data!=e)
{
p=p->next;
n++;
}
// p==NULL表示遍历链表后未发现存储着与e相等的值的节点
if(p==NULL)
{
return 0;
}
// 找到存储着与e相等的值的节点
return n;
}
按标号查找
Status GetElem_L(LinkList L,int i,ElemType &e)
{
// 表头不记录数据,也不占标号
p=L->next;
// 计数
j=1;
// 当p存在且j<i,当j==i时跳出
// 不可调换
while(p && j<i)
{
p=p->next;
j++;
}
// p存在或i等于0
if(!p||j>i)
{
return ERROR;
}
e=p->data;
return OK;
}
插入
Status ListInsert(LinkList L,int i,ElemType e)
{
// 按标号查找的过程与上一段源码一样
p=L->next;
j=1;
while(p&&j<i)
{
p=p->next;
j++;
}
if(!p||j>i)
{
return ERROR;
}
// 为新节点开辟空间
s=(LNode *)malloc(sizeof(LNode));
// 开辟失败
if(!s)
{
return OVERFLOW;
}
s->next=p->next;
p->next=s;
s->data=e;
return OK;
}
删除节点
Status ListDelete(LinkList L,int i,ElemType &e)
{
// 按标号查找第i-1个节点
p=L->next;
j=1;
while(p&&j<i-1)
{
p=p->next;
j++;
}
if(!(p->next)||j>i-1)
{
return ERROR;
}
q=p->next;
p->next=q->next;
e=q->data;
free(q);
return OK;
}
例题：
两个有序链表合并成有序链表
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)
{
pa=La->next;
pb=Lb->next;
// 将La所指向的表头作为Lc的表头
Lc=pc=La;
// 如果pa和pb均不是NULL
while(pa&&pb)
{
if(pa->data<pb->data)
{
pc->next=pa;
pc=pa;
pa=pa->next;
}
else
{
pc->next=pb;
pc=pb;
pb=pb->next;
}
}
// 跳出while循环一定是pa和pb中至少有一是NULL
if(!pa)
{
pc->next=pa;
}
if(!pb)
{
pc->next=pb;
}
free(Lb);
}
设$C={a_1 ,b_1 ,a_2 ,b_2,…,a_n ,b_n}$为一线性表,采用带头结点的hc单链表存放,编写一个算法,将其拆分为两个线性表,使得:$A={a_1 ,a_2,…,a_n },B={b_1 ,b_2,…,b_n}$
void split(LinkList hc,LinkList &ha,LinkList &hb)
{
// p指向第一个有数据的节点
LinkList p=hc->next;
// hc指向的节点作为ha指向的节点
ha=hc;
// 由于头节点只有*hc一个故hb指向的节点需要另外创建
hb=(LNode *)malloc(sizeof(LNode));
pa=ha;
pb=hb;
// 每循环一次p向后走两个节点
while(p!=NULL)
{
pa->next=p;
pa=p;
p=p->next;
if(p!=NULL)
{
pb->next=p;
pb=p;
p=p->next;
}
}
// 赋空值
pa->next=pb->next=NULL;
}
内部排序
插入排序
稳定
适用于链表
时间:
-
最好复杂度 $O(n)$ 顺序
- 针对每一个元素，首先需要跟它前一个元素进行比较(它之前的序列已经是排好序的)，如果它比前一个元素大，那么它就不需要移动。因此，如果是顺序的话，每个元素仅需要比较一次。故需要比较$n-1$次。
-
最坏复杂度 $O(n^2)$ 逆序
- 针对每一个元素，都需要和它前面所有的元素进行比较，因此第n个元素(从1开始计数)需要比较$n-1$次。故需要比较$(n \times (n-1)) / 2$。
-
平均复杂度$O(n^2)$
空间:
- 复杂度$O(1)$
若完成前 $i$ 轮循环，那么前 $i$ 个数应该是排好序的。
下列排序方法中，经过一趟排序后，所有元素都有可能不在其最终位置上的排列算法是____。
A）直接插入排序 B）冒泡排序
C）快速排序 D）简单选择排序
冒泡排序进行一次后，首元素一定是最小的。简单选择排序也是同理。快排第一趟之后确定了枢轴元素的位置。
倘若使用了折半查找其平均复杂度依然是$O(n^2)$
希尔排序
不稳定
时间复杂度:
- 最坏$O(n^2)$
- 比较次数和移动次数约为$n^{1.3}$
冒泡排序
稳定
-
最好复杂度 $O(n)$ 顺序
- 比较次数$n-1$次。
-
最坏复杂度 $O(n^2)$ 逆序
- 针对第$i$趟排序，需要进行$n-i$次关键字比较。故$(n \times (n-1)) / 2$。
-
平均复杂度$O(n^2)$
快速排序
https://www.bilibili.com/video/BV1b7411N798?p=81
不稳定
-
最坏:$O(n^2)$
-
最好:$O(nlog_2n)$
每次排序确定了枢轴元素的位置，且枢轴元素前的都小于枢轴元素，枢轴元素后的都大于枢轴元素。
简单选择排序
每次从在后边$n-i+1 $个待排序元素中选择一个关键字最小元素作为第$i$个元素。
不稳定
- 最好复杂度$O(n^2)$
- 最坏复杂度$O(n)$
- 平均$O(n^2)$
归并排序
核心:将两个有序的合并成一个有序的。
归并趟数$\lceil log_2n \rceil$
每趟$O(n)$
故复杂度为$O(nlog_2n)$
不稳定
- 希尔
- 简单选择
- 快排
期中复习
判断题
【$\surd$】字符串模式匹配KMP算法中的k=next[j],k一定小于j。
【$\surd$】链栈的TOP指针指向栈顶元素所在的位置。
【$\surd$】满二叉树中一定不存在度为1的结点。
定义
【$\surd$】哈夫曼树中一定不存在度为1的结点。
两两配对，一定没有度为1的节点。
【$\surd$】设模式串的长度为m,目标串的长度为n,当n≈m且处理只匹配一次的模式时,朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。
【$ \times$】删除只带尾指针的循环链表的首元结点与尾元结点的时间复杂度是相同的。
由于是单循环链表因此需要从尾节点开始遍历直到到达尾指针的上一个节点。
【$\surd$】一棵多叉树转换成二叉树，该二叉树的根结点一定没有右子树。
【$\surd$】KMP 算法中模式串的 next 值与主串无关。
选择题
若一棵完全二叉树有10000个结点，则叶子结点个数是【B】 A）4999 B）5000 C）5001 D）不确定
$n_0 + n_1 + n_2 = 10000$
$n_0 = n_2 + 1$
if $(n_0 + n_1 + n_2)$ % $2 == 0:$
$n_1 == 1$
else:
$n_1 == 0$ $n_0 = 10000 - n_1 -n_2 = 10000 -1 - n_0 + 1$
$n_0 = 5000$
设有一个10X10的对称矩阵A，采用压缩存储方式，以行序为主存储，$a_{1,1}$为第一 元素，其存储地址为1，每个元素占一个地址空间，则$a_{8,5}$的地址为【 B 】
A)13 B)33 C)18 D) 40
1 + 2 + 3 + 4 + 5 + 6 + 7 + 5 = 33
若深度为6的完全二叉树的第6层有3个叶结点，则该二叉树一共有【 B 】个结点。 A）33 B）34 C）35 D）不确定
前五层: $2^5 -1 = 31$
故 31 + 3 = 34
在具有n个结点以二叉链表表示的二叉树中，其非空指针域的个数为 A）n+1 B）n-1 C）2n+1 D） 不确定
根节点不占用指针，故n-1
多叉树F转换成二叉树T，则树F中的叶子结点个数应等于二叉树T中 【 B 】。
A）叶子结点个数 B）左子树为空的结点个数
C）右子树为空的结点个数 D）度为1的结点个数
若一棵二叉树中有10个度为2的结点，5个度为1的结点，则树中度为0的结点数为【 C 】个。 A）15 B）13 C）11 D）9
节点数 = 度数 + 1
度数 = 2 $\times$ 10 + 5 $\times$ 1 = 25
节点数 = 26
$n_0 = 26 - 10 -5 = 11$
设有100个元素的有序表，用折半查找法查找表中元素，查找成功时最大的比较次数为_________。 A）25 B）50 C）10 D）7
$\lfloor log_2 x \rfloor + 1$
非代码题
设循环队列存放在一段连续空间内，写出队列空和队列满的条件以及队列的长度。（3分）
#define MAXQSIZE 100
typedef struct {
QElemType *base ;
int front , rear ;
} SqQueue ;
SqQueue Q ;
初始时 Q.front = Q.rear = 0
队列为空：Q.rear=Q.front;
队列为满：(Q.rear+1)%MAXQSIZE=Q.front;
队列长度：Q.length=(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
一棵完全二叉树中有501个叶子结点，则该树中至少有多少结点？最多有多少结点？（3分）
至少结点数为：2N-1 至多结点数为：2N N为完全二叉树含有的叶子结点的个数。
$n_0 = n_2 + 1$
故$n_2 = 500$
$n_1$可能为1也可能为0
因此最多有1002，最少有1001
若一棵二叉树共有n个结点，则二叉树的深度最小为多少？最大为多少？（4分）
$\lfloor log_2n \rfloor + 1$ n
设有二个栈S1和S2共享一段存储空间V[0…n-1]。
// 初始时
S1.TOP = 0 ；
S2.TOP = n-1 ；
为了尽量利用空间，栈满的条件是什么？
S1.TOP > S2.TOP
有一份电文中共使用 6个字符：a,b,c,d,e,f，它们的出现频率依次为2，3.5，4.9，7，8.2，9.1。试构造一棵哈夫曼树(4分），并求其加权路径长度WPL(1分）。本小题合计5分。
写出下列模式串按KMP算法进行匹配时的next值。
| a | b | a | b | a | a | b | a | b |
|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 2 | 3 | 4 | 2 | 3 | 4 |
| a | a | b | a | a | b | c | a | a | b | c | a |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 |
代码题
已知带头单链表，其数据域类型为整数类型，编一算法，找出链表中所有结点数据域值的最大值，并返回。 链表的结点结构为：
typedef struct LNode {
int data ;
struct LNode * next ;
} LNode , * LinkList ;
解:
int find(LinkList &L)
{
p = L -> next;
e = p -> next;
while(p -> next)
{
p = p -> next;
if(p -> data > e)
{
e = p -> data;
}
}
return e;
}
已知一个带有表头结点的单链表（结点结构同四题），设计一个尽可能高效的算法，查找链表中倒数第k（k为正整数）个位置上的结点。若查找成功，算法输出该结点的data值，并返回1；否则，只返回0。
解:
int find(LinkList *L, int k)
{
q = NULL;
p = L -> next;
count = 1;
while(p -> next)
{
p = p -> next;
count ++;
if (count == k)
{
q = L -> next;
break;
}
}
if(count < k)
{
return 0;
}
while(p -> next)
{
p = p -> next;
q = q -> next;
}
print(q -> data);
return 1;
}
已知一棵二叉树，设计一个算法，统计树中叶子结点个数。 二叉树的存储结构为：
typedef struct BiTNode{
TElemType data;
Struct BiTNode *lchild ,*rchild;
} BiTNode , * BiTree;
解:
int Count(BiTree &T)
{
if(T == NULL)
{
return 0;
}
if(T -> lchild == NULL && T -> rchild == NULL)
{
return 1;
}
return Count(T -> lchild) + Count(T -> rchild);
}
已知一棵二叉树（存储结构同六题），设计一个算法，判断给定数据元素e在树中是否存在。
typedef struct BiTNode{
TElemType data;
Struct BiTNode *lchild ,*rchild;
} BiTNode , * BiTree;
解:
bool find(BiTree &T ,int e)
{
if(T == NULL)
{
return False;
}
if(T -> data == e)
{
return True;
}
return find(T->lchild) || find(T->rchild);
}
已知非空带头单链表L，其数据域类型为整数类型。编一算法，找出链表中所有数据域值大于给定值Value的结点个数，并返回。设链表的结点结构为：
typedef struct LNode {
int data ;
struct LNode * next ;
} LNode , * LinkList ;
LinkList L;
解:
int Count(LinkList &L, int Value)
{
count = 0;
p = L -> next;
while(p -> next)
{
if(p->data > Value)
{
count ++;
}
p = p -> next;
}
return count;
}
已知一棵非空二叉树T，以二叉链表方式存储。 存储结构为：
typedef struct BiTNode{
TElemType data;
Struct BiTNode *lchild ,*rchild;
} BiTNode , * BiTree;
BiTree T;
设计一个算法，统计树T中右孩子为空的结点个数。
解:
int Count(BiTree &T)
{
if(T == NULL)
{
return 0;
}
if(T -> rchild == NULL)
{
return 1 + Count(T->lchild);
}
else
{
return Count(T -> lcihild) + Count(T -> rchild);
}
}
已知一带头结点单链表P， 链表中结点存储结构为：
typedef struct Node{
ElemType data;
Struct Node *next;
}Node , * LinkList;
LinkList P;
设计一个语句频度尽可能少的算法，判断该链表的长度是偶数还是奇数,并返回。
解:
bool solve(LinkList &L)
{
count = 0;
p = L;
while(p->next)
{
p = p -> next;
count ++;
}
if(count % 2)
{
// 奇数
return true;
}
else
{
// 偶数
return false;
}
}
已知带头单链表La和Lb，设计一个尽量高效的算法，将两个链表合并成一个链表，即将一个链表连接到另一链表尾结点之后，使La、Lb均指向新链表头结点，删除多余的头结点。设链表的结点结构为：
typedef struct LNode {
ElemType data ;
struct LNode * next ;
} LNode , * LinkList ;
解:
LinkList merge(LinkList &La,LinkList &Lb)
{
pa = La;
pb = Lb;
while(pa -> next && pb -> next)
{
pa = pa -> next;
pb = pb -> next;
}
if(pa -> next == NULL)
{
pa -> next = Lb -> next;
free(Lb);
return La;
}
else
{
pb -> next = La -> next;
free(La);
return Lb;
}
}
设顺序表va中的数据元数递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。
typedef struct{
ElemType *elem;
int length;
int size;
}Sqlist;
status insert(Sqlist &L,ElemType e)
{
i = 0;
if(L.length + 1 > L.size)
{
return ERROR;
}
for(i = 0;i < L.length;i ++)
{
if(L.elem[i] > e)
{
break;
}
}
for(j = L.length - 1; j >= i; j--)
{
L.elem[j+1] = L.elem[j];
}
L.elem[i] = e;
return OK;
}
