数据结构-期末复习重要知识点总结

第一章-绪论

第二章-线性表

3.顺序表表示

4.顺序表基本运算

5.图的核心（可能与前文有重合部分，此处加以实用化）

第一章-绪论

1.数据元素是组成数据的基本单位，是数据集合的个体。

2.数据项是有独立含义的最小单位，此时的数据元素通常称为记录。

3.数据对象是性质相同的数据元素的集合，是数据的一个子集。

4.数据结构是指相互之间存在一种或多种特定关系的数据元素集合。

5.抽象数据类型最重要的特点是数据抽象与信息隐蔽。

6.数据元素之间的相互关系具体应包括三个方面：数据的逻辑结构，数据的存储结构，数据的运算集合。

7.根据数据元素之间的不同特性，通常有下列四类基本结构：集合结构（无任何关系），线性结构（一对一），树状结构（一对多），图状结构（多对多）。

8.算法的特性：有限性，确定性，可行性，输入，输出。

9.算法设计的要求：正确性，可读性，鲁棒性，高效率和低存储量。

10.语句频度：语句在一个算法中重复执行的次数。

E.G：


int i = 1;
int k = 0;
int n = 10;
while(i <= n-1){
	k += 10 * i;  /*语句频度：n-1*/
	i++;
}


int i = 1;
int k = 0;
int n = 10;
do{
	k += 10 * i;  /*语句频度：n-1*/
	i++;
}while(i <= n-1);


int k = 0;
int n = 10;
for(int i = 1; i <= n; i++){
	for(int j = i; j<=n; j++){
		k++;    /*第一层循环 n 次
                  第二层循环 n+(n-1)+(n-2)+…+2+1 = n(n+1)/2 ,所以 k++ 执行了 n(n+1)/2 次*/
	}
}

ps：一個等差數列的和，等於其首項與末項的和，乘以項數除以2。


int n = 100;
int i = 0;
while(n >= (i+1)*(i+1)){
	i++;    	/*语句频度：sqrt(n)*/
}


int x = 0;
int i,j,k;
int n = 10;
for(i = 1; i <= n; i++) {
	for(j = 1; j <= i ; j++) {
		for(k = 1; k <= j; k++) {
			x += 1;   /*语句频度：n(n+1)(n+2)/6*/
		}
	}
}

11.时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度决定的

E.G：


//O(n)
for(int i=0;i
 
   System.out.println(result[i]);
 
}


//O(logn)
int result=1;
 
while(result
 
    result=result*2;
 
}

12.空间复杂度是该算法所耗费的存储空间的数量级

E.G：若算法执行时所需要的辅助空间是一个常数，则空间复杂度为O(1);

若需要一个一维数组，空间复杂度为O(n);

若需要一个二维数组，空间复杂度为O(n^2);

13.变量的作用域是指：包含改变量定义的最小范围。

14.一种抽象类型包括：数据对象，对象间关系，一组处理数据的操作。

15.数据结构的存储结构分为：顺序，非顺序两种

16.结构化程序设计的方法：①自顶向下，逐步求精；

②独立功能，一个入口，一个出口；

③仅用三种基本控制结构（顺序，选择，重复）。

17.函数结果三种带出方式：全程变量，函数返回值，传址参数。

第二章-线性表

1.线性表的特点:同一性（每个ai必须属于同一数据类型），有穷性（表长度就是表中元素个数），有序性（相邻元素间存在序偶关系）。

2.顺序表可以实现随机存取。

3.顺序表表示


#define MAXSIZE 100
typedef struct{
    ElemType elem[MAXSIZE];
    int last;
}SeqList;

4.顺序表基本运算

①按内容查找


int Locate(SeqList L,ElemType e){
	int i=0;
	while(i
		i++;
	}
	if(i<=L.last)return (i+1);//找到值为e的元素，返回其序号 
	else return -1;//没找到，返回空序号 
}

②按序号查找


int Serail(SeqList L,int n){
	return L.elem[n-1];
}

③插入操作


#define OK 1
#define ERROR 0
int InsList(SeqList *L,int i,ElemType e){
	int k;
	if(i<1||i>L->last+2){
		//插入位置不合法 
		return ERROR;
	}
	if(L->last>=MAXSIZE-1){
		//表已满 
		return ERROR;
	}
	for(k=L->last;k>=i-1;k--){
		L->elem[k+1]=L->elem[k];//依次后移
	}
	L->elem[i-1]=e;
	L->last++;
	return OK;
}

④删除操作


int DelList(SeqList *L,int i,ElemType *e){
	int k;
	if(i<1||i>L->last+1){
		//删除位置不合法 
		return ERROR;
	}
	*e=L->elem[i-1];
	for(k=i;k<=L->last;k++){
		L->elem[k-1]=L->elem[k];//依次前移
	}
	L->last--;
	return OK;
}

5.链表

链表中结点的逻辑顺序和物理顺序不一定相同。

由于线性表第一个元素无前驱，应设一个头指针指向第一个结点，由于线性表最后一个结点无后驱，则设为NULL；

单链表的存储结构：


typedef struct Node{
	ElemType data;
	struct Node* next;
}Node,*LinkList;

使用定义LinkList L，则L为头指针，指向表中第一个结点（对于带头结点的单链表，则指向单链表的头结点），若L==NULL（对于带头结点的单链表为L->next==NULL），表示单链表是一个空表。

6.链表的基本运算

①初始化单链表


void InitList(LinkList L){
	*L=(LinkList)malloc(sizeof(Node));//建立头结点
	(*L)->next=NULL;
}

②头插法建立单链表


void CreatFromHead(LinkList L){
	//输入字符串，$是输入结束标志 
	Node* s;
	char c;
	int flag=1;
	while(flag){
		c=getchar();
		if(c!='$'){
			s=(Node*)malloc(sizeof(Node*));
			s->data=c;
			s->next=L->next;
			L->next=s;
		}else{
			flag=0;
		}
	}
}

③尾插法建立单链表


void CreatFromTail(LinkList L){
	Node *r,*s;//r指向表尾 
	int flag=1;
	r=L;//表尾初值指向头结点 
	while(flag){
		c=getchar();
		if(c!='$'){
			s=(Node*)malloc(sizeof(Node));
			s->data=c;
			r->next=s;
			r=s;
		}else{
			flag=0;
			r->next=NULL;
		} 
	}
}

④按序号查找


Node* Get(LinkList L,int i){
	int j=0;
	Node*p=L;
	if(i<=0)return NULL;
	while(p->next!=NULL&&j
		p=p->next;
		j++;
	}
	if(i==j)return p;
	else return NULL;
}

⑤按值查找


Node* Locate(LinkList L,ElemType key){
	Node* p=L->next;
	while(p!=NULL)
	if(p->data!=key)
	p=p->next;
	else break;
	return p;
}

ps:两种查找方式时间复杂度均为O（n）

⑥求链表长度


int LinkLength(LinkList L){
	Node* p=L->next;
	int len=0;
	while(p!=NULL){
		p=p->next;
		len++;
	}
	return len;
}

⑦插入操作


void InsList(LinkList L,int i,ElemType e){
	Node *pre=L;Node *s;
	int k=0;
	if(i<=0)return ERROR;
	while(pre!=NULL&&k-1){
		pre=pre->next;
		k++;
	}
	if(pre==NULL)return ERROR//插入位置不合法
	s=(Node*)malloc(sizeof(Node));
	s->data=e;
	s->next=pre->next;
	pre->next=s;
	return OK; 
}

⑧删除操作


int DelList(LinkList L,int i,ElemType *e){
	Node* pre=L,*temp;
	int k=0;
	while(pre->next!=NULL&&k-1){
		pre=pre->next;
		k++;
	}
	if(pre->next==NULL)return ERROR;
	temp=pre->next;
	pre->next=temp->next;
	*e=temp->data;
	free(temp);
	return OK;
}

7.循环链表

循环单链表判空条件：p!=L||p->next!+L;(p：当前结点，L：头结点）

建立循环单链表：


void CreatCList(LinkList CL){
	Node*rear=CL,*s;
	char c;
	c=getchar();
	while(c!='$'){
		s=(Node*)malloc(sizeof(Node));
		s->data=c;
		rear->next=s;
		rear=s;
		c=getchar();
	}
	rear->next=CL;//让最后一个结点的next指向头结点 
	
}

8.双链表

结构定义：


typedef struct DMode{
	ElemType data;
	struct DNode* next,*prior;
}DNode,*DoubleList;

插入操作：


int DlinkIns(DoubleList L,int i,ElemType e){
	DNode *s,*p=L;
	if(i<=0)return ERROR;
	int k=0;
	while(p->next!=NULL&k-1){
		p=p->next;
		k++;
	}
	if(p->next==NULL)return ERROR;
	s=(DNode*)malloc(sizeof(DNode));
	if(s){
		s->data=e;
		s->prior=p->prior;
		p->prior->next=s;
		s->next=p;
		p->prior=s;
		return OK;
	}
	else return ERROR;
}

删除操作：


int DlinkDel(DoubleList L,int i,ElemType *e){
	DNode* p=L;
	if(i<=0)return ERROR;
	int k=0;
	while(p->next!=NULL&k-1){
		p=p->next;
		k++;
	}
	if(p->next==NULL)return ERROR;
	*e=p->data;
	p->prior->next=p->next;
	p->next->prior=p->prior;
	free(p);
	return OK;
}

9.静态链表

静态链表：用数组的方式实现的链表

优点：增、删、改不需要大量移动元素

缺点：不能随机存取，容量也是固定不变的。

10.一元多项式表示及相加

结点结构：


typedef struct Polynode{
	int coef;
	int exp;
	struct Polynode* next;
}Polynode,*PolyList;

建立一元多项式：


//尾插法建立一元多项式
PolyList PolyCreat(){
	Polynode* head,*rear,*s;
	int c,e;
	head=(Polynode*)malloc(sizeof(Polynode));
	rear=head;
	scanf("%d,%d",&c,&e);//c=0表示输入结束 
	while(c!=0){
		s=(Polynode*)malloc(sizeof(Polynode));
		s->cef=c;
		s->exp=e;
		rear->next=s;
		rear=s;
		scanf("%d,%d",&c,&e);
	}
	rear->next=NULL;
	return head;
}

多项式相加：


void PolyAdd(PolyList G,PolyList X){
	Polynode *p,*q,*tail,*temp;
	int sum=0;
	p=G->next;
	q=X->next;
	tail=G;
	while(p!=NULL&&q!=NULL){
		if(p->expexp){
			tail->next=p;
			tail=p;
			p=p->next;
		}else if(p->exp==q->exp){
			sum=p->coef+q->coef;
			if(sum!=0){
				p->coef=sum;
				tail->next=p;
				tail=p;
				p=p->next;
				temp=q;q=q->next;free(temp); 
			}
			else{
				temp=p;p=p->next;free(temp);
				temp=q;q=q->next;free(temp);
			}
		}else{
			tail->next=q;
			tail=q;
			q=q->next;
		}
	}
	if(p!=NULL)tail->next=p;
	else ail->next=q;
}

11.在带头结点的非空链表中，头结点的存储位置由头指针指示，首元素结点的存储位置由头结点的指针域指示，除首元素结点外，其他任一元素结点的存储位置由其前驱指针域指示。

12.设顺序表L中有n个数据元素，则删除该表中第i个元素需要移动n-i个元素。

第三章-限定性线性表（栈与队列）

1.顺序栈


#define Stack_Size 50
typedef struct {
	StackElementType elem[Stack_Size];
	int top;
}SeqStack;

①初始化空栈：


void InitStack(SeqStack *S){
	S->top=-1;
}

②进栈


int Push(SeqStack *S,StackElemrntType x){
	if(S->top==Stack_Size-1) return False;//栈满
	S->top++;
	S->elem[S->top]=x;
	return TRUE; 
}

③出栈


int Pop(SeqStack *S,StackElementType *x){
	if(S->top==-1)return FALSE;
	else{
		*x=S->elem[S->top];
		S->top--;
		return TRUE;
	}
}

④读栈顶元素


int GetTop(SeqStack *S,StackElementType *x){
	if(S->top==-1)return FALSE;//栈空
	else{
		*x=S->elem[S->top];
		return TRUE;
	}
}

⑤多栈共享技术


#define M 100
typedef struct {
	StackElementType Stack[M];
	StackElementType top[2];
}DqStack;

双端栈初始化


void InitStack(DqStack *S){
	S->top[0]=-1;
	S->top[1]=M;
}

双端栈进栈


int Push(DqStack *S,StackElementType x,int i){
	if(S->top[0]+1==S->top[1])return FALSE;//栈满
	 switch(i){
	 	case 0:
		 	S->top[0]++;
	 		S->Stack[S->top[0]]=x;
	 		break;
	 	case 1:
	 		S->top[1]--;
	 		S->Stack[S->top[1]]=x;
	 		break;
	 	default:return FALSE;
	 }
	 return TRUE;
}

双端栈出栈


int Pop(DqStack *S,StackElementType *x,int i){
	switch(i){
		case 0:
			if(S->top[0]==-1)return FALSE;
			*x=S->Stack[S->top[0]];
			S->top[0]--;
		case 1:
			if(S->top[1]==M)return FALSE;
			*x=S->Stack[S->top[1]];
			S->top[1]++;
		default:return FALSE;
	}
	return TRUE;
}

2.链栈


typedef struct node{
	StackElementType data;
	struct node* next;
}LinkStackNode;
typedef LinkStackNode* LinkStack;

①进栈


int Push(LinkStack top,StackElementType x){
	LinkStackNode*temp=(LinkStackNode*)malloc(sizeof(LinkStackNode));
	if(temp==NULL)return FALSE;//申请空间失败
	temp->data=x;
	temp->next=top->next;
	top->next=temp;
	return TRUE; 
}

②出栈


int Pop(LinkStack top,StackElementType *x){
	LinkStackNode*temp=top->next;
	if(temp==NULL)return FALSE;//栈空
	top->next=temp->next;
	*x=temp->data;
	free(temp);
	return TRUE; 
}

③括号匹配算法

//每读入一个括号，若是左括号，直接入栈。若读入右括号，且与栈顶左括号同类型，则栈顶左括号出栈


void BracketMatch(char *str){
	Stack S;int i;char ch;
	InitStack(&S);
	for(=0;str[i]!='\0';i++){
		switch(str[i]){
			case '(':
				case '[':
					case '{':
						Push(&S,str[i]);
						break;
			case ')':
				case ']':
					case '}':
						if(IsEmpty(&S)) return ;//右括号多余
						else{
							GetTop(&S,&ch);
							if(Match(ch,str[i]))Pop(&S,&ch);//判断两个括号是否匹配 
							else return ;//对应左右括号不匹配 
						} 
		}
	}
	if(IsEmpty(S))printf("括号匹配");
	else printf("左括号多余");
}

④无括号算术表达式处理算法

规定运算符优先级，设置两个栈分别存储运算符和运算数；若遇到运算数则进OVS栈，若遇到运算符则与栈顶运算符进行优先级比较，如果当前运算符优先级大于栈顶的，则入OPTR栈；若当前运算符优先级小于等于栈顶的，则OPTR出栈一次，得到运算符*，OVS出栈两次，得到操作数a和b，对a，b进行*运算，得到结果入OVS栈。


int ExpEvaluation(){
	InitStack(&OPTR);
	InitStack(&OVS);
	Push(&OPTR,'#');
	//输入表达式，以#为结尾
	ch=getchar();
	while(ch!='#'||GetTop(OPTR)!='#'){
		if(!In(ch,OPset)){//不是操作符，进OVS栈
			n=GetNumber(ch);
			push(&OVS,n);
			ch=getchar();
	    } 
		else{
	 		switch(Compare(ch,GetTop(OPTR))){
	 			case '>':Push(&OPTR,ch);
	 			ch=getchar();break;
	 			case '=':case '<':Pop(&OPTR,&op);
	 			Pop(&OVS,&b);
	 			Pop(&OVS,&a);
	 			v=Excute(a,op,b);//对a和b进行op运算
				Push(&OVS,v);
				break; 
		 	}
		}
	}
	v=GetTop(OVS);
	return v; 
}

3.链队列

①定义：


typedef struct Node{
	QueueElementType data;
	struct Node* next
}LinkQueueNode;
typedef struct{
	LinkQueueNode* front;
	LinkQueueNode* rear;
}LinkQueue;

②初始化


int InitQueue(LinkQueue* Q){
	Q->front=(LinkQueueNode*)malloc(sizeof(LinkQueueode));
	if(Q->front!=NULL){
		Q->rear=Q->front;
		Q->front->next=NULL;
		return TRUE;
	}
	else return FALSE;
}

③链队列入队


int EnterQueue(LinkQueue* Q,QueueElementType x){
	LinkQueueNode *NewNode;
	NewNode=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));
	if(NewNode!=NULL){
		NewNode->data=x;
		NewNode->next=NULL;
		Q->rear->next=NewNode;
		Q->rear=NewNode;
		return True;
	}
	else return FALSE;
}

④链队列出队


int DeleteQueue(LinkQueue* Q,QueueElementType *x){
	LinkQueueNode* p;
	if(Q->front==Q->rear)return FASLE;//队列为空
	p=Q->front->next;
	Q->front->next=p->next;//队头元素出队
	if(Q->rear==p)//如果队中只有一个元素，出队后成为空队
	Q->rear=Q->front;
	*x=p->data;
	free(p);
	return TRUE; 
}

4.循环队列

循环队列是队列的一种顺序表示和实现方法。

①定义


#define MAXSIZE 100
typedef struct{
	QueueElementType element[MAXSIZE];
	int front;
	int rear;
}SeqQueue;

②初始化


void InitQueue(SeqQueue *Q){
	Q->front=Q->rear=0;
}

③循环队列入队操作


int EnterQueue(SeqQueue* Q,QueueElementType x){
	if((Q->rear+1)%MAXSIZE==Q->front)//尾指针加一追上头指针,队列已满 
	return FALSE; 
	Q->element[Q->rear]=x;
	Q->rear=(Q->rear+1)%MAXSIZE;
	return TRUE;
}

④循环队列出队操作


int DeleteQueue(SeqQueue* Q,QueueElementType* x){
	if(Q->rear==Q->front)return FALSE;//队列为空
	*x=Q->element[Q->front];
	Q->front=(Q->front+1)%MAXSIZE;
	return TRUE; 
}

5.习题

①主机将要打印输出的数据依次写入缓冲区，而打印机则依次从缓冲区中取出数据，该缓冲区的逻辑结构应该是：__队列_____

②某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，元素a，b，c，d，e依次入队，则不可能的出队顺序是：___C__

A。bacde B。dbace C。dbcae D。ecbad

ps:在原序列中相对位置比它靠前的，也就是比它先入栈的，出栈顺序必须是逆序。在原序列中相对位置比它大的，也就是比它后入栈的，出栈顺序没有要求；以选项中出栈的第一个元素为基准，判断它后面的元素是否满足上述规律

③设输入序列是1，2，3，4........，n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是___n+1-i_____

④设循环队列Q[0:M-1]的队头指针和队尾指针分别为F和R，队头指针F总是指向队头元素，队尾指针R总是指向队尾元素的下一个位置，则该循环队列中的元素个数为___（R-F+M)%M______

第四章-串

1.定长顺序串

①定义


#define MAXLINE 100
typedef struct{
	char ch[MAXLINE];
	int len;
}SString;

②顺序串插入操作


int StrInsert(SString *s,int opt,SString t){
	int i;
	if(pos<0||pos>s->len)return 0;//插入位置不合法
	if(s->len+t.len<=MAXLEN){//插入后串长<=MAXLINE 
		for(i=s->len+t.len-1;i>=t.len;i--){
			s->ch[i]=s->ch[i-t.len];
		}
		for(i=0;i
			s->ch[i+pos]=t.ch[i]; 
		}
		s->len+=t.len;
	} 
	else if(pos+t.len<=MAXLINE){//插入后串长>MAXLINE，但t可以全部插入 
		for(i=MAXLINE-1;i>t.len+pos-1;i--){
			s->ch[i]=s->ch[i-t.len];
		}
		for(i=0;i
			s->ch[i+pos]=t.ch[i];
		}
		s->len=MAXLINE;
	} 
	else{//插入后串长>MAXLINE 
		for(i=0;i
			s->ch[i+pos]=t.ch[i];
		}
		s->len=MAXLINE;
	}
	return 1;
}

③顺序串删除操作


int StrDelete(SString *s,int pot,int len){
	int i;
	if(pos<0||pos>s->len-len)return 0;//删除参数不合法
	for(i=pos+len;ilen;i++){
		s->ch[i-len]=s->ch[i];
	} 
	s->len=s->len-len;
	return 1;
}

④串比较操作


int StrCompare(SString s,SString t){//若s>t则返回正数，若s
	int i;
	for(i=0;i
		if(s.ch[i]!=t.ch[i])return (s.ch[i]-t.ch[i]);
	}
	return (s.len-t.len);
}

⑤顺序串简单模式匹配操作


int StrIndex(SString s,int pot,SString t){
	//求串s从下标pot开始，子串t第一次出现的位置，不成功返回-1.
	int i,j,start;
	if(t.len==0)return 0;//空串匹配任意串
	start=pos;i=start;j=0;
	while(i
		if(s.ch[i]==t.ch[j]){
			i++;j++;
		}
		else{
			start++;
			i=start;j=0;
		}
	} 
	if(j>=t.len)return start;
	else return -1;
}

补充：KMP算法（字符串匹配）：失配后无回溯，匹配速度高


#include 
 
using namespace std;
 
const int N = 100010, M = 1000010;
 
int n, m;
int ne[N];
char s[M], p[N];
 
int main()
{
    cin >> n >> p + 1 >> m >> s + 1;
 
    for (int i = 2, j = 0; i <= n; i ++ )
    {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j ++ ;
        ne[i] = j;
    }
 
    for (int i = 1, j = 0; i <= m; i ++ )
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == n)
        {
            printf("%d ", i - n);
            j = ne[j];
        }
    }
 
    return 0;
}

2.堆串

定义：ch指示串的起始地址。


typedef struct{
	char *ch;
	int len;
}HString;

3.块链串

定义：一个链表存放一个串值，每个结点可以存放一个或多个字符。每个结点成为块。


#define BLOCK_SIZE 4;
typedef struct{
	char ch[BLOCK_SIZE];
	struct Block* next;
}Block;
typedef struct{
	Block* head;
	Block* tail;
	int len;
}BLString;

第五章-数组和广义表

1.数组地址计算

一维数组：Loc(A[i])=Loc(A[1])+(i-1)*size。

二维数组：假设以行为主存放，下标从1开始，首元素a11地址为Loc(A[1][1])，每个元素占size个存储单元

Loc(A[i][j])=Loc(A[1][1])+(n*(i-1)+j-1)*size。

三维数组：Loc(A[i][j][k])=Loc(A[1][1][1])+((i-1)*m*n+(j-1)*n+(k-1))*size。

2.特殊矩阵的压缩存储

①三角矩阵（上三角矩阵，下三角矩阵，对称矩阵）

下三角矩阵元素个数为n*（n+1）/2.

即，将下三角矩阵的非零元存储到一个大小为n*（n+1）/2的一维数组中。

下标为：Loc[i,j]=Loc[1,1]+(i*(i-1)/2+j-1):

Loc[1,1]+前i-1行非零元素个数+第i行中aij前的非零元素个数

对称矩阵满足aij=aji，可以为每一对相等的元素分配一个存储空间，即只存下三角或上三角矩阵。从而将n^2个元素压缩到n*(n+1)/2个空间中。k为压缩后的数组下标。②

方案一：存储对角线及其以下元素，按行序存储：

当i>=j时，k=i（i-1）/2+j。

当i//该元素未存储，但[j][i]单元的元素即为该元素。

方案二：存储对角线及其以上元素，按行序存储：

当i<=j时，k=j（j-1）/2+i。

当i>j时，k=i（i-1）/2+j。//该元素未存储，但[i][j]单元的元素即为该元素。

②带状矩阵

在矩阵中，所有非零元都集中在以主对角线为中心的带状区域中，最常见的是三角带状矩阵

特点：

当i=1时，j=1，2；

当1
当i=n时，j=n-1，n。

三角带状矩阵可以压缩到大小为3n-2的一维数组中。

Aij在一维数组中的地址：
Loc(A[i][j])=Loc(A[1][1])+(3*(i-1)-1+j-i+1)*size.

Loc(A[1][1])+(前i-1行非零元素个数+第i行中aij前非零元素个数）*size。

③稀疏矩阵

稀疏矩阵是指矩阵中大多数元素为0的矩阵。稀疏矩阵的三元组表表示法：

定义

#define MAXSIZE 100 typedef struct{ int row,col; ElementType e; }Triple; typedef struct{ Triple data[MAXSIZE];//非零元素的三元组表 int m,n,len;//矩阵的行数，列数，非零元个数。 }TSMatrix;

稀疏矩阵转置经典算法：

void TransMatrix(ElementType source[m][n],ElementType dest[m][n]){ for(int i=0;i for(int j=0;j dest[j][i]=source[i][j]; } } }

3.广义表

①举例：

D=（）；//空表

A=（a，（b，c））//表长为2的广义表，第一个元素是单个数据a，第二个元素是子表（b，c）

B=（A，A，D）//长度为3的广义表，前两个元素为表A，第三个元素为空表D。

C=（a，C）//长度为2递归定义的广义表，C相当于无穷表C=（a，（a，（a，（...））））

以表A为例，head（A）=a，表示A的表头是a，tail（A）=（（b，c）），表示A的表尾是

（（b，c）），广义表的表尾一定是一个表。

e.g:广义表A=（a，（b，（c））），那么Tail（Head（Tail（A）））是：（（c））

对于广义表来说，难以用顺序存储结构来表示他，通常用链式存储结构来表示。

②链表存储结构：
Ⅰ头尾链表结点结构：

表中有两类结点：单个元素结点，子表结点。

①中的A，B，C，D的头尾链存储结构

Ⅱ同层结点链存储结构：

结点均由三个域组成：

①中的A，B，C，D的同层结点链存储结构：

第六章-树与二叉树

1.树

①树的相关术语：

结点的度：一个结点的子树个数

叶结点：度为0的结点，即无后继的结点，也称终端节点。

分支结点：度不为0的结点。

结点的层次：从根结点开始，根结点的层次为1，根的直接后继层次为2，以此类推。

树的度：树中所有结点的度的最大值。

树的高度：树中所有结点的层次的最大值。

森林：将一棵非空树的根结点删去，树就变成一个森林；反之，给森林增加一个统一的根结点，森林就变成一棵树。

同构：如果树A通过若干次左右子树替换得到树B，就称树A和树B同构。

2.二叉树

任何树都可以转化为二叉树进行处理。

①二叉树的性质：

Ⅰ.在二叉树第i层至多有2^（i-1）个结点（i>=1）;

Ⅱ.深度为k的二叉树之多有2^k-1个结点。

Ⅲ.对于任一二叉树，叶子结点数为n0，度数为2的结点数为n2，则n0=n2+1.

Ⅳ.具有n个结点的完全二叉树深度为[logn]+1.

Ⅴ.对于有n个结点的顺序存储二叉树，结点从1开始编号，对于任意编号为i的结点有：

若i=1，则是根节点，无双亲结点，若i>1，双亲结点的序号是[i/2]；

左孩子编号是2*i，右孩子编号是2*i+1。

Ⅵ.n个结点的二叉树，共2n个指针域，其中n-1个非空指针域，n+1个空指针域。

②二叉树顺序存储结构

可以将二叉树的数据元素逐层放入数组中。对于非完全二叉树来说，必须用“虚结点”将其补成完全二叉树。这个行为就会造成一定浪费。

3.二叉树链式存储结构

设计每个结点至少包括三个域：数据域，左孩子域，右孩子域。

①结点结构定义：

typedef struct{ DataType data; struct Node* LChild; struct Node* RChild; }BiTree,*BiTree;

有时，为了便于找到双亲结点，可以增加一个Parent域

4.二叉树的遍历

①先序遍历

void PreOrder(BiTree root){ if(root!=NULL){ Visit(root->data); PreOrder(root->LChild); PreOrder(root->RChild) } }

②中序遍历

void InOrder(BiTree root){ if(root!=NULL){ InOrder(root->LChild); Visit(root->data); InOrder(root->RChild); } }

③后序遍历

void PostOrder(BiTree root){ if(root!=NULL){ PostOrder(root->LChild); PostOrder(root->RChild); Visit(root->data); } }

这些二叉树递归遍历算法的时间复杂度为O（n）。

④先序遍历输出二叉树中的叶子结点

void PreOrder(BiTree root){ if(root!=NULL){ if(root->LChild!=NULL&&root->RChild!=NULL)printf(root->data); PreOrder(root->LChild); PreOrder(root->RChild); } }

⑤用扩展先序遍历创建二叉链表

void CreatBiTree(BiTree* root){ char ch; ch=getchar(); if(ch=='.')*root=NULL; else{ *root=(BiTree)malloc(sizeof(BiTree)); (*root)->data=ch; CreatBiTree(&((*root)->LChild)); CreatBiTree(&((*root)->RChild)); } }

⑥后序遍历求二叉树高度

int PostOrder(BiTree root){ int hl,hr,max; if(root!=NULL){ hl=PostOrder(root->LChild); hr=PostOrder(root->RChild); max=hl>hr?hl:hr; return max+1 }else return 0; }

⑦中序遍历非递归（调用栈操作的函数）

void InOrder(BiTree root){ InitStack(&S); p=root; while(p!=NULL||!IsEmpty(S)){ if(p!=NULL){ Push(&S,p); p=p->LChild; } else{ Pop(&S,&p);Visit(p->data); p=p->RChild; } } }

⑧中序遍历非递归（直接实现栈操作）

void InOrder(BiTree root){ //data[m]表示栈，top表示栈顶指针 top=0; p=root; do{ while(p!=NULL){ if(top>m)return ; top++; data[top]=p; p=p->LChild; } if(top!=0){ p=data[top]; top--; Visit(p->data); p=p->RChild; } }while(p!=NULL||top!=0) }

⑨后序遍历非递归（调用栈的操作函数）

void PostOrder(BiTree root){ BiTNode* p,*q; Stack S; q=NULL; p=root; InitStack(&S); while(p!=NULL||!IsEmpty(S)){ if(p!=NULL){ Push(&S,p); p=p->LChild; } else{ GetTop(&S,&p); if((p->RChild==NULL)||(p->RChild==q)){ visit(p->data); q=p; Pop(&S,&p); p=UNLL; } else{ p=p->RChld; } } } }

5.线索二叉树

①基本概念

充分利用二叉链表中的空链域，将遍历过程中的结点前驱，后继的信息保存下来。可以利用空闲的n+1个空链域来存放：若结点有左子树，则LChild指向其左孩子，否则LChild指向其前驱结点；若结点有右子树，则RChild指向其右孩子，否则RChild指向其后继结点。为了区分孩子结点和前驱后继结点，为结点结构增加两个标志域：Ltag=0时，LChild指向左孩子，Ltag=1时，LChild指向其前驱结点；Rtag=0时，RChild指向其右孩子，Rtag=1时，RChild指向其后继结点。在这种存储结构中，指向前驱和后继结点的指针称为线索。

二叉树的线索化实质上是将二叉链表中的空指针域填上相应节点的前驱和后继。因此线索化的过程即在遍历的过程中修改空指针域的过程。对于不同的遍历次序可以得到不同的线索二叉树。

②建立中序线索树

void Inthread(BiTree root){ BiTree pre=NULL; if(root!=NULL){ Inthread(root->LChild); if(root->LChild==NULL){ root->Ltag=1; root->LChild=pre;//置前驱线索 } if(pre!=NULL&&pre->RChild==NULL){ pre->Rtag=1; pre->RChild=root;//置后继线索 } pre=root; Inthread(root->RChild); } }

③在中序线索树中找结点前驱

BiTNode* InPre(BiTNode* p){ if(p->Ltag==1)pre=p->LChild; else{//在左子树中找最右下端结点 for(q=p->LChild;q->Rtag==0;q=q->RChild) pre=q; } return pre; }

④在中序线索树中找结点后继

BiTNode* InNext(BiTNode* p){ if(p->Rtag==1)Next=p->RChild; else{//在p的右子树中查找最左下端结点 for(q=p->RChild;q->Ltag==0;q=q->LChild) Next=q; } return Next; }

⑤在中序线索树上求中序遍历的第一个结点

BiTNode* InFirst(BiTree root){ BiTNode* p=root; if(!p)return NULL; while(p->Ltag==0)p=p->LChild; return p; }

⑥遍历中序线索树

void InOrder(BiTree root){ BiTNode* p=InFirst(root); while(p){ visit(p); p=InNext(p); } }

⑦已知两种遍历序列，求二叉树：

已知后序和中序：后序的最后一个结点就是根结点，中序的根结点左边是左子树，右边是右子树，然后递归进行前面的操作即可。

已知前序和中序：前序的第一个结点就是根结点，其余同上。

已知后序和前序：无法求得唯一二叉树。

6.树，森林，二叉树的关系

①将树转换成二叉树：

树中所有兄弟之间加一条连线；对树中每个结点，只保留其与第一个孩子之前的连线，删去其与其他孩子的连线。

②将森林转换成二叉树：

先将森林中的每棵树转换成相应的二叉树

第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子。

③二叉树还原为树或森林：

若某结点是其双亲的左孩子，则把该结点的右孩子，右孩子的右孩子……都与该结点的双亲结点用线连起来；删掉二叉树中所有双亲结点与右孩子结点的连线；

7.哈夫曼树

①基本概念

路径：从根结点到该结点的分支序列。

路径长度：是指根结点到该结点所经过的分支数目。

结点的权：人们常常给树的结点赋予一个具有某种实际意义的实数。

结点的带权路径长度：从根结点到某一结点的路径长度与该结点的权的乘积。

树的带权路径长度：树中从根到所有叶子结点的各个带权路径长度之和，记为WPL= $\sum$ Wi*Li。

②构造哈夫曼树

哈夫曼树是由n个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树，又称最优二叉树

用静态三叉链表实现哈夫曼树的类型定义

#define N 20 #define M 2*N-1 typedef struct{ int weight;//结点的权值 int parent;//双亲下标 int LChild;// int RChild; }HTNode,HuffmanTree[M+1]; //Huffman树是一个结构数组，0号单元不用

创建哈夫曼树

void CreatHuffmanTree(HuffmanTree ht,int w[],int n){ for(int i=1;i<=n;i++){ ht[i]={w[i],0,0,0}; //1~n号单元存放叶子结点 } int m=2*n-1; for(int i=n+1;i<=m;i++){ ht[i]={0,0,0,0};//n+1~m号单元存放非叶子结点 } //------------------------初始化完成 for(int i=n+1;i<=m;i++){ select(ht,i-1,&s1,&s2);//在ht[1]~ht[i-1]选择两个parent为0且weight最小的结点，序号赋值给s1,s2. ht[i].weight=ht[s1].weight+ht[s2].weight; ht[s1].parent=i; ht[s2].parent=i; ht[i].LChild=s1; ht[i].RChild=s2; } }

哈夫曼编码：

对于一棵具有n个叶子的哈夫曼树，若对树中每个左分支赋予0，右分支赋予1，则从根到每个叶子的通路上，各分支的赋值分别构成一个二进制串，该二进制串就称为哈夫曼编码。

相关特性：

哈夫曼编码是前缀编码。哈夫曼编码是最优前缀编码。

求哈夫曼树的哈夫曼编码：

void CHuffmanTree(HuffmanTree ht,HuffmanCode hc,int n){ //从叶子结点到根，逆向求哈夫曼编码 char *cd; cd=(char*)malloc(n*sizeof(char)); cd[n-1]='\0';//从右向左存放编码，先放结束符 for(int i=1;i<=n;i++){ start=n-1;//起始指针 c=i;p=ht[i].parent; while(p!=0){ --start; if(ht[p].LChild==c)cd[start]='0';//左分支 else cd[start]='1';//右分支 c=p;p=ht[p].parent;//向上倒推 } hc[i]=(char*)malloc((n-start)*sizeof(char)); strcpy(hc[i],&cd[start]);//把编码复制到hc[i]中 } free(cd); }

8.习题

①已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，nk个度为k的结点，则该树中有多少叶子结点？

答：设该树中的叶子数为n0个.该树中的总结点数为n个；

则有 n=n0+n1+n2+…+nK (1)

        n-1=0×n0+1×n1+2×n2+…+K×nK (2)

联立(1)(2)方程组可得叶子数为：n0=1+0×n1+1×n2+2×n3+……+(K-1)×nK

②已知二叉树有50个叶子结点，则该二叉树总结点数至少多少个？

答：设n0表示叶子结点数，n2表示度为2的结点数；

则n0 = n2+1 所以n2= n0 -1=49，当二叉树中没有度为1的结点时，总结点数 n=n 0+ n2=99

③计算：

Ⅰ.n个结点的k叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的child域有多少个？

答：总的child域为：n*k

分支总数：n-1

所以非空child域是：n*k-（n-1）=n*（k-1）+1。

Ⅱ.一棵完全二叉树共有520个结点，该完全二叉树有多少个叶子结点，度为1的结点，度为2的结点？

答：因为520是偶数，所以n1=1.

由n0=n2+1，可得n0=260，n2=259.

ps：

满二叉树的所有节点的度都是2或者0，没有度为1的节点。

完全二叉树，可以看做是满二叉树在最后一层从右往左砍掉一些节点。

如果从满二叉树中在最后一层自左向右砍掉的节点数是偶数，那么该完全二叉树中度为1的节点数就是0。

如果砍掉的节点数是奇数，那么该完全二叉树中就有且仅有一个节点的度为1.

Ⅲ.已知完全二叉树第7层有10个结点，则整个二叉树的结点数为多少个？

答：第六层是满的，前6层结点数：2^6-1=63.

总数：63+10=73.

Ⅳ.不同的线索化二叉树张，空余指针个数分别是多少？

答：第一个结点没有前驱,则其左指针为空,最后一个结点没有后继,则其右指针为空.
因此在不同的线索化二叉树中,空余指针个数应该是两个.

④已知一棵二叉树按顺序方式存储在数组A[1..n]中，设计算法求出下标分别为i和j的两个结点的最近的公共结点祖先的值。

void Ancestor(ElemType A[],int n,int i,int j){ while(i!=j){ if(i>j)i/=2; else j/=2; } printf("最近的公共祖先的下标是：%d，值是：%d",i,A[i]); }

⑤假设采取二叉链表的方式存储二叉树，root指向根结点，p所指向结点和q所指向结点是二叉树中的两个结点，编写一个函数计算他们最近的公共祖先。

答：采用非递归后序遍历，假设p在q左边。当后序遍历访问到p时，此时St中所有结点均为结点p的祖先，将其复制到anor中，继续后序遍历访问到q时，情况同p，将其与anor中结点依次比较，找出最近的共同祖先。

int ancestor(BTNode* root,BTNode* p,BTNode* q){ BTNode* St[MAXSIZE]; BTNode* temp; ElemType anor[MAXSIZE]; int i,flag,top=-1; do{ while(root){//将t的所有左结点入栈 top++; St[top]=root; root=root->LChild; } temp=NULL;//p指向前一个已访问过的结点 flag=1; while(top!=-1&&flag){ root=St[top];// if(t->RChild==temp){ if(root==p){ for(i=0;i<=top;i++) anor[i]=St[i]->data; top--; temp=root; } else if(root==q){ i=0; while(anor[i]==St[i]->data) i++; cout<<"最近公共祖先:"<-1]< return i; } else{ top--; temp=root; } } else{ root=root->RChild; flag=0; } } }while(top!=-1); return 0; }

⑥编写递归算法：对于二叉树中每一个元素为x的结点，删去以它为根的子树，释放相应空间。

void Del_x(BiTree T,int x){ if(T->data==x)Del_sub(T); else{ if(T->LChild)Del_x(T->LChild); if(T->RChild)Del_x(T->RChild); } } void Del_sub(BiTree T){ if(T->LChild)Del_sub(T->LChild); if(T->RChild)Del_sub(T->RChild); free(T); }

⑦写算法判别一棵二叉树是否为一棵正则二叉树（二叉树中不存在子树个数为1的结点）

bool IsNormalTree(BitTree *T) { if(!T) return true; if(!T->LChild&&!T->RChild) return true; else if(T->LChild&&T->RChild) { if(IsNormalTree(bt->lchild)&&IsNormalTree(bt->rchild)) return true; else return false; } else return false; }

⑧计算二叉树的最大宽度（二叉树所有层中结点个数的最大值）

int MWidth(BiTree T) { if(T==NULL) return 0; Queue Q; int temp = 0, last = 0, max = 0; BiTree t = T; InitQueue(&Q); Push(&Q, &t); while (Q.front <= last){ OutQueue(&Q, &t); temp++; if (t->LChild != NULL){ Push(&Q, &t->LChild); } if (t->RChild != NULL){ Push(&Q, &t->RChild); } if (Q.front > last){ //一层结点全部遍历完成，开始判断最大宽度 last = Q.rear-1; max = max > temp ? max : temp; temp = 0; } } return max; }

⑨二叉链表方式存储二叉树，编写算法将左右子树进行交换。

void exchange(BiTree T){ BiNode *r,*p,*stack[MAXSIZE]; int top=0; stack[top++]=T; while(top>0){ p=stack[--top]; if(p){ r=p->LChild; p->LChild=p->RChild; p->RChild=r; stack[top++]=p->LChild; stack[top++]=p->RChild; } } }

第七章-图

1.基本术语

图是一种网状数据结构，其形式化定义：G=（V,E）。

其中G表示图，V表示顶点集合，E表示边集合。

完全图：有n（n-1）/2条边的无向图，有n（n-1）条边的有向图。

对于有很少条边的图称为稀疏图，反之称为稠密图。

邻接点：对于无向图G=（V,E），如果边（v1，v2）∈E，称v1，v2相邻接。对于有向图G=（V,A），如果边（v1，v2）∈A，称v1邻接到v2 。

顶点的度是指和v向邻接的边的数目，记作TD（v），在有向图中度有出度和入度，记作TD（v）=ID（v）+OD（v）。

图的边上往往与具有一定实际意义的数有关，即权；带权的图称为网。

路径：无向图的路径是一个顶点序列，如果是有向图，则路径也是有向的，路径长度是指路径上经过边的个数。在一个路径中，若其第一个顶点和最后一个顶点是相同的，就称为回路或环。

连通图：在无向图中，若从Vi到Vj有路径相通，就称Vi和Vj是连通的。如果对于图中的任意两顶点都是连通的，则称该无向图是连通图。无向图的极大连通子图称为该无向图的连通分量。在有向图中，若对于每对顶点都有Vi到Vj且Vj到Vi有路径相通，则称该有向图是强连通图。有向图的极大连通子图称为有向图的强连通分量。

2.存储结构

1.邻接矩阵表示法

也称数组表示法，用二维数组来表示顶点之间的关系

#define INFINITY 32768//无穷大 #define MAX_VERTAX_NUM 20 typedef struct GNode* MGraph; struct GNode{ int Nv; int Ne; WeightType G[MAX_VERTAX_NUM][MAX_VERTAX_NUM]; DataType Data[MAX_VERTAX_NUM]; }; typedef int Vertax;//顶点下标表示顶点

特点：①存储空间：对于无向图来说，一个具有n个顶点的无向图，需要n（n-1）/2个存储空间（可以采用对称矩阵压缩存储法），对于有向图，需要n^2个存储空间。

②便于运算：便于判定两顶点之间是否有边相连。还便于求各个顶点的度：

对于无向图而言，其邻接矩阵第i行元素之和就是图中第i个顶点的度。

对于有向图而言，其邻接矩阵的第i行元素之和就是图中第i个顶点的出度，第i列元素之和就是第i个顶点的入度。

采用邻接矩阵法创建图：

//初始化一个有VertaxNum个顶点但没有边的图 MGraph CreatGraph(int VertaxNum){ Vertax V,M; MGraph Graph; Graph=(MGraph)malloc(sizeof(GNode)); Graph->Nv=VertaxNum; Graph->Ne=0; for(V=0;VNv;V++){ for(M=0;MNv;M++){ Graph->G[V][M]=0; } } return Graph; } //向图中插入边； typedef struct ENode* Edge; struct ENode{ Vertax V1,V2;//有向边 WeightType weight;//权重 }; void InsertEgde(MGraph Graph,Edge E){ Graph->G[E->V1][E->V2]=E->weight; //若是无向图，还须 Graph->G[E->V2][E->V1]=E->weight; } //建立用邻接矩阵表示的图 MGraph BuildGraph(){ MGraph Graph; Vertax V; int Nv; scanf("%d",&Nv); Graph=CreatGraph(Nv); scanf("%d",&(Graph->Ne)); if(Graph->Ne!=0){ E=(Edge)malloc(sizeof(ENode)); for(int i=0;i scanf("%d %d %d",&E->V1,&E->V2,&E->weight); Insert(Graph,E); } } //如果顶点有数据 for(int i=0;i scanf("%d",&(Graph->Data[V])); } return Graph; } //简便表示 int G[MAX][MAX],Nv,Ne; void BuildGraph(){ int V1,V2,W; for(int i=0;i for(int j=0;j G[i][j]=0; } } scanf("%d",&Ne); for(int i=0;i scanf("%d %d %d",&V1,&V2,&W); G[V1][V2]=W; G[V2][V1]=W; } }

2.邻接表表示法

//邻接表表示图 typedef struct AdjVNode* PreToAdjVNode; //邻接表的结点结构 struct AdjVNode{ Vertax AdjV;//邻接点下标 WeightType weight;//边权重 PtrToAdjVNode next; }; //邻接表结构：指针数组 typedef struct Vnode{ PtrToAdjVNode FristEdge;//指向第一条边 DataType Data;//存顶点的数据 }AdjList[MAX_VERTAX_NUM]; //LGraph结构 typedef struct GNode* LGraph; struct GNode{ int Nv,Ne;//顶点数，边数 AdjList G;//邻接表 };

特点：

①对于稀疏图，存储空间按比邻接矩阵表示法节省得多。

②无向图中，顶点i的度就是第i个单链表上的结点数。

有向图中，第i个单链表上的结点数是顶点i的出度，要求顶点i的出度就必须遍历整个邻接表，求出度并不方便，一种解决方法是逆邻接表法。

采用邻接表法创建图：

//初始化一个有Vertax个顶点但没有边的图 LGraph CreatLGraph(int VertaxNum){ Vertax V,M; LGraph Graph=(LGraph)malloc(sizeof(GNode)); Graph->Nv=VertaxNum; Graph->Ne=0; for(int i=0;iNv;i++) Graph->G[V].FristEdge=NULL; return Graph; } //向LGraph插入一条边 void InsertEdge(LGraph Graph,Egde E){ PtrToAdjLNode NewNode; //为V2建立新的邻接点 NewNode=(PtrToAdjNode)malloc(sizeof(struct AdjNode)); NewNode->AdjV=E->V2; NewNode->Weight=E->Weight; //将V2插入V1的表头 NewNode->next=Graph->G[E->V1].FristEdge; Graph->G[E->V1].FristEdge=NewNode; //若是无向图，还要插入边 NewNode=(PtrToAdjLNode)malloc(sizeof(struct AdjLNode)); NewNode->AdjV=E->V1; NewNode->Weight=E->Weight; NewNode->next=Graph->G[E->V2].FristEdge; Graph->G[E->V2].FristEdge=NewNode; }

3.图的遍历

1.深度优先搜索（DFS）

基本思想：①从图中某个顶点V0出发，先访问V0。

②找出刚访问过的顶点的第一个未被访问的邻接点，然后访问该顶点；以该顶点为新顶点，重复此步骤，直到刚访问过的顶点没有未被访问的邻接点为止。

③返回前一个访问过的且仍有未被访问的邻接点的顶点，找出该顶点的下一个未被访问的邻接点，访问该顶点，然后执行步骤②。

#define False 0 #define True 1 int visited[MAX_VERTAX_NUM];//访问标志数组 void Traverse(MGraph G){ for(v=0;v for(v=0;vif(!visited[v])DFS(G,v); } void DFS(MGraph G,Vertax v){ //访问顶点并设置访问标志为已访问 visit(v); visited[v]=True; w=FristAdjVertax(G,v); while(w!=-1){ //邻接点存在 if(!visited[w])DFS(G,w); w=NextAdjVertax(G,v,w); //找下一个邻接点 } }

对于FirstAdjVertax和NextAdjVertax，因为图的存储结构不同，对应操作的实现方法也不同；

①用邻接矩阵的DFS

void DFS(MGraph Graph,Vertax v){ visit(v); visited[v]=True; for(i=0;i if(!visited[i]&&Graph.G[v][i]==1){ DFS(Graph,i); } } }

②用邻接表的DFS

void DFS(LGraph Graph,Vertax v){ visit(v); visited[v]=True; p=Graph.G[v].FristEdge; while(p!=NULL){ if(!visited[p->AdjV]) DFS(Graph,p->AdjV); p=p->next; } }

非递归形式的DFS

//非递归形式的DFS void DFS(Graph g,Vertax v){ InitStack(&S); Push(&S,v); while(!IsEmpty(S)){ Pop(&S,&v); if(!visited[v]){ visit(v); visited[v]=True; w=FirstAdjVertax(g,v); while(w!=-1){ if(visited[w])Push(&S,w); w=NextAdjVertax(g,v,w); } } } }

DFS的时间复杂度是O（n+e），e是边数。

2.广度优先遍历（BFS）

基本思想：①从图中某个顶点v0出发，首先访问v0；

②依次访问v0的各个未被访问的邻接点；

③分别从这些邻接点出发，依次访问他们的各个未被访问的邻接点。重复③直到所有结点均没有已被访问的邻接点为止。

若此时还有顶点未被访问，选一个作为起始点，重复上述过程，直到所有顶点均被访问过为止。

4.图的应用

1.图的连通性问题：

对图进行遍历时，对于连通图，无论是广度优先搜索还是深度优先搜索，仅需要调用一次搜索过程。即从任一顶点出发，便可遍历图中的所有顶点；对于非连通图，则需要多次调用搜索过程，而每次调用得到的顶点访问序列恰为各连通分量中的顶点集。

所以，可以通过图的遍历来判断一个图是否连通，如果在遍历过程中，不止一次调用搜索过程，则说明该图就是一个非连通图，调用搜索过程几次，就表明该图有几个连通分量。

2.图中两个顶点之间的简单路径

可以将此问题看作有条件的图的遍历。

深度优先找出从顶点u到v的简单路径：

void one_path(Graph *G,int u,int v){ int *pre=(int *)malloc(sizeof(int)); for(int i=0;iNv;i++)pre[i]=-1; pre[u]=-2;//将pre[u]置-2表示初始顶点已被访问，且u无前驱。 DFS_path(G,u,v); free(pre); } int DFS_path(Graph *G,int u,int v){ for(int j=firstadj(G,u);j>=0;j=nextadj(G,u,j)){ if(pre[j]==-1){ pre[j]=u; if(j==v){ print_path(pre,v);//从v开始，沿着pre中保存的前驱指针输出路径。 return 1; } else if(DFS_path(G,j,v))return 1; } } return 0; }

3.最小生成树

一个连通图的生成树是指一个极小连通子图，含有图中全部顶点，但只有足以构成一棵树的n-1条边。

在一个连通网的所有生成树中，各边代价之和最小的那棵生成树称为最小生成树（MST）。

MST有重要性质：设N=（V,E）是一个连通网，若（u，v）是一条具有最小权值的边，则存在一棵包含（u，v）的最小生成树。

下面介绍两种算法：

Ⅰ普里姆算法：

假设N=（V,E）是连通网，TE是最小生成树的边的集合。

①初始TE=∅；

②在u∈U（U={u0|u0∈V}），v∈V-U的边中选一条代价最小的边（u0，v0）并入集合TE，同时将v0并入U。

③重复②，直到U=V为止。

此时TE中必含有n-1条边，则T=（V,TE）为N的最小生成树。

可以看出，普里姆算法逐步增加U中的顶点，可称为“加点法”。

PS：选择最小边时，条件是一点属于U而另一点不属于U，即保证加点不构成回。

struct { int adjvex;//最小边在U中的顶点 int lowcost;//最小边权值 }closedge[MAX_VERTAX_NUM]; void MiniSpanTree_Prim(MGraph Graph,int u){ closedge[u].lowcost=0;//初始化U={u} for(int i=0;i if(i!=u){ //对V-U中的顶点i初始化closedge{i}; closedge[i].adjvex=u; closedge[i].lowcost=Graph.G[u][i]; } } for(int e=1;e v=Minium(closedge);//closedge[v]中存有最小边（u，v）的信息。 u=closedge[v].adjvex; printf(u,v);//输出生成树当前最小边（u，v）。 closedge[v].lowcost=0; //将v纳入U for(int i=0;i//更新closedge[i]. if(Graph.G[v][i] closedge[i].lowcost=Graph.G[v][i]; closedge[i].adjvex=v; } } } }

时间复杂度（O^2）.

Ⅱ克鲁斯卡尔算法：

假设N=（V,E）是连通网，将N中的边按权值从小到大排序。

①将n个顶点看成n个集合；

②按权值由小到大选择边，所选边应满足顶点不在同一顶点集合内，将该边放到生成树集合中，同时将该边的两个顶点所在的顶点集合合并。

③重复②直到所有顶点都在一个集合内。

可以看出，克鲁斯卡尔算法可称为“加边法”。

4.有向无环图

Ⅰ拓扑排序

用顶点表示活动，用边表示活动间的优先关系的有向无环图，称为顶点表示活动的网，AOV-网。

AOV-网的特性：

①在AOV-网中不能存在回路，否则回路中的活动就会互为前驱，从而无法执行。

②AOV-网的拓扑序列不是唯一的。

由于有向图的存储形式不同，拓扑排序算法的实现也不同。

壹.基于邻接矩阵：

A是有向图G的邻接矩阵，则有：

①找到G中的无前驱结点————在A中找到值全为0的列；

②删除以i为起点的所有边————将矩阵中i对应的行全部置为0.

5.图的核心（可能与前文有重合部分，此处加以实用化）

图这部分的算法，重点在于先掌握手动模拟，在此基础上对算法进行理解。

①BFS

要点：Ⅰ找到与一个顶点相邻的顶点；

Ⅱ标记哪些顶点被访问过（辅助数组）；

Ⅲ需要一个辅助队列（与层序遍历类似）；

Ⅳ图的基本操作：

FirstAdjVex（G，v）：求图G中顶点v的第一个邻接点，若存在，返回顶点号，若v不存在邻接点，返回-1。

NextAdjVex（G，v，w）：求图G中除v外的下一个邻接点w，若存在，返回顶点号，反之返回-1。

代码：

void BFS(Graph G,int v){ visit(v);//访问初始点 visited[v]=1; Enqueue(Q,v); while(!isEmpty(Q)){ Dequeue(Q,v); for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)){ if(visit[w]==0){ visit(w); vsited[w]=1; Enqueue(Q,w); } } } } int FirstAdjVex(Graph G,int v){ for(int i=0;i if(G.arcs[v][i].adj)return i; } return -1; } int NextAdjVex(Graph G,int v,int w){ for(int i=w+1;i if(G.arcs[v][i].adj)return i; } return -1; } void InitQueue(queue Q){ for(int i=0;i visited[i]=0; }

②DFS

借助visited[]和栈（完成回溯（到刚开始的点））

void DFS(Graph G,int v){ visit(v); visited[v]=1; for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)){ if(visited[w]==0){ DFS(G,w); } } }

BFS&DFS时：邻接矩阵的结果不唯一，邻接表结果唯一。

③AOV网：拓扑排序

拓扑排序就是判断有向图是否存在回路：

Ⅰ选择一个入度为0的顶点并输出；

Ⅱ从图中删除该点及该点的边；

Ⅲ循环ⅠⅡ：若输出的顶点数小于原顶点数，即存在回路，否则，输出序列就是拓扑排序的序列

P.S：有向无环图🉐有拓扑序列

bool TuoPusort(Graph G){ nitStack(S); for(int i=0;i if(indegree[i]==0)Push(S,i); int count=0; while(!IsEmpty(S)){ Pop(S,i); Print(i); count++; for(p=G.vextices[i].firstarc;p;p=p->nextarc){//循环条件，p！=NULL v=p->adjvex; } if(!(--indegree[v]))Push(S,v); } if(countreturn false; else return true; }

④AOE网：关键路径（最长路径）

重点在手动模拟：
例：

# V0 V1 V2 V3 V4 V5 V6 V7 V8
Ve 0 6 4 5 7 7 16 14 18
Vl 0 6 6 8 7 10 16 14 18

Ve:事件最早开始（挑长的），Vl：事件最晚开始（挑短的）

# a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11
e 0 0 0 6 4 5 7 7 7 16 14
l 0 2 3 6 6 8 7 7 10 16 14

e:活动最早开始=前一事件的最早开始时间，

l：活动最晚开始=后一事件的最晚开始时间-当前活动时间

关键路径：找e，l一样的/找Ve，Vl一样的。

⑤最小生成树

最小生成树存在<->图连通

Prim算法：适用稠密图：

void Prim(Grapg G,int S){ MST={S}; while(1){ v=未收录顶点中dist最小者; if(v不存在)break; dist[v]=0;//将angv收录入MST； for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)){ if(dist[w]!=0){ if(E dist[w]=E; parent[w]=v; } } } if(MST中顶点数 ERROR("生成树不存在/图不连通"); } } } void Init(){ dist[v]=E; parent[S]=-1; }

Kruskal算法：适用稀疏图：

void Kruskal(Graph G){ MST={}; while(MST中不到v-1条边&&E中还有边){ 从E中取权重最小边E(v,w); 将E (v,w)从E中删除; if(E(v,w)不在MST中构成回路){ 将E(v,w)加入MST; } else{ 无视E(v,w); } if(MST中不到v-1条边){ ERROR("生成树不存在/图不连通"); } } }

⑥无权图的单源最短路径

改装BFS：dist[w]=s(到w的最短距离),dist[s]=0(其他点初始化为-1)，path[w]=s到w的路径上经过某点。

void BFS(Graph G,int v){ Enqueue(Q,v); while(!IsEmpty(Q)){ Dequeue(Q,v); for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)){ if(dist[w]==-1){ dist[w]=dist[v]+1; path[w]=v; Enqueue(Q,w); } } } }

⑦有权图的单源最短路径

Dijkstra算法：

Ⅰ令S={源点s+已确定的最短路径的顶点vi}

Ⅱ对任一未收录的顶点v，定义dist[v]为s到v的最短路径长度，但该路径仅经过S中的顶点；

即{s->(vi∈S）->v}的最小长度。

Ⅲ若路径是按照递增的顺序生成的，则：

        真正的最短路径必须只经过S中的顶点；

每次从未收录的顶点中选一个dist最小的收录；

增加一个v进入S，可能影响另一个w的dist值；

dist[w]=min{dist[w],dist[v]+E(v,w)}。

dist数组初始化：dist[v]=0,dist[其他]=∞。

void Dijkstra(Graph G,int v){ while(1){ v=未收录顶点中dist最小者; if(v不存在)break; collected[v]=true;//收录 for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(Q,v,w)){ if(collected[w]==false){ if(dist[v]+E(v,w) dist[w]=dist[v]+E(v,w); path[w]=v; } } } } }

⑧多源最短路径

Floyd算法：

ⅠDk[i][j]={i→{l≤k}→j}的最小长度；

ⅡD0，D1，D2……Dv-1[i][j]给出了i到j的真正距离；

ⅢD-1[i][j]=G.arcs[i][j];

Ⅳ当Dk-1已完成，递推到Dk时：

        k不属于{i→{l≤k}→j}，Dk=Dk-1；

k∈{i→{l≤k}→j}，则Dk[i][j]=Dk-1[i][k]+Dk-1[k][j]；

void Floyd(Graph G){ for(i=0;i for(j=0;j D[i][j]=G[i][j]; path[i][j]=-1; } } for(k=0;k for(i=0;i for(j=0;j if(D[i][k]+D[k][j] D[i][j]=D[i][k]+D[k][j]; path[i][j]=k; } } }

第八章-查找

1.基于线性表的查找法

#define LIST_SIZE 20 typedef struct{ KeyType key; OtherType data; }RecordType; typedef struct{ RecordType r[LIST_SIZE+1];//r[0]为工作单元； int length; }RecordList;

①顺序查找法

设置监视哨：

int SeqSearch(RecordList l,KeyType k){ l.r[0].key=k;i=l.length;//其中 l.r[0]为监视哨，起到防止越界的作用。 while(l.r[i].key!=k)i--; return i; }

不设置监视哨：

int SeqSerach(RecordList l,KeyType k){ i=l.length; while(i>=1&&l.r[i].key!=k)i--; if(i>=1)return i; else return 0; }

②折半查找法即二分查找

前提：Ⅰ必须采用顺序存储；Ⅱ必须按关键字大小有序排列。

int BinSearch(RecordList l,KeyType k){ low=1;high=l.length; while(low<=high){ mid=(low+hgh)/2; if(k==l.r[mid].key)return mid; else if(k-1; else low=mid+1; } return 0; }

2.基于树的查找法

详见Binary-Search-Tree二叉搜索树及其操作集

http://t.csdn.cn/4ZHY1

3.计算式查找法（哈希法）

创建哈希表（散列表）时，把关键字为k的元素直接存入地址为H（k）的单元，以后查找关键字为k的元素时，再用哈希函数计算出该元素的存储位置p=H（k），从而达到按关键字直接存取元素的目的，可见，哈希法是计算式查找的方法。

1.数字关键字哈希函数的构造方法：

①直接定址法：取key的某个线性函数值为散列地址：h（key）=a*key+b。

②除留余数法：h（key）=key mod p。p一般取素数。

③数字分析法：分析各位变化，取比较随机的位做散列地址

④折叠法

⑤平方取中法

2.字符关键字哈希函数的构造方法：

①ASCII码加和法：h（key）= $\sum$ key[i] mod TableSize

②前三字符移位法：h（key）=（key[0]*27^2+key[1]*27+key[2]) mod TableSize

3.冲突处理方法：

开放地址法：一旦产生冲突，就按照某种规矩寻找另一空地址。

若发生了第i次冲突，试探地下一个地址增加Di

Di决定了不同的解决方案：线性探测，平方探测，双散列。

①线性探测法：Di=i，增量序列：1，2，3，4，5，6，……

例：{47，7，29，11，9，84，54，20，30}TableSize=11. h（key）=key mod 11.

散列表查找性能分析：成功平均查找长度：ASLs，不成功平均查找长度：ASLu。

H（key） 0 1 2 3 4 5 6 7 8 9 10 11 12
key 11 30 47 7 29 9 84 54 20
冲突次数 0 6 0 0 1 0 3 1 3

冲突次数+1=比较次数

ASLs=（1+7+1+1+2+1+4+2+4）/9≈2.56

ASLu= $\sum$ 各个key须查找几次确定不在散列表里（查找几次到key为空的位置）

=（3+2+1+2+1+1+1+9+8+7+6）/11≈3.73

②平方探测法：Di=±i^2，增量序列：1，-1，4，-4……

如果TableSize是4k+3的素数，平方探测法可以探查到整个散列表。

③双散列探测法：h2（key）=p -（key mod p）

增量序列：h2（key），2h2（key）……

分离链接法：将冲突的关键字存在同一单链表。

第九章-内部排序

void X_sort(ElementType A[],int N);

1.冒泡排序

每一趟排序保证最大的沉底，（下一趟排序只用排N-1个）

void Bubble_sort(ElementType A[],int N){ for(p=N-1;p>=0;p--){ flag=0;//避免一趟无效遍历 for(int i=0;i if(A[i]>A[i+1]){ swap(A[i],A[i+1]); flag=1; } } if(flag==0)break; } }

2.插入排序

如果序列本身基本有序，插入排序是更优选。

void Insertion_Sort(ElementType A[],int N){ for(p=1;p temp=A[p]; for(i=p;i>0&&A[i-1]>temp;i--){ A[i]=A[i-1]; } A[i]=temp; } }

3.时间复杂度下界

Def：任意N个不同元素组成的序列平均具有N（N-1）/4个逆序对；

Def：任何仅以交换两相邻元素来排序的算法，其平均时间复杂度为O（N^2）；

要提高算法效率，我们必须：

Ⅰ每次消去不止一个逆序对；

Ⅱ每次交换间隔较远的2个元素。

4.希尔排序

定义增量序列：Dm>Dm-1>……>D1=1;对每个Dk进行Dk间隔排序

原始希尔排序：Dm=（N/2），Dk=Dk+1/2.

void Shell_Sort(ElementType A[],int N){ for(D=N/2;D>0;D/=2){ for(p=D;p temp=A[p]; for(i=p;i>=D&&A[i-D]>temp;i-=D){ A[i]=A[i-D]; } A[i]=temp; } } }

5.选择排序

void Selection_Sort(ElementType A[],int N){ for(i=0;i MinPosition=ScanForMin(A,i,N-1);//找最小元 swap(A[i],A[MinPosition]); } }

6.堆排序

优化了选择排序中的ScanForMin。

void Heap_Sort(ElementType A[],int N){ BuildHeap(A); for(i=0;i temp[i]=DeleteMin(A); } for(i=0;i A[i]=temp[i]; } }

7.归并排序

核心：有序子列的归并

void merge(int left,int right,int mid) { int p1=left; int p2=mid+1; int p3=left; while(p1<=mid&&p2<=right) { help[p3++]=arr[p1]<=arr[p2]?arr[p1++]:arr[p2++]; } while(p1<=mid) { help[p3++]=arr[p1++]; } while(p2<=right) { help[p3++]=arr[p2++]; } p1=left;p3=left; //这里多出一部分：把help数 //组拷贝到arr中 while(p1<=right) { arr[p1++]=help[p3++]; } } void merge_sort(int left ,int right) { if(left { int mid=left+((right-left)>>1); merge_sort(left,mid); merge_sort(mid+1,right); merge(left,right,mid); } }

8.快速排序

void Quick_Sort(ElementType A[],int l,int r){ if(l>=r)return ; int i=l-1,j=r+1,x=A[l+r>>1]; while(i do i++;while(A[i] do j--;while(A[j]>x); if(iswap(A[i],A[j]); } Quick_Sort(A,l,j); Quick_Sort(A,j+1,r); }

9.各种排序方法性能比较

排序方法平均时间复杂度最坏时间复杂度辅助存储空间
简单排序法 O（n^2）
O（n^2）
O(1)
快速排序 O(nlogn) O(n^2) O(logn)
堆排序 O(nlogn) O(nlogn) O(1)
归并排序 O(nlogn) O(nlogn) O(n)
基数排序 O(d(n+rd)) O(d(n+rd)) O(rd)

排序方法稳定性反例
插入排序是
冒泡排序是
选择排序否
（3，3，2）

希尔排序否
（2，4，1，2）

快速排序否（3，2，2）
堆排序否（5，5，3）
归并排序是
基数排序是

综合比较，可得出以下结论：

①简单排序法一般只用于n较小的情况，当序列基本有序，插入排序是最佳排序方式，当记录中的数据较多，则应采用选择排序法。

②快速排序，堆排序，归并排序的平均时间复杂度均为O（nlogn），但就平均性能而言，快速排序是最好的。

相关阅读:
算法学习笔记(21): 平衡树（二）
“熊猫视图”.Net图形控件功能介绍 [二]：一行代码实现图形图像缩放平操作
 pandas reindex、set_index 和 reset_index
BD Rhapsody单细胞分析系统
 Cron表达式_用于定时调度任务
 8、Bean的循环依赖问题
 剑指offer62 圆圈中最后剩余的数字
 头歌的数据库的第二次作业的答案
 iperf+natapp做4g模块网络带宽测试
 游戏开发团队配置与协作流程

原文地址：https://blog.csdn.net/qq_62795094/article/details/127801221

最新文章

攻防演习之三天拿下官网站群
 数据安全治理学习——前期安全规划和安全管理体系建设
 企业安全 | 企业内一次钓鱼演练准备过程
 内网渗透测试 | Kerberos协议及其部分攻击手法
 0day的产生 | 不懂代码的"代码审计"
安装scrcpy-client模块av模块异常，环境问题解决方案
 leetcode hot100【LeetCode 279. 完全平方数】java实现
 OpenWrt下安装Mosquitto
AnatoMask论文汇总
 【AI日记】24.11.01 LangChain、openai api和github copilot

热门文章

十款代码表白小特效一个比一个浪漫赶紧收藏起来吧！！！
奉劝各位学弟学妹们，该打造你的技术影响力了！
五年了，我在 CSDN 的两个一百万。
Java俄罗斯方块，老程序员花了一个周末，连接中学年代！
面试官都震惊，你这网络基础可以啊！
你真的会用百度吗？我不信 — 那些不为人知的搜索引擎语法
 心情不好的时候，用 Python 画棵樱花树送给自己吧
 通宵一晚做出来的一款类似CS的第一人称射击游戏Demo！原来做游戏也不是很难，连憨憨学妹都学会了！
13 万字 C 语言从入门到精通保姆级教程2021 年版
 10行代码集2000张美女图，Python爬虫120例，再上征途

H（key）	0	1	2	3	4	5	6	7	8	9	10	11	12
key	11	30		47				7	29	9	84	54	20
冲突次数	0	6		0				0	1	0	3	1	3

排序方法	平均时间复杂度	最坏时间复杂度	辅助存储空间
简单排序法	O（n^2）	O（n^2）	O(1)
快速排序	O(nlogn)	O(n^2)	O(logn)
堆排序	O(nlogn)	O(nlogn)	O(1)
归并排序	O(nlogn)	O(nlogn)	O(n)
基数排序	O(d(n+rd))	O(d(n+rd))	O(rd)

排序方法	稳定性	反例
插入排序	是
冒泡排序	是
选择排序	否	（3，3，2）
希尔排序	否	（2，4，1，2）
快速排序	否	（3，2，2）
堆排序	否	（5，5，3）
归并排序	是
基数排序	是