2024-08-12 实验一：设计实现抽象数据类型“有理数”
#include<stdio.h>
typedef struct
{
int num,deno;
}RatNum;
double fabs(double x)
{
return (x>0)?x:(-x);
}
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int lcm(int a,int b)
{
return a/gcd(a,b)*b;
}
void create(RatNum *p)
{
printf("input a num:");
scanf("%d %d",&(p->num),&(p->deno));
}
void print(RatNum a)
{
if(a.deno==1) printf("%d",a.num);
else printf("%d/%d",a.num,a.deno);
}
RatNum approximation(RatNum a)
{
int factor=gcd(a.num,a.deno);
a.deno/=factor;
a.num/=factor;
if((a.deno<0&&a.num>0)||(a.deno<0&&a.num<0))
{
a.num=-a.num;
a.deno=-a.deno;
}
return a;
}
RatNum add(RatNum a,RatNum b)
{
RatNum res;
res.num=a.num*b.deno+b.num*a.deno;
res.deno=a.deno*b.deno;
return approximation(res);
}
RatNum sub(RatNum a,RatNum b)
{
RatNum res;
res.num=a.num*b.deno-b.num*a.deno;
res.deno=a.deno*b.deno;
return approximation(res);
}
RatNum muti(RatNum a,RatNum b)
{
RatNum res;
res.num=a.num*b.num;
res.deno=a.deno*b.deno;
return approximation(res);
}
RatNum div(RatNum a,RatNum b)
{
RatNum res={0,0};
if(a.deno==0||b.deno==0)
{
printf("error\n");
return res;
}
res.num=a.num*b.deno;
res.deno=a.deno*b.num;
return approximation(res);
}
RatNum Create_RatNum(double x, double error) {
int sign=(x<0)?-1:1;
x=(x>0)?x:(-x);
double lower_n=0,lower_d=1;
double upper_n=1,upper_d=0;
int num=1,denom=1;
while (1)
{
num=lower_n+upper_n;
denom=lower_d+upper_d;
double approx = (double)num / denom;
if (fabs(approx - x) < error)
{
RatNum result = {sign * num, denom};
return result;
}
if (approx < x)
{
lower_n = num;
lower_d = denom;
} else
{
upper_n = num;
upper_d = denom;
}
}
}
int main()
{
int ch;
RatNum a,b,res;
printf("1.Create from a decimal\n2.clac\n");
scanf("%d",&ch);
if(ch==1)
{
printf("Input the num and the maxmize error\n");
double input,error;
scanf("%lf",&input);
RatNum x=Create_RatNum(input,error);
print(x);
}
else
{
printf("1.add\n2.sub\n3.muti\n4.div\n");
scanf("%d",&ch);
printf("give the first number\n");
create(&a);
printf("give the second number\n");
create(&b);
switch (ch)
{
case 1:res=add(a,b);break;
case 2:res=sub(a,b);break;
case 3:res=muti(a,b);break;
case 4:res=div(a,b);break;
default:break;
}
print(res);
}
return 0;
}
2024-08-16 实验二：顺序表基本操作的实现
#include<stdio.h>
#define ElemType int
#define ERROR 1
#define maxsize 110
//#define CLS "cls"//win
#define CLS "clear"//macos/linux
typedef struct
{
ElemType elem[maxsize];//静态申请顺序表所需要的空间
int last;
}SeqList;
SeqList List;
void Init_List(SeqList *L);
void Visit(SeqList *L);
void Create(SeqList *L,int n);
void Insert_List(SeqList *L,int arr,ElemType x);
int Seq_Length(SeqList *L);
void Reserve_List(SeqList *L,int l,int r);
void Sort_List(SeqList *L,int l,int r);
void Merge_List(SeqList *a,SeqList *b,SeqList *c);
void swap(ElemType *a,ElemType *b);
void Merge_List(SeqList *a,SeqList *b,SeqList *c);
void Delete_List(SeqList *L,int arr);
void Merge_Sort_List(SeqList *a,SeqList *b,SeqList *c);
void swap(ElemType *a,ElemType *b)
{
ElemType tmp=*a;
*a=*b;
*b=tmp;
}
void Init_List(SeqList *L)//初始化操作
{
L->last=-1;
}
void Visit(SeqList *L)//按顺序输出顺序表
{
if(L->last==-1)
{
printf("Empty_array\n");
return;
}
for(int i=0;i<=L->last;++i) printf("%d ",L->elem[i]);
printf("\n");
}
void Create(SeqList *L,int n)//创建一个单链表，并使用尾插法输入n个数字
{
if(n>maxsize)
{
printf("Failed to create the array,the num is out of the size\n");
}
Init_List(L);
//初始化链表L
for(int i=0;i<n;++i)
{
//依次输入数据，并将其添加至顺序表尾部
ElemType input;
scanf("%d",&input);
Insert_List(L,i-1,input);
}
}
void Insert_List(SeqList *L,int arr,ElemType x)//在顺序表L中，索引号arr的数字之后插入数据元素x
{
//第一步，移动索引号为arr+1到last到元素，使其索引号+1
if(L->last==maxsize)
{
//处理静态顺序表满的异常
printf("Error,the array is full\n");
return;
}
else ++L->last;
for(int i=L->last;i>=arr+1;--i) L->elem[i+1]=L->elem[i];
//第二步，将x添加到顺序表的arr结点当中
L->elem[arr+1]=x;
}
int Seq_Length(SeqList *L)//返回顺序表L的长度
{
return L->last+1;
}
void Reserve_List(SeqList *L,int l,int r)//对顺序表L中，索引号为l到r的项进行逆序操作
{
if(l>r) printf("Error,the num L is larger than R\n");
while(l<r)
{
swap(&(L->elem[l]),&(L->elem[r]));
++l,--r;
}
}
void Sort_List(SeqList *L,int l,int r)//将顺序表中,对索引号l到r的项从小到大排序
{
if(l>=r) return;
int arr=L->elem[l+r>>1];
int i=l-1,j=r+1;
while(i<j)
{
do ++i; while(L->elem[i]<arr);
do --j; while(L->elem[j]>arr);
if(i<j) swap(&(L->elem[i]),&(L->elem[j]));
}
Sort_List(L,l,j);
Sort_List(L,j+1,r);
}
void Merge_List(SeqList *a,SeqList *b,SeqList *c)//将a和b两个顺序表合并，并将答案存入c中
{
int i=0,j=0,k=0;
for(int i=0;i<=a->last;++i,++k) Insert_List(c,k-1,a->elem[i]);
for(int i=0;i<=b->last;++i,++k) Insert_List(c,k-1,b->elem[i]);
}
void Merge_Sort_List(SeqList *a,SeqList *b,SeqList *c)//合并两个有序的顺序表
{
int i=0,j=0,k=0;
while(i<=a->last&&j<=b->last)
{
if(a->elem[i]<b->elem[j])
{
Insert_List(c,k-1,a->elem[i]);
++i;
}
else
{
Insert_List(c,k-1,b->elem[j]);
++j;
}
++k;
}
while(i<=a->last)
{
Insert_List(c,k-1,a->elem[i]);
++i,++k;
}
while(j<=b->last)
{
Insert_List(c,k-1,b->elem[j]);
++j,++k;
}
}
void Delete_List(SeqList *L,int arr)//删除顺序表L中索引号为arr的元素
{
for(int i=arr+1;i<=L->last;++i) L->elem[i-1]=L->elem[i];
--L->last;
}
void fun()
{
//system(CLS);
printf("1.在顺序表中插入数组元素\n");
printf("2.删除数组中的元素\n");
printf("3.求顺序表的长度\n");
printf("4.顺序表的逆序\n");
printf("5.将顺序表中的值从小到大排序\n");
printf("6.合并两个顺序表\n");
printf("7.合并两个有序的顺序表\n");
printf("8.输出L\n");
printf("9.使用尾插法一次性向List输入数据\n");
int ch;
scanf("%d",&ch);
if(ch==1)
{
printf("2个参数：在顺序表L中，索引号arr的数字之后插入数据元素x\n");
int arr;
ElemType x;
scanf("%d%d",&arr,&x);
Insert_List(&List,arr,x);
}
else if(ch==2)
{
printf("1个参数：在顺序表L中，删除索引号为arr的元素\n");
int arr;
scanf("%d",&arr);
Delete_List(&List,arr);
}
else if(ch==3)
{
printf("0个参数\n");
printf("顺序表L的长度为：%d\n",Seq_Length(&List));
}
else if(ch==4)
{
printf("2个参数：需要逆序部分索引号的左边界和右边界\n");
int l,r;
scanf("%d%d",&l,&r);
Reserve_List(&List,l,r);
}
else if(ch==5)
{
printf("2个参数：需要排序的索引号左边界和右边界\n");
int l,r;
scanf("%d%d",&l,&r);
Sort_List(&List,l,r);
}
else if(ch==6)
{
SeqList a,b;
printf("4个参数：请先输入顺序表a的长度，再依次输入a中的值；再输入顺序表b的长度，再依次输入b中的值\n");
int len;
scanf("%d",&len);
Create(&a,len);
scanf("%d",&len);
Create(&b,len);
Init_List(&List);
Merge_List(&a,&b,&List);
}
else if(ch==7)
{
SeqList a,b;
printf("4个参数：请先输入顺序表a的长度，再依次输入a中的值；再输入顺序表b的长度，再依次输入b中的值\n");
int len;
scanf("%d",&len);
Create(&a,len);
scanf("%d",&len);
Create(&b,len);
Init_List(&List);
Merge_Sort_List(&a,&b,&List);
}
else if(ch==8)
{
Visit(&List);
}
else if(ch==9)
{
printf("2个参数：输入需要创建顺序表的表长，以及顺序表的每个数字\n");
int n;
scanf("%d",&n);
Create(&List,n);
}
}
int main()
{
Init_List(&List);
while(1) fun();
return 0;
}
/*
在顺序表中插入数据元素
删除数据元素
求顺序表的长度
顺序表的逆置
顺序表的按值从小到大排序
合并有序的两个顺序表*/
2024-08-16 实验三：单链表基本操作的实现
//单链表的初始化
//数据的插入
//数据的删除
//输出单链表内中各元素
//求单链表的长度
//实现单链表中数据结点的按值排序
//实现单链表的逆置
//合并两个有序的单链表（有序的a表和有序的b表合并之后的结果保存在a表中）
//Powered By @Zeyu.Fang
#include<stdio.h>
#include<stdlib.h>
#define ElemType int
//#define CLS "cls"//win
#define CLS "clear"//macos/linux
typedef struct Node
{
ElemType data;
struct Node *next;
}Node,*LinkList;
Node *List;
void Init_List(Node *L);
void Insert_List(Node *L,int arr,ElemType x);
void Delete_List(Node *L,int arr);
void Visit(Node *L);
int List_Length(Node *L);
void List_Bubble_Sort(Node *L);
void List_Reserve(Node *L);
void Merge_List(Node *a,Node *b);
void swap(ElemType *a,ElemType *b);
void swap(ElemType *a,ElemType *b)
{
ElemType tmp=*a;
*a=*b;
*b=tmp;
}
void Init_List(Node *L)//单链表的初始化
{
L->next=NULL;
}
void Insert_List(Node *L,int arr,ElemType x)//向单链表L的第arr位后面插入x
{
Node *p=L;
int cnt=-1;
while(p->next!=NULL&&arr!=-1)
{
p=p->next;
++cnt;
if(cnt==arr) break;
}
if(cnt<arr)
{
printf("Insert_Out_of_Array\n");
return;
}
Node *new_node=(Node*)malloc(sizeof(Node));
new_node->data=x;
new_node->next=p->next;
p->next=new_node;
}
void Delete_List(Node *L,int arr)//删除单链表L中索引号为arr的结点
{
Node *p=L;
int cnt=0;
while(p->next!=NULL&&arr!=0)
{
p=p->next;
++cnt;
if(cnt==arr) break;
}
if(p->next==NULL)
{
printf("Delete_Out_of_Array\n");
return;
}
Node *tmp=p->next;
p->next=p->next->next;
free(tmp);
}
void Visit(Node *L)//输出单链表中的所有元素
{
Node *p=L->next;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
int List_Length(Node *L)//返回1以L为头节点的链表的长度
{
Node *p=L;
int cnt=0;
while(p->next!=NULL)
{
p=p->next;
++cnt;
}
return cnt;
}
void List_Bubble_Sort(Node *L)//对链表L进行冒泡排序
{
Node *p=L;
int change=1;
while(change)
{
change=0;
p=L;
while(p->next->next!=NULL)
{
p=p->next;
if(p->data>p->next->data)
{
swap(&(p->data),&(p->next->data));
change=1;
}
}
}
}
void List_Reserve(Node *L)//实现单链表的逆置
{
if(!L->next||!(L->next->next)) return;
Node *p=L->next->next; L->next->next=NULL;
while(p)
{
Node *temp=p->next;
p->next=L->next; L->next=p;
p=temp;
}
}
void Merge_List(Node *a,Node *b)//合并两个有序的单链表（有序的a表和有序的b表合并之后的结果保存在a表中）
{
Node *pre=a,*p=a->next,*q=b->next;
while(p&&q)
{
if(p->data<q->data) {pre->next=p;pre=p;p=p->next;}
else {pre->next=q;pre=q;q=q->next;}
}
pre->next=p?p:q;
free(b);
}
void Init_Insert(Node *L,int n)
{
Init_List(L);
for(int i=1;i<=n;++i)
{
int x;
scanf("%d",&x);
Insert_List(L,i-2,x);
}
}
void fun()
{
printf("1.初始化链表L，并使用尾插法添加n个元素\n");
printf("2.在链表L的索引号arr后面插入一个数字x\n");
printf("3.删除链表L中索引号为arr的项\n");
printf("4.输出单链表L中所有的项\n");
printf("5.输出单链表L的长度\n");
printf("6.将单链表L中的值按照升序排序\n");
printf("7.将单链表中的值逆序\n");
printf("8.合并两个有序的单链表\n");
int ch;
scanf("%d",&ch);
if(ch==1)
{
printf("2个参数：需要添加的元素个数，所有元素\n");
int n;
scanf("%d",&n);
Init_Insert(List,n);
}
else if(ch==2)
{
printf("2个参数：在索引号arr后面添加元素x\n");
int arr,x;
scanf("%d%d",&arr,&x);
Insert_List(List,arr,x);
}
else if(ch==3)
{
printf("1个参数：删除元素的索引号arr\n");
int arr;
scanf("%d",&arr);
Delete_List(List,arr);
}
else if(ch==4)
{
printf("无参数\n");
Visit(List);
}
else if(ch==5)
{
printf("无参数\n");
printf("List的长度为%d\n",List_Length(List));
}
else if(ch==6)
{
printf("无参数\n");
List_Bubble_Sort(List);
}
else if(ch==7)
{
printf("无参数\n");
List_Reserve(List);
}
else if(ch==8)
{
printf("2个参数：需要和List归并的升序数组b的长度，以及他的所有元素\n");
int n;
scanf("%d",&n);
Node *b=malloc(sizeof(Node));
Init_Insert(b,n);
Merge_List(List,b);
}
}
int main()
{
List=malloc(sizeof(Node));
while(1) fun();
return 0;
}
2024-08-19 实验四：顺序栈和循环队列的基本运算
stack.h
typedef struct
{
StackElementType elem[maxsize];
int top;
}SeqStack;
void InitStack(SeqStack *s)//顺序栈的初始化操作
{
s->top=-1;
}
int Stack_IsEmpty(SeqStack *s)//顺序栈的判空
{
if(s->top==-1) return 1;
else return 0;
}
int Stack_IsFull(SeqStack *s)//顺序栈的判满
{
if(s->top==maxsize-1) return 1;
else return 0;
}
int Stack_Push(SeqStack *s,StackElementType e)//顺序栈的入栈操作
{
if(Stack_IsFull(s)) return 0;
++s->top;
s->elem[s->top]=e;
return 1;
}
int Stack_Pop(SeqStack *s,StackElementType *e)//顺序栈的出栈操作
{
if(Stack_IsEmpty(s)) return 0;
--s->top;
return 1;
}
int Stack_GetTop(SeqStack *s,StackElementType *e)//读取栈顶元素
{
if(Stack_IsEmpty(s)) return 0;
*e=s->elem[s->top];
return 1;
}
queue.h
//构建循环队列类型
// 1.实现循环队列的初始化
// 2.循环队列的判空
// 3.循环队列的入队
// 4.循环队列的出队
// 5.读取队头元素
// 6.读取队尾元素内容
// 7.基于循环队列实现杨辉三角形N行数据输出
// @右手fang 2024-08-19
typedef struct
{
QueueElementType elem[maxsize];
int rear;
int front;
}SeqQueue;
void InitQueue(SeqQueue *q)//循环链表的初始化操作
{
q->front=0;
q->rear=0;
}
int Queue_IsEmpty(SeqQueue *q)//循环队列的判空
{
if(q->front==q->rear) return 1;
else return 0;
}
int Queue_IsFull(SeqQueue *q)
{
return (q->rear+1)%maxsize==q->rear;
}
int Queue_Push(SeqQueue *q,QueueElementType e)
{
if(Queue_IsFull(q)) return 0;
q->elem[q->rear]=e;
q->rear=(q->rear+1)%maxsize;
return 1;
}
int Queue_Pop(SeqQueue *q,QueueElementType *e)
{
if(Queue_IsEmpty(q)) return 0;
*e=q->elem[q->front];
q->front=(q->front+1)%maxsize;
return 1;
}
int Queue_Front(SeqQueue *q,QueueElementType *e)
{
if(Queue_IsEmpty(q)) return 0;
*e=q->elem[q->front];
return 1;
}
int Queue_Back(SeqQueue *q,QueueElementType *e)
{
if(Queue_IsEmpty(q)) return 0;
*e=q->elem[(q->rear-1+maxsize)%maxsize];
return 1;
}
DebugStack.c
//顺序栈和循环队列的基本运算
// 1.实现顺序栈的初始化
// 2.顺序栈的判空
// 3.顺序栈的入栈
// 4.顺序栈的出栈
// 5.读取栈顶元素
// 6.基于顺序栈实现表达式或者文本括号匹配的检验运算
//构建循环队列类型
// 1.实现循环队列的初始化
// 2.循环队列的判空
// 3.循环队列的入队
// 4.循环队列的出队
// 5.读取队头元素
// 6.读取队尾元素内容
// 7.基于循环队列实现杨辉三角形N行数据输出
// @右手fang 2024-08-19
#include<stdio.h>
#define maxsize 100
#define StackElementType int
#include"Stack.h"
SeqStack s;
void menu()
{
printf("1.实现顺序栈的初始化\n2.顺序栈的判空\n3.顺序栈的入栈\n4.顺序栈的出栈\n5.读取栈顶元素\n6.基于顺序栈实现表达式或者文本括号匹配的检验运算\n");
int op;
scanf("%d",&op);
if(op==1) InitStack(&s);
else if(op==2)
{
if(Stack_IsEmpty(&s)) printf("The stack is empty\n");
else printf("It is not an empty stack\n");
}
else if(op==3)
{
if(Stack_IsFull(&s))
{
printf("You cannot push number into the stack\n");
return;
}
printf("Input the number that you want to push\n");
int x;
scanf("%d",&x);
Stack_Push(&s,x);
}
else if(op==4)
{
int x;
if(Stack_Pop(&s,&x)) printf("OK\n");
else printf("Oops!The stack is empty\n");
}
else if(op==5)
{
int x;
if(Stack_GetTop(&s,&x)) printf("The top of the stack is:%d\n",x);
else printf("Oops!The stack is empty\n");
}
}
int main()
{
while(1) menu();
return 0;
}
DebugQueue
//顺序栈和循环队列的基本运算
// 1.实现顺序栈的初始化
// 2.顺序栈的判空
// 3.顺序栈的入栈
// 4.顺序栈的出栈
// 5.读取栈顶元素
// 6.基于顺序栈实现表达式或者文本括号匹配的检验运算
//构建循环队列类型
// 1.实现循环队列的初始化
// 2.循环队列的判空
// 3.循环队列的入队
// 4.循环队列的出队
// 5.读取队头元素
// 6.读取队尾元素内容
// 7.基于循环队列实现杨辉三角形N行数据输出
// @右手fang 2024-08-19
#include<stdio.h>
#define maxsize 100
#define QueueElementType int
#include"Queue.h"
SeqQueue s;
void menu()
{
printf("1.循环队列的初始化\n2.循环队列的判空\n3.循环队列的判满\n4.循环队列的入队\n5.循环队列的出队\n");
printf("6.读取队头元素\n7.读取队尾元素内容\n");
int op;
scanf("%d",&op);
if(op==1) InitQueue(&s);
else if(op==2)
{
if(Queue_IsEmpty(&s)) printf("The queue is empty\n");
else printf("It is not an empty queue\n");
}
else if(op==3)
{
if(Queue_IsFull(&s)) printf("The queue is full\n");
else printf("The queue is not full\n");
}
else if(op==4)
{
if(Queue_IsFull(&s))
{
printf("You cannot push number into the queue\n");
return;
}
printf("Input the number that you want to push\n");
int x;
scanf("%d",&x);
Queue_Push(&s,x);
}
else if(op==5)
{
int x;
if(Queue_Pop(&s,&x))printf("OK\n");
else printf("The queue is empty\n");
}
else if(op==6)
{
int x;
if(Queue_Front(&s,&x)) printf("The front of the queue is:%d\n",x);
else printf("Oops!The queue is empty\n");
}
else if(op==7)
{
int x;
if(Queue_Back(&s,&x)) printf("The back of the queue is:%d\n",x);
else printf("Oops!The queue is empty\n");
}
}
int main()
{
while(1) menu();
return 0;
}
Parenthese
#include<stdio.h>
#define StackElementType char
#define maxsize 100
#include"Stack.h"
int match(char str1,char str2)
{
if(str1=='('&&str2==')') return 1;
if(str1=='['&&str2==']') return 1;
if(str1=='{'&&str2=='}') return 1;
return 0;
}
void BracketMatch(char str[])
{
SeqStack s;
int i;
char ch;
InitStack(&s);
for(i=0;str[i]!='\0';++i)
{
switch(str[i])
{
case '(':
case '[':
case '{':
Stack_Push(&s,str[i]);break;
case ')':
case ']':
case '}':
if(Stack_IsEmpty(&s))
{printf("右括号多余\n");return;}
else
{
Stack_GetTop(&s,&ch);
if(match(ch,str[i])) Stack_Pop(&s,&ch);
else {printf("括号类型不匹配\n");return;}
}
break;
}
}
if (Stack_IsEmpty(&s)) printf("括号匹配成功\n");
else printf("左括号多余\n");
}
int main()
{
char str[100];
scanf("%s",str);
BracketMatch(str);
return 0;
}
Yang_Hui_Triangle
#include<stdio.h>
#define maxsize 100
#define QueueElementType int
#include"Queue.h"
void Yang_Hui_Triangle(int N)
{
SeqQueue q;
InitQueue(&q);
Queue_Push(&q,1);//第一行元素入队
for(int n=2;n<=N;++n)
{
Queue_Push(&q,1);//第n行的第一个元素入队
for(int i=1;i<=n-2;++i)
{
QueueElementType tmp1,tmp2;
Queue_Pop(&q,&tmp1);
printf("%d ",tmp1);
Queue_Front(&q,&tmp2);
tmp2+=tmp1;
Queue_Push(&q,tmp2);
}
QueueElementType x;
Queue_Pop(&q,&x);
printf("%d ",x);
Queue_Push(&q,1);
printf("\n");
}
while(!Queue_IsEmpty(&q))
{
QueueElementType x;
Queue_Pop(&q,&x);
printf("%d ",x);
}
}
int main()
{
Yang_Hui_Triangle(20);
return 0;
}
2024-08-20 实验五：串的模式匹配
//构建串的定长顺序存储结构；实现串的创建，串的访问输出；实现模式串和主串的简单匹配算法和kmp模式匹配算法。
#include<stdio.h>
#include<string.h>
#define maxlength 100
typedef struct
{
char ch[maxlength];
int len;
}SString;
void get_next(SString *str,int nxt[])
{
int i=1,j=0;
nxt[0]=-1;nxt[1]=0;
while(i<str->len)
{
if(j==-1||str->ch[i]==str->ch[j]) {++i;++j;nxt[i]=j;}
else j=nxt[j];
}
}
int KMP_Pair(SString *str,SString *substr,int nxt[])
{
int i=0,j=0;
while(i<str->len)
{
if(str->ch[i]==substr->ch[j]) ++i,++j;
else j=nxt[j];
if(j==substr->len) return i-j+1;
}
return -1;
}
int Easy_Pair(SString *str,SString *substr)
{
int i=0,j=0;
while(i<str->len&&j<substr->len)
{
if(str->ch[i]==substr->ch[j]) ++i,++j;
else {i=i-j+1;j=0;}
if(j==substr->len) return i-j+1;
}
return -1;
}
int get_str(SString *str)
{
scanf("%s",str->ch);
str->len=strlen(str->ch);
return 1;
}
void print_str(SString *str)
{
printf("%s",str->ch);
}
int main()
{
int nxt[100];
SString str,substr;
int ch;
printf("1.简单模式匹配\n2.KMP模式匹配\n3.输入一个串并输出\n");
scanf("%d",&ch);
if(ch==1)
{
printf("Input the main string\n");
get_str(&str);
printf("Input the sub str\n");
get_str(&substr);
int ans=Easy_Pair(&str,&substr);
if(ans==-1) printf("Error\n");
else printf("The start of the string is %d",ans);
}
else if(ch==2)
{
printf("Input the main string\n");
get_str(&str);
printf("Input the sub str\n");
get_str(&substr);
int nxt[100];
get_next(&substr,nxt);
int ans=KMP_Pair(&str,&substr,nxt);
if(ans==-1) printf("Error\n");
else printf("The start of the string is %d",ans);
}
else if(ch==3)
{
get_str(&str);
print_str(&str);
}
return 0;
}
2024-08-22 实验六：三元组顺序表压缩存储结构的稀疏矩阵的运算
//构建矩阵的三元组顺序表压缩存储结构；
//实现三元组顺序表压缩存储结构的矩阵的创建
//矩阵的输出
//矩阵的简单转置和快速转置算法
//以及两个矩阵的相加。
#include<stdio.h>
#include<string.h>
#define ElemType int
#define MAXSIZE 100
typedef struct
{
int row,col;
ElemType e;
}Triple;
typedef struct
{
Triple data[MAXSIZE+1];
int m,n,len;
}TSMarix;
void init(TSMarix *table)
{
table->len=0;
}
void build(TSMarix *table)
{
printf("输入矩阵的行数和列数\n");
scanf("%d%d",&(table->m),&(table->n));
for(int i=1;i<=table->m;++i)
{
for(int j=1;j<=table->n;++j)
{
int e;
scanf("%d",&e);
if(e==0) continue;
table->len++;
table->data[table->len].row=i;
table->data[table->len].col=j;
table->data[table->len].e=e;
}
}
}
void output(TSMarix *table)
{
int t=1;
for(int i=1;i<=table->m;++i)
{
for(int j=1;j<=table->n;++j)
{
if(table->data[t].row==i&&table->data[t].col==j)
printf("%d ",table->data[t++].e);
else
printf("0 ");
}
printf("\n");
}
}
void add(TSMarix *table1,TSMarix *table2,TSMarix *ans)
{
if((table1->m!=table2->m)||(table1->n!=table2->n))
{
printf("Error\n");
return;
}
ans->m=table1->m;
ans->n=table1->n;
init(ans);
int t1=1,t2=1,t=1;
for(int i=1;i<=table1->m;++i)
{
for(int j=1;j<=table1->n;++j)
{
int v=0;
if(table1->data[t1].row==i&&table1->data[t1].col==j)
v+=table1->data[t1++].e;
if(table2->data[t2].row==i&&table2->data[t2].col==j)
v+=table2->data[t2++].e;
if(v==0) continue;
ans->len=t;
ans->data[t].row=i;
ans->data[t].col=j;
ans->data[t++].e=v;
}
}
output(ans);
}
void quick_tranpose(TSMarix *table,TSMarix *ans)
{
int col,q;
int num[MAXSIZE],position[MAXSIZE];
ans->len=table->len;
ans->n=table->m;
ans->m=table->n;
init(ans);
memset(num,0,sizeof num);
for(int i=1;i<=table->len;++i) ++num[table->data[i].col];//统计出现次数
position[1]=1;
for(int i=2;i<=table->n;++i) position[i]=position[i-1]+num[i-1];
for(int i=1;i<=table->len;++i)
{
col=table->data[i].col;
q=position[col];
ans->data[q].row=table->data[i].col;
ans->data[q].col=table->data[i].row;
ans->data[q].e=table->data[i].e;
++position[col];
}
}
void tranpose(TSMarix *table,TSMarix *ans)
{
int t=0;
ans->len=table->len;
ans->m=table->n;
ans->n=table->m;
for(int i=1;i<=table->n;++i)
{
for(int j=1;j<=table->len;++j)
{
if(table->data[j].col==i)
{
ans->data[++t].col=table->data[j].row;
ans->data[t].row=table->data[j].col;
ans->data[t].e=table->data[j].e;
}
}
}
}
void menu()
{
printf("1.读入矩阵直接输出\n");
printf("2.读入矩阵，转置输出\n");
printf("3.读入矩阵，快速转置输\n");
printf("4.读入2个矩阵，相加后输出\n");
int op;
scanf("%d",&op);
if(op==1)
{
TSMarix table;
init(&table);
build(&table);
output(&table);
}
else if(op==2)
{
TSMarix table,ans;
init(&table);
init(&ans);
build(&table);
tranpose(&table,&ans);
output(&ans);
}
else if(op==3)
{
TSMarix table,ans;
init(&table);
init(&ans);
build(&table);
quick_tranpose(&table,&ans);
output(&ans);
}
else if(op==4)
{
TSMarix table1,table2,ans;
init(&table1);
init(&table2);
init(&ans);
build(&table1);
build(&table2);
add(&table1,&table2,&ans);
}
}
int main()
{
while(1) menu();
return 0;
}
2024-08-26 实验七：二叉树的基本运算
//构建二叉树的二叉链表存储结构
//实现二叉树的创建
//二叉树的先序/中序/后序递归遍历
//统计二叉树的高度
//统计各类结点的个数
//先序/中序非递归遍历
//层序遍历等运算
//二叉树中数据元素的类型统一抽象表示为TElemType类型，在程序中将TElemType类型具体化为char类型
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxsize 100
#define TElemType char
typedef struct BiTree
{
TElemType data;
struct BiTree *lchild,*rchild;
}BiTree;
#define StackElementType BiTree*
#define QueueElementType BiTree*
#include"queue.h"
#include"stack.h"
BiTree *tree;
int max(int a,int b)
{
return a>b?a:b;
}
BiTree *build()//使用先序遍历创建一棵树
{
char str;
str=getchar();
if(str=='#') return NULL;
BiTree *new_node=(BiTree*)malloc(sizeof(BiTree));
if(new_node==NULL)
{
printf("申请空间失败");
return NULL;
}
new_node->data=str;
new_node->lchild=build();
new_node->rchild=build();
return new_node;
}
void pre_recursion(BiTree *tree)//先序遍历tree
{
if(tree==NULL) return;
printf("%c",tree->data);
pre_recursion(tree->lchild);
pre_recursion(tree->rchild);
}
void mid_recursion(BiTree *tree)//中序遍历tree
{
if(tree==NULL) return;
mid_recursion(tree->lchild);
printf("%c",tree->data);
mid_recursion(tree->rchild);
}
void post_recursion(BiTree *tree)//后序遍历tree
{
if(tree==NULL) return;
post_recursion(tree->lchild);
post_recursion(tree->rchild);
printf("%c",tree->data);
}
int height(BiTree *tree)//统计二叉树的高度
{
if(tree==NULL) return 0;
return max(height(tree->lchild),height(tree->rchild))+1;
}
void cnt(BiTree *tree,int t[])
{
if(tree->lchild==tree->rchild&&tree->lchild==NULL) ++t[0];
else if(tree->rchild!=NULL&&tree->lchild!=NULL) ++t[2];
else ++t[1];
if(tree->lchild!=NULL) cnt(tree->lchild,t);
if(tree->rchild!=NULL) cnt(tree->rchild,t);
}
void Inorder(BiTree *root)//中序遍历
{
SeqStack stack;
InitStack(&stack);
BiTree *p=root;
while(p!=NULL||!Stack_IsEmpty(&stack))
{
if(p!=NULL)
{
Stack_Push(&stack,p);
p=p->lchild;
}
else
{
Stack_Pop(&stack,&p);
printf("%c",p->data);
p=p->rchild;
}
}
}
void Preorder(BiTree *root)//先序遍历
{
SeqStack stack;
InitStack(&stack);
BiTree *p=root;
while(p!=NULL||!Stack_IsEmpty(&stack))
{
if(p!=NULL)
{
printf("%c",p->data);
Stack_Push(&stack,p);
p=p->lchild;
}
else
{
Stack_Pop(&stack,&p);
p=p->rchild;
}
}
}
void Levelorder(BiTree *root)//层序遍历
{
SeqQueue queue;
InitQueue(&queue);
BiTree *p=root;
Queue_Push(&queue,root);
while(!Queue_IsEmpty(&queue))
{
Queue_Pop(&queue,&p);
if(p!=NULL)
{
printf("%c",p->data);
Queue_Push(&queue,p->lchild);
Queue_Push(&queue,p->rchild);
}
}
}
int menu()
{
printf("1.退出\n2.二叉树的先序/中序/后序递归遍历\n3.统计二叉树的高度\n4.统计各类结点的个数\n5.先序/中序非递归遍历\n6.层序遍历等运算\n");
int op;
scanf("%d",&op);
if(op==1) return 0;
else if(op==2)
{
printf("基于递归的先序遍历:");
pre_recursion(tree);
printf("\n基于递归的中序遍历:");
mid_recursion(tree);
printf("\n基于递归的后序遍历:");
post_recursion(tree);
printf("\n");
}
else if(op==3) printf("树的高度为:%d\n",height(tree));
else if(op==4)
{
int c[3];
memset(c,0,sizeof c);
cnt(tree,c);
printf("入度为0:%d\n入度为1:%d\n入度为2:%d\n",c[0],c[1],c[2]);
}
else if(op==5)
{
printf("基于非递归的先序遍历:");
Preorder(tree);
printf("\n基于非递归的中序遍历:");
Inorder(tree);
printf("\n");
}
else if(op==6)
{
printf("层序遍历:");
Levelorder(tree);
printf("\n");
}
return 1;
}
int main()
{
tree=build();
int v=1;
while(v) v=menu();
return 0;
}
2024-08-28 实验八：图的创建及遍历
//构建图的邻接矩阵、邻接表存储结构，实现图的深度优先搜索遍历、广度优先搜索遍历。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define QueueElementType int
#define maxsize 100
#include"queue.h"
#define MAX_VERTEX_NUM 20
#define INFNITY 32768
#define VertexData char
typedef enum{DG,DN,UDG,UDN}GraphKind;
//DG有向图，DN有向网，UDG无向图，UDN无向网
typedef char EertexData;
int visited[MAX_VERTEX_NUM];
typedef struct ArcNode
{
int adjvex;
int weight;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VertexNode
{
VertexData data;
ArcNode *firstarc;
}VertexNode;
typedef struct
{
VertexNode vertex[MAX_VERTEX_NUM];
int vexnum,arcnum;//图的顶点数，边数
GraphKind kind;
}AdjList;
int get_num(AdjList *graph,VertexData target)
{
for(int i=1;i<=graph->vexnum;++i)
{
if(graph->vertex[i].data==target)
return i;
}
return -1;
}
void build(AdjList *graph)
{
printf("请输入图的顶点数:");
scanf("%d",&(graph->vexnum));
printf("请输入图各个顶点的名称:(不要带有空格)");
for(int i=1;i<=graph->vexnum;++i)
{
char input;
do scanf("%c",&input);while(input=='\n');
graph->vertex[i].data=input;
graph->vertex[i].firstarc=NULL;
}
printf("输入边的数量:");
scanf("%d",&(graph->arcnum));
printf("输入各个顶点之间的关系(边a) (边b) (边权):\n");
for(int i=1;i<=graph->arcnum;++i)
{
char a,b;
int c;
scanf("\n%c %c %d",&a,&b,&c);
int a_num=get_num(graph,a);
int b_num=get_num(graph,b);
if(a_num==-1||b_num==-1)
{
printf("输入数据错误,建图失败\n");
return;
}
ArcNode *new_node=(ArcNode*)malloc(sizeof(ArcNode));
if (new_node == NULL)
{
printf("内存分配失败\n");
return;
}
new_node->nextarc=graph->vertex[a_num].firstarc;
graph->vertex[a_num].firstarc=new_node;
new_node->adjvex=b_num;
new_node->weight=c;
}
}
// 辅助函数：从指定顶点 v 开始进行深度优先搜索
void dfs(AdjList *graph, int v)
{
// 打印当前顶点并标记为已访问
printf("%c ", graph->vertex[v].data);
visited[v] = 1;
// 遍历当前顶点的邻接表
ArcNode *arc = graph->vertex[v].firstarc;
while (arc != NULL)
{
int adjVex = arc->adjvex;
if (!visited[adjVex]) dfs(graph, adjVex); // 递归访问相邻顶点
arc = arc->nextarc; // 继续下一个邻接顶点
}
}
void bfs(AdjList *graph, int start)
{
memset(visited,0,sizeof visited);
printf("广度优先搜索遍历:\n");
SeqQueue queue;
InitQueue(&queue);
Queue_Push(&queue, start);
visited[start] = 1;
while (!Queue_IsEmpty(&queue))
{
int v;
Queue_Pop(&queue, &v);
printf("%c ", graph->vertex[v].data);
for (ArcNode *p = graph->vertex[v].firstarc; p != NULL; p = p->nextarc)
{
if (!visited[p->adjvex])
{
Queue_Push(&queue, p->adjvex);
visited[p->adjvex] = 1;
}
}
}
printf("\n");
}
int main()
{
AdjList g;
build(&g);
memset(visited, 0, sizeof(visited));
printf("深度度优先搜索遍历：\n");
for (int i=1;i<=g.vexnum;++i)
if (!visited[i]) dfs(&g, i);
printf("\n");
bfs(&g,1);
return 0;
}
