在经过了一个学期的数据结构课程学习后，我对数据结构也有了一定的了解，因此在这里做个简单的小结

基础知识

数据结构的概念

逻辑结构
线性： 是指数据元素之间只存在一对一线性关系的数据结构
1. 集合中必存在唯一的一个”第一个元素”和”最后的元素”；
2. 除最后元素之外，其它数据元素均有唯一的”后继”；
3. 除第一元素之外，其它数据元素均有唯一的”前驱”。
  非线性： 是指数据元素之间不只存在一对一线性关系的数据结构
4. 一个结点元素可能对应多个直接前驱和多个后继；
5. 必定存在至少一个根节点。
储存结构
顺序顺序存储方法是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构，通常借助于程序设计语言中的数组来实现。
链式链接存储方法它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的，由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现。
索引除建立存储结点信息外，还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。
散列选取某个函数，依照改函数来计算元素的存储位置，形成函数值和存储位置之间的一一对应，例如hash函数。
抽象数据结构(ADT) 是指一个数学模型以及定义在该模型上的一组操作，通常可以用以下三元组表示(D,S,P)其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。在下文中，采用如下方式定义抽象数据类型
ADT 抽象数据类型名{
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<基本操作的定义>
}ADT 抽象数据类型名
其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为
基本操作名(参数表)
初始条件：<初始条件描述>
操作结果：<操作结果描述>
算法的概念
对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。
意义算法代表着用系统的方法描述解决问题的策略机制，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。
描述语言 通常采用伪代码
算法的评价
时间复杂度 算法的时间复杂度是指执行算法所需要的计算工作量。一般来说，计算机算法是问题规模n的函数f(n)，算法的时间复杂度也因此记做T(n)=Ο(f(n))
空间复杂度 算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。
正确性 算法应当满足具体问题的需求。
可读性 算法的可读性是指一个算法可供人们阅读的容易程度。
健壮性 健壮性是指一个算法对不合理数据输入的反应能力和处理能力，也称为容错性。
递归的概念
程序调用自身的编程技巧称为递归
规律一般来说，递归需要有边界条件、递归前进段和递归返回段。
结束当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

常见线性结构的应用

线性表抽象数据结构

ADT List{
数据对象:D={ $a_i$ | $a_i$∈ElemSet , i=1,2,···,n , n≥0 }
数据关系:R1={<$a_{i-1}$,$a_i$> | $a_{i-1}$ , $a_i$∈D , i=2,···,n}
基本操作:
InitList(&L)
初始条件：无
操作结果：构造一个空的线性表L。
DestoryList(&L)
初始条件：线性表L已存在
操作结果：销毁线性表L
ClearList(&L)
初始条件：线性表L已存在
操作结果：将线性表L重置为空表
ListEmpty(L)
初始条件：线性表L已存在
操作结果：若L为空表，则返回TRUE，否则返回FALSE
ListLength(L)
初始条件：线性表L已存在
操作结果：返回L中数据元素个数
GetElem(L,i,&e)
初始条件：线性表L已存在，1≤i≤ListLength(L)
操作结果：用e返回L中第i个数据元素的值
LocateElem(L,e,compare())
初始条件：线性表L已存在，compare()是数据元素判定函数
操作结果：返回L中第1个与e满足compare()的数据元素的位序。若这样的数据元素不存在，则返回值为0
PriorElem(L,cur_e,&pre_e)
初始条件：线性表L已存在
操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义
NextElem(L,cur_e,&next_e)
初始条件：线性表L已存在
操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义
ListInsert(&L,i,e)
初始条件：线性表L已存在，1≤i≤ListLength(L)+1
操作结果：在L中的第i个位置之前插入新的数据元素e，L的长度加1
ListDelete(&L,i,&e)
初始条件：线性表L已存在且非空，1≤i≤ListLength(L)
操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
ListTraverse(L,visit())
初始条件：线性表L已存在
操作结果：依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败
}ADT List

1.顺序表

1.1 顺序表的结构定义

#define LIST_INIT_SIZE 100
#define LISTINCREMENT  10
typedef struct {
	ElemType* elem;
	int length;
	int listsize;
}SqList;

1.2 构造空的顺序表

Status InitList_Sq(SqList &L) {
	L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
	if (!L.elem)
		return OK;
	L.length = 0;
	L.listsize = LIST_INIT_SIZE;
	return OK;
}

1.3 销毁顺序表

Status DestroyList_Sq(SqList &L){
	if (L.elem)
		free(L.elem);
	L.elem=NULL;
	return OK;
}

1.4 清空顺序表

Status ClearList_Sq(SqList &L){
	L.length = 0;
	return OK;
}

1.5 判断顺序表是否为空

1
2
3

Status ListEmpty_Sq(SqList L){
	return L.length == 0;
}

1.6 求顺序表的长度

1
2
3

int ListLength_Sq(SqList L){
	return (L.length);
}

1.7 返回顺序表中的第i个元素

Status GetElem_Sq(SqList L, int i, ElemType &e){
	if (i<1 || i>L.length)
		return ERROR;
	e = L.elem[i - 1];
	return OK;
}

1.8 在顺序线性表L中查找第1个值与e满足compare()的元素的位序

int LocateElem_Sq(SqList L, ElemType e, Status(*compare)(ElemType, ElemType)) {
	int i;
	ElemType* p;
	i = 1;
	p = L.elem;
	while (i <= L.length && !(*compare)(*p++, e))
		++i;
	if (i <= L.length)
		return i;
	else
		return 0;
}

1.9 返回一个不是首元素的前驱

Status PriorElem_Sq(SqList L, ElemType cur_e, ElemType &pre_e){
	int i = 2;
	if (cur_e == L.elem[0])
		return ERROR;
	while (i <= L.length && (L.elem[i - 1] != cur_e))
		i++;
	if (i == L.length + 1)
		return ERROR;
	else
		pre_e = L.elem[i - 2];
	return OK;
}

1.10 返回一个不是末元素的后继

Status NextElem_Sq(SqList L, ElemType cur_e, ElemType &next_e){
	//返回一个不是末元素的后继
	int i = 1;
	while (i < L.length && (L.elem[i - 1] != cur_e))
		i++;
	if (i == L.length)
		return ERROR;
	else next_e = L.elem[i];
	return OK;
}

1.11 在顺序线性表L的第i个元素之前插入新的元素e

Status ListInsert_Sq(SqList &L, int i, ElemType e) {
	ElemType* p;
	if (i < 1 || i > L.length+1)
		return ERROR;
	if (L.length >= L.listsize) {
		ElemType* newbase = (ElemType*)realloc(L.elem, (L.listsize+LISTINCREMENT) * sizeof (ElemType));
		if (!newbase)
			return ERROR;
		L.elem = newbase;
		L.listsize += LISTINCREMENT;
	}
	ElemType* q = &(L.elem[i-1]);
	for (p = &(L.elem[L.length - 1]); p >= q; --p)
		*(p + 1) = *p;
	*q = e;
	++L.length;
	return OK;
}

1.12 在顺序线性表L中删除第i个元素，并用e返回其值

Status ListDelete_Sq(SqList &L, int i, ElemType &e) {
	ElemType *p, *q;
	if (i<1 || i>L.length)
		return ERROR;
	p = &(L.elem[i - 1]);
	e = *p;
	q = L.elem + L.length - 1;
	for (++p; p <= q; ++p)
		*(p - 1) = *p;
	--L.length;
	return OK;
}

1.13 遍历顺序线性表

Status ListTraverse_Sq(SqList L, Status(*visit)(ElemType)){
	if (ListEmpty_Sq(L))return ERROR;
	for (int i = 0; i < L.length; i++){
		(*visit)(L.elem[i]);
	}
}

2.链表

2.1 链表数据结构的定义

typedef struct LNode{
	ElemType      data;
	struct LNode* next;
}* Link, * Position;
typedef struct {
	Link head, tail;
	int  len;
}LinkList;

2.2 分配结点并赋值为e

Status MakeNode(Link &p, ElemType e){
	p = (Link)malloc(sizeof(struct LNode));
	if (p){
		p->data = e;
		p->next = NULL;
	}
	else
		return ERROR;
	return OK;
}

2.3 释放p所指向的结点

1
2
3

void FreeNode(Link &p){
	free(p);
}

2.4 构造一个由L指向的空的线性表

Status InitList(LinkList &L){
	Link p = NULL;
	MakeNode(p, 0);
	if (!p) exit(ERROR);
	L.head = p;
	L.tail = NULL;
	L.len = 0;
	for (int i = 1; i <= 5; i++){
		Link s;
		ElemType e = i + '0';
		MakeNode(s, e);
		InsertElem(L, i, s);
	}
	return OK;
}

2.5 销毁由L指向的线性表

Status DestroyList(LinkList &L){
	Link p = NULL;
	Link t = NULL;
	p = L.head;
	while (p->next){
		t = p->next;
		FreeNode(p);
		p = t;
	}
	L.len = 0;
	return TRUE;
}

2.6 在链表L的第i个元素之前插入新的元素e

Status InsertElem(LinkList &L, int i, Link s){
	Link p;
	if (i < 1 || i > L.len + 1)
		return ERROR;
	p = L.head;
	i--;
	while (i){
		p = p->next;
		i--;
	}
	s->next = p->next;
	if (!p->next)
		L.tail = s;
	p->next = s;
	L.len++;
	return OK;
}

2.7 删除链表L的第i个元素

Status DeleteElem(LinkList &L, int i){
	Link p;
	if (i < 2 || i > L.len + 1)
		return ERROR;
	p = L.head;
	i -= 2;
	while (i){
		p = p->next;
		i--;
	}
	p->next = p->next->next;
	L.len--;
	return OK;
}

2.8 用e更新p所指向的当前结点

Status SetCurElem(Link &p, ElemType e){
	p->data = e;
	return OK;
}

2.9 返回p所指结点中元素的值

1
2
3

ElemType GetCurElem(Link p){
	return p->data;
}

2.10 返回p所指结点的直接前驱的位置

Position PriorPos(LinkList L, Link p){
	Link q;
	q = L.head;
	if (q->next == p)
		return NULL;
	while (q->next != p)
		q = q->next;
	return q;
}

2.11 用p返回线性表l中第i个结点的位置，并返回ok

Status LocatePos(LinkList L, int i, Link &p){
	p = L.head;
	if (i <= 0 || i > L.len)
		return ERROR;
	while (i){
		p = p->next;
		i--;
	}
	return OK;
}

2.12 用一个函数遍历表中所有结点

Status ListTraverse(LinkList L, Status(*visit)(ElemType)){
	Link p;
	int i = 0;
	if (!L.len)
		return ERROR;
	p = L.head->next;
	while (p && (*visit)(p->data) && (++i)){
		p = p->next;
		cout << ' ';
		if (i % 5 == 0) cout << endl;
	}
	if (p != NULL)
		return ERROR;
	return OK;
}

3.栈

3.1 顺序栈

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct {
	SElemType *base, *top;
	int stacksize;
}SqStack;
Status InitStack_Sq(SqStack &S);   //初始化栈
Status StackEmpty_Sq(SqStack S);         //栈是否为空
int StackLength_Sq(SqStack S);        //栈的长度
Status GetTop_Sq(SqStack S, SElemType &e);  //得到栈顶
Status Push_Sq(SqStack &S, SElemType e);   //压栈
Status Pop_Sq(SqStack &S, SElemType &e);   //出栈
Status InitStack_Sq(SqStack &S) {
	S.base = (SElemType*)malloc(STACK_INIT_SIZE*(sizeof(SElemType)));
	if (!S.base)
		exit(OVERFLOW);
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
	return OK;
}
Status StackEmpty_Sq(SqStack S) {
	if (S.base == S.top)
		return TRUE;
	else
		return FALSE;
}
int StackLength_Sq(SqStack S) {
	if (S.base == S.top)
		return ERROR;
	else
		return (S.top - S.base);
}
Status GetTop_Sq(SqStack S, SElemType &e) {
	if (StackEmpty_Sq(S))
		return ERROR;
	e = *(S.top - 1);
	return OK;
}
Status Push_Sq(SqStack &S, SElemType e) {
	if (S.top - S.base >= S.stacksize) {
		S.base = (SElemType*)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
		if (!S.base)exit(OVERFLOW);
		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREMENT;
	}
	*S.top++ = e;
	return OK;
}
Status Pop_Sq(SqStack &S, SElemType &e) {
	if (StackEmpty_Sq(S))
		return ERROR;
	e = *(--S.top);
	return OK;
}
Status StackTraverse_Sq(SqStack S) {
	//
	if (StackEmpty_Sq(S))
		return ERROR;
	for (SElemType *i = S.top - 1; i >= S.base; i--) {
		cout << *i << ' ';
	}
	cout << endl;
	return OK;
}

3.2 链栈

typedef struct SNode {
	SElemType data;
	SNode *next;
}*SLink, *SPosition;
typedef struct {
	SLink head, tail;
	int  len;
}LinkStack;
Status MakeNode(SLink &p, SElemType e) {
	//分配由p指向的结点并赋值为e
	p = (SLink)malloc(sizeof(SNode));
	if (p) {
		p->data = e;
		p->next = NULL;
	}
	else
		return ERROR;
	return OK;
}
Status InitStack_Link(LinkStack &L) {
	//构造一个由L指向的空的线性表
	SLink p = NULL;
	MakeNode(p, 0);
	if (!p) exit(ERROR);
	L.head = p;
	L.tail = NULL;
	L.len = 0;
	return OK;
}
Status Push_Link(LinkStack &L, SLink s) {
	//将s指向的结点插入线性链表的第一个结点之前
	s->next = L.head->next;
	if (!L.head->next)
		L.tail = s;
	L.head->next = s;
	L.len++;
	return OK;
}
Status Pop_Link(LinkStack &L, SLink &q) {
	//删除表中第一个结点并以q返回
	if (!L.head->next)
		return ERROR;
	q = L.head->next;
	L.head->next = L.head->next->next;
	L.len--;
	return OK;
}
Status GetTop_Link(LinkStack L, SElemType &e) {
	//获得栈顶节点的值
	if (!L.head->next)
		return ERROR;
	e = L.head->next->data;
	return OK;
}
Status StackTraverse_Link(LinkStack L) {
	//
	if (!L.head->next)
		return ERROR;
	SLink p;
	p = L.head->next;
	while (p) {
		cout << p->data << ' ';
		p = p->next;
	}
	cout << endl;
	return OK;
}

4.队列

4.1 循环队列

#define MAXSIZE 100

typedef struct {
	QElemType *base;
	int front, rear;
}SqQueue;
Status InitQueue_Sq(SqQueue &Q) {
	//初始化
	Q.base = (QElemType*)malloc(MAXSIZE * sizeof(QElemType));
	if (!Q.base)
		exit(OVERFLOW);
	Q.front = Q.rear = 0;
	return OK;
}
int QueueLength_Sq(SqQueue Q) {
	return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}
Status EnQueue_Sq(SqQueue &Q, QElemType e) {
	//插入
	if ((Q.rear + 1) % MAXSIZE == Q.front)
		return ERROR;
	Q.base[Q.rear] = e;
	Q.rear = (Q.rear + 1) % MAXSIZE;
	return OK;
}
Status DeQueue_Sq(SqQueue &Q, QElemType &e) {
	//删除
	if (Q.front == Q.rear)
		return ERROR;
	e = Q.base[Q.front];
	Q.front = (Q.front + 1) % MAXSIZE;
	return OK;
}
Status GetTop_Sq(SqQueue Q, QElemType &e) {
	//获取队首元素
	if (Q.front == Q.rear)
		return ERROR;
	e = Q.base[Q.front];
	return OK;
}
Status QueueTraverse_Sq(SqQueue Q) {
	if (Q.front == Q.rear)
		return ERROR;
	for (int a = Q.front; Q.base[a] && (a != Q.rear); a = (a + 1) % MAXSIZE) {
		cout << Q.base[a] << ' ';
	}
	cout << endl;
	return OK;
}

4.2 链队列

typedef struct QNode {
	QElemType data;
	QNode *next;
}QNode, *QueuePtr;
typedef struct {
	QueuePtr front, rear;
}LinkQueue;
Status InitQueue_Link(LinkQueue &Q);//构造一个空队列Q
Status QueueEmpty_Link(LinkQueue Q);//若Q为空队列，则返回TRUE，否则返回FALSE
int QueueLength_Link(LinkQueue Q);//求队列的长度
Status GetHead_Link(LinkQueue Q, QElemType &e);//若队列不空，则用e返回Q的队头元素，并返回OK，否则返回ERROR
Status EnQueue_Link(LinkQueue &Q, QElemType e);//插入元素e为Q的新的队尾元素
Status DeQueue_Link(LinkQueue &Q, QElemType &e);//若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR
Status InitQueue_Link(LinkQueue &Q) {
	// 构造一个空队列Q   
	Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
	if (!Q.front)
		exit(OVERFLOW);
	Q.front->next = NULL;
	return OK;
}
Status QueueEmpty_Link(LinkQueue Q) {
	// 若Q为空队列，则返回TRUE，否则返回FALSE   
	if (Q.front->next == NULL)
		return TRUE;
	else
		return FALSE;
}
int QueueLength_Link(LinkQueue Q) {
	// 求队列的长度   
	int i = 0;
	QueuePtr p;
	p = Q.front;
	while (Q.rear != p) {
		i++;
		p = p->next;
	}
	return i;
}
Status GetHead_Link(LinkQueue Q, QElemType &e) {
	// 若队列不空，则用e返回Q的队头元素，并返回OK，否则返回ERROR   
	QueuePtr p;
	if (QueueEmpty_Link(Q))
		return ERROR;
	p = Q.front->next;
	e = p->data;
	return OK;
}
Status EnQueue_Link(LinkQueue &Q, QElemType e) {
	// 插入元素e为Q的新的队尾元素   
	QueuePtr p;
	p = (QueuePtr)malloc(sizeof(QNode));
	if (!p)
		exit(OVERFLOW);
	p->data = e;
	p->next = NULL;
	Q.rear->next = p;
	Q.rear = p;
	return OK;
}
Status DeQueue_Link(LinkQueue &Q, QElemType &e) {
	// 若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR   
	QueuePtr p;
	if (QueueEmpty_Link(Q))
		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;
}
Status QueueTraverse_Link(LinkQueue Q) {
	if(QueueEmpty_Link(Q))
		return ERROR;
	QueuePtr p = Q.front->next;
	while (p) {
		cout << p->data << ' ';
		p = p->next;
	}
	cout << endl;
	return OK;
}

5.串

typedef struct{
	char *ch;
	int length;
}HString;
void InitString(HString &T);//初始化(产生空串)字符串T
Status StrAssign(HString &T, char *chars);//生成一个其值等于串常量chars的串T
Status StrCopy(HString &T, HString S);//复制串S
Status StrEmpty(HString S);//判断串S是否为空
int StrLength(HString S);//返回S的元素个数，称为串的长度
int StrCompare(HString S, HString T);//若S>T，则返回>0；若S<T，则返回<0；若S=T，则返回=0
Status ClearString(HString &S);//将S清空
Status Concat(HString &T, HString S1, HString S2);//链接两个串
Status SubString(HString &Sub, HString S, int pos, int len);//返回串S的第pos个字符起长度为len的子串
int Index(HString S, HString T, int pos);//返回主串S存在的pos位置之后第一次出现的子串T的位置
Status Replace(HString &S, HString T, HString V);//用V替换S中所有T
Status StrInsert(HString &S, int pos, HString T);//S中pos后插入T
Status StrDelete(HString &S, int pos, int len);//S中pos后删除len个字符

void InitString(HString &T){
	T.length = 0;
	T.ch = NULL;
}
Status StrAssign(HString &T, char *chars){
	int i, j;
	if (T.ch)
		free(T.ch);
	i = strlen(chars);
	if (!i)	{
		T.ch = NULL;
		T.length = 0;
	}
	else{
		T.ch = (char*)malloc(i*sizeof(char));
		if (!T.ch)
			exit(OVERFLOW);
		for (j = 0; j<i; j++)
			T.ch[j] = chars[j];
		T.length = i;
	}
	return OK;
}
Status StrCopy(HString &T, HString S){ /* 初始条件:串S存在。操作结果: 由串S复制得串T */
	int i;
	if (T.ch)
		free(T.ch);
	T.ch = (char*)malloc(S.length*sizeof(char));
	if (!T.ch)
		exit(OVERFLOW);
	for (i = 0; i<S.length; i++)
		T.ch[i] = S.ch[i];
	T.length = S.length;
	return OK;
}
Status StrEmpty(HString S){ /* 初始条件: 串S存在。操作结果: 若S为空串,则返回TRUE,否则返回FALSE */
	if (S.length == 0 && S.ch == NULL)
		return TRUE;
	else
		return FALSE;
}
int StrCompare(HString S, HString T){ /* 若S>T,则返回值>0;若S=T,则返回值=0;若S<T,则返回值<0 */
	int i;
	for (i = 0; i < S.length && i < T.length; ++i)
		if (S.ch[i] != T.ch[i])
			return S.ch[i] - T.ch[i];
	return S.length - T.length;
}
int StrLength(HString S){ /* 返回S的元素个数,称为串的长度 */
	return S.length;
}
Status ClearString(HString &S){ /* 将S清为空串 */
	if (S.ch){
		free(S.ch);
		S.ch = NULL;
	}
	S.length = 0;
	return OK;
}
Status Concat(HString &T, HString S1, HString S2){ /* 用T返回由S1和S2联接而成的新串 */
	int i;
	if (T.ch)
		free(T.ch);
	T.length = S1.length + S2.length;
	T.ch = (char *)malloc(T.length*sizeof(char));
	if (!T.ch)
		exit(OVERFLOW);
	for (i = 0; i<S1.length; i++)
		T.ch[i] = S1.ch[i];
	for (i = 0; i<S2.length; i++)
		T.ch[S1.length + i] = S2.ch[i];
	return OK;
}
Status SubString(HString &Sub, HString S, int pos, int len){
	int i;
	if (pos<1 || pos>S.length || len<0 || len>S.length - pos + 1)
		return ERROR;
	if (Sub.ch)
		free(Sub.ch);
	if (!len){
		Sub.ch = NULL;
		Sub.length = 0;
	}
	else{
		Sub.ch = (char*)malloc(len*sizeof(char));
		if (!Sub.ch)
			exit(OVERFLOW);
		for (i = 0; i <= len - 1; i++)
			Sub.ch[i] = S.ch[pos - 1 + i];
		Sub.length = len;
	}
	return OK;
}
int Index(HString S, HString T, int pos){
	int n, m, i;
	HString sub;
	InitString(sub);
	if (pos>0){
		n = StrLength(S);
		m = StrLength(T);
		i = pos;
		while (i <= n - m + 1){
			SubString(sub, S, i, m);
			if (StrCompare(sub, T) != 0)
				++i;
			else
				return i;
		}
	}
	return 0;
}
int Index_KMP(HString S, HString T, int pos) {
	// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的
	int *next = (int *)malloc((T.length + 1) * sizeof(int));
	int i = 1;
	next[1] = 0;
	int j = 0;
	while (i<T.length) {
		if (j == 0 || T.ch[i] == T.ch[j]) {
			++i;
			++j;
			next[i] = j;
		}
		else j = next[j];
	}
	i = pos;
	j = 1;
	while (i < S.length && j < T.length) {
		if (j == 0 || S.ch[i] == T.ch[j]) {
			++i;
			++j;
		}
		else j = next[j];
	}
	if (j >= T.length) return  i - (T.length - 1);
	else return 0;
}
Status StrInsert(HString &S, int pos, HString T){
	int i;
	if (pos<1 || pos>S.length + 1)
		return ERROR;
	if (T.length){
		S.ch = (char*)realloc(S.ch, (S.length + T.length)*sizeof(char));
		if (!S.ch)
			exit(OVERFLOW);
		for (i = S.length - 1; i >= pos - 1; --i)
			S.ch[i + T.length] = S.ch[i];
		for (i = 0; i<T.length; i++)
			S.ch[pos - 1 + i] = T.ch[i];
		S.length += T.length;
	}
	return OK;
}
Status StrDelete(HString &S, int pos, int len){
	int i;
	if (S.length<pos + len - 1)
		exit(ERROR);
	for (i = pos - 1; i <= S.length - len; i++)
		S.ch[i] = S.ch[i + len];
	S.length -= len;
	S.ch = (char*)realloc(S.ch, S.length*sizeof(char));
	return OK;
}
Status Replace(HString &S, HString T, HString V){
	int i = 1;
	if (StrEmpty(T))
		return ERROR;
	do
	{
		i = Index(S, T, i);
		if (i)
		{
			StrDelete(S, i, StrLength(T));
			StrInsert(S, i, V);
			i += StrLength(V);
		}
	} while (i);
	return OK;
}
void StrPrint(HString T){
	int i;
	for (i = 0; i<T.length; i++)
		printf("%c", T.ch[i]);
	printf("\n");
}

6.数组(十字链表实现)

typedef struct Node {//十字链表的节点
	int i, j;
	ElemType e;
	Node *down, *right;
}OLNode, *OLink;
class SMatrix_OL {
private:
	OLink *rhead, *chead;//十字链表行指针、列指针
	int mu, nu, tu;//十字链表所表示矩阵的行数mu、列数nu、非零元个数tu
public:
	SMatrix_OL(int m = 0, int n = 0, int t = 0);//构造矩阵，即声明szlb类的同时传入行数、列数、非零元个数、并进行相应的初始化
	Status InsertOLNode(OLNode *p);//节点的插入
	Status DeleteOLNode(int i, int j, OLNode *e);//节点的删除 。。。 暂时并没有什么卵用
	OLink GetRHead(int i) { // 获得行指针数组的头指针
		return rhead[i];
	}
	OLink GetCHead(int i) { // 获得列指针数组的头指针
		return chead[i];
	}
	int GetMu() { return mu; } //这个，以及下面两个 分别获得矩阵的行数mu、列数nu、非零元个数tu
	int GetNu() { return nu; }
	int GetTu() { return tu; }
	Status Create(); // 创建十字链表
	SMatrix_OL Transpose(); // 转置十字链表，返回值为 转置后的链表类
	SMatrix_OL operator+(SMatrix_OL b);
	void Output(); // szlb的输出
};//szlb
SMatrix_OL::SMatrix_OL(int m, int n, int t) {
	mu = m;
	nu = n;
	tu = t;
	rhead = (OLink *)malloc((m + 1) * sizeof(OLink));
	chead = (OLink *)malloc((n + 1) * sizeof(OLink));
	for (int x = 1; x <= m; x++)
		rhead[x] = NULL;
	for (int y = 1; y <= n; y++)
		chead[y] = NULL;
}//SMatrix_OL()
void MakeNode(int i, int j, ElemType e, OLNode *p) { // 创建节点的函数，就是将相应的值赋值给相应的变量
	p->i = i;
	p->j = j;
	p->e = e;
	p->down = NULL;
	p->right = NULL;
}//MakeNode()
Status SMatrix_OL::InsertOLNode(OLNode *p) { //根据书上算法实现的节点插入
	int i = p->i, j = p->j;
	OLNode *q;
	//行插入
	if (rhead[i] == NULL || rhead[i]->j > j) {
		p->right = rhead[i];
		rhead[i] = p;
	}//if
	else {
		for (q = rhead[i]; (q->right) && (q->right->j < j); q = q->right);//获取插入位置的前一个节点
		if ((q->right) && (q->right->j == j))return ERROR;
		p->right = q->right;
		q->right = p;
	}//else
	//列插入
	if (chead[j] == NULL || chead[j]->i > i) {
		p->down = chead[j];
		chead[j] = p;
	}//if
	else {
		for (q = chead[j]; (q->down) && (q->down->i < i); q = q->down);//获取插入位置的前一个节点
		if ((q->down) && (q->down->i == i))return ERROR;
		p->down = q->down;
		q->down = p;
	}//else
	tu++;//非零元个数加一
	return OK;
}//InsertOLNode()
Status SMatrix_OL::DeleteOLNode(int i, int j, OLNode *e) { // ：） 随便看看就好
	OLNode *p, *q;
	if (rhead[i] == NULL || rhead[i]->j > j || chead[j] == NULL || chead[j]->i > i) return ERROR;
	else {
		for (q = rhead[i]; (q->right) && (q->right->j < j); q = q->right)p = q;
		if ((q->right) && (q->right->j == j)) {
			q->right = q->right->right;
		}//if
		else return ERROR;
		for (q = chead[j]; (q->down) && (q->down->i < i); q = q->down);
		if ((q->down) && (q->down->i == i)) {
			q->down = q->down->down;
		}//if
		else return ERROR;
	}//else
	return OK;
}//DeleteOLNode()
Status SMatrix_OL::Create() {
	int m, n, t;
	OLNode *p;
	int i, j;
	ElemType e;
	cout << "请分别输入m,n,t";
	cin >> m >> n >> t;
	mu = m;
	nu = n;
	if (!(rhead = (OLink *)malloc((m + 1) * sizeof(OLink)))) return ERROR;
	if (!(chead = (OLink *)malloc((n + 1) * sizeof(OLink)))) return ERROR;
	for (int x = 1; x <= m; x++)
		rhead[x] = NULL;
	for (int y = 1; y <= n; y++)
		chead[y] = NULL;
	for (int z = 1; z <= t; z++) {
		cout << "请分别输入i,j,e";
		cin >> i >> j >> e;
		if (!(p = (OLNode *)malloc(sizeof(OLNode)))) return ERROR;
		MakeNode(i, j, e, p);
		InsertOLNode(p);
	}//for
	return OK;
}//Create()
SMatrix_OL SMatrix_OL::Transpose() { // 转置函数
	SMatrix_OL b(nu, mu);
	OLNode *p, *q;
	int i, j;
	ElemType e;
	for (int x = 1; x <= nu; x++) {
		q = chead[x];
		while (q) {
			p = (OLNode *)malloc(sizeof(OLNode));
			i = q->j;
			j = q->i;
			e = q->e;
			MakeNode(i, j, e, p);
			b.InsertOLNode(p);
			q = q->down;
		}//while
	}//for
	return b;
}// Transpose()
SMatrix_OL SMatrix_OL::operator+(SMatrix_OL b) {//实现十字链表表示的矩阵的相加
	SMatrix_OL c(mu, nu);
	OLNode *p, *q, *r;
	int i, j;
	ElemType e;
	for (int x = 1; x <= mu; x++) {
		p = rhead[x];
		q = b.GetRHead(x);
		while (p || q) {
			r = (OLNode *)malloc(sizeof(OLNode));
			i = x;
			if (!q || (p && p->j < q->j)) {
				j = p->j;
				e = p->e;
				MakeNode(i, j, e, r);
				p = p->right;
			}//if
			else if (!p || (q && p->j > q->j)) {
				j = q->j;
				e = q->e;
				MakeNode(i, j, e, r);
				q = q->right;
			}//else if
			else {
				j = p->j;
				e = p->e + q->e;
				MakeNode(i, j, e, r);
				p = p->right;
				q = q->right;
			}//else
			if (e == 0)continue;
			c.InsertOLNode(r);
		}//while
	}//for
	return c;
}//operator+()

常见非线性结构的应用

1.二叉树

1.1 二叉树的定义与遍历

typedef struct BiTNode {
	TElemType data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
Status CreateBiTree(BiTree &T);//先序创建二叉树
Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType));//先序遍历二叉树
Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType));//中序遍历二叉树
Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType));//后序遍历二叉树
Status LevelOrderTraverse(BiTree T, Status(*Visit)(TElemType));//层序遍历二叉树
Status CreateBiTree(BiTree &T) {
	TElemType ch;
	if (cin.peek() == ' ') {
		cin.get();
		T = NULL;
	}
	else {
		cin >> ch;
		if (!(T = (BiTNode*)malloc(sizeof(BiTNode))))return ERROR;
		T->data = ch;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
	return OK;
}
Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType)) {
	if (T) {
		if (Visit(T->data))
			if (PreOrderTraverse(T->lchild, Visit))
				if (PreOrderTraverse(T->rchild, Visit))
					return OK;
		return ERROR;
	}
	else return OK;
}
Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType)) {
	if (T) {
		if (InOrderTraverse(T->lchild, Visit))
			if (Visit(T->data))
				if (InOrderTraverse(T->rchild, Visit))
					return OK;
		return ERROR;
	}
	else return OK;
}
Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType)) {
	if (T) {
		if (PostOrderTraverse(T->lchild, Visit))
			if (PostOrderTraverse(T->rchild, Visit))
				if (Visit(T->data))
					return OK;
		return ERROR;
	}
	else return OK;
}
Status LevelOrderTraverse(BiTree T, Status(*Visit)(TElemType)) {
	if (!T)return ERROR;
	deque<BiTree> Qh, Ql;
	BiTree t;
	Ql.push_back(T);
	do {
		Qh.swap(Ql);
		Ql.clear();
		while (!Qh.empty()) {
			t = Qh.front();
			Qh.pop_front();
			if (t) {
				Visit(t->data);
				if (t->lchild)Ql.push_back(t->lchild);
				if (t->rchild)Ql.push_back(t->rchild);
			}
		}
	} while (!Ql.empty());
	return OK;
}
Status PrintElement(TElemType e) {
	printf("%c ", e);
	return OK;
}
Status Swap(BiTree &T) {
	if (T) {
		Swap(T->lchild);
		Swap(T->rchild);
		BiTree tmp = T->lchild;
		T->lchild = T->rchild;
		T->rchild = tmp;
	}
	return OK;
}

1.2 二叉树的应用

typedef struct BiTNode {
	TElemType data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
Status CreateBiTree(BiTree &T);//先序创建二叉树
int GetLevesNum(BiTree T);//叶子结点数
int GetNonlevesNum(BiTree T);//非叶子结点数
int GetAllNum(BiTree T);//所有结点数
int Depth(BiTree T);//树的深度
Status SearchFromTree(BiTree T, TElemType value);//查找
Status OutputAllPath(BiTree T);//输出所有到叶节点的路径
Status CreateBiTree(BiTree &T) {
	TElemType ch;
	if (cin.peek() == ' ' || cin.peek() == 13) {
		cin.get();
		T = NULL;
	}
	else {
		cin >> ch;
		if (!(T = (BiTNode*)malloc(sizeof(BiTNode))))return ERROR;
		T->data = ch;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
	return OK;
}
int GetLevesNum(BiTree T) {
	if (!T)return 0;
	else if (!T->lchild && !T->rchild)return 1;
	else return GetLevesNum(T->lchild) + GetLevesNum(T->rchild);
}
int GetNonlevesNum(BiTree T) {
	if (!T || (!T->lchild && !T->rchild))return 0;
	else return GetNonlevesNum(T->lchild) + GetNonlevesNum(T->rchild) + 1;
}
int GetAllNum(BiTree T) {
	if (!T)return 0;
	else return GetAllNum(T->lchild) + GetAllNum(T->rchild) + 1;
}
int Depth(BiTree T) {
	int hl, hr;
	if (!T)return 0;
	if (T && (!T->lchild && !T->rchild))return 1;
	else {
		hl = Depth(T->lchild);
		hr = Depth(T->rchild);
		if (hl > hr)return hl + 1;
		else return hr + 1;
	}
}
Status SearchFromTree(BiTree T, TElemType value) {
	if (T) {
		if (T->data == value) {
			return OK;
		}
		else {
			return SearchFromTree(T->lchild, value) || SearchFromTree(T->rchild, value);
		}
	}
	return ERROR;
}
Status GetAllPath(BiTree T, BiTree *path, int pathLen) {
	if (!T)
		return OK;
	path[pathLen] = T;
	pathLen++;
	if (!T->lchild && !T->rchild) {
		for (int i = 0; i < pathLen; i++)
			cout << path[i]->data;
		cout << endl;
	}
	else {
		GetAllPath(T->lchild, path, pathLen);
		GetAllPath(T->rchild, path, pathLen);
	}
	return OK;
}
Status OutputAllPath(BiTree T) {
	BiTree *path = (BiTree*)malloc(Depth(T) * sizeof(BiTree));
	GetAllPath(T, path, 0);
	return OK;
}

1.3赫夫曼树

struct HTNode {        // 树中结点的结构  
	unsigned int weight;
	unsigned int parent, lchild, rchild;
};
struct HTCode {
	char data;      // 待编码的字符  
	int weight;     // 字符的权值  
	char *code;   // 字符的编码  
};
void Init(HTCode *hc, int n) {
	// 初始化，读入待编码字符的个数n，从键盘输入n个字符和n个权值  
	int i;
	cout << "请输入" << n << " 个字符" << endl;
	for (i = 1; i <= n; ++i)
		cin >> hc[i].data;
	cout << "请按顺序输入" << n << "个字符的权重" << endl;
	for (i = 1; i <= n; ++i)
		cin >> hc[i].weight;
}
void Select(HTNode *ht, int k, int &s1, int &s2) {
	// ht[1...k]中选择parent为0，并且weight最小的两个结点，其序号由指针变量s1，s2指示
	int i;
	for (i = 1; i <= k && ht[i].parent != 0; ++i) {
		; ;
	}
	s1 = i;
	for (i = 1; i <= k; ++i) {
		if (ht[i].parent == 0 && ht[i].weight<ht[s1].weight)
			s1 = i;
	}
	for (i = 1; i <= k; ++i) {
		if (ht[i].parent == 0 && i != s1)
			break;
	}
	s2 = i;
	for (i = 1; i <= k; ++i) {
		if (ht[i].parent == 0 && i != s1 && ht[i].weight<ht[s2].weight)
			s2 = i;
	}
}
void HuffmanCoding(HTNode *ht, HTCode *hc, int n) {
	// 构造Huffman树ht，并求出n个字符的编码
	char *cd = (char*)malloc(n * sizeof(char));
	int i, m, c, f, s1, s2, start;
	m = 2 * n - 1;
	for (i = 1; i <= m; ++i) {
		if (i <= n)
			ht[i].weight = hc[i].weight;
		else
			ht[i].weight = 0;
		ht[i].parent = ht[i].lchild = ht[i].rchild = 0;
	}
	for (i = n + 1; i <= m; ++i) {
		Select(ht, i - 1, s1, s2);
		ht[s1].parent = i;
		ht[s2].parent = i;
		ht[i].lchild = s1;
		ht[i].rchild = s2;
		ht[i].weight = ht[s1].weight + ht[s2].weight;
	}
	cd[n - 1] = '\0';
	for (i = 1; i <= n; ++i) {
		start = n - 1;
		for (c = i, f = ht[i].parent; f; c = f, f = ht[f].parent) {
			if (ht[f].lchild == c)
				cd[--start] = '0';
			else
				cd[--start] = '1';
		}
		hc[i].code = (char*)malloc((n - start + 1) * sizeof(char));
		strcpy(hc[i].code, &cd[start]);
	}
}
int main(){
	int i, n;
	HTNode *ht;
	HTCode *hc;
	cout << "请输入字符个数 n = ";
	cin >> n;
	hc = (HTCode*)malloc((n + 1) * sizeof(HTCode));
	ht = (HTNode *)malloc((2 * n) * sizeof(HTNode));
	Init(hc, n); // 初始化
	HuffmanCoding(ht, hc, n); // 构造Huffman树，并形成字符的编码
	cout << endl;
	for (i = 1; i <= n; ++i)
		cout << hc[i].data << "-----" << hc[i].code << endl;
	return 0;
}

2.图

typedef int Status;
#define MAX_VERTEX_NUM 20		//最大顶点个数
typedef char VertexType;		//顶点类型
typedef int InfoType;			//边的信息 权重
typedef int VRType;				//顶点关系，无权图中的邻接与否，带权图中的权值
typedef int VisitIf;		//访问标志 0 未访问 >0 已访问
typedef int GraphKind;		//{有向图=0，有向网=1，无向图=2，无向网=3}
//
//图的数组表示“邻接矩阵”
#define INFINITY INT_MAX		//最大值
typedef struct ArcCell {
	VRType adj; //VRType是顶点关系类型。对于无权图，用1或0表示相邻否；对带权图，则为权值类型。
	char * info;//该弧相关信息的指针
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵
typedef struct {
	VertexType vexs[MAX_VERTEX_NUM]; //顶点向量
	VisitIf visited[MAX_VERTEX_NUM];
	AdjMatrix arcs;                  //邻接矩阵
	int vexnum, arcnum;               //图的当前顶点数和弧数
	GraphKind kind;                  //图的种类标志
}MGraph;
Status CreateGraph(MGraph &G);//邻接矩阵建图
int LocateVex(MGraph G, VertexType u);//确认位置
VertexType FirstAdjVex(MGraph G, VertexType v);//返回v的第一个邻接顶点。
VertexType NextAdjVex(MGraph G, VertexType v, VertexType w);//返回v的（相对于w的）下一个邻接顶点。
Status CreateDG(MGraph &G);//邻接矩阵建有向图
Status CreateDN(MGraph &G);//邻接矩阵建有向网
Status CreateUDG(MGraph &G);//邻接矩阵建无向图
Status CreateUDN(MGraph &G);//邻接矩阵建无向网
Status DFSTraverse(MGraph G, Status(*Visit)(VertexType));//对图进行深度优先遍历。
Status BFSTraverse(MGraph G, Status(*Visit)(VertexType));//对图进行广度优先遍历。
typedef struct {
	VertexType  adjvex;
	VRType     lowcost;
}ClosEdge;
typedef struct {
	VertexType *adjvex;
	int len;
}VexSet;
typedef struct {
	int i, j;
	VRType adj;
}ArcSet;
Status MiniSpanTree_PRIM(MGraph G, VertexType u);//用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边
Status MiniSpanTree_KRUSKAL(MGraph G);//用克鲁斯卡尔算法构造网G的最小生成树T，输出T的各条边
//
//图的邻接表表示
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 vexs;
	VisitIf visited[MAX_VERTEX_NUM];
	int vexnum, arcnum;			//图的当前顶点数和弧数
	int kind;					//图的种类标志
}ALGraph;						//图的结构
Status InsertArcToGraph(ALGraph &G, int i, ArcNode *u);//将边插入
Status CreateGraph(ALGraph &G);//邻接矩阵建图
int LocateVex(ALGraph G, VertexType u);//确认位置
VertexType FirstAdjVex(ALGraph G, VertexType v);//返回v的第一个邻接顶点。
VertexType NextAdjVex(ALGraph G, VertexType v, VertexType w);//返回v的（相对于w的）下一个邻接顶点。
Status CreateDG(ALGraph &G);//邻接表建有向图
Status CreateDN(ALGraph &G);//邻接表建有向网
Status CreateUDG(ALGraph &G);//邻接表建无向图
Status CreateUDN(ALGraph &G);//邻接表建无向网
Status DFSTraverse(ALGraph G, Status(*Visit)(VertexType));//对图进行深度优先遍历。
Status BFSTraverse(ALGraph G, Status(*Visit)(VertexType));//对图进行广度优先遍历。
//
//有向图的十字链表表示
typedef struct ArcBox {
	int tailvex, headvex;
	ArcBox *hlink, *tlink;
	InfoType *info;
}ArcBox;
typedef struct VexNode {
	VertexType data;
	ArcBox *firstin, *firstout;
}VexNode;
typedef struct {
	VexNode xlist[MAX_VERTEX_NUM];
	VisitIf visited[MAX_VERTEX_NUM];
	int vexnum, arcnum;
}OLGraph;
Status CreateGraph(OLGraph &G);//十字链表建图
Status CreateDG(OLGraph &G);//十字链表建有向图
int LocateVex(OLGraph G, VertexType u);//确认位置
VertexType FirstAdjVex(OLGraph G, VertexType v);//返回v的第一个邻接顶点。
VertexType NextAdjVex(OLGraph G, VertexType v, VertexType w);//返回v的（相对于w的）下一个邻接顶点。
Status DFSTraverse(OLGraph G, Status(*Visit)(VertexType));//对图进行深度优先遍历。
Status BFSTraverse(OLGraph G, Status(*Visit)(VertexType));//对图进行广度优先遍历。
//
//无向图的邻接多重表表示
typedef struct EBox {
	VisitIf mark;			//访问标记
	int ivex, jvex;			//该边依附的两个顶点的位置
	EBox *ilink, *jlink;	//分别指向依附这两个顶点的下一条边
	InfoType *info;			//该边信息指针
}EdgeBox;
typedef struct VexBox {
	VertexType data;
	EdgeBox *firstedge;		//指向第一条依附该顶点的边
}VexBox;
typedef struct {
	VisitIf visited[MAX_VERTEX_NUM];
	VexBox adjmulist[MAX_VERTEX_NUM];
	int vexnum, edgenum;	//无向图的当前顶点数和边数
}AMLGraph;
Status CreateGraph(AMLGraph &G);//邻接多重表建图
Status CreateUDG(AMLGraph &G);//邻接多重表建无向图
int LocateVex(AMLGraph G, VertexType u);//确认位置
VertexType FirstAdjVex(AMLGraph G, VertexType v);//返回v的第一个邻接顶点。
VertexType NextAdjVex(AMLGraph G, VertexType v, VertexType w);//返回v的（相对于w的）下一个邻接顶点。
Status DFSTraverse(AMLGraph G, Status(*Visit)(VertexType));//对图进行深度优先遍历。
Status BFSTraverse(AMLGraph G, Status(*Visit)(VertexType));//对图进行广度优先遍历。

Status CreateGraph(MGraph &G) {
	cout << "请选择要创建的图的类型：" << endl << "有向图\t0\n有向网\t1\n无向图\t2\n无向网\t3\n";
	cin >> G.kind;
	switch (G.kind) {
	case 0:return CreateDG(G);
	case 1:return CreateDN(G);
	case 2:return CreateUDG(G);
	case 3:return CreateUDN(G);
	default:return ERROR;
	}
}
int LocateVex(MGraph G, VertexType u) {
	for (int i = 0; i < G.vexnum; i++)
		if (G.vexs[i] == u)return i;
	return -1;
}
VertexType FirstAdjVex(MGraph G, VertexType v) {
	int i = LocateVex(G, v), j;
	if (G.kind == 0 || G.kind == 2)
		for (j = 0; j < G.vexnum && G.arcs[i][j].adj == 0; j++);
	else if (G.kind == 1 || G.kind == 3)
		for (j = 0; j < G.vexnum && G.arcs[i][j].adj == INFINITY; j++);
	if (j == G.vexnum)return -1;
	return G.vexs[j];
}
VertexType NextAdjVex(MGraph G, VertexType v, VertexType w) {
	int i = LocateVex(G, v), j = LocateVex(G, w) + 1;
	if (G.kind == 0 || G.kind == 2)
		for (; j < G.vexnum && G.arcs[i][j].adj == 0; j++);
	else if (G.kind == 1 || G.kind == 3)
		for (; j < G.vexnum && G.arcs[i][j].adj == INFINITY; j++);
	if (j == G.vexnum)return -1;
	return G.vexs[j];
}
Status CreateDG(MGraph &G) {
	int i, j, k;
	VertexType  v1, v2;
	cout << "请输入顶点的数目：";
	cin >> G.vexnum;
	cout << "请输入弧的数目：";
	cin >> G.arcnum;
	for (i = 0; i<G.vexnum; i++) {
		cout << "请输入第" << i + 1 << "个顶点";
		cin >> G.vexs[i];
	}
	for (i = 0; i<G.vexnum; ++i)
		for (j = 0; j<G.vexnum; ++j) {
			G.arcs[i][j].adj = 0;
			G.arcs[i][j].info = NULL;
		}
	for (k = 0; k<G.arcnum; ++k) {
		cout << "请输入起始点 (字符)：";
		cin >> v1;
		cout << "请输入终止点 (字符)：";
		cin >> v2;
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);
		G.arcs[i][j].adj = 1;
	}
	return OK;
}
Status CreateDN(MGraph &G) {
	int i, j, k, w;
	VertexType  v1, v2;
	cout << "请输入顶点的数目：";
	cin >> G.vexnum;
	cout << "请输入弧的数目：";
	cin >> G.arcnum;
	for (i = 0; i<G.vexnum; i++) {
		cout << "请输入第" << i + 1 << "个顶点";
		cin >> G.vexs[i];
	}
	for (i = 0; i<G.vexnum; ++i)
		for (j = 0; j<G.vexnum; ++j) {
			G.arcs[i][j].adj = INFINITY;
			G.arcs[i][j].info = NULL;
		}
	for (k = 0; k<G.arcnum; ++k) {
		cout << "请输入起始点 (字符)：";
		cin >> v1;
		cout << "请输入终止点 (字符)：";
		cin >> v2;
		cout << "请输入权值：";
		cin >> w;
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);
		G.arcs[i][j].adj = w;
	}
	return OK;
}
Status CreateUDG(MGraph &G) {
	int i, j, k;
	VertexType  v1, v2;
	cout << "请输入顶点的数目：";
	cin >> G.vexnum;
	cout << "请输入边的数目：";
	cin >> G.arcnum;
	for (i = 0; i<G.vexnum; i++) {
		cout << "请输入第" << i + 1 << "个顶点";
		cin >> G.vexs[i];
	}
	for (i = 0; i<G.vexnum; ++i)
		for (j = 0; j<G.vexnum; ++j) {
			G.arcs[i][j].adj = 0;
			G.arcs[i][j].info = NULL;
		}
	for (k = 0; k<G.arcnum; ++k) {
		cout << "请输入起始点 (字符)：";
		cin >> v1;
		cout << "请输入终止点 (字符)：";
		cin >> v2;
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);
		G.arcs[i][j].adj = 1;
		G.arcs[j][i].adj = G.arcs[i][j].adj;
	}
	return OK;
}
Status CreateUDN(MGraph &G) {
	int i, j, k, w;
	VertexType  v1, v2;
	cout << "请输入顶点的数目：";
	cin >> G.vexnum;
	cout << "请输入边的数目：";
	cin >> G.arcnum;
	for (i = 0; i<G.vexnum; i++) {
		cout << "请输入第" << i + 1 << "个顶点 (字符)";
		cin >> G.vexs[i];
	}
	for (i = 0; i<G.vexnum; ++i)
		for (j = 0; j<G.vexnum; ++j) {
			G.arcs[i][j].adj = INFINITY;
			G.arcs[i][j].info = NULL;
		}
	for (k = 0; k<G.arcnum; ++k) {
		cout << "请输入起始点 (字符)：";
		cin >> v1;
		cout << "请输入终止点 (字符)：";
		cin >> v2;
		cout << "请输入权值：";
		cin >> w;
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);
		G.arcs[i][j].adj = w;
		G.arcs[j][i].adj = G.arcs[i][j].adj;
	}
	return OK;
}
void DFS(MGraph &G, VertexType v, Status(*Visit)(VertexType)) {
	G.visited[LocateVex(G, v)] = 1;
	Visit(v);
	for (VertexType w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))
		if (G.visited[LocateVex(G, w)] == 0)
			DFS(G, w, Visit);
}
Status DFSTraverse(MGraph G, Status(*Visit)(VertexType)) {
	cout << "图的深度优先遍历：";
	for (int i = 0; i < G.vexnum; ++i)
		G.visited[i] = 0;
	for (int v = 0; v < G.vexnum; ++v)
		if (G.visited[v] == 0)
			DFS(G, G.vexs[v], Visit);
	cout << endl;
	return OK;
}
Status BFSTraverse(MGraph G, Status(*Visit)(VertexType)) {
	cout << "图的广度优先遍历：";
	VertexType v, w;
	queue<VertexType> Q;
	VertexType u;
	for (int i = 0; i<G.vexnum; ++i) G.visited[i] = 0;
	for (int i = 0; i < G.vexnum; ++i)
		if (G.visited[i] == 0) {
			v = G.vexs[i];
			G.visited[i] = 1;
			Visit(v);
			Q.push(v);
			while (!Q.empty()) {
				u = Q.front();
				Q.pop();
				for (w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w))
					if (G.visited[LocateVex(G, w)] == 0) {
						G.visited[LocateVex(G, w)] = 1;
						Visit(w);
						Q.push(w);
					}
			}
		}
	cout << endl;
	return OK;
}
int minimum(ClosEdge *clos, int num) {
	int min, tag = 0;
	for(int i = 0;i < num;i++){
		if (clos[i].lowcost > 0) {
			if (tag == 0) tag = 1, min = i;
			else min = clos[i].lowcost < clos[min].lowcost ? i : min;
		}
	}
	return min;
}
Status MiniSpanTree_PRIM(MGraph G, VertexType u) {
	cout << "普里姆算法生成最小生成树：" << endl;
	ClosEdge closedge[MAX_VERTEX_NUM];
	int i, j, k;
	k = LocateVex(G, u);
	for (j = 0; j<G.vexnum; ++j) {
		if (j != k) {
			closedge[j].adjvex = u;
			closedge[j].lowcost = G.arcs[k][j].adj;
		}
	}
	closedge[k].lowcost = 0;
	for (i = 1; i<G.vexnum; ++i) {
		k = minimum(closedge, G.vexnum);
		cout << closedge[k].adjvex << ' ' << G.vexs[k] << endl;
		closedge[k].lowcost = 0;
		for (j = 0; j<G.vexnum; ++j)
			if (G.arcs[k][j].adj < closedge[j].lowcost) {
				closedge[j].adjvex = G.vexs[k];
				closedge[j].lowcost = G.arcs[k][j].adj;
			}
	}
	return OK;
}
void UnionSet(VexSet *vex,int i,int j, int num) {
	VexSet *v = new VexSet;
	v->len = vex[i].len + vex[j].len;
	v->adjvex = new VertexType[v->len];
	for (int k = 0; k < v->len; k++) {
		if (k < vex[i].len)v->adjvex[k] = vex[i].adjvex[k];
		else v->adjvex[k] = vex[j].adjvex[k - vex[i].len];
	}
	for (int k = 0; k < num; k++) {
		if (k != i && k != j) {
			if (vex[k].adjvex == vex[i].adjvex || vex[k].adjvex == vex[j].adjvex)
				vex[k].adjvex = v->adjvex;
		}
	}
	vex[i].adjvex = vex[j].adjvex = v->adjvex;
}
int comp(ArcSet a1, ArcSet a2) {
	return a1.adj < a2.adj;
}
Status MiniSpanTree_KRUSKAL(MGraph G) {
	cout << "克鲁斯卡尔算法生成最小生成树：" << endl;
	VexSet *vex = new VexSet[G.vexnum];
	ArcSet *arc = new ArcSet[G.arcnum];
	int i, j, k = 0, l;
	for (i = 0; i < G.vexnum; i++)
		for (j = i; j < G.vexnum; j++)
			if (G.arcs[i][j].adj > 0 && G.arcs[i][j].adj != INFINITY) {
				arc[k].i = i;
				arc[k].j = j;
				arc[k].adj = G.arcs[i][j].adj;
				k++;
			}
	sort(arc, arc + G.arcnum, comp);
	for (i = 0; i < G.vexnum; i++) {
		vex[i].len = 1;
		vex[i].adjvex = new VertexType;
		*(vex[i].adjvex) = G.vexs[i];
	}
	for (l = 0,k = 1; k < G.vexnum; k++) {
		i = arc[l].i;
		j = arc[l].j;
		l++;
		if (vex[i].adjvex != vex[j].adjvex) {
			cout << G.vexs[i] << " " << G.vexs[j] << endl;
			UnionSet(vex, i, j, G.vexnum);
		}
		else
			k--;
	}
	return OK;
}

Status CreateGraph(ALGraph & G) {
	cout << "请选择要创建的图的类型：" << endl << "有向图\t0\n有向网\t1\n无向图\t2\n无向网\t3\n";
	cin >> G.kind;
	switch (G.kind) {
	case 0: return CreateDG(G);
	case 1: return CreateDN(G);
	case 2: return CreateUDG(G);
	case 3: return CreateUDN(G);
	default:return ERROR;
	}
	return OK;
}
Status InsertArcToGraph(ALGraph &G, int i, ArcNode *u) {
	ArcNode *p = G.vexs[i].firstarc;
	if (!p) {
		u->nextarc = p;
		G.vexs[i].firstarc = u;
	}
	else{
		while (p->nextarc && p->nextarc->adjvex < u->adjvex)p = p->nextarc;
		u->nextarc = p->nextarc;
		p->nextarc = u;
	}
	return OK;
}
int LocateVex(ALGraph G, VertexType u) {
	for (int i = 0; i < G.vexnum; i++)
		if (G.vexs[i].data == u)return i;
	return -1;
}
VertexType FirstAdjVex(ALGraph G, VertexType v) {
	int i = LocateVex(G, v);
	if (G.vexs[i].firstarc == NULL)return -1;
	return G.vexs[G.vexs[i].firstarc->adjvex].data;
}
VertexType NextAdjVex(ALGraph G, VertexType v, VertexType w) {
	int i = LocateVex(G, v);
	ArcNode *p = G.vexs[i].firstarc;
	while (p) {
		if (G.vexs[p->adjvex].data == w)break;
		p = p->nextarc;
	}
	if (p->nextarc == NULL)return -1;
	return G.vexs[p->nextarc->adjvex].data;
}
Status CreateDG(ALGraph & G) {
	int i, j, k;
	VertexType  v1, v2;
	ArcNode *p;
	cout << "请输入顶点的数目：";
	cin >> G.vexnum;
	cout << "请输入边的数目：";
	cin >> G.arcnum;
	for (i = 0; i < G.vexnum; i++) {
		cout << "请输入第" << i + 1 << "个顶点 (字符)";
		cin >> G.vexs[i].data;
		G.vexs[i].firstarc = NULL;
	}
	for (k = 0; k<G.arcnum; k++) {
		cout << "请输入起始点 (字符)：";
		cin >> v1;
		cout << "请输入终止点 (字符)：";
		cin >> v2;
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);
		p = (ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex = j;
		p->info = NULL;
		InsertArcToGraph(G, i, p);
	}
	return OK;
}
Status CreateDN(ALGraph & G) {
	int i, j, k, w;
	VertexType  v1, v2;
	ArcNode *p;
	cout << "请输入顶点的数目：";
	cin >> G.vexnum;
	cout << "请输入边的数目：";
	cin >> G.arcnum;
	for (i = 0; i < G.vexnum; i++) {
		cout << "请输入第" << i + 1 << "个顶点 (字符)";
		cin >> G.vexs[i].data;
		G.vexs[i].firstarc = NULL;
	}
	for (k = 0; k<G.arcnum; k++) {
		cout << "请输入起始点 (字符)：";
		cin >> v1;
		cout << "请输入终止点 (字符)：";
		cin >> v2;
		cout << "请输入权值：";
		cin >> w;
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);
		p = (ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex = j;
		p->info = new int();
		*(p->info) = w;
		InsertArcToGraph(G, i, p);
	}
	return OK;
}
Status CreateUDG(ALGraph & G) {
	int i, j, k;
	VertexType  v1, v2;
	ArcNode *p;
	cout << "请输入顶点的数目：";
	cin >> G.vexnum;
	cout << "请输入边的数目：";
	cin >> G.arcnum;
	for (i = 0; i < G.vexnum; i++) {
		cout << "请输入第" << i + 1 << "个顶点 (字符)";
		cin >> G.vexs[i].data;
		G.vexs[i].firstarc = NULL;
	}
	for (k = 0; k<G.arcnum; k++) {
		cout << "请输入起始点 (字符)：";
		cin >> v1;
		cout << "请输入终止点 (字符)：";
		cin >> v2;
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);
		p = (ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex = j;
		p->info = NULL;
		InsertArcToGraph(G, i, p);
		p = (ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex = i;
		p->info = NULL;
		InsertArcToGraph(G, j, p);
	}
	return OK;
}
Status CreateUDN(ALGraph & G) {
	int i, j, k, w;
	VertexType  v1, v2;
	ArcNode *p;
	cout << "请输入顶点的数目：";
	cin >> G.vexnum;
	cout << "请输入边的数目：";
	cin >> G.arcnum;
	for (i = 0; i < G.vexnum; i++) {
		cout << "请输入第" << i + 1 << "个顶点 (字符)";
		cin >> G.vexs[i].data;
		G.vexs[i].firstarc = NULL;
	}
	for (k = 0; k<G.arcnum; k++) {
		cout << "请输入起始点 (字符)：";
		cin >> v1;
		cout << "请输入终止点 (字符)：";
		cin >> v2;
		cout << "请输入权值：";
		cin >> w;
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);
		p = (ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex = j;
		p->info = new int();
		*(p->info) = w;
		InsertArcToGraph(G, i, p);
		p = (ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex = i;
		p->info = new int();
		*(p->info) = w;
		InsertArcToGraph(G, j, p);
	}
	return OK;
}
void DFS(ALGraph &G, VertexType v, Status(*Visit)(VertexType)) {
	G.visited[LocateVex(G, v)] = 1;
	Visit(v);
	for (VertexType w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))
		if (G.visited[LocateVex(G, w)] == 0)
			DFS(G, w, Visit);
}
Status DFSTraverse(ALGraph G, Status(*Visit)(VertexType)) {
	cout << "图的深度优先遍历：";
	for (int i = 0; i < G.vexnum; ++i)
		G.visited[i] = 0;
	for (int v = 0; v < G.vexnum; ++v)
		if (G.visited[v] == 0)
			DFS(G, G.vexs[v].data, Visit);
	cout << endl;
	return OK;
}
Status BFSTraverse(ALGraph G, Status(*Visit)(VertexType)) {
	cout << "图的广度优先遍历：";
	VertexType v, w;
	queue<VertexType> Q;
	VertexType u;
	for (int i = 0; i<G.vexnum; ++i) G.visited[i] = 0;
	for (int i = 0; i < G.vexnum; ++i)
		if (G.visited[i] == 0) {
			v = G.vexs[i].data;
			G.visited[i] = 1;
			Visit(v);
			Q.push(v);
			while (!Q.empty()) {
				u = Q.front();
				Q.pop();
				for (w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w))
					if (G.visited[LocateVex(G, w)] == 0) {
						G.visited[LocateVex(G, w)] = 1;
						Visit(w);
						Q.push(w);
					}
			}
		}
	cout << endl;
	return OK;
}

Status CreateGraph(OLGraph &G) {
	return CreateDG(G);
}
Status CreateDG(OLGraph & G) {
	int i, j, k;
	VertexType  v1, v2;
	ArcBox *p;
	cout << "请输入顶点的数目：";
	cin >> G.vexnum;
	cout << "请输入边的数目：";
	cin >> G.arcnum;
	for (i = 0; i < G.vexnum; ++i) {
		cout << "请输入第" << i + 1 << "个顶点 (字符)";
		cin >> G.xlist[i].data;
		G.xlist[i].firstin = G.xlist[i].firstout = NULL;
	}
	for (k = 0; k < G.arcnum; ++k) {
		cout << "请输入起始点 (字符)：";
		cin >> v1;
		cout << "请输入终止点 (字符)：";
		cin >> v2;
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);
		p = (ArcBox *)malloc(sizeof(ArcBox));
		p->headvex = i;
		p->tailvex = j;
		p->hlink = G.xlist[i].firstout;
		p->tlink = G.xlist[j].firstin;
		p->info = NULL;
		G.xlist[j].firstin = G.xlist[i].firstout = p;
	}
	return OK;
}
int LocateVex(OLGraph G, VertexType u) {
	for (int i = 0; i < G.vexnum; i++)
		if (G.xlist[i].data == u)return i;
	return -1;
}
VertexType FirstAdjVex(OLGraph G, VertexType v) {
	int i = LocateVex(G, v);
	if (G.xlist[i].firstout == NULL)return -1;
	return G.xlist[G.xlist[i].firstout->tailvex].data;
}
VertexType NextAdjVex(OLGraph G, VertexType v, VertexType w) {
	int i = LocateVex(G, v);
	ArcBox *p = G.xlist[i].firstout;
	while (p) {
		if (G.xlist[p->tailvex].data == w)break;
		p = p->hlink;
	}
	if (p->hlink == NULL)return -1;
	return G.xlist[p->hlink->tailvex].data;
}
void DFS(OLGraph &G, VertexType v, Status(*Visit)(VertexType)) {
	G.visited[LocateVex(G, v)] = 1;
	Visit(v);
	for (VertexType w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))
		if (G.visited[LocateVex(G, w)] == 0)
			DFS(G, w, Visit);
}
Status DFSTraverse(OLGraph G, Status(*Visit)(VertexType)) {
	cout << "图的深度优先遍历：";
	for (int i = 0; i < G.vexnum; ++i)
		G.visited[i] = 0;
	for (int v = 0; v < G.vexnum; ++v)
		if (G.visited[v] == 0)
			DFS(G, G.xlist[v].data, Visit);
	cout << endl;
	return OK;
}
Status BFSTraverse(OLGraph G, Status(*Visit)(VertexType)) {
	cout << "图的广度优先遍历：";
	VertexType v, w;
	queue<VertexType> Q;
	VertexType u;
	for (int i = 0; i<G.vexnum; ++i) G.visited[i] = 0;
	for (int i = 0; i < G.vexnum; ++i)
		if (G.visited[i] == 0) {
			v = G.xlist[i].data;
			G.visited[i] = 1;
			Visit(v);
			Q.push(v);
			while (!Q.empty()) {
				u = Q.front();
				Q.pop();
				for (w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w))
					if (G.visited[LocateVex(G, w)] == 0) {
						G.visited[LocateVex(G, w)] = 1;
						Visit(w);
						Q.push(w);
					}
			}
		}
	cout << endl;
	return OK;
}

Status CreateGraph(AMLGraph &G) {
	return CreateUDG(G);
}
Status CreateUDG(AMLGraph & G) {
	int i, j, k;
	VertexType  v1, v2;
	EdgeBox *p;
	cout << "请输入顶点的数目：";
	cin >> G.vexnum;
	cout << "请输入边的数目：";
	cin >> G.edgenum;
	for (i = 0; i < G.vexnum; i++) {
		cout << "请输入第" << i + 1 << "个顶点 (字符)";
		cin >> G.adjmulist[i].data;
		G.adjmulist[i].firstedge = NULL;
	}
	for (k = 0; k<G.edgenum; k++) {
		cout << "请输入起始点 (字符)：";
		cin >> v1;
		cout << "请输入终止点 (字符)：";
		cin >> v2;
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);
		p = (EdgeBox*)malloc(sizeof(EdgeBox));
		p->ivex = i;
		p->jvex = j;
		p->ilink = G.adjmulist[i].firstedge;
		p->jlink = G.adjmulist[j].firstedge;
		G.adjmulist[i].firstedge = p;
		G.adjmulist[j].firstedge = p;
		p->info = NULL;
	}
	return OK;
}
int LocateVex(AMLGraph G, VertexType u) {
	for (int i = 0; i < G.vexnum; i++)
		if (G.adjmulist[i].data == u)return i;
	return -1;
}
VertexType FirstAdjVex(AMLGraph G, VertexType v) {
	int i = LocateVex(G, v);
	if (G.adjmulist[i].firstedge == NULL)return -1;
	if (G.adjmulist[i].firstedge->ivex == i)
		return G.adjmulist[G.adjmulist[i].firstedge->jvex].data;
	else return G.adjmulist[G.adjmulist[i].firstedge->ivex].data;
}
VertexType NextAdjVex(AMLGraph G, VertexType v, VertexType w) {
	int i = LocateVex(G, v), j;
	EdgeBox *p = G.adjmulist[i].firstedge;
	while (p) {
		if (p->ivex == i) {
			j = p->jvex;
			p = p->ilink;
		}
		else {
			j = p->ivex;
			p = p->jlink;
		}
		if (G.adjmulist[j].data == w)
			break;
	}
	if (p == NULL)return -1;
	if (p->ivex == i)
		return G.adjmulist[p->jvex].data;
	else return G.adjmulist[p->ivex].data;
}
void DFS(AMLGraph &G, VertexType v, Status(*Visit)(VertexType)) {
	G.visited[LocateVex(G, v)] = 1;
	Visit(v);
	for (VertexType w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))
		if (G.visited[LocateVex(G, w)] == 0)
			DFS(G, w, Visit);
}
Status DFSTraverse(AMLGraph G, Status(*Visit)(VertexType)) {
	cout << "图的深度优先遍历：";
	for (int i = 0; i < G.vexnum; ++i)
		G.visited[i] = 0;
	for (int v = 0; v < G.vexnum; ++v)
		if (G.visited[v] == 0)
			DFS(G, G.adjmulist[v].data, Visit);
	cout << endl;
	return OK;
}
Status BFSTraverse(AMLGraph G, Status(*Visit)(VertexType)) {
	cout << "图的广度优先遍历：";
	VertexType v, w;
	queue<VertexType> Q;
	VertexType u;
	for (int i = 0; i<G.vexnum; ++i) G.visited[i] = 0;
	for (int i = 0; i < G.vexnum; ++i)
		if (G.visited[i] == 0) {
			v = G.adjmulist[i].data;
			G.visited[i] = 1;
			Visit(v);
			Q.push(v);
			while (!Q.empty()) {
				u = Q.front();
				Q.pop();
				for (w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w))
					if (G.visited[LocateVex(G, w)] == 0) {
						G.visited[LocateVex(G, w)] = 1;
						Visit(w);
						Q.push(w);
					}
			}
		}
	cout << endl;
	return OK;
}

散列储存结构

哈希(Hash)表

特殊运算

1.查找

typedef struct {
	KeyType key;
}ElemType;
#define EQ(a,b) ((a) == (b))
#define LT(a,b) ((a) < (b))
#define LQ(a,b) ((a) <= (b))
typedef struct {
	ElemType *elem;
	int length;
}SSTable;
Status Create(SSTable &ST, int n);
int Search_Seq(SSTable ST, KeyType key);
int Search_Bin(SSTable ST, KeyType key);
Status Create(SSTable &ST, int n) {
	ST.elem = (ElemType*)malloc((n + 1) * sizeof(ElemType));
	ST.length = n;
	for (int i = 1; i <= n; i++) {
		cout << "请顺序输入第" << i << "个元素:";
		cin >> ST.elem[i].key;
	}
	return OK;
}
int Search_Seq(SSTable ST, KeyType key) {
	int i;
	ST.elem[0].key = key;
	for (i = ST.length; !EQ(ST.elem[i].key, key); --i);
	return i;
}
int Search_Bin(SSTable ST, KeyType key) {
	int low = 1, high = ST.length, mid;
	while (low <= high) {
		mid = (low + high) / 2;
		if (EQ(key, ST.elem[mid].key)) return mid;
		else if (LT(key, ST.elem[mid].key)) high = mid - 1;
		else low = mid + 1;
	}
	return 0;
}

2.排序

#define EQ(a,b) ((a) == (b))
#define LT(a,b) ((a) < (b))
#define LQ(a,b) ((a) <= (b))
#define MT(a,b) ((a) > (b))
#define MQ(a,b) ((a) >= (b))
typedef struct {
}InfoType;
typedef struct {
	KeyType key;
	InfoType otherinfo;
}RedType;
typedef struct {
	RedType *r;
	int length;
}SqList;
Status CreateList(SqList &L) {
	cout << "请输入顺序表的长度" << endl;
	cin >> L.length;
	L.r = new RedType[L.length + 1];
	for (int i = 1; i <= L.length; i++) {
		cout << "请输入第" << i << "个元素的关键字：";
		cin >> L.r[i].key;
	}
	return OK;
}
void PrintList(SqList L) {
	for (int i = 1; i <= L.length; i++)
		cout << L.r[i].key << " ";
	cout << endl;
}
Status InsertSort(SqList &L) {
	int i, j, n;
	n = 0;
	for (i = 2; i <= L.length; i++) {
		if (LT(L.r[i].key, L.r[i - 1].key)) {
			L.r[0] = L.r[i];
			L.r[i] = L.r[i - 1];
			for (j = i - 2; LT(L.r[0].key, L.r[j].key); j--) L.r[j + 1] = L.r[j];
			L.r[j + 1] = L.r[0];
		}
		cout << "第" << ++n << "趟排序后" << endl;
		PrintList(L);
	}
	return OK;
}
Status BubbleSort(SqList &L) {
	int i, j, k, n;
	k = L.length;
	n = 0;
	while (1) {
		i = k;
		for (j = 1; j < i; j++) {
			if (LT(L.r[j + 1].key, L.r[j].key)) {
				L.r[0] = L.r[j];
				L.r[j] = L.r[j + 1];
				L.r[j + 1] = L.r[0];
				k = j;
			}
		}
		if (i == k)break;
		cout << "第" << ++n << "趟排序后" << endl;
		PrintList(L);
	}
	return OK;
}
int SelectMinKey(SqList L, int i) {
	int j, min = i;
	for (j = i; j <= L.length; j++) {
		if (LT(L.r[j].key, L.r[min].key))min = j;
	}
	return min;
}
Status SelectSort(SqList &L) {
	int i, j;
	for (i = 1; i < L.length; i++) {
		j = SelectMinKey(L, i);
		if (i != j) {
			L.r[0] = L.r[j];
			L.r[j] = L.r[i];
			L.r[i] = L.r[0];
		}
		cout << "第" << i << "趟排序后" << endl;
		PrintList(L);
	}
	return OK;
}
int Partition(SqList &L, int low, int high) {
	L.r[0] = L.r[low];
	KeyType pivotkey = L.r[low].key;
	while (low < high) {
		while (low<high&&MQ(L.r[high].key, pivotkey))--high;
		L.r[low] = L.r[high];
		while (low<high&&LQ(L.r[low].key, pivotkey))++low;
		L.r[high] = L.r[low];
	}
	L.r[low] = L.r[0];
	return low;
}
Status QSort(SqList &L, int low, int high) {
	static int num = 0;
	if (low < high) {
		int pivotloc = Partition(L, low, high);
		QSort(L, low, pivotloc - 1);
		QSort(L, pivotloc + 1, high);
	}
	cout << "第" << ++num << "趟排序后" << endl;
	PrintList(L);
	return OK;
}

基础知识

数据结构的概念

算法的概念

递归的概念

常见线性结构的应用

线性表抽象数据结构

1.顺序表

1.1 顺序表的结构定义

1.2 构造空的顺序表

1.3 销毁顺序表

1.4 清空顺序表

1.5 判断顺序表是否为空

1.6 求顺序表的长度

1.7 返回顺序表中的第i个元素

1.8 在顺序线性表L中查找第1个值与e满足compare()的元素的位序

1.9 返回一个不是首元素的前驱

1.10 返回一个不是末元素的后继

1.11 在顺序线性表L的第i个元素之前插入新的元素e

1.12 在顺序线性表L中删除第i个元素，并用e返回其值

1.13 遍历顺序线性表

2.链表

2.1 链表数据结构的定义

2.2 分配结点并赋值为e

2.3 释放p所指向的结点

2.4 构造一个由L指向的空的线性表

2.5 销毁由L指向的线性表

2.6 在链表L的第i个元素之前插入新的元素e

2.7 删除链表L的第i个元素

2.8 用e更新p所指向的当前结点

2.9 返回p所指结点中元素的值

2.10 返回p所指结点的直接前驱的位置

2.11 用p返回线性表l中第i个结点的位置，并返回ok

2.12 用一个函数遍历表中所有结点

3.栈

3.1 顺序栈

3.2 链栈

4.队列

4.1 循环队列

4.2 链队列

5.串

6.数组(十字链表实现)

常见非线性结构的应用

1.二叉树

1.1 二叉树的定义与遍历

1.2 二叉树的应用

2.图

散列储存结构

特殊运算

1.查找

2.排序