前言

  1. 记录一下,这几天学习链表时感悟和困难,毕竟算是我接触的第一个抽象数据结构。
  2. 本篇主要分享“约瑟夫问题”的两种实现,以及插入排序的简单实现。

约瑟夫环

  1. x = malloc(sizeof *x)?
  2. 对于两个结构指针 p = x,为什么修改其中一个,没有修改另外一个的内容?对于这个问题我可能是没有了解到,我只是修改指针指向的位置,并没有改变第一个指向的指针。

链表实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
typedef struct node {
int data;
struct node *next;
}link;

int main(){
link *x, *p;
int i;

x = malloc(sizeof *x); //展开研究一下sizeof的使用
x->data = 1; x -> next = x;
p = x; //开始我在疑惑这样赋值,是否会让P修改X的内容
//但并没有修改x的内容
for(i = 2; i < 10; i++){
p = p ->next = malloc(sizeof *p);
p ->data = i; p -> next = x;
} //此时的指针P指向了链表的最后;

while(p != p -> next){
for(i = 1; i < 5; i++){
p = p -> next;
}
p -> next=p -> next -> next;
}
printf("%d", p->data);

return 0;
}

索引数组实现

  1. 索引数组是指数组的内容,是指向下一个元素;
  2. 迷惑了好久,终于写出来了。一开始还想用for循环去写,而且我对环起始的位置也有一些误解。
  3. 通过数组的实现,进一步简化了代码, 不用特意去定义一个结构。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    #include <stdio.h>
    int main(){
    int x, next[9], i;

    for(x = 0; x < 8; x++){
    next[x] = x + 1;
    }
    next[x] = 0; index//0 1 2 3 4 5 6 7 8
    next //1 2 3 4 5 6 7 8 0(next 0是这个循环的其实位置,一开始我就卡在了这里)

    while(x != next[x]){
    for(i = 1; i < 5; i++){
    x = next[x];
    }
    next[x] = next[next[x]];
    }
    printf("%d ", x+1);
    return 0;
    }

插入排序

  1. 这是我所了解的第三种排序算法。
  2. 书中定义的插入排序,由两个链表实现。链表a存放未排序,链表b存放已经排序过的。通过不断的比较,将链表a中比较的内容插入到链表b适当的位置。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    typedef struct node{
    int data;
    struct node *next;
    }link;
    //本程序通过随机数函数,生成是个0~999的数字,并按降序排序
    int main(){
    link *a, *b, *t, *u, *x, heada, headb;
    int i;
    srand((unsigned)time(NULL));
    a = &heada; a -> next = NULL; //这里用了一个空的哑元节点
    for(i = 0, t = a; i < 9; i++){
    t = t -> next = malloc(sizeof *a);
    t -> data = rand() % 1000;
    t -> next = NULL;
    }

    b = &headb; b -> next = NULL;

    for(t = a -> next; t != NULL ; t = u){
    u = t -> next;
    for(x = b; x -> next != NULL; x = x -> next){
    if(t -> data > x -> next -> data) break; //判断循环停下来的位子,若下一个节点是NULL,直接停下插入到该位之后
    }
    t -> next = x -> next;//t的链接变成x后面的链接
    x -> next = t; //x后面的链接是t
    }
    b = b -> next;

    while(b){
    printf("%d ", b -> data);
    b = b -> next;
    }


    return 0;
    }

留言

⬆︎TOP