链表-约瑟夫

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 struct _Node
  4 {
  5     int data;
  6     struct _Node *next;
  7 };
  8 typedef struct _Node node_t;//
  9 typedef struct _Linklist
 10 {
 11     node_t * phead;//就算下面那个结构体有一个尾指针，也不是双向,尾指针只能用来索引尾节点，没法往前索引了。只有单向,主要看方向
 12     //不是看头结点那个表头单向可以用双向也可以用
 13     node_t * ptail;
 14     int len;
 15 }Linklist;
 16 static node_t * GetNode(int i)    // 新建并初始化节点
 17 {
 18     node_t *pNode;
 19     pNode = (node_t *) malloc(sizeof(node_t));
 20     if (!pNode)
 21     {
 22         printf("Error,the memory is not enough!
");
 23         exit(-1);
 24     }
 25     pNode->data = i;
 26     pNode->next = NULL;
 27     return pNode;
 28 }
 29 void init_list(Linklist *plist)    // 用第一个节点初始化循环单链表
 30 {
 31     node_t *p;
 32     p = GetNode(1);
 33     //  printf("The New Node is: %d
", p -> data);   // **** TEST ****
 34     plist->phead = p;
 35     plist->ptail = p;
 36     p->next = plist->phead;
 37     plist->len = 1;
 38 }
 39 static void Create_List(Linklist *plist, int n)    // 把其余数据添加到循环单链表中
 40 {
 41     int i = 0;
 42     node_t *pNew;
 43     for (i = 2; i <= n; i++)
 44     {
 45         pNew = GetNode(i);
 46         /******** TEST ********
 47         printf("The New Node is: %d
", pNew -> data);
 48         ******** TEST ********/
 49         plist->ptail->next = pNew;
 50         plist->ptail = pNew;
 51         pNew->next = plist->phead;
 52         plist->len++;
 53     }
 54     printf("Completes the e-way circulation chain table the foundation!
");
 55 }
 56 void Print_List(Linklist *plist)    // 输出链表内容
 57 {
 58     node_t *pCur = plist->phead;//
 59     do
 60     {
 61         printf("The %d person.
", pCur->data);
 62         pCur = pCur->next;
 63     } while (pCur != plist->phead);
 64     printf("The length of the List: %d
", plist->len);
 65 }
 66 void joseph(Linklist *plist, int m)    //约瑟夫回环函数实现
 67 {
 68     node_t *pPre = plist->ptail;
 69     node_t *pCur = plist->phead;
 70     int i;
 71     while (plist->len != 1)
 72     {
 73         i = 0;
 74         while (i < m - 1)
 75         {
 76             pPre = pPre->next;
 77             i++;
 78         }
 79         pCur = pPre->next;
 80         pPre->next = pCur->next;
 81         free(pCur);
 82         plist->len--;
 83     }
 84     printf("The last one is: %d
", pPre->data);
 85 }
 86 int main()
 87 {
 88     int n = 0;
 89     printf("Please input the Length of the Circle list: ");
 90     scanf_s("%d", &n);
 91     int m = 0;
 92     printf("Please input the Stop point: ");
 93     scanf_s("%d", &m);
 94     Linklist pList;
 95     init_list(&pList);
 96     Create_List(&pList, n);
 97     Print_List(&pList);
 98     joseph(&pList, m);
 99     system("pause");
100     return 0;
101 }

 1 #include<iostream>
 2 using namespace std;
 3 struct node{
 4     int data;
 5     node*next;
 6 };
 7 
 8 node*header()
 9 {
10     node *head, *n;
11     int a;
12     head = NULL;
13     cout << "首节点插入法产生链表，输入数据（-1结束）：" << endl;
14 
15     for (cin >> a; a != -1; cin >> a)
16     {
17         n = new node;
18         n->data = a;
19         if (!head)
20             head = n, n->next = NULL;
21         else 
22             n->next = head, head = n;
23     }
24     return head;
25 }
26 int va(node *head)
27 {
28     node *a, *b;
29     a = head;
30     b = head->next;
31 
32     for (; b != NULL; a = a->next, b = b->next)
33     {
34         if (a->data > b->data)
35             return 0;
36     }
37     return 1;
38 }
39 
40 int main()
41 {
42     node *p1;
43     p1 = header();
44     node *cp = p1;//先弄个副本,p1指针要始终指向人为的head,这样循环完内存都不能回收了已经没有指针指向申请的那段内存了.head始终指向当前节点, 也就是最后申请的一个
45     while (cp)
46     {
47         cout << cp->data << "  ";
48         cp = cp->next;
49     }
50     if (va(p1) == 1)
51         cout << "递增单链表元素！" << endl;
52     else cout << "非递增单链表元素！" << endl;
53     system("pause");
54     return 0;
55 }