当前位置：首页 > news >正文

华清数据结构day5 24-7-22

news 来源：原创 2024/9/20 15:06:48

1>使用栈，完成进制转换输入：一个整数，进制数输出：该数的对应的进制数

seqstack.h

#ifndef SEQSTACK_H
#define SEQSTACK_H
#define MAX 10
#include"myhead.h"
typedef int datatype;typedef struct 
{datatype *data;int top;
}Stack,*StackPtr;
//创建栈
StackPtr stack_create();
//判空
int stack_empty(StackPtr S);
//判满
int stack_full(StackPtr S);
//入栈
void stack_push(StackPtr S, datatype e);
//出栈
void stack_pop(StackPtr S);
//遍历栈
void stack_show(StackPtr S);
//获取栈顶元素
datatype* stack_get_top(StackPtr S);
//求栈的大小
int stack_size(StackPtr S);
//销毁栈
void stack_destroy(StackPtr S);
//进制转换
void base_conversion(StackPtr S);
#endif

seqstack.c

#include"seqstack.h"StackPtr stack_create()
{StackPtr S = (StackPtr)malloc(sizeof(Stack));if(NULL == S){printf("创建失败\n");return NULL;}S->data = (datatype *)malloc(sizeof(datatype)*MAX);if(NULL == S->data){printf("创建失败\n");return NULL;}memset(S->data,0,sizeof(datatype)*MAX);S->top = -1;return S;
}int stack_empty(StackPtr S)
{return S->top == -1;
}int stack_full(StackPtr S)
{return S->top == MAX-1;
}void stack_push(StackPtr S,datatype e)
{if(NULL == S||stack_full(S)){printf("入栈失败\n");return;}S->top++;S->data[S->top] = e;
}void stack_pop(StackPtr S)
{if(NULL == S||stack_empty(S)){printf("出栈失败\n");return;}S->top--;
}void stack_show(StackPtr S)
{if(NULL == S|| stack_empty(S)){printf("遍历失败\n");return;}for(int i = S->top;i>=0;i--){printf("%c\t",S->data[i]+48);}printf("\n");
}datatype* stack_get_top(StackPtr S)
{if(NULL == S||stack_empty(S)){printf("操作失败\n");return NULL;}return &S->data[S->top];
}int stack_size(StackPtr S)
{if(NULL == S){printf("操作失败\n");}return S->top+1;
}void stack_destroy(StackPtr S)
{if(S!=NULL){free(S->data);free(S);S=NULL;}
}void base_conversion(StackPtr S)
{int num = 0,base = 0;printf("请输入一个数(10进制):");scanf("%d",&num);printf("请输入你想要将他转换成为的进制:");scanf("%d",&base);while(num){if (num%base >9){stack_push(S,num%base+7);}else{stack_push(S,num%base);}	num=num/base;}stack_show(S);
}

main.c

#include"seqstack.h"
#include<myhead.h>
int main(int argc, const char *argv[])
{StackPtr S = stack_create();if(NULL == S){return -1;}base_conversion(S);//调用销毁函数stack_destroy(S);S = NULL;return 0;
}

2> 将双向链表和循环链表自己实现一遍，至少要实现创建、增、删、改、查、销毁工作

双向链表

doublelinklist.h

#ifndef DOUBLELINKLIST_H
#define DOUBLELINKLIST_H
#include"myhead.h"
typedef char datatype;typedef struct Node
{union{int len;datatype data;};struct Node *prio;struct Node *next;
}Node,*NodePtr;NodePtr list_create();int list_empty(NodePtr L);NodePtr apply_node(datatype e);int list_insert_head(NodePtr L,datatype e);int list_show(NodePtr L);NodePtr list_search_pos(NodePtr L ,int  pos);int list_delete_pos(NodePtr L,int pos);void list_destroy(NodePtr L);
int list_update_pos(NodePtr L, int pos, datatype e);
#endif

doublellinklist.c

#include"doublelinklist.h"NodePtr list_create()
{NodePtr L = (NodePtr)malloc(sizeof(Node));if(L == NULL){printf("申请失败\n");return NULL;}L->len = 0;L->prio = NULL;L->next = NULL;printf("创建成功\n");return L;
}int list_empty(NodePtr L)
{return L->next == NULL;
}NodePtr apply_node(datatype e)
{NodePtr p = (NodePtr)malloc(sizeof(Node));if(NULL == p){printf("节点申请失败\n");return NULL;}p->data = e;p->prio == NULL;p->next == NULL;return p;
}int list_insert_head(NodePtr L,datatype e)
{if(NULL == L){printf("插入失败\n");}NodePtr p = apply_node(e);if(NULL == p){return -1;}if(list_empty(L)){p->prio = L;L->next = p;}else{p->prio = L;p->next = L->next;L->next->prio = p;L->next = p;}L->len++;printf("插入成功\n");return 0;
}int list_show(NodePtr L)
{if(NULL == L||list_empty(L)){printf("遍历失败\n");return -1;}NodePtr q = L->next;while(q){printf("%c\t",q->data);q=q->next;}printf("\n");return 0;
}NodePtr list_search_pos(NodePtr L ,int  pos)
{if(NULL == L|| list_empty(L) ||pos<0 || pos>L->len){printf("查找失败\n");return NULL;}NodePtr q = L;for(int i=0;i<pos;i++){q=q->next;}return q;
}
int list_update_pos(NodePtr L, int pos, datatype e)
{if (NULL == L || list_empty(L)|| pos<0||pos>L->len){printf("修改失败\n");return -1;}NodePtr p = list_search_pos(L,pos);p->data = e;printf("修改成功\n");return 0;
}
int list_delete_pos(NodePtr L,int pos)
{   if(NULL == L|| list_empty(L) || pos<0||pos>L->len){printf("删除失败\n");return -1;}NodePtr p = list_search_pos(L,pos);if(NULL == p->next){p->prio->next = NULL;free(p);}else{p->prio->next = p->next;p->next->prio = p->prio;free(p);}L->len--;printf("删除成功\n");return 0;
}void list_destroy(NodePtr L)
{if(NULL == L){printf("删除失败\n");return;}while(!list_empty(L)){list_delete_pos(L,1);}free(L);L=NULL;printf("链表释放成功\n");return;
}

main.c

#include"doublelinklist.h"int main(int argc, const char *argv[])
{NodePtr L = list_create();if(NULL == L){return -1;}list_insert_head(L,'Q');list_insert_head(L,'W');list_insert_head(L,'E');list_insert_head(L,'R');list_show(L);list_update_pos(L,2,'F');list_show(L);list_delete_pos(L,4);list_show(L);list_destroy(L);return 0;
}

循环链表

looplinklist.h

#ifndef LOOPLINKLIST_H
#define LOOPLINKLIST_H
#include"myhead.h"
typedef char datatype;typedef struct Node
{union{int len;datatype data;};struct Node *prio;struct Node *next;
}Node,*NodePtr;
//链表创建
NodePtr list_create();
//链表判空
int list_empty(NodePtr L);
//链表申请空间封装节点
NodePtr apply_node(datatype e);
//按位置查找
NodePtr list_search_pos(NodePtr L ,int pos);
//链表尾插
int list_insert_tail(NodePtr L,datatype e);
//链表输出
int list_show(NodePtr L);
//链表头删
int list_delete_head(NodePtr L);
//链表任意位置删除
int list_delete_pos(NodePtr L, int pos);
//链表按位置进行修改
int list_update_pos(NodePtr L, int pos, datatype e);
//链表销毁
void list_destory(NodePtr L);
#endif

looplinklist.c

#include"looplinklist.h"
//链表创建
NodePtr list_create()
{NodePtr L = (NodePtr)malloc(sizeof(Node));if(NULL == L){printf("创建失败\n");return NULL;}L->len=0;L->next = L;printf("创建成功\n");return L;
}
//链表判空
int list_empty(NodePtr L)
{return L->next==L;
}
//链表申请空间封装节点
NodePtr apply_node(datatype e)
{NodePtr p = (NodePtr)malloc(sizeof(Node));if(NULL == p){printf("创建失败\n");return NULL;}p->data = e;p->next = NULL;return p;
}
//按位置查找
NodePtr list_search_pos(NodePtr L ,int pos)
{if(NULL == L|| pos<0 ||pos>L->len){printf("查找失败\n");return NULL;}NodePtr q = L;for(int i= 0;i<pos;i++){q=q->next;}return q;
}
//链表尾插
int list_insert_tail(NodePtr L,datatype e)
{if(NULL == L){printf("插入失败\n");return -1;}NodePtr q = list_search_pos(L,L->len);NodePtr p = apply_node(e);if(NULL == L){return -1;}p->next = q->next;q->next = p;L->len++;printf("插入成功\n");return 0;
}
//链表输出
int list_show(NodePtr L)
{if(NULL== L||list_empty(L)){printf("遍历失败\n");return -1;}NodePtr q = L->next;while(q!=L){printf("%c\t",q->data);q=q->next;}printf("\n");
}
//链表头删
int list_delete_head(NodePtr L)
{if(NULL==L || list_empty(L)){printf("删除失败\n");return -1;}NodePtr q = L->next;L->next = q->next;free(q);q=NULL;L->len--;printf("删除成功\n");
}
//链表销毁
void list_destory(NodePtr L)
{if(NULL == L){printf("释放失败\n");return;}while(!list_empty(L)){list_delete_head(L);}free(L);L = NULL;printf("销毁成功\n");
}
//链表任意位置删除
int list_delete_pos(NodePtr L, int pos)
{if (NULL == L||pos<0 ||pos>L->len||list_empty(L)){printf("删除失败\n");return -1;}NodePtr p = list_search_pos(L,pos-1);NodePtr q = p->next;p->next = q->next;free(q);q=NULL;printf("删除成功\n");L->len--;  return 0;
}
//链表按位置进行修改
int list_update_pos(NodePtr L, int pos, datatype e)
{if (NULL == L||pos<0 ||pos>L->len||list_empty(L)){printf("修改失败\n");return -1;}NodePtr p = list_search_pos(L,pos);p->data = e;printf("修改成功\n");return 0;
}

main.c

#include"looplinklist.h"
#include<myhead.h>
int main(int argc, const char *argv[])
{NodePtr L = list_create();if(NULL == L){return -1;}list_insert_tail(L,'Q');list_insert_tail(L,'W');list_insert_tail(L,'E');list_insert_tail(L,'R');list_insert_tail(L,'T');list_show(L);list_update_pos(L,2,'P');list_show(L);list_delete_pos(L,3);list_show(L);list_destory(L);L=NULL;return 0;
}

3> 使用循环链表完成约瑟夫环问题

looplinklist.h

#ifndef LOOPLINKLIST_H
#define LOOPLINKLIST_H
#include"myhead.h"
typedef char datatype;typedef struct Node
{union{int len;datatype data;};struct Node *prio;struct Node *next;
}Node,*NodePtr;
//链表创建
NodePtr list_create();
//链表判空
int list_empty(NodePtr L);
//链表申请空间封装节点
NodePtr apply_node(datatype e);
//按位置查找
NodePtr list_search_pos(NodePtr L ,int pos);
//链表尾插
int list_insert_tail(NodePtr L,datatype e);
//链表输出
int list_show(NodePtr L);
//链表头删
int list_delete_head(NodePtr L);
//链表任意位置删除
int list_delete_pos(NodePtr L, int pos);
//链表按位置进行修改
int list_update_pos(NodePtr L, int pos, datatype e);
//链表销毁
void list_destory(NodePtr L);
//约瑟夫
void Josephus_problem(NodePtr L);
#endif

looplinklist.c

#include"looplinklist.h"
//链表创建
NodePtr list_create()
{NodePtr L = (NodePtr)malloc(sizeof(Node));if(NULL == L){printf("创建失败\n");return NULL;}L->len=0;L->next = L;printf("创建成功\n");return L;
}
//链表判空
int list_empty(NodePtr L)
{return L->next==L;
}
//链表申请空间封装节点
NodePtr apply_node(datatype e)
{NodePtr p = (NodePtr)malloc(sizeof(Node));if(NULL == p){printf("创建失败\n");return NULL;}p->data = e;p->next = NULL;return p;
}
//按位置查找
NodePtr list_search_pos(NodePtr L ,int pos)
{if(NULL == L|| pos<0 ||pos>L->len){printf("查找失败\n");return NULL;}NodePtr q = L;for(int i= 0;i<pos;i++){q=q->next;}return q;
}
//链表尾插
int list_insert_tail(NodePtr L,datatype e)
{if(NULL == L){printf("插入失败\n");return -1;}NodePtr q = list_search_pos(L,L->len);NodePtr p = apply_node(e);if(NULL == L){return -1;}p->next = q->next;q->next = p;L->len++;printf("插入成功\n");return 0;
}
//链表输出
int list_show(NodePtr L)
{if(NULL== L||list_empty(L)){printf("遍历失败\n");return -1;}NodePtr q = L->next;while(q!=L){printf("%c\t",q->data);q=q->next;}printf("\n");
}
//链表头删
int list_delete_head(NodePtr L)
{if(NULL==L || list_empty(L)){printf("删除失败\n");return -1;}NodePtr q = L->next;L->next = q->next;free(q);q=NULL;L->len--;
}
//链表销毁
void list_destory(NodePtr L)
{if(NULL == L){printf("释放失败\n");return;}while(!list_empty(L)){list_delete_head(L);}free(L);L = NULL;printf("销毁成功\n");
}
//链表任意位置删除
int list_delete_pos(NodePtr L, int pos)
{if (NULL == L||pos<0 ||pos>L->len||list_empty(L)){printf("删除失败\n");return -1;}NodePtr p = list_search_pos(L,pos-1);NodePtr q = p->next;p->next = q->next;free(q);q=NULL;printf("删除成功\n");L->len--;  return 0;
}
//链表按位置进行修改
int list_update_pos(NodePtr L, int pos, datatype e)
{if (NULL == L||pos<0 ||pos>L->len||list_empty(L)){printf("修改失败\n");return -1;}NodePtr p = list_search_pos(L,pos);p->data = e;printf("修改成功\n");return 0;
}
void Josephus_problem(NodePtr L)
{int count = 0,num = 0;printf("请输入数到几退出:");scanf("%d",&num);NodePtr p = L;while (!list_empty(L)){	if (p->next == L){p = p->next;}	if (num ==1){printf("%c\t",list_search_pos(L,1)->data);list_delete_head(L);}else	if(count == num-1) {printf("%c\t",p->next->data);NodePtr q = p->next;p->next = q->next;free(q);q=NULL;L->len--;  count = 0;}count++;p = p->next;}printf("\n");
}

main.c

#include"looplinklist.h"
#include<myhead.h>
int main(int argc, const char *argv[])
{NodePtr L = list_create();if(NULL == L){return -1;}list_insert_tail(L,'Q');list_insert_tail(L,'W');list_insert_tail(L,'E');list_insert_tail(L,'R');list_insert_tail(L,'T');// list_show(L);// list_update_pos(L,2,'P');// list_show(L);// list_delete_pos(L,3);// list_show(L);Josephus_problem(L);list_destory(L);L=NULL;return 0;
}