2024.7.22 作业

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

循环链表

looplinklist.h

#ifndef LOOPLINKLIST_H
#define LOOPLINKLIST_H#include <myhead.h>typedef int datatype;typedef struct Node
{union {int len;datatype data;};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);//链表销毁
void list_destroy(NodePtr L);//约瑟夫环
void ysfh(NodePtr L,int m);#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=1;i<=pos;i++){q=q->next;}return q;
}//链表尾插
int list_insert_tail(NodePtr L,datatype e)
{if( NULL==L ){printf("尾插失败\n");return -1;}NodePtr p = apply_node(e);if( NULL==p ){return -1;}NodePtr q = list_search_pos(L,L->len);p->next = q->next;q->next = p;L->len++;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("%d\t",q->data);q = q->next;}printf("\n");return 0;
}//链表头删
int list_delete_head(NodePtr L)
{if( NULL==L || list_empty(L) ){printf("头删失败\n");return -1;}NodePtr q = L->next;L->next = q->next;L->len--;free(q);q=NULL;return 0;
}//链表销毁
void list_destroy(NodePtr L)
{if( NULL==L ){printf("销毁失败\n");return ;}while( !list_empty(L) ){list_delete_head(L);}free(L);L=NULL;printf("销毁成功\n");return;
}

双向链表 

doublelinklist.h

#ifndef DOUBLELINKLIST_H
#define DOUBLELINKLIST_Htypedef 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);#endif

doublelinklist.c

#include "doublelinklist.h"//创建双向链表
NodePtr list_create()
{NodePtr L = (NodePtr)malloc(sizeof(Node));if( NULL==L ){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
}//链表头插
int list_insert_head(NodePtr L,datatype e)
{if( NULL==L ){printf("头插失败\n");return -1;}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++;return 0;
}//链表遍历
int list_show(NodePtr L)
{if( NULL==L || list_empty(L) ){printf("遍历失败\n");return -1;}printf("当前数据为：");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=1;i<=pos;i++){q = q->next;}return q;
}//链表任意位置删除
int list_delete_pos(NodePtr L,int pos)
{if( NULL==L || list_empty(L) || pos<1 || pos>L->len ){printf("删除失败\n");return -1;}NodePtr q = list_search_pos(L,pos);if( q->next==NULL ){q->prio->next==NULL;}else{q->prio->next = q->next;q->next->prio = q->prio;}free(q);q=NULL;L->len--;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 ;
}

 

2.使用循环链表完成约瑟夫环问题

//约瑟夫环
void ysfh(NodePtr L,int m)
{NodePtr p = L->next;NodePtr q = L;while( p->next!=p ){for(int i=1;i<m;i++){q = p;p = p->next;if(p==L){q=q->next;p=p->next;}}printf("%d\t",p->data);NodePtr a = p;           //标记q->next = p->next;   //p->next 孤立p=p->next;free(a);                   //释放a = NULL;}printf("\n最后剩下的节点: %d\n", p->data);  free(p); // 释放最后一节点  }

3.使用栈，完成进制转换

输入：一个整数，进制数

输出：该数的对应的进制数

void DC(StackPtr S,int m,int n)
{while(m/n!=0){S->top++;S->data[S->top]=m%n;m=m/n;}S->top++;S->data[S->top]=1;while(S->top!=-1){printf("%d",S->data[S->top]);S->top--;}printf("\n");
}

思维导图