11月 我的数据结构与算法学习笔记（4）

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

//字符串与多维数组
//KMP算法
 char s1[] = "abcbbabc";
 char s2[] = "ba";
 printf("%p\n",strstr(s1,s2));                          //%p 地址符  从s1中找s2 
 for(int i = 0;i<8;i++)  printf("%p\t",&s1[i]);                        //\t占位符
const char *str = "abcabaabcabc";
const char *p = "abaa";
  int pos = sm(str,p);
 cout<<pos<<endl;
	 return 0;
 }
//KMP算法 (next数组) 
#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;
void gn(char *p,int *next){
	int m = strlen(p);
	int i = 0;
	int j = -1;
	next[0] = -1;
	while(i<m){
		if(j == -1||p[i] == p[j]){
			i++;
			j++;
			next[i] = j;
		}
		else j = next[j];
	}
}
int kmp(char *str,char *p){
	int i = 0;
	int j= 0;
	int next[100];
	gn(p,next);
	int n = strlen(str);
	int m = strlen(p);
	while (i<n&&j<m){
		if(j == -1||str[i] == p[j]){
			i++;
			j++;
		}
		else  j=next[j];}
		if(j == m)  return i-j;
		else return -1;
}
int main(void){
    char *str = "abaabaabacacaabaabcc";
char *p = "abaabc";
     cout<<kmp(str,p)<<endl;
	return 0;
}
#include<iostream>
#include<stdlib.h>
using namespace std;

//二叉树的存储结构 链式结构
typedef char em;
typedef struct tn{
	em data;
	tn *lchild;                                             //左子树 
	tn *rchild;                                             //右子树  
}tn;
typedef tn *BiTree;
char str[] = "ABDH#K###E##CFI###G#J##";                       //#为空 
int idx = 0;
void ct(BiTree *t){                                         //造树 
	em ch;
	ch = str[idx++];
	if(ch =='#')   *t = NULL;
    else{
    	*t =(BiTree)malloc(sizeof(tn));
    	(*t)->data = ch;
    	ct (&(*t)->lchild);
    	ct(&(*t)->rchild);
	}
}
//前序遍历
void po(BiTree t){
	if(t == NULL) return;
	printf("%c",t->data);
	po(t->lchild); //先左后右 
	po(t->rchild);
}                                                        //ABDHKECFIGJ
//中序遍历 
void io(BiTree t){
	if(t ==NULL) return;
	io(t->lchild);
	printf("%c",t->data);
	io(t->rchild); 
}                                                        //HKDBEAIFCGJ
//后序遍历
void ppo(BiTree t){
	if( t == NULL) return;
	ppo(t->lchild);
	ppo(t->rchild);
	printf("%c",t->data);
}                                                             //KHDEBIFJGCA
//一维数组
int main(void){
	int a[] = {16,458,45,12,54};
	                                                   //二维数组 （坐标） 
	int b[5][6];
	char ch[3][4];
	float f[3][5];
	BiTree t;
	ct(&t);
	po(t);
	cout<<endl;
	io(t);
	cout<<endl;
	po(t);
	cout<<endl; 
	return 0;
}
//线索二叉树 
#include<iostream>
#include<stdlib.h>
using namespace std;

typedef char em;
typedef struct tn{
    em data;
    struct tn *lc;
    struct tn *rc;
    int lt;                                          // 0=左孩子，1=前驱线索
    int rt;                                          // 0=右孩子，1=后继线索
}tn;
typedef tn *tt;
char s[] = "ABDH##I##EJ###CF##G##";
int idx = 0;
// 1. 创建普通二叉树
void ct(tt *t){ 
    em ch = s[idx++];
    if(ch == '#')  *t = NULL;
    else {
        *t = (tt)malloc(sizeof(tn));
        (*t)->data = ch;
        ct(&(*t)->lc);
        (*t)->lt = (*t)->lc ? 0 : 1;
        ct(&(*t)->rc);
        (*t)->rt = (*t)->rc ? 0 : 1;
    }
}
// 2. 中序线索化函数：pr改为指针参数
void tr(tt t, tt *pr){                           // 接收pr的地址，实时更新前驱
    if(t != NULL){
        tr(t->lc, pr);                                      // 递归左子树
        
                                                 // 建立前驱线索
        if(t->lt == 1) t->lc = *pr;
                                   // 建立后继线索（*pr不为NULL时）
        if(*pr != NULL && (*pr)->rt == 1) (*pr)->rc = t;
        
        *pr = t;                                   // 更新前驱为当前节点
        tr(t->rc, pr);                                  // 递归右子树
    }
}
// 3. 建立线索二叉树（调用tr时传递pr地址）
void iot(tt *t, tt *head){
    *head = (tt)malloc(sizeof(tn));
    (*head)->lt = 0;
    (*head)->rt = 1;
    (*head)->rc = *head;                     // 初始右指针指向自己
    if(*t == NULL){
        (*head)->lc = *head;
    } else {
        (*head)->lc = *t;
        tt pr = *head;             // 局部pr，初始化为头节点（替代全局变量）
        tr(*t, &pr);                               // 传递pr地址给tr
                                       // 处理最后一个节点的后继线索
        pr->rc = *head;
        pr->rt = 1;
        (*head)->rc = pr;
    }
}
// 4. 中序遍历（无修改）
void io(tt t){
    tt curr = t->lc;
    while(curr != t){
                                            // 找左子树最左节点
        while(curr->lt == 0) curr = curr->lc;
        printf("%c ", curr->data);
       
                                              // 沿后继线索遍历
        while(curr->rt == 1 && curr->rc != t){
            curr = curr->rc;
            printf("%c ", curr->data);
        }
                                               // 进入右子树
        curr = curr->rc;
    }
}

int main(void){
    tt t, head;
    ct(&t);                                       // 创建树
    iot(&t, &head);                                    // 线索化
    printf("中序遍历结果：");
    io(head);                                   // 输出：D H B I J E A F C G
    return 0;
}
//树与队列的转换   #=-1
#include<iostream>
using namespace std;
//深度问题 左右子树一起出队 
int md(tn *root){
	if(root == NULL) return 0;
	int dp = 0;
	Q *q = initQueue();
	eq(q,root);
	while(!ie(q)){
		int count = qs(q);
		while (count > 0){
			tn *curr;
			dq(q,&curr);
			if(curr->lc!= NULL)  eq(q,curr->lc);
			if(curr->rc!= NULL)  eq(q,curr->rc);
			count--;
		}
		dp++;                                                  //深度 
	}
	return dp;
}
int main(void){
	return 0;
} 
//图   链表或数组 
//邻接矩阵 
#include<iostream>
#include<stdlib.h>
using namespace std;
typedef char vt;                                         //顶点类型 
typedef int et;                                 //边的权值类型 （0或1） 
//带有权值的矩阵（没有连接输入无穷  0为对角线  有连接就写权值）   
#define MAX 0x7fffffff                            //表示无穷 
#define MAXSIZE 100                                //最大顶点数 
//图的邻接矩阵（无向图）结构体定义 
typedef struct{
	vt v[MAXSIZE];                                          //顶点数组 
	et a[MAXSIZE][MAXSIZE];                         //邻接矩阵（二维数组） 
	int vn;                                            //顶点个数 
	int en;                                             //边条数  
}M;
//创建图的邻接矩阵
void cg(M *g){
	g->vn = 4;                                         //顶点数 
	g->en = 5;                                           //边数 
	                                 //图的邻接矩阵（有向图）结构体定义      
	                                            //有向图改为两个4 
	                                        //权值矩阵也是两个4 
	                                                //权值矩阵：
	                                                   /*
	g->v[0] = '0';
	g->v[1] = '1';
	g->v[2] = '2';
	g->v[3] = '3' ;                                            */
	                                                  //顶点命名 
	g->v[0] = '0';
	g->v[1] = '1';
	g->v[2] = '2';
	g->v[3] = '3';
	                                                //初始化邻接矩阵
	for(int i=0;i<g->vn;i++){
		for(int j=0;j<g->vn;j++){
			g->a[i][j] = 0;
			                                        //权值矩阵默认为MAX
			                                       /*if（i == j) g->a[i][j] = 0;*/ 
		}
	} 
	                                                       //添加边
	                                                     //对称赋值
	g->a[0][1] = 1; g->a[1][0] = 1; 
	g->a[0][2] = 1; g->a[2][0] = 1; 
	g->a[0][3] = 1; g->a[3][0] = 1; 
	g->a[1][2] = 1; g->a[2][1] = 1; 
	g->a[2][3] = 1; g->a[3][2] = 1; 
	/*添加边及权值（等号后面为权值） 
	g->a[0][3] = 3; 
     g->a[1][0] = 5; 
      g->a[1][2] = 2; 
        g->a[2][0] = 4; 
        g->a[2][1] = 6; 
	                                                          */ 
} 
/*有向边
g->a[0][3] = 1; 
g->a[1][0] = 1; 
g->a[1][2] = 1; 
g->a[2][0] = 1; 
g->a[2][1] = 1; 
*/
//打印邻接矩阵
void pm(M g){
	cout<<"邻接矩阵表示如下："<<endl;
	for(int i=0;i<g.vn;i++){
		for(int j = 0;j<g.vn;j++){
			                                           //权值矩阵：
			//if（g.a[i][j] == MAX)  cout<<"MAX"<<endl;
			cout<<g.a[i][j];
		}
		cout<<endl;
	} 
} 
int main(void){
	M g;                                   //创建一个邻接矩阵结构体变量
	cg(&g);                                                   //初始化 
	pm(g);                                                 //输出 
	return 0; 
}

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：学习笔记 数据结构 习笔记 include RETURN

相关内容：数据结构学习笔记