[数据结构与算法]数据结构实验笔记

顺序表

• 顺序表的建立与运用（插入 删除 查找）

/*顺序表的 插入 删除 查找 */

#include<bits/stdc++.h>
using namespace std;
int n;
typedef struct{
	int *elem;
	int len,listsize;
	
}Sqlist;

void Init(Sqlist &L,int n){
	L.elem=(int*)malloc((n+2)*sizeof(int));
	if(!L.elem) exit(-1);
	L.len=0;
	L.listsize=n;
	return;
}
void Creatlist(Sqlist &L){
	printf("输入%d个顺序表的元素:\n",n);
	for(int i=0;i<n;i++){
		cin>>L.elem[i];	
		int *newcase=(int *)realloc(L.elem,(L.listsize+10)*sizeof(int));
		if(!newcase) exit(-1);
		L.elem=newcase;
		L.len++;
		L.listsize+=10;
	}

	return ;
}

void Output(Sqlist &L){
	for(int i=0;i<L.len;i++) cout<<L.elem[i]<<" ";
	putchar('\n');
	return ;
}

void Insert(Sqlist &L){
	printf("输入要插入的元素和要插入的位置:\n");
	int c,i;
	cin>>c>>i;
	if(i<1||i>L.len+1) exit(-1);//通过i-1是下标来查找 
	if(L.len>=L.listsize){
		int *newcase=(int *)realloc(L.elem,(L.listsize+10)*sizeof(int));
		if(!newcase) exit(-1);
		L.elem=newcase;
		L.listsize+=10;
		
	}
	int *q=&(L.elem[i-1]);
	int *p=&(L.elem[L.len-1]);
	for(p;p>=q;p--){
		*(p+1)=*p;
	}
	*q=c;
	L.len++;
	printf("插入后的顺序表长这样:\n");
	Output(L);
	return ;
} 



void Search(Sqlist &L){
	printf("输入要查找的元素:\n");
	int c;
	cin>>c;
	for(int i=0;i<L.len;i++){
		if(L.elem[i]==c) {
			printf("%d在顺序表的第%d个\n",c,i+1);
		} 
	}
	return ;
} 

void Delete(Sqlist &L){
	printf("输入要删除的元素的位置:\n");
	int i;
	cin>>i;
	if(i<1||i>L.len) exit(-1);
	int *q=L.elem+L.len-1;//?
	for(int *p=&(L.elem[i-1]);p<q;p++){
		*p=*(p+1);
	}
	L.len--;
	printf("删除后的顺序表长这样:\n");
	Output(L);
	return ;
} 

int main(){
	Sqlist zp;
	
	printf("输入将要建立的顺序表的大小:\n");
	cin>>n;
	Init(zp,n);
	Creatlist(zp);
	
	
	printf("1:插入\n2:查找\n3:删除\n") ; 
	printf("请选择要进行的操作:\n");
	int op;
	cin>>op;
	switch(op){
		case 1:Insert(zp);break;
		case 2:Search(zp);break;
		case 3:Delete(zp);break;
		case 4:Output(zp);break;
		default: cout<<"输入指令有问题\n"<<endl; 
	}
	return 0;
} 

链表

• 链表的合并

/*链表表的连接 */

#include<bits/stdc++.h>
using namespace std;
int n,m;
typedef struct LNode{
	int date;
	struct LNode *next;
}LNode,*Linklist;

void Output(Linklist &L){
	Linklist p;
	if(!L->next) printf("空链表\n");
	 else {
	 	for(p=L->next;p!=NULL;p++){
	 		printf("%d ",p->date);
		 }
	 }
}
void Init(Linklist &L,int n){
	Linklist p;
	p=(LNode *)malloc(sizeof(LNod)*(n+2));
	L=p;
	L->date=NULL;
	
	return ;
}

void Creat(Linklist &L){
	
	return ;
}

void Connect(Linklist &L1,Linklist &L2,LinkList &ans){
	return ;
}


int main(){	
	LNode zp1,zp2,ans;
	Init(zp1);
	Init(zp2);
	Init(ans);
	printf("输入两个链表的大小：\n");
	cin>>n>>m;
	Creat(zp1,n);
	Creat(zp2,m);
	
	Connect(zp1,zp2,ans);
	printf("连接后的最终链表为:\n");
	Output(ans);
	

	
	return 0;
} 

• 链表的差

#include<bits/stdc++.h>
using namespace std;
#define ElemType int 
#define Status int 
#define ERROR -1
#define OK 1
typedef struct LNode{
	ElemType date;
	struct LNode *next;
}LNode,*LinkList;
Status Init_LinkList(LinkList &L)//初始化 
{
	LinkList p;
	p=(LinkList)malloc(sizeof(LNode));
	
	L=p;
	L->next=NULL;
	return OK;
}
void difference(LinkList La,LinkList Lb,LinkList &Lc){
	LinkList p,q,s,k;
	p=La->next;
	while(p!=NULL){
		q=Lb->next;
		while(q!=NULL){
			if(q->date==p->date) break;//B中有A的元素；
			q=q->next; 
		}
		if(q==NULL){//B中没有A的元素；
			s=Lc->next;
			while(s!=NULL){
				if(s->date==p->date) break;
				s=s->next;
			}
			if(s==NULL){//准备插入到lc
			k=(LinkList)malloc(sizeof(LNode));
			k->date=p->date;
			k->next=Lc->next;
			Lc->next=k;
			
			}
			 
		}
		p=p->next;
	}
} 
void input(LinkList &L,int n)  
{
	 
	LinkList p;
	int i;
	for(i = 1;i <= n;i ++)
	{
		
		p=(LinkList)malloc(sizeof(LNode));
		
		
			scanf("%d",&p->date);
	
			p->next = L->next;   //头插法
			L->next = p;
	
	}
}
void output(LinkList L){
	LinkList p;
	if(L->next==NULL) printf("空链表\n");
	else {
		for(p=L->next;p!=NULL;p=p->next)
		printf("%d ",p->date);
	}
}
int main(){
	LinkList La,Lb,Lc,x;
	Init_LinkList(La);
	Init_LinkList(Lb);
	Init_LinkList(Lc);
	int n,m,i;
	printf("输入La链表的大小\n");
	cin>>n;
	printf("输入La链表的值\n");
	input(La,n);
	
	printf("输入Lb链表的大小\n");
	cin>>m;
		
	printf("输入Lb链表的值\n");
	input(Lb,m);
	
	difference(La,Lb,Lc);
	printf("La-Lb的值为：\n");
	output(Lc);
	
	return 0;
} 

KMP算法

建议去哔哩哔哩看视频理解原理，附上我当时看的。
整体理解kmp(不含N=next【】)
next数组详解

#include<stdio.h>
#include<string.h>
using namespace std;
const int N=1e6+6;
char s1[N],s2[N];
int next[N];
int len1,len2;
void getnext(){
	next[0]=-1;
	next[1]=0;
	int i=0,j=-1;
	while(i<len2){
		if(j==-1||s2[i]==s2[j]){
			i++;j++;
			next[i]=j;
		}
		else j=next[j];
	}
}
int KMP(){
	int i=0,j=0;
	while(i<len1&&j<len2){
		if(j==-1||s1[i]==s2[j]){
			i++;j++;
		}
		else j=next[j];
	}
	if(j==len2) printf("%d\n",i-len2+1);
	else printf("-1\n");
}
int main()
{
  
    while(~scanf("%s",&s1)){
    	scanf("%s",&s2);
    	len1=strlen(s1);
    	len2=strlen(s2);
    	getnext();
    	KMP();
	}
  
 
  return 0;
}

二叉树

• 二叉树的递归遍历（先序、中序、后序）

#include<bits/stdc++.h>
using namespace std;
typedef struct Tree{
	int data;
	struct Tree *l;
	struct Tree *r;
}Tree,*BitTree;
BitTree CreateLink(){  //创建返回BitTree类型 
	int data,t;
	BitTree T;
	scanf("%d",&data);
	if(data==-1) return NULL; //
	
	
	T=(BitTree)malloc(sizeof(Tree));
	T->data=data;
	printf("输入%d的左节点:",data);
	T->l=CreateLink();
	printf("输入%d的右节点:",data);
	T->r=CreateLink();
	
	return T;
}

void Showxianxu(BitTree T){
	if(T==NULL) return ;
	printf("%d ",T->data);
	Showxianxu(T->l);
	Showxianxu(T->r);
} 


void Showzhongxu(BitTree T){
	if(T==NULL) return ;
	
	Showzhongxu(T->l);
	printf("%d ",T->data);
	Showzhongxu(T->r);
} 


void Showhoxu(BitTree T){
	if(T==NULL) return ;
	
	Showhoxu(T->l);
	Showhoxu(T->r);
	printf("%d ",T->data);
} 
int main(){
	BitTree zp;
	
	printf("输入root：\n");
	zp=CreateLink();
	
	printf("先序遍历:");
	Showxianxu(zp); 
	putchar('\n');
	
	printf("中序遍历:");
	Showzhongxu(zp);
	putchar('\n');
	
	printf("后序遍历:");
	Showhoxu(zp);
	putchar('\n');
	return 0;
}