大家好，我是良哥，眼见期末考试越来越近，但由于我们数据结构老师技术太过厉害，导致全班都处于不听不听，王八念经的状态，所以今天我开始自学数据结构，并对其中难点部分进行C++编程实现，以此打破老师所谓的给你们正确代码你们就不好好学的理由。他的代码都是用word打的，‘=’打成‘-’，还自称自己是专家，技术证明一切，计算机不存在老专家和经典。最新才最具有生命力，不进步就是外行，长江后浪推前浪，前浪死在沙滩上，欧耶！
首先我们来了解下静态链表，什么是静态链表？我们知道，链表是动态结构，通过指针将数据串联起来，只要内存有空间就可以继续分配链表，没有固定的长度限制，是一种非常好用存储结构，而且从操作系统原理上来说，他可以利用内存的碎片化空间，并且更容易找到合适空间分配，减少操作系统对内存空闲区域的检索时间，在一定程度上提高了程序的速度，但是浪费了一定的空间用来存放指针，相对来说，牺牲空间，提升时间，对于较大内存调入来说，这个牺牲还是比较划算的。
那么什么是静态链表？我们指导，跟链表对应的是数组，在内存划分一段连续空间，用来存放数据。优点是操作简单，寻址快，但缺点同样要命。首先数组要求在内存划分连续区域，只能使用较大的连续区域，这样在一定程度上增加了操作系统的负担，而且，连续区域不好找啊，划分连续区域一定程度上就会造成内存碎片化，造成资源浪费。再考虑数组大小固定，扩容很麻烦，所以一般程序员会设定一个较大的空间，以防止内存溢出。但是如果用户使用的数据量较小，就会造成浪费，同时也可能会造成内存溢出，导致程序崩溃，也给计算机安全造成危害。不过对于小数据，使用数组的确是方便快捷。
而我们所讨论的静态链表，简直就是逆天的存在，将数组与链表结合起来，各取其缺点……，或许你内心一万只草泥马在呼伦贝尔大草原上狂野奔腾，why ？猴子请来的逗比吗？事实上，为了使用链表，在一些语言中是不能使用指针或者链表的，而为了使用链表，我们不得不把数组当链表用。
静态链表：
1.定义结构体：SLinkList
typedef struct SLinkList { int date;//存放数据 int next;//指向下一个节点 }SLinkList;我们知道，一般链表指向下一个节点的是指针，这个为什么是数字？原因是他要记录下一个节点在数组中的位置。并且我们约定，指针位为-2时，代表此位为空，指针位为-1时，代表他是链表末节点。
2.为静态链表划分空间
//为静态链表划分空间 SLinkList *newSl(int n) { SLinkList* a = new SLinkList[n]; for (int i = 0; i < n; i++) { a[i].date = 0; a[i].next = -2; } return a; }3.功能函数 返回静态链表中的一个空位地址（以整形数字存储） //对静态链表空位置进行检索 return n,n为数组长度,-1为无空位 int nothing_num(SLinkList *a, int n) { for (int i = 0; i < n; i++) { if (a[i].next == -2) return i; } return -1; }4.功能函数 返回静态链表的末结点 //对静态链表末节点进行检索，返回值为-1为检索失败 int end_num(SLinkList* a, int n) { for (int i = 0; i < n; i++) { if (a[i].next == -1) return i; } if (a[0].next == -2) return 0; return -1; }返回值为‘-1’时，代表检索失败或是链表损坏。5.功能函数 对静态链表进行初始或续写入
//对静态链表进行写入或补充写入 bool write(SLinkList* a, int *b, int nS,int nInt) { int End_num = end_num(a, nS); int No_num = nothing_num(a, nS); for (int i = 0; i < nInt; i++) { if (End_num == -1 || No_num == -1) return false; a[End_num].next = No_num; a[No_num].date = b[i]; a[No_num].next = -1; End_num = end_num(a, nS); No_num = nothing_num(a, nS); } return true; }返回值为确定写入是否成功6.功能函数 查找数值为num的节点位置
//查找数值为num的节点 int ifind(SLinkList* a, int n, int num) { for (int i = 0; i < n; i++) { if (a[i].date == num) return i; } return -1; }返回值为-1代表查找失败7.功能函数 插入结点 poineer为其前结点位置，num为插入值
//插入结点 bool interposition(SLinkList* a, int n, int poineer,int num) { int No_num = nothing_num(a, n); if (No_num == -1)return false; a[No_num].date = num; a[No_num].next = a[poineer].next; a[poineer].next = No_num; return true; } 8.功能函数 找到指向结点为NO的结点 //找到指向节点NO的结点 int Jfind(SLinkList* a, int n, int NO) { for (int i = 0; i < n; i++) { if (a[i].next == NO) return i; } return -1; }9.功能函数 删除某一结点 //删除节点 bool idelete(SLinkList* a, int n,int NO) { if (NO > n || NO == n) return false; int J = Jfind(a, n, NO); if (J == -1) return false; a[J].next = a[NO].next; a[NO].next = -2; a[NO].date = 0; return true; } 10.测试用主函数 int main() { SLinkList *a = newSl(20); int b[10] = { 1,2,3,4,5,6,7,8,9,10 }; bool pd = write(a, b, 20, 10); int ii = 0; if (pd == false) cout << "写入失败" << endl; else { cout << "写入成功，写入结果为：" << endl; while (a[ii].next != -1) { cout << a[ii].date << '\t'; ii = a[ii].next; } cout << endl; cout << "测试查找结点，正确答案为：4 测试结果为" << ifind(a, 20, 5); cout << endl; cout << "测试插入函数" << endl; if (!interposition(a, 20, 2, 11)) cout << "插入失败" << endl; else { cout << "插入结果为：" << endl; ii = 0; while (a[ii].next != -1) { cout << a[ii].date << '\t'; ii = a[ii].next; } } cout << endl; cout << "测试删除函数" << endl; if (idelete(a, 20, 10)) { cout << "删除结果为：" << endl; ii = 0; while (a[ii].next != -1) { cout << a[ii].date << '\t'; ii = a[ii].next; } } else cout << "删除失败" << endl; cout << endl; } system("pause"); return 0; }
附赠整个解决方案，使用VS2015编辑 // SLinkList.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include"iostream" using namespace std; typedef struct SLinkList { int date; int next; }SLinkList; //生成新的静态链表 SLinkList *newSl(int n) { SLinkList* a = new SLinkList[n]; for (int i = 0; i < n; i++) { a[i].date = 0; a[i].next = -2; } return a; } //对静态链表空位置进行检索 return n,n为位置,-1为无空位 int nothing_num(SLinkList *a, int n) { for (int i = 0; i < n; i++) { if (a[i].next == -2) return i; } return -1; } //对静态链表末节点进行检索，返回值为-1为检索失败 int end_num(SLinkList* a, int n) { for (int i = 0; i < n; i++) { if (a[i].next == -1) return i; } for (int i = 0; i < n; i++) { if (a[i].next != -2) return -1; } return 0; } //对静态链表进行写入或补充写入 bool write(SLinkList* a, int *b, int nS,int nInt) { int End_num = end_num(a, nS); int No_num = nothing_num(a, nS); for (int i = 0; i < nInt; i++) { if (End_num == -1 || No_num == -1) return false; a[End_num].next = No_num; a[No_num].date = b[i]; a[No_num].next = -1; End_num = end_num(a, nS); No_num = nothing_num(a, nS); } return true; } //查找数值为num的节点 int ifind(SLinkList* a, int n, int num) { for (int i = 0; i < n; i++) { if (a[i].date == num) return i; } return -1; } //插入结点 bool interposition(SLinkList* a, int n, int poineer,int num) { int No_num = nothing_num(a, n); if (No_num == -1)return false; a[No_num].date = num; a[No_num].next = a[poineer].next; a[poineer].next = No_num; return true; } //找到指向节点NO的结点 int Jfind(SLinkList* a, int n, int NO) { for (int i = 0; i < n; i++) { if (a[i].next == NO) return i; } return -1; } //删除节点 bool idelete(SLinkList* a, int n,int NO) { if (NO > n || NO == n) return false; int J = Jfind(a, n, NO); if (J == -1) return false; a[J].next = a[NO].next; a[NO].next = -2; a[NO].date = 0; return true; } int main() { SLinkList *a = newSl(20); int b[10] = { 1,2,3,4,5,6,7,8,9,10 }; bool pd = write(a, b, 20, 10); int ii = 0; if (pd == false) cout << "写入失败" << endl; else { cout << "写入成功，写入结果为：" << endl; while (a[ii].next != -1) { cout << a[ii].date << '\t'; ii = a[ii].next; } cout << endl; cout << "测试查找结点，正确答案为：4 测试结果为" << ifind(a, 20, 5); cout << endl; cout << "测试插入函数" << endl; if (!interposition(a, 20, 2, 11)) cout << "插入失败" << endl; else { cout << "插入结果为：" << endl; ii = 0; while (a[ii].next != -1) { cout << a[ii].date << '\t'; ii = a[ii].next; } } cout << endl; cout << "测试删除函数" << endl; if (idelete(a, 20, 10)) { cout << "删除结果为：" << endl; ii = 0; while (a[ii].next != -1) { cout << a[ii].date << '\t'; ii = a[ii].next; } } else cout << "删除失败" << endl; cout << endl; } system("pause"); return 0; } 本文为作者原创，任何形式的引用、转载等操作请提前获得作者授权，未经授权，禁止以任何形式引用或转载此文。
