java算法刷题00——数据结构基础知识回顾

数据结构基础知识回顾

• 1、数据结构概述
  • 0.数据结构在学什么
  • 1.数据结构的基本概念（抓大放小）
    • 1）基本概念
    • 2）数据结构的三要素
    • 3）数据类型、抽象数据类型
  • 2.算法的基本概念
    • 1）什么是算法
    • 2）算法的五大特性
    • 3）“好算法”的特点
  • 3.算法的时间复杂度
  • 4.算法的空间复杂度
• 2、线性表
  • 1.线性表的定义与基本操作
    • 1）定义
    • 2）基本操作
  • 2.线性表的顺序表示
    • 1）顺序表的定义
    • 2）顺序表的实现
    • 3）顺序表的四大特点
    • 4）顺序表的基本操作
    • 5）练习题
  • 3.单链表
    • 1）顺序表与链式表的比较
    • 2）单链表定义
    • 3）单链表的插入
    • 4）单链表的删除
    • 5）单链表的查找
    • 6）单链表的建立
  • 4.双链表
    • 1）双链表的定义
    • 2）双链表的插入
    • 3）双链表的删除
    • 4）双链表的遍历
  • 5.循环链表
    • 1）循环单链表
    • 2）循环双链表
  • 6.静态链表
    • 1）静态链表的定义
    • 2）静态链表的基本操作
    • 3）静态链表的优缺点
  • 7.顺序表与链表的对比
  • 8.练习题
• 3、栈和队列
  • 1.栈
    • 1）栈的基本概念
    • 2）栈的基本操作
    • 3）顺序栈的实现
    • 4）链式栈
  • 2.队列
    • 1）队列的基本概念
    • 2）队列的顺序存储结构
    • 3）队列的链式存储结构
  • 3.栈和队列的应用
    • 1）栈在括号匹配中的应用
    • 2）栈在表达式中的应用
    • 3）进制转换
  • 4.串
    • 1）串的基本操作
    • 2）串的朴素模式匹配算法
• 4、树
  • 1.二叉树
    • 1）树的顺序存储
    • 2）树的链式存储
    • 3）二叉树的层次遍历
    • 4）线索二叉树的构造
    • 5）线索二叉树的遍历
    • 6）平衡二叉树
• 5、图
  • 1.图的存储结构
    • 1）数组表示法
    • 2）邻接表
    • 3）十字链表法
  • 2.图的遍历
    • 1）广度优先遍历
    • 2）深度优先遍历
  • 3.最小生成树（prim算法）
  • 4.最短路径
    • 1）单源最短路径
  • 5.拓扑排序
• 6、排序
  • 1.插入排序
    • 1）直接插入排序
    • 2）折半插入排序
    • 3）希尔排序
  • 2.交换排序
    • 1）冒泡排序
    • 2）快速排序
  • 3.选择排序
    • 1）简单选择排序
    • 2）堆排序
  • 4.归并排序
  • 5.快速排序

1、数据结构概述

0.数据结构在学什么

1.数据结构的基本概念（抓大放小）

1）基本概念

数据、数据元素（如一个账号）、数据项（密码、昵称）、数据结构（具有关系的一组数据元素集合，联想汉字的结构其实就是具有布局关系的符号组合）、数据对象（具有相同性质的数据元素的集合、一家海底捞的排队信息可以看作数据结构、全国所有门店排队信息看做同一个数据对象，它们虽无直接关系，但是具有同样的联系）

2）数据结构的三要素

逻辑结构、物理结构、数据运算

逻辑结构：集合、线性、树、图

物理结构：顺序存储、链式存储、索引存储（在存储数据的同时建立一张索引表，索引表中一般存放唯关键字 地址，比如海底捞中每个人取一个号）、散列存储（由关键字计算出其存储位置）。顺序存储数据是连续的，非顺序存储数据是离散的。数据存储的物理结构影响：增删与查找的便利度

数据运算的定义由逻辑结构定义，由物理结构实现。

3）数据类型、抽象数据类型

数据类型：一组同类型数据 操作，比如int类型数据，可以±*/，比如boolean类型，可以与或非操作。

数据类型分类：原子类型、结构类型（结构体）

抽象数据类型：抽象数据组织及其操作，即定义一个理论的数据类型，讨论其元素的逻辑关系，不讨论其实际物理结构。

2.算法的基本概念

1）什么是算法

程序=数据结构 算法，数据结构把现实生活中的信息存储到了计算机中，算法提供了解决实际问题的方法。比如海底捞的顾客排队信息用数据结构存储到了计算机中，那怎么实现vip插队就由算法来实现。

2）算法的五大特性

有穷性（程序可以无穷，比如海底捞排队系统只要不关机就一直运行）、确定性（无二义）、可行性（可由基本运算执行有限次实现）、0个或多个输入、1个或多个输出

3）“好算法”的特点

正确性（能够正确解决问题）、可读性、健壮性（非法输入可处理）、高效率低存储

3.算法的时间复杂度

算法的时间复杂度：预估运行时间与问题规模的关系T（n）。大O法表示，本质是：时间与问题规模的函数，不考虑低阶，不考虑系数，只考虑其数量级。

T（n）=O（f（n））

运算：加法规则、乘法规则（略）。

结论：

1.顺序执行的代码只影响常数项、忽略。

2.只需挑循环中的一个基本语句来判断其执行次数、分析时间复杂度即可。

3.多层嵌套只需关注最深层。

代码语言：javascript复制

void loveYou（int flag[],int n）
{
    int i;
    for(i=0;flag[i]<n;i  )
    {
        if(flag[i]==n)printf("I love U");
        break;
    }
}

最好的情况：flag[0]等于n，最优时间复杂度O（1）；

最坏的情况：要查找至最后一个数，最坏时间复杂度O（n）；

平均情况：(1 2 … n)/n=n*(n 1)/2，平均时间复杂度O（n）。

4.算法的空间复杂度

算法原地工作：算法的空间复杂度是常量。

代码语言：javascript复制

void loveYou(int n;)
{
 	int flag[n];   
    int i;
}

数据所占内存：4 4n 4 B；空间复杂度：S(n）=O(n）；

递归调用：

代码语言：javascript复制

void loveYou(int n)
{
    if(n>1) loveYou(n-1);
    printf("I love U %dn");
}

int main(void){
    loveYou(5);
    return 0;
}

每次执行loveYou需要使用k（常数）个存储空间存储数据，调用5次就会使用5k个存储空间，空间复杂度S(n)=O(n);

代码语言：javascript复制

void loveYou(int n)
{
	int flag[n];
    if(n>1) loveYou(n-1);
    printf("I love U %dn");
}

int main(void){
    loveYou(5);
    return 0;
}

每一次执行loveYou占用4*(n (n-1) …1) 个空间存储数据[数组]，S(n)=O(n^2);

2、线性表

1.线性表的定义与基本操作

1）定义

具有相同类型数据的有限序列（有次序）。表长、空表、位序（是线性表中第几个元素,从1开始）

2）基本操作

初始化:InitList(&L)；

增加元素:ListInsert(&L,i,e);

删除元素:LisDelete(&L,i,&e);//用e返回删除元素的值,要把数据“带回来”，传地址，其实也可以传e，用return语句带回来

销毁:DestroyList(&L);

按值查找:LacateElem(L,e);

按位查找:GetElem(L,i);

输出:PrintList(L);

判空:Empty(L);

2.线性表的顺序表示

1）顺序表的定义

顺序存储实现的线性表。第一个a1元素位置，LOC(L);后续元素ai位置，LOC(L) (i-1)*sizeof(ElemType)。

2）顺序表的实现

静态分配：

代码语言：javascript复制

#define MaxSize 50
typedef struct{
	int data[MaxSize];
	int length;
}SqlList;

void InitList(SqlList &L)
{
	int i;
	for(i=0;i<L.length;i  ) L.data[i]=0;
	L.length=0;
}

int main(void)
{
	SqlList L;
	InitList(L);
	int i;
	for(i=0;i<L.length;i  )printf("%d ",L.data[i]);
	return 0;
}

动态分配：

代码语言：javascript复制

#include<stdio.h>
#include<stdlib.h>
#define InitSize 4 //默认长度
typedef struct{
	int * data;
	int MaxSize;
	int length;
}SeqList;

void InitList(SeqList &L)
{
	L.data=(int *)malloc(InitSize*sizeof(int));
	L.length=0;
	L.MaxSize=InitSize;
}

void IncreaseSize(SeqList &L,int len)
{
	int * p=L.data;
	L.data=(int *)malloc((L.MaxSize len)*sizeof(int));
	for(int i=0;i<L.MaxSize;i  ) L.data[i]=p[i];
	free(p);
	L.MaxSize=L.MaxSize len;
}
int main(void)
{
	SeqList L;
	InitList(L);
    //这种插入数据的方式不规范，并没有改变length
	L.data[0]=1;
	L.data[1]=2;
	L.data[2]=3;
	L.data[3]=4;
	for(int i=0;i<L.MaxSize;i  ) printf("a[%d]=%d,",i,L.data[i]);
	printf("n");
	IncreaseSize(L,3);
	for(int i=0;i<L.MaxSize;i  ) printf("a[%d]=%d,",i,L.data[i]);
	return 0;
}

3）顺序表的四大特点

可以随机访问。

存储密度高，只需存数据，不需存指针。

扩展容量不方便，静态分配无法扩展，动态分配需要把存储的内容复制到新分配的区域。

插入、删除效率低。

4）顺序表的基本操作

插入

代码语言：javascript复制

#include<stdio.h>
#include<stdlib.h>
#define InitSize 10

typedef struct{
int * data;
int length;
int MaxSize;
}SeqList;

void InitList(SeqList &L)
{
	int i=0;
	L.data=(int *)malloc(InitSize*sizeof(int));
	for(i=0;i<L.MaxSize;i  )L.data[i]=0;
	L.length=0;
	L.MaxSize=InitSize;
}

bool ListInsert(SeqList &L,int i,int e)//i是位序,不是数组下标
{
	if(i<1||i>L.length 1) return false;
	if(i>L.MaxSize) return false;
	int j;
	for(j=L.length;j>=i;j--)
		L.data[j]=L.data[j-1];  //1
	L.data[i-1]=e;
	L.length  ;
	return true;
}


int main(void)
{
	SeqList L;
	InitList(L);
	ListInsert(L,1,1);
	ListInsert(L,2,2);
	ListInsert(L,3,3);
	for(int i=0;i<L.length;i  )printf("data[%d]=%d,",i,L.data[i]);
	printf("n");
	ListInsert(L,1,0);
	for(int i=0;i<L.length;i  )printf("data[%d]=%d,",i,L.data[i]);
	return 0;
}

最优时间复杂度：O（1），即插入到表尾——位序n 1处，不需要执行最深层的for循环（1处）；

最坏时间复杂度：O（n），插入到表头——位序为1处，最深层for循环执行n次；

平均复杂度：O（n），每个位序插入的可能性是1/（n 1）,(0 1 … n)/(n 1)=n*(n 1)/2 /(n 1)=n/2;

删除

代码语言：javascript复制

#include <stdio.h>
#include <stdlib.h>
#define InitSize 10

typedef struct{
int * data;
int MaxSize;
int length;
}SeqList;

void InitList(SeqList &L)
{
	int i;
	L.data=(int *)malloc(InitSize*sizeof(int));
	L.MaxSize=InitSize;
	for(i=0;i<L.MaxSize;i  ) L.data[i]=0;
	L.length=0;
}

bool ListInsert(SeqList &L,int i,int e)
{
	int j;
	if(i<1||i>L.length 1)return false;
	if(i>L.MaxSize)return false;
	for(j=L.length;j>=i;j--)
		L.data[j]=L.data[j-1];
	L.data[i-1]=e;
	L.length  ;
	return true;
}
//按位删除
bool ListDelete(SeqList &L,int i,int &e) //此处传入的参数i是位序为i的元素，即删除对应下标为i-1的元素
{
	if(i<1||i>L.length)return false;
	e=L.data[i-1]; 
	int j;
	for(j=i;j<L.length;j  )
		L.data[j-1]=L.data[j];
	L.length--;
	return true;
}

int main(void)
{
	int e=-1;
	SeqList L;
	InitList(L);
	ListInsert(L,1,1);
	ListInsert(L,2,2);
	ListInsert(L,3,3);
	for(int i=0;i<L.length;i  )printf("data[%d]=%d,",i,L.data[i]);
	printf("n");
	if(ListDelete(L,1,e))
		printf("Delete %dn",e);
	else
		printf("Failure!n");
	for(int i=0;i<L.length;i  )printf("data[%d]=%d,",i,L.data[i]);
	return 0;
}

最好时间复杂度：O（1);

最坏时间复杂度：O（n);

平均复杂度：O（n）;

按位查找

代码语言：javascript复制

#include<stdio.h>
# define MaxSize 10
typedef struct{
	int data[MaxSize];
	int length;
}SeqList;

void InitList(SeqList &L)
{
	int i;
	for(i=0;i<MaxSize;i  )L.data[i]=0;
	L.length=0;
}

bool ListInsert(SeqList &L,int i,int e)
{
	int j;
	if(i<1||i>L.length 1)return false;
	if(i>MaxSize)return false;
	for(j=L.length;j>=i;j--)
		L.data[j]=L.data[j-1];
	L.data[i-1]=e;
	L.length  ;
	return true;
}

int GetElem(SeqList L,int i){
	if(i<1||i>L.length) return -1;
	return L.data[i-1];
}

int main(void)
{
	SeqList L;
	InitList(L);
	ListInsert(L,1,1);
	ListInsert(L,2,2);
	ListInsert(L,3,3);
	printf("%d,",GetElem(L,1));
	printf("%dn",GetElem(L,0));
	return 0;
}

时间复杂度：O（1）

按值查找

代码语言：javascript复制

int LocateElem(SeqList L,int e)
{
	int i;
	for(i=0;i<L.length;i  )
		if(L.data[i]==e)return i 1;
	return 0;
}

最好时间复杂度：O(1)

最坏时间复杂度：O(n)

平均时间复杂度：O(n)

5）练习题

T1 删除顺序表中的最小值（假设唯一），并由函数返回被删元素的值。若顺序表为空则显示出错信息并退出运行

代码语言：javascript复制

//删除最小元素，并返回该元素的值
bool ListDelete(SeqList &L,int &min)
{
	int i; 
	int index=0;//记录最小元素的位序
	if(L.length==0) return false; //如果链表为空，则返回false
	min=L.data[0];
	//查找最小的元素
	for(i=1;i<L.length;i  )
	{
		if(L.data[i]<min) min=L.data[i];
		index=i 1;
	}
	//将空出来的位置由最小的元素代替
	L.data[index]=L.data[L.length-1];
	L.length--;
	return true; 
}

T2 设计算法将顺序表中的元素逆序，要求算法的空间复杂度O(1);

代码语言：javascript复制

bool ReverseList(SeqList &L)
{
	if(L.length==0)return false;
	int i;
	int j;
	int temp;
	for(i=0;i<(L.length)/2;i  )
	{
		j=L.length-i-1;
		temp=L.data[i];
		L.data[i]=L.data[j];
		L.data[j]=temp;
	}
	return true;
}

*T3 长度为n的顺序表L，编写一个时间复杂度为O(n)，空间复杂度为O(1)的算法。该算法删除线性表中所有值为x的元素。

代码语言：javascript复制

void DeleteByValue(SeqList &L,int x)
{
	int k=0;//用来存储不是x的数的个数
	for(int i=0;i<L.length;i  )
	{
		if(L.data[i]!=x)
		{
			L.data[k]=L.data[i];
			k  ;
		}
	}
	L.length=k;
}

T4 从有序顺序表中删除其值在给定值s与t之间(要求s<t)的所有元素，如果s或者t不合理或顺序表为空，则显示出错信息并退出运行。

代码语言：javascript复制

bool DeleteBetweenValue(SeqList &L,int s,int t,int &start,int &end)
{
	if(L.length==0) return false;
	if(s>=t) return false;
	int i;
	for(i=0;i<L.length;i  )
	{
		if(L.data[i]==s)start=i 1;
		if(L.data[i]==t)end=i 1;
	}
	return true;
}

int main(void)
{
	int e=0;
	SeqList L;
	InitList(L);
	int start;
	int end;
	ListInsert(L,1,1);
	ListInsert(L,2,2);
	ListInsert(L,3,3);
	for(int i=0;i<L.length;i  )printf("%d,",L.data[i]);
	DeleteBetweenValue(L,1,2,start,end);
	printf("n");
	int k=end-start 1;
	for(int j=0;j<k;j  ) ListDelete(L,start,e);
	for(int i=0;i<L.length;i  )printf("%d,",L.data[i]);
	return 0;
}

3.单链表

1）顺序表与链式表的比较

顺序表：存储密度高、可以随机存取，但是扩展容量不方便，删除、插入元素开销大。

链式表：需要存储指针信息，不能随机存取，只能依次遍历，删除、插入元素开销小，扩展容量很容易。

2）单链表定义

不带头结点

代码语言：javascript复制

#include <stdio.h>

typedef struct LNode{
	int data;
	struct LNode * next;
}LNode,*LinkList;

//无头节点
bool InitList(LinkList &L)
{
	L=NULL; //把头指针置空
	return true;
}

//判断链表是否为空，如果为空，头指针指向NULL
bool IsListEmpty(LinkList L)
{
	return (L==NULL);
}

int main(void)
{
	LinkList L; //声明一个指向单链表的指针
	InitList(L);
	printf("%d",IsListEmpty(L));
	return 0;
}

带头结点

代码语言：javascript复制

#include <stdio.h>
#include <stdlib.h>

typedef struct LNode{
	int data;
	struct LNode * next;
}LNode,*LinkList;

//带头节点
bool InitList(LinkList &L)
{
	L=(LNode *)malloc(sizeof(LNode));
	if(L==NULL)return false; //上面头指针指向了头结点，头指针还指向NULL,说明内存空间不足，返回false；
	L->next=NULL; //头结点置空
	return true;
}

//判断链表是否为空，如果为空，头指针指向NULL
bool IsListEmpty(LinkList L)
{
	return (L->next==NULL);
}

int main(void)
{
	LinkList L; //声明一个指向单链表的指针
	InitList(L);
	printf("%d",IsListEmpty(L));
	return 0;
}

3）单链表的插入

按序号插入——带头结点(推荐)

代码语言：javascript复制

#include <stdio.h>
#include <stdlib.h>
typedef struct LNode{
	int data;
	LNode * next;
}LNode,*LinkList;

void InitList(LinkList &L)
{
	L=(LNode *)malloc(sizeof(LNode)); //分配一个空间作为头结点，头指针指向头结点
	L->next=NULL; //头节点的next域置空
}

//按位序插入
bool ListInsert(LinkList &L,int i,int e)
{
	if(i<1) return false;
	LNode * p=L; //指针p指向头结点
	int j=0; //下标j用来记录指针p指向第几个结点
	while(p!=NULL&&j<i-1) //循环找到第i-1个结点
	{
		p=p->next;
		j  ;
	}
	if(p==NULL) return false; //i值超过了链表的范围，不合法
	LNode * s=(LNode *)malloc(sizeof(LNode)); //指针s指向一个新的结点
	s->data=e; //将要插入的数据e存到结点中
	s->next=p->next;
	p->next=s;
	return true;
}

int main(void)
{
	LinkList L; //申请一个LinkList类型的头指针
	InitList(L);
	if(ListInsert(L,1,1))
	{
		printf("%dn",L->next->data);
	}
	else
		printf("Failed!n");
	return 0;
}

最好时间复杂度：O(1),最坏时间复杂度：O(n),平均时间复杂度：O(n)

按序号插入——不带头结点

代码语言：javascript复制

#include <stdio.h>
#include <stdlib.h>
typedef struct LNode
{
	int data;
	LNode * next;
}LNode,*LinkList;

//不带头结点
bool InitList(LinkList &L)
{
	L=NULL; //将头指针置空
	return true;
}

//按位插入
bool ListInsert(LinkList &L,int i,int e)
{
	if(i<1) return false; //非法输入
	if(i=1)
	{
		LNode * s=(LNode *)malloc(sizeof(LNode));
		s->data=e;
		s->next=L;
		L=s;
		return true;
	}
	int j=1; //用来记录p指向第几个结点
	//找到第i-1个结点
	LNode * p=L;
	while(p!=NULL&&j<i-1)
	{
		p=p->next;
		j  ;
	}
	if(p==NULL) return false;
	LNode * s=(LNode *)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;
}

int main(void)
{
	LinkList L;//声明一个头指针
	InitList(L);
	if(ListInsert(L,0,1))
	{
		printf("%dn",L->data);
	}
	else
		printf("Failed!n");
	return 0;
}

指定结点后插操作

代码语言：javascript复制

bool InsertNextNode(LNode * p,int e)
{
	if(p==NULL) return false; //i值超过了链表的范围，不合法
	LNode * s=(LNode *)malloc(sizeof(LNode)); //指针s指向一个新的结点
	s->data=e; //将要插入的数据e存到结点中
	s->next=p->next;
	p->next=s;
	return true;
}

时间复杂度:O（1）

指定结点前插操作

代码语言：javascript复制

#include <stdio.h>
#include <stdlib.h>
typedef struct LNode
{
	int data;
	LNode * next;
}LNode,*LinkList;

void InitList(LinkList &L)
{
	LNode * p;
	L=(LNode *)malloc(sizeof(LNode));
	p=L;
	p->next=NULL;
}

//按位插入
bool ListInsert(LinkList &L,int i,int e)
{
	if(i<1) return false; //非法输入
	int j=0; //用来记录p指向第几个结点
	//找到第i-1个结点
	LNode * p=L;
	while(p!=NULL&&j<i-1)
	{
		p=p->next;
		j  ;
	}
	if(p==NULL) return false;
	LNode * s=(LNode *)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;
}

//核心代码块，插入制定结点之前
bool InsertPrioList(LNode * p,int e)
{
	if(p==NULL)return false;
	LNode * s=(LNode *)malloc(sizeof(LNode));
	if(s==NULL)return false;
	//把s插入p结点之后
	s->next=p->next;
	p->next=s;
	//把p的数据拷贝到s，再把要插入的数据存入p
	s->data=p->data;
	p->data=e;
	return true;
}

int main(void)
{
	LinkList L;
	InitList(L);
	ListInsert(L,1,1);
	LNode * r=L->next;
	InsertPrioList(r,5);
	printf("%d",L->next->data);
	return 0;
}

时间复杂度：O（1）

4）单链表的删除

代码语言：javascript复制

#include <stdio.h>
#include <stdlib.h>
typedef struct LNode
{
	int data;
	LNode * next;
}LNode,*LinkList;

bool InitList(LinkList &L)
{
	L=(LNode *)malloc(sizeof(LNode));
	if(L==NULL)return false;
	L->next=NULL;
	return true;
}

//按位插入
bool ListInsert(LinkList &L,int i,int e)
{
	if(i<1) return false; //非法输入
	int j=0; //用来记录p指向第几个结点
	//找到第i-1个结点
	LNode * p=L;
	while(p!=NULL&&j<i-1)
	{
		p=p->next;
		j  ;
	}
	if(p==NULL) return false;
	LNode * s=(LNode *)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;
}

//核心代码，按位序删除
bool ListDelete(LinkList &L,int i,int &e)
{
	if(L->next==NULL)return false;
	if(i<1)return false;
	//找到第i-1个位置
	LNode * p=L;
	int j=0;
	while(j<i-1&&p!=NULL)
	{
		p=p->next;
		j  ;
	}
	if(p==NULL) return false;
	//在第i-1个位置后执行删除操作
	LNode * q=p->next;
	e=q->data;
	p->next=q->next;
	free(q);
	return true;
}

void PrintList(LinkList L)
{
	LNode * p=L;
	while(p->next!=NULL)
	{
		p=p->next;
		printf("%d ",p->data);
	}
	printf("n");
}

int main(void)
{
	LinkList L;
	InitList(L);
	ListInsert(L,1,1);
	ListInsert(L,2,2);
	ListInsert(L,3,3);
	LNode * p=L;
	PrintList(L);
	int e;
	ListDelete(L,2,e);
	p=L;
	PrintList(L);
	return 0;
}

最好时间复杂度：O（1）、最坏、平均时间复杂度O（n).

指定结点的删除

代码语言：javascript复制

bool DeleteNode(LNode * p)
{
	if(p==NULL) return false;
	LNode * q=p->next;
	p->data=q->data;
	p->next=q->next;
	free(q);
	return true;
}

时间复杂度:O(1)

[注]若要删除最后一个结点，p->next为NULL，故q不存在data域，这种解法不适用了。

5）单链表的查找

按位查找

代码语言：javascript复制

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

平均时间复杂度:O（n）

按值查找

代码语言：javascript复制

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

表长

代码语言：javascript复制

int ListLength(LinkList L)
{
	int i=0;
	LNode * p=L->next;
	while(p!=NULL)
	{
		p=p->next;
		i  ;
	}
	return i;
}

6）单链表的建立

尾插法

可以通过每一次插入都调用

代码语言：javascript复制

while 循环
{
	//取数据元素
	ListInsert(LinkList,length 1,e); //插至链表尾部
    length  ;
}

但每次插入一个元素都要从头开始遍历，时间复杂度为O（n^2);可以通过一个指针来指向表尾，每次移动尾指针改良；

代码语言：javascript复制

LinkList Link_TailInsert(LinkList &L) //正向建立单链表
{
	//初始化
	L=(LNode *)malloc(sizeof(LNode)); //头指针指向头结点
	LNode * p=L; //指针p指向头结点
	//用户输入数据、并依次生成结点,直至用户输入9999退出
	int x;
	scanf("%d",&x);
	while(x!=9999)
	{
		LNode * q=(LNode *)malloc(sizeof(LNode));
		p->next=q;
		p=q;
		p->data=x;
		scanf("%d",&x);
	}
	p->next=NULL; //尾指针置空，不做这一步，最后尾指针会指向自己
	return L;
}

头插法

代码语言：javascript复制

LinkList Link_HeadInsert(LinkList &L)
{
	int a;
	LNode * p;
	//初始化
	L=(LNode *)malloc(sizeof(LNode)); //头指针指向头结点
	L->next=NULL; //必须指向NULL
	//输入数据、并把输入的数据插入到头结点之后
	scanf("%d",&a);
	while(a!=9999)
	{
		p=(LNode *)malloc(sizeof(LNode));
		p->data=a;
		p->next=L->next;
		L->next=p;
		scanf("%d",&a)；
	}
	return L;
}

头插法的应用：实现链表的逆置

代码语言：javascript复制

//法一：通过新建一个链表实现
LinkList ReverseList(LinkList &L)
{
	LNode * p; //指针
	LinkList s=(LNode *)malloc(sizeof(LNode)); //生成一个新的链表
	s->next=NULL;
	while(L->next!=NULL)
	{
		//从头开始依次取下链表L的结点
		p=L->next; //指向要被取下的结点
		L->next=p->next;
		//把取下的数据使用头插法插入到新的链表s
		p->next=s->next;
		s->next=p;
	}
	return s;
}

代码语言：javascript复制

//法二：就地转置，将头结点摘下，然后从第一结点开始，依次前插入到头结点的后面（头插法），直到最后一个结点为止。 
LinkList ReverseList2(LinkList &L)
{
	LNode *p,*q; //p指针指向位序为一的结点
	p=L->next;
	L->next=NULL; //取下头结点
	//使用头插法把结点从头依次插入头结点后面
	while(p!=NULL)
	{
		q=p->next; 
		p->next=L->next;
		L->next=p;
		p=q;
	}
	return L;
}

其实以上两个方法基本上原理是相同的，用法二更好，因为是原地转置，用法一也可以再最后把头指针L->s;

4.双链表

1）双链表的定义

代码语言：javascript复制

typedef struct DNode{
	int data;
	DNode * next,* prior;
}DNode,*DLinkList;

bool InitList(DLinkList &L)
{
	L=(DNode *)malloc(sizeof(DNode));
	if(L==NULL)
		return false;
	L->next=NULL;
	L->prior=NULL;
	return true;
}

bool Empty(DLinkList &L)
{
	return(L->next==NULL);
}

2）双链表的插入

代码语言：javascript复制

bool ListInsert(DNode * p,DNode * s)
{
	if(p==NULL||s==NULL) return false;
	s->next=p->next; //1
	if(p->next!=NULL)
		p->next->prior=s; //2
	s->prior=p; //3
	p->next=s;  //4  1,2必须在4前
	return true;
}

这是指定结点的后插操作，按位序插入只需要设置尾指针，依次进行后插操作即可；前插操作只需要找到一个结点的前继结点，对其进行后插操作即可。

3）双链表的删除

代码语言：javascript复制

bool ListDelete(DNode * p) //删除指定结点的后继节点
{
	if(p==NULL) return false;
	DNode * q=p->next; 
	if(q==NULL) return false;
	p->next=q->next;
	if(q->next!=NULL) q->next->prior=p;
	free(q);
	return true;
}

销毁一个双链表

代码语言：javascript复制

void DestroyList(DLinkList &L)
{
	while(L->next!=NULL) ListDelete(L);
	free(L); //释放头结点
	L->next=NULL; //头指针置空
}

4）双链表的遍历

代码语言：javascript复制

//后向遍历
while(p!=NULL)
{
    //...
    p=p->next;
}

//前向遍历
while(p->pror!=NULL) //跳过了头结点
{
    //...
    p=p->prior;
}

5.循环链表

1）循环单链表

代码语言：javascript复制

typedef struct LNode
{
	int data;
	LNode * next;
}LNode,*LinkList;

bool InitList(LinkList L)
{
	L=(LNode *)malloc(sizeof(LNode));
	if(L=NULL) return false;
	L->next=L;
	return true;
}

bool Empty(LinkList L)
{
	if(L->next=L) return true;
	return false;
}

bool isTail(LinkList L,LNode * p) //判断一个结点是否为尾节点
{
	return(p->next==L);
}

使用循环单链表时，如果经常需要对表头、表尾操作，可以使L指向表尾，这样找到表头、表尾的时间复杂度都是O（1）。

2）循环双链表

代码语言：javascript复制

typedef struct LNode
{
	int data;
	LNode * next;
	LNode * prior;
}LNode,*LinkList;

bool InitList(LinkList L)
{
	L=(LNode *)malloc(sizeof(LNode));
	if(L=NULL) return false;
	L->next=L;
	L->prior=L;
	return true;
}

bool Empty(LinkList L)
{
	if(L->next=L) return true;
	return false;
}

bool isTail(LinkList L,LNode * p) //判断一个结点是否为尾节点
{
	return(p->next==L);
}

bool ListInsert(DNode * p,DNode * s) 
{
	if(p==NULL||s==NULL) return false;
	s->next=p->next; //1
	p->next->prior=s; //2 尾节点会指向头结点，不会置空，因此不需要条件判断
	s->prior=p; //3
	p->next=s;  //4  1,2必须在4前
	return true;
}


bool ListDelete(DNode * p) //删除指定结点的后继节点
{
	if(p==NULL) return false;
	DNode * q=p->next; 
	p->next=q->next;
    q->next->prior=p;
	free(q);
	return true;
}

指针类链表小结

链表类代码在编写时需要考虑三个问题：

1.如何判空，知道空的状态如何判断就知道如何初始化

2.如何判断表头，表尾，知道怎么判断表头表尾就知道怎么遍历，就知道了怎么去查找、删除、增加

3.表尾、表头是否需要特殊处理

6.静态链表

1）静态链表的定义

代码语言：javascript复制

#define MaxSize 10

typedef struct Node
{
	int data;
	int next;
}SLinkList[MaxSize];

void InitList()
{
	SLinkList a;
}

2）静态链表的基本操作

初始化：要将a[0]置为-1；将其他空的结点游标置为-2（方便后续计算机判断哪些结点是空结点）；

查找：通过游标依次遍历元素，时间复杂度为O(n)

插入：

1.找到一个空的结点用来存放元素

2.找到位序为i-1的结点

3.修改新的结点的next游标

4.修改i-1结点的next

删除：

1.找到其前驱结点

2.修改前驱结点游标

3.被删除结点的游标置为-2；

3）静态链表的优缺点

优点：增删容易，不需要大量的移动数据

缺点：查找需要遍历，容量固定

7.顺序表与链表的对比

	顺序表	链式表
逻辑结构	均为线性表；	均为线性表；
存储结构	1）基于静态分配的顺序表不能改变其大小，基于动态分配的顺序表改变容量不容易 。分配一片连续的存储区域不方便。2）存储密度较高。	1）结点无需申请一大片连续的存储空间，可以改变容量的大小。2）存储密度较低。
基本操作	1）初始化容量大小不好确定。2）静态分配销毁由系统自动完成，动态分配手动销毁。3）插入、删除操作时间复杂度较大。4）可以随机访问元素，按位查找时间复杂度为O（1），按值查找时间复杂度为O（n）【无序】或者O（log2n）【有序】	1）销毁操作需要手动free。2）优点是插入、删除结点很方便 ，只需要改变next指针所指向的元素。3）不能够随机访问元素，只能够通过遍历的方式进行元素的访问。查找的时间复杂度为O(n)

注：虽然顺序表、链式表的插入、删除操作时间复杂度都为O（n），但顺序表的时间开销来自于元素的移动，

链式的时间开销来自于结点遍历，故顺序表的时间花销其实更大。

8.练习题

T1 设计一个递归算法，删除不带头结点的单链表L中所有值为x的结点

代码语言：javascript复制

//设计一个递归算法，删除不带头结点的单链表L中所有值为x的结点
void Delete_x(LinkList &L,int x)
{
	LNode * p;
	if(L==NULL)return;
	while(L->data!=x)
	{
		Delete_x(L->next,x);
		return;
	}
	p=L;
	L=L->next;
	free(p);
	Delete_x(L,x);
}

T21带头结点单链表，头指针为list。在不改变链表的前提下，设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。要求：

1）描述算法的基本设计思想

2）描述算法的详细实现步骤

3）根据设计思想和步骤，采用程序设计语言描述算法，关键之处请给出简要注释。

解：

1）两个指针p，q分别指向位序为1的结点（头结点的后继结点），指针p依次移动直至指向位序为k的元素时，指针q随p同步移动，当指针p移动至表尾，指针q所指向元素即为倒数第k个元素。

2）算法的详细实现步骤如下：

代码语言：javascript复制

//1.count=0,p,q指向链表头结点的后继结点；

//2.若p为空，返回0；

//3.若count<k,count累加，若count=k，指针q后移；

//4.p结点后移，

//5.若count等于k，则查找成功，输出该结点的data域，返回1;

//6.算法结束

3、栈和队列

1.栈

1）栈的基本概念

只能从栈顶进行插入或者删除操作的线性表

2）栈的基本操作

InitStack(&S);

DestroyStack(&L);

Push(&S,x);

Pop(&S,&x);

GetTop(S,&x);

StackEmpty(S);

3）顺序栈的实现

代码语言：javascript复制

#include <stdio.h>
#define MaxSize 10
typedef struct
{
	int data[MaxSize];
	int top;
}SeqStack;
//初始化
void InitStack(SeqStack &S)
{
	S.top=-1;
}
//栈空判断
bool StackEmpty(SeqStack S)
{
	return(S.top==-1);
}
//入栈
bool Push(SeqStack &S,int x)
{
	if(S.top==MaxSize-1) return false;
	S.data[  S.top]=x;
	return true;
}
//出栈
bool Pop(SeqStack &S,int &x)
{
	if(S.top==-1) return false;
	x=S.data[S.top--];
	return true;
}
//读取栈顶元素
bool GetTop(SeqStack S,int &x)
{
	if(S.top==-1) return false;
	x=S.data[S.top];
	return true;
}

//上述代码top指针初始指向栈顶
int main()
{
	SeqStack S;
	InitStack(S);
	printf("%dn",StackEmpty(S));
	Push(S,2);
	printf("%dn",StackEmpty(S));
	int x;
	Pop(S,x);
	printf("%d,%dn",StackEmpty(S),x);
	Push(S,3);
	GetTop(S,x);
	printf("%d,%dn",StackEmpty(S),x);
	return 0;
}

缺点：存储容量不可改变

4）链式栈

代码语言：javascript复制

#include <stdio.h>
#include <stdlib.h>
//定义栈结点
typedef struct SNode{
	int data;
	SNode * next;
}*LinkStack,SNode;
//初始化栈（不带头结点）
bool InitStack(LinkStack &S)
{
	S=NULL;
	return true;
}
//判空
bool StackEmpty(LinkStack S)
{
	return (S==NULL);
}
//入栈操作
bool Push(LinkStack &S,int x)
{
	//在头部插入元素
	SNode * p=(SNode *)malloc(sizeof(SNode));
	//这里并不需要区分是不是第一个结点，两者操作时一致的！！！
	p->data=x;
	p->next=S;
	S=p;
	return true;
}
//出栈操作（不带头结点）
bool Pop(LinkStack &S,int &x)
{
	if(S==NULL) return false;
	SNode * p=S;
	x=S->data;
	S=S->next;
	free(p);
	return true;
}
//打印栈中元素（不带头结点）
void PrintStack(LinkStack S)
{
	if(S==NULL) return;
	while(S!=NULL)
	{
		printf("%d ",S->data);
		S=S->next;
	}
	printf("n");
}

//对于链式存储结构实现的栈（不带头结点）进行增删改查操作
int main(void)
{
	int x;
	LinkStack S;
	InitStack(S);
	printf("%dn",StackEmpty(S));
	Push(S,1);
	Push(S,2);
	Push(S,5);
	Push(S,1);
	PrintStack(S);
	Pop(S,x);
	Pop(S,x);
	PrintStack(S);
	return 0;
}

2.队列

1）队列的基本概念

队头：允许删除元素的一端；

队尾：允许插入元素的一端。

2）队列的顺序存储结构

代码语言：javascript复制

#include <stdio.h>
#define MaxSize 10
typedef struct SeQueue
{
	int data[MaxSize];
	int front,rear;
};
//初始化队列，队头、队尾指针均指0
void InitQueue(SeQueue &Q){
	Q.front=0;
	Q.rear=0;
}
//队列判空:队头与队尾指向相同空间，即差值为0，队空
bool QueueEmpty(SeQueue Q)
{
	return (Q.front==Q.rear);
}
//入队操作：先将数据插入至队尾，再将尾指针后移
bool EnQueue(SeQueue &Q,int x)
{
	if((Q.rear 1)%MaxSize==Q.front) return false; //判断队列是否满，满则返回false,这里牺牲了一个存储空间用来区分队满和队空
	Q.data[Q.rear]=x;
	Q.rear=(Q.rear 1)%MaxSize; //这里要注意！由于这种方式实现的队列在逻辑上似乎是循环的，也称作循环队列
	return true;
}
//出队操作：先将数据取出，再将头指针后移
bool DeQueue(SeQueue &Q,int &x)
{
	if(Q.front==Q.rear) return false; //判断是否队空
	x=Q.data[Q.front];
	Q.front=(Q.front 1)%MaxSize;
	return true;
}
//查;获取队头元素
bool GetHead(SeQueue Q,int &data)
{
	if(Q.front==Q.rear) return false;
	data=Q.data[Q.front];
	return true;
}
int main(void)
{
	SeQueue Q;
	int x;
	int data;
	InitQueue(Q);
	printf("队列是否为空：%dn",QueueEmpty(Q));
	EnQueue(Q,1);
	printf("队列是否为空：%dn",QueueEmpty(Q));
	GetHead(Q,data);
	printf("队头元素为：%dn",data);
	DeQueue(Q,x);
	printf("队列是否为空：%dn",QueueEmpty(Q));
	return 0;
}

队列元素个数：(Q.rear-Q.front MaxSize)%MaxSize;

如果想要不浪费一个存储空间用来区分队满与队空，我们可以使用一个在队列中定义一个size用来记录元素个数，初始设为0，增加元素size ，减少元素size–，队满条件size= =Maxsize，队空条件为：size= =0；

也可以设置tag，删除tag置为0，插入tag置为1，队满一定是因为插入，tag一定为1；

3）队列的链式存储结构

代码语言：javascript复制

#include <stdio.h>
#include <stdlib.h>
//定义链式队列结点
typedef struct LinkNode
{
	int data;
	LinkNode * next;
}LinkNode;
//定义链式队列
typedef struct 
{
	LinkNode * front,* rear;
}LinkQueue;
//初始化(带头结点)
void InitQueue(LinkQueue &Q)
{
	Q.front=Q.rear=(LinkNode *)malloc(sizeof(LinkNode)); 
	Q.front->next=NULL;
}
//队列判空:如果头、尾指针指向同一个结点或者头结点的next指向为NULL则为空
bool QueueEmpty(LinkQueue Q)
{
	return (Q.front->next==NULL);
	//return (Q.front=Q.rear);
}
//入队操作(带头结点)
void EnQueue(LinkQueue &Q,int x)
{
	//申请一个新的结点用于存储待插入的数据
	LinkNode * p=(LinkNode *)malloc(sizeof(LinkNode));
	p->data=x;
	//将新结点入队,即在队尾插入新结点
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
}
//出队操作(带头结点)
void DeQueue(LinkQueue &Q,int &x)
{
	LinkNode * p;
	p=Q.front->next;
	x=p->data;
	Q.front->next=p->next;
	//！！如果删除的元素为表尾结点,要将尾指针指向头结点
	if(Q.rear==p)Q.rear=Q.front;
	free(p);
}
//带头结点版本
int main(void)
{
	int x;
	LinkQueue Q;
	InitQueue(Q);
	printf("队列是否为空：%dn",QueueEmpty(Q));
	EnQueue(Q,2);
	printf("队列是否为空：%dn",QueueEmpty(Q));
	DeQueue(Q,x);
	printf("删除的元素为：%dn",x);
	printf("队列是否为空：%dn",QueueEmpty(Q));
	return 0;
}

代码语言：javascript复制

#include <stdio.h>
#include <stdlib.h>
//定义链式队列结点
typedef struct LinkNode
{
	int data;
	LinkNode * next;
}LinkNode;
//定义链式队列
typedef struct 
{
	LinkNode * front,* rear;
}LinkQueue;
//初始化队列（不带头结点）:使front、rear都指向NULL
void InitQueue1(LinkQueue &Q)
{
	Q.front=NULL;
	Q.rear=NULL;
}
//判断队列是否为空（不带头结点）
bool QueueEmpty1(LinkQueue Q)
{
	return (Q.front==NULL);
}
//入队操作(不带头结点)
void EnQueue1(LinkQueue &Q,int x)
{
	//申请一个结点用来存储入队数据
	LinkNode * p=(LinkNode *)malloc(sizeof(LinkNode));
	p->data=x;
	//执行入队操作
	p->next=NULL;
	if(Q.rear==NULL)
	{
		Q.front=p;
		Q.rear=p;
	}
	else
	{
		Q.rear->next=p;
		Q.rear=p;
	}
}
//出队操作(不带头结点)
void DeQueue1(LinkQueue &Q,int &x)
{
	LinkNode * p=Q.front;
	x=p->data;
	Q.front=p->next;
	//如果出队恰好使最后一个结点，那么要把rear恢复为NULL
	if(Q.rear==p)
		Q.rear=NULL;
	free(p);
}

int main(void)
{
	int x;
	LinkQueue Q;
	InitQueue1(Q);
	printf("队列是否为空：%dn",QueueEmpty1(Q));
	EnQueue1(Q,2);
	printf("队列是否为空：%dn",QueueEmpty1(Q));
	DeQueue1(Q,x);
	printf("删除的元素为：%dn",x);
	printf("队列是否为空：%dn",QueueEmpty1(Q));
	return 0;
}

3.栈和队列的应用

1）栈在括号匹配中的应用

（（（））），最后的左括号要优先匹配——栈

代码语言：javascript复制

#include <stdio.h>
#define MaxSize 10		
typedef struct
{
	char data[MaxSize];
	int top;
}SeqStack; 
//初始化栈
void InitStack(SeqStack &S)
{
	for(int i=0;i<MaxSize;i  )
	{
		S.data[i]=NULL;
	}
	S.top=-1; //指栈顶元素，初始时置为-1；
}
//判断栈是否为空
bool StackEmpty(SeqStack S)
{
	return S.top==-1;
}
//入栈
bool Push(SeqStack &S,char  x)
{
	if(S.top==MaxSize-1) return false;
	S.top  ;
	S.data[S.top]=x;
	return true;
}
//出栈
bool Pop(SeqStack &S,char &x)
{
	if(S.top==-1) return false;
	x=S.data[S.top];
	S.top--;
	return true;
}
//核心代码，这里为了结果直观，对不同匹配情况进行了打印，考试时可以不用，在调用Push、Pop等时对其简单
//注 释，可直接调用
bool BraketCheck(char Str[],SeqStack S)
{
	//判断是否有括号1
	for(int i=0;i<6;i  )
	{
		//判断是否有左括号
		if(Str[i]=='['||Str[i]=='(')
		{
			//左括号入栈
			Push(S,Str[i]);
		}
		else
		{
			//判断是否栈空
			if(!StackEmpty(S))
			{
				char b;
				Pop(S,b); //弹出栈顶元素b
				//判断括号是否匹配，
				if(Str[i]==')'&&b=='(') { printf("%c %cn",b,Str[i]);}
				else if(Str[i]==']'&&b=='['){ printf("%c %cn",b,Str[i]);}
				else 
				{
					printf("Failed!Different type of baracet!n");return false;
				}
			}
			else
			{
				 printf("Failed!Right Sigle.n"); return false;
			}
		}
	}
	if(StackEmpty(S)){printf("Sucess!n"); return true;}
	else{printf("Failed!Left Sigle!n");return true;}
}
//栈的应用——括号的匹配
int main(void)
{
	SeqStack S;
	InitStack(S);
	char Str[6]={'[','(',')',']',')',')'};
	BraketCheck(Str,S);
	return 0;
}

2）栈在表达式中的应用

后缀表达式的求值：

将后缀表达式依次压栈，遇到操作符号则弹出栈顶的两个元素，将其进行运算，先出栈的放在操作符右边；将运算的结果压栈。

代码语言：javascript复制

//算法思想：设置操作数栈OPND，运算符栈OPTR，依次扫描表达式，遇到操作数则进操作数栈，遇到运算符则栈顶元素与运算符栈比较，若栈顶元素优先级低，则进栈，若栈顶元素优先级高则出栈。特别的，界限符'(运算优先级级最高直接入栈，)'则依次弹出运算符栈的元素，直到遇到‘（’，同时弹出操作数栈顶两个元素，第一个元素在运算符后，第二个元素在运算符前进行运算，将运算的结果重新压入操作数栈。
OprandType EvaluateExpression(){
    InitStack(OPND); InitStack(OPTR);
    PUSH(OPTR,'#');
    ch=getchar();
    while(GetTop(OPTR)!='#'||ch!='#'){
        if(!In(ch,OP)) Push(OPND,ch);//不是运算符则进栈
        else
            switch(Precede(GetTop(OPTR),ch)){ //拿栈顶元素与其进行比较
                case '<' : 
                    Push(OPTR,ch);ch=getchar();
                    break;
                case '=': //(,)中间没有其他运算符，脱括号
                    Pop(OPTR,x); ch=getchar();
                    break;
                case '>':
                    Pop(OPTR,theta);
                    pop(OPND,b);pop(OPND,a);
            		Push(OPND,Opread(a,theta,b));
                    break;
            } //switch
    } //while
} //EvalueateExpression

3）进制转换

将十进制数N转换为8进制

代码语言：javascript复制

//算法思想：除8、取余倒排
void convention(int n){
    //初始化栈
    InitStack(S);
    //N除以8，取余数，余数入栈，n更新为商，直到商为0
    while(n>0){
    	 Push(S,n%8);
  		 n=n/8; 
    }
    for(!StackEmpty(S)){
        Pop(S,e);
        printf("%d",e);
    }
}

4.串

1）串的基本操作

代码语言：javascript复制

#include <stdio.h>
#define MaxSize 255
typedef struct 
{
	char ch[MaxSize];
	int len;
}MyString;
//从指定位序开始截取串的子串
bool SubString(MyString &Sub,MyString S,int pos,int len)
{
	if(pos len-1>S.len) return false; //子串范围越界
	for(int i=pos;i<pos len;i  )
	{
		Sub.ch[i-pos 1]=S.ch[i];
	}
	Sub.len=len;
	return true;
}
//比较两个串的大小
int CompareString(MyString S1,MyString S2)
{
	//逐个字符比较
	for(int i=1;i<=S1.len&&i<=S2.len;i  )
	{
		if(S1.ch[i]!=S2.ch[i]) return S1.ch[i]-S2.ch[i];	
	}
	//扫描过的字符皆相同，比较两字符串长度
	return S1.len-S2.len;
}
//定位子串
int indexString(MyString S,MyString Sub)
{
	//暂存截取串
	int i=1;
	MyString temp;
	temp.len=Sub.len;
	while(i<=S.len-Sub.len 1)
	{
		SubString(temp,S,i,Sub.len);
		if(CompareString(Sub,temp)!=0)   i;
		else return i;
	}
	return 0;
}
//串的基本操作
int main(void)
{
	MyString S1;
	S1.ch[0]=NULL;
	S1.ch[1]='w';
	S1.ch[2]='z';
	S1.len=2;
	MyString S2;
	S2.ch[0]=NULL;
	S2.ch[1]='z';
	S2.len=1;
	printf("%dn",indexString(S1,S2));
	return 0;
}

2）串的朴素模式匹配算法

代码语言：javascript复制

//串的朴素模式匹配算法
int Index(MyString S,MyString Sub)
{
	int i,j,k;//k用于定位S当前匹配到哪个位置,i,j分别用于S与Sub的活动定位
	k=1;
	i=k;
	j=1;
	while(S.len-k 1<=Sub.len)
	{
		if(S.ch[i]==Sub.ch[j])
		{
			  i;
			  j;
		}
		else
		{
			j=1;
			  k;
			i=k;
		}
		if(j>Sub.len) return k;
		else return 0;
	}
}

4、树

1.二叉树

1）树的顺序存储

代码语言：javascript复制

#include <stdio.h>
#define MaxSize 100
struct TreeNode{
	int value;
	bool isEmpty;
};

void InitTreeNode(TreeNode t[MaxSize])
{
	for(int i=0;i<MaxSize;i  ){
		t[i].isEmpty=true;
	}
}
void main(){
	TreeNode t[MaxSize];
	InitTreeNode(t);
}

2）树的链式存储

代码语言：javascript复制

typedef struct BiTreeNode{
	int value;
	BiTreeNode * rchild,* lchild;
}BiTreeNode,* BiTree;

//插入根节点
	BiTree root=(BiTree)malloc(sizeof(BiTreeNode));
	root->value=1;
	root->lchild=NULL;
	root->rchild=NULL;
	return true;

//插入新节点
	BiTreeNode * p=(BiTreeNode *)malloc(sizeof(BiTreeNode));
	p->value=2;
	p->lchild=NULL;
	p->rchild=NULL;
	root->lchild=p;
	return true;

//先序遍历
void PreOrder(BiTree T)
{
	if(T!=NULL)
	{
		Visit(T);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}

//求树的深度：后序的应用
int TreeDepth(BiTree T)
{
	if(T==NULL) return 0;
	int l=TreeDepth(T->lchild);
	int r=TreeDepth(T->rchild);
	return l>r?l 1:r 1;
}

//中序遍历（非递归实现）
bool InOrderTraverse(BiTree T)
{
    BiTreeNode * p=T; InitStack(S); //初始化一个栈
    while(p||!ISEmpty(S))
    {
        if(p){push(S,p);p=p->lchild;}
        else
        {
            pop(S,q);
            printf("%d,",q->data);
            p=q->rchild;
        }
    }
    return true;
}

3）二叉树的层次遍历

代码语言：javascript复制

//层次遍历
void LevelOrder(BiTree T)
{
	LinkQueue Q;
	InitQueue(Q);
	BiTree p; //用来存DeQueue后的树结点
	EnQueue(Q,T);
	while(!IsEmpty(Q))
	{
		DeQueue(Q,p);
		Visit(p);
		if(T->lchild!=NULL){EnQueue(Q,p->lchild);}
		if(T->rchild!=NULL){EnQueue(Q,p->rchild);}
	}
	
}

4）线索二叉树的构造

代码语言：javascript复制

#include <stdio.h>
//定义线索二叉树结点
typedef struct ThreadNode
{
	int data; //数据域存放二叉树数据
	ThreadNode * lchild,*rchild; //左右孩子
	int ltag,rtag; //左右孩子标志位
}ThreadNode,* ThreadTree;

ThreadNode * pre; //全局变量，当前结点的前驱结点

构造并中序线索化

代码语言：javascript复制

//访问某一个树结点同时进行线索化
void Visit(ThreadNode * p)
{
	if(p->lchild==NULL)
	{
		p->lchild=pre;
		p->ltag=1;
	}
	if(pre!=NULl&&pre->rchild==NULL)
	{
		pre->rchild=p; //建立前驱结点的后继线索
		pre->rtag=1;
	}
	pre=p; //把pre置为当前结点，当下一次调用visit时访问的pre就是当前结点（下一次遍历的前驱）
}
//二叉树中序遍历（并调用Visit进行线索化）
void InThread(ThreadTree T)
{
    if（T！=NULL）
    {
	 InThread(T->lchild);
	 Visit(T);
	 InThread(T->rchild);
    }
}

void CreateInThread(ThreadTree T)
{
    pre=NULL;
    if(T!=NULL)
    {
        InThread(T);
        if(pre->rchild==NULL) pre->rtag=1; //对最后一个结点进行特殊处理
    }  
}

构造并先序线索化（构造代码同上）

代码语言：javascript复制

//二叉树先序遍历（并调用Visit进行线索化）
void InThread(ThreadTree T)
{
    if（T！=NULL）
    {
    Visit(T);
    if（T->LTag==0）InThread(T->lchild); //!!!注意此处的判断条件，因为先序遍历访问顺序是根左右，如果根线索化了，无论根有没有左孩子，lchild都有指向，因此必须加此判断条件，判断其到底有没有左孩子
	InThread(T->rchild);
    }
}

5）线索二叉树的遍历

中序遍历

代码语言：javascript复制

//找到以p为根的子树中第一个被中序遍历的结点，即最左下的那个结点
ThreadNode * FirstNode(ThreadNode * p)
{
	while(p->ltag==0) p=p->lchild;
	return p;
}

//找到某个结点的后继节点
ThreadNode * NextNode(ThreadNode * p)
{
	if(p->rtag==1) return p->rchild;
	else if(p->rchild==0) return FirstNode(p->rchild); //返回右子树最左下的那个结点
}

void Inorder(ThreadTree * T)
{
    for(ThreadNode * p=FirstNode(T)；p!=NULL；p=NextNode(p)) //先找到第一个结点，然后不断的找其后继
        visit(p);
}

逆向中序遍历：从最后一个结点开始不断遍历其前驱即可。

6）平衡二叉树

代码语言：javascript复制

//平衡二叉树结点
typedef struct AVLNode
{
	int ket; //数据域
	int balance; //平衡因子
	struct AVLNode * lchild,* rchild;
}* AV

代码语言：javascript复制

//LL平衡旋转（右旋）
f->lchild=p->rchild;
p->rchild=f;
gf->lchild/rchild=p;

5、图

1.图的存储结构

1）数组表示法

代码语言：javascript复制

//-----图的组（邻接矩阵）存储表示-----
#define INFINITY INT_MAX //最大值∞
#define MAX_VERTEX_NUM 20 //最大的顶点个数
typedef enum {DG,DN,UDG,UDN}GraphKind; //{有向图（Digraph），有向网（DiNet），无向图(UniDigraph),无向网} 
typedef struct ArcCell{
    VRType adj; //VRType是顶点关系类型。对无权图，用1或者0表示相邻与否；对带权图，则为权值类型。
    InfoType *info; //该弧相关信息的指针
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{
    VertexType vexs[MAX_VERTEX_NUM]; //顶点向量
    AdjMatrix arcs; //邻接矩阵
    int vexnum,arcnum; //图的当前顶点数与边数
    GraphKind kind; //图的种类标志
}MGpraph

2）邻接表

代码语言：javascript复制

//---------图的邻接表存储表示-----------
#define MAX_VERTEX_NUM 20
typedef struct ArcNode{
    int adjvex; //该弧指向的顶点的位置
    struct ArcNode *nextarc; //指向下一条弧的指针
    InfoType *info; //该弧相关信息的指针
}ArcNode;
typedef struct VNode{
    VertexType data; //顶点信息
    ArcNode *firstarc;  //指向的一条依附该顶点的弧的指针
}VNode，AdjList[MAX_VERTEX_NUM]；
typedef struct{
	AdjList vertices;
	int vexnum,arcnum; //图的当前顶点数和弧数
	int kind; //图的种类
}

3）十字链表法

十字路口有方向，十字链表法是专门针对有向图设计的，旨在解决有向图用邻接表法找不到入度的这个问题。顶点结点包含三个域，数据域，firstin和firstout域分别指向第一个入度边，第一个出度边；边结点有五个域，尾域头域分别表示该弧的弧尾和弧头，链域tlink指向弧尾相同的下一条弧，hlink指向弧头相同的下一条弧，这样弧头相同的弧就在一个链表上，弧尾相同的弧也在一个链表上，info域指向该弧的相关信息。

2.图的遍历

1）广度优先遍历

代码语言：javascript复制

void BFSTraverse(Graph G,Status(*visit)(int v)){
    //按广度优先搜索遍历非递归遍历图G，使用辅助队列和访问标志数组visited
    for(v=0;v<G.vexnum;v  )	 visited[v]=FALSE;
    InitQueue(Q);
    for(v=0;v<G.vexnum;  v)
        if(!visited[v]){
        	visited[v]=True;
        	visit(v);
            EnQueue(Q,v);
            while(!QueueEmpty(Q)){
                DeQueue(Q,u);
                for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
                      if(!visited[w]){
                          visited[w]=True;
        				visit(w);
                		EnQueue(Q,w);
                      } //if
                } //while
        } //if
} //BFSTraverse

2）深度优先遍历

代码语言：javascript复制

void DFSTraverse(Graph G,Statues(* Visit)(int v)){
    for(v=0;v<G.vexnum;  v) visited[v]=FALSE;
    for(v=0;v<G.vexnum;  v){
        if(!visited[v]) DFS(G,v);
    }
}
void DFS(Graph G,int v){
    if(!visited[v]) {
        visit(G,v);
        visted[v]=TRUE;
    } //if
    while(w=FirstAdjVetex(G,v);w>=0;w=NextAdjVetex(G,v,w)){
        if(!visited[w]){
        	DFS(G,w);
        } //if 
    } //while
} //DFSTraverse

3.最小生成树（prim算法）

代码语言：javascript复制

//prim算法的思想：选择一个初始顶点，把它加入辅助数组，计算该顶点到其他顶点的代价，选择其中最小代价对应点加入辅助数组，扫描加入新的顶点有没有使其到各个顶点的代价变化，并更新代价数组；重复进行以上步骤，知道所有顶点都已经加入了辅助数组
//记录顶点集U到V-U的代价最小的边的辅助数组
struct{
    VertexType adjvex;
    VRType lowcost;
}closedge[MAX_VERTEX_NUM];

void MiniSpanTree_PRIM(MGraph G,VetexType u){
    //用prim算法从第v个顶点出发构造网的最小生成树T，并输出最小生成树的各条边
  	k=LocateVex(G,u);
    for(j=0;j<G.vexnum;j  ) //辅助数组初始化
        if(j!=k) closedge[j]={u,G.arcs[k][j].adj}; //{adjvex,lowcost}
    closedge[k].lowcost=0; //初始，U={u}
    for(i=1;i<G.vexnum;  i){ //选择其余G.vexnum-1个顶点
        k=minimum(closedge);  //求出T的下一个顶点:第k顶点
        printf(closedge[k].adjvex,G.vexs[k]);
        closedge[k].lowcost=0;
        for(j=0;j<G.vexnum;  j)
            if(G.arcs[k][j]).adj<closedge[j].lowcost)
                closedge[j]={G.vexs[k],G.arcs[k][j].adj};
    }
} //MiniSpanTree

4.最短路径

1）单源最短路径

BFS可用于求不带权的图的单源最短路径（课本上没有）

代码语言：javascript复制

bool viisted[Max_VeTex_num];

void BFS_Min_Distance(Graph G,int v){
    //BFS求无向图的单源最短路径
    for(int i=0;i<G.vexNum;i  ){
        d[i]=Inifinate; //最短路径大小
        path[i]=-1; //最短路径从哪里过来
    }
    d[v]=0; //起点到自己的距离置为0；
    visited[v]=true;
    EnQueue(Q,v);
    while(!IsEmpty(Q)){
        DeQueue(Q,v);
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
            if(!visited[w]){
                visited[w]=true;
                EnQueue(Q,w);
                d[w]=d[v] 1;
                path[w]=u;
              }
        }
    }
}

5.拓扑排序

代码语言：javascript复制

Status TopologicalOrder(ALGraph G,Stack &T){
    //有向网G采用邻接表存储结构，求各顶点事件最早发生时间ve（全局变量）
    //T为拓扑序列顶点栈，S为零入度顶点栈
    //若G无回路，则栈T返回G的一个拓扑序列，且函数值为OK，否则为ERROR
    FindInDegree(G,indegree); //对各顶点求入度indegree[0...vernum-1]
    InitStack(S)； //建立并初始化零入度顶点栈
    count=0;ve[0...G.vexnum-1]=0; //初始化
    while(!StackEmpty(S)){
        Pop(S,j); Push(T,j);  count; //j号顶点入T栈并计数
        for(p=G.vertices[j].firstarc;p;p->nextarc){
            k=p->adjvex; //对j号顶点的每个邻接点的入度减1
            if(--indgree[k]==0) Push(S,k); //若入度减为0，则入栈
            if(ve[j] *(p->info)>ve[k]) ve[k]=ve[j] *(p->info) ;
        }
    }
    if(count<G.vexnum) return ERROR; //该有向图有回路
    else retrun OK;
}

6、排序

1.插入排序

1）直接插入排序

代码语言：javascript复制

//直接插入排序，进行增序排序
void InsertSort(SqlList &L){
    //从第2个元素开始，进行i-1轮插入
    for(int i=2;i<=L.length;i  ){
        //如果待插入元素与之前元素比较已经属于有序，无需操作，否则执行操作
        if(L.r[i].key<L.r[i-1].key){
            //复制待插入元素为哨兵
            L.r[0]=L.r[i];
            for(int j=i-1;L.r[0].key<L.r[j].key;j--) //比待插入元素大的都往后移
                    L.r[j 1]=L.r[j];
            L.r[j]=L.r[0];
        } //if
    } //for
} //InsertSort

2）折半插入排序

代码语言：javascript复制

void BInsertSort(SeqList &L)
{
      //从第二个元素开始把待排序序列插入到有序序列
    for(int i=2;i<=L.length;i  )
    {
        L.r[0]=L.r[i]; 
        int low=1,high=i-1; //从第i-1个元素（有序序列的最后一个元素）开始往前找空
        while(low<=high){ //当low=high,还执行一次，将mid与low，high指向相同位置，并因此会执行else语句，使high 1位置为待插入元素的位置
             mid=(low high)/2;
             if(L.r[mid].key<L.r[0].key) low=mid 1;
       		 else high=mid-1;
        } //循环结束，high 1为插入位置
        for(int j=i-1;j>high 1;--j) L.r[j 1]=L.r[j];
        L.r[high 1]=L.r[0];
    }
}

3）希尔排序

代码语言：javascript复制

//一趟增量为dk的希尔排序
void ShellSort(SeqList &L,int dk){
    for(i=dk 1;i<=L.length;i  ){ //从dk 1个元素开始，把无序子序列的元素插入有序序列
        if(L.r[i]<L.r[i-dk]){ //当第i个元素比他前面子序列的元素要小，则执行，否则已经有序，无需操作
            L.r[0]=L.r[i]; //复制为哨兵
            for(j=i-dk;j>0&&(L.r[0].key<L.r[j].key);j-=dk) //比L.r[i]大的元素后移空位置
                L.r[j dk]=L.r[j];
             L.r[j]=L.r[0];
        }
    }
}

2.交换排序

1）冒泡排序

代码语言：javascript复制

void BubbleSort(SeqList &L){
    for(int i=0;i<L.length;i  ){
        flag=false; //用来记录一趟冒泡排序是否发生了交换
        for(int j=L.length;j>i;j--){
            if(L.r[j-1].key>L.r[j].key) //逆序：前面的比后面的大，则交换
            	{
                	swap(L.r[j-1],L.r[j]);
            		flag=true;
            	}
        }
        if(flag==false) return;
    }
}

2）快速排序

代码语言：javascript复制

void QuickSort(ElemType A[],int low,int high)
{
    if(low<high) //递归跳出条件
    {
        //partition()就是划分操作，将表A[low...high]划分为两个子表
        int pivotopos=partition(A,low,high); //划分
        QuickSort(A,low,privotopos-1); //依次对两个子表进行递归排序
        QuickSort(A,privotopos 1,high);
    }
}

代码语言：javascript复制

int Partition（SqlList &L,int low,int high){
    L.r[0]=L.r[low];
    privotkey=L.r[low].key;//将当前表中的第一个元素设置为枢轴值，将表进行划分
    while(low<high){ //循环跳出条件
        while(low<high&&L.r[high].key>=privotkey) --high;
        L.r[low]=L.r[high];
        while(low<high&&L.r[low].key<=prvotkey)   low;
        L.r[high]=L.r[low];
    }
    L.r[low]=L.r[0]; //枢轴纪录到位
    return low; //返回枢轴位置
}

3.选择排序

1）简单选择排序

代码语言：javascript复制

void SeclectSort(SeqList &L){
    for(int i=1;i<L.length;i  ){ //让i从1到n-1进行n-1趟选择排序（最后一个位置不用再选择了）
        min=i;
        for(j=i 1;j<L.length;j  ){
            if(L.r[j].key<L.r[min].key)
            	min=j;
        }
        if(min!=i) swap(L.r[i]=L.r[min]);
    }
}

2）堆排序

代码语言：javascript复制

void HeapSort(HeapType &H)
{
    //对顺序表进行堆排序
    for(i=H.length/2;i>0;--i) //从最后一个非叶子结点开始建立堆
        HeapAdjust(H,i,H.length); 
    for(i=H.length;i>1;--i){
         //...输出堆顶元素
         H.r[1]<-->H.r[i];  //将堆顶记录和最后一个记录交换
         HeapAdjust(H,1,i-1); //重新建堆
    }
}

void HeapAdjust(HeapAdjust &H,int s,int m){ //调整为大顶堆
    rc=H.r[s]; //暂存堆顶元素
    for(j=2*s;j<=m;j*=2){ //从上到下调整。让j指向堆顶左孩子，对其子树依次执行循环体（j*=2）
        if(j<m&&LT(H.r[j].key,H.r[j 1].key))   j; //如果左孩子小于右孩子，那么把j指右孩子，如果j==m，说明j已经是最后一个结点了，没有右孩子
        if(!LT(rc.key,H.r[j].key)) break; //比较堆顶与孩子结点大小，如果堆顶已经比孩子大，break；
        H.r[s]=H.r[j];  //否则，把堆顶置换为孩子结点元素 
        s=j; //对其子树进行判断调整，以调整由于之前置换导致的子树下坠情况
    }
    H.r[s]=rc; //把暂存的元素插入最后空出的位置
}

4.归并排序

代码语言：javascript复制

void Merge(RcdType SR[],RcdType TR[],int i,int m,int n){
    //两个有序子序列的归并，SR中存待归并数据，TR是数据暂存的临时空间，i是SR第一个序列开始，m是第1个子序列结尾位置，n是第2个子序列结束位置
    for(j=m 1,k=i;i<=m&&j<=n;  k){//j指向第二个子序列开始位置,k指向i指针对应位置（即让TR插入元素的起始位置与SR相同）
        if(LQ(SR[i].key,SR[j].key)) TR[k]=SR[i  ];
        else TR[k]=SR[j  ];
    }
    //判断哪个子序列还有剩余元素，全部复制到TR
    if(i<=m) TR[k...n]=SR[i...m]; //伪代码，可以用while循环实现
    if(j<=n) TR(k...n)=SR[j...n];
}

void MSort(RcdType SR[],RcdType &TR1[],int s,int t){
    if(s==t) TR1[s]=SR[s];
    else{
        m=s t/2;
        MSort(SR,TR2,s,m);
        MSort(SR,TR2,m 1,t);
        Merge(TR2,TR1,s,m,t);
    }
}

void MergeSort(SqlList &L){
    Msort(L.r,L.r,1,L.length);
}

        if(flag==false) return;
    }
}

5.快速排序

代码语言：javascript复制

void QuickSort(ElemType A[],int low,int high)
{
    if(low<high) //递归跳出条件
    {
        //partition()就是划分操作，将表A[low...high]划分为两个子表
        int pivotopos=partition(A,low,high); //划分
        QuickSort(A,low,privotopos-1); //依次对两个子表进行递归排序
        QuickSort(A,privotopos 1,high);
    }
}

代码语言：javascript复制

int Partition（SqlList &L,int low,int high){
    L.r[0]=L.r[low];
    privotkey=L.r[low].key;//将当前表中的第一个元素设置为枢轴值，将表进行划分
    while(low<high){ //循环跳出条件
        while(low<high&&L.r[high].key>=privotkey) --high;
        L.r[low]=L.r[high];
        while(low<high&&L.r[low].key<=prvotkey)   low;
        L.r[high]=L.r[low];
    }
    L.r[low]=L.r[0]; //枢轴纪录到位
    return low; //返回枢轴位置
}

二叉树 数据结构 size 遍历 链表

0 人点赞