1. [problem description]
There are n people sitting around a round table. Now start counting from the s person, count to the m person, then start counting again from the next person, and count to the m person again. Repeat until all people are listed. The Josephus problem is: for any given n, m, s, find the sequence table of n people obtained according to the column order.
[input]
Initial string, insert position, insert character, delete character.
[output]
The linked list (string) has been established. The linked list after inserting characters, deleting characters and reversing characters.
[storage structure]
Chain storage structure is adopted
[basic idea of algorithm]
The core idea is to use the circular linked list to complete the code writing. Referring to the solutions to the Joseph Ring problem on some networks, the ideas are as follows: first build the circular linked list, and then list l, s, m and n in turn to find the position of S; Use the if statement to solve the value problem of M, and then output it to solve the problem.
#include <stdio.h>
#include <malloc.h>
typedef struct node{//Single linked list node structure
int date;
struct node *next;
}node,*nodelink;
void make(nodelink head,int n){
//n is the number of people around the round table
//Establish a single linked list with length n and fill in the corresponding number of each node
//The pointer of the last element of the linked list points to the position indicated by the head node to form a circular linked list
int i;
nodelink p,q;
p=head;
for(i=0;i<n;i++){
q=(nodelink)malloc(sizeof(node));//Request memory
p->next=q;
q->date=i+1;
q->next=head->next;
p=p->next;
}
}
void dequeue(nodelink head,nodelink line,int n,int m,int s){
//Those who count to m are out of the line
//Start counting from the s-th person
int i;
nodelink p,q,r;
p=head->next;
//The loop makes p point to the person who starts counting
for(i=1;i<s;i++){
p=p->next;
q=p;
}
//Cycle through the linked list and store the linked list at the corresponding position in the new linked list
r=line; //line is the head pointer of the new linked list
do{
for(i=1;i<m; i++) //Look for elements to be out of the team
{
q=p;
p=p->next;
}
q->next=p->next; //Point both q and p to the element to be dequeued
p->next=NULL; //Set the found element as the last element of the new linked list
r->next=p; //r is always at the end of the new linked list, and the new element is followed by the linked list
r=r->next;
p=q->next; //Point p to the next element to start a new round of out of line
}while(p!=p->next); //When there is only one element left, the loop is terminated
r->next=p;
r->next->next=NULL;
}
void write(nodelink line,int n){
int i;
nodelink p;
p=line->next;
for(i=0; i<n; i++,p=p->next) //Output the elements in the new linked list in turn
printf("%d ",p->date);
}
int main()
{
nodelink head,line;
int m,n,s;
head=(nodelink)malloc(sizeof(node));
line=(nodelink)malloc(sizeof(node)); //Save out of column order
printf("Enter the total number of people n:");
scanf("%d",&n);
make(head,n);
printf("Enter who started s:");
scanf("%d",&s);
printf("Enter the number you want to count m:");
scanf("%d",&m);
dequeue(head,line,n,m,s);
write(line,n);
printf("\n\n");
}2.
[problem description]
Write a recursive algorithm to find the node at the K position in the preorder sequence in the binary tree.
[input]
If the node of a binary tree has no subtree, its subtree can be regarded as ".", When inputting, enter the content of the node in the order of the pre order sequence.
The node location k to find.
[output]
If the binary tree is not empty, it will be output in sequence.
Output the value of the k-th node.
[storage structure]
Binary linked list storage.
[basic idea of algorithm]
Firstly, the left and right subtrees are established by recursion, and then the left and right subtrees are established by the method of binary tree. The binary tree is traversed first. For each node traversed, the value of K is reduced by 1. When the value of K is 0, the current node is output. If the value of K is greater than the number of nodes in the tree, there are too few nodes in the output tree, and the k-th node is empty.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct BiTNode{
char data;
struct BiTNode *Lchild, *Rchild;
}BiTNode,*BiTree;
//Find the k-th element
bool Find_K(BiTree B1,int *i, int k){
if(B1 == NULL) return false;
(*i)++;
if(k == *i){
printf("%c\n", B1->data);
return true;
}
if(Find_K(B1->Lchild,i,k) || Find_K(B1->Rchild,i,k))
return true;
return false;
}
// create Binary Tree
BiTree CreateBiTree(BiTree T){
char ch;
scanf("%c", &ch);
if(ch == '.') T = NULL;
else{
if(!(T = (BiTNode*)malloc(sizeof(BiTNode)))) return false;
T->data = ch;
T->Lchild = CreateBiTree(T->Lchild);
T->Rchild = CreateBiTree(T->Rchild);
}
return T;
}
int main()
{
BiTree T1 = NULL,B1;
int k;
scanf("%d",&k);
B1 = CreateBiTree(T1);
printf("success !\n");
scanf("%d",&k);
int a = 0;
if(Find_K(B1,&a,k)){
printf("find K!");
}else{
printf("sorry, can't find K!");
}
return 0;
}3.
[problem description]
Using adjacency table storage structure, an algorithm for finding the number of connected components of undirected graph is written.
[input]
The number of vertices N of the graph, the relationship between vertices in the graph and the starting point A and ending point B of the path to be found.
[output]
The number of connected components of a graph.
[storage structure]
The graph is stored in the form of adjacency matrix.
[basic idea of algorithm]
Using the breadth first search method, starting from vertex A, access the vertices VA1, VA2,... Adjacent to A in turn, VAK, after access, if B is not accessed, continue to access the vertices VA11, VA12,... Adjacent to VA1, Va1m, then access the vertex adjacent to VA2, If you go on like this until you find B, the path that first reaches point B must be the path with the least number of sides. When implemented, the accessed vertices are recorded in A queue. Each time the vertex adjacent to the queue head vertex is accessed, the queue head vertex is deleted from the queue. If the queue is empty, it indicates that there is no access. In the process of accessing vertices, each time the sequence number of the current vertex is recorded as the precursor vertex of the adjacent unreached vertex, so that it can be traced back during output.
#include<stdio.h>
#include<malloc.h>
int n;
struct VNode{ //vertex
int position;struct VNode*next;
};
struct ArcNode{ //arc
int mark;
struct VNode*first;
};
void DFS(struct ArcNode*v,struct ArcNode*w){ //Depth first search
struct VNode*L;
w->mark=1;
L=w->first;
while(L!=NULL){
if((v+(L->position))->mark==0){
DFS(v,(v+L->position)); //Recursive call}
L=L->next;}}
int main(){
int i,j,k;
int num=0;
struct ArcNode*p;
struct VNode*temp;
struct VNode*flag;
printf("\n Please enter the number of vertices n:");
scanf("%d",&n);
while(n<1){
printf("The value you entered is unreasonable. Please re-enter it:\n");
scanf("%d",&n);
}
p=(struct ArcNode*)malloc(n*sizeof(struct ArcNode));
for(i=0;i<n;i++){ //Create undirected graph
printf("\n Please enter to V%d Is all arcs at the end of the arc, and-1 End input\n",i+1);
scanf("%d",&k);
if(k==-1){
p[i].mark=0;
p[i].first=NULL;
}
else{
temp=(struct VNode*)malloc(sizeof(struct VNode));
temp->position=k;
temp->next=NULL;
p[i].first=temp;
p[i].mark=0;
flag=temp;
scanf("%d",&k);
while(k!=-1){
temp=(struct VNode*)malloc(sizeof(struct VNode));
temp->position=k;
temp->next=NULL;
flag->next=temp;
flag=temp; scanf("%d",&k);
}}
}
i=0;
while(p[i].mark==0){ //Calculate the number of connected components
DFS(p,(p+i));
num++;
i=0;
while(p[i].mark!=0&&i<n){
i++;
}
}
printf("The number of connected components of this graph is:%d\n",num);
return 0;
}
4.
[problem description]
Write a program to realize the following operations: find records with key in binary sort tree.
[input]
Enter a set of sequences ending with 0.
Enter the element to find.
[output]
Traverse the output in sequence.
Search succeeded or failed.
[storage structure]
Ordered tables are stored in a sequential manner.
[basic idea of algorithm]
First, compare the record to be searched with the record in the middle of the search interval. If it is equal, the search is successful, and the number of positions of the record in the table is returned. If it is less than the record in the middle position, the upper bound of the modified interval is the middle position minus 1. If it is greater than the record in the middle position, the lower bound of the modified interval is the middle position plus 1, and continue to search in the new interval. When the lower bound of the search interval is greater than the upper bound, the record does not exist.
#include <stdio.h>
#include <stdlib.h>
#define ENDKEY 0
typedef int KeyType;
typedef struct node
{
KeyType key ; /*Value of keyword*/
struct node *lchild,*rchild;/*Left and right pointer*/
}BSTNode, *BSTree;
void InsertBST(BSTree *bst, KeyType key)
/*If there is no element with keyword equal to key in binary sort tree, insert the element*/
{
BSTree s;
if (*bst == NULL)/*Recursive end condition*/
{
s=(BSTree)malloc(sizeof(BSTNode));/*Apply for new node s*/
s-> key=key;
s->lchild=NULL;
s->rchild=NULL;
*bst=s;
}
else
if (key < (*bst)->key)
InsertBST(&((*bst)->lchild), key);/*Insert s into the left subtree*/
else
if (key > (*bst)->key)
InsertBST(&((*bst)->rchild), key); /*Insert s into the right subtree*/
}
void CreateBST(BSTree *bst)
/*Enter the value of the element from the keyboard to create the corresponding binary sort tree*/
{
KeyType key;
*bst=NULL;
scanf("%d", &key);
while (key!=ENDKEY) /*ENDKEY Is a custom constant*/
{
InsertBST(bst, key);
scanf("%d", &key);
}
}
void PreOrder(BSTree root)
/*Traverse the binary tree in the middle order, and root is the pointer to the root node of the binary tree*/
{
if (root!=NULL)
{
PreOrder(root->lchild); /*Middle order traversal of left subtree*/
printf("%d ",root->key); /*Output node */
PreOrder(root->rchild); /*Middle order traversal right subtree*/
}
}
/*
BSTree SearchBST(BSTree bst, KeyType key)
/ *In the binary sort tree indicated by the root pointer bst, recursively search for an element with a keyword equal to key. If the search is successful, a pointer to the node of the element is returned; otherwise, a null pointer * is returned/
{
if (!bst)
return NULL;
else
if (bst->key == key)
return bst;/ *Search succeeded */
else
if (bst->key > key)
return SearchBST(bst->lchild, key);/ *Continue searching in the left subtree */
else
return SearchBST(bst->rchild, key);/ *Continue searching in the right subtree */
}*/
BSTree SearchBST(BSTree bst, KeyType key)
/*On the binary sort tree bst indicated by the root pointer bst, find the node whose keyword is equal to key. If the search is successful, return the pointer to the element node, otherwise return the null pointer*/
{
BSTree q;
q=bst;
while(q)
{
if (q->key == key)
return q; /*Search succeeded*/
if (q->key > key)
q=q->lchild; /*Find in the left subtree*/
else
q=q->rchild; /*Find in right subtree*/
}
return NULL; /*Search failed*/
}/*SearchBST*/
int main()
{
BSTree T;
int k;
BSTree result;
printf("To create a binary sort tree, please enter a sequence ending with 0:\n");
CreateBST(&T);
printf("The output sequence of preorder traversal is:");
PreOrder(T);
printf("\n Please enter the element to find:");
fflush(stdin);
scanf("%d",&k);
result = SearchBST(T,k);
if (result != NULL)
printf("Found");
else
printf("not found!\n");
}
5.
[problem description]
1. Design a direct selection sorting algorithm represented by linked list and implement it by program.
Algorithm description: the known initial sequence to be sorted is stored in a single linked list, and the head pointer head points to the first node. Find the minimum node from the sequence to be sorted, insert the head and indicate it with R. R is a sorted sequence before, and R is an unordered sequence after. Find the smallest node from the unordered sequence, insert it after r, and let r point to this node. Repeat the process until it is in order.
[input]
Number of records to be sorted n, value of each record to be sorted.
[output]
The results of n records are arranged from small to large.
[storage structure]
The records to be sorted are stored in sequence.
[basic idea of algorithm]
The quick sort algorithm takes the keyword of one record as the standard every time, divides the other records into two groups, puts all records with keyword less than or equal to the standard before its position, and puts all records with keyword greater than the standard after its position. The two groups are quickly sorted until they are completely ordered. For each recursion, the recursion depth is increased by 1.
#include <stdio.h>
#include <malloc.h>
#include <Windows.h>
int n;
struct Number{
int data;
struct Number* next;
};
struct Number* Creat_H(int k){//Create linked list
struct Number* L;
struct Number* p;
int temp,i;
p=(struct Number*)malloc(sizeof(struct Number));
L=p;
printf("Please enter data(The data is an integer variable separated by a space): \n");
for(i=1;i<=k;i++){
scanf("%d",&temp);
p->data=temp;
if(i==k){
p->next=NULL;
break;
}
p->next=(struct Number*)malloc(sizeof(struct Number));
p=p->next;
}
return L;
}
struct Number* Sort(struct Number* p){//sort
struct Number* max;
struct Number* min;
struct Number* temp;
struct Number* r;
int flag=0;
r=p;
do{
if(flag==0){//Initialization at the first decimal point
temp=min=max=r;
}
else{
temp=min=max=r->next;
}
while(1){//Find the decimal point
if(min->data<=max->next->data){
if(max->next->next!=NULL){
max=max->next;
}
else{
break;
}
}
else{
temp=max;//Equivalent to temp - > next = min
min=max->next;
if(max->next->next!=NULL){
max=max->next;
}
else{
break;
}
}
}
if(temp!=min){
if(min->next==NULL){
temp->next=NULL;
}
else{
temp->next=min->next;
}
if(flag==0){
r=min;
r->next=p;
p=r;
}
else{
min->next=r->next;
r->next=min;
r=min;
}
}
else{//min already points to the minimum number during initialization
if(flag==0){//Find the minimum number for the first time
r=min;
p=r;
}
else{
r=min;
}
}
flag++;//Another number
if(flag==n-1){
return p;
}
}while(1);
}
int main(){
struct Number* H;
printf("How many data do you have to enter(Not less than 2): \n");
scanf("%d",&n);
while(n<2){
printf("The number of data you entered is less than 2. Please re-enter:\n");
scanf("%d",&n);
}
H=Creat_H(n);
H=Sort(H);
printf("The sequence after data sorting is:\n");
while(H!=NULL){
printf("%-4d",H->data);
H=H->next;
}
printf("\n");
system("pause");
return 0;
}