LinkList InitRing(int n, LinkList R) //尾插入法建立单循环链表函数 { ListNode *p, *q; int I; R=q=(LinkNode *)malloc(sizeof(LinkNode)); for(i=1;i<n;i++){ p=(LinkNode *)malloc(sizeof(LinkNode)); q->data=i; q->next=p; q=p; } p->data=n; p->next=R; R=p; return R; } LinkList DeleteDeath(int n, int k, LinkList R) //生者与死者的选择 { int i, j; ListNode *p, *q; p=R; for(i=1; i<n/2; i++){ //删除一半结点 for(j=1; j<k-1; j++) //沿链前进k-1步 p=p->next; q=p->next; p->next=q->next; printf(“%4d”, q->data); free(q); } R=p; return R; } void OutRing(int n, LinkList R){ //输出所有生者 int i; LinkNode *p; p=R; for(i=1;i<=n/2; i++, p=p->next){ printf(“%4d”, p->data) } } 有了上述算法分析和设计之后,实现就比较简单了。首先要定义一个链表结构类型,然后编写一个主函数调用上面已定义好的函数即可。主函数的源程序如下: #include<stdio.h> #include<stdlib.h> typedef struct node{ int data; struct node * next; }ListNode; typedef ListNode * LinkList; void main(){ LinkList R; int n,k; LinkList InitRing(int n, LinkList R); LinkList DeleteDeath(int n, int k, LinkList R); void OutRing(int n, LinkList R); printf(“总人数n. 报数上限k=”); scanf(“%d%d”,&n, &k); R=InitRing(n, R); R=DeleteDeath(n, k, R); OutRing(n, R); }
时间: 2024-02-14 20:14:24 浏览: 21
这段代码实现的是约瑟夫问题,即有n个人围成一圈,从第一个人开始报数,报到k的人出圈,直到只剩下一人为止。其中InitRing函数是使用尾插法建立单循环链表,DeleteDeath函数是模拟生者与死者的选择,OutRing函数是输出所有生者。主函数中先获取输入的总人数n和报数上限k,然后调用InitRing函数初始化单循环链表,接着调用DeleteDeath函数进行约瑟夫问题的模拟,最后调用OutRing函数输出所有生者。
相关问题
用尾插法创建一个单链表,函数声明为 LinkList CreatList_LT(LinkList L, int n)
好的,以下是用尾插法创建单链表的函数实现:
```
typedef struct Node {
int data;
struct Node *next;
} Node, *LinkList;
LinkList CreatList_LT(LinkList L, int n) {
L = (LinkList)malloc(sizeof(Node));
L->next = NULL;
LinkList p, q = L;
for (int i = 0; i < n; i++) {
p = (LinkList)malloc(sizeof(Node));
scanf("%d", &p->data);
p->next = NULL;
q->next = p;
q = p;
}
return L;
}
```
这个函数接受一个 LinkList 类型的参数 L 和一个整数 n,返回一个创建好的单链表。函数通过循环 n 次,每次创建一个新的节点 p,将输入的数据存入 p->data 中,然后将 p 插入到链表的尾部,最后返回头节点 L。
int listinsert(linklist &l,int i,elemtype e) ;//在循环单链表l中第i个位置之前
introduce, int data)是向链表linklist中插入一个元素data的操作。链表是一种动态数据结构,由一系列节点组成,每个节点包含一个数据项和指向下一个节点的指针。
要实现该操作,首先需要创建一个新节点new_node并将data赋值给它的数据项。然后,找到要插入的位置。
如果要插入的位置是链表头部,即插入到空链表中或者作为新的头节点,将new_node的指针指向当前头节点,然后将new_node设为新的头节点即可。
如果要插入的位置是链表中的某个节点之后,找到该节点,令node指向它。然后,将new_node的指针指向node后面的节点,将node的指针指向new_node,即可完成插入操作。
如果要插入的位置超出了链表的范围,即大于链表长度或小于0,那么插入操作无效,返回错误。
最后,将链表的长度加1,表示成功插入了一个新的节点。
综上所述,int listinsert(linklist introduce, int data)的作用是向链表introduce中插入一个新的节点,节点的数据项为data。插入操作分为在链表头部插入和在链表中某个节点之后插入两种情况,实现思路相似,都是创建一个新节点,然后修改指针完成插入。