第二次上机报告
只要求提交了顺序串和顺序栈的基本操作的实现，这里把剩下两个也补充上去
顺序栈——进制转换
1. 问题描述
本程序基于栈功能实现一个进制转换程序。（用顺序栈完成此题）
InitStack()函数用于构造一个空栈；
StackEmpty()函数用于判断栈是不是空栈；
Push()函数实现将一个元素压入栈顶;
Pop()函数实现将栈顶的元素推出；
Coversion()函数实现进制转换；
main()函数为主函数：
要求：将十进制数转换为任意进制数。例如二，八，十六进制等。例如：将八进制数23，转换为2进制数10011
2.数据结构设计
如题，用顺序栈完成，顺序栈是操作受限的线性表，只能对栈顶操作，且为先进后出结构
3.算法设计
事实上由进制转换的算法可以看出，将一个十进制数一直除以要转换的进制，并将余数入栈，最后把栈中的数读出即为对应的进制数。
注意到输出的是字符串，要进行相应的ASCII码转换
1 //
2 // Created by Administrator on 2023/10/19/019.
3 //
4 /*
5 本程序基于栈功能实现一个进制转换程序。（用顺序栈完成此题）
6 InitStack()函数用于构造一个空栈；
7 StackEmpty()函数用于判断栈是不是空栈；
8 Push()函数实现将一个元素压入栈顶;
9 Pop()函数实现将栈顶的元素推出；
10 Conversion()函数实现进制转换；
11 main()函数为主函数：
12 要求：将十进制数转换为任意进制数。例如二，八，十六进制等。
13 例如：将八进制数23，转换为2进制数10111
14 */
15
16 #include <stdio.h>
17 #include <stdlib.h>
18
19 #define Maxsize 100
20
21 typedef struct
22 {
23 int data[Maxsize];
24 int Top;
25 }SeqStack;
26
27 void Init(SeqStack *S)
28 {
29 S->Top=-1;
30 }
31
32 int Push(SeqStack *S,int elem)
33 {
34 if(S->Top==Maxsize-1)
35 return 0;
36 else
37 {
38 S->Top++;
39 S->data[S->Top]=elem;
40 return 1;
41 }
42 }
43
44 int Pop(SeqStack *S,int *elem)
45 {
46 if(S->Top==-1)
47 return 0;
48 else
49 {
50 *elem=S->data[S->Top];
51 S->Top--;
52 return 1;
53 }
54 }
55
56 int StackEmpty(SeqStack *S)
57 {
58 if(S->Top==-1)
59 return 1;
60 else
61 return 0;
62 }
63
64 void Conversion(SeqStack *S,int n,int base)
65 {
66
67 int bit;//bit存储余数用
68 while (n!=0)//要转换的数一直往下除一直到0时
69 {
70 Push(S,n%base);//将余数存入栈，注意到嵌套函数调用Push传入的是指针名而不是再取地址，由于Conversion已经传入过了
71 n=n/base;//向下除；上面是转换进制的逻辑
72 }
73 while(!StackEmpty(S))
74 {
75 Pop(S,&bit);//将余数出栈，实现打印
76 if(bit>9)
77 printf("%c",bit+55);
78 else
79 printf("%c",bit+48);//涉及到ASCII码的知识
80 }
81 printf("\n");
82 }
83
84 int main()
85 {
86 SeqStack S;
87 Init(&S);//这里实际涉及到了一个传参的问题
88 /*
89 Init(&S);：这一行代码调用了 Init 函数，并传递了 S 的地址（&S 表示 S 的地址）作为参数。
90 这是因为 Init 函数期望接受一个指向 SeqStack 结构体的指针作为参数，以便在函数内部可以修改 S 的成员。
91 */
92 int num,base;
93 printf("请依次输入要转化的十进制数字和进制数：\n");
94 scanf("%d %d",&num,&base);
95 Conversion(&S,num,base);
96 return 0;
97 }
顺序串——一些基本操作
1. 问题描述
熟悉串的定义和基本运算的含义及实现：(用顺序串进行相关操作)
要求：子串测试、串联接测试、串替换测试
例如：S1=THIS IS A BOOK，S2=ESE ARE。（1） 找出S1中子串（测试当堂检测）（定点定长） （2） 联接S1和S2 （3） 用S2替换S1后半部分（如替换后为THIS ISESE ARE）
2.数据结构设计
如题，顺序串，一维数组即可，再加上一些对串的基本操作函数
3.算法设计
分别写三个函数实现以上功能即可。
如寻找子串是：判断传入的Pos和len是否符合规范，然后在len限制的循环里把主串Pos及以后的字符赋值给新数组即可；
实现连接是先获取两串长度（可以用strlen或者自己写一个），判断是否有长度溢出风险，然后找到串一的结束符，自增到下一个位置，把S2的赋值过去即可
4.源代码
1 //
2 // Created by Administrator on 2023/10/25/025.
3 //
4 //串是内容受限的字符串，要求是字符（包括空格）组成，同时基本操作是对串的整体或者子串进行操作；
5 //不过C中也提供了一定的操作库函数
6
7 #include <stdio.h>
8 #include <stdlib.h>
9 #include <string.h>
10 #define Maxsize 100
11
12 typedef char Seqstring[Maxsize];//typedef一个char类型的数组Seqstring
13
14 /*注意到其实有三种存储方式，一种是类似结构体那个线性顺序表的
15 * 写一个动态分配的顺序串存储
16 * typedef struct
17 * {
18 * char *ch;
19 * int length;
20 * }Hstring;
21 *
22 * Hstring S;
23 * S.ch=(char*)malloc(Maxsize*sizeof(char));
24 * S.length=0;//nalloc开辟一个堆空间
25 */
26 //有空把串的其他基本操作都写了
27
28
29 void StrCopy(Seqstring S1,Seqstring S2,int pos)//把S2的内容复制到S1中覆盖掉，从S1的pos位开始
30 {
31 int i=pos;
32 int j=0;
33 while(S2[j]!='\0')//循环遍历完S2
34 {
35 S1[i]=S2[j];
36 i++;
37 j++;
38 }
39 S1[i]='\0';//给S1加上结束值表示结束
40 puts(S1);
41 }
42
43 void StrConnection(Seqstring S1,Seqstring S2)//将S2连接在S1后面形成新的串1,对应strcat（）
44 {
45 //获取长度->判断溢出->找到要连接的S1尾巴->连接过去
46 int length1= strlen(S1);
47 int length2= strlen(S2);
48 if(length1+length2>Maxsize)
49 {
50 printf("ERROR");
51 return;
52 }
53 int i=0,j=0;
54 while(S1[i]!='\0')
55 i++;//一直自增，找到最后一位位置
56 while(S2[j]!='\0')
57 S1[i++]=S2[j++];
58 S1[i]='\0';
59 puts(S1);
60 }
61
62
63
64 void SubStr(Seqstring S,Seqstring Sub,int pos,int len)//求子串,从pos位置开始长度为len的子串,并把这段存到新的Sun中
65 {
66 //判断异常，看pos和len是否符合规范
67 int i;
68 int Length=strlen(S);
69 if(pos<0||pos>Length-1||len<0||len>Length-pos)
70 {
71 printf("ERROR");
72 return;
73 }
74 for(i=0;i<len;i++)
75 {
76 Sub[i]=S[pos+i];//或Sub[i]=S[pos+i],这样写是不对pos进行变动
77 }
78
79 Sub[i++]='\0';//输出用；为什么不加限制的puts输出会输出额外量？puts功能是将字符串输出到屏幕。输出时只有遇到 '\0' 也就是字符串结束标志符才会停止。
80 puts(Sub);
81 printf("\n");
82 }
83 //上面几个基本操作可以用库函数来替代
84
85
86
87 int main()
88 {
89 int pos , len ,pos2;
90 Seqstring strMain_1,strMain_2,str_PrintSub;//初始化
91
92 printf("请输入主串1:");
93 fgets(strMain_1,100,stdin);//scanf不能输入空格，gets函数能读取空格但是有风险
94 strMain_1[strcspn(strMain_1, "\n")] = '\0';
95 /* 这行代码的作用是将字符串 strMain_1 中第一个换行符之前的部分截断，并用空字符 \0 替换。具体解释如下：
96 strcspn(strMain_1, "\n") 函数会返回 strMain_1 中第一个出现换行符 \n 的位置，即换行符在字符串中的索引值。
97 然后，该索引值被传递给 strMain_1[strcspn(strMain_1, "\n")]，将对应下标位置的字符进行修改。
98 最后，= '\0' 表示将该位置处的字符赋值为空字符，起到截断字符串的效果。
99 换言之，在该操作后，原来的字符串 strMain_1 ，只保留了换行符之前的部分，把换行符换为结束符。
100 */
101
102 printf("输入pos和len:\n");
103 scanf("%d %d",&pos,&len);
104 printf("输出要主串1中查找的第pos位开始长度为len的子串：\n");
105 SubStr(strMain_1,str_PrintSub,pos,len);
106
107 getchar();
108 /*
109 这段代码中的问题是在使用fgets函数读取输入时，会将换行符'\n'也作为字符串的一部分存储起来。
110 当之后调用fgets函数读取strMain_2时，它会立即读取到输入缓冲区中的换行符，并将其作为空串结束符，导致无法正确输入第二串字符串。
111 可以加上一行getchar()语句来接收并丢弃换行符：
112 */
113 printf("请输入主串2:");
114 fgets(strMain_2,100,stdin);
115
116 printf("输出连接后的主串1：\n");
117 StrConnection(strMain_1,strMain_2);
118
119 printf("请输入要替换的数字序号：\n");
120 scanf("%d",&pos2);
121 printf("输出替换后的主串1：\n");
122 StrCopy(strMain_1,strMain_2,pos2);
123
124 return 0；
125
126 }
模式匹配：(用顺序串进行相关操作)
要求：实现在主串中找到子串的位置并返回
用原始模式匹配算法实现
朴素匹配的暴力穷举法，最直观的方法,,,
1 //
2 // Created by Administrator on 2023/10/25/025.
3 //
4 #include <stdio.h>
5 #include <string.h>
6
7 int searchSubstring(const char *mainString, const char *substring,int pos) {
8 int mainLen = strlen(mainString);
9 int subLen = strlen(substring);
10
11 for (int i = pos; i <= mainLen - subLen - pos; i++) {
12 int j;
13
14 // 逐个字符比较子串和主串中的对应部分
15 for (j = 0; j < subLen; j++) {
16 if (mainString[i + j] != substring[j]) {
17 break; // 一旦有字符不匹配，跳出内循环
18 }
19 }
20 /*这个算法的设计也是可以的；事实上这个看起来更容易理解和记忆
21 * 原来的设计是主串下标指针和匹配串下标指针同时移动，这里是用了双循环的模式，第一级循环固定主串指针且限制移动在pos到两串长度差之间(限制i移动)
22 * 这是利用了匹配要求主串中必须有一段长度完全相同的子串和匹配串相等
23 * 如主串长度5，匹配串长度4，相差1，如果pos设置为0,主串下标指针i从0自增到1这两次搜索中都失败了，那么i也没有继续自增的必要了，因为后面主串的子串长度必然小于匹配串
24 *第二级循环里实现主串和匹配串的逐个匹配，可以看出主串下标移动是i+j，也就是匹配串移动多少主串就移动多少，不匹配就跳出。
25 *
26 * */
27 // 如果内循环完全匹配子串，则返回子串在主串中的起始位置
28 if (j == subLen) {
29 return i;
30 }
31 }
32
33 return -1; // 没有找到子串，返回-1表示失败
34 }
35
36 //下面用课本的代码实现
37 int EXAMPLE_BF(const char *mainString,const char *subString,int pos)
38 {
39 int i=pos,j=1;//这里从主串的pos位置开始比较
40 int mainLen= strlen(mainString);
41 int subLen= strlen(subString);
42 while(i<=mainLen&&j<=subLen)//一级循环，两个下标指针都不能超出最大长度
43 {
44 if(mainString[i-1]==subString[j-1])//位序比数组下标多1
45 {
46 i++;
47 j++;
48 }
49 else
50 {
51 i=i-j+2;//下标指针重新初始化，主串下标指针要比上一次的后移一位（这里设置的j=1,画图看比较明显）
52 j=1;
53 }
54 }
55 if(j>subLen)//由于上面那个循环直到最后一个字符匹配成功后还会步进一次j，所以此时j是大于匹配串长的，这也表明匹配成功，返回主串下标匹配的初始位置即可
56 return i-subLen;
57 else
58 return -1;
59 }
60
61 //模式匹配用链串也可以实现，且比较好理解
62
63 int main() {
64 const char *mainString = "Hello, my_world! This is a test.";
65 const char *substring = "world";
66
67 int position = searchSubstring(mainString, substring,2);
68 int position_1 = EXAMPLE_BF(mainString,substring,2);
69
70 if (position != -1) {
71 printf("子串在主串中的位置是：%d\n", position);
72 } else {
73 printf("子串未找到\n");
74 }
75
76 if (position_1 != -1) {
77 printf("子串在主串中的位置是：%d\n", position);
78 } else {
79 printf("子串未找到\n");
80 }
81
82 return 0;
83 }
鸽子：链表的实现代码后续再补充
队列的相关操作，这里是链队列
initQueue()函数是用来初始化一个空的链队；
enQueue()函数用来向队列的队尾插入一个元素；
outQueue()函数用来从队首删除一个元素；
peekQueue()函数用来读取队首的元素；
emptyQueue()函数用来判断队列是否为空；
clearQueue()函数用来清除队列中的元素；
main()函数为主函数，
实现将一个数组插入到一个队列中，并对队列进行插入、删除和读取队首元素等基本操作。
1 //
2 // Created by Administrator on 2023/10/19/019.
3 //链队列看作是单链表，但是能尾进头出；可以看出存储结构和部分操作是相似的，当然其他也带有队列的特点
4 /* initQueue()函数是用来初始化一个空的链队；
5 enQueue()函数用来向队列的队尾插入一个元素；
6 outQueue()函数用来从队首删除一个元素；
7 peekQueue()函数用来读取队首的元素；
8 emptyQueue()函数用来判断队列是否为空；
9 clearQueue()函数用来清除队列中的元素；
10 main()函数为主函数，实现将一个数组插入到一个队列中，并对队列进行插入、删除和读取队首元素等基本操作。
11 */
12
13 #include <stdio.h>
14 #include <stdlib.h>
15
16 typedef struct node
17 {
18 int data;
19 struct Linklist *next;
20 }QueueNode;//和链表存储结构一样
21
22 typedef struct//和链栈一样新建一个结构体来存指向其的指针，作为“接口”
23 {
24 QueueNode *head,*tail;//如果这里写QueueNode head,tail的话要怎么传参？函数括号传参要求为Linknode的*Lq
25 }LinkQueue;
26
27 void Init(LinkQueue *Lq)//用头删法和尾插法
28 {
29
30 Lq->head=Lq->tail=(QueueNode*)malloc(sizeof(QueueNode));//初始化就要给队头队尾，（当然空队列情况下队头=队尾)开辟空间了；同时这一步就已经有尾指针指向头指针
31 Lq->head->next=NULL;//将头结点后继指向空，置空链队列; 注意到，我们设置链队是带有头结点的受限操作的单链表形式
32 //看起来如果只是上面这样写有个问题是如果不在后面补一个SETNULL就会使tail空;这是为什么？
33 }
34
35 void SetNULL(LinkQueue *Lq)
36 {
37 Lq->tail=Lq->head;//跟初始化一样，队尾指向队头，且队头后继指向空
38 Lq->head->next=NULL;
39 }
40
41 int Queue_Empty(LinkQueue *Lq)
42 {
43 if(Lq->head==Lq->tail&&Lq->head->next==NULL)
44 return 1;
45 else
46 return 0;
47 }
48
49 void enQueue(LinkQueue *Lq,int elem)
50 {
51 Lq->tail->next=(QueueNode*) malloc(sizeof(QueueNode));
52 Lq->tail=Lq->tail->next;
53 Lq->tail->data=elem;
54 Lq->tail->next=NULL;
55 }
56
57 void outQueue(LinkQueue *Lq,int *elem)
58 {
59 QueueNode *freenode;
60 if(Queue_Empty(Lq)==1)//传参进的是地址，函数里直接调用就行，不用再加&!
61 printf("ERROR");
62 else
63 {
64 freenode=Lq->head->next;//注意这里删除结点要考虑两个问题，一个是队在删除之前是不是已经就是空队，二是删除后是空队就需要置空，否则变为野指针了
65 if(freenode->next==NULL)
66 {
67 SetNULL(Lq);//传参进的是地址，这里直接调用就行，不用再加&!由于freenode已经指向Lq->head->next，对其操作无妨
68 }
69 else
70 Lq->head->next=freenode->next;//如果删除后队还是非空，就把Lq链接上
71 *elem=freenode->data;
72 free(freenode);
73
74 }
75 }
76
77 void peekQueue(LinkQueue *Lq,int *elem)
78 {
79 if(Queue_Empty(Lq)==1)
80 printf("ERROR");
81 else
82 {
83 *elem=Lq->head->next->data;
84 }
85 }
86
87 void clearQueue(LinkQueue *Lq)
88 {
89 if(Queue_Empty(Lq)==1)
90 printf("队列已空！");
91 else
92 {
93 while (Queue_Empty(Lq)==0)
94 {
95 QueueNode *freenode;
96 freenode=Lq->head->next;
97 if(freenode->next==NULL)
98 SetNULL(Lq);
99 else
100 {
101 Lq->head->next=freenode->next;
102 }
103 free(freenode);
104 }
105 }
106 }
107
108 void Print_FromheadTotail(LinkQueue *Lq)
109 {
110 if(Queue_Empty(Lq)==1)
111 printf("ERROR");
112 else
113 {
114 QueueNode *find;
115 find=Lq->head->next;
116 int i=1;
117 while(find!=NULL)//如果判断的是find->next!=NULL就会把最后一个省略掉！
118 {
119 printf("第%d个元素是%d\n",i,find->data);
120 find=find->next;
121 i++;
122 }
123 }
124 }
125
126 int main()
127 {
128 int num,num1,e,cnt=0;
129 printf("请输入任意个个整型数字填入数组：");
130 scanf("%d",&num);
131 int arr[num];
132 for(int i=0;i<num;i++)
133 {
134 scanf("%d",&e);
135 arr[i]=e;
136 }
137
138 LinkQueue Lq;
139 Init(&Lq);
140 //SetNULL(&Lq);注意到前面Linkquwuw lq开辟了一个空间，如果还在init里面开辟空间就会导致内存泄漏，原来指向空间的指针丢失了！所以需要后面setnull它；当然init改写后就不需要了
141 printf("正在将数组填入链队！\n");
142 while(cnt<num)
143 {
144 enQueue(&Lq,arr[cnt]);
145 cnt++;
146 }
147 peekQueue(&Lq,&e);
148 printf("现在队列的首元素是：%d\n",e);
149 printf("现在队列中的元素是：\n");
150 Print_FromheadTotail(&Lq);
151
152 printf("请输入任意个数字，现在连续从链队中删除输入个数的元素,并插入新元素!\n");
153 scanf("%d",&num1);
154 for(int j=0;j<num1;j++)
155 {
156 outQueue(&Lq,&e);
157 printf("删除的元素是%d,插入的元素:%d \n",e,j+1000);
158 /* scanf("%d",&d); */
159 e=j+1000;
160 enQueue(&Lq,e);
161 }
162 printf("现在队列中的元素是：\n");
163 Print_FromheadTotail(&Lq);
164
165 clearQueue(&Lq);
166 SetNULL(&Lq);
167 if(Queue_Empty(&Lq)==1)
168 printf("队列已经清空！");
169 return 0;
170
171 }
鸽子：写这个的时候还遇到了堆栈空间分配和内存溢出的问题，后续再进一步补充相关
标签：函数,上机,int,S1,printf,电专,next,Lq,电院 From： https://www.cnblogs.com/WCMS-XDU688/p/17793947.html