{"action":"opened","issue":{"url":"https://api.github.com/repos/Sunxb/blog/issues/13","repository_url":"https://api.github.com/repos/Sunxb/blog","labels_url":"https://api.github.com/repos/Sunxb/blog/issues/13/labels{/name}","comments_url":"https://api.github.com/repos/Sunxb/blog/issues/13/comments","events_url":"https://api.github.com/repos/Sunxb/blog/issues/13/events","html_url":"https://github.com/Sunxb/blog/issues/13","id":345142521,"node_id":"MDU6SXNzdWUzNDUxNDI1MjE=","number":13,"title":"数据结构: 静态链表","user":{"login":"Sunxb","id":16040931,"node_id":"MDQ6VXNlcjE2MDQwOTMx","avatar_url":"https://avatars1.githubusercontent.com/u/16040931?v=4","gravatar_id":"","url":"https://api.github.com/users/Sunxb","html_url":"https://github.com/Sunxb","followers_url":"https://api.github.com/users/Sunxb/followers","following_url":"https://api.github.com/users/Sunxb/following{/other_user}","gists_url":"https://api.github.com/users/Sunxb/gists{/gist_id}","starred_url":"https://api.github.com/users/Sunxb/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Sunxb/subscriptions","organizations_url":"https://api.github.com/users/Sunxb/orgs","repos_url":"https://api.github.com/users/Sunxb/repos","events_url":"https://api.github.com/users/Sunxb/events{/privacy}","received_events_url":"https://api.github.com/users/Sunxb/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2018-07-27T08:47:34Z","updated_at":"2018-07-27T08:47:34Z","closed_at":null,"author_association":"OWNER","body":"#### 什么叫静态链表？\r\n\r\n用数组描述的链表叫做静态链表，这种描述方法叫做游标实现法。\r\n\r\n如何用数组了描述呢 ？\r\n简单的说，就是我们会先创建一个固定的数组，然后数组中的每一个元素都使用一个结构体，该结构体包括两个元素，一个是要储存的数据，一个是游标。\r\n\r\n什么是游标？\r\n游标是用来记录链表的下一个结点的位置（节点所在数组中的下标）。\r\n\r\n这都是一些比较抽象的概念，不太好理解，也很容易搞乱，下面我结合这些图简单的说一些。\r\n\r\n#### 我的理解\r\n\r\n![静态链表](https://upload-images.jianshu.io/upload_images/1491333-b06ef916184258bd.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)\r\n\r\n大家可以先建立几个概念，数组和链表可不要搞混了。\r\n首先这个数组，其实就是我们用来储存用的。那链表呢， 我个人的理解，指得是数组已经使用的这一部分（剩余没使用的那部分暂且叫做备用链表）。我们使用这个数组下标为0的这个位置来当做链表的头结点，所以说这个位置不进行实际的储存。\r\n\r\n**我们在进行存储的时候，是按照数组下标的位置把数据逐一存储进数组的（数组的第0个位置不做实际的存储功能，下面会说到），也就是说我们要把‘甲’，‘乙’，‘丙’，‘丁’，‘戊’，‘己’，‘庚’ 这七个字储存起来，使用的是数组的下标1到6的连续位置，但是在数组中的连续位置，不代表他在链表中的位置，打个比方说，我们要继续存储一个‘辛’这个字，但是我要把它存到甲和乙中间，他的数组的位置就是在下标为7的位置，但是他的链表位置是在甲和乙中间，这是通过游标来体现出来的，下面会说到**\r\n\r\n好的，我们分析一下\r\n在初始化完这个数组之后，所有的位置上都没有储存数据，然后每个位置的游标表示数组的下一个元素，也就是第0个元素的游标为1，第1个元素的游标为2.... \r\n进行了存储之后，如上图，我们看几个比较关键的位置，第0个元素的游标变味了7，第6个元素的游标为0，第999个元素的游标为1，这代表什么意思呢？ \r\n我们在进行插入数据操作的时候，第0个元素的游标总是指向下次储存要用的那个位置，数组的最后一个元素也就是999这个位置的元素，他的游标指向链表的第一个节点（不包括头结点的）在数组中的下标。然后链表的最后一个节点的游标要指向0，因为没有下一个了嘛，所以我们看到第6个元素的位置的游标是0。\r\n\r\n#### 代码实现\r\n理论差不多说完了，下面该说具体的实现了，网上的实现代码很多，直接找了一份代码，咱们一起看一下代码吧\r\n\r\n```objc\r\nint main(int argc, const char * argv[]) {  \r\n    StaticLinkList list[MAXSIZE];\r\n    // 初始化数组中的数据\r\n    createLinkList(list);\r\n    \r\n    for (int i = 0; i < 2; i ++) {\r\n        ListInsert(list, 1, 100+i);\r\n    }\r\n    return 0;\r\n}\r\n```\r\n我们在循环中执行了两次的插入操作，`ListInsert`方法中的参数1指的是每次都是把数据插在链表的第1个结点之前，我们先推测一下结果。\r\n\r\n我们先存了一个100这个数字，又存了101这个数字，因为之前初始化之后并没有进行别的存储，所以完成存储之后，因为按照之前的说法，数组的第1个元素应该放的100，第2个位置才是101，但是我们在储存的时候，是把要插入的数据插入到链表第一个元素的前面，所以从链表的角度看，101应该是第一个节点，100是第二个。那要怎么表现出来呢？结合我们上面说的，999这个位置的游标应该指向链表第一个节点，也就是游标应该为2，数组下标2的元素因为他是链表的第一个节点，所以他的游标应该指向链表第二个节点，也就是数组下标1。链表就两个节点，所以最后一个节点的游标要指向0. 然后数组下标0的位置的游标指向了下一个可用的存储位置3。\r\n\r\n![结果](https://upload-images.jianshu.io/upload_images/1491333-b4d1f2e78f1a9bfa.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)\r\n![结果](https://upload-images.jianshu.io/upload_images/1491333-43b9f5386a82de41.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)\r\n\r\n结果跟我们之前分析的是一致的。\r\n\r\n只要理清楚了这些思路之后，其他的代码看起来也就容易很多了。\r\n\r\n比如说下面这个计算链表长度的方法\r\n```objc\r\nint linkLength(StaticLinkList list[]) {\r\n    int j = 0;\r\n    int i = list[MAXSIZE-1].cur;\r\n    while (i) {\r\n        i = list[i].cur;\r\n        j ++;\r\n    }\r\n    return j;\r\n}\r\n```\r\n先拿到数组的最后一个元素游标的数值，如果是0，就说明还没有储存呢，索引链表长度就是0，如果已经储存过了，所以得到i的值就不是0，通过一个while循环，一个个的遍历链表结点，直到链表最后一个结点的游标又是0，跳出循环，然后通过一个j来标识循环次数，也就是链表长度。\r\n\r\n关于静态链表就说这么多吧，更多的内容大家可以上网搜一下。\r\n\r\n下面我把使用的代码放上，主要是实现了插入操作，删除暂时没做，大家可以看懂了插入然后自己写一下删除，代码上我尽可能详细的做了注释，大家可以看看代码 ~  \r\n```objc\r\n//  main.c\r\n//  链表\r\n//  Created by sunxiaobin on 2018/6/15.\r\n\r\n#include <stdio.h>\r\n#define MAXSIZE 1000\r\ntypedef int ElemType;\r\ntypedef struct {\r\n    ElemType data;\r\n    int cur;\r\n}StaticLinkList;\r\n\r\n// 声明\r\nvoid createLinkList(StaticLinkList list[]);\r\nint linkLength(StaticLinkList list[]);\r\nint Malloc_SLL(StaticLinkList list[]);\r\nint ListInsert(StaticLinkList L[], int i, ElemType e);\r\n\r\nint main(int argc, const char * argv[]) {\r\n    StaticLinkList list[MAXSIZE];\r\n    \r\n    // 初始化数组中的数据\r\n    createLinkList(list);\r\n    \r\n    for (int i = 0; i < 2; i ++) {\r\n        ListInsert(list, 1, 100+i);\r\n    } \r\n    return 0;\r\n}\r\n\r\nvoid createLinkList(StaticLinkList list[]){\r\n    int i;// i就代表数组下标\r\n    for (i = 0; i < MAXSIZE-1; i ++) {\r\n        list[i].cur = i + 1;  // cur存放的是下一个结点的下标\r\n    }\r\n    list[MAXSIZE-1].cur = 0; //\r\n    \r\n}\r\n\r\n// 求链表长度\r\nint linkLength(StaticLinkList list[]) {\r\n    int j = 0;\r\n    int i = list[MAXSIZE-1].cur;\r\n    while (i) {\r\n        i = list[i].cur;\r\n        j ++;\r\n    }   \r\n    return j;\r\n}\r\n\r\n// 得到备用链表的第一个元素下标\r\nint Malloc_SLL(StaticLinkList list[]) {\r\n    \r\n    int i = list[0].cur;\r\n    \r\n    if (list[0].cur)\r\n        // 更新头结点的游标, 原来头结点的游标指向i这个位置,\r\n        // 但是这个位置要进行了存储 , 被使用了,\r\n        // 头结点应该把游标更新到新的备用链表的第一个元素, 也就是刚刚使用了这个i位置的元素的游标指向的位置.\r\n        list[0].cur = list[i].cur;\r\n    \r\n    return i;\r\n}\r\n\r\n// 在静态链表L中第i个元素之前插入新的数据元素e\r\nint ListInsert(StaticLinkList list[], int i, ElemType e) {\r\n    \r\n    int k = MAXSIZE - 1; // 数组的最后一个元素\r\n    \r\n    //判断要插入的位置是不是合法范围\r\n    if (i<1 || i>linkLength(list)+1) return 0;\r\n    \r\n    int j = Malloc_SLL(list); // 得到备用链表的第一个元素下标\r\n    \r\n    if (j) {  // 如果元素存在,(不存在就说明数组已经满了)\r\n        \r\n        list[j].data = e;// 先把e存进来,然后通过改变某几个结点的游标\r\n        \r\n        // 这个for循环内, 如果是第一次存储的话根本不走\r\n        //\r\n        for (int l = 1; l<=i-1; l++) {\r\n            // 得到第i-1个结点在数组中的下标\r\n            k = list[k].cur;\r\n        }\r\n        \r\n        list[j].cur = list[k].cur; // 将第i-1个元素的cur设置为新加的这个结点的下标，将新加的这个结点的下标设置为之前第i-1个元素存储的cur值\r\n        list[k].cur = j;\r\n    \r\n        return 1;\r\n    } \r\n    return 0;    \r\n}\r\n\r\n```\r\n\r\n\r\n"}}
{"actor":{"display_login":"Sunxb"}}