西北电专大二电院_数据结构上机报告记录_第二次上机报告

 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 //
  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 }

  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 }