1. 顺序存储线性表的缺点
上一篇讲了顺序存储线性表，实际上就是用数组的顺序来表达一个有顺序的一维数据集合。
但是数据这种存储结构存在一些问题：
容量有限，数组属于连续存储空间，不能太大，如果申请太大的连续数组空间，可能会GG，至于具体能申请多大，请大家试试，猫哥比较懒，此处就不试了
插入与删除速度慢。这个是肯定的啦，比如插入一个元素，后面所有的元素都得往后移动，删除一个元素，前面的元素都得往前移动。
咋办捏，有一个很朴素的想法就是，让前面一个人记住后面一个人，不用关心整体，只要前后关联就OK。这种数据结构即为链式存储线性表。
2. 链式存储线性表的实现原理
因为C语言支持指针啊，让前面一个记住后面一个，太简单了啊，直接让前面一个的指针指向后面一个完事。那第一个咋办捏，第一个没有前面一个啊，那也么事，我们直接定义一个头部指向第一个元素，也就是说头部实际上不是线性表的数据部分，但是它能把链式线性表关联出来。
就像火车头，虽然不拉乘客，但是能带着乘客去他们想去的地方。这个比喻实在太形象了，厉害炸了~
3. 链式存储线性表的操作
此处跟顺序线性表一模一样，因为都是线性表嘛，功能一样，只是存储结构不一样。
显示线性表元素个数
列出线性表的所有元素
获取指定位置元素
在指定位置插入元素
删除指定位置元素
清空线性表
4. 代码实现
话不多说，说多了上头。酒不多喝，喝多了会难受，直接上代码~
PS：我自己测试没发现BUG，但是不能保证肯定没有BUG…保佑我~！
/* * 链式存储线性表 * 作者:熊猫大大 * 时间:2019-09-25 */ #include<stdio.h> // 线性表的节点结构体 typedef struct { int data;//保存节点数据 struct Node *next;//指向下一个节点 }Node; // 获取元素个数 int getCount(Node *head) { int count = 0; Node* p = head;//定义一个指针首先指向头结点 while (p->next != NULL)//还有数据元素 { count++; p = p->next; } return count; } // 显示所有元素 void printList(Node *head) { int i; printf("\n所有元素:"); Node* p = head;//定义一个指针首先指向头结点 while (p->next != NULL) { p = p->next; printf("%d ", p->data); } } // 获取指定位置元素，返回值放入result指向元素，注意位置从0开始 int getData(Node *head, int index, int *result) { int i = 0;//当前位置 if (index < 0) { return 0; //位置不存在 } Node* p = head;//定义一个指针首先指向头结点 while (p->next != NULL) { p = p->next; if (i == index) { *result = p->data; } i++; } if (i >= index) //位置超限 { return 0; } return 1;//1表示成功 } // 插入元素 int insertData(Node *head, int index, int input) { int i = 0;//当前位置 Node* temp = (Node*)malloc(sizeof(Node));//临时节点 if (index < 0) { return 0; //位置不存在 } if (index == 0) //第一个位置插入元素 { temp->data = input; temp->next = head->next; head->next = temp; return; } Node* p = head;//定义一个指针首先指向头结点 while (p->next != NULL) { p = p->next; i++; if (i == index) {//找到插入位置 temp->data = input; temp->next = p->next; p->next = temp; return; } } if (i == index) //最后一个后面追加 { return 1; } else { return 0;//位置超限 } return 1; } // 删除指定位置元素 int deleteData(Node *head, int index) { int i = 0;//当前位置 if (index < 0) { return 0; //位置不存在 } Node* p = head;//定义一个指针首先指向头结点 Node* front = head;//记录前一个元素 while (p->next != NULL) { front = p; p = p->next; if (i == index) {//删除该元素 front->next = p->next;//跳过被删除元素 free(p);//释放 return; } i++; } if (i >= index) //位置超限 { return 0; } return 1;//1表示成功 } // 清空所有元素 int clearData(Node *head) { Node* p = head->next; Node* temp; while (p != NULL) { temp = p->next; free(p); p = temp; } head->next = NULL; return 1; } // 入口 int main() { Node head;//头部节点实际上就代表了一个链表 head.data = 0;//头部节点存储的数据没意义 head.next = NULL;//刚开始没有数据节点 int count = getCount(&head); printf("初始长度:%d\n", count); insertData(&head, 0, 1); insertData(&head, 1, 2); insertData(&head, 1, 3); count = getCount(&head); printf("新增后长度:%d\n", count); printList(&head); int result = 0; getData(&head, 2, &result); printf("位置2元素:%d\n", result); deleteData(&head, 0); printList(&head); clearData(&head); count = getCount(&head); printf("清空后长度:%d\n", count); return 1; }
