数据结构期末复习

字数统计: 9.6k字   |   阅读时长≈ 41分钟

第1章 绪论

基本概念

  • 常用的数据结构包括__ 、_ 、_ 、___ 。（线性结构、树型结构、图状结构）
  • 数据项是数据结构中讨论的最小单位。数据元素可以是数据项的集合。
  • 数据元素是数据结构中讨论的基本单位。
  • 数据结构是相互之间存在某种逻辑关系的数据元素的集合。
  • 数据是计算机操作的对象的总称。
  • 存储结构是逻辑结构在存储器（内存）中的映像。
  • 数据关系的映像方法：
    1. 顺序映像，以相对的存储位置表示后继关系；
    2. 链式映像，以附加信息（指针）表示后继关系。
  • 常用的逻辑结构包括、 、_ 、_ 。
    （集合结构、线性结构、树型结构、图状结构）
    • 算法的设计取决于选定的_ ，算法的实现依赖于采用的__ 。（逻辑结构、存储结构）
    • 数据类型是一个值的集合和定义在此集合的一组操作的总称。

抽象数据类型

  • Abstract Data Type （简称ADT）的描述方法： ADT 抽象数据类型名 {
        数据对象：〈数据对象的定义〉
    数据关系：〈数据关系的定义〉
    基本操作：〈基本操作的定义〉
} ADT 抽象数据类型名
  • 抽象数据类型（ADT）的两个重要特征：
    1. 数据抽象
      用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。
    2. 数据封装
      将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。
  • 抽象数据类型是指一个数学模型以及定义在此数学模型上的一组操作，包括__ 、 和_____ 三部份。（数据对象、数据关系、基本操作）

类C语言

  • 类C语言是介于伪码和C语言之间，用来描述抽象数据类型和算法的工具。
    （1）预定义常量和类型
    #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define INFEASIBLE（不可行的） -1
    #define OVERFLOW（溢出） -2
    //Status是函数的类型，其值是函数结果状态代码
    typedef int Status
（2）数据结构的表示

用类型定义（typedef）描述，数据元素类型约定为ElemType，用户在使用时可以自行定义。

（3）算法的描述形式

函数类型 函数名（函数参数表）{
//算法说明
语句序列
}//函数名
当函数返回值为函数结果状态码时，函数定义为Status类型。
在形参表中，以&打头的参数即为引用参数。

（4）赋值语句

简单赋值 变量名 = 表达式；
串联赋值 变量名1 = 变量名2 = ┅ = 变量名k = 表达式；
成组赋值 （变量名1，┅，变量名k） = （表达式1，┅，表达式k）；
结构名1 = 结构名2；
结构名1 = （值1，┅，值k）；
变量名 [ ] =表达式；
变量名1 [ 起始下标 ┅ 终止下标] =变量名2 [ 起始下标 ┅ 终止下标] ；
交换赋值 变量名1 ←→ 变量名2
条件赋值 变量名 = 条件表达式 ？ 表达式 T：表达式 F

（5）选择语句

条件语句1 if（表达式） 语句；
条件语句2 if（表达式） 语句；
else 语句；
开关语句1 switch {
case 值1：语句序列1；break;
┅
case 值n：语句序列n；break;
default : 语句序列n+1;
}
开关语句2 switch {
case 条件1：语句序列1；break;
┅
case 条件n：语句序列n；break;
default : 语句序列n+1;
}

（6）循环语句

for语句 for（赋初值表达式序列；条件；修改表达式序列）语句；
while语句 while（条件）语句；
do-while语句 do {
语句序列；
} while（条件）；

（7）结束语句

函数结束语句 return 表达式；
return；
case结束语句 break ;
异常结束语句 exit(异常代码）；

（8）输入和输出语句

输入语句 scanf（变量1， ┅ ，变量n）；
输出语句 printf（表达式1， ┅ ，表达式n）；

（9）注释

单行注释 // 文字序列；

（10）逻辑运算

与运算 &&： 对于A&&B，当A的值为0时，不再对B求值；
或运算∥ ： 对于A∥B，当A的值为非0时，不再对B求值；

11）基本函数

求最大值 max（表达式1， ┅ ，表达式n ）；
求最小值 min（表达式1， ┅ ，表达式n ）；
求绝对值 abs（表达式）；
求不足整数值 floor（表达式）；
求进位整数值 ceil（表达式）；
判定文件结束 eof（文件变量）或 eof；
判定行结束 eoln（文件变量）或 eoln；

例题
  • 类C语言中的Status表示函数的_ ，其值是函数结果的_ 。 (类型、状态代码)

算法

  • 算法必须满足五个重要特性：有穷性，确定性，可行性，有输入，有输出。
    有穷性：不会死循环； 确定性：在每种情况下，都有唯一的执行路径； 可行性：操作都是基本的； 有输入：输入被嵌入算法中也算有输入； 有输出：略。
  • 设计算法时要考虑：正确性、可读性、健壮性、高效率和低存储量的要求。

算法的时间复杂度

举例：
x=n;y=0;
While (x>=(y+1)*(y+1))
y=y+1;
基本操作: 加法操作；时间复杂度为O(n1/2)

  • 求时间复杂度，是求最坏情况下的。
  • 算法时间取决于控制结构和原操作的综合效果。

算法的空间复杂度

算法的存储分析
  • 若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除 输入和程序之外的辅助变量所占额外空间。
  • 所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。
  • 若所需存储量依赖于特定的输入，则通常按最坏情况考虑。
    举例
1
2
3
4
5
6
7
Void bubble_sort (int a[ ],int n){
      for (i=n-1,change=TRUE; i>=1 && change; --i){
      change=FALSE;
        for (j=0; j<i; ++j)
          if (a[j]>a[j+1]) {a[j] ←→a[j+1]; change=TRUE;}
     }
  }
  • 算法的空间复杂度为O（n），即输入的a[]；
  • 算法的辅助存储空间为O（1），即i,j,change。不考虑常数。

第2章 线性表

线性表

线性表是一种最简单的线性结构，线性表的抽象数据类型定义如下：
ADT List {
数据对象：
D＝{ ai | ai ∈ElemSet, i=1,2,…,n, n≥0 }
{称 n 为线性表的表长; 称 n=0 时的线性表为空表。}
数据关系：
R1＝{ <ai-1 ,ai >|ai-1 ,ai∈D, i=2,…,n }
{设线性表为 (a1，a2, . . . ，ai，. . . ，an), 称 i 为 ai 在线性表中的位序。}

  • 将线性表置为空表，不同于销毁这个线性表。
  • 线性表的起始地址，称作线性表的基地址

表格

线性表的顺序存储结构

1
2
3
4
5
6
7
8
9
// 顺序映像的类C语言描述
#define  LIST_INIT_SIZE     100       // 线性表存储空间的初始分配量
#define  LISTINCREMENT    10      // 线性表存储空间的分配增量

typedef  struct {
  ElemType *elem;    // 存储空间基址
  int      length;        // 当前长度
  int      listsize;       // 当前分配的存储容量
} SqList;  // 称为 顺序表
1
2
3
4
5
6
7
8
// 顺序表的初始化
Status InitList_Sq( SqList &L ) { // 构造一个空的线性表 
 L.elem = (ElemType*) malloc (LIST_INIT_SIZE*sizeof (ElemType));
if (!L.elem) exit(OVERFLOW);
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
} // InitList_Sq
1
2
3
4
5
6
7
8
9
10
// 顺序表的查找
int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType))
{ // 在顺序表中查询第一个满足判定条件的数据元素，
  // 若存在，则返回它的位序，否则返回 0
  i = 1;           // i 的初值为第 1 元素的位序
  p = L.elem;      // p 的初值为第 1 元素的存储位置
  while (i <= L.length && !(*compare)(*p++, e))  ++i;
  if (i <= L.length)  return i;
                      else  return 0;
} // LocateElem_Sq

背诵malloc函数的使用

1
L.elem = (int*) malloc (LIST_INIT_SIZE * sizeof (int));

引用顺序表中的变量：

  • 第一个元素a1 L->elem[0]
  • 第 i 个元素ai L->elem[i-1]
  • 第 n 个元素an L->elem[n-1] 或者 L->elem[L->length-1] 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Status ListInsert_Sq(SqList &L, int i, ElemType e) {
  // 在顺序表L的第 i 个元素之前插入新的元素e,1≤i≤L.length+1
 if (i < 1 || i > L.length+1) return ERROR; // 插入位置不合法
 if (L.length >= L.listsize) { // 当前存储空间已满，增加分配
    newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType));
    if (!newbase) exit(OVERFLOW); // 存储分配失败
    L.elem = newbase;                // 新基址
    L.listsize += LISTINCREMENT; // 增加存储容量
 	}
  q = &(L.elem[i-1]);                 // q 指示插入位置
  for (p = &(L.elem[L.length-1]); p >= q; --p)  
       *(p+1) = *p;       // 插入位置及之后的元素右移
  *q = e;       // 插入e
  ++L.length;   // 表长增1
  return OK;
} // ListInsert_Sq

注意上面使用的是realloc(从哪里开始重新分配，分配多少);
在顺序表中，指针p所指向的元素后移一位如何用C语言程序表示？ *(p+1) = *p;

1
2
3
4
5
6
7
8
9
10
Status ListDelete_Sq(SqList &L, int i, ElemType &e) 
{
	if ((i < 1) || (i > L.length))  return ERROR;   // 删除位置不合法
	p = &(L.elem[i-1]);      // p 为被删除元素的位置
	e = *p;                             // 被删除元素的值赋给 e
	q = L.elem+L.length-1;     // 表尾元素的位置
	for (++p; p <= q; ++p)  *(p-1) = *p;  // 被删除元素之后的元素左移
		--L.length;       // 表长减1
	return OK;
} // ListDelete_Sq

指针q指向顺序表（表长为n)的表尾元素如何用C语言程序表示？ q = &(L.elem[n-1]); 或 q = L.elem+L.length-1;

单链表

为了操作方便，常在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。
enter description here

1
2
3
4
5
6
7
8
9
10
11
12
// 结点和单链表的类 C 语言描述
Typedef struct  LNode {
      ElemType      data;  // 数据域
      struct Lnode   *next;  // 指针域
   } LNode, *LinkList;  
LinkList  L；  // L 为单链表的头指针

typedef struct {  // 链表类型
   Link  head, tail;     // 分别指向头结点和最后一个结点的指针
   int   len;              // 指示链表长度
   Link  current;    // 指向当前被访问的结点的指针，初始位置指向头结点
} LinkList;

例题

画出一个有三个元素的单链表的结构。
enter description here

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 单链表的插入
void LinkListInsert(LinkList L,int i,int x)  //在线性表的第i个元素前插入新的元素x
{	LNode *p,*s;
	int n;
	
	p=L;   //p指向头结点，n为计数器
	n=0;
	while(p&&n<i-1)   //沿指针向后查找，直到p指向第i-1个元素或p为空 
	{	p=p->next;
		n++;
	}
		
	if(!p||n>i-1)   // i大于表长或者小于1则退出程序
	{	printf("第%d个元素不存在!\n",i);
		exit(1);
	}
 	
	s=(LinkList)malloc(sizeof(LNode));   //插入新的元素
	s->data=x;
	s->next=p->next;
	p->next=s;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 单链表的删除
void LinkListDelete(LinkList L,int i)   //删除线性表的第i个元素
{	
	LNode *p,*s;
	int n; 
	p=L;   //p指向头结点，n为计数器
	n=0; 
	while(p&&n<i-1)   //沿指针向后查找，直到p指向第i-1个元素或p为空
	{	p=p->next;
		n++;
	}

 	if(!p||n>i-1||p->next==NULL)   // i大于表长或者小于1则退出程序
	{	printf("第%d个元素不存在!\n",i);
		exit(1);
	} 
	
	s=p->next;     //删除第i个元素
	p->next=s->next;
	printf("删除的元素为%d\n",s->data);
	free(s);
}

记住要free掉被删除的空间。

单循环链表

单循环链表最后一个结点的指针域的指针又指回头结点的链表。
它和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。

例题：单循环链表逆置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 类c语言
Status Contray_Cirl (LinkList &L) {
    t=L;              //t指向单循环链表的头结点
    p=t->next;    //p指向单循环链表的第一个结点
    q=p->next;   //q指向单循环链表的第二个结点
	While (p!=L) {
		p->next=t;   //让p结点next域指针指向其前驱
		t=p;             //顺链向后移动指针t
		p=q;            //顺链向后移动指针p
		q=p->next; //顺链向后移动指针q
	  }
	L->next=t;    //让L的next域指针指向新链表的第一个结点
	return OK;
}  // Contray_Cirl

例题：约瑟夫环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/*约瑟夫环问题 Josephus：
编号为1，2，3，…，n的n个人按顺时针方向
围坐一圈，任选一个正整数作为报数上限m（
其中m<n）。从第一个人开始按顺时针方向自
1开始顺序报数，报到m时停止报数。报m的人
出列，从他在顺时针方向上的下一个人重新
从1报数，如此下去，直至所有人全部出列。*/

#include <bits/stdc++.h>
using namespace std;
#define ufor(i,l,r) for (int i=l;i<=r;i++)

typedef struct node{
	int data;
	struct node *next;
} Lnode, *LinkList;  //线性表 

//表尾插入结点构造指定长度的单向循环链表
void CreatList(LinkList L, int n)
{
	int i;
	Lnode *p,*s;
	
	p=L; //表尾
	ufor (i,1,n-1)
	{
		s=(LinkList) malloc(sizeof(Lnode));
		s->data = i+1;
		s->next = p->next;
		p->next = s;
		p=s;	//p往后移 
	} 
}

void printList(LinkList L, int n)
{
	Lnode *p=L;
	int i;
	ufor (i,0,n-1)
	{
		printf("%d ",p->data);
		p = p->next;
	}
}

//依次删除线性表的第m个元素
void LinkListDelete(LinkList L, int n, int m)
{
	Lnode *p,*s;
	int i,j;
	p=L;
	ufor (i,0,n-1)
	{
		j=1;
		while (j<m-1) p=p->next, j++;
	
		s = p->next; //要被删除的结点
		p->next = s->next;
		printf("%d ",s->data);
		free(s);
		p = p->next;
	}
} 

int main()
{
	LinkList L;
	int m,n;
	L=(LinkList) malloc(sizeof(Lnode));
	L->data = 1; L->next = L; //最后一个结点的指针指向头 
	
	printf("请输入初始人数:\n");
	scanf("%d",&n);
	CreatList(L,n); 
	
	printf("\n参与游戏人员编号分别为：\n");
	printList(L,n);
	printf("\n");

	printf("\n请输入报数上限：\n");
	scanf("%d",&m);
	printf("\n依次出列的人员编号为：\n");
	LinkListDelete(L,n,m);
	printf("\n");
	return 0;
}

双向链表

结构：

1
2
3
4
5
typedef struct  DuLNode {
    ElemType         data;   // 数据域
    struct DuLNode   *prior;    // 指向前驱的指针域
    struct DuLNode  *next;     // 指向后继的指针域
} DuLNode, *DuLinkList;

双向链表结构图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 双向链表的插入
void LinkListInsert(DuLinkList L,int i,int x)   //在双向链表的第i个元素前插入新的元素x
{	LNode *p,*s;
	int n; 
	
	p=L;   //p指向第一个结点，n为计数器
	n=0;
	while(p&&n<i-1)   //沿指针向后查找，直到p指向第i-1个元素或p为空 
	{	p=p->next;
		n++;
	}	
	
	if(!p||n>i-1)   // !p则i大于表长； n>i-1则i<1
	{	printf("第%d个元素不存在!\n",i);
		exit(1);
	} 
	
	s=(DuLinkList)malloc(sizeof(LNode));   //插入新的元素
	s->data=x;
	s->next=p->next;  	s->prior=p;
	p->next=s;
	if(s->next)  	s->next->prior=s;
}  //LinkListInsert
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 双向链表的删除
void LinkListInsert(DuLinkList L,int i,int x)   //在双向链表中删除第i个元素
{	LNode *p,*s;
	int n; 
	
	p=L;   //p指向第一个结点，n为计数器
	n=0;
	while(p&&n<i-1)   //沿指针向后查找，直到p指向第i-1个元素或p为空 
	{	p=p->next;
		n++;
	}	
	
	if(!p||n>i-1||p->next==NULL)   // i大于表长或者小于1则退出程序
	{	printf("第%d个元素不存在!\n",i);
		exit(1);
	}
 	
	s=p->next;   //删除第i个元素
	printf("删除的元素为%d\n",s->data);
	p->next=s->next;
	if(s->next)  	s->next->prior=p;
	free(s);
}

注意

  • if(!p||n>i-1|| p->next==NULL)
    有可能这个数要删，但是没必要/dog
  • if(s->next) s->next->prior=p;
    这也是很容易忘记的啊，得s有后继，才改后继的前驱。

第3章 栈和队列

栈

栈的抽象数据类型定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ADT Stack {
      数据对象：
         D＝{ ai | ai ∈ElemSet, i=1,2,...,n,  n≥0 }
      数据关系：
         R1＝{ <ai-1, ai >| ai-1, ai∈D, i=2,...,n }
                   约定an 端为栈顶，a1 端为栈底。
      基本操作：
      InitStack(&S)
      DestroyStack(&S)
	  StackLength(S)
      StackEmpty(s)
      GetTop(S, &e)
      ClearStack(&S)
      Push(&S, e)
      Pop(&S, &e)
     StackTravers(S, visit())
}ADT Stack
1
2
3
4
5
6
7
8
// 栈的顺序存储表示
 #define  STACK_INIT_SIZE  100; 
  #define  STACKINCREMENT   10;  
  typedef struct {
    SElemType  *base;    //基底
    SElemType  *top;  	   //栈顶
    int  stacksize;    
  } SqStack;
1
2
3
4
5
6
7
8
9
10
11
12
//顺序栈的插入
Status Push (SqStack &S, SElemType e) {
   if (S.top - S.base >= S.stacksize) {//栈满，追加存储空间
      S.base = (ElemType *) realloc ( S.base,
                (S.stacksize + STACKINCREMENT) * sizeof (ElemType));
       if (!S.base) exit (OVERFLOW); //存储分配失败
       S.top = S.base + S.stacksize;
       S.stacksize += STACKINCREMENT;
   }
   *S.top++ = e;
    return OK;
}

注意

  • 上面这段程序，主要是注意realloc和S.top的赋值
  • 顺序栈满的判断： S.top >= S.base+S.stacksize
  • 顺序栈空的判断: S.top == S.base
1
2
3
4
5
6
7
8
9
// 顺序栈的删除
Status Pop (SqStack &S, SElemType &e) {
     // 若栈不空，则删除S的栈顶元素，
     // 用e返回其值，并返回OK；
     // 否则返回ERROR
    if (S.top == S.base) return ERROR;
    e = *--S.top;
    return OK;
}

例题：用顺序栈实现数值转换

1
2
3
4
5
6
7
8
9
10
11
12
void conversion ( ) {  //数制转换的算法
    InitStack(S); 
    scanf ("%d",N);
    while (N) {
      Push(S, N % 8);
      N = N/8;
    }
    while (!StackEmpty(S)) {
      Pop(S,e);
      printf ( "%d", e );
    }
} // conversion

队列

队列的抽象数据类型定义：

1
2
3
4
5
6
7
8
9
10
11
12
 ADT Queue {
    数据对象：
      D＝{ai | ai∈ElemSet, i=1,2,...,n, n≥0}
    数据关系：
      R1＝{ <a i-1,ai > | ai-1, ai ∈D, i=2,...,n}  //约定其中a1 端为队列头， an 端为队列尾
    基本操作：
      InitQueue(&Q)                  DestroyQueue(&Q)
      QueueEmpty(Q)                QueueLength(Q)
      GetHead(Q, &e)                ClearQueue(&Q)
      EnQueue(&Q, e)               DeQueue(&Q, &e)
      QueueTravers(Q, visit())
} ADT Queue

注意

  • 对于一个队列，出队序列必然等于入队序列。
  • 栈和队列的共同点：只允许在端点处插入和删除元素。

链队列

1
2
3
4
5
6
7
8
9
10
//链队列的结构定义
typedef struct QNode { // 结点类型
   QElemType      data;
   struct QNode  *next;
} QNode, *QueuePtr;

typedef struct { // 链队列类型
    QueuePtr  front;  // 队头指针
    QueuePtr  rear;   // 队尾指针
} LinkQueue;
  • 链队列判空：Q.front == Q.rear
1
2
3
4
5
6
7
8
9
//链队列的插入
Status EnQueue (LinkQueue &Q, QElemType e) {
    // 插入元素e为Q的新的队尾元素
    p = (QueuePtr) malloc (sizeof (QNode));
    if (!p)  exit (OVERFLOW);   //存储分配失败
    p->data = e;   p->next = NULL;
    Q.rear->next = p;    Q.rear = p;
    return OK;
}
1
2
3
4
5
6
7
8
9
10
//链队列的删除
Status DeQueue (LinkQueue &Q, QElemType &e) {
  // 若队列不空，则删除Q的队头元素，
  //用 e 返回其值，并返回OK；否则返回ERROR
   if (Q.front == Q.rear)    return ERROR;
   p = Q.front->next;   e = p->data;
   Q.front->next = p->next;
   if (Q.rear == p)  Q.rear = Q.front;
   free (p);      return OK;
}

循环队列

就是，队尾的下一个是队头，的队列。相当于一个圈。
顺序队列的结构定义：

1
2
3
4
5
6
#define MAXQSIZE  100  //最大队列长度
  typedef struct {
    QElemType  *base;  // 动态分配存储空间
    int  front;     // 头指针，若队列不空，指向队列头元素
    int  rear;      // 尾指针，若队列不空，指向队列尾元素的下一个位置
  } SqQueue;
1
2
3
4
5
6
7
8
// 循环队列的插入
Status EnQueue (SqQueue &Q, ElemType e) {   // 插入元素e为Q的新的队尾元素
    if ((Q.rear+1) % MAXQSIZE == Q.front) 
        return ERROR; //队列满
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear+1) % MAXQSIZE;
    return OK;
}

注意

  • Q.rear = (Q.rear+1) % MAXQSIZE; 可以很好地执行循环队列，队尾的后移。
1
2
3
4
5
6
7
8
//循环队列的删除
Status DeQueue (SqQueue &Q, ElemType &e) {  // 若队列不空，则删除Q的队头元素，
   // 用e返回其值，并返回OK;  否则返回ERROR
    if (Q.front == Q.rear)  return ERROR;
    e = Q.base[Q.front];
    Q.front = (Q.front+1) % MAXQSIZE;
    return OK;
}

注意

  • Q.front = (Q.front+1) % MAXQSIZE; 可以很好地执行循环队列，队首的后移。
1
2
3
4
5
//求队列长度
int QueueLength (SqQueue Q) {  // 返回Q的元素个数，
   // 即队列的长度
  return (Q.rear – Q.front + MAXQSIZE) % MAXQSIZE;
}

第4章 串

串是和线性表很相似的数据结构。不过串的数据对象约束为字符集，而且串通常以串的整体作为操作对象

串的抽象数据类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ADT String {
数据对象：
    D＝{ ai |ai∈CharacterSet , i=1,2,...,n, n≥0 }
数据关系：
    R1＝{ < ai-1, ai > | ai-1, ai ∈D , i=2,...,n }
基本操作：
   StrAssign (&T, chars)        DestroyString(&S)
  StrCopy (&T, S)                 StrLength(S)
  StrCompare (S, T)             Concat (&T, S1, S2)
  StrEmpty (S)                     SubString (&Sub, S, pos, len)
  ClearString (&S)              Index (S, T, pos)
  Replace (&S, T, V)           StrInsert (&S, pos, T)
  StrDelete (&S, pos, len)
} ADT String

例题

  • 空串的长度为零
    （我猜的）期末考会涉及串的几个操作：
  1. StrAssign (&T, chars)
    初始条件：chars 是字符串常量。
    操作结果：把 chars 赋为 T 的值。
  2. StrCopy (&T, S)
    初始条件：串 S 存在。
    操作结果：由串 S 复制得串 T。
  3. StrEmpty(S)
    初始条件：串S存在。
    操作结果：若 S 为空串，则返回TRUE，否则返回 FALSE。
  4. StrCompare(S,T)
    初始条件：串 S 和 T 存在。
    操作结果：若S > T，则返回值 > 0；
    若S == T，则返回值 = 0；
    若S < T，则返回值 < 0 。
    例如：StrCompare(‘data’, ‘state’) < 0
    StrCompare('cat', 'case') > 0
  5. StrLength(S)
    初始条件：串 S 存在。
    操作结果：返回 S 的元素个数， 称为串的长度。
  6. Concat(&T,S1,S2)
    初始条件：串 S1 和 S2 存在。
    操作结果：用 T 返回由 S1 和 S2联接而成的新串。
    例如： Concat( T, ‘man’, ‘kind’)
    求得  T = 'mankind'
  7. SubString (&Sub, S, pos, len)
    初始条件：
    串 S 存在，1≤pos≤StrLength(S)，且0≤len≤StrLength(S)-pos+1。
    操作结果：
    用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串，子串为“串” 中的一个字符子序列
    例如：SubString(&Sub, ‘hello’,2,3), 得Sub=’ell’
  8. Index (S, T, pos)
    初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。
    操作结果： 若主串 S 中存在和串 T 值相同的子串, 则返回它在主串 S 中第pos个字符之后第一次出现的位置；否则函数值为0。
    （ “子串在主串中的位置”意指子串中的第一个字符在主串中的位序。）
    假设 S = ‘abcaabcaaabc’, T = ‘bca’
    Index(S, T, 1) = 2；
    Index(S, T, 3) = 6；
    Index(S, T, 8) = 0 。

    例题

    若串S1=‘ABCDEFG’,S2= 1223’,S3=‘###’,执行Substring(&Sub, S1, Strlength(S3) ,Index(S2, ‘2’,1))，
    即为求SubString(&Sub, ‘ABCDEFG’, 3, 2), 则Sub= ‘CD’。

注意

串超过限定长度的话，要截断，即舍去后面的部分

串的模式匹配-一般算法

1
2
3
4
5
6
7
8
9
10
11
int Index(SString S, SString T, int pos) {
   // 返回子串T在主串S中第pos个字符之后的位置。若不存在，
    // 则函数值为0。其中，T非空，1≤pos≤StrLength(S)。
    i = pos;   j = 1;
    while (i <= S[0] && j <= T[0]) {
      if (S[i] == T[j]) { ++i;  ++j; }   // 继续比较后继字符
      else { i = i-j+2;   j = 1; }     // 指针后退重新开始匹配
    }
   if (j > T[0])  return  i-T[0];
   else return 0;
} // Index

一般算法的最坏时间复杂度是O(StrLength(S) * StrLength(T))

串的模式匹配-KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) 算法

KMP的基本思想：
在匹配过程中，当 S[i] <> T[j] 时，已经得到的结果：
S[i-j+1..i-1] == T[1..j-1]
若已知 T[1..k-1] == T[j-k+1..j-1]
则有 S[i-k+1..i-1] == T[1..k-1]

KMP算法的时间复杂度可以达到O(m+n)

next数组的求法

next数组的定义
下面的图有点歧义。“向左向右扩展”不是说扩展的过程中，两个框保持相同；而是扩展到两个框相同的最长（且不重合）的地方。
举个例子
举个栗子

nextval数组的求法

nextval[1]肯定是0。
然后i从2开始，nextval[i]=(a[i]==a[next[i])? nextval[next[i]] : next[i];

例题

求模式串T=‘abaababcaabbabaabac’的next和nextval：
next 0112234312231234567
nextval 0102104302130102107

第5章 数组和广义表

数组的抽象数据类型：

1
2
3
4
5
6
7
8
9
10
ADT Array {
  数据对象：
      D＝{aj1,j2, ..., jn| ji =0,...,bi -1,  i=1,2,..,n, n(>0)是数组的维数，bi 是数组第i 维的长度}
  数据关系：
      R＝{R1, R2, ..., Rn}
      Ri＝{<aj1,... ji,... jn , aj1, ...ji +1, ...jn  > |  0  jk  bk -1, 1  k  n  且k  i,  0  ji  bi -2, i=2,...,n }
  基本操作:
     InitArray（）,  DestroyArray（）,
     Value（）,        Assign（）
} ADT Array

数组是什么，懂得都懂，就不赘述啦~

二维数组按行序/列序为主存放

设有个3*3的数组。

  • 按行序存放即为： a0,0 a0,1 a0,2 a1,0 a1,1 a1,2 a2,0 a2,1 a2,2
  • 按列序存放即为： a0,0 a1,0 a2,0 a0,1 a1,1 a2,1 a0,2 a1,2 a2,2

    例题

    设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( B )。
    A．BA+141            B．BA+180
C．BA+222            D．BA+225
    【解析】以列为主，则 首地址 = 基地址 + （前面有几列每行几个数 + 这一列之前放了几个数）每个元素占几个字节
    所以A[5,8]的存储首地址 = BA + （78 + 5-1）3 = BA+180

稀疏矩阵

假设 m 行 n 列的矩阵含 t 个非零元素，则称
σ = t/(m*n) 为稀疏因子，通常认为 σ<=0.05 的矩阵为稀疏矩阵。

1) 特殊矩阵
非零元在矩阵中的分布有一定规则
例如: 三角矩阵
对称矩阵
对角矩阵
2) 随机稀疏矩阵
非零元在矩阵中随机出现

三种特殊矩阵

例题

  • 有一N阶对称矩阵，矩阵元为Aij,将其下三角部分以行序为主序存放在一维数组M[0,n(n+1)/2-1]中，设矩阵最左上角矩阵元为A00，则M[31]对应的矩阵元为（D）。

    A. A2,6              B. A7,3               C. A3,7              D. A7,3和A3,7

    【解析】这题的trick在于，因为是对称的，所以如果M[31]对应A3,7 ,则必定也对应A7,3

  • 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ B ）。

    A. 13               B. 33                C. 18               D. 40

    【解析】
    i(i-1)/2+j = 87/2+5 = 33
    注意“地址”和“存储的首地址”是俩概念

  • 三维数组a[4][3][2] (下标从0开始)，假设a[0][0][0] 的地址为50，数据以行序有限方式存储，每个元素的长度为2字节，则a[2][1][1]的地址是___.(80)
    【解析】50+（2* 3* 2 +2 +1）*2 = 80

稀疏矩阵的转置

存储结构：

1
2
3
4
5
6
7
8
9
10
//三元组顺序表
 #define  MAXSIZE  12500
 typedef struct {
     int  i, j;      //该非零元的行下标和列下标
     ElemType  e;    // 该非零元的值
 } Triple;  // 三元组类型
typedef union {
     Triple  data[MAXSIZE + 1]; 
      int     mu, nu, tu; 
} TSMatrix;  // 稀疏矩阵类型

快速转置算法：

1
2
3
4
5
6
7
8
9
10
11
12
Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T){
  T.mu = M.nu;  T.nu = M.mu;  T.tu = M.tu;
  if (T.tu) {
    for (col=1; col<=M.nu; ++col)  num[col] = 0;
    for (t=1; t<=M.tu; ++t)  ++num[M.data[t].j];
    cpot[1] = 1;
    for (col=2; col<=M.nu; ++col)
       cpot[col] = cpot[col-1] + num[col-1];
    for (p=1; p<=M.tu; ++p) {转置矩阵元素}
  } // if
  return OK;
} // FastTransposeSMatrix

思想类似基数排序。上面的代码看起来没有排序，但实际上可以保证转置后三元组的有序性。
因为在转置之前，三元组保证了以行为第一关键字，列为第二关键字的有序性。
所以我们按顺序扫一遍，把它们放进堆里，列相同的，它们的行数依然有序。

广义表

广义表的抽象数据结构：

1
2
3
4
5
6
ADT Glist {
  数据对象：D＝{ei | i=1,2,..,n;  n≥0; 
                    ei∈AtomSet 或 ei∈GList,
                    AtomSet为某个数据对象  }
  数据关系：
            LR＝{<ei-1, ei >| ei-1 ,ei∈D, 2≤i≤n}

广义表的长度定义为最外层包含元素个数；
广义表的深度定义为所含括弧的重数；
（注意：“原子”的深度为 0 ，空表”的深度为 1 ）

任何一个非空广义表 LS = ( a1, a2, …, an) 均可分解为
表头 Head(LS) = a1 和
表尾 Tail(LS) = ( a2, …, an) 两部分。

例如: D = ( E, F ) = ((a, (b, c))，F )
Head( D ) = E, Tail( D ) = ( F )
Head( E ) = a, Tail( E ) = ( ( b, c) )
Head( (( b, c)) ) = ( b, c), Tail( (( b, c)) ) = ( )
Head( ( b, c) ) = b, Tail( ( b, c) ) = ( c )
Head( ( c ) ) = c, Tail( ( c ) ) = ( )

例题

（1）广义表（（a,b,c,d））的表头是（ C ），表尾是（ B ）。
A. a B.（） C.（a,b,c,d） D.（b,c,d）
（2）下面说法不正确的是( A )。
A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表
C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构
（3）当广义表中的每个元素都是原子时，广义表便成了__ 。（线性表）
（4）广义表的表尾是指除第一个元素之外， 。（其余元素组成的表）
（5）设广义表L=（（a,b,c）），则L的长度和深度分别为（ C ）。
A. 1和1 B. 1和3 C. 1和2 D. 2和3

（6）已知广义表 LS=((a,b), (c,d,e,f), g)， head 和 tail 分别是求表头和表尾，则tail( tail( head( tail(LS)))) 的运算结果是_____ 。
【解析】
tail( tail( head( tail(LS))))
= tail( tail( head( ((c,d,e,f),g) )
= tail( tail( (c,d,e,f) )
= tail( (d,e,f) )
= (e,f)
规律就是，做tail()时要补上一对括号，做head()时则不用。

广义表怎么画

广义表基本结构图

由刚刚划分表头、表位的思想，结合上图中原子、非空表的画法，我们可以知道广义表的画法是怎样的。具体看下图的典型例题。

广义表画法例题

广义表的递归操作

思想就是，把广义表分为表头表尾，分别操作，这样就可以递归了。

第6章 树和二叉树

树

树的基本术语

结点:数据元素+若干指向子树的分支。
结点的度:分支的个数。所以叶子节点的度是0。
树的度:树中所有结点的度的最大值。
叶子结点:度为零的结点。
分支结点:度大于零的结点。
结点的层次:
假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1。
树的深度： 树中叶子结点所在的最大层次。
孩子结点和双亲结点对应；兄弟结点互为兄弟；祖先结点和子孙结点对应。
一个点的祖先结点，是从它到根节点的路径上经过的除本身外所有点。
内部结点：不是叶子也不是根的结点。

有向树：
(１) 有确定的根；
(２) 树根和子树根之间为有向关系。
有序树： 子树之间存在确定的次序关系。
无序树： 子树之间不存在确定的次序关系。

森林： 是m（m≥0）棵互不相交的树的集合。
任何一棵非空树是一个二元组:
Tree = （root，F）
其中：root 被称为根结点，F 被称为子树森林。

n0表示度为0的点的个数，ni表示度为i的点的个数，n表示点的个数。

树的两个操作

LeftChild(T, cur_e) // 求当前结点的最左孩子
RightSibling(T, cur_e) // 求当前结点的右兄弟

sibling 英[ˈsɪblɪŋ] 美[ˈsɪblɪŋ]
n. 兄; 弟; 姐; 妹;

恶心例题

  • 树一定有唯一的根结点。（×，可以是空树）
  • 从J结点到结点H的路径包括：结点J、G、D、H和分支JG、GD、DH。（要在意分支分支分支）
  • 树中每个结点有唯一的双亲结点。(×，根结点除外)

二叉树

二叉树是有序树。

二叉树的性质

  • 在二叉树的第 i 层上至多有2^(i-1) 个结点 (i≥1) 。
  • 深度为 i 的二叉树上至多含 2^i -1 个结点（i≥1）。
  • 对任意二叉树，n0 = n2+1。
  • 如果在[1,n]，则
    i/2向下取整 是i的双亲结点；
    2i 是i的左孩子结点；
    2    i+1 是i的右孩子结点。

满二叉树

深度为i，含2^i -1个结点的， 挤得满满当当的二叉树是也~

完全二叉树

定义：
人话：满二叉树，按照层次遍历的逆序，非常严谨地删点。
这个过程能到达的树，都是完全二叉树。
严谨：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点相对应。

性质：
具有 n 个结点的完全二叉树的深度为 ┗（log2 n）┛ +1 。

例题

  • 在完全二叉树中，结点总数为n为999，求叶子结点数n0为多少？
    【解析】n=999, 推出完全二叉树深度为┗ log2 999┛+1=10 ；
    前9层共有结点数29-1=511，第10层有999-511=488个结点（叶子结点）；
    488个叶子结点对应第9层244个度为2的结点，第9层共有29-1=256个结点，第9层的叶子结点数为256-244=12；叶子结点数n0=488+12=500。
    这里的，第九层叶子节点是很容易被漏掉的。

  • 在完全二叉树中，结点总数为n，求叶子结点数n0为多少？（要求n0仅用n 来表示）
    n0 = n2 +1
    n = n0+ n1+ n2 = 2 n0+ n1 – 1
    n0 = ( n - n1+1)/2
    完全二叉树中n1只能为1或0
    当n1为1时，n只能是偶数，n0 = n/2
    当n1为0时，n只能是奇数，n0 =( n+1)/2
    所以： n0 =┗ (n+1)/2┛

二叉树的存储表示

顺序存储：

1
2
3
#define MAX_TREE_SIZE 100
typedef TElemType SqBiTree[MAX_TREE_SIZE];
SqBiTree bt;

就是个一维数组，点在满二叉树的下标，就是它在数组中存储的下标。root下标为0。

二叉链表存储：

1
2
3
4
typedef struct BiTNode{
	TElemType data;
	struct BiTnode *lchild, *rchild;
} BiTNode, *BiTree;

两个指针分别指向左孩子、右孩子。

二叉树的二叉链表存储表示

三叉链表存储：

1
2
3
4
5
typedef struct TriTNode {  // 结点结构
      TElemType       data;
      struct TriTNode  *lchild, *rchild;   // 左右孩子指针
      struct TriTNode  *parent;   //双亲指针 
   } TriTNode, *TriTree;

三叉链表就是：比二叉链表存储多了个双亲指针。

二叉树的三叉链表存储表示

双亲链表存储：

1
2
3
4
5
6
7
8
9
10
typedef struct BPTNode {   // 结点结构
         TElemType  data;
         int  *parent;       // 指向双亲的指针
         char  LRTag;      // 左、右孩子标志域
    } BPTNode
    typedef struct BPTree{   // 树结构
         BPTNode nodes[MAX_TREE_SIZE];
         int  num_node;        // 结点数目
         int  root;                  // 根结点的位置
    } BPTree;

双亲链表存储方式下，一个结点包含：data、双亲指针、它是左孩子还是右孩子的tag。

二叉树的双亲链表存储表示

例题

1、如果二叉树用二叉链表表示，有多少个空链域？
答：二叉树的空链域为2n0+n1=n0+n0+n1=n2+1+n0+n1=n+1
2、如果二叉树用三叉链表表示，有多少个空链域？
答：每个结点的双亲指针都不空，但根结点的双亲指针为空，所以有n+2个空链域。
3、二叉树不能用顺序结构来存储。(×)

森林

双亲链表存储

1
2
3
4
5
6
7
8
9
10
#define MAX_TREE_SIZE  100
typedef struct PTNode {  //结点结构
      Elem  data;
      int    parent;   // 双亲位置域
   } PTNode; 

typedef struct {  //树结构
     PTNode  nodes[MAX_TREE_SIZE];
     int    r, n;  // 根结点的位置和结点个数
   } PTree;

孩子链表存储

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct CTNode {  // 孩子结点结构
     int          child;
     struct CTNode *next;
   } *ChildPtr;
typedef struct {  // 双亲结点结构
     Elem    data;
     int    parent;   // 双亲位置域
     ChildPtr  firstchild; // 孩子链的头指针
   } CTBox;
typedef struct {  // 树结构
     CTBox  nodes[MAX_TREE_SIZE];
     int    n, r;        // 结点数和根结点的位置
   } CTree;

森林的孩子链表存储表示

左孩子右兄弟链表存储

1
2
3
4
typedef struct CSNode{
     Elem     data;
     struct   CSNode  *firstchild, *nextsibling;
} CSNode, *CSTree;

森林的孩子兄弟链表存储表示

由森林转换成二叉树
根据左孩子有兄弟规则；互不相交的树之间的根看作兄弟。

蓝色框住的是转换结果

也可以反过来，考把二叉树转坏成对应的森林。

二叉树的遍历

先序：根左右；
中序：左根右；
后序：左右根。

求这棵二叉树的先中后序遍历

先序： -+ab-cd/ef
中序： a+b*c-d-e/f
后序： abcd-+ef/-

中序遍历算法的非递归描述

1
2
3
4
5
6
7
8
9
10
11
12
Status InOrderTraverse(BiTree T, Status (*Visit)(TElemType e))
   {  InitStack(S); Push(S,T);   //根指针进栈
     while (!StackEmpty (S)) {
          while(GetTop(S, p) && p) Push (S,p->lchild);
          Pop(S, p);   //空指针退栈
          if (!StackEmpty(S)){  //访问节点，退后一步
               Pop (S, p); if (!Visit(p->data))   return ERROR;
               Push(S,p->rchild);
          }  //if
     }  //while
     return OK;
  }

层次遍历算法的非递归描述
层次遍历，就是按照 顺序存储二叉树 的顺序来遍历。
具体实现类似bfs，对于队列内的结点，把它们的（存在的）左儿子、右儿子依次入队。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void translevel(BinNode  *bt) 
{ 
	struct BinNode  *b;
   	q.front=0;     q.rear=0;  
  	if (!bt)   return;
    q.elem[q.rear]=bt;     q.rear=q.rear+1;    
	while (q.front < q.rear)
     { 
	 	b=q.elem[q.front];   q.front=q.front+1;
       	printf("%c  ",b->data);
        if (b->lch!=0)         { q.elem[q.rear]=b->lch;      
                                          q.rear=q.rear+1;
                                        }
        if (b->rch!=0)         { q.elem[q.rear]=b->rch;   
                                           q.rear=q.rear+1;
                                        }
     }
}

例题

若二叉树先序遍历的扩展序列为ABDECF*,其中代表空链域，则二叉树的后序遍历序列为*CFEDBA**。
【j解析】后序遍历的最后一个必然是根。然后可以找到它在中序遍历的位置，左边为它的左子树，右边为右子树。

线索二叉树

普通二叉树有lchild和rchild。
线索二叉树，某个结点如果没有左子树，则lchild指向前驱；如果没有右子树，则rchild指向后继。
线索二叉树还有ltag和rtag。如果有该子树，则该tag=0；否则为1.
画实线表示指向子树；画虚线表示指向前驱后继。
在根节点上方还有个结点，表示超级前驱/dog

线索二叉树

森林的前中后序遍历

先序：依次从左至右对森林中的每一棵树进行先根遍历
中序：依次从左至右对森林中的每一棵树进行后根遍历

例题

森林的遍历例题

赫夫曼树

（1）赫夫曼树中没有度为1的结点
（2）赫夫曼树中结点总数n为2n0 -1
画法同离散。

第7章 图

图的基本术语

  • 网：弧或变带权的图分别称作有向网和无向网。
  • 完全图：有n*(n-1)/2条边的无向图。
  • 有向完全图：有n*(n-1)条边的有向图。
  • e < nlogn 稀疏图；否则称为稠密图。
  • 有向图中定点的度=出度+入度
  • 强连通图：任意两个顶点之间都存在一条有向路径的有向图。否则，其各个强连通子图称作它的强连通分量。

第8章 动态存储管理

第9章 查找

第10章 内部排序

打赏
  • 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！
  • © 2023 glisses
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信