数据结构作业代码
顺序表基本操作
实现功能:增删查修序
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
//插入
int insert(int a[],int n,int index,int x)
{
if(index>MAX)
{
printf("数字插入位置错误
");
return ;
}
int i;
if(n==MAX)
{
printf("储存空间不足
");
}
for(i=n-1;i>index-2;i--)
{
a[i+1]=a[i];
}
a[index-1]=x;
n++;
return n;
}
//删除
void delet(int a[],int n,int index)
{
if(index>MAX)
{
printf("所需删除数字位置错误
");
return ;
}
int i;
for(i=index;i<n;i++)
{
a[i-1]=a[i];
}
n--;
return n;
}
//查找
int find(int a[],int n,int x)
{
int i;
for(i=0;i<n;i++)
{
if(a[i]==x)
{
printf("查找的数字位置为
");
return i+1;
}
}
return -1;
}
//修改
void modify(int a[],int index,int x)
{
a[index-1]=x;
}
//排序(降序)
void sort(int a[],int n)
{
int i,j;
int pos;
for(i=0;i<n;i++)
{
for(j=1;j<n-1;j++)
{
if(a[i]<a[j])
{
pos=a[j];
a[j]=a[i];
a[i]=pos;
}
}
}
}
//输出
void printarray(int a[],int n)
{
int i;
for(i=0;;i++)
{
if(i==n-1)
{
printf("%%d
",a[i]);
break;
}
printf("%%d ",a[i]);
}
}
int main()
{
int a[100],n,i;
printf("请输入数字个数
");
scanf("%%d",&n);
printf("请依次输入数字
");
for(i=0;i<n;i++)
{
scanf("%%d",&a[i]);
}
int index,x;
printf("请输入所要插入的数字位置和所要插入的数字
");
scanf("%%d %%d",&index,&x);
n=insert(a,n,index,x);
printarray(a,n);
printf("请输入要删除的数字位置
");
scanf("%%d",&index);
delet(a,n,index);
printarray(a,n);
printf("请输入需要查找的数字
");
scanf("%%d",&x);
i=find(a,index,x);
if(i==-1)
printf("输入的数字未查询到
");
else printf("%%d",i);
printf("进行完所有操作数字将进行排序并输出,结果如下:
");
sort(a,n);
printarray(a,n);
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
快速排序
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int mod=1000000007 , N = 1e5 + 10;
const double eps=1e-8;
int a[N];
void quick_sort(int q[] , int l , int r)
{
if(l >= r) return ;
int i = l - 1 , j = r + 1 , x = q[l + r >> 1];
while(i < j)
{
do i ++ ; while(q[i] < x);
do j -- ; while(q[j] > x);
if(i < j) swap(a[i] , a[j]);
}
quick_sort(q , l , j);
quick_sort(q , j + 1 , r);
}
//读取数据
void file(int n)
{
int i;
FILE *fw=fopen("1000.txt","r");
for(i=0;i<n;i++)
{
fscanf(fw,"%%d",&a[i]);//读取文件中的数据,遇到空格和换行停止读。
}
fclose(fw);
}
int main()
{
//time_t c_start, t_start, c_end, t_end;
int i,n;
cin>>n; //输入数据量
file(n);
//for(i = 0 ; i < n ; i ++ ) cout<<a[i]<<" ";
/*c_start = clock(); //!< 单位为ms
t_start = time(NULL); //!< 单位为s*/
quick_sort(a,0,n-1);
for(int i = 0 ; i < n ; i ++ ) cout<<a[i]<<" ";
/*c_end = clock();
t_end = time(NULL);
//!<difftime(time_t, time_t)返回两个time_t变量间的时间间隔,即时间差
printf("The pause used %%f ms by clock()
",difftime(c_end,c_start));
printf("The pause used %%f s by time()
",difftime(t_end,t_start));*/
system("pause");
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
随机数生成代码:
#include <bits/stdc++.h>
#define fi first
#define se second
#define mkp make_pair
#define lowbit(x) (x & (-x))
#define sz(x) (int)(x).size()
#define all(a) a.begin() , a.end()
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define pre(i, b, a) for (int i = (b); i >= (a); --i)
using namespace std;
int read() {int x = 0, w = 1;char ch = 0;while (ch < '0' || ch > '9') { if (ch == '-') w = -1;ch = getchar();}while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0');ch = getchar(); }return x * w;}
typedef long long LL;
typedef pair<int , int > PII;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int dx[4] = {1 , 0 , -1 , 0} , dy[4] = {0 , 1 , 0 , -1};
LL get(LL n)
{
return rand() %% n;
}
int main()
{
srand(time(0));
FILE *fp = fopen("doc.txt" , "w");
LL n;scanf("%%lld" , &n);
LL t = n + 1;
for (int i = 0;i < n;i ++)
{
fprintf(fp , "%%lld " , get(t));
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
单链表的基本操作
/*
Project: single linkeed list (数据结构 单链表)
Date: 2021-10-7 09:26:57
Author: Frank Wang
InitList(LinkList &L) 参数:单链表L 功能:初始化 时间复杂度 O(1)
ListLength(LinkList L) 参数:单链表L 功能:获得单链表长度 时间复杂度O(n)
ListInsert(LinkList &L,int i,ElemType e)
ListDelete(LinkList &L,int i) 参数:单链表L,位置i 功能:删除位置i元素 时间复杂度O(n)[加入了查找]
若已知p指针指向的删除 最好是O(1),因为可以与后继结点交换数据域,然后删除后继结点。
最坏是O(n),即从头查找p之前的结点,然后删除p所指结点
LocateElem(LinkList L,ElemType e) 参数:单链表L,元素e 功能:查找第一个等于e的元素,返回指针 时间复杂度O(n)
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
#define Status int
#define ElemType int
//单链表结点数据结构
typedef struct LNode
{
ElemType data;//数据域
struct LNode *next;//指针域
}LNode,*LinkList;
//**************************基本操作函数***************************//
//初始化函数
Status InitList(LinkList &L)
{
L = new LNode;//生成头结点 这样删除等操作就不必分第一个结点和其他了
L->next = NULL;
return 1;
}
//获取单链表长度 头结点无数据,不算
int ListLength(LinkList L)
{
LinkList p=L;int sum=0;
while(p)
{
sum++;
p=p->next;
}
return sum-1;//去除头结点
}
//前插
bool ListInsert_A(LinkList &L,int i,ElemType e)
{
LNode* s;LinkList p=L;int j=0;
while(p&&(j<i-1))//j指到i-1位置或者p已经到最后时跳出
{
p=p->next;
++j;
}
if(!p||j>i-1)//i<1或者i>ListLength(L)+1时,插入位置无效 不调用ListLength,提高效率
{
printf("插入位置无效!!!
");
return false;
}
s=new LNode;
s->data=e;
s->next=p->next;
p->next=s;
return true;
}
//后插
bool ListInsert_B(LinkList &L,int i,ElemType e)
{
LNode* s,* r;LinkList p=L;int j=0;
while(p&&(j<i-1))//j指到i-1位置或者p已经到最后时跳出
{
p=p->next;
++j;
}
if(!p||j>i-1)//i<1或者i>ListLength(L)+1时,插入位置无效 不调用ListLength,提高效率
{
printf("插入位置无效!!!
");
return false;
}
r=p;
s=new LNode;
s->data=e;
s->next=r->next;
r->next=s;
}
//删除函数 删除位置i的结点 即删除i-1之后的结点
bool ListDelete(LinkList &L,int i)
{
LNode* s;LinkList p=L;int j=0;
LinkList q;
while(p&&(j<i-1))//j指到i-1位置
{
p=p->next;
++j;
}
if(!(p->next)||j>i-1)//i<1或者i>ListLength(L)时,删除位置无效
{
printf("删除位置无效!!!
");
return false;
}
q=p->next;
p->next=q->next;
free(q);//释放空间
return true;
}
//查找函数 按值查找 查找第一个等于e的结点 成功返回该结点指针,否则返回NULL
LNode *LocateElem(LinkList L,ElemType e)
{
LNode *p=L;
while(p&&(p->data!=e))
{
p=p->next;
}
return p;
}
//**************************功能实现函数**************************//
//遍历输出函数
void PrintList(LinkList L)
{
LinkList p=L->next;//跳过头结点
if(ListLength(L))
{
printf("当前单链表所有元素:");
while(p)
{
printf("%%d ",p->data);
p=p->next;
}
printf("
");
}
else
{
printf("当前单链表已空!
");
}
}
//插入功能函数 调用ListInsert插入
void Insert_A(LinkList &L)
{
int place;ElemType e;bool flag;
printf("请输入要插入的位置(从1开始)及元素:
");
scanf("%%d%%d",&place,&e);
flag=ListInsert_A(L,place,e);
if(flag)
{
printf("插入成功!!!
");
PrintList(L);
}
}
//插入功能函数 调用ListInsert插入
void Insert_B(LinkList &L)
{
int place;ElemType e;bool flag;
printf("请输入要插入的位置(从1开始)及元素:
");
scanf("%%d%%d",&place,&e);
flag=ListInsert_B(L,place,e);
if(flag)
{
printf("插入成功!!!
");
PrintList(L);
}
}
//删除功能函数 调用ListDelete删除
void Delete(LinkList L)
{
int place;bool flag;
printf("请输入要删除的位置(从1开始):
");
scanf("%%d",&place);
flag=ListDelete(L,place);
if(flag)
{
printf("删除成功!!!
");
PrintList(L);
}
}
//查找功能函数 调用LocateElem查找
void Search(LinkList L)
{
ElemType e;LNode *q;
printf("请输入要查找的值:
");
scanf("%%d",&e);
q=LocateElem(L,e);
if(q)
{
printf("找到该元素!
");
}
else
printf("未找到该元素!
");
}
//菜单
void menu()
{
printf("********1.前插 2.删除*********
");
printf("********3.查找 4.输出*********
");
printf("********5.后插 6.退出*********
");
}
//主函数
int main()
{
LinkList L;int choice;
InitList(L);
while(1)
{
menu();
printf("请输入菜单序号:
");
scanf("%%d",&choice);
if(choice==5) break;
switch(choice)
{
case 1:Insert_A(L);break;
case 2:Delete(L);break;
case 3:Search(L);break;
case 4:PrintList(L);break;
case 6:break;
case 5:Insert_B(L);break;
default:printf("输入错误!!!
");
}
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
单链表实现前插后插
#include<stdio.h>
#include <stdlib.h>
/*
01 构建链表
02 初始化链表 注意头节点 直接赋值
03 输出链表
*/
typedef struct stu{
int num;
float score;
struct stu *next;
}Node,*Link;
// typedef struct stu Node;
//typedef Node *Link;
//前插法
void F(Link head)
{
Link New;
New=new Node;
New->next=NULL;
New = (Link) malloc (sizeof(Node));
printf("num:");
scanf("%%d",&New->num);
printf("score:");
scanf("%%f", &New->score);
New->next=head->next;
head->next=New;
}
//后插法
void B(Link head)
{
Link New;
Link r;
New=(Link)malloc(sizeof(Node));
printf("num:");
scanf("%%d",&New->num);
printf("score:");
scanf("%%f", &New->score);
r=head;
while(1)
{
if(r->next==NULL)
break;
r=r->next;
}
New->next=NULL;
r->next=New;
}
//输出
//Link p(Link head)
//{
// Link r;
// r=head;
// while(r->next!=NULL)
// {
// printf("[%%d,%%d]",r->num,r->score);
// r=r->next;
// }
//}
Link p(Link head)
{
Link pointer; //节点声明
pointer = head->next; //pointer指针设为首节点
while(pointer!= NULL)
{
printf("[%%d, %%.1f]", pointer->num, pointer->score);
pointer = pointer->next;
}
printf("
");
}
/**********************
* 释放链表
*********************/
Link free_list(Link head)
{
Link pointer;
while(head != NULL)
{
pointer = head;
head = head->next;
free(pointer);
}
}
int main(){
int n,i,choice;
Link head;
head=new Node;
head->next=NULL;
printf("请输入插入数据量:");
scanf("%%d",&n);
for(i=0;i<n;i++)
{
printf("请选择插入方式
");
printf("1.前插 2.后插
");
scanf("%%d",&choice);
switch(choice)
{
case 1:F(head);break;
case 2:B(head);break;
}
}
p(head);
free_list(head);
system("pause");
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
双向循环链表的基本操作
/*
Project: single linkeed list (数据结构 单链表)
Date: 2021-10-7 09:26:57
Author: Frank Wang
InitList(LinkList &L) 参数:单链表L 功能:初始化 时间复杂度 O(1)
ListLength(LinkList L) 参数:单链表L 功能:获得单链表长度 时间复杂度O(n)
ListInsert(LinkList &L,int i,ElemType e)
ListDelete(LinkList &L,int i) 参数:单链表L,位置i 功能:删除位置i元素 时间复杂度O(n)[加入了查找]
若已知p指针指向的删除 最好是O(1),因为可以与后继结点交换数据域,然后删除后继结点。
最坏是O(n),即从头查找p之前的结点,然后删除p所指结点
LocateElem(LinkList L,ElemType e) 参数:单链表L,元素e 功能:查找第一个等于e的元素,返回指针 时间复杂度O(n)
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
#define Status int
#define ElemType int
//单链表结点数据结构
typedef struct LNode
{
ElemType data;//数据域
struct LNode *next;//指针域
struct LNode *pr;//指针域
}LNode,*LinkList;
//**************************基本操作函数***************************//
//初始化函数
Status InitList(LinkList &L)
{
L = new LNode;//生成头结点 这样删除等操作就不必分第一个结点和其他了
L->next = NULL;
L->pr=NULL;
return 1;
}
//获取单链表长度 头结点无数据,不算
int ListLength(LinkList L)
{
LinkList p=L;int sum=0;
while(p)
{
sum++;
p=p->next;
}
return sum-1;//去除头结点
}
//输出长度
void ListLeng(LinkList L)
{
LinkList p=L;int sum=0;
while(p)
{
sum++;
p=p->next;
}
sum--;
printf("%%d",sum);
}
//后插
bool ListInsert_A(LinkList L,int i,ElemType e)
{
LNode* s;LinkList p=L;int j=0;
while(p&&(j<i-1))//j指到i-1位置或者p已经到最后时跳出
{
p=p->next;
++j;
}
if(!p||j>i-1)//i<1或者i>ListLength(L)+1时,插入位置无效 不调用ListLength,提高效率
{
printf("插入位置无效!!!
");
return false;
}
s=new LNode;
s->data=e;
s->next=p->next;
p->next=s;
if((s->next)!=NULL)
s->next->pr=s;
s->pr=p;
return true;
}
//前插
bool ListInsert_B(LinkList L,int i,ElemType e)
{
LNode* s,* r;LinkList p=L;int j=0;
while(p&&(j<i-1))//j指到i-1位置或者p已经到最后时跳出
{
p=p->next;
++j;
}
if(!p||j>i-1)//i<1或者i>ListLength(L)+1时,插入位置无效 不调用ListLength,提高效率
{
printf("插入位置无效!!!
");
return false;
}
r=p;
s=new LNode;
s->data=e;
s->next=r->next;
r->next=s;
if((s->next)!=NULL)
s->next->pr=s;
s->pr=r;
return true;
}
//删除函数 删除位置i的结点 即删除i-1之后的结点
bool ListDelete(LinkList L,int i)
{
LNode* s;LinkList p=L;int j=0;
LinkList q;
while(p&&(j<i-1))//j指到i-1位置
{
p=p->next;
++j;
}
if(!(p->next)||j>i-1)//i<1或者i>ListLength(L)时,删除位置无效
{
printf("删除位置无效!!!
");
return false;
}
q=p->next;
p->next=q->next;
p->next->pr=p;
free(q);//释放空间
return true;
}
//查找函数 按值查找 查找第一个等于e的结点 成功返回该结点指针,否则返回NULL
LNode *LocateElem(LinkList L,ElemType e)
{
LNode *p=L;
while(p&&(p->data!=e))
{
p=p->next;
}
return p;
}
//**************************功能实现函数**************************//
//遍历输出函数
void PrintList(LinkList L)
{
LinkList p=L->next;//跳过头结点
if(ListLength(L))
{
printf("当前单链表所有元素:");
while(p)
{
printf("%%d ",p->data);
p=p->next;
}
printf("
");
}
else
{
printf("当前单链表已空!
");
}
}
//插入功能函数 调用ListInsert插入
void Insert_A(LinkList &L)
{
int place;ElemType e;bool flag;
printf("请输入要插入的位置(从1开始)及元素:
");
scanf("%%d%%d",&place,&e);
flag=ListInsert_A(L,place,e);
if(flag)
{
printf("插入成功!!!
");
PrintList(L);
}
}
//插入功能函数 调用ListInsert插入
void Insert_B(LinkList &L)
{
int place;ElemType e;bool flag;
printf("请输入要插入的位置(从1开始)及元素:
");
scanf("%%d%%d",&place,&e);
flag=ListInsert_B(L,place,e);
if(flag)
{
printf("插入成功!!!
");
PrintList(L);
}
}
//删除功能函数 调用ListDelete删除
void Delete(LinkList L)
{
int place;bool flag;
printf("请输入要删除的位置(从1开始):
");
scanf("%%d",&place);
flag=ListDelete(L,place);
if(flag)
{
printf("删除成功!!!
");
PrintList(L);
}
}
//查找功能函数 调用LocateElem查找
void Search(LinkList L)
{
ElemType e;LNode *q;
printf("请输入要查找的值:
");
scanf("%%d",&e);
q=LocateElem(L,e);
if(q)
{
printf("找到该元素!
");
}
else
printf("未找到该元素!
");
}
//sort
void sort(LinkList head)
{
if (NULL == head)
{
return;
}
else
{
int flag = 0;
LinkList pTailNode = NULL;
while (pTailNode != head)
{
LinkList pPreNode = head;
while (pPreNode->next != pTailNode)
{
LinkList pCurNode = pPreNode->next;
if (pPreNode->data > pCurNode->data)
{
ElemType dTemp = pPreNode->data;
pPreNode->data = pCurNode->data;
pCurNode->data = dTemp;
flag = 1;
}
pPreNode = pPreNode->next;
}
if (0 == flag)
{
break;
}
pTailNode = pPreNode;
}
}
}
//头插尾
void New_1(LinkList L)
{
LinkList p=L->next;
LinkList q=p->next;
L->next=p->next;
while(q->next) q=q->next;
q->next=p;
p->pr=q;
p->next->pr=NULL;
p->next=NULL;
PrintList(L);
}
// 逆序输出
void New_2(LinkList L)
{
LinkList p=L;
while(p->next!=NULL)
{
p=p->next;
}
printf("当前单链表所有元素:");
while(p->pr!=NULL)
{
printf("%%d ",p->data);
p=p->pr;
}
printf("
");
}
//菜单
void menu()
{
printf("********1.前插 2.删除*********
");
printf("********3.查找 4.输出*********
");
printf("********5.后插 6.排序*********
");
printf("********7.头换尾 8.输出结点数***
");
printf("********9.逆序输出10.退出*********
");
}
//主函数
int main()
{
LinkList L;int choice;
InitList(L);
while(1)
{
menu();
printf("请输入菜单序号:
");
scanf("%%d",&choice);
if(choice==10) break;
switch(choice)
{
case 1:Insert_B(L);break;
case 5:Insert_A(L);break;
case 2:Delete(L);break;
case 3:Search(L);break;
case 4:PrintList(L);break;
case 6:sort(L->next);break;
case 7:New_1(L);break;
case 8:ListLength(L);break;
case 9:New_2(L);break;
case 10:break;
default:printf("输入错误!!!
");
}
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
- 255
- 256
- 257
- 258
- 259
- 260
- 261
- 262
- 263
- 264
- 265
- 266
- 267
- 268
- 269
- 270
- 271
- 272
- 273
- 274
- 275
- 276
- 277
- 278
- 279
- 280
- 281
- 282
- 283
- 284
- 285
- 286
- 287
- 288
- 289
- 290
- 291
- 292
- 293
- 294
- 295
- 296
- 297
- 298
- 299
- 300
- 301
- 302
- 303
- 304
- 305
- 306
- 307
- 308
- 309
- 310
栈的使用(斐波+回文+进制转换)
#include<iostream>
#include<time.h>
#include<algorithm>
using namespace std;
typedef long long ll;
ll power(int a,int j);
int k=0;
typedef struct
{
char *base;
char *top;
int max;
} stack;
//顺序栈初始化
void init(stack *s)
{
s->base=new char[100];
s->top=s->base;
s->max=100;
}
//入栈
void push(stack &s,char e)
{
if(s.top-s.base==s.max)
{
puts("栈满");
return ;
}
*s.top=e;
s.top++;
}
//出栈
void pop(stack &s,char &e)
{
if(s.top==s.base)
{
puts("栈空");
return ;
}
s.top--;
e=*s.top;
}
int a(int n)
{
if(n==1) return n;
else return n*a(n-1);
}
long feibo(int n)
{
int i=1,j=1;
if(n==1||n==2) return 1;
else{
return feibo(n-1)+feibo(n-2);
}
}
void feibo_2(int n)
{
long f1=1,f2=1,f3;
int i;
if(n==1||n==2) printf("1 ");
else {
for(i=3;i<=n;i++)
{
f3=f1+f2;
f1=f2,f2=f3;
}
cout<<f3<<" ";
}
}
//斐波那契数列递归与非递归耗时对比
void first()
{
int n;
long a;
scanf("%%d",&n);
int c_start = clock();
a=feibo(n);
int c_end = clock();
int c_start_1 = clock();
feibo_2(n);
int c_end_1 = clock();
cout<<a;
cout<<"【time1:"<<c_end-c_start<<"ms time2:"<<c_end_1-c_start_1<<"ms】"<<"
";
}
//判断回文数
void second()
{
cout<<"输入一个字符串:";
string a;
cin>>a;
stack s;
init(&s);
int len=a.length();
for(int i=0;i<len/2;i++)
{
push(s,a[i]);
}
// 判断数组奇偶性
int start; // 用于记录数组中的字符与栈中字符比较的起始位置
// 若数组为偶数
if (len %% 2 == 0) {
start = len/ 2;
}
// 若数组为奇数
else {
start = len / 2 + 1;
}
char c;
bool flag=true;
for(int i=start;i<len;i++)
{
pop(s,c);
if(c!=a[i]){
flag=false;
//break;
}
}
if(flag) cout<<"YES";
else cout<<"NO";
}
//进制转换
void third()
{
cout<<"请输入一个数:";
int a,b,n,j=0;
ll sum=0;
cin>>n;
printf("需要将这个数由什么进制转换为什么进制?:
");
cin>>a>>b;
while(n)
{
if(j==0) sum+=n%%10;
else sum+=n%%10*power(a,j);
j++;
n/=10;
}
stack s;
init(&s);
do{
int t=sum%%b;
if(t>=0&&t<=9) push(s,(t+'0'));
else push(s,(t-10+'a'));
sum/=b;
}while(sum!=0);
//reverse(ans.begin(),ans.end());
puts("转换后:");
char c;
while(s.top!=s.base)
{
pop(s,c);
cout<<c;
}
cout<"
";
}
ll power(int a,int j)
{
ll sum=1;
while(j)
{
sum*=a;
j--;
}
}
//四则运算
//void forth()
//{
//
//}
int main()
{
while(1){
int a;
cout<<"
想玩什么?
";
cout<<"1.对比斐波那契数列递归非递归耗时
" ;
cout<<"2.回文数判断(栈)
";
cout<<"3.进制转换(栈)
" ;
//cout<<"4.四则运算(栈)
" ;
cout<<"5.退出
";
cout<<"请输入操作编号!";
cin>>a;
switch (a){
case 1:first();break;
case 2:second();break;
case 3:third();break;
//case 4:forth();break;
case 5: break;
}
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
大数计算
#include<stdio.h>
#define N 500
//最多输出500位
void full(int n1[N], int n2[N]) //用于数组的赋值 把n2赋值给n1
{
for (int i = 0; i < N; i++)
{
n1[i] = n2[i];
}
}
int main()
{
int n = 0;
while (scanf("%%d", &n) && n) //输入项数并且为0时结束
{
int t1[N] = { 0 };
int t2[N] = { 0 };
int sum[N] = { 0 };
int temp[N] = { 0 }; //空数组,用于清零数组的
t1[0] = t2[0] = 1;
for (int i = 2; i < n; i++)
{
//大数相加
for (int k = 0; k < N; ++k)
{
sum[k] += t1[k] + t2[k];
if (sum[k] > 9)
{
sum[k + 1]++;
sum[k] -= 10;
}
}
full(t1, t2); //t2给t1
full(t2, sum); //sum 给t2
full(sum, temp); //再把sum清零
}
//输出
for (int i = N-1;; i--)
{
if (t2[i] != 0)
{
for (int k = i; k >= 0; k--)
printf("%%d", t2[k]);
printf("
");
break;
}
}
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
数组栈的基本操作
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXSIZE 100
using namespace std;
typedef int SElemType;
typedef struct
{
int *base;
int *top;
int stacksize;
}stack;//top始终指向栈顶元素的上一个位置
stack S;//栈S
int e;
void menu(); //菜单
bool Init_stack(stack &S);//初始化栈
void Push(stack &S);//入栈
void Pop(stack &S, int &e);//出栈
void Get_top(stack S);//输出栈顶元素
void Printf_stack(stack S);//打印栈
void menu()
{
puts("****1.向栈顶插入一个数 2.将栈顶元素弹出 ****");
puts("****3.输出栈顶元素 4.打印栈内所有元素****");
puts("****5.退出 ****");
int op;
cin >> op;
switch(op)
{
case 1:Push(S);break;
case 2:Pop(S, e);break;
case 3:Get_top(S);break;
case 4:Printf_stack(S);break;
case 5: return;
}
}
bool init(stack &S)//栈的初始化;
{
S.base = new int[MAXSIZE];
//if(!S.base) exit(OVERFLOW);
S.top = S.base;
S.stacksize = MAXSIZE;
return true;
}
//元素入栈
void Push(stack &S)
{
puts("请输入要入栈的元素:");
cin >> e;
if(S.top - S.base == S.stacksize)
{
puts("栈内空间不足!");
return ;
}
*S.top = e;
S.top ++;
menu();
}
//元素出栈
void Pop(stack &S, int &e)
{
if(S.top == S.base)
{
puts("栈已空!");
return ;
}
S.top --;
e = *S.top;
menu();
}
//栈顶元素的 获取
void Get_top(stack S)
{
if(S.top == S.base)
{
puts("栈内无元素!");
return ;
}
cout << *(S.top - 1);
menu();
return;
}
//栈的遍历
void Printf_stack(stack S)
{
cout << "栈底: " ;
int *p = S.base;
while(p != S.top)
{
cout << *p << " ";
p ++;
}
cout << endl;
puts("栈内元素输出完毕!");
menu();
}
int main()
{
init(S);//栈初始化
menu();
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
链表栈基本操作
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXSIZE 100
using namespace std;
typedef int SElemType;
typedef struct
{
int *base;
int *top;
int stacksize;
}stack;//top始终指向栈顶元素的上一个位置
stack S;//栈S
int e;
void menu(); //菜单
bool Init_stack(stack &S);//初始化栈
void Push(stack &S);//入栈
void Pop(stack &S, int &e);//出栈
void Get_top(stack S);//输出栈顶元素
void Printf_stack(stack S);//打印栈
void menu()
{
puts("****1.向栈顶插入一个数 2.将栈顶元素弹出 ****");
puts("****3.输出栈顶元素 4.打印栈内所有元素****");
puts("****5.退出 ****");
int op;
cin >> op;
switch(op)
{
case 1:Push(S);break;
case 2:Pop(S, e);break;
case 3:Get_top(S);break;
case 4:Printf_stack(S);break;
case 5: return;
}
}
bool init(stack &S)//栈的初始化;
{
S.base = new int[MAXSIZE];
//if(!S.base) exit(OVERFLOW);
S.top = S.base;
S.stacksize = MAXSIZE;
return true;
}
//元素入栈
void Push(stack &S)
{
puts("请输入要入栈的元素:");
cin >> e;
if(S.top - S.base == S.stacksize)
{
puts("栈内空间不足!");
return ;
}
*S.top = e;
S.top ++;
menu();
}
//元素出栈
void Pop(stack &S, int &e)
{
if(S.top == S.base)
{
puts("栈已空!");
return ;
}
S.top --;
e = *S.top;
menu();
}
//栈顶元素的 获取
void Get_top(stack S)
{
if(S.top == S.base)
{
puts("栈内无元素!");
return ;
}
cout << *(S.top - 1);
menu();
return;
}
//栈的遍历
void Printf_stack(stack S)
{
cout << "栈底: " ;
int *p = S.base;
while(p != S.top)
{
cout << *p << " ";
p ++;
}
cout << endl;
puts("栈内元素输出完毕!");
menu();
}
int main()
{
init(S);//栈初始化
menu();
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
队列(数组基本操作)
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
#define MAXSIZE 100
// 定义顺序队列结构体
typedef struct{
int *base; // 队列首地址
int front; // 队列头下标
int rear; // 队列尾下标
}Queue;
//队列初始化
void initqueue(Queue &q)
{
q.base=new int[MAXSIZE];
q.front=q.rear=0;
}
//入队
void QueuePush(Queue &q)
{
if((q.rear+1)%%MAXSIZE==q.front)
{
printf("队列已满
");
return ;
}
int e;
printf("请输入需要存储的数据:
");
scanf("%%d",&e);
q.base[q.rear]=e;
q.rear=(q.rear+1)%%MAXSIZE;
cout<<"完成
";
}
//遍历输出
void Queueprint(Queue &q)
{
int p=q.front,n=q.front;
cout<<"队列如下:
";
while(n!=q.rear)
{
printf("%%d ",q.base[p]);
p=(p+1)%%MAXSIZE;
n++;
}
}
// 出队
void QueuePop(Queue &q)
{
if(q.rear==q.front)
{
printf("队列已空
");
return ;
}
q.front=(q.front+1)%%MAXSIZE;
cout<<"完成";
}
//队列长度
void Queuelenth(Queue &q)
{
int a;
cout<<"队列长度";
a=(q.rear-q.front+MAXSIZE)%%MAXSIZE;
cout<<a;
}
//输出头元素
void Queuehead(Queue &q)
{
cout<<"头元素为";
cout<<q.base[q.front];
}
int main()
{
Queue q;
initqueue(q);
int i;
while(1)
{
printf("********1.插入 2.遍历*********
");
printf("********3.删除 4.输出头元素*********
");
printf("********5.输出队列长度 *********
");
printf("请输入操作:
");
scanf("%%d",&i);
switch(i)
{
case 1:QueuePush(q);break;
case 2:Queueprint(q);break;
case 3:QueuePop(q);break;
case 4:Queuehead(q);break;
case 5:Queuelenth(q);break;
}
printf("
");
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
队列(链式基本操作)
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
// 队列的节点
struct Node
{
int data;
struct Node* next;
};
// 队首队尾指针
struct Queue
{
struct Node* front;
struct Node* rear;
int size;
};
void QueueInit(struct Queue* queue)
{
queue->front = NULL;
queue->rear = NULL;
queue->size = 0;
}
//判断
int QueueEmpty(struct Queue* queue)
{
return (queue->size == 0);
}
//入队
void QueuePush(struct Queue* queue)
{
struct Node* node;
node = (struct Node*)malloc(sizeof(struct Node));
int data;
printf("请输入需要存储的数据:
");
scanf("%%d",&data);
node->data = data;
node->next = NULL;
if(QueueEmpty(queue))
{
queue->front = node;
queue->rear = node;
}
else
{
queue->rear->next = node;
queue->rear = node;
}
++queue->size;
}
//出队
int QueuePop(struct Queue* queue)
{
if (QueueEmpty(queue))
{
printf("队列已空
");
return 0;
}
struct Node* tmp = queue->front;
queue->front = queue->front->next;
free(tmp);
--queue->size;
printf("删除完成
");
return 1;
}
//销毁
void QueueDestroy(struct Queue* queue)
{
struct Node* tmp;
while(queue->front)
{
tmp = queue->front;
queue->front = queue->front->next;
free(tmp);
}
}
//遍历 输出
void Queueprint(struct Queue* queue)
{
int a=queue->size;
struct Node* tmp;
tmp=queue->front;
while(a)
{
printf("%%d ",tmp->data);
tmp=tmp->next;
--a;
}
}
//头元素
int Queuehead(struct Queue* queue)
{
int a;
if(queue->size==0) return 0;
printf("头元素为");
a=queue->front->data;
printf("%%d",a);
}
//输出长度
void Queuelenth(struct Queue* queue)
{
printf("长度");
printf("%%d",queue->size);
}
int main(void)
{
struct Queue queue;
QueueInit(&queue);
int i;
while(1){
printf("********1.插入 2.遍历*********
");
printf("********3.删除 4.输出头元素*********
");
printf("********5.输出队列长度 *********
");
printf("请输入操作:
");
scanf("%%d",&i);
switch(i)
{
case 1:QueuePush(&queue);break;
case 2:Queueprint(&queue);break;
case 3:QueuePop(&queue);break;
case 4:Queuehead(& queue);break;
case 5:Queuelenth(& queue);break;
}
printf("
");
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
约瑟夫环四种实现方式
1.数组
/*
有n个人围城一圈,按顺序编号,从第一个人开始报数,从1报到m,凡报到m的人退出圈子,
然后接着报数,问最后留下来的是原来的第几号的那位?
*/
//数组
//用长度为n的数组存储人的编号,退出的人编号置为0,当n-1个人都退出后,剩下的那个编号不为0的人就是要找的人。
#include <stdio.h>
#include <malloc.h>
void left_num(int* a,int n,int m) {
int out = n,count = 0,i = 0; //out为剩下的人数,count为报的数,i为目前报到第几个人
int *p = a;
int num = 0;
for(num = 0;num < n;num++) {
*(a+num) = num+1;
} //为n个人编号1-n
while (out>15) {
if (*(p+i) != 0) {
count ++; //不等于0才报数+!
if (count == m) {
count = 0;
*(p+i) = 0;
out--; //人数-1,且内容置0,报数置0
printf("%%d
",i+1);
}
}
i++;
if (i == n) {
i = 0; //到队尾重头开始
}
}
//输出剩下的人
for (num = 0; num < n; num++) {
if (*(a+num) != 0) {
printf("left num:%%d
",*(a+num));
}
}
}
int main()
{
int m,n;
int a[50] = {0};
printf("Please input total num:");
scanf("%%d",&n);
printf("Please input out num:");
scanf("%%d",&m);
printf("leave sequence:
");
left_num(a,n,m);
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
2.链表
/*
有n个人围城一圈,按顺序编号,从第一个人开始报数,从1报到m,凡报到m的人退出圈子,
然后接着报数,问最后留下来的是原来的第几号的那位?
*/
//循环链表实现
//构造一个循环链表,链表节点的数据域存放人的编号,遍历整个链表,每次报到m的人退出,并释放该节点,直到链表只剩一个节点。
#include <stdio.h>
#include <malloc.h>
/*构建结构体*/
typedef struct Node{
int Num;
struct Node *next;
}JoseNode, *PNode, *HNode;
/**********初始化循环单链表*********/
int JoseInit(HNode h)
{
if (!h)
{
printf("初始化链表错误!
");
return 0;
}
(h)->next = (h);//循环单链表
return 1;
}
/*************单链表插入操作**********/
int JoseInsert(JoseNode *h, int pos, int x)
{
PNode p=h,q;
int i=1;
if (pos == 1)/*尾插法*/
{
p->Num = x;
p->next = p;
return 1;
}
while(i<pos-1)
{
p=p->next;
i++;
}
q=(PNode)malloc(sizeof(JoseNode));
q->Num=x;
q->next=p->next;
p->next=q;
return 1;
}
/*遍历*/
void TraverseList(HNode h, int M)
{
int i = 0;
PNode p = h;
printf("参与的人的编号为:
");
while (i<M)
{
printf("%%d ", p->Num);
p = p->next;
i++;
}
printf("
");
}
/**************出局函数****************/
int JoseDelete(HNode h, int M, int k)
{ int i;
PNode p=h,q;
while(M>15)//留十五个结点,多的结点删除
{
for(i=1;;i++)//循环找到报n的结点
{
if(i%%(k-1)==0) break;
p=p->next;
}
q=p->next;
p->next=q->next;
printf("出局的人为:%%d号
",q->Num);
free(q);
p=p->next;
M--;
}
for(i=0;i<15;i++)//将幸存者及其位置输出
{
printf("***************获胜者为:%%d号***************
",p->Num);
p=p->next;
}
return 1;
}
/***************************************/
int main()
{
int i;//计数器
int N;//参与的人数
int k;//报数密码
printf("请输入参与人数:");
scanf("%%d",&N);
printf("请输入出局密码:");
scanf("%%d",&k);
/**************得到头结点****************/
HNode h = ((HNode)malloc(sizeof(JoseNode)));
/***************初始化单链表************/
JoseInit(h);
/******将编号插入到循环单链表中******/
for (i = 1; i <=N; i++)
{
JoseInsert(h, i, i);
}
/**************遍历单链表***************/
TraverseList(h,N);
/***************出局函数************/
JoseDelete(h, N, k);
printf("
");
printf("
");
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
3.数学法
#include<stdio.h>
int main(){
int n,m;
printf("请输入参与人数:");
scanf("%%d",&n);
printf("请输入报数密码:");
scanf("%%d",&m);
int ans=0,i=0;
for(i=1;i<=n;i++){
ans=(ans+m)%%i;
}
printf("获胜者为:%%d号",ans+1);
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
4.递归
#include<stdio.h>
int josephus(int n,int m);
int main(){
int n,m;
printf("请输入参与人数:");
scanf("%%d",&n);
printf("请输入报数密码:");
scanf("%%d",&m);
int ret=josephus(n,m);
printf("获胜者为:%%d号",ret+1);
return 0;
}
int josephus(int n,int m){
if(n==1)
return 0;
else
return (josephus(n-1,m)+m)%%n;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
走迷宫
//走迷宫
#include<stdio.h>
#include<stdlib.h>
int migo[7][7]={
{2, 2, 2, 2, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 2},
{2, 0, 2, 0, 2, 0, 2},
{2, 0, 0, 0, 0, 2, 2},
{2, 2, 0, 2, 0, 2, 2},
{2, 0, 0, 0, 0, 0, 2},
{2, 2, 2, 2, 2, 2, 2}};//迷宫图
int starti=1,startj=1;//出发点
int endi=5,endj=5;//出口
int success=0;
//递归思想
int visit(int i,int j)
{
migo[i][j]=1;
if(i==endi&&j==endj)//判断有没有到出口
success=1;
if(success!=1&&migo[i][j+1]==0) visit(i,j+1);//四种走法,右,下,左,上
if(success!=1&&migo[i+1][j]==0) visit(i+1,j);
if(success!=1&&migo[i][j-1]==0) visit(i,j-1);
if(success!=1&&migo[i-1][j]==0) visit(i-1,j);
if(success!=1)
migo[i][j]=0;
return success;
}
int main()
{
int i,j;
printf("显示迷宫:
");
//打印迷宫
for(i=0;i<7;i++)
{
for(j=0;j<7;j++){
if(migo[i][j]==2)
printf(" █");
else
printf(" ");
}
printf("
");
}
if(visit(starti,startj)==0)
{
printf("
没有找到出口!
");
}
else
{
printf("
显示路径:
");
for(i=0;i<7;i++)
{
for(j=0;j<7;j++)
{
if(migo[i][j]==2)
printf(" █");
else if(migo[i][j]==1)
printf(" *");
else
printf(" ");
}
printf("
");
}
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
推荐阅读