这周已经是第九周了，为了期末的时候能够兼顾其他课程的复习，所以提早对数据结构这门课进行回顾总结。
数据结构忽略前面两章的C语言基础(有机会以后再补)，直接从第三章最简单的线性表开始。
线性表的第一种结构是 顺序表 。
首先定义一个结构体，
1. #define MAXX 1000 2. typedef int lei; 3. struct ss 4. { 5. lei data[MAXX]; 6. int len; 7. };
之所以用#define 定义MAXX ，是因为 需要改变 这个线性表大小的时候 只需要在这个语句改变大小即可 不需要再从整段代码再逐一修改。
typedef的意思是取别名。把lei这个小名 给int，作用同上 修改线性表数据类型的时候可以直接改动
这个结构体里面有两部分，一部分是数据，第二部分是长度，初始化为-1.
（ps：为什么从-1开始，因为数组是从0开始的）
顺序表根据《数据结构》这本书 需要会写初始化、指定位置插入、查找、删除、取长度、判断是否为空的函数。
首先是初始化函数。
初始化一个顺序表，只要用c++的new函数 ，new一个顺序表就可以，把长度初始化为-1，然后返回首地址就行了。
1. ss *chushihua() 2. { 3. ss *L; 4. L=new ss; 5. L->len=-1; 6. return L; 7. }
第二个是查找函数，查找函数只要按照o~len的顺序遍历过去，凡是找到就返回，找不到就返回一个负数，思路简单粗暴，时间复杂度是o(n)。
ps:不考虑有数据重复的情况.
1. int find(ss *L,lei X) 2. { 3. for(int i=0;i<=L->len;i++) 4. { 5. if(L->data[i]==X) return i; 6. } 7. return -1; 8. }
第三个是插入函数。
插入只需要判断是否插入成功就可以，所以用bool类型作为返回值。
需要三个参数，顺序表的首地址、插入的数据、插入的位置。
需要考虑两种极端情况：第一种顺序表已经满了，第二种插入的位置越界。
否则就正常插入，把插入位置的后面元素往后移，再在插入的位置插入该插的数，然后让顺序表的长度+1即可。
1. bool charu(ss* L,lei shu,int weizhi) 2. { 3. if(L->len==MAXX-1) 4. { 5. cout<<"顺序表已满"<<endl; 6. return false; 7. } 8. if(weizhi<0||weizhi>L->len+1) 9. { 10. cout<<"插入位置错误"<<endl; 11. return false; 12. } 13. for(int i=L->len;i>=weizhi;i--) 14. { 15. L->data[i+1]=L->data[i]; 16. } 17. L->data[weizhi]=shu; 18. L->len++; 19. return true; 20. }
第四个是删除函数。
同上为bool类型，参数为顺序表的首地址和需要删除的位置。
考虑一种极端情况，如果需要删除的位置为空。
删除只需要把后面的元素往前移，覆盖掉前面的元素就可以，在把长度-1.
ps：此时L->[len]的数据还是存在，但是不用管。
1. bool shanchu(ss *L,int weizhi) 2. { 3. if(weizhi<0||weizhi>L->len) 4. { 5. cout<<"位置越界"<<endl; 6. return false; 7. } 8. for(int i=weizhi;i<=L->len;i++) 9. { 10. L->data[i]=L->data[i+1]; 11. } 12. L->len--; 13. return true; 14. }
最后一个最简单，就是判断是否为空。
只要判断他的长度是否为初始化的-1即可。
1. bool empty(ss *L) 2. { 3. if(L->len==-1) return true; 4. return false; 5. }
所以给出总的代码：
1. #include<iostream> 2. #include<algorithm> 3. #include <cstring> 4. using namespace std; 5. #define MAXX 1000 6. typedef int lei; 7. struct ss 8. { 9. lei data[MAXX]; 10. int len; 11. }; 12. ss *chushihua() 13. { 14. ss *L; 15. L=new ss; 16. L->len=-1; 17. return L; 18. } 19. int find(ss *L,lei X) 20. { 21. for(int i=0;i<=L->len;i++) 22. { 23. if(L->data[i]==X) return i; 24. } 25. return -1; 26. } 27. bool charu(ss* L,lei shu,int weizhi) 28. { 29. if(L->len==MAXX-1) 30. { 31. cout<<"顺序表已满"<<endl; 32. return false; 33. } 34. if(weizhi<0||weizhi>L->len+1) 35. { 36. cout<<"插入位置错误"<<endl; 37. return false; 38. } 39. for(int i=L->len;i>=weizhi;i--) 40. { 41. L->data[i+1]=L->data[i]; 42. } 43. L->data[weizhi]=shu; 44. L->len++; 45. return true; 46. } 47. bool shanchu(ss *L,int weizhi) 48. { 49. if(weizhi<0||weizhi>L->len) 50. { 51. cout<<"位置越界"<<endl; 52. return false; 53. } 54. for(int i=weizhi;i<=L->len;i++) 55. { 56. L->data[i]=L->data[i+1]; 57. } 58. L->len--; 59. return true; 60. } 61. bool empty(ss *L) 62. { 63. if(L->len==-1) return true; 64. return false; 65. } 66. int main() 67. { 68. ss *L; 69. L=chushihua(); 70. charu(L,1,0); 71. charu(L,2,1); 72. cout<<"1在第"<<find(L,1)<<"个位置"<<endl; 73. shanchu(L,1); 74. shanchu(L,0); 75. cout<<"下面判断是否为空，空为1"<<endl; 76. cout<<empty(L)<<endl; 77. return 0; 78. }
顺序表不难，明天复习链表。
