精华内容
下载资源
问答
  • 考研期间总结的数据结构代码大全,包括列表,栈,队列,树,图,查找,字符串,排序等数据结构的实现C语言实现版本,需要的朋友可以参考一下。
  • 本文档是针对考研专业课《数据结构》所编写的,是对考研数据结构的核心算法进行总结,我们知道,不管是统考还是非统考,都会涉及至少10分的算法题(非统考至少25分),而这些题的答案都是在一些经典算法的思想上进行...
  • 数据结构考研代码

    2021-08-20 09:22:23
    数据结构考研代码 第一章 1.一维数组静态分配 #define MaxSize 50 //线性表的最大长度 typedef struct { ElemType data[MaxSize]; //顺序表的元素 //ElemType是由typedef定义的数组元素的类型 int length; //...

    数据结构考研代码

    第一章:线性表

    1.一维数组静态分配

    #define MaxSize 50           //线性表的最大长度
    typedef struct {
    	ElemType data[MaxSize];  //顺序表的元素
    	                         //ElemType是由typedef定义的数组元素的类型
    	int length;              //顺序表的当前长度
    }SqList;  
    

    2.一维数组动态分配

    #define InitSize 100         //表长的初始定义
    typedef struct {
    	ElemType *data;          //指示动态分配数组的指针
    	int length,              //顺序表的当前长度
    	    MaxSize;             //动态数组的最大容量
    }SqList;
    /*动态分配空间*/
    L.data = (ElemType *)malloc(InitSize *sizeof(ElemType));
    

    3.元素e插入到顺序表L中位序i的位置

    bool ListInsert(SqList &L. int i, ElemType e){
    	                               //下标[1,L.length+1]
    	if(i<1 || i>L.length+1)
    		return false;
    	                               //当前存储空间已满,不能插入
    	if(L.length >= MaxSize)
    		return false;
    	                               //移位
    	for(int j=L.length;j>=i;j--)
    		L.data[j] = L.data[j-1];
    	L.data[i-1] = e;               //插入
    	L.length++;                    //表长+1
    	return true;
    }
    

    4.删除顺序表L中第i个位置的元素

    bool listDelete(SqList &L; int i; ElemType &e){
    	                                  //非法判断
    	if(i<1 || i>L.length){
    		return false;
    	}
    	                                  //去除需要删除的元素的元素
    	e = L.data[i-1];
    	                                  //移位
    	for(int j=i; j<L.length; ++j){
    		L.data[j-1] = L.data[j];
    	}
    	                                  //长度-1
    	L.length--;
    	return true;
    }
    

    5.查找顺序表中值为e的元素,如果查找成功,返回元素位序,否则返回0

    int LocateElem(SqList L, ElemType e){
    	int i;
    	for(i=0; i<L.length; ++i){
    		if(L.data[i] == e){
    			return i+1;  //位序与下标有1的差距
    		}
    	}
    	return 0;            //查找失败
    }
    

    6.单链表结点类型描述

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

    7.头插法建立单链表

    LinkList creatListByHead(LinkList &L){
    	LNode *s; //工作指针
    	int x;    //存入输入元素
    	
    	L = (LinkList)malloc(sizeof(LNode));  //创建头节点
    	L->next = NULL;                       //初始为空表
    	scanf("%d",&x);                       //读取输入值
    	
    	while(x != 9999){                     //约定输入9999表示创建结束
    		s = (LinkList)malloc(sizeof(LNode));  //创建新节点
    		s->data = x;                      //设置数据域
    		/*插s到表头*/
    		s->next = L->next;                //s后继设置L
    		L->next = s;                      //L后继设置s
    		scanf("%d",&x);
    	}
    	return L;                             //返头节点
    }
    

    8.尾插法建立单链表

    LinkList creatListByTail(LinkList &L){
    	int x;                                    //存输入元素
    	L = (LinkList)malloc(sizeof(LNode));      //创建头节点
    	LNode *s,                                 //s为工作指针
    	      *r = L;                             //r为表尾元素
    	scanf("%d",&x);                           //读取输入值
    	while(x != 9999){
    		s = (LinkList)malloc(sizeof(LNode));  //创建新节点
    		s->data = x;
    		
    		//插入s到表尾
    		r->next = s;
    		r = s;
    		scanf("%d",&x);
    	}
    	r->next = NULL;                           //尾巴置空
    	return L;                                 //返回头结点
    }
    

    9.取出单链表L(带头节点)中第i个位置的结点指针(在单链表中按照序号查找结点值)

    LNode *getElemByPos(LinkList L, int i){
    	int j = 1;                  //计数,初始为1
    	LNode *p = L->next;
    	
    	if(i == 0){                 //i为0,返回头节点
    		return L;
    	}
    	
    	if(i < 1)                   //无效的i,返回NULL
    		return NULL;
    	
    	while(p!=NULL               //链表还没有遍历完
    		   && j<i){             // 还没有到达所求的节点
    		p = p->next;            //指针后移
    		j++;                    //计数++
    	}
    	return p;                   //i大于表长,NULL;否则返回找到的节点
    }
    

    10.在单链表中按值查找结点

    /*从头开始遍历,返回其中数据域为给定e的节点的指针,不存在则返回NULL*/
    LNode *locateElemByValue(LinkList L, ElemType e){
    	LNode *p = L->next;
    	while(p!=NULL && p->data!=e){   //表中还有元素,且还没有找到数据域是e的节点
    		p = p->next;
    	}
    	return p;
    }
    

    11.将值为x的节点插入到单链表的第i个位置上

    void insertNode(LinkList L, int i; ElemType x){
    	if(i<1 || i>length(L)+1){                     //非法插入位置
    		return;
    	}
    	LNode *s = (LinkList)malloc(sizeof(LNode))//创造一个新的节点
    	s->data = x;                                  //数据域赋值
    	LNode p = getElem(L,i-1);                     //找到第i个节点的前驱节点
    	s->next = p->next;                            //执行插入
    	p->next = s;
    }
    

    12.将单链表上的第i个节点删除

    bool deleteNode(LinkList L; int i; ElemType &e){
    	if(i<1 || i>length(L)){           //删除位置非法
    		return false;
    	}
    	LNode *p,                         //被删除节点的前驱节点
    	      *q;                         //辅助指针
    	p = getElem(L,i-1);
    	q = p->next;                      //q指向需要删除的节点
    	p->next = p->next;                //将需要删除的节点从链表上取下
    	e = q->data;                      //将值交给e
    	free(q);                          //释放掉需要删除的节点
    	return true;
    }
    

    13.双链表的结点类型描述

    typedef struct DNode{
    	ElemType data;         //数据域
    	struct DNode *prior,   //前驱指针域
    	             *next;    //后继指针域
    }DNode,*DLinkList;
    

    14.双链表在p之后插入s

    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p->next = s;
    

    15.双链表的删除:删除p的后继结点q

    p->next = q->next;
    q->next->prior = p;
    free(q);
    

    16.静态链表结构类型描述

    #define MaxSize 50    //静态链表的最大长度
    typedef struct{
    	ElemType data;    //数据域
    	int next;         //指针域:下一个元素的数组下标
    }SLinkList[MaxSize];
    

    第二章:栈和队列

    1.栈的顺序存储类型描述

    #define MaxSize 50           //栈中元素的最大个数
    typedef struct{
    	ElemType data[MaxSize];  //用数组实现对栈中元素的存放
    	int top;                 //栈顶指针
    }SqStack;
    

    2.顺序栈:初始化栈

    void InitStack(SqStack &S){
    	S.top = -1;
    }
    

    3.顺序栈:判断栈空

    bool StackEmpty(SqStack S){
    	if(S.top == -1){     //栈空
    		return true;
    	}else{               //栈非空
    		return false;
    	}
    }
    

    4.顺序栈:进栈

    bool Push(SqStack &S, ElemType x){
    	if(S.top == MaxSize-1){  //栈满
    		return false;
    	}
    	S.data[++S.top] = x;     //先+1,再送元素进栈
    	return true;
    }
    

    5.顺序栈:出栈

    bool Pop(SqStack &S, ElemType &x){
    	if(S.top == -1){         //栈空
    		return false;
    	}
    	x = S.data[S.top--];     //先取栈顶元素,再栈顶指针-1
    	return true;
    }
    

    6.顺序栈:读取栈顶元素

    bool GetTop(SqStack &S, ElemType &x){
    	if(S.top == -1){         //栈空
    		return false;
    	}
    	x = S.data[S.top];       //读取栈顶元素
    	return true;
    }
    

    7.栈的链式存储类型描述

    typedef struct LNode{
    	ElemType data;        //数据域
    	struct LNode *next;   //指针域
    }
    

    8.链栈:初始化

    void initStack(LNode *&lst){                  //因为下面要对lst进行同步修改,所以用*&
    	lst = (LNode* )malloc(sizeof(LNode));     //申请头结点
    	lst->next = NULL;                         //后继指向空
    }
    

    9.链栈:判断栈空

    bool isEmpty(LNode *lst){
    	if(lst->next == NULL){  //头结点的指针域为NULL,则链表空
    		return true;
    	}else{
    		return false;
    	}
    }
    

    10.链栈:使用头插法将新的结点插入到头结点后

    void push(LNode *lst, ElemType x){
    	LNode *p;
    	p = (LNode *)malloc(sizeof(LNode));   //申请一个空间,用于存放进栈元素
    	p->data = x;                          //为数据域赋值
    	p->next = lst->next                   //新插入的结点指向原来的栈顶结点
    	lst->next = p;                        //头结点指向新入栈的结点
    }
    

    11.链栈:出栈

    bool pop(LNode *lst, ElemType &x){
    	if(lst->next == NULL)    //栈空
    		return false;
    	LNode *p ;
    	p = lst->next;           //出栈结点
    	x = p->data;             //出栈结点的数据域
    	lst->next = p->next;     //将栈顶结点摘下
    	free(p);
    	return true;
    }
    

    12.队列的顺序存储类型描述

    typedef struct{
    	ElemType data[MaxSize];  //用一维数组存放队列元素
    	int front,               //队头指针
    	    rear;                //队尾指针
    }SqQueue;
    

    13.循环队列:初始化

    void InitQueue(SqQueue &Q){
    	Q.rear = Q.front = 0;
    }
    

    14.循环队列:判断队列是否为空

    bool isEmpty(SqQueue Q){
    	return Q.rear = Q.front;
    }
    

    15.循环队列:入队

    bool EnQueue(SqQueue &Q, ElemType x){
    	if((Q.rear+1) % MaxSize == Q.front){  //队满
    		return false;
    	}
    	Q.data[Q.rear] = x;
    	Q.rear = (Q.rear + 1) % MaxSize;      //队尾指针加一环
    	return true;
    }
    

    16.循环队列:出队

    bool DeQueue(SqQueue &Q, ElemType &X){    //队空
    	if(Q.rear == Q.front){
    		return false;
    	}
    	X = Q.data[Q.front];                  //获取队首元素
    	Q.front = (Q.front+1) % MaxSize;      //队头指针加一环
    	return true;
    }
    

    17.队列的链式存储类型描述

    /*链式队列的结点*/
    typedef struct LinkNode{
    	ElemType data;            //数据域
    	struct LinkNode * next;   //指针域,指向下一个结点
    }LinkNode;
    /*链式队列*/
    typedef struct LinkNode{
    	LinkNode *front,          //队列的队头指针
    	         *rear;           //队列的队尾指针
    }LinkQueue;
    

    18.链式队列【有头结点】:初始化

    void InitQueue(LinkQueue &Q){
    	//申请头结点
    	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
    	Q.front->next = NULL;
    }
    

    19.链式队列【有头结点】:判断队空

    bool isEmpty(LinkQueue Q){
    	if(Q.front = Q.rear){
    		return true;
    	}else{
    		return false;
    	}
    }
    

    20.链式队列【有头结点】:入队

    void EnQueue(LinkQueue &Q, ElemType X){
    	LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode)); //申请头结点
    	s->data = x;
    	s->next = NULL;
    	Q.rear->next = s;                                  //插入队尾
    	Q.rear = s;                                        //更新rear
    }
    

    21.链式队列【有头结点】:出队

    bool DeQueue(LinkQueue &Q,ElemType &X){
    	if(Q.front == Q.rear){                //空队,出队失败
    		return false;
    	}
    	LinkNode *p = Q.front->next;          //队首结点
    	x = p->data;
    	Q.front->next = p->next;              //从链表上摘下结点
    	if(Q.rear == p){                      //链表上只有p这一个结点
    		q.rear = Q.front;                 //删除后,队列空
    	}
    	free(p);
    	return true;
    }
    
    

    第三章:数组、矩阵、广义表

    1.矩阵的转置

    void trsmat(int A[][MaxSize], int B[][MaxSize], int m, int n){
    	for(int i=0; i<m; ++i){
    		for(int j=0; j<n; ++j){
    			B[j][i] = A[i][j];
    		}
    	}
    }
    

    2.矩阵的相加

    void addMat(int C[][MaxSize], int A[][MaxSize], int B[][MaxSize], int m, int n){
    	for(int i=0;i<m;++i){
    		for(int j=0;j<n;++j){
    			C[i][j] = A[i][j] + B[i][j];
    		}
    	}
    }
    

    3.矩阵相乘

    void mutMat(int C[][MaxSize], int A[][MaxSize], int B[][MaxSize], int m, int n, int k){
    	for(int i=0;i<m;++i){
    		for(int j=0;j<k;++j){
    			C[i][j] = e;
    			for(int h=0;h<n;++h){
    				C[i][j] += A[i][h] * B[h][j];
    			}
    		}
    	}
    }
    

    4.三元组表示法定义

    typedef struct{
    	ElemType val;    //元素值
    	int i,           //元素所在行
    	    j;           //元素所在列
    }TriMat;
    

    5.稀疏矩阵转化为三元组表示

    /*统计非0元个数*/
    int countValNot0(ElemType A[][MaxSize], int m, int n){
    	int count = 0;
    	for(int i=0;i<m;++i){
    		for(int j=0;j<n;++j){
    			if(A[i][j] != 0){
    				count++;
    			}
    		}
    	}
    	return count;
    }
    /*稀疏矩阵转三元组表示*/
    TriMat* matToTriMat(ElemType A[][MaxSize], int m, int n){
    	//统计非0元个数
    	int count = countValNot0(A,m,n);
    	//申请存储空间
    	TriMat *triMat = (TriMat*)malloc(sizeof(TriMat)*(count+1));
    	//用三元组存储稀疏矩阵
    	//下表0:记录非0元个数,原矩阵总行数,总列数
    	triMat[0].val = count;
    	triMat[0].i = m;
    	triMat[0].j = m;
    	
    	int index = 1;
    	for(int i=0; i<m; ++i){
    		for(int j=0; j<n; ++j){
    			if(A[i][j] != 0){
    				triMat[index].val = A[i][j];
    				triMat[index].i = i;
    				triMat[index].j = j;
    				index++;
    			}
    		}
    	}
    	return triMat;
    }
    

    6.打印三元组表示的稀疏矩阵

    void printTriMat(TriMat triMat[]){
    	int index = 1;
    	//下标0处存储:总的非0元个数。原矩阵的行数,原矩阵的列数
    	for(int i=0; i<triMat[0].i; ++i){
    		for(int j=0; j<triMat[0].j; ++j){
    			if(triMat[index].i == i && triMat[index].j == j){
    				cout << triMat[index].val << "\t";
    				index++;
    			}else{
    				cout << "0" << "\t";
    			}
    		}
    		cout << endl;
    	}
    }
    

    7.十字链表描述

    typedef struct OLNode{
    	int row,                   //存储的非0元素的行下标
    	    rol;                   //存储的非0元素的列下标
    	struct OLNode *right,      //指同一行的右侧的结点
    	              *down;       //指同一行的下侧的结点
    	float val;                 //非0元素值
    }OLNode;
    typedef struct{
    	OLNode *upHeadArray,       //上侧的头结点数组
    	       *leftHeadArray;     //左侧的头结点数组
    	int rows,                  //矩阵总的行数
    	    cols,                  //矩阵总的列数
    		notZeroTotal;          //矩阵总的非0元个数
    }CrossList;
    

    第四章:串

    1.定长顺序存储表示的结构体

    typedef struct{
    	char str[MaxSize];   //串最大长度+一个“\0”
    	int length;          //记录串的当前长度
    }Str;
    

    2.堆分配存储表示

    typedef struct{
    	char *str;    //串
    	int length;   //记录串的当前长度
    }Str;
    

    3.串的赋值操作

    /**
     *str:待赋值的串
     *ch:串内容
     */
    bool strAssign(Str &str, char *ch){
    	if(str.ch != null){              //释放原串空间
    		free(str.ch);
    		str.ch = null;               //防止串重复释放
    	}
    	int len = 0;                     //记录串的当前长度
    	char *c = ch;                    //指向串
    	while(*c != "\0"){               //统计字符串长度
    		++len;
    		++c;
    	}
    	if(len == 0){                    //空串
    		str.ch = null;
    		str.length = 0;
    		return true;
    	}
    	str.ch = (char*)malloc(sizeof(char)*(len+1));  //申请存储串的空间
    	if(ch == null){                  //申请空间失败
    		return false;
    	}
    	c = ch;                          //指向串的首部
    	for(int i=0; i<=len; ++i,++c){   //复制串,以及‘\0’
    		str.ch[i] = *c;
    	}
    	str.length = len;                //更新串的长度
    	return true;
    }
    

    4.获取串长度

    int getStrLength(Str &str){
    	return str.length;
    }
    

    5.串比较

    int strCompare(Str s1, Str s2){
    	for(int i=0; i<s1.length && i<s2.length; ++i){  //某个串到达了结束位置后退出
    		if(s1.ch[i] != s2.ch[i]){ 
    			return s1.ch[i]-s2.ch[i];               //返回比较结果
    		}
    	}
    	//某个串结束了
    	return s1.length-s2.length;                     //串长的大
    }
    

    6.串连接

    /**
     *将str1,str2拼接到str
     */
    bool strConcat(Str &str, Str str1, Str str2){
    	if(str.ch != null){                             //释放str的空间
    		free(str.ch);
    		str.ch = null;                              //防止串重复释放
    	}
    	str.ch = (char*)malloc(sizeof(char)*(str1.length+str2.length+1));  //申请数组空间
    	if(str.ch == null){                                                //申请空间失败
    		return false;
    	}
    	int i = 0;
    	while(i<str1.length){                           //拷贝str1的字符到str
    		str.ch[i] = str1.ch[i];
    		++i;
    	}
    	int j = 0;
    	while(j <= str2.length){                        //拷贝str2的字符与‘\0’到str
    		str.ch[i+j] = str.ch[j];
    		++j;
    	}
    	str.length = str1.length + str2.length;         //修改串长度
    	return true;
    }
    

    7.求子串

    bool getSubString(Str &subStr, Str str, int pos, int len){
    	if(pos<0 || pos>=str.length || len<0 || len>str.length-pos){
    		return false;
    	}
    	if(subStr.ch != null){      //释放subStr的空间
    		free(subStr.ch);
    		subStr.ch = null;       //为了防止重复释放
    	}
    	if(len == 0){               //串长为0
    		subStr.ch = null;
    		subStr.length = 0;
    		return true;
    	}
    	subStr.ch = (char*)malloc(sizeof(char)*(len+1));
    	if(subStr.ch = null){       //申请空间失败
    		return false;
    	}
    	int i = pos;
    	int j = 0;
    	while(i < pos+len){
    		subStr.ch[j] = str.ch[i];//取子串
    		++i;
    		++j;
    	}
    	subStr.ch[j] = 0;            //'\0'  
    	subStr.length = len;
    	return true;
    }
    

    8.串清空

    bool clearStr(Str &str){
    	if(str.ch != null){     //释放空间
    		free(str.ch);
    		str.ch = null;      //防止重复释放
    	}
    	str.length = 0;         //串长置0
    	return true;
    }
    

    9.简单模式匹配

    int index(Str str, Str subStr){
    	int k = i =j = 1;
    	while(i<=str.length && j<=subStr.length){  //两个串都没有结束
    		if(str.ch[i] == subStr.ch[j]){         //匹配上了
    			++i;
    			++j;
    		}else{
    			j = 1;                             //匹配不上,从主串下一个位置重新开始比较
    			i = ++k;
    		}
    	}
    	if(j<subStr.length){                       //模式串结束了,成功
    		return k;
    	}else{
    		return 0;
    	}
    }
    

    10.求next数组

    /**
     *subStr:模式串
     *next[]:待求解的next数组
     */
    void getNext(Str subStr, int next[]){
    	int indexS = 1,                     //索引TS串中字符
    	    indexC = 0;                     //索引TC串中字符
    	next[1] = 0;
    	while(indexS<subStr.length){        //处理模式串中的每一个字符
    		if(indexC == 0 ||               /*TC串与TS串完全没有重合,跳转到模式串的第一位去
    										**TC:1...indexC
    										**TS:1...indexS
    										**TC与TS最大重合了,next[indexS+1]有结果了
    		                                */
    		   subStr.ch[indexS] == subStr.ch[indexC]){ 
    			++indexC;
    			++indexS;
    			next[indexS] = indexC;
    		}else{
    			indexC = next[indexC];      //利用已求得的next,对TC串进行跳转
    		}
    	}
    }
    

    11.KMP

    int kmp(Str str, Str subStr, int next){
    	int i = 1,                                  //主串下标
    	    j = 1;                                  //模式串下表
    	while(i<=str.length && j<=subStr.length){   //两个串都没有到尾
    		if(j==0 ||                              //主串后移一位,模式串用第一位继续比较
    		   str.ch[i] == subStr.ch[j]){          //匹配上了都后移
    			++i;
    			++j;
    		}else{                                  //没有匹配上,跳转到next[j]
    			j = next[j];
    		}
    	}
    	if(j > subStr.length){
    		return i-subStr.length;
    	}else{
    		return 0;
    	}
    }
    

    12.getNextVal

    void getNextVal(Str subStr, int nextVal[]){
    	int indexS = 1,                                                 //索引TS串中字符
    	    indexC = 0;                                                 //索引TC串中字符
    	nextVal[1] = 0;                                                 //处理的特殊情况
    	while(indexS < subStr.length){                                  //处理模式串中的每一个字符
    		if(indexC == 0 ||                                           //TC串长度为0
    		   subStr.ch[indexS] == subStr.ch[indexC]){                 //TC与TS最大重合了,next[indexS+1]有结果了
    			++indexC;
    			++indexS;
    			//跳转后的字符,与当前的字符不同,则找到了最终跳转的位置
    			if(subStr.ch[indexS] != subStr.ch[indexC]){
    				nextVal[indexS] = indexC;
    			}else{
    				//nextVal[indexC]已经求得了
    				nextVal[indexS] = nextVal[indexC];
    			}
    		}else{
    			indexC = nextVal[indexC];                                //利用已求得的next,对TC串进行跳转
    		}
    	}
    }
    

    第五章:树与二叉树

    1.双亲表示法

    typedef struct{
    	PTNode nodes [MAX_TREE_SIZE];   //存储结点的数组
    	int n;                          //真实节点数
    }PTree;
    

    2.孩子兄弟存储结构

    typedef struct CSNode{
    	ElemType data;                  //数据域
    	struct CSNode *fristChild,      //指向第一个孩子的指针
    	              *nextsibling;     //指向下一个兄弟的指针
    
    }CSNode, *CSTree;
    

    3.二叉树的链式存储结构描述

    typedef struct BiTNode{
    	ElemType data;                  //数据域
    	struct BiTNode *lchild,         //左孩子指针域
    				   *rchild;         //右孩子指针域
    }BiTNode, *BiTree;
    

    4.先序遍历:递归

    void preOrder(BiTree T){
    	if(T != null){                  //空树什么也不做,非空树才进行操作
    		visit(T);                   //先访问根结点
    		preOrder(T->lchild);        //再先序遍历左子树
    		preOrder(T->rchild);        //再先序遍历右子树
    	}
    }
    

    5.先序遍历:非递归

    void preOrderNoRecursion(BiTree bt){
    	if(bt != null){                 //不是空树
    		BiTNode *Stack[MaxSize];    //定义栈
    		int top = -1;               //定义栈顶指针,并初始化为-1
    		//1)初始化,根入栈
    		Stack[++top] = bt;
    		//2)循环执行直至栈空
    		while(top != 1){
    			//1.取栈顶结点,访问之
    			p = Stack[top--];
    			visit(p);
    			//2.将该结点的右孩子,左孩子依次入栈
    			if(p->rchild != null){
    				Stack[++top] = p->rchild;
    			}
    			if(p->lchild != null){
    				Stack[++top] = p->lchild;
    			}
    		}
    	}
    }
    

    6.中序遍历:递归

    void inOrder(BiTree T){  
    	if(T != null){              //空树什么也不做,非空树才进行操作
    		inOrder(T->lchild);     //中序遍历左子树
    		visit(T);               //访问根节点
    		inOrder(T->rchild);     //中序遍历右子树
    	}
    }
    

    7.中序遍历:非递归

    void inOrderNoRecursion(BiTree){
    	//初始化栈
    	InitStack(S);
    	//定义一个工作指针,初始化指向根结点
    	BiTree p = T;
    	//栈不为空,或者右孩子存在的时候,继续执行
    	//p代表着左孩子时,栈一定不为空
    	while(p || !isEmpty(S)){
    		if(p){                  //非空结点
    			Push(S,p);          //先把当前结点进栈
    			p = p->lchild;      //再去判断左孩子
    		}else{                  //空结点
    			//p代表左孩子:应该弹出访问
    			//p代表右孩子:应该弹出访问
    			Pop(S,p);
    			visit(p);
    			p = p->rchild;
    		}
    	}
    }
    

    8.后序遍历:递归

    void posOrder(BiTree T){
    	if(T != null){                 //空树什么也不做,非空树才进行操作
    		postOrder(T->lchild);      //后序遍历左子树
    		postOrder(T->rchild);      //后序遍历右子树
    		visit(T);                  //访问根结点
    	}
    }
    

    9.后序遍历:非递归

    void postOrderRecursion(BiTree T){
    	//初始化栈
    	InitStack(S);
    	//工作指针
    	BiTNode p = T;
    	//有来记录前一个访问的结点【判断是否有右子树访问完】
    	BiTNode r = null;
    	//上一轮是进行的访问节点操作且目前栈空就停止循环
    	while(p || !isEmpty(S)){
    		if(p){                                //先对左子树进行操作
    			Push(S,p);
    			p = p->lchild;
    		}else{
    			//查看栈顶结点
    			GetTop(S,p);
    			if(p->rchild != null
    			   && p->rchild != r){            //还没访问右子树
    				p = p->rchild;
    				Push(S,p);                    //右子树入栈
    				//对右子树进行同样的操作
    				p = p->lchild;
    			}else{                            //右子树已经访问完毕
    				//栈顶元素出栈
    				Pop(S,p);
    				//访问
    				visit(p);
    				//记录刚刚访问的结点
    				r = p;
    				//访问了一个结点后,应该直接去看栈顶元素的右子树
    				p = null;
    			}
    		}
    	}
    }
    

    10.层序遍历

    void levelOrder(BiTree T){
    	//初始化队列
    	Queue Q;
    	InitQueue(Q);
    	//工作指针
    	BiTree p;
    	//初始化根结点,入队
    	Enqueue(Q,T);
    	//队列非空,循环
    	while(!isEmpty(Q)){
    		//出队元素,交给p
    		Dequeue(Q,p);
    		//执行访问
    		visit(p);
    		//有左孩子
    		if(p->lchild != null){
    			Enqueue(Q,p->lchild)
    		}
    		//有右孩子
    		if(p->rchild != null){
    			Enqueue(Q,p->rchild);
    		}
    	}
    }
    

    11.线索二叉树结点

    typedef struct ThreadNode{
    	ElemType data;          //数据域
    	struct ThreadNode       //左右孩子指针域
    	        *lchild,
    			*rchild;
    	int ltag,               //左右线索标志
    	    rtag;
    }
    

    12.中序线索二叉树的构造

    void creatInThread(ThreadTree T){
    	ThreadTree pre = null;
    	if(T != null){
    		inThread(T,pre);
    		//最后一个结点,右孩子单独处理
    		pre->rchild = null;
    		pre->rtag = 1;
    	}
    }
    
    void inThread(ThreadTree &p, ThreadNode &pre){
    	//当前处理结点不为空
    	if(p != null){
    		//线索化左子树
    		inThread(p->lchild,pre);
    		//当前结点p的左子树为空,则存储前驱
    		if(p->lchild == null){
    			p->lchild = pre;
    			p->ltag = 1;
    		}
    		//前驱节点pre的右子树为空,则存储后继
    		if(pre != null && pre->rchild = null){
    			pre->rchild = p;
    			pre->rtag = 1;
    		}
    		//当前结点已经访问过
    		pre = p;
    		//线索化左子树
    		inThread(p->rchild,pre);
    	}
    }
    

    13.中序线索二叉树的遍历

    ThreadNode *FirstNode(ThreadNode *p){
    	while(p->ltag == 0){ //找最左侧的结点
    		p = p->lchild;
    	}
    	return p;
    }
    //求结点p的后继结点
    ThreadNode *nextNode(ThreadNode *p){
    	if(p->rtag == 0){   //存储的是右孩子
    		return FirstNode(p->rchild);
    	}else{              //存储的是后继
    		return p->rchild;
    	}
    }
    //利用线索二叉树进行中序遍历
    void inOrder(ThreadNode *T){
    	for(ThreadNode *p = FirstNode(T);p!=NULL;p=nextNode(p)){
    		visit(p);
    	}
    }
    

    14.并查集的结构定义

    #define SIZE 100
    int UFSetd[SIZE];
    

    15.并查集的初始化

    void Initial(int S[]){
    	for(int i=0;i<SIZE;++i){
    		S[i] = -1;
    	}
    }
    

    16.Find操作

    int Find(int S[], int x){
    	if(x>SIZE || x<0){
    		return -1;
    	}
    	
    	//根的值为负数,退出时x是根
    	while(S[x]>0){
    		x = S[x];
    	}
    	return x;
    }
    

    17.Union操作

    void Union(int S[], int root1, int root2){
    	//检测root1与root2没有交集
    	
    	//将root2连接到root1上
    	S[root2] == root1;
    }
    

    18.二叉排序树的查找:递归

    BTNode *BSTSearch(BTNode *bt, int key){
    	if(){
    		return NULL;   //查找失败
    	}
    	
    	if(bt->key == key){
    		return bt;                           //查找成功
    	}else if(bt->key > key){
    		return BSTSearch(bt->lchild, key);   //需要进入左子树查找
    	}else{
    		return BSTSearch(bt->rchild, key);   //需要进入右子树查找
    	}
    }
    

    19.二叉排序树的查找:非递归

    BSTSearch *BSTSearch(BiTree T, ElemType key){
    	//没有查找失败 并且 没有查找到
    	while(T!=NULL && key!=T->data){
    		if(key < T->data){           //需要进入左子树查找
    			T = T->lchild;
    		}else{                       //需要去右子树
    			T = T->rchild;
    		}
    	}
    	return T;
    }
    

    20.二叉排序树的插入

    bool BSTInsert(BTNode *&bt, int key){
    	if(bt == NULL){                          //查找失败的位置,就是需要插入的位置
    		bt = (BTNode*)malloc(sizeof(BTNode));
    		bt->lchild = NULL;
    		bt->rchild = NULL;
    		bt->key = key;
    		return true;                         //插入成功
    	}
    	if(bt->key == key){
    		return false;                        //插入失败
    	}else if(bt->key > key){
    		return BSTSearch(bt->lchild, key);   //需要进入左子树查找
    	}else{
    		return BSTSearch(bt->rchild, key);   //需要进入右子树查找
    	}
    }
    

    21.二叉排序树的构造

    void CreateBST(BTNode *&bt, int keys[], int n){
    	bt = NULL;
    	for(int i=0; i<n; ++i){
    		BSTInsert(bt,keys[i]);
    	}
    }
    

    第六章:图

    1.图的邻接矩阵存储结构定义

    #define MaxVertexNum 100
    typedef char VertexType;     //顶点数据类型
    typedef int EdgeType;        //带权图中边上权值的数据类型
    
    typedef struct{
    	VertexType Vex[MaxVertexNum];               //顶点表
    	EdgeType Edge[MaxVertexNum][MaxVertexNum];  //邻接矩阵,边表
    	int vexNum,     //图实际的顶点数
    		arcNum;     //图实际的弧数
    }MGraph;
    

    2.邻接表的存储结构定义

    #define MaxVertexNum 100
    
    //边表
    typedef struct ArcNode{
    	int adjVex;                //该弧所指向的顶点的下标
    	struct ArcNode *next;      //指向下一个边表中的结点
    }ArcNode;
    //顶点表
    typedef struct VNode{
    	VertexType data;           //顶点信息
    	ArcNode *first;            //指向边表
    }VNode,AdjList[MaxVertexNum];
    //邻接表下的图
    typedef struct{
    	AdjList vertices;          //邻接表
    	int vexNum,                //顶点数
    		arcNum;                //边数
    }ALGraph;
    

    3.图的十字链表存储结构定义

    #define MaxVertexNum 100              //图中顶点数目的最大值
    //边表结点
    typedef struct ArcNode{
    	int tailvex,headvex;              //该弧的头尾结点下标
    	struct ArcNode *hlink, *tlink;    //分别指向弧头相同和弧尾相同的结点
    	InfoType info;                    //相关信息指针
    }ArcNode;
    //顶点表结点
    typedef struct VNode{
    	VertexType data;                  //顶点表结点
    	ArcNode *firstin, *firstout;      //指向第一条入弧和出弧
    }VNode;
    //图
    typedef struct{
    	VNode xlist [MaxVertexNum];       //邻接表
    	int vexnum,arcnum;                //图的顶点数和弧数
    }GLGraph;
    

    4.邻接多重表存储结构

    #define MaxVertexNum 100             //图中顶点数目的最大值
    typedef struct ArcNode{              //边表结点
    	bool mark;                       //访问标记
    	int iVex,                        //弧的顶点i
    		jVex;                        //弧的顶点j
    	struct ArcNode *ilink,           //指向下一条依附于顶点iVex的边
    				   *jlink;           //指向下一条依附于顶点jVex的边
    	InfoType info;                   //指向和边相关的各种信息的指针域
    }ArcNode;
    
    typedef struct VNode{                //顶点表结点
    	VertexType data;                 //顶点信息
    	ArcNode *firstEdge;              //指向第一条依附该顶点的边
    }VNode;
    
    typedef struct{                      //以邻接多重表存储的图
    	VNode adjMuList[MaxVertexNum];   //邻接表
    	int vexNum,                      //图的顶点数
    		arcNum;                      //图的弧数
    }AMLGraph;
    

    5.广度优先搜索(BFS)

    bool visit[MAX_VERTEX_NUM];          //存放已经访问过的顶点
    Queue Q;                             //创建一个队列,等待使用
    
    /**
      *广度优先遍历图G
      */
    void BFSTraverse(Graph G){
    	//1.全部结点置为未访问
    	for(int i=0; i<G.vexNum; ++i){
    		visited[i] = false;
    	}
    	
    	//2.初始化队列
    	InitQueue(Q);
    	
    	//3.遍历整个图【非连通图时,这个循环中的if体将多次被执行】
    	for(int i=0; i<G.vexNum; ++i){
    		//该结点没有被访问【每个连通分量会进去一次if体】
    		if(!visited[i]){
    			BFS(G,i);
    		}
    	}
    }
    
    /**
      *按广度优先策略,遍历连通分量中的结点
      *G:图
      *v:第一个开始顶点
      */
    void BFS(Graph G, int v){
    	//1.访问当前顶点v
    	Visit(v);
    	//2.修改顶点v的访问标记
    	visited[v] = true;
    	//3.将顶点v入队
    	Enqueue(Q,v);
    	//4.处理剩余所有顶点
    	while(!isEmpty(Q)){
    		//4.1.顶点出队列
    		Dequeue(Q,v);
    		
    		//FirstNeighbor:顶点v的第一邻接顶点,没有时返回-1
    		//NextNeighbor:在v所有邻接顶点组成的链表中,当前遍历到了w,该函数返回w之后的邻接点
    		//4.2.按广度优先策略进行顶点v的所有邻接顶点
    		//访问顶点v的所有邻接顶点
    		for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w)){
    			if(!visited[w]){    //该顶点没被访问过
    				visit(w);
    				visited[w] = true;
    				//将顶点w入队
    				Enqueue(Q,w);
    			}
    		}
    	}
    }
    
    

    6.BFS算法求解单元最短路径问题

    /**
      *通过广度优先求单源最短路径
      */
    void BFS_MIN_Distance(Graph G, int u){
    	for(int i=0; i<G.vexNum; ++i){      //初始化路径长度
    		d[i] = INFINITY;
    	}
    	visited[u] = true;
    	d[u] = 0;
    	Enqueue(Q,u);
    	while(!isEmpty(Q)){
    		//出队,交给u
    		Dequeue(Q,u);
    		//访问顶点v的所有邻接顶点,这些邻接顶点距离都增加1
    		for(w=FirstNeighbor(G,u); w>=0;w=NextNeighbor(G,u,w)){
    			if(!visited[w]){
    				visit(w);
    				visited[w] = true;
    				
    				//路径长度+1
    				d[w] = d[u] +1;
    				
    				//入队,等待下一层处理
    				//同层上的d值一样
    				Enqueue(Q,w);
    			}
    		}
    	}
    }
    

    7.深度优先搜索遍历(DFS)

    //访问数组标记
    bool visited[MAX_VERTEX_NUM];
    
    bool DFSTraverse(Graph G){
    	//初始化访问标记数组
    	for(int v=0; v<G.vertices; ++v){
    		visited[v] = false;
    	}
    	
    	for(int v=0; v<G.vexNum; ++v){
    		if(!visited[v]){
    			DFS(G,v);
    		}
    	}
    }
    
    void DFS(Graph G, int v){
    	//访问v
    	visit(v);
    	//设置访问标记
    	visited[v] = true;
    	for( w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w)){
    		if(!visited[w]){    //该顶点没被访问过
    			//递归访问
    			DFS(G,w);
    		}
    	}
    }
    

    8.Prim(普里姆算法)

    void Prim(MGraph g, int v0, int &sum){
    	int lowcost[MaxSize],               //当前树到剩余顶点最短边
    		vest[MaxSize],                  //当前树顶点
    		v;                              //工作顶点指针
    	int i,j,k,min;                  //后续需要用到的变量
    		
    	v = v0;                         //从顶点v0开始执行prim算法
    		
    	for(i=0; i<g.n; ++i){
    		lowcost[i] = g.edges[v0][i];//初始化lowcost【树种只有v0】
    		vest[i] = 0;                //所有顶点先都设置为在树外
    	}
    		
    	vset[v0] = 1;                   //顶点v0加入树中
    	sum = 0;                        //sum用于累计树的权值
    	for(i=0; i<g.n; ++i){
    		min = INF;                  //INF是无穷量【自己到自己是INF】
    		for(j=0; j<g.n;++j){        //找出当前到树外顶点最短的边
    			if(vset[j] == 0 && lowcost[j]<min){
    				min = lowcost[j];
    				k = j;              //记录最短边的另一端顶点
    			}
    		}
    		vset[k] = 1;                //顶点k加入树中
    		sum += min;                 //更新树的权值
    		
    		v = k;                      //下面进行更新lowcost操作【看看顶点k的加入,是否导致了有更小的值】
    		
    		for(j=0; j<g.n; ++j){
    			if(vset[j] == 0 && g.edges[v][j] < lowcost[j]){
    				lowcost[j] = g.edges[v][j];
    			}
    		}
    	}
    }
    

    9.kruskal(克鲁斯卡尔)算法

    //边结点信息
    typedef struct{
    	int a,     //边的一端的顶点
    		b;     //边的另一端的顶点
    	int w;     //边的权值
    }Road;
    
    //边信息
    Road road[MaxSize];
    //并查集
    int v[MaxSize];
    
    /**
     *获取a的祖先(a所处的集合)
     */
    int getRoot(int a){
    	while(a != v[a]){
    		a = v[a];
    	}
    	return a;
    }
    
    /**
     *g:图
     *sum:统计生成树的总权值
     *road:图g的边信息
     */
    void kruskal(MGraph g, int &sum, Road road[]){
    	int i,
    		N,    //图的总顶点数
    		E,    //图的总变数
    		a,    //边的一端顶点
    		b;    //边的另一端顶点
    	N = g.n;  //图顶点总数
    	E = g.e;  //图边总数
    	//初始化,各个元素的双亲都是自己
    	//getRoot的时候,单个结点的树,根是自己
    	for(i=0; i<N; ++i){
    		v[i] = i;
    	}
    	sum = 0;                       //树总权值初始化为0
    	sort(road, E);                 //对边进行按权值从小到大排序
    	//对每一条边进行遍历
    	for(i=0; i<E; ++i){
    		//当前的两个顶点
    		a = getRoot(road[i].a);
    		b = getRoot(road[i].b);
    		//当前边的两个顶点在不同的树种,则合并
    		if(a != b){
    			v[a] = b;
    			sum += road[i].w;
    		}
    	}
    }
    

    10.Dijkstra

    /**
     *g:图
     *v:顶点
     *dist:记录从v到其余各个顶点的最短路径
     *path:记录v...a的路径中a的前一个结点
     */
    void dijkstra(MGraph g, int v; int dist[], int path[]){
    	int set[MaxSize];
    	int min,i,j,u;
    	
    	//初始化各数组
    	for(i=0; i<g.n; ++i){
    		//距离
    		dist[i] = g.edges[v][i];
    		//已求得最短路径结点
    		set[i] = 0;
    		//图中有边
    		if(g.edges[v][i] < INF){
    			path[i] = v;
    		}else{
    			path[i] = -1;
    		}
    	}
    	//源点
    	set[v] = 1;
    	path[v] = -1;
    	//处理
    	for(i=0; i<g.n; ++i){
    		//选取当前最短路径出来
    		min = INF;
    		for(j=0; j<g.n; ++j){
    			if(set[j] == 0 && dist[j] < min){
    				u =j;
    				min = dist[j];
    			}
    		}
    		set[u] = 1;
    		//用上一步选取出来的路径,去更新各顶点的最短路径
    		for(j=0; j<g.n; ++j){
    			//可以更新
    			if(set[j] == 0 && dist[u]+g.edges[u][j] < dist[j]){
    				dist[j] = dist[u] + g.edges[u][j];
    				//源点到顶点j,j前面的顶点是u
    				path[j] = u;
    			}
    		}
    	}	
    }
    /**
     *打印从原点到顶点a的最短路径
     */
    void printPath(int path[], int a){
    	//初始化栈
    	int stack[MaxSize],
    		top = -1;
    	while(path[a] != -1){
    		//输出内容,加入到栈
    		stack[++top] = a;
    		//去到“双亲”【路径的上一个结点】
    		a = path[a];
    	}
    	//单独处理最后一个顶点
    	stack[++top] = a;
    	//正序打印路径
    	while(top != -1){
    		cout << stack[top--] << " ";
    	}
    	cout << endl;
    }
    

    11.Floyd算法求各顶点之间的最短路径

    /**
     *输出u到v的最短路径上的顶点序列
     *<u,a1>、<a1,a1>、......、<an,v>
     */
    void printPath(int u, int v, int path[][MaxSize]){
    	if(A[u][v] == INF){
    		//u,v不可达,不输出
    	}else{
    		if(path[u][v] = -1){
    			//输出边<u,v>
    			cout << "<"+u+","+v+">"
    		}else{
    			int mid = path[u][v];
    			printPath(u,mid,path);  //前半段
    			printPath(mid,v,path);  //后半段
    		}
    	}
    }
    /**
     *g:图
     *path:存储最短路径
     *A:记录最短路径长度
     */
    void Floyd(MGraph *g, int Path[][MaxSize], int A[MaxSize][MaxSize]){
    	int i,j,k;
    	//初始化A数组,path数组
    	for(i=0; i<g->n; i++){
    		for(j=0; j<g->n; j++){
    			A[i][j] = g->edges[i][j];
    			Path[i][j] = -1;
    		}
    	}
    	//以顶点k为中间点,完成对所有的顶点对(i,j)的更新
    	for(k=0; k<g->n; k++){
    		for(i=0; i<g->n; i++){
    			for(j=0; j<g->n;j++){
    				if(A[i][j] > A[i][k]+A[k][j]){
    					A[i][j] = A[i][k] + A[k][j];
    					Path[i][j] = k;
    				}
    			}
    		}
    	}
    }
    

    12.拓扑排序

    //改造后的顶点
    typedef struct{
    	char data;
    	int count;             //统计该顶点的入度
    	ArcNode *firstArc;
    }VNode;
    
    int topSort(AGraph *G){
    	int i,j,n=0;
    	//初始化栈
    	int stack[MaxSize],
    		top = -1;
    	ArcNode *p;
    	//初始化,将入度文0的顶点入栈
    	for(i=0; i<G->n; i++){
    		if(G->adjList[i].count == 0){
    			stack[++top] = i;
    		}
    	}
    	//栈不为空,则循环
    	while(top != -1){
    		//栈顶入度为0的顶点出栈
    		i=stack[top--];
    		//输出计数器加一
    		++n;
    		//输出当前顶点
    		cout << i << " ";
    		//与顶点i邻接的顶点,入度减去1,如果产生了入度为0的顶点,则入栈
    		p = G->adjList[i].firstArc;
    		while(p != NULL){
    			j = p->addVex;
    			--(G->adjList[j].count);
    			if(G->adjList[j] == 0){
    				stack[++top] = j;
    			}
    			p=p->nextArc;
    		}
    	}
    	if(n == G->n){   //成功
    		return 1;
    	}else{           //失败
    		return 0;
    	}
    }
    

    第七章:查找

    1.一般线性表的顺序查找

    typedef struct{
    	ElemType *elem;                               //一维指针表示数组,从下标1开始存储
    	int tabLen;
    }SSTable;
    
    int searchSeq(SSTable ST, ElemType key){
    	ST.elem[0] = key;
    	for(int i=ST.tabLen; ST.elem[i]!=key; --i);   //查找
    	//查找失败时,i=0;
    	return i;
    }
    

    2.折半查找

    int binarySearch(SeqList L, ElemType key){
    	int low = 0,                 //表头下标
    		high = L.tabLen - 1,     //表尾下标
    		mid;                     //记录表中元素下标
    	//还没有查找完毕
    	while(low<=high){
    		//取表的中见下标
    		mid = (low + high) / 2;
    		//查找成功
    		if(L.elem[mid] == key){  
    			return mid;
    		}else if(L.elem[mid] > key){ //在表的前半部分继续查找   
    			high = mid - 1;
    		}else{                   //在表的后半部分继续查找
    			low = mid +1;
    		}
    	}
    	return -1;
    }
    

    第八章:内部排序

    1.直接插入排序

    /**
     *用到哨兵思想
     *A:1-n
     */
    void insertSort(ElemType A[], int n){
    	int i,j;
    	for(i=2; i<=n; ++i){
    		//为A[i]查找插入位置
    		if(A[i].key < A[i-1].key){
    			//把A[i]暂存在A[0]
    			A[0] = A[i];
    			//从后向前找到第一个小于等于A[i]的元素的下标
    			for(j=i-1; A[0].key<A[j].key; --j){
    				//后移,腾出空间
    				A[j+1] = A[j];
    			}
    			//将A[i]插入到第一个小于等于A[i]的元素的最后一位
    			A[j+1] = A[0];
    		}
    	}
    }
    

    2.折半插入

    void insertSortByHalf(ElemType A[], int n){
    	int i,j,low,high,mid;
    	for(i=2; i<=n; ++i){
    		A[0] = A[i];
    		//折半查找插入位置
    		low = 1;
    		high = i-1;
    		while(low<=high){
    			mid = (low + high) / 2;
    			if(A[mid].key)>A[0].key{
    				high = mid - 1;
    			}else{
    				low = mid + 1;
    			}
    		}
    		//结束时的high+1就是插入位置
    		//统一移动的元素
    		for(j=i-1; j>=high+1; --j){
    			A[j+i] = A[j];
    		}
    		//将A[i]放到最终位置
    		A[high + 1] = A[0];
    	}
    }
    

    3.希尔排序

    void shellSort(ElemType A[], int n){
    	//增量变化
    	//d1=n/2, di+1=[di/2],并且最后一个增量等于1
    	for(int dk=n/2; dk>=1;dk/=2){
    		//1...dk认为都是有序的子序列
    		for(int i=dk+1; i<=n; ++i){
    			//如果前面有序子表最后一位(A[i-dk])比当前需要调整位置的(A[i])key值大
    			//则需要招到A[i]应该插入的位置
    			if(A[i].key<A[i-dk].key){
    				//将A[i]插入到应该插入的位置(类似前面直接插入排序招到插入位置)
    				//注意步长是dk
    				A[0] = A[i];
    				for(int j=i-dk; j>0&&A[0].key<A[j].key; j-=dk){
    					A[j+dk] = A[j];
    				}
    				A[j+dk] = A[0];
    			}
    		}
    	}
    }
    

    4.冒泡排序

    void bubbleSort(ElemType A[], int n){
    	//从后向前进行冒泡,每轮产生一个最小值
    	//冒泡的规模:0...n-1,i<n-1,...,n-2...n-1,
    	for(int i=0; i<n-1; ++i){
    		//用于标记本轮冒泡排序是否进行过交换操作
    		bool isBublle = false;
    		//从后往前冒泡
    		for(j=n-1; j>i; --j){
    			//前面的更大则需要交换
    			if(A[j-1].key > A[j].key){
    				swap(A[j-1],A[j]);
    				//发生了交换
    				isBublle = true;
    			}
    		}
    		//如果没有发生过交换,证明已经完全有序了
    		if(!isBublle){
    			return;
    		}
    	}
    }
    

    5.快速排序

    int partition(ElemType A[], int low, int high){
    	//选表中第一个元素作为枢轴值
    	ElemType pivot = A[low];
    	//进行移动
    	while(low < high){
    		//考察右侧,找到第一个比pivot小的元素下标
    		while(low<high && A[high]>=pivot){
    			--high;
    		}
    		//放到表头去
    		A[low] = A[high];
    		//考察左侧,找到第一个比pivot大的元素下标
    		while(low<high && A[low]<=pivot){
    			++low;
    		}
    		//放到表尾去
    		A[high] = A[low];
    	}
    	
    	//将枢轴放到最终位置
    	A[low] = pivot;
    	return low;
    }
    
    void quickSort(ElemType A[], int low, int high){
    	//执行条件
    	if(low < high){
    		//进行一次快排
    		int pivotPos = partition(A,low,high);
    		//递归的对左子表快排
    		quickSort(A,low,pivotPos-1);
    		//递归的对右子表快排
    		quickSort(A,pivotPos+1,high);
    	}
    }
    

    6.简单选择排序

    void selectSort(ElemType A[], int n){
    	for(int i=0; i<n-1; ++i){
    		//找出无序部分最小
    		min = i;
    		for(j=i+1; j<n; ++j){
    			if(A[j] < A[min]){
    				min = j;
    			}
    		}
    		//将最小元素放到有序部分尾巴上
    		if(min != i){
    			swap(A[i],A[min]);
    		}
    	}
    }
    

    7.构造初始堆

    void  buildMaxHeap(ElemType A[], int len){
    	for(int i=len/2; i>0; --i){
    		adjustDown(A,i,len);
    	}
    }
    
    /**
     *将元素k向下调整
     */
    void adjustDown(ElemType A[], int k, int len){
    	A[0] = A[k];
    	//向下调整
    	for(i=2*k; i<=len; i*=2){
    		//左孩子右孩子选择最大的
    		if(i<len&&A[i]<A[i+1]){
    			i++;
    		}
    		//已满足最大根堆,不需要调整
    		if(A[0] >= A[i]){
    			break;
    		}else{
    			//将更大的孩子作为根
    			A[k] = A[i];
    			//对i这颗字数继续调整
    			k = i;
    		}
    	}
    	//结点“k”的最终位置【这里的k值已经发生变化了】
    	A[k] = A[0];
    }
    

    8.堆排序

    void heapSort(ElemType A[], int len){
    	//建立初始堆
    	buildMaxHeap(A,len);
    	//每次选出一个最大值
    	for(i=len; i>1; --i){
    		//将堆底元素与堆顶元素交换【堆顶元素输出】
    		swap(A[i],A[1]);
    		//调整堆
    		adjustDown(A,1,i-1);
    	}
    	//最终就是一个递增的顺序
    }
    

    9.归并排序

    void mergeSort(ElemType a[], int low; int high){
    	if(low < high){
    		//从中间划分
    		int mid = (low+high)/2;
    		//对左表排序
    		mergeSort(A,low,mid);
    		//对右表排序
    		mergeSort(A,mid+1,high);
    		//将左右表归并
    		Merger(A,low,mid,high);
    	}
    }
    
    //辅助数组B
    ElemType *B = (ElemType*)malloc((n+1)*sizeof(ElemType));
    
    /**
     *A:待排序表
     *low:表A起始下标
     *mid:左边终止下标
     *mid+1:右表起始下标
     *high:右表终止下标
     */
    void Merger(ElemType A[], int low, int mid, int high){
    	//将A中所有内容复制到B中
    	for(int k=low; k<=high; k++){
    		B[k] = A[k];
    	}
    	//归并B的左右表,归并结果放到A中
    	for(int i=low, j=mid+1, k=i;   //i左表,j右表,k索引数组A
    		i<=mid && j<=high;         //两个表都还有元素
    		k++){
    		if(B[i]<=B[j]){            //左表表头元素小于等于右表表头元素
    			A[k] = B[i++];         //取左表表头元素到A中,左表指针后移
    		}else{                     //右表表头更小
    			A[k] = B[j++];         //取右表表头元素到A中,右表指针后移
    		}
    	}
    	//可能还有一个表中有剩余元素,按顺序复制到A中
    	while(i <= mid) A[k++] = B[i++];
    	while(j <= high) A[k++] = B[j++];
    }
    
    展开全文
  • 考研数据结构代码整理

    万次阅读 多人点赞 2019-10-07 22:10:37
    顺序表的基本操作2.1)初始化顺序表2.2)求指定位置元素2.3)插入数据元素2.4)按元素值查找2.5)删除数据元素2.6)顺序表的元素逆置2.7)删除下标为i~j的数据元素2.8)Partition操作3. 单链表的基本操作3.1)初始...

    文章目录

    1. 线性表的结构体定义

    1.1)顺序表的结构体定义

    typedef struct Sqlist{
        int data[maxSize];
        int length;
    }Sqlist;
    

    1.2)考试中顺序表定义简写法

    int A[maxSize];
        int n;
    

    1.3)单链表的结构体定义

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

    1.4)双链表结构体定义

    typedef struct DLNode {
        int data;
        struct DLNode *prior;
        struct DLNode *next;
    }DLNode;
    

    2. 顺序表的基本操作

    2.1)初始化顺序表

    void initList(Sqlist &L) {
        L.length = 0;
    }
    

    2.2)求指定位置元素

    int getElem(Sqlist L, int p, int &e){
        if (p < 0 || p >= L.length) {
            return 0;
        }
        e = L.data[p];
        return 1;
    }
    

    2.3)插入数据元素

    int insertElem(Sqlist &L, int p, int e) {
        if (p < 0 || p > L.length || L.length == maxSize) {
            return 0;
        }
        for (int i = L.length-1; i >= p; i--) {
            L.data[i+1] = L.data[i];
        }
        L.data[p] = e;
        ++(L.length);
        return 1;
    }
    

    2.4)按元素值查找

    int findElem(Sqlist L, int e) {
        for (int i = 0; i < L.length; i++) {
            if (L.data[i] == e) {
                return i;
            }
        }
        return -1;
    }
    

    2.5)删除数据元素

    int deleteElem(Sqlist &L, int p, int &e) {
        if (p < 0 || p >= L.length) {
            return 0;
        }
        e = L.data[p];
        for (int i = p; i < L.length-1; i++) {
            L.data[i] = L.data[i+1];
        }
        --(L.length);
        return 1;
    
    

    2.6)顺序表的元素逆置

    void reverse(Sqlist &L) {
        int i, j, temp;
        for (i = 0, j = L.length - 1; i < j; ++i, --j) {
            // 交换
            temp = L.data[i];
            L.data[i] = L.data[j];
            L.data[j] = temp;
        }
    }
    

    2.7)删除下标为i~j的数据元素

    void deleteRange(Sqlist &L, int i, int j) {
        assert(0 <= i && 0 <= j && i < L.length && j < L.length);
        // 用j+1后面的元素去覆盖往前数第j-i+1个元素
        int delta = j - i + 1;
        for (int k = j+1; k < L.length; ++k) {
            L.data[k-delta] = L.data[k];
        }
        L.length -= delta;
    }
    

    2.8)Partition操作

    void partition(Sqlist &L) {
        assert(L.length != 0);
        int p = L.data[0];
        int i = 0, j = L.length-1;
        while (i < j) {
            while (i < j && L.data[j] > p) --j;
            if (i < j) {
                L.data[i] = L.data[j];
                ++i;
            }
    
            while (i < j && L.data[i] < p) ++i;
            if (i < j) {
                L.data[j] = L.data[i];
                --j;
            }
        }
        L.data[i] = p;
    }
    

    3. 单链表的基本操作

    3.1)初始化单链表

    void InitLinkList(LNode *list) {
        assert(list != NULL);
        list->next = NULL;
    }
    

    3.2)尾插法建立单链表

    void createlistR(LNode *&list, int a[], int n) {
        LNode *s, *r; // s用来指向新申请的节点,r始终指向list的终端节点
        int i;
        list = (LNode*)malloc(sizeof(LNode));
        list->next = NULL;
        r = list;
        for (int i = 0; i < n; i++) {
            s = (LNode*)malloc(sizeof(LNode));
            s->data = a[i];
            r->next = s;  // 让当前的终端节点指向新来的节点
            r = r->next;  // 更新r,让r指向新的终端节点
        }
        r->next = NULL;
    
    

    3.3)头插法建立单链表

    void createlistF(LNode *&list, int a[], int n) {
        LNode *s;  // s用来指向新申请的节点
        list = (LNode*)malloc(sizeof(LNode));
        list->next = NULL;
        for (int i = 0; i < n; i++) {
            s = (LNode*)malloc(sizeof(LNode));
            s->data = a[i];
            s->next = list->next;
            list->next = s;
        }
    }
    

    3.4)合并递增单链表

    void mergeR(LNode *A, LNode *B, LNode *&C) {
        // 由于不能改变了A, B自己的内容,所以得设定p, q来进行操作
        LNode *p = A->next;
        LNode *q = B->next;
    
        LNode *r;  // r始终指向C的终端节点
        C = A;  // 将A的头结点用来做C的头结点
        C->next = NULL;
        free(B);
        r = C;  // 初试的时候C也是终端节点
        while (p != NULL && q != NULL) {
            if (p->data <= q->data) {
                r->next = p; // 让当前的终端节点指向新的终端节点
                p = p->next; // p自然要往后挪一步
                r = r->next; // 更新r的指向,让r指向新的终端节点
            } else {
                r->next = q;
                q = q->next;
                r = r->next;
            }
        }
    
        // p还有剩余
        if (p != NULL) {
            r->next = p;
        }
    
        // q还有剩余
        if (q != NULL) {
            r->next = q;
        }
    }
    

    3.5)合并递减单链表

    void mergeF(LNode *A, LNode *B, LNode *&C) {
        LNode *p = A->next;
        LNode *q = B->next;
        LNode *s;
        C = A;
        C->next = NULL;
        free(B);
        while (p != NULL && q != NULL) {
            if (p->data <= q->data) {
                // 这里就体现出s的作用了
                // 如果没有s,
                // 则直接p->next = C->next, 
                // 那么改变了p的指向,p无法再往后挪了
                s = p;
                p = p->next;
                s->next = C->next;
                C->next = s;
            } else {
                s = q;
                q = q->next;
                q->next = C->next;
                C->next = s;
            }
        }
    
        // 由于头插,所以这里必须循环将每个剩余元素放到链表C的前面去
        while (p != NULL) {
            s = p;
            p = p->next;
            s->next = C->next;
            C->next = s;
        }
    
        while (q != NULL) {
            s = q;
            q = q->next;
            s->next = C->next;
            C->next = s;
        }
    }
    

    3.6)查找元素并删除

    int findAndDelete(LNode *list, int x) {
        // 先找到该元素
        LNode *p;
        p = list;
        while (p->next != NULL) {
            if (p->next->data == x) {
                break;
            }
            p = p->next;
        }
    
        // 然后删除
        if (p->next == NULL) {
            return 0;
        } else {
            LNode *del;
            del = p->next;
            p->next = p->next->next;
            free(del);
            return 1;
        }
    } 
    

    3.7)对于一个递增单链表,删除其重复的元素

    void deleteDuplicate(LNode *list) {
        LNode *p, *q;  // q用来释放被删除的元素
        p = list->next;
        while (p->next != NULL) {
            if (p->data == p->next->data) {
                q = p->next;
                p->next = p->next->next;
                free(q);
            } else {
                p = p->next;
            }
        }
    }
    

    3.8)删除单链表中的最小值

    void deleteMin(LNode *list) {
        // 这题的关键是要弄清楚需要哪些指针:
        // p用来扫描链表,pre指向p的前驱
        // minp用来指向最小值节点,premin用来指向minp的前驱
        LNode *p = list->next, *pre = list, *minp = p, *premin = pre;
        while (p != NULL) {
            if (p->data < minp->data) {
                minp = p;
                premin = pre;
            }
            pre = p;
            p = p->next;
        }
        premin->next = minp->next;
        free(minp);
    }
    

    3.9)单链表的原地逆置

    // 将L->NULL设置为空,然后将剩余的节点一一用头插法插入到L中
    void reverseList(LNode *list) {
        LNode *p = list->next, *q;
        list->next = NULL;  // 断开头节点
        while (p != NULL) {
            q = p->next;  // 首先得让q临时保存一下p的下一个节点,待会儿还得用呢
            p->next = list->next;  // 头插法
            list->next = p;
            p = q;  // 拿回下一个节点
        }
    }
    

    3.10)将一个数据域为整数的单链表分割为两个分别为奇数和偶数的链表

    void split2(LNode *A, LNode *&B) {
        // p用来扫描,但是指向的是要删除节点的前驱
        // q用来临时保存要删除的节点
        // r用来指向B中的终端节点
        LNode *p, *q, *r;
        B = (LNode*)malloc(sizeof(LNode));
        B->next = NULL; // 每申请一个新的节点,都将指针域设置为空,这样可以避免出事儿
        p = A;
        r = B;
        while (p != NULL) {
            if (p->next->data%2 == 0) {
                q = p->next;
                p->next = p->next->next;
                r->next = q;
                r = q;
                q->next = NULL;  // 不写这句话绝对出事
            } else {
                p = p->next;
            }
        }
    }
    

    3.11)逆序打印单链表中的节点

    // 逆序,入栈不就逆序了吗,所以可以考虑递归打印
    void reprintList(LNode *list) {
        if (list != NULL) {
            reprintList(list->next);
            printf("%d ", list->data);
        }
    }
    

    3.12)查找链表中倒数第k个节点

    int findkLast(LNode *list, int k) {
        LNode *p, *q;
        p = list->next;
        q = list;
        int i = 1;
        while (p != NULL) {
            p = p->next;
            ++i;  // 这里的计数器i自己画图给弄清楚
            if (i > k) q = q->next; 
        }
    
        if (q == list) return 0;  // 链表的节点不到k个
        else {
            printf("%d ", p->data);
            return 1;
        }
    
    

    4. 双链表的基本操作

    4.1)尾插法建立双链表

    void createDListR(DLNode *&list, int a[], int n) {
        // 准备工作...
        DLNode *s, *r;  // s指向新申请的节点,r指向终端节点
        list = (DLNode*)malloc(sizeof(DLNode));  // 创建头结点
        list->prior = NULL;
        list->next = NULL;
        r = list;  // 初始状态,r指向头结点
        
        // 开始插入元素
        int i;
        for (int i = 0; i < n; i++) {
            s = (DLNode*)malloc(sizeof(DLNode));
            s->data = a[i];
            
            // 最关键的三句话
            r->next = s;
            s->prior = r;
            r = s;
        }
        r->next = NULL;  // 如果不加这句话,一定会出事的
    }
    

    4.2)查找结点的算法

    DLNode* findNode(DLNode *list, int x) {
        DLNode *p = list->next;
        while (p != NULL) {
            if (p->data == x) {
                break;
            }
            p = p->next;
        }
        return p;
    }
    

    4.3)插入结点的算法

    int insertNode(DLNode *&list, int index, int e) {
        if (index < 0) return 0;
        DLNode *p = list;
        for (int i = 0; i < index; ++i) {
            p = p->next;
        }
    
        DLNode *s = (DLNode*)malloc(sizeof(DLNode));
        s->data = e;
        // 最关键的四句话:将新节点插入到p指向节点的后面
        s->next = p->next;
        s->prior = p;
        p->next = s;
        s->next->prior = s;
        return 1;
    }
    

    4.4)删除结点的算法

    int deleteNode(DLNode *&list, int index) {
        DLNode *p = list;
        for (int i = 0; i < index; ++i) {
            p = p->next;
        }
        if (p->next == NULL) return 0;
    
        // 最关键的四句话:删除p的后继结点
        DLNode *del;
        del = p->next;
        p->next = del->next;
        if (del->next != NULL) {  // 不加这个判断也是会出事的
            del->next->prior = p;
        }
        free(del);
        return 1;
    }
    

    5. 栈和队列的结构体定义

    5.1)顺序栈的定义

    typedef struct SqStack{
        int data[maxSize];
        int top;
    } SqStack;
    

    5.2)链栈结点定义

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

    5.3)顺序队列的定义

    typedef struct {
        int data[maxSize];
        int front;  // 队首指针
        int rear;  // 队尾指针
    }SqQueue;
    

    5.4)链队定义

    (5.4.1)队结点类型定义

    typedef struct QNode {
        int data;  // 数据域
        struct QNode *next;   // 指针域
    }QNode;
    

    (5.4.2)链队类型定义

    typedef struct {
        QNode *front;  // 队头指针
        QNode *rear;  // 队尾指针
    }LiQueue;
    

    6. 顺序栈的基本操作

    6.1)顺序栈的初始化

    void initStack(SqStack &st) {
        st.top = -1;
    }
    

    6.2)判断栈空

    int isEmpty(SqStack st) {
        return st.top == -1;
    }
    

    6.3)进栈代码

    int push(SqStack &st, int x) {
        if (st.top == maxSize) return 0;
        st.data[++st.top] = x;
        return 1;
    }
    

    6.4)出栈代码

    int pop(SqStack &st, int &x) {
        if (st.top == -1) return 0;
        x = st.data[st.top--];
        return 1;
    }
    

    6.5)考试中顺序栈用法的简洁写法

    int stack[maxSize]; int top = -1;  // 这两句话连定义带初始化都有了
    stack[++top] = x;  // 一句话实现进栈
    x = stack[top--];  // 一句话实现出栈
    

    7. 链栈的基本操作

    7.1)链栈的初始化

    void initStack(LNode *&lst) {
        lst = (LNode*)malloc(sizeof(LNode));
        lst->next = NULL;  // 还是老规矩:申请新的节点后一定要为其指针域设置为空
    }
    

    7.2)判断栈空

    int isEmpty(LNode *lst) {
        return lst->next == NULL;
    }
    

    7.3)进栈代码

    void push(LNode *lst, int x) {
        // 步骤一:申请新的节点,存放x的值
        // 步骤二:头插法将新的节点插入链栈中
        
        LNode *p = (LNode*)malloc(sizeof(LNode));
        p->next = NULL;
    
        p->data = x;
        p->next = lst->next;
        lst->next = p;
    }
    

    7.4)出栈代码

    int pop(LNode *lst, int &x) {
        // 步骤一:判空
        // 步骤二:删除节点
    
        if (lst->next == NULL) return 0;
    
        x = lst->data;
        LNode *p;
        p = lst->next;
        lst->next = lst->next->next;
        free(p);
        return 1;
    }
    

    8. 顺序队列的基本操作

    8.1)顺序队列的初始化

    void initQueue(SqQueue &qu) {
        qu.front = qu.rear = 0;  // 队首和队尾指针重合,并且指向0
    }
    

    8.2)判断队空

    int isQueueEmpty(SqQueue qu) {
        return qu.front == qu.rear;  // 只要重合,即为空队
    }
    

    8.3)进队算法

    int enQueue(SqQueue &qu, int x) {
        if ((qu.rear+1)%maxSize == qu.front) return 0;  // 队满则不能入队
        qu.rear = (qu.rear+1)%maxSize;  // 若未满,则先移动指针
        qu.data[qu.rear] = x;  // 再放入元素
        return 1;
    }
    

    8.4)出队算法

    int deQueue(SqQueue &qu, int &x) {
        if (qu.front == qu.rear)  return 0;  // 若队空,则不能删除
        qu.front = (qu.front+1)%maxSize;  // 若队不空,则先移动指针
        x = qu.data[qu.front];  // 再取出元素
        return 1;
    }
    

    9. 链队的基本操作

    9.1)链队的初始化

    void initQueue(LiQueue *&lqu) {
        lqu = (LiQueue*)malloc(sizeof(LiQueue));
        lqu->front = lqu->rear = nullptr;
    }
    

    9.2)判断队空算法

    int isQueueEmpty(LiQueue *lqu) {
        return (lqu->rear == nullptr || lqu->front == nullptr);  // 注意有两个
    }
    

    9.3)入队算法

    void enQueue(LiQueue *lqu, int x) {
        QNode *p;
        p = (QNode*)malloc(sizeof(QNode));
        p->data = x;
        p->next = nullptr;
        if (lqu->rear == nullptr) {  // 若队列为空,则新结点是队首结点,也是队尾结点
            lqu->front = lqu->rear = p;
        } else {
            lqu->rear->next = p;  // 将新结点链接到队尾,rear指向它
            lqu->rear = p;
        }
    }
    

    9.4)出队算法

    int deQueue(LiQueue *lqu, int &x) {
        QNode *p;
        if (lqu->rear == nullptr) {  // 队空不能出队
            return 0;
        } else {
            p = lqu->front;
        }
        if (lqu->front == lqu->rear) {  // 队列中只有一个结点时的出队操作需要特殊处理
            lqu->front = lqu->rear = nullptr;
        } else {
            lqu->front = lqu->front->next;
        }
        x = p->data;
        free(p);
        return 1;
    }
    

    10. 串的结构体定义

    10.1)定长顺序存储表示

    typedef struct {
        char str[maxSize+1];  // 多出一个'\0'作为结束标记
        int length;
    }Str;
    

    10.2)变长分配存储表示

    typedef struct {
        char *ch;  // 指向动态分配存储区首地址的字符指针
        int length;  // 串长度
    }Str;
    

    11. 串的基本操作

    11.1)赋值操作

    int strassign(Str& str, char* ch) {
        if (str.ch) {
            free(str.ch);  // 释放原空间
        }
        int len = 0;
        char *c = ch;
        while (*c) {  // 求ch串的长度
            ++len;
            ++c;
        }
        if (len == 0) {  // 如果ch为空串,则直接返回空串
            str.ch = nullptr;
            str.length = 0;
            return 1;
        } else {
            str.ch = (char*)malloc(sizeof(char)*(len+1));  // 取len+1是为了'\0'
            if (str.ch == nullptr) return 0;  // 分配失败
            else {
                c = ch;
                for (int i = 0; i <= len; ++i, ++c) {
                    str.ch[i] = *c;   // 之所以取<=也是为了将'\0'复制过去
                }
                str.length = len;
                return 1;
            }
        }
    }
    

    11.2)取串长度操作

    int strlength(Str str) {
        return str.length;
    }
    

    11.3)串比较操作

    int strcompare(Str s1, Str s2) {
        for (int i = 0; i < s1.length && i < s2.length; ++i) {
            if (s1.ch[i] != s2.ch[i]) return s1.ch[i] - s2.ch[i];
        }
        return s1.length - s2.length;
    }
    

    11.4)串连接操作

    int concat(Str &str, Str str1, Str str2) {
        if (str.ch) {
            free(str.ch);  // 释放原空间
            str.ch = nullptr;
        }
        str.ch = (char*)malloc(sizeof(char)*(str1.length+str2.length));
        if (str.ch == nullptr) return 0;
        int i = 0;
        while (i < str1.length) {
            str.ch[i] = str1.ch[i];  
            ++i;
        }
        int j = 0;
        while (j <= str2.length) {
            str.ch[i+j] = str2.ch[j];  // 之所以取<=也是为了将'\0'复制过去
            ++j;
        }
        str.length = str1.length + str2.length;
        return 1;
    }
    
    

    11.5)求子串操作

    int substring(Str& substr, Str str, int pos, int len) {
        if (pos<0 || pos>=str.length || len<0 || len>str.length-pos) return 0;
        if (substr.ch) {
            free(substr.ch);
            substr.ch = nullptr;
        }
        if (len == 0) {
            substr.ch = nullptr;
            substr.length = 0;
            return 1;
        } else {
            substr.ch = (char*)malloc(sizeof(char)*(len+1));
            int i = pos;
            int j = 0;
            while (i<pos+len) {
                substr.ch[j++] = str.ch[i++];
            }
            substr.ch[j] = '\0';
            substr.length = len;
            return 1;
        }
    }
    

    11.6)串清空操作

    int clearstring(Str& str) {
        if (str.ch) {
            free(str.ch);
            str.ch = nullptr;
        }
        str.length = 0;
        return 1;
    }
    

    12. 串的模式匹配

    12.1)简单模式匹配算法

    int index(Str str, Str substr) {
        int i = 1, j = 1, k = i;
        while (i<=str.length && j<=substr) {
            if (str.ch[i] == substr[j]) {
                ++i;
                ++j;
            } else {
                j = 1;
                i = ++k;  // 匹配失败,i从主串的下一位置开始,k中记录了上一次的起始位置
            }
        }
        if (j>substr.length) return k;
        else return 0;
    }
    

    12.2)KMP算法

    注:这里的代码全部都认为下标从0开始

    (12.2.1)求next数组的代码

    void GetNext(char* p,int next[])
    {
        int pLen = strlen(p);
        next[0] = -1;
        int k = -1;
        int j = 0;
        while (j < pLen - 1)
        {
            //p[k]表示前缀,p[j]表示后缀
            if (k == -1 || p[j] == p[k])
            {
                ++k;
                ++j;
                next[j] = k;
            }
            else
            {
                k = next[k];
            }
        }
    }
    

    (12.2.2)求nextval数组的代码

    //优化过后的next 数组求法
    void GetNextval(char* p, int next[])
    {
        int pLen = strlen(p);
        next[0] = -1;
        int k = -1;
        int j = 0;
        while (j < pLen - 1)
        {
            //p[k]表示前缀,p[j]表示后缀
            if (k == -1 || p[j] == p[k])
            {
                ++j;
                ++k;
                //较之前next数组求法,改动在下面4行
                if (p[j] != p[k])
                    next[j] = k;   //之前只有这一行
                else
                    //因为不能出现p[j] = p[ next[j ]],所以当出现时需要继续递归,k = next[k] = next[next[k]]
                    next[j] = next[k];
            }
            else
            {
                k = next[k];
            }
        }
    }
    

    (12.2.3)KMP算法

    int KMP(char* s, char* p, int next[])
    {
        int i = 0;
        int j = 0;
        int sLen = strlen(s);
        int pLen = strlen(p);
        while (i < sLen && j < pLen)
        {
            //①如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++
            if (j == -1 || s[i] == p[j])
            {
                i++;
                j++;
            }
            else
            {
                //②如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]
                //next[j]即为j所对应的next值
                j = next[j];
            }
        }
        if (j == pLen)
            return i - j;  // 匹配成功,则返回匹配的位置
        else
            return -1;
    }
    

    13. 二叉树的结点定义

    13.1)普通二叉树的链式存储结点定义

    typedef struct BTNode {
        char data;   // 这里默认结点data域为char类型
    
        struct BTNode *lchild;  // 左儿子
        struct BTNode *rchild;  // 右儿子
    }BTNode;
    

    13.2)线索二叉树的结点定义

    // 线索二叉树
    typedef struct TBTNode{
        char data;
        int ltag, rtag;
        struct TBTNode *lchild;
        struct TBTNode *rchild;
    }TBTNode;
    

    13. 二叉树的遍历算法

    13.1)先序遍历(递归)

    void preorder(BTNode *p) {
        if (p != nullptr) {  // 一定要记得判空
            printf("%c ", p->data);
            preorder(p->lchild);
            preorder(p->rchild);
        }
    }
    

    13.2)中序遍历(递归)

    void inorder(BTNode *p) {
        if (p != nullptr) {
            inorder(p->lchild);
            printf("%c ", p->data);
            inorder(p->rchild);
        }
    }
    

    13.3)后序遍历(递归)

    void postorder(BTNode *p) {
        if (p != nullptr) {
            postorder(p->lchild);
            postorder(p->rchild);
            printf("%c ", p->data);
        }
    }
    

    13.4)层序遍历

    void level(BTNode *p) {
        BTNode *que[maxSize];
        BTNode *q = nullptr;
        int front = 0, rear = 0;  // 定义一个循环队列
    
        if (p != nullptr) {
            rear = (rear+1) % maxSize;
            que[rear] = p;  // 让根节点入队
            while (front != rear) {  // 只要队列不空,则进行循环
                front = (front+1) % maxSize;
                q = que[front];  // 队头元素出队
                printf("%c\n", q->data);  // 访问队头元素
    
                if (q->lchild) {  // 左子树存在,则左子树根节点入队
                    rear = (rear+1) % maxSize;
                    que[rear] = q->lchild;
                }
                if (q->rchild) {  // 右子树存在,则右子树根节点入队
                    rear = (rear+1) % maxSize;
                    que[rear] = q->rchild;
                }
            }
        }
    
    

    13.5)先序遍历(非递归)

    void preorderNonrecursion(BTNode *bt) {
        if (bt != nullptr) {
            BTNode *Stack[maxSize];
            int top = -1;  // 定义人工栈
            Stack[++top] = bt;  // 根节点入栈
            BTNode *p;
            while (top != -1) {  // 判断不空
                p = Stack[top--];  // 出栈 并完成一次访问
                printf("%c\n", p->data);
                if (p->rchild != nullptr) {   // 记得,先序遍历一定是先右孩子,再左孩子
                    Stack[++top] = p->rchild;
                }
                if (p->lchild != nullptr) {
                    Stack[++top] = p->lchild;
                }
            }
        }
    }
    

    13.6)中序遍历(非递归)

    void inorderNonrecursion(BTNode *bt) {
        BTNode *Stack[maxSize];
        int top = -1;
        BTNode *p = bt;
        if (bt != nullptr) {
            while (top != -1 || p != nullptr) {
                while (p != nullptr) {
                    Stack[++top] = p;
                    p = p->lchild;
                }
    
                if (top != -1) {
                    p = Stack[top--];
                    printf("%c\n", p->data);
                    p = p->rchild;
                }
            }
        }
    }
    

    13.7)后序遍历(非递归)

    void postorderNonrecursion(BTNode *bt) {
        if (bt != nullptr) {
            BTNode *Stack1[maxSize]; int top1 = -1;
            BTNode *Stack2[maxSize]; int top2 = -1;  // 定义两个栈
            BTNode *p;
            Stack1[++top1] = bt;
            while (top1 != -1) {
                p = Stack1[top1--];
                Stack2[++top2] = p;  // 注意这里与先序的区别,放入栈2中即可
                if (p->lchild) {
                    Stack1[++top1] = p->lchild;
                }
                if (p->rchild) {
                    Stack1[++top1] = p->rchild;
                }
            }
            // 这时候循环结束,则会将逆后序遍历的结果都存放到了栈2中
            // 所以对栈2进行输出即可得到后序遍历的结果
            while (top2 != -1) {
                p = Stack2[top2--];
                printf("%c\n", p->data);
            }
        }
    }
    

    14. 图的存储结构

    14.1)邻接矩阵的结点定义

    typedef struct {
        int no;  // 顶点编号
        char info;  // 顶点的其他信息,这里默认为char型。这一句一般在题目中很少用到,因此题目不做特殊要求可以不写
    }VertexType;  // 顶点类型
    
    typedef struct {
        int edges[maxSize][maxSize];  // 临街矩阵定义,如果是有权图,则在此句中将int改为float
        int n, e;  // 分别为定点数和边数
        VertexType vex[maxSize];  // 存放节点信息
    }MGraph;  // 图的邻接矩阵类型
    

    14.2)邻接表的结点定义

    typedef struct ArcNode{
        int adjvex;  // 该边所指向的节点的位置
        struct ArcNode *nextarc;  // 指向下一条边的指针
        int info;  // 该边的相关信息(如权值)
    }ArcNode;
    
    typedef struct {
        char data;  // 定点信息
        ArcNode *firstarc;  // 指向第一条边的指针
    }VNode;
    
    typedef struct{
        VNode adjlist[maxSize];  // 邻接表
        int n, e;  // 定点数和边数
    }AGraph;  // 图的邻接表类型
    
    

    15. 图的遍历方式

    15.1)DFS

    int visit[maxSize];
    void DFS(AGraph *G, int v) {
        ArcNode *p;
        visit[v] = 1;
        cout << v << endl;
        p = G->adjlist[v].firstarc;  // 让p指向顶点v的第一条边
        while (p != nullptr) {
            if (visit[p->adjvex] == 0) {
                DFS(G, p->adjvex);
                p = p->nextarc;
            }
        }
    }
    

    15.2)BFS

    void BFS(AGraph *G, int v) {
        ArcNode *p;
        int que[maxSize], front = 0, rear = 0;  // 定义一个队列
        int j;
        cout << v << endl;
        visit[v] = 1;
        rear = (rear+1)%maxSize;  // 入队
        que[rear] = v;
        while (front != rear) {
            front = (front+1)%maxSize;  // 顶点出队
            j = que[front];
            p = G->adjlist[j].firstarc;  // p指向出队顶点j的第一条边
            while (p != nullptr) {  // 将p的所有邻接点未被访问的入队
                if (visit[p->adjvex] == 0) {
                    cout << p->adjvex << endl;
                    rear = (rear+1)%maxSize;
                    que[rear] = p->adjvex;
                }
                p = p->nextarc;
            }
        }
    }
    

    16. 最小(代价)生成树

    16.1)Prim算法

    void Prim(MGraph g, int v0, int &sum) {
        int lowcost[maxSize], vset[maxSize], v;
        int i, j, k, min;
        v = v0;
        for (i = 0; i < g.n; ++i) {
            lowcost[i] = g.edges[v0][i];
            vset[i] = 0;
        }
        vset[v0] = 1;  // 将v0并入树中
        sum = 0;  // sum清零用来累计树的权值
        for (i = 0; i < g.n-1; ++i) {
            min = INF;  // INF是一个已经定义的比图中所有边权值都大的常量
            // 下面这个循环用于选出候选边中的最小者
            for (j = 0; j < g.n; ++j) {
                if (vset[j] == 0 && lowcost[j] < min) {  // 选出当前生成树其他顶点到最短边中最短的一条
                    min = lowcost[j];
                    k = j;
                }
                vset[k] = 1;
                v = k;
                sum += min;  // 这里用sum记录了最小生成树的权值
                // 下面这个循环以刚进入的顶点v为媒介更新候选边
                for (j = 0; j < g.n; ++j) {
                    if (vset[j] == 0 && g.edges[v][j] < lowcost[j]) {
                        lowcost[j] = g.edges[v][j];
                    }
                }
            }
        }
    }
    

    16.2)Kruskal算法

    typedef struct {
        int a, b;  // a和b为一条边所连的两个顶点
        int w;  // 边的权值
    }Road;
    Road road[maxSize];
    int v[maxSize];  // 定义并查集数组
    int getRoot(int a) {
        while (a != v[a])  a = v[a];  // 在并查集中查找根结点的函数
        return a;
    }
    
    void Kruskal(MGraph g, int &sum, Road road[]) {
        int i, N, E, a, b;
        N = g.n;
        E = g.e;
        sum = 0;
        for (i = 0; i < N; ++i)  v[i] = i;
        sort(road, E);   // 对road数组中的E条边按其权值从小到大排序, 假设该函数已定义好
        for (i = 0; i < E; ++i) {
            a = getRoot(road[i].a);
            b = getRoot(road[i].b);
            if (a != b) {
                v[a] = b;
                sum += road[i].w;
            }
        }
    }
    

    17. 最短路径算法

    17.1)Dijkstra算法

    void Dijkstra(MGraph g, int v, int dist[], int path[]) {
        int set[maxSize];
        int min, i, j, u;
        // 从这句开始对各数组进行初始化
        for (i = 0; i < g.n; ++i) {
            dist[i] = g.edges[v][i];
            set[i] = 0;
            if (g.edges[v][i] < INF)
                path[i] = v;
            else {
                path[i] = -1;
            }
        }
        set[v] = 1; path[v] = -1;
        //  初始化结束
        // 关键操作开始
        for (i = 0; i < g.n-1; ++i) {
            min = INF;
            // 这个循环每次从剩余顶点中选出一个顶点,通往这个顶点的路径在通往所有剩余顶点的路径中是长度最短的
            for (j = 0; j < g.n; ++j) {
                if (set[j] == 0 && dist[j] < min) {
                    u = j;
                    min = dist[j];
                }
            }
            set[u] = 1;  // 将选出的顶点并入最短路径中
            // 这个循环以刚并入的顶点作为中间点,对所有通往剩余顶点的路径进行检测
            for (j = 0; j < g.n; ++j) {
                // 这个if语句判断顶点u的加入是否为出现通往顶点j的更短的路径
                if (set[j] == 0 && dist[u]+g.edges[u][j] < dist[j]) {
                    dist[j] = dist[u] + g.edges[u][j];
                    path[j] = u;
                }
            }
        }
    }
    

    17.2)Floyd算法

    void Floyd(MGraph g, int Path[][maxSize]) {
        int i, j, k;
        int A[maxSize][maxSize];
        // 这个双循环对数组A[][]和Path[][]进行了初始化
        for (i = 0; i < g.n; ++i) {
            for (j = 0; j < g.n; ++j) {
                A[i][j] = g.edges[i][j];
                Path[i][j] = -1;
            }
        }
        // 下面三层循环是主要操作,完成了以k为中间点对所有的顶点对{i, }进行检测和修改
        for (k = 0; k < g.n; ++k) {
            for (i = 0; i < g.n; ++i) {
                for (j = 0; j < g.n; ++j) {
                    if (A[i][j] > A[i][k] + A[k][j]) {
                        A[i][j] = A[i][k] + A[k][j];
                        Path[i][j] = k;
                    }
                }
            }
        }
    }
    

    18. 拓扑排序

    18.1)拓扑排序中对邻接表表头结构的修改

    typedef struct {
        char data;
        int count;  // 此处为新增代码,count用来统计顶点当前的入度
        ArcNode *firstarc;
    }VNode;
    

    18.2)拓扑排序算法

    int TopSort(AGraph *G) {
        int i, j, n = 0;
        int stack[maxSize], top = -1;  // 定义并初始化栈
        ArcNode *p;
        // 这个循环将图中入度为0的顶点入栈
        for (i = 0; i < G->n; ++i) {  // 图中的顶点从0开始编号
            if (G->adjlist[i].count == 0) {
                stack[++top] = i;
            }
        }
        // 关键操作开始
        while (top != -1) {
            i = stack[top--];  // 顶点出栈
            ++n;  // 计数器加1,统计当前顶点
            cout << i << " ";  // 输出当前顶点
            p = G->adjlist[i].firstarc;
            // 这个循环实现了将所有由此顶点引出的边所指向的顶点的入度都减少1
            // 并将这个过程中入度变为0的顶点入栈
            while (nullptr != p) {
                j = p->adjvex;
                --(G->adjlist[j].count);
                if (G->adjlist[j].count == 0)
                    stack[++top] = j;
                p = p->nextarc;
            }
        }
        // 关键操作结束
        return n == G->n;
    }
    

    19. 排序算法

    19.1)直接插入排序

    void InsertSort(int a[], int n) {
        int i, j;
        int temp;
        for (i = 1; i < n; ++i) {
            if (a[i] < a[i-1]) {
                temp = a[i];  
                for (j = i; a[j-1] > temp && j >= 1; --j) {
                    a[j] = a[j-1];
                }
                a[j] = temp;
            }
        }
    }
    

    19.2)折半插入排序

    void BinaryInsertSort(int R[],int n) {
        int i,j,low,mid,high,temp;
        for(i=1; i<n; i++) {
            low=0;
            high=i-1;
            temp=R[i];
            // 下面的折半是为了在i元素的前面查找到合适的插入位置
            while(low <= high) {
                mid=(low+high)/2;
                if(R[mid]>temp) {
                    high=mid-1;
                } else {
                    low=mid+1;
                }
            }
            for(j=i-1;j>=high+1;j--) {
                R[j+1]=R[j];
            }
            R[j+1]=temp;   
        }
    }
    

    19.3)希尔排序

    // 更小间隔的排序并没有破坏之前的排序后的相对性,但是排序的结果可能不一样了
    void ShellSort(int arr[], int n) {
        for (int d = n/2; d > 0; d /= 2) {
            // 下面的内容就是把上面插入排序中所有的1改为d,一共有5处修改,别忘了--j也要改
            for (int i = d; i < n; ++i) {
                int temp = arr[i];
                int j;
                for (j = i; j >= d && temp < arr[j-d]; j -= d) {
                    arr[j] = arr[j-d];
                }
                arr[j] = temp;
            }
        }
    }
    

    19.4)起泡排序

    void BubbleSort(int arr[], int n) {
        int temp;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n-i-1; ++j) {
                if (arr[j] > arr[j+1]) {
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
    

    19.5)快速排序

    (19.5.1)两路快排

    void QuickSort(int arr[], int l, int r) {
        if (l >= r) return;
        swap(arr[l], arr[rand()%(r-l+1)+l]);
        int v = arr[l];
    
        // arr[l+1...i) <= v, arr(j...r] >= v
        int i = l+1, j = r;  // 一边开,一边闭,所以初始值取端点值即可
        while (1) {
            while (i <= r && arr[i] < v) ++i;
            while (j >= l+1 && arr[j] > v) --j;
            if (i > j) break;
            swap(arr[i++], arr[j--]);
        }
        swap(arr[l], arr[j]);
        int p = j;
        
        QuickSort(arr, l, p-1);
        QuickSort(arr, p+1, r);
    }
    

    (19.5.2)三路快排

    // 三路快排(性能最好)
    template <typename T>
    void __quickSort3Ways(T arr[], int l, int r) {
        if (l >= r) return;
    
        // partition
        swap(arr[l], arr[rand()%(r-l+1)+l]);
        T v = arr[l];
        int lt = l;  // arr[l+1...lt] < v
        int gt = r+1;  // arr[gt...r] > v
        int i = l+1;  // arr[lt+1...i) == v
        while (i < gt) {
            if (arr[i] < v) {
                swap(arr[++lt], arr[i++]);
            } else if (arr[i] > v) {
                swap(arr[--gt], arr[i]);
            } else {
                ++i;
            }
        }
    
        swap(arr[l], arr[lt]);
        __quickSort3Ways(arr, l, lt-1);
        __quickSort3Ways(arr, gt, r);
    }
    

    19.6)简单选择排序

    void SelectSort(int arr[], int n) {
        int temp;
        for (int i = 0; i < n; ++i) {
            for (int j = i+1; j < n; ++j) {
                if (arr[i] > arr[j]) {
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }
    

    19.7)堆排序

    (19.7.1)shiftDown操作

    // 在原地堆排序中,元素是从数组下标0的位置开始存储的,因此i的左孩子应该为2*i+1
    template <typename T>
    void __shiftDown(T arr[], int n, int k) {
        while (2*k+1 < n) {
            int j = 2*k + 1;
            if (j + 1 < n && arr[j+1] > arr[j]) {
                ++j;
            }
            if (arr[k] >= arr[j]) break;
            swap(arr[j], arr[k]);
            k = j;
        }
    }
    

    (19.7.2)堆排序代码

    template <typename T>
    void heapSort3(T arr[], int n) {
        // heapify
        for (int i = (n-1)/2; i >= 0; --i) {
            __shiftDown(arr, n, i);
        }
    
        for (int i = n-1; i > 0; --i) {
            swap(arr[0], arr[i]);
            __shiftDown(arr, i, 0);
        }
    }
    

    19.8)归并排序

    (19.8.1) merge操作

    // 将arr[l...mid]和arr[mid+1...r]进行归并
    template <typename T>
    void __merge(T arr[], int l, int mid, int r) {
        T aux[r-l+1];
        for (int i = l; i <= r; ++i) {
            aux[i-l] = arr[i];
        }
        int i = l, j = mid+1;
        for (int k = l; k <= r; ++k) {
            // 首先处理i, j越界
            if (i > mid) {
                arr[k] = aux[j-l];
                ++j;
            } else if (j > r) {
                arr[k] = aux[i-l];
                ++i;
            } else if (aux[i-l] <= aux[j-l]) {
                arr[k] = aux[i-l];
                ++i;
            } else {
                arr[k] = aux[j-l];
                ++j;
            }
        }
    }
    

    (19.8.2)递归的归并排序算法

    // 递归使用归并排序,对arr[l...r]的范围进行排序
    template <typename T>
    void __mergeSort(T arr[], int l, int r) {
        if (l >= r) return;
        int mid = l + (r-l)/2;
        __mergeSort(arr, l, mid);
        __mergeSort(arr, mid+1, r);
        if (arr[mid] > arr[mid+1]) {  // 优化处理,使之能够更好处理近乎有序的数组
            __merge(arr, l, mid, r);
        }
    }
    

    (19.8.3)非递归的归并排序算法

    // 使用循环进行自底向上的归并排序
    template <typename T>
    void mergeSortBU(T arr[], int n) {
        for (int sz = 1; sz <= n; sz += sz) {
            // 对arr[i...i+sz-1]和arr[i+sz...i+sz+sz-1]进行归并
            for (int i = 0; i + sz < n; i += sz+sz) {  
                // 细节一:i+sz < n是为了防止前一段的右端点i+sz-1不会越界
                if (arr[i+sz-1] > arr[i+sz]) {
                    __merge(arr, i, i+sz-1, min(i+sz+sz-1, n-1));  
                    // 细节二:min在这里的作用是为了防止后一段的右端点i+sz+sz-1不会越界
                }
            }
        }
    }
    /*由于自底向上的归并排序没有直接使用索引对数据进行操作,
    因此可以方便应用于对链表这种结构进行排序的过程中*/
    

    20. 折半查找法

    int Bsearch(int arr[], int low, int high, int k) {
        int mid;
        while (low < high) {
            mid = (low+high) / 2;
            if (arr[mid] == k) {
                return mid;
            } else if (arr[mid] > k) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return 0;
    }
    

    21. 二叉排序树

    21.1)二叉排序树的结点定义

    typedef struct BTNode {
        int key;
        struct BTNode *lchild;
        struct BTNode *rchild;
    }BTNode;
    

    21.2)二叉排序树的查找算法

    BTNode* BSTSearch(BTNode *bt, int key) {
        if (bt == nullptr) return nullptr;
        if (bt->key == key) {
            return bt;
        } else if (key < bt->key) {
            return BSTSearch(bt->lchild, key);
        } else {
            return BSTSearch(bt->rchild, key);
        }
    }
    

    21.3)二叉排序树的插入算法

    int BSTInsert(BTNode *&bt, int key) {  // 因为bt要改变,所以要用引用型指针
        if (bt == nullptr) {
            bt = (BTNode*)malloc(sizeof(BTNode));  // 创建新结点
            bt->lchild = bt->rchild = nullptr;
            bt->key = key;
            return 1;
        } else {
            if (key == bt->key) return 0;   // 关键字已经存在于树中
            else if (key < bt->key) return BSTInsert(bt->lchild, key);
            else return BSTInsert(bt->rchild, key);
        }
    }
    

    21.4)二叉排序树的构造算法

    void CreateBST(BTNode *&bt, int key[], int n) {
        bt = nullptr;  // 将树清空
        for (int i = 0; i < n; ++i) {
            BSTInsert(bt, key[i]);
        }
    }
    

    <2020年考研,必须上岸>

    展开全文
  • 数据结构重点代码总结(考研

    千次阅读 多人点赞 2020-09-07 21:26:24
    } } if(count 查找 顺序查找 typedef struct{ //查找表的数据结构 ElemType *elem; //元素存储空间基址,建表时按实际长度分配,0号单元留空 int TableLen; //表的长度 }SSTable; int Search_Seq(SSTable ST,...

    线性表

    顺序表的定义
    #define MaxSize 50
    typedef struct{
    
    	ElemType data[MaxSize];
    
    	int length;
    
    }SqList;
    
    顺序表插入

    在下标为i的位置插入元素e:

    bool ListInsert(SqList &L, int i, ElemType e){
    	if(i<0||i>L.length||L.length==MaxSize)			//i取0到length
    		return false;
    	for(int j=L.length-1; j>=i; --j)
    		L.data[j+1]=L.data[j];			//从后往前,逐个将元素后移一个位置
    	L.data[i]=e;
    	++(L.length);
    	return true;
    }
    
    abcdef
    0123456
    顺序表删除

    删除下标为i的元素,并返回元素值e:

    bool ListDelete(SqList &L, int i, ElemType &e){
    	if(i<0||i>L.length-1)
    		return false;
    	e=L.data[i];
    	for(int j=i; j<L.length-1; ++j)
    		L.data[j]=L.data[j+1];
    	--(L.length);
    	return true;
    }
    
    顺序表按值查找

    查找第一个等于e的元素,并返回其下标:

    int LocateElem(SqList L, ElemType e){
    	int i;
    	for(i=0; i<L.length; ++i){
    		if(L.data[i]==e)
    			return i;
    	}
    	return 0;
    }
    
    元素逆置

    设计一个高效算法,将顺序表所有元素逆置,要求算法的空间复杂度为O(1):

    void Reverse(SqList &L,){
    	ElemType temp;		//定义一个临时变量
    	for(int i=0,j=L.length-1; i<j; ++i,--j){
    		temp=a[i];
    		a[i]=a[j];
    		a[j]=temp;
    	}
    }
    
    合并顺序表

    将两个有序顺序表合并成新的有序顺序表,并由函数返回结果顺序表:

    bool Merge(SqList A, SqList B, SqList &C){
    	if(A.length+B.length>C.MaxSize)
    		return false;
    	int i=0,j=0,k=0;
    	while(i<A.length && j<B.length){
    		if(A.data[i]<=B.data[j]){		//若A中元素值小于B中元素值,则A值入C
    			C.data[k]=A.data[i];
    			++k;
    			++i;
    		}else{
    			C.data[k]=B.data[j];
    			++k;
    			++j;
    		}
    	}
    	while(i<A.length){				//若A中有剩余
    			C.data[k]=A.data[i];
    			++k;
    			++i;
    	}
    	while(j<B.length){				//若A中有剩余
    		C.data[k]=B.data[j];
    			++k;
    			++j;
    	}
    	C.length=k;
    	return true;
    }
    
    单链表定义
    typedef struct LNode{			//因为结构体中包含了LNode,所以定义结构体时struct后面要加LNode
    	ElemType data;
    	struct LNode *next;
    }LNode, *LinkList;
    
    头插法

    头插法建立单链表(天勤)

    void List_HeadInsert(LNode *&C, int a[], int n){
    	LNode *s;				//s用来指向新申请的结点
    	int i;
    	C=(LNode *)malloc(sizeof(LNode));	//申请C的头结点空间
    	C->next=NULL;
    	for(i=0; i<n; ++i){
    		s=(LNode*)malloc(sizeof(LNode));
    		s->data=a[i];
    		s->next=C->next;	//新插入的s结点的next指向头结点C的next
    		C->next=s;			//头结点C的next指向新建的s结点
    	}
    	r->next=NULL;
    }
    
    尾插法

    尾插法建立单链表(天勤)

    void List_TailInsert(LNode *&C, int a[], int n){
    	LNode *s, *r;
    	int i;
    	C=(LNode *)malloc(sizeof(LNode));
    	C->next=NULL;
    	r=C;
    	for(i=0; i<n; ++i){
    		s=(LNode *)malloc(sizeof(LNode);
    		s->data=a[i];
    		r->next=s;		//r所在的next指向新建的s结点
    		r=r->next;
    	}
    	r->next=NULL;
    }
    
    合并链表

    A,B是两个带头结点的单链表,其中元素递增有序,设计一个算法,将A,B归并成一个按元素值非递减有序的链表C,C由A和B中的结点组成。

    void Merge(LNode *A, LNode *B, LNode *&C){
    	LNode *p=A->next;
    	LNode *q=B->next;
    	LNode *r;			//r始终指向C的终端结点
    	C=A;
    	C->next=NULL;
    	free(B);
    	r=C;
    	while(p!=NULL && q!=NULL){
    		if(p->data<=q->data){
    			r->next=p;
    			p=p->next;
    			r=r->next;
    		}
    		else{
    			r->next=q;
    			q=q->next;
    			r=r->next;
    		}
    	}
    	r->next=NULL;
    	if(p!=NULL)			//将剩余结点链接在C的尾部
    		r->next=p;
    	if(q!=NULL)
    		r->next=q;
    }
    

    栈与队列

    基本概念

    当n个元素以某种顺序进栈,并在任意时刻出栈,排列数目 N= 1 n + 1 \frac{1}{n+1} n+11 KaTeX parse error: Undefined control sequence: \C at position 1: \̲C̲_{2n}^{n}= ( 2 n ) ! ( n + 1 ) ( n ! ) 2 \frac{(2n)!}{(n+1)(n!)^2} (n+1)(n!)2(2n)!

    栈:先进后出; 队列:先进先出;

    当较大的数首先出栈时,较小的数都是降序压在栈内的。

    循环队列:

    ​ 队空状态:qu.rear==qu.front;

    ​ 队满状态:(qu.rear+1)%maxSize==qu.front;

    递归过程或者函数调用时,处理参数及返回地址要用栈。

    串是一种特殊的线性表,其数据元素是一个字符。

    树与二叉树

    基本概念

    结点数 = 度数 + 1

    度为m的树第i层至多有 mi-1 个结点

    高度为h的m叉树至多有(mh-1)/(m-1)个结点

    具有n个结点的m叉树最小高度为 ⌈ \lceil logm(n(m-1)+1) ⌉ \rceil

    非空二叉树上叶子结点数等于双分支结点数加1

    总结点数=n0+n1+···+nm

    总分支数=1n1+2n2+···+m*nm

    总分支数=总结点数-1 ③

    由①②③得 n0=1+n2+2n3+···+(m-1)nm

    二叉树的第i层上最多有 2i-1个结点

    高度为k的二叉树上最多有2k-1个结点

    具有n个结点的完全二叉树的深度为 ⌊ \lfloor log2n ⌋ \rfloor +1

    在哈夫曼二叉树中任何一个序列都不是另一个序列的前缀,且树中不含单分支结点

    二叉树链式存储结构定义
    typedef struct BiTNode{
    	ElemType data;
    	struct BiTNode *lchild, *rchild;
    }BiTNode, *BiTree;
    
    二叉树遍历
    先序遍历递归(根左右)
    void PreOrder(BiTree T){
    	if(T!=NULL){
    		visit(T);
    		PreOrder(T->lchild);
    		PreOrder(T->rchild);
    	}
    }
    
    中序遍历递归(左根右)
    void InOrder(BiTree T){
    	if(T!=NULL){
    		InOrder(T->lchild);
    		visit(T);
    		InOrder(T->rchild);
    	}
    }
    
    后序遍历递归(左右根)
    void PostOrder(BiTree T){
    	if(T!=NULL){
    		PostOrder(T->lchild);
    		PostOrder(T->rchild);
    		visit(T);
    	}
    }
    
    先序遍历递归(根左右)
    void PreOrder(BiTree T){
    	InitStack(S);
    	BiTree T;
    	while(p||!IsEmpty(S)){		//栈不空或p不空时循环
    		if(p){					//一路向左
    			visit(p);
    			Push(S,p);
    			p=p->lchild;
    		}
    		else{
    			Pop(S,p);
    			p=p->rchild;
    		}
    	}
    }
    
    中序遍历非递归(左根右)
    void InOrder(BiTree T){
    	InitStack(S);
    	BiTree p=T;
    	while(p||!IsEmpty(S)){		//栈不空或p不空时循环
    		if(p){
    			Push(S,p);
    			p=p->lchild;
    		}
    		else{
    			Pop(S,p);
    			visit(p);
    			p=p->rchild;
    		}
    	}
    }
    
    后序遍历非递归(左右根)
    void PostOrder(BiTree){
    	InitStack(S);
    	p=T;
    	r=NULL;
    	while(p||!IsEmpty(S)){
    		if(p){								//走到最左边
    			Posh(S,p);
    			p=p->lchild;
    		}
    		else{								//向右
    			GetTop(S,p);					//读栈顶结点(非出栈)
    			if(p->rchild && p->rchild!=r){	//若左子树存在且未被访问过
    				p=p->rchild;				//转向右
    				Push(S,p);					//压栈
    				p=p->lchild;				//再走到最左
    			}
    			else{							//否则,弹出结点并访问
    				Pop(S,p);					//出栈
    				visit(p->data);
    				r=p;						//记录最近访问过的结点
    				p=NULL;
    			}
    		}
    	}
    }
    
    
    层次遍历
    void LevelOrder(BiTree T){
    	InitQueue(Q);		//初始化辅助队列
    	BiTree T;
    	EnQueue(Q,T);		//根节点入队
    	while(!IsEmpty(Q)){
    		DeQueue(p);		//队头结点出队
    		visit(p);
    		if(p->lchild!=NULL)		//若左子树不空,左子树根节点入队
    			EnQueue(Q,p->lchild);
    		if(p->rchild!=NULL)
    			EnQueue(Q,p->rchild);
    	}
    }
    

    基本概念

    有向完全图:若有向图有n个顶点,则最多有n(n-1)条边,将具有n(n-1)条边的有向图成为有向完全图。

    无向完全图:若无向图有n个结点,则最多有n(n-1)/2条边,将具有n(n-1)/2条边的有向图成为无向完全图。

    连通图:如果图中任意两个顶点都连通,则称该图为连通图;否则,图中的极大连通子图称为连通分量。

    强连通图:在有向图中,从vi到vj和从vj到vi都有路径,则称该图为强连通图;否则将其中的极大强连通子图称为强连通分量。

    图的定义
    邻接矩阵定义
    #define MaxVertexNum 100		//顶点数目的最大值
    typedef char VertexType;		//顶点的数据类型
    typedef int EdgeType;			//带权图中边上权值的数据类型
    typedef struct{
    	VertexType Vex[MaxVertexMum];	//顶点表
    	EdgeType Edge[MaxVertexMum][MaxVertexNum];	//邻接矩阵,边表
    	int vexnum, arcnum;			//图当前的定点数和边数
    }
    
    邻接表存储结构定义
    #define MaxVertexNum 100		//图中顶点数的最大值
    typedef struct ArcNode{			//边表结点
    	int adjvex;					//该弧指向的顶点的位置
    	struct ArcNode *next;		//指向下一条弧的指针
    }ArcNode;
    typedef struct VNode{			//顶点表结点
    	VertexType data;			//顶点信息
    	ArcNode *first;				//指向第一条依附该顶点的弧的指针
    }VNode, AdjList[MaxVertexNum];
    typedef struct{					
    	AdjList vertices;			//邻接表
    	int vexnum; arcnum;			//图的顶点数和弧数
    }ALGraph;						//ALGraph是以邻接表存储的图类型
    
    图的遍历
    图的广度优先遍历
    bool visited[MAX_VERTEX_NUM];	//访问标记数组
    void BFSTraverse(Graph G){		//对图G进行广度优先遍历
    	for(i=0; i<G.vexnum; ++i)	
    		visited[i]=FALSE;		//访问标记数组初始化
    	InitQueue(Q);				//初始化辅助队列Q
    	for(i=0; i<G.vexnum; ++i)	//从0号顶点开始遍历
    		if(!visited[i])			//对每个连通分量调用一次BFS
    			BFS(G,i);			//vi未访问过,从vi开始BFS
    }
    void BFS(Graph G, int v){		//从顶点v出发,广度优先遍历图G
    	visit(v);	
    	visited[v]=TRUE;			//对v做以访问标记
    	EnQueue(Q,v);				//顶点v入队Q
    	while(!isEmpty(Q)){
    		DeQueue(Q,v);
    		for(w=FirstNeighbor(G,v); w>=0; w=NexNeighbor(G,v,w)){	//检测v所有邻接点
    			if(!visited[w]){	//w为v的尚未访问的邻接顶点
    				visit(w);
    				visited[w]=TRUE;
    				EnQueue(Q,w);
    			}
    		}
    	}
    }
    
    图的深度优先遍历
    bool visited[MAX_VERTEX_NUM];	//建立访问标记数组
    void DFSTraverse(Graph G){		//对图G进行深度优先遍历
    	for(v=0; v<G.vexnum; ++v)	//将所有位置都置false
    		visited[v]=FALSE;
    	for(v=0; v<G.vexnum; ++v)	
    		if(!visited[v])			//只要未被访问过就执行DFS
    			DFS(G,v);
    }
    void DFS(Graph G, int v){		//从顶点v出发,深度优先遍历图G
    	visit(v);
    	visited[v]=TRUE;
    	for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w))
    		if(!visited[w]){		//若w未被访问,则执行DFS
    			DFS(G,w);
    		}
    }
    
    拓扑排序
    拓扑排序算法实现(17年考过一次)
    bool TopologicalSort(Graph G){
    	InitStack(S);				//初始化栈,存储入度为0的顶点
    	for(int i=0; i<G; ++i)
    		if(indegree[i]==0)		//将所有入度为0的顶点进栈
    			Push(S,i);
    	int count=0;				//记录当前已经输出的顶点数
    	while(!IsEmpty(S)){			//栈不空则存在入度为0的顶带你
    		Pop(S,i);
    		print[count++]=i;		//输出顶点i
    		for(p=G.vertices[i].firstarc; p; p=p->nextarc){
    		//将所有i指向的顶点的入度减1,并且将入度为0的顶点压入栈S
    			v=p->adjvex;
    			if(!(--indegree[v]))	//入度为0则入栈
    				Push(S,v);
    		}
    	}
    	if(count<G.vexnum)	//排序失败,有向图中有回路
    		return false;
    	else
    		return true;	//排序成功
    }
    

    查找

    顺序查找
    typedef struct{			//查找表的数据结构
    	ElemType *elem;		//元素存储空间基址,建表时按实际长度分配,0号单元留空
    	int TableLen;		//表的长度
    }SSTable;
    int Search_Seq(SSTable ST, ElemType key){
    	ST.elem[0]=key;		//“哨兵”
    	for(i=ST.TableLen; ST.elem[i]!=key; --i);	//从后往前找
    	return i;			//若表中不存在key,将查找到i为0时退出for循环
    }
    
    折半查找
    int Binary_Search(SeqList L, ElemType key){
    	int low=0, high=L.TableLen-1, mid;
    	while(low<=high){
    		mid=(low+high)/2;
    		if(L.elem[mid]==key)
    			return mid;
    		else if(L.elem[mid]>key)
    			high=mid-1;
    		else
    			low=mid+1;
    	}
    	return -1;
    }
    

    排序

    冒泡排序
    void BubbleSort(ElemType A[], int n){
    	for(i=0; i<n-1; ++i){
    		flag=false;				//表示本趟冒泡是否发生交换的标志
    		for(j=n-1; j>i; --j){	//一趟冒泡过程
    			if(A[j-1]>A[j]){	//若为逆序
    				swap(A[j-1],A[j]);	//交换
    				flag=true;
    			}
    		}
    		if(flag==false)
    			return 0;			//本趟遍历后没有发生交换,说明表已有序
    	}
    }
    
    快速排序
    void QuickSort(ElemType A[], int low, int high){
    	if(low<high){									//递归跳出的条件
    	//Partition()就是划分操作,将表A[low···high]划分为满足上述条件的两个子表
    		int pivotpos=Partition(A,low,high);	//划分
    		QuickSort(A,low,pivotpos-1);		//依次对两个子表进行递归排序
    		QuickSort(A,pivotpos-1,high);
    	}
    }
    int Partition(ElemType A[], int low, int high){		//一趟划分
    	ElemType pivot=A[low];	//将表中第一个元素设为枢轴,对表进行划分
    	while(low<high){		//循环跳出条件
    		while(low<high && A[high]>=pivot)
    			--high;
    		A[low]=A[high];		//将比枢轴小的元素移动到左端
    		while(low<high && A[low]<=pivot)
    			++low;
    		A[high]=A[low];		//将比枢轴大的元素移动到右端
    
    	}
    	A[low]=pivot;			//枢轴元素存放到最终位置
    	return low;				//返回存放枢轴的最终位置
    }
    
    简单选择排序
    void SelectSort(ElemType A[], int n){
    	for(i=0; i<n-1; ++i){
    		min=i;							//记录最小元素位置
    		for(j=i+1; j<n; ++j)			//在A[i...n-1]中选择最小的元素
    			if(A[j]<A[min])				//更新最小元素位置
    				min=j;
    		if(min!=i)						//封装的swap()函数共移动元素3次
    			swap(A[i],A[min]);
    	}
    }
    
    各种排序的算法性质

    排序算法分析

    展开全文
  • 考研数据结构代码总结

    千次阅读 多人点赞 2020-10-30 15:51:05
    数据结构所有代码总结

    一、线性表

    1.1 顺序表

    • 顺序表的结构描述
    typedef struct
    {
    	int data[maxSize];
    	int length;
    }Sqlist;
    
    • 插入元素
    int insertElem(int A[],int &len,int p,int k) //考试中顺序表常用方式(一般不使用结构体) p为要插入的位置,k为插入值 
    {
    	int i;
    	if(p<0 || p>len || len==maxSize)
    		return 0;
    	for(i=len-1;i>=p;i--)
    	{
    		A[i+1]=A[i];//元素后移 
    	}
    	A[p]=k;
    	len++;
    	return 1;
    }
    
    • 删除元素
    int delElem(int A[],int &len,int p)
    {
    	int i;
    	if(p<0 || p>len-1)
    		return 0;
    	for(i=p;i<len-1;i++) //注意i<len-1,不需要让i到达最后一个元素 
    		A[i]=A[i+1]; //前移
    	--len;
    	return 1;
    }
    

    1.2 单向链表

    #include <iostream>
    using namespace std;
    //类型描述
    typedef struct LNode
    {
    	int data;
    	struct LNode *next;
    }LNode;
    
    //尾插法创建 
    void createlistR(LNode *&C,int a[],int n)
    {
    	LNode *s,*r;//r是尾指针,s指向每一次的新节点 
    	int i;
    	C=(LNode *)malloc(sizeof(LNode));
    	C->next=NULL;
    	r=C;
    	for(i=0;i<n;i++)
    	{
    		s=(LNode*)malloc(sizeof(LNode));
    		s->data=a[i];
    		s->next=NULL;
    		r->next=s;
    		r=s; 
    	}
    }
    //头插法创建 
    void createlistF(LNode *&C,int a[],int n)
    {
    	//关键代码:
    	LNode *s;
    	s->data=a[i];
    	s->next=C->next;
    	C->next=s; 
    }
    //插入节点
    void insert()
    {
    	//keycode:
    	LNode *s,*p;
    	s->next=p->next;
    	p->next=s;
    } 
    //删除节点
    void del(LNode *L)
    {
    	//关键代码: 
    	LNode *p,*q;//删除p的后继
    	q=p->next;
    	p->next=q->next;
    	free(q); 
    }
    int main()
    {
    	return 0;
    }
    

    1.3 单向循环链表

    #include <iostream>
    using namespace std;
    //类型描述
    typedef struct LNode
    {
    	int data;
    	struct LNode *next;
    }LNode;
    // 初始化
    int init(LNode *&L)
    {
    	L=(LNode *)malloc(sizeof(LNode));
    	L->next=L;
    }
    // 插入节点
    int insert(LNode *L,int i,int x)//插入到第i-1到i个位置之间 
    {
    	LNode *p;
    	int pos;
    	// 让p指向第i-1个节点
    	while(p->next!=L && pos<i-1) //注意结束条件 
    	{
    		p=p->next;
    		pos++;
    	}
    	if(p->next==L && pos<i-1||pos>i-1)
    		return 0;
    	LNode *s=(LNode*)malloc(sizeof(LNode));
    	s->data=x;
    	s->next=p->next;
    	p->next=s;
    	return 1;
    }
    // 删除节点
    int del(LNode *L,int i,int x) //删除第i个节点 
    {
    	LNode *p;
    	int pos=0;
    	//让p指向第i-1个节点 
    	while(p->next!=L && pos<i-1)
    	{
    		p=p->next;
    		pos++;
    	}
    	if(p->next==L || pos>i-1)
    		return 0;
    	LNode *q=p->next;
    	p->next=q->next;
    	free(q);
    	return 1;
    }
    

    1.4 双向循环链表

    #include <iostream>
    using namespace std;
    //类型描述
    typedef struct DLNode
    {
    	int data;
    	struct DLNode *prior;
    	struct DLNode *next;
    }DLNode;
    // 初始化
    int init(DLNode *L)
    {
    	L=(DLNode*)malloc(sizeof(DLNode));
    	L->next=L->prior=L;
    }
    // 插入节点
    int insert(DLNode *L,int i,int x)
    {
    	DLNode *p=L,*s;
    	int j=0;
    	// 让p指向第i-1个结点
    	while(p->next!=L && j<i-1)
    	{
    		p=p->next;
    		j++;
    	}
    	if(p->next==L && j<i-1||j>i-1)
    		return 0;
    	DLNode *s=(DLNode*)malloc(sizeof(DLNode));
    	s->data=x;
    	s->prior=p;
    	s->next=p->next;
    	p->next->prior=s;
    	p->next=s;
    	return 1;
    }
    //删除结点
    inr del(DLNode *L,int i,int x)
    {
    	DLNode *p,*q;
    	// 让p指向第i-1个节点
    	p=L;
    	int j=0;
    	while(p->next!=L && j<i-1)
    	{
    		p=p->next;j++;
    	}
    	if(p->next==L||j>i-1)
    		return 0;
    	q=p->next;
    	p->next=q->next;
    	q->next->prior=p;
    	free(q);
    	return 1;
    }
    //遍历
    void disp(DLNode *L)
    {
    	// 后继遍历
    	DLNode *p=L->next;
    	while(p!=L) //结束条件 
    	{
    		p=p->next;
    	}
    	// 前驱遍历
    	p=L->prior;
    	while(p!=L)
    	{
    		p=p->next;
    	 } 
    }
    int main()
    {
    	return 0;
    }
    

    1.5 线性表的应用

    1.5.1 两个线性表的合并

    #include <iostream>
    using namespace std;
    typedef struct LNode
    {
    	int data;
    	struct LNode *next;
    }LNode;
    /*方法一假设合并的链表上的结点空间是原来的空间,其算法设计的主要思想是将
    其中一个链表上的结点逐个插人到另一个链表中。*/
    void merge1(LNode *La,LNode *Lb)//合并到La 
    {
    	LNode *pa,*pb,*qa,*qb;
    	q=La;pa=La->next;pb=qb=Lb->next;
    	while(pa&&pb)
    	{
    		if(pb->data<=pa->data)//插入到qa和pa之间 (qa始终是pa的前驱结点) 
    		{
    			qb=qb->next;//key
    			pb->next=pa;
    			qa->next=pb;
    			pa=qa->next;//key error 调整pa,让其前驱为qa 
    			pb=qb;//key
    		}
    		else
    		{
    			qa=pa;
    			pa=pa->next;
    		}
    	}
    	if(pb) qa->next=pb;//剩余结点 
    	free(Lb);
    }
    /*
    方法二假设合并的链表上的结点空间是重新申请的空间,其算法设计的主要思想是
    将原来的两个链表上的结点依次比较逐个插入到新链表中。 
    */
    void merge2(LNode *La,LNode *Lb,LNode *&Lc)
    {
    	LNode *pa,*pb,*pc,*s;
    	pa=La->next;
    	pb=Lb->next;
    	Lc=(LNode*)malloc(sizeof(LNode));
    	pc=Lc;
    	while(pa&&pb)
    	{
    		if(pb->data<=pa->data)
    		{
    			s=(LNode*)malloc(sizeof(LNode));
    			s->data=pb->data;
    			s->next=NULL;
    			pc->next=s;
    			pc=s;
    			pb=pb->next;//后移 
    		}
    		else
    		{
    			s=(LNode*)malloc(sizeof(LNode));
    			s->data=pa->data;
    			s->next=NULL;
    			pc->next=s;
    			pc=s;
    			pa=pa->next;//后移 
    		}
    	}
    	//收尾
    	while(pb)
    	{
    		s=(LNode*)malloc(sizeof(LNode));
    		s->data=pb->data;
    		s->next=NULL;
    		pc->next=s;
    		pc=s;
    		pb=pb->next;
    	}
    	while(pa)
    	{
    		s=(LNode*)malloc(sizeof(LNode));
    		s->data=pa->data;
    		s->next=NULL;
    		pc->next=s;
    		pc=s;
    		pa=pa->next;
    	}
    }
    int main()
    {
    	return 0;
    }
    

    1.5.2 一元函数的求和与求积

    #include <iostream>
    using namespace std;
    //类型描述
    typedef struct
    {
    	float coef;//存放系数
    	int exp;//存放指数 
    }Term;
    typedef struct Pnode
    {
    	Term data;
    	struct Pnode *next;
    }Pnode;
    //插入节点
    void insert(Pnode *L,Term x)
    {
    	Pnode *p=L,*q=L->next,*s;//p q 记住相邻的两个结点 
    	while(p)
    	{
    		if(q!=NULL && x.exp>p->data.exp && x.exp<q->data.exp) //插入到p、q之间 
    		{
    			s=(Pnode*)malloc(sizeof(Pnode));
    			s->data=x;
    			s->next=q;
    			p->next=s;
    			return;
    		}
    		else if(q!=NULL && x.exp==q.data.exp)
    		{
    			if(fabs(q.data.coef + x.coef) < 1.0E-6) //指数相等,系数符号相反,绝对值相等 
    			{
    				p->next=q->next; //删除q结点 
    				free(q);
    				return ;
    			}
    			else
    			{
    				q->data.coef = x.coef + q->data.coef; //指数相等,系数不同,合并 
    				return ;
    			}
    		}
    		else if(q==NULL && x.exp > p->data.exp) //插入到最后 
    		{
    			s=(Pnode*)malloc(sizeof(Pnode));
    			s->data=x;
    			s->next=NULL;
    			p->next=s;
    			return;
    		}
    		else  //后移,寻找插入位置 
    		{
    			p=q;
    			q=q->next;
    		}
    	}
    }
    //两个一元函数多项式的加法
    void add(Pnode *La,Pnode *Lb,Pnode *Lc)
    {
    	Pnode *s,*pa,*pb,*pc;
    	Lc=(Pnode*)malloc(sizeof(Pnode));
    	Lc->data.exp=-1;
    	Lc->next=NULL;
    	pa=La->next;
    	pb=Lb->next;
    	pc=Lc;
    	while(pa&&pb)
    	{
    		if(pa->data.exp < pb.data.exp)
    		{
    			s=(Pnode*)malloc(sizeof(Pnode));
    			s->data=pa->data;
    			s->next=NULL;
    			pc->next=s;
    			pc=s;
    			pa=pa->next;//后移 
    		}
    		else if(pa->data.exp == pb->data.exp)//合并同类项 
    		{
    			if(fabs(pa->data.coef + pb->data.coef) > 1.0E-6)//之后和不为零才会插入 
    			{
    				s=(Pnode*)malloc(sizeof(Pnode));
    				s->data.coef = pa->data.coef + pb->data.coef;
    				s->data.exp = pa->data.exp;
    				s->next = NULL;
    				pc->next=s;
    				pc=s;
    			}
    			pa=pa->next;
    			pb=pb->next;
    		}
    		else
    		{
    			s=(Pnode*)malloc(sizeof(Pnode));
    			s->data=pb->data;
    			s->next=NULL;
    			pc->next=s;
    			pc=s;
    			pb=pb->next;
    		}
    	}
    	while(pa)
    	{
    		s=(Pnode*)malloc(sizeof(Pnode));
    		s->data=pb->data;
    		s->next=NULL;
    		pc->next=s;
    		pc=s;
    		pa=pa->next;
    	}
    	while(pb)
    	{
    		s=(Pnode*)malloc(sizeof(Pnode));
    		s->data=pb->data;
    		s->next=NULL;
    		pc->next=s;
    		pc=s;
    		pb=pb->next;
    	}
    }
    //乘法
    /*
    将第1个一元多项式的每一项与第2个一元多项式的各项相乘,再插人到新的一元
    多项式中。 
    */ 
    void mul(Pnode *La,Pnode *Lb,Pnode *Lc)
    {
    	Pnode *pa,*pb;
    	Term x;
    	Lc=(Pnode*)malloc(sizeof(Pnode));
    	Lc->data.exp=-1;
    	Lc->next=NULL;
    	pa=La->next;
    	while(pa)
    	{
    		pb=Lb->next;
    		while(pb)
    		{
    			x.coef = pa->data.coef * pb->data.coef;//系数相乘 
    			x.exp = pa->data.exp + pb->data.exp;//指数相加 
    			insert(Lc,x);
    			pb=pb->next;
    		}
    		pa=pa->next;
    	}
    }
    int main()
    {
    	return 0;
    }
    

    二、栈和队列

    2.1 表达式求值的两种方法

    [分析]后缀表达式是一个字符串,为了方便处理,以’#‘结束。用一个栈(假定数据元素类型为整型)来存放操作数和中间的计算结果。对后缀表达式从左向右依次扫
    描,若是操作数,则将字符转换成整数进栈;若是运算符,则连续出栈两次,第一次出栈的元素是第二个操作数,第二次出栈的元素是第一个操作数,根据当前的运算符做相应的运算,并将计算结果进栈,直到遇到’#'为止。此时栈中只剩下一个元素,即最后的运算结果,出栈即可。

    #include <iostream>
    using namespace std;
    
    //后缀表达式求值(仅仅适用于个位数)
    void suffix_value(char a[])
    {
    	int i=0,x1,x2;
    	char s[maxSize];
    	int top=-1;
    	while(a[i]!='#')
    	{
    		switch(a[i])
    		{
    			case'+':x2=pop(s); x1=pop(s); push(s,x1+x2);break;
    			case'-':x2=pop(s); x1=pop(s); push(s,x1-x2);break;
    			case'*':x2=pop(s); x1=pop(s); push(s,x1*x2);break;
    			case'/':x2=pop(s); x1=pop(s);
    			if(x2!=0) push(s,x1/x2);
    			else
    			{
    				cout<<"分母为0"<<endl;
    				return ;
    			}
    			break;
    			default: push(s,a[i]-'0');//将字符转换为数字 
    		}
    		i++; //处理下一个a[i] 
    	}
    	cout<<"结果为"<<pop(s)<<endl;
    }
    //将中缀表达式转换为后缀表达式
    //判断字符优先级 
    int prior(char a)
    {
    	if(a=='*' || a=='/') return 4;
    	else if(a=='+' || a=='-') return 3;
    	else if(a== '(') return 2;
    	else if(a=='#') return 1;
    	else return 0;
    }
    //转换函数
    void transform(char a[],char suff[]) //a指向算术表达式,suff存储后缀表达式 
    {
    	int i=0,k=0,n;
    	char ch;
    	Stack s;
    	push(s,'#');
    	n=strlen(a);
    	a[n]='#';a[n+1]='\0';
    	while(a[i]!='\0')
    	{
    		if(a[i]>='0' && a[i]<='9')//操作数,直接存入后缀表达式 
    		suff[k++]=a[i];
    		else
    		switch(a[i])
    		{
    			case'(':push(s,a[i]);break;
    			case')':
    				ch=pop(s);
    				while(ch!='(')
    				{
    					suff[k++]=ch;
    					ch=pop(s);
    				}
    				break;
    			default:
    				ch=gettop(s);
    				while(prior(ch)>=prior(a[i]))
    				{
    					suff[k++]=ch;
    					ch=pop(s);
    					ch=gettop(s);
    				}
    				if(a[i]!='#') push(s,a[i]);
    		}
    		i++;
    	}
    	suff[k]='\0';
    }
    /*
    (代码层面)将计算后缀表达式的函数和将中缀表达式转换为后缀表达式的函数结合
    即可计算出中缀表达式的值 
    (手工求值层面)看参考书 
    */
    /*
    以上算法仅适用于操作数是个位数。如果对任意的实数都能计算,需要解决如下
    问题:
    (1)后缀表达式中的操作数与操作数之间用空格隔开;
    (2)操作数栈的元素类型为实数;
    (3)将一个数字串转换为一个实数的算法;
    (4)操作数为负数的情况。.
    例如,原表达式为: -3+(-15. 7+9) *4. 25+7/8.2
    (1)处理负数的情况
    原则:第1个字符为'-',前面加0;'('之后是'-',在'('之后加0。
    原表达式变为: 0-3+(0-15. 7+9) *4. 25+7/8.2
    (2)在操作数与操作数之间加空格
    后缀表达式为: 03- 0 15.7 -9 + 4.25 *+7 8.2/+
    请读者将上述的有关算法进行修改,使其可以计算任意实数的算术表达式。
    
    */
    int main()
    {
    	return 0;
    }
    

    三、树和二叉树

    3.1 二叉树的类型描述

    typedef struct BTNode
    {
    	char data;
    	struct BTNode *lchild;
    	struct BTNode *rchild;
    }BTNode;
    

    3.2 二叉树的创建

    #include <iostream>
    using namespace std;
    typedef struct BTNode
    {
    	char data;
    	struct BTNode *lchild;
    	struct BTNode *rchild;
    }BTNode;
    /*
    以“根 左子树 右子树”的字符串形式读人结点值
    的递归算法按先序遍历顺序(空结点以#表示)读人每个结点值建立二叉链表。
    */
    void  crt_tree(BTNode *T)//递归创建(先序遍历) 
    {
    	char c;
    	cin>>c;
    	if(ch=='#') T=NULL;
    	else
    	{
    		T=(BTNode*)malloc(sizeof(BTNode));
    		T->data=ch;
    		crt_tree(&T->lchild);
    		crt_tree(&T->rchild);
    	}
    }
    // 层次遍历可以实现非递归创建 详见p183 
    void Creat_BiTree(BTNode *T)
    {
    	Queue q;
    	T=NULL;
    	char fa,ch,lrflag;//fa为父亲节点 
    	cin>>fa>>ch>>lrflag;
    	while(ch!='#')
    	{
    		BTNode *p=(BTNode*)malloc(sizeof(BTNode));
    		p->data=ch;
    		p->lchild=p->rchild=NULL;
    		EnQueue(Q,p);
    		if(fa=='#') T=p; //根节点
    		else
    		{
    			BTNode *s=GetHead(Q);
    			while(s->data!=fa)//寻找当前节点的父亲节点(该过程中遇到的非父亲节点一定已经创建完成) 
    			{
    				DeQueue(Q,p);
    				s=GetHead(Q); 
    			}
    			if(lrflag==0) s->lchild=p;
    			else s->rchild=p;
    		}
    		cin>>fa>>ch>>lrflag;
    	}
    }
    

    3.3 二叉树的递归遍历(以先序遍历为例)

    void preorder(BTNode *p)
    {
    	if(p!=NULL)
    	{
    		cout<<p->data<<endl;
    		preorder(p->lchild);
    		preorder(p->rchild);	
    	}
    }
    

    3.4 二叉树的非递归遍历

    // 非递归先序遍历
    void preorderNO(BTNode *bt)
    {
    	if(bt!=NULL)
    	{
    		BTNode *stack[maxSize];
    		int top=-1;
    		// 根节点入栈 
    		top++;
    		stack[top] = bt;
    		//开始遍历
    		BTNode *p;
    		while(top!=-1)
    		{
    			p=stack[top--];
    			cout<<p->data<<endl; //先序遍历(先右孩子进栈,然后是左孩子) 
    			if(p->rchild != NULL)
    			{
    				stack[++top] = p->rchild; 
    			}
    			if(p->lchild != NULL)
    			{
    				stack[++top] = p->lchild;
    			 } 
    		} 
    	}
    }
    
    // 非递归中序遍历
    void inorderNo(BTNode *bt)
    {
    	if(bt!=NULL)
    	{
    		BTNode *stack[maxSize];
    		int top=-1;
    		BTNode *p;
    		p=bt;
    		while(top!=-1 || p!=NULL)
    		{
    			while(p!=NULL) //左孩子不断入栈 ,直到最左边的结点 
    			{
    				stack[++top] = p;
    				p= p->lchild;
    			}
    			if(top!=-1)
    			{
    				p=stack[top--];
    				cout<<p->data<<endl;
    				p=p->rchild; //后访问右孩子(最左边结点是没有右孩子的,这一步会赋值为NULL,然后退回到最近的根节点进行访问,然后再对其右子树进行同样的操作) 
    			}
    		}
    	}
    } 
    
    // 非递归后序遍历
    void postorder(BTNode *bt)
    {
    	if(bt!=NULL)
    	{
    		BTNode *stack1[maxSzie]; int top1=-1;
    		BTNode *stack2[maxSize]; int top2=-1;
    		BTNode *p;
    		stack1[++top1]=bt;
    		while(top1!=-1)
    		{
    			p = stack1[top1--];
    			stack2[++top2] = p; // 出一个进一个,实现逆序
    			if(p->lchild!=NULL)
    			{
    				stack1[++top1] = p->lchild;
    			}
    			if(p->rchild!=NULL)
    			{
    				stack1[++top] = p->rchild;
    			}
    		}
    		while(top2!=-1)
    		{
    			p = stack2[top2--];
    			cout<<p->data<<endl;
    		}
    	}
    }
    

    3.5 二叉树的层次遍历

    // 层次遍历 
    void level(BTNode *p)
    {
    	int front,rear;
    	BTNode *que[15];
    	front=rear=0;
    	BTNode *q;
    	if(p!=NULL)
    	{
    		rear = (rear+1) % maxSize;
    		que[rear] = p;
    		while(front!=rear)
    		{
    			//出队
    			front = (front+1)%maxSize;
    			q = que[front];
    			cout<<q->data<<endl;
    			if(q->lchild != NULL)
    			{
    				rear = (rear+1) % maxSize;
    				que[rear] = q->lchild;	
    			}
    			if(q->rchild != NULL)
    			{
    				rear = (rear+1) % maxSize;
    				que[rear] = q->rchild;
    			}
    		}
    	}
    }
    

    3.6 树的创建

    • 孩子链表表示法(邻接表)
    /*--------孩子链表表示法(邻接表)---------*/
    typedef struct CTNode //表节点 
    {
    	int child;
    	struct CTNode *next;
    }CTNode;
    typedef struct CTbox //表头节点 
    {
    	char data;
    	CTNode *first;
    }CTbox;
    typedef struct
    {
    	CTbox nodes[maxSize];
    	int n,r;//节点数目和根节点的位置 
    }ChildList;
    void createPtree(ChildList *T)
    {
    	int i,j,k;
    	CTNode *p,*s;
    	char father,child;
    	cout<<"请输入结点数"<<endl;
    	cin>>T->n;
    	getchar();
    	cout<<"请按照层次依次输入"<<T->n<<"个结点的值"<<endl;
    	for(i=0;i<T->n;i++)
    	{
    		cin>>T->nodes[i].data;
    		T->nodes[i].first=NULL; 
    	}
    	getchar();
    	cout<<"请按照格式(双亲,孩子)输入"<<T->n-1<<"分支(按照层次)"<<endl;
    	for(i=1;i<=T->n-1;i++)
    	{
    		cin>>father>>child;
    		getchar();
    		for(j=0;j<T->n;j++) //找到父节点的值 
    		{
    			if(father==T->nodes[j].data);
    			break;
    		}
    		if(j>=T->n)
    		{
    			cout<<"error"<<endl;
    			return ;
    		}
    		for(k=0;k<T->n-1;k++)//找孩子节点的值 
    		{
    			if(child==T->nodes[j].data)
    			break;
    		}
    		if(k>=T->n)
    		{
    			cout<<"error"<<endl;
    			return ;
    		}
    		p=T->nodes[j].first;
    		if(p==NULL)//第一个孩子结点 
    		{
    			s=(CTNode*)malloc(sizeof(CTNode));
    			s->child=k;
    			s->next=NULL;
    			T->nodes[j].first=s;
    		}
    		else //不是第一个孩子 
    		{
    			while(p->next) p=p->next;
    			s=(CTNode*)malloc(sizeof(CTNode));
    			s->child=k;
    			s->next=NULL;
    			p->next=s; 
    		}
    	}
    }
    
    • 孩子兄弟链表表示法
    /*--------孩子兄弟链表表示法---------*/
    typedef struct CSNode
    {
    	char data;
    	struct CSNode *fch,*nsib;//第一个孩子和下一个兄弟 
    }CSNode;
    void createCSTree(CSNode *T)
    {
    	Queue q;//队列(伪代码形式)
    	CSNode *p,*s,*r; 
    	T=NULL;
    	char fa,ch;
    	cin>>fa>>ch;
    	while(ch!='#')
    	{
    		p=(CSNode*)malloc(sizeof(CSNode));
    		p->data=ch;
    		p->fch=p->nsib=NULL;
    		EnQueue(q,p);	//指针入队列
    		if(fa=='#')
    			T=p;	//建立根节点
    		else
    		{
    			s=getHead(Q);
    			while(s->data!=fa) //在队列中找到双亲节点 
    			{
    				DeQueue(Q);
    				s=getHead(Q);
    			}
    			if(s->fch==NULL)//第一个孩子节点 
    			{
    				s->fch=p;
    				r=p;
    			}
    			else	//不是第一个孩子 
    			{
    				r->nsib=p;
    				r=p;
    			}
    		}
    		cin>>fa>>ch;
    	}
    }
    

    3.7 树的查找算法

    /*--------树的查找算法---------*/
    void preSearch(CSNode *T,char val[],CSNode *p)
    {
    	if(T)
    	{
    		if(strcmp(val,T->data)==0)//查找成功 
    		{
    			p=T;
    			return ;
    		}
    		preSearch(T->fch,val,p);
    		preSearch(T->nsib,val,p);
    	}
    }
    

    3.8 树的插入算法

    /*--------树的结点插入---------*/
    int insert(CSNode *T,char fa[],char ch[])
    {
    	CSNode *s,*p=NULL,*q;
    	//fa是双亲,ch是孩子
    	preSearch(T,fa,&p);	//查找双亲节点
    	if(p)
    	{
    		s=(CSNode*)malloc(sizeof(CSNode));
    		strcpy(s->data,ch);
    		s->fch=s->nsib=NULL;
    		if(p->fch==NULL)
    			p->fch=s;//第一个孩子结点
    		else
    		{
    			q=p->fch;
    			while(q->nsib) q=q->nsib;
    			q->nsib=s;
    		}
    		return 1;
    	}
    	return 0;
    }
    

    3.9 树的删除算法

    删除树中的一个结点,约定删除以该结点为根的子树。首先根据双亲和孩子的值在孩子,兄弟链表中分别进行查找,如果有一个不存在,不能进行删除操作;否则得到双亲结点和孩子结点的地址。如果删除的结点是双亲结点的第一个孩子,重新链接其他的孩子结点,再删除第一个孩子子树;如果删除的结点不是第一个孩子,继续寻找该结点的前一个兄弟,将该结点的其他兄弟与前一个兄弟链接,再刪除以该结点为根的子树。

    /*
    其中函数deleteRoot()是完成子树的删除,并重接其他子树;函数postDelTree()是按照
    后序遍历的顺序释放每一个结点的空间。
    
    */
    void deleteRoot(CSNode *p,CSNode *f) //从树中删除一结点p为根的子树 ,f是p在存储结构上的双亲节点 
    {
    	if(f->fch==p)	//p是f的第一个孩子,是双亲关系 
    	{
    		f->fch=p->nsib;
    		p->nsib=NULL;
    		postDelTree(p);
    	}
    	if(f->nsib==p)	//p与f是兄弟关系 
    	{
    		f->nsib=p->nsib;
    		p->nsib=NULL;
    		postDelTree(p);
    	}
    }
    void postDelTree(CSNode *T)
    {
    	if(T)
    	{
    		postDelTree(T->fch);
    		postDelTree(T->nsib);
    		free(T);
    	}
    }
    void deleteTree(CSNode *T,char fa[],char ch[])
    {
    	CSNode *pfa=NULL,*pch=NULL;
    	if(strcmP(fa,"#")==0)	//删除的是整棵树 
    	{
    		postDelTree(T);
    		T=NULL;
    		return;
    	}
    	else
    	{
    		preSearch(T,fa,&pfa);	//查找双亲 
    		preSearch(T,ch,&pch);	//查找孩子
    		if(pfa==NULL || pch=NULL)
    		{
    			cout<<"error"<<endl;
    			return;
    		}
    		else
    		{
    			if(pfa->fch != pch)
    			{
    				pfa=pfa->fch;
    				while(pfa)
    				{
    					if(pfa->nsib == pch) break;
    					pfa=pfa->nsib;
    				}
    			}
    			deleteRoot(pch,pfa);
    		}
    	}
    }
    

    3.10 树的深度

    在树的孩子兄弟链表中,每棵子树根与它的左子树根是双亲与孩子的关系,每棵子树根与它的右子树根是兄弟关系,所以每棵子树的高度是(左子树高度+1)和右子树高度的最大值。

    int depth(CSNode *T)
    {
    	int d1,d2;
    	if(T==NULL) return 0;
    	d1=depth(T->fch);
    	d2=depth(T->nsib);
    	return d1+1>d2 ? d1+2:d2;
    }
    

    3.11 输出树中的所有叶子节点路径

    输出树中所有从根到叶子的路径的主要步骤:
    (1)树不空,将根结点进栈。
    (2)如果栈顶元素的第一棵孩子树为空,路径找到,输出栈内的所有结点,转向(3);
    否则继续寻找第一棵子树上的叶子路径。
    (3)栈顶元素出栈。如果栈顶元素有其余的兄弟子树,回到(1)继续寻找其余的兄弟
    子树上的叶子路径。

    void AllTreePath(CSNode *T,Stack *s)
    {
    	//非递归形式(可以更改为递归形式,可参考二叉树的叶子节点求法) 
    	while(T)
    	{
    		Push(S,T->data);
    		if(T->fch==NULL) PrintStack(S);//只把数据打印一遍,不出栈
    		else
    		AllTreePath(T->fch,S);
    		Pop(s);//出栈
    		T=T->nsib;
    	}
    }
    

    3.12 二叉树的应用

    3.12.1 输出二叉树的叶子节点路径

    #include <iostream>
    using namespace std;
    #define maxSize 1500
    typedef struct BTNode
    {
    	char data;
    	struct BTNode *lchild;
    	struct BTNode *rchild;
    }BTNode;
    /*--------输出二叉树中所有叶子节点的路径---------*/
    void AllTreePath(BTNode *T,Stack *s)
    {
    	if(T)
    	{
    		Push(S,T->data);
    		if(T->lchild==NULL && T->rchild==NULL)
    			PrintStack(S);//只打印数据,不出栈
    		else
    		{
    			AllTreePath(T->lchild,S);
    			AllTreePath(T->rchild,S);
    		}
    		Pop(s);//出栈 
    	}
    }
    

    3.12.2 表达式二叉树

    #include <iostream>
    using namespace std;
    //类型描述
    typedef struct BTNode
    {
    	char data;
    	struct BTNode *lchild;
    	struct BTNode *rchild;
    }BTNode; //二叉树节点
    int isOperator(char ch){}//判断是否为运算符(暂时未写) 
    //判断字符优先级 
    int prior(char a)
    {
    	if(a=='*' || a=='/') return 4;
    	else if(a=='+' || a=='-') return 3;
    	else if(a== '(') return 2;
    	else if(a=='#') return 1;
    	else return 0;
    }
    //创建子节点并入子树栈 
    void CrtNode(BTNode subTreeStack[],int &top,char ch)//subTreeStack是存储子树的栈 
    {
    	BTNode *T;
    	T=(BTNode*)malloc(sizeof(BTNode));
    	T->data=ch;
    	T->lchild=T->rchild=NULL;
    	subTreeStack[++top]=T;
    }
    //创建子树并入子树栈
    void CrtSubTree(BTNode subTreeStack[],int &top,char c)
    {
    	BTNode *T;
    	BTNode lc,rc;//一次性出栈两个元素,一个左孩子,一个右孩子
    	T=(BTNode*)malloc(sizeof(BTNode));
    	T->data=c;
    	lc=subTreeStack[top--];
    	rc=subTreeStack[top--];
    	T->lchild=lc;
    	T->rchild=rc;
    	subTreeStack[++top]=T;//新生成的子树的根节点入栈 
    }
    //核心函数,创建表达式二叉树
    void CrtExptree(BTNode *T,char exp[])
    {
    	BTNode subTreeStack[maxSize];int subTreeTop=-1;//子树栈
    	BTNode charStack[maxSize];int charStackTop=-1;//运算符栈
    	charStack[++top]='#';//结束符入栈
    	char ch,c;
    	int i=0;
    	while( (c=charStack[top])!='#' || exp[i]!='#' )
    	{
    		if(!isOperator(exp[i]))
    		CrtNode(subTreeStack,subTreeTop,exp[i]);//非运算符,直接建立叶节点并入子树栈中 
    		else
    		{
    			switch(exp[i])
    			{
    				case'(':charStack[++charStackTop]=exp[i];break;//左括号 
    				case')':c=charStack[charStackTop--];//右括号 
    						while(c!='(')
    						{
    							CrtSubTree(subTreeStack,c);
    							c=charStack[charStackTop--];
    						}
    				default:
    					while( (c=charStack[charStackTop])!='#' && prior(c)>prior(exp[i]))
    					{
    						/*
    						当栈顶运算符不是#号且优先级高于表达式中的当
    						前运算符,则取栈顶的运算符建子树,再出栈
    						*/
    						CrtSubTree(subTreeStack,subTreeTop,c);
    						charStackTop--;//出栈
    					}
    					if(exp[i]!='#')
    					charStack[++charStackTop]=exp[i];
    			}
    		}
    		if(exp[i]!='#') i++;
    	}
    	T=subTreeStack[top--];//二叉树根节点出栈 
    }
    /*
    表达式二叉树的计算(使用后序遍历) 
    */
    double culExp(BTNode *T)
    {
    	double result,a,b;
    	if(T)
    	{
    		if(!isOperator(T->data))//如果不是运算符,说明是字母变量,需要输入具体值,同时也是叶子节点 
    		{
    			cout<<"请输入变量"<<T->data<<"的值"<<endl;
    			cin>>result;
    			return result; 
    		}
    		a=culExp(T->lchild);
    		b=culExp(T->rchild);
    		//后序遍历进行计算
    		switch(T->data)
    		{
    			case'+':return a+b;
    			case'-':return a-b;
    			case'*':return a*b;
    			case'/':
    					if(b!=0)
    						return a/b;
    					else
    					{
    						cout<<"分母为0";
    						exit(0);
    					}
    		}
    	}
    }
    int main()
    {
    	return 0;
    }
    

    四、图

    4.1 图的创建

    4.1.1 邻接矩阵创建

    /***********邻接矩阵***********/ 
    typedef struct
    {
    	int edges[maxSize][maxSize];
    	int n,e;
    }MGraph;
    /*邻接矩阵创建(以无向图为例)*/
    void crt_graph(MGraph *G)
    {
    	cin>>G->n>>G->e;//输入顶点数和边数
    	/*初始化*/
    	for(int i=0;i<G->n;i++)
    		for(int j=0;j<G->n;j++)
    		G->edges[i][j]=0;
    	for(int k=0;k<G->e;k++)
    	{
    		int i,j;
    		cin>>i>>j;
    		G->edges[i][j]=G->edges[j][i]=1;
    	}
    }
    

    4.1.2 邻接表创建

    /***********邻接表存储法***********/ 
    // 被指向的点 
    typedef struct ARCNode
    {
    	int vex;
    	struct ARCNode *next;
    	char info;
    }ARCNode;
    // 顶点
    typedef struct VNode
    {
    	int data;
    	ARCNode *first;
    }VNode;
    //邻接表
    typedef struct
    {
    	VNode list[maxSize];
    	int n,e; 
    }AGraph;
    //邻接表创建(以有向图为例) 
    void build_list(AGraph *G)
    {
    	cin>>G->n>>G->e;//顶点数和边数
    	for(int i=0;i<G->n;i++)
    	{
    		// 创建表节点(以编号形式输入)
    		cin>>G->list[i].data;
    		G->list[i].first=NULL;
    	}
    	for(int k=0;k<G->e;k++)//创建边 
    	{
    		int i,j;
    		cin>>i>>j;
    		ARCNode *p=(ARCNode*)malloc(sizeof(ARCNode));
    		p->vex=j;//假设编号和下标一致
    		//头插法插入 
    		p->next=G->list[i].first;
    		G->list[i].first=p;
    	}
    }
    

    4.2 图的遍历

    #include <iostream>
    #include<malloc.h>
    using namespace std;
    #define maxSize 150
    int visit[maxSize];
    /***********邻接表存储法***********/ 
    // 被指向的点 
    typedef struct ARCNode
    {
    	int vex;
    	struct ARCNode *next;
    	char info;
    }ARCNode;
    // 顶点
    typedef struct VNode
    {
    	char data;
    	ARCNode *first;
    }VNode;
    //邻接表
    typedef struct
    {
    	VNode list[maxSize];
    	int n,e; 
    }AGraph;
    //------- 深度优先遍历----------//
    void DFS(AGraph *G,int v)
    {
    	ARCNode *p;
    	visit[v]=1;
    	cout<<G->list[v].data<<" ";
    	p=G->list[v].first;
    	while(p!=NULL)
    	{
    		if(visit[p->vex]==0)
    		DFS(G,p->vex);
    		p=p->next;
    	}
    }
    /*广度优先遍历*/
    void BFS(AGraph *G,int v)
    {
    	ARCNode *p;
    	int que[maxSize];int front=0,rear=0;
    	int j;
    	cout<<G->list[v].data<<endl;
    	visit[v]=1;
    	rear=(rear+1)%maxSize;
    	que[rear]=1;
    	while(front!=rear)
    	{
    		front=(front+1)%maxSize;
    		int j = que[front];
    		p=G->list[j].first;
    		while(p!=NULL)
    		{
    			if(visit[p->vex]==0)
    			{
    				cout<<G->list[p->vex].data<<endl; //先访问,后入队 
    				visit[p->vex]=1;
    				rear=(rear+1)%maxSize;
    				que[rear]=p->vex;
    			}
    			p=p->next
    		}
    	}
    }
    int main()
    {
    	return 0;
    }
    

    4.3 最小生成树

    4.3.1 Prim算法

    //邻接矩阵
    typedef struct
    {
    	int edges[maxSize][maxSize];
    	int n,e;
    }MGraph;
    void Prim(MGraph g,int v0,int &sum)
    {
    	int lowcost[maxSize],vset[maxSize],v;
    	int i,j,k,min;
    	v=v0;
    	//初始化
    	for(i=0;i<g.n;i++)
    	{
    		lowcost[i]=g.edges[v0][i];
    		vset[i]=0;
    	}
    	vset[v0]=1;
    	sum=0;
    	for(i=0;i<g.n-1;i++)
    	{
    		min=INF;
    		//选择距离最小者(在lowcost数组中选取)
    		for(j=0;j<g.n;j++)
    		{
    			if(vset[j]==0 && lowcost[j]<min)
    			{
    				min=lowcost[j];
    				k=j;
    			} 
    		}
    		// 并入
    		vset[k]=1;  
    		v=k;//准备更新信息,k为这次的跳板 
    		sum+=min; //error 出错点 
    		for(j=0;j<g.n;j++)
    		{
    			if(vset[j]==0 && g.edges[v][j]<lowcost[j])
    			{
    				lowcost[j]=g.edges[v][j];
    			} 
    		} 
    	} 
    }
    

    4.3.2 Kruskal算法

    /*-------克鲁斯卡尔-------*/
    typedef struct
    {
    	int a,b;
    	int w;
    }Road;
    Road road[maxSize]; // 路径信息
    int v[maxSize]; //并查集使用 
    //获取根节点
    int getRoot(int a)
    {
    	while(a!=v[a]) a=v[a];
    	return a;
    }
    void Kruskal(MGraph g,int &sum,Road road[])
    {
    	//初始化 
    	int i;
    	int N,E,a,b;
    	N=g.n; 
    	E=g.e;
    	sum=0;
    	for(i=0;i<N;i++)
    	{
    		v[i]=i;
    	}
    	sort(road,E);//按照边的长度进行排序
    	for(i=0;i<E;i++)
    	{
    		a=getRoot(road[i].a);
    		b=getRoot(road[i].b);
    		if(a!=b)
    		{
    			v[a]=b;
    			sun+=road[i].w; //error出错点 
    		}
    	} 
    }
    

    4.4 最短路算法

    #include <iostream>
    using namespace std;
    #define INF 99999999
    typedef struct
    {
    	int edges[maxSize][maxSize];
    	int n,e;
    }MGraph;
    /**************Dijkstra算法********************/
    void Dijkstra(MGraph g,int v,int dist[],int path[])
    {
    	int set[maxSize];
    	int min,i,j,u;
    	for(i=0;i<g.n;++i)
    	{
    		dist[i]=g.edges[v][i];
    		set[i]=0;
    		if(g.edges[v][i]<INF)
    		{
    			path[i]=v;
    		}
    		else
    		path[i]=-1;
    	}
    	set[v]=1;path[v]=-1;
    	/*关键操作*/
    	for(i=0;i<g.n-1;i++)
    	{
    		min=INF;
    		//选取最小的点 
    		for(j=0;j<g.n;++j)
    		{
    			u=j;
    			min=dist[j];
    		}
    		set[u]=1;
    		//更新路径 
    		for(j=0;j<g.n;++j)
    		{
    			if(set[j]==0 && dist[j]>dist[u]+g.edges[u][j]) //忘记set为0 
    			{
    				dist[j]=dist[u]+g.edges[u][j];
    				path[j]=u; //更新前驱 
    			}
    			
    		}
    	}
    }
    // 打印路径
    void printPath(int path[],int a)
    {
    	int stack[maxSize];int top=-1;
    	while(path[a]!=-1)
    	{
    		stack[++top]=a;
    		a=path[a];
    	}
    	stack[++top]=a;
    	while(top!=-1)
    	cout<<stack[top--]<<" ";
    	cout<<endl;
    }
    /**************Flyod算法**********/
    void printpath(int u,int v,int path[][max])
    {
    	if(A[u][v]==INF) 
    	else
    	{
    		if(path[u][v]==-1)
    		cout<<u<<"--->"<<v;
    		else
    		{
    			int mid=path[u][v];
    			printpath(u,mid,path);
    			printpath(mid,v,path);
    		}
    	}
    }
    void Flyod(MGraph *g,int path[][maxSize],int A[][maxSize])
    {
    	int i,j,k;
    	for(i=0;i<g->n;i++)
    	for(j=0;j<g->n;j++)
    	{
    		A[i][j]=g->edges[i][j];
    		path[i][j]=-1;
    	}
    	for(k=0;k<g->n;++k)
    		for(i=0;i<g->n;i++)
    			for(j=0;j<g->n;j++)
    			{
    				if(A[i][j]>A[i][k]+A[k][j])
    				{
    					A[i][j]=A[i][k]+A[k][j];
    					path[i][j]=k;
    				}
    			}
    }
    int main()
    {
    	return 0;
    }
    

    五、查找

    4.1 顺序查找(带哨岗)

    #include <iostream>
    using namespace std;
    int SeqSearch(int A,int k,int len)
    {
    	A[0]=k;//存放岗哨
    	for(int i=len;A[i]!=k;i--);
    	return i;//如i为0,说明查找失败 
    }
    int main()
    {
    	return 0;
    }
    

    4.2 折半查找

    #include <iostream>
    using namespace std;
    int Bsearch(int R[],int low,int high,int k)
    {
    	int mid;
    	while(low<=high)
    	{
    		mid=(low+high)/2;
    		if(R[mid]==k)
    		return mid;
    		else if(R[mid]>k)
    		high=mid-1;
    		else
    		low=mid+1;
    	}
    	return -1; //查找失败则返回-1 
    }
    int main()
    {
    	int R[150];
    	int n;
    	cin>>n;
    	for(int i=0;i<n;i++)
    	cin>>R[i];
    	int flag = Bsearch(R,0,n-1,5);
    	cout<<R[flag]<<endl;
    	return 0;
    } 
    

    4.3 二叉排序树

    #include <iostream>
    using namespace std;
    typedef struct BTNode
    {
    	int key;
    	struct BTNode *lchild;
    	struct BTNode *rchild;
    }BTNode;
    /**
    * 查找关键字 
    */
    BTNode* BSTSearch(BTNode *bt,int key)
    {
    	if(bt==NULL)
    	return NULL;
    	else
    	{
    		if(bt->key==key)
    			return bt;
    		else if(key<bt->key)
    			return BSTSearch(bt->lchild,key); //小于根节点,到左子树查找
    		else
    			return BSTSearch(bt->rchild,key); //查找右子树 
    	}
    }
    /**
    * 插入关键字 
    **/
    BTNode *(BTNode *&bt,int key)
    {
    	if(bt==NULL)
    	{
    		bt=(BTNode*)malloc(sizeof(BTNode));
    		bt->lchild=bt->rchild=NULL;
    		bt->key=key;
    		return 1;
    	}
    	else
    	{
    		if(bt->key==key)
    			return 0;
    		else if(key<bt->key)
    			return BSTInsert(bt->lchild,key);
    		else
    			return BSTInsert(bt->rchild,key);
    	}
    }
    /**
    * 构造二叉排序树 
    **/
    void CreatBST(BTNode *&bt,int key[],int n)
    {
    	int i;
    	bt=NULL;
    	for(i=0;i<n;i++)
    		BSTInsert(bt,key[i]);
    }
    int main()
    {
    	return 0;
    }
    

    六、排序

    6.1 直接插入排序

    #include <iostream>
    using namespace std;
    void InsertSort(int R[],int n)
    {
    	int i,j;
    	int temp;
    	for(i=1;i<n;i++) //i从1开始 
    	{
    		temp=R[i];
    		j=i-1; //key
    		while(j>=0 && temp<R[j])
    		{
    			R[j+1]=R[j]; //向后移动 
    			--j;
    		}
    		R[j+1]=temp;
    	}
    }
    int main()
    {
    	int R[15];
    	int n;
    	cin>>n;
    	for(int i=0;i<n;i++)
    	{
    		cin>>R[i];
    	}
    	InsertSort(R,n);
    	for(int i=0;i<n;i++)
    	{
    		cout<<R[i]<<" ";
    	}
    	return 0;
    }
    

    6.2 折半插入排序

    #include <iostream>
    using namespace std;
    void BinsertSort(int A[],int len)
    {
    	int i,j,m,low,high;
    	for(i=2;i<=len;i++)
    	{
    		A[0]=A[i];//A[i]暂时存入A[0]中 
    		low=1;high=i-1;
    		while(low<=high)
    		{
    			m=(low+high)/2;
    			if(A[0]>R[m])
    				high=m-1;
    			else
    				low=m+1;
    		}
    		for(j=i-1;j>=high+1;--j)
    			A[j+1]=A[j];//元素后移
    		R[high+1]=R[0];//插入 
    	}
    }
     
    

    6.3 冒泡排序

    #include <iostream>
    using namespace std;
    void BubbleSort(int R[],int n)
    {
    	int i,j,flag;
    	int temp;
    	for(i=n-1;i>=1;i--)
    	{
    		flag=0;
    		for(j=1;j<=i;j++)
    		{
    			if(R[j-1]>R[j])
    			{
    				temp=R[j];
    				R[j]=R[j-1];
    				R[j-1]=temp;
    				flag=1;
    			}
    		}
    		if(flag==0)
    		return;
    	}
    }
    int main()
    {
    	int R[15];
    	int n;
    	cin>>n;
    	for(int i=0;i<n;i++)
    	{
    		cin>>R[i];
    	}
    	BubbleSort(R,n);
    	for(int i=0;i<n;i++)
    	cout<<R[i]<<" ";
    	return 0;
    }
    

    6.4 快速排序

    #include <iostream>
    #include<stdlib.h>
    using namespace std;
    int sum;
    void QuickSort(int R[],int low,int high)
    {
    	sum++;
    	int temp;
    	int i=low,j=high;
    	if(low<high)
    	{
    		
    		temp=R[low]; //选出中间点
    		while(i<j)
    		{
    			while(j>i && R[j]>=temp) j--; //先从右往左 
    			if(i<j)
    			{
    				R[i]=R[j];
    				++i; //key 
    			}
    			
    			//从左往右扫描
    			while(i<j && R[i]<=temp) i++;
    			if(i<j)
    			{
    				R[j]=R[i];
    				j--; //key 
    			}
    			R[i]=temp;
    			QuickSort(R,low,i-1);
    			QuickSort(R,i+1,high);
    		}
    	}
    }
    

    6.5 二路归并排序

    #include <iostream>
    using namespace std;
    #define max 100
    void merge(int A[], int L1, int R1, int L2, int R2)
    {
         int i=L1,j=L2;
         int temp[max], index=0;
         while(i<=R1 && j<=R2)
    	 {
            if(A[i] <= A[j])
    		{
                temp[index++] = A[i++];
            }
    		else
    		{
                temp[index++] = A[j++];
            }
        }
        while(i <= R1) temp[index++] = A[i++];
        while(j <= R2) temp[index++] = A[j++];
        //将temp的值一一赋给A[L1~R2]
        for(int i=0; i<index; i++)
    	{
            A[L1+i] = temp[i];
        }
    }
    void mergeSort(int A[],int low,int high)
    {
    	if(low<high)
    	{
    		int mid=(low+high)/2;
    		mergeSort(A,low,mid); //归并前半段 
    		mergeSort(A,mid+1,high); //归并后半段 
    		merge(A,low,mid,mid+1,high); //将low->mid和mid+1->high两个有序序列合并成一个有序序列 
    	}
    }
    int main()
    {
    	int R[max];
    	for(int i=0;i<6;i++)
    	cin>>R[i];
    	mergeSort(R,0,5);
    	for(int i=0;i<6;i++)
    	cout<<R[i]<<" ";
    	return 0;
    } 
    
    展开全文
  • 删除线性链表中数据域为 item 的所有结点3. 逆转线性链表4. 复制线性链表(递归)5. 将两个按值有序排列的非空线性链表合并为一个按值有序的线性链表二、树1. 二叉树的先序遍历(非递归算法)2. 二叉树的中序遍历...
  • 计算机考研数据结构代码题总结 链表 题目1 在带头节点的单链表L中,删除所有值为X的结点,并释放其空间,假设值为X的节点不唯一,试编写算法实现。 .算法思路 1、图解 . 2、图解含义描述 实现带头节点的单链表的...
  • 数据结构习题集leetcode21PAT 6-1 单链表逆转 (20 分)leetcode 141. 环形链表PAT 6-2 顺序表操作集 (20 分) leetcode21 /* Created by salmon on 2021-9-14 21:27. */ /** * Definition for singly-linked list....
  • 【灰灰考研】算法必背100题.pdf
  • 编程实现一组数据集合的全排列 排序 实现归并排序、快速排序、插入排序、冒泡排序、选择排序 编程实现O(n)时间复杂度内找到一组数据的第K大元素 二分查找 实现一个有序数组的二分查找算法 实现模糊二分查找算法...
  • 计算机考研数据结构真题
  • 数据结构简答题汇总

    万次阅读 多人点赞 2020-05-12 23:56:08
    面对即将要参加的考研复试,数据结构是必考科目,希望以下能派上用场 1.算法的时间复杂度: 答:在程序中反复执行的语句的执行次数被称为语句的频度,时间复杂度就是所有语句频度之和的数量级,而所有语句的频度之和...
  • 数据结构 第一章:数据结构的基本概念 定义 在任何问题中,数据元素都不是孤立存在的,而是在它们之间存在着某种关系,这种数据元素相互之间的关系称为结构(Structure)。数据结构是相互之间存在一种或多种特定...
  • 2022王道考研有关数据结构笔记

    多人点赞 2021-09-02 23:01:47
    第二章 线性表 2.1 线性表的定义和基本操作 要点: 线性表的基本操作——创销、增删、改查 传入参数时,何时要用引用 &... //用静态的“数组”存放数据元素 ElemType:int int Length; //顺序表的
  • 考研数据结构100天 Day1:在带头结点的单链表L中,删除所有值为X的节点,并释放其空间,假设值为的X节点不唯一,试编写算法以实现上述操作 void Del-X(LinkList &L,int x){ LNode *p=L->next; LNode *pre=L...
  • 本文的思维导图根据王道的数据结构书本整理而来并标记出重点内容,包括了知识点和部分课后习题 思维导图源文件已经发布在我的资源当中,有需要的可以去 我的主页 了解更多学科的精品思维导图整理 本文可以转载,但...
  • 写在前面:本文写于吴签时期,在家备考时刷完数据结构王道书之后想着把书中重点梳理汇总一下。本文内容包括但不局限于王道数据结构每章的知识点及其课后习题所涵盖的知识点。本人曾在大三期间打过一些程序设计类比赛...
  • 考研408复习笔记(五)—— 数据结构(五)前篇跳转三、栈和队列3.1 栈()stack3.2 顺序栈 本文中使用图片,来对微信公众号【研者荣耀】中相关课程的学习 若发布的内容有什么错误,欢迎留言探讨。 前篇跳转 考研408...
  • 严蔚敏所著的《数据结构》(C语言版,清华大学出版社)是我国高校采用较多的计算机专业优秀教材,也被众多高校指定为计算机专业考研参考书目。作为该教材的辅导书,本书具有以下几个方面的特点:1.整理名校笔记,浓缩...
  • 一、数据结构基本概念 1、数据:数据是信息的载体。客观事物的一种表现形式。万事万物都能用数据表示出来。 2、数据元素:数据元素是数据的基本单位,一个数据元素有若干个数据项组成 3、数据项:构成数据元素的不可...
  • 考研数据结构笔记(1) 时间复杂度和空间复杂度开篇语总述时间复杂度:空间复杂度另外一点参考书籍 开篇语 本人大三考研狗一枚,最近要提前准备下数据结构复习,所以写一系列关于复习数据结构知识的博文,以总结和...
  • 一个勤勤恳恳23级408考研党。今天非常开心的运行天勤的顺序表算法操作集,特此整理在这个博文里面。博文涉及天勤书籍上的一些基本操作,主要有线性表定义、查找元素、删除元素、遍历元素、初始化元素。特别精彩!
  • 课程全程讲师手敲代码,一步步代你走进数据结构与算法。 本课程涉及的数据结构与算法有,栈,队列,单向链表,双向循环链表,树,二叉树,搜索二叉树,平衡搜索二叉树,冒泡,选择,直插,希尔,,归并等,课程还...
  • 数据结构实践课程-表

    2020-08-15 16:30:16
    数据结构是非常重要,无论是考研还是大厂面试,数据结构都是必考内容。我也是从学生时代过的,非常清楚部分同学遇到的问题。有少数同学学数据结构就是拿个书看,偶尔画个图。坦率地讲,这种方法就不对。数据结构的...
  • 考研408 完整知识点篇2.0版

    千次阅读 多人点赞 2020-12-28 16:20:21
    数据结构 时间复杂度 线性表: 具有随机存储特性,查找时间复杂度为O(1) 单链表-尾插法⭐️ 栈及其应用 根据限定条件判断合法性;最小容量;表达式求值*;中缀表达式转化为后缀表达式过程* 应用:数制转换、括号匹配...
  • ​在考研计算机专业课C语言或者C语言和数据结构结合的考试中,文件一般是不作为考试的重点的,有些学校一般考一道文件选择题或者文件填空题,对于这类学校,我们对于文件这章节的学习只需要掌握每个函数的基本功能,...
  • 计算机考研408的算法题详解

    千次阅读 2020-05-22 15:13:50
    /*结点的数据域*/ struct node *next;/*结点的指针域*/ }LNode,*LinkList; int Search_K(LinkList L, ElemType k) { //查找倒数第k个结点 LNode *p = L->next; LNode *q = L->next; while(p != NULL) { if(k >...
  • 1·操作系统的概念(必背) 操作系统是一组控制和管理计算机硬件和软件资源、合理的对各类作业进行调度,以方便用户使用计算机的程序集合。 1·1·1目标 方便、有效、可扩充、开放(性) *单道批处理系统(特征:...

空空如也

空空如也

1 2 3 4
收藏数 72
精华内容 28
关键字:

数据结构考研必背代码

数据结构 订阅