C++中如何建立一个顺序表.doc

C+中如何建立一个顺序表1. 准备数据2. 初始化顺序表3. 计算线性表的长度4. 插入结点5. 追加结点6. 删除结点7. 查找结点1. 按照序号查找结点2. 按照关键字查找结点8. 显示所有的结点9. 顺序表操作完整示例准备数据cpp view plaincopyprint?1. #define MAXLEN 100 /定义顺序表的最大长度 2. struct DATA 3. 4. char key10; /结点的关键字 5. char name20; 6. int age; 7. ; 8. struct SLType /定义顺序表结构 9. 10. DATA ListDataMAXLEN+1;/保存顺序表的结构数组 11. int ListLen; /顺序表已存结点的数量 12. ; #define MAXLEN 100/定义顺序表的最大长度struct DATAchar key10;/结点的关键字 char name20;int age;structSLType/定义顺序表结构 DATA ListDataMAXLEN+1;/保存顺序表的结构数组int ListLen;/顺序表已存结点的数量 ; 定义了顺序表的最大长度MAXLEN、顺序表数据元素的类型DATA以及顺序表的数据结构SLType。在数据结构SLType中，Listen为顺序表已存结点的数量，也就是当前顺序表的长度，ListData是一个结构数组，用来存放各个数据结点。我们认为该顺序表是一个班级学生的记录。其中，key为学号，name为学生的名称，age为年龄。因为数组都是从下标0开始的，为了使用方便，我们从下标1开始记录数据结点，下标0的位置不可用。初始化顺序表在使用顺序表之前，首先创建一个空的顺序表，也就是初始化顺序表。这里，在程序中只需设置顺序表的结点数量ListLen为0即可。这样，后面需要添加的数据元素将从顺序表的第一个位置存储。示例代码：cpp view plaincopyprint?1. void SLInit(SLType * SL) /初始化顺序表 2. 3. SL-Listlen=0; 4. void SLInit(SLType * SL)/初始化顺序表SL-Listlen=0; 计算线性表的长度计算线性表的长度也就是计算线性表中结点的个数，由于我们在SLType中定义了ListLen来表示结点的数量，所以我们只需要获得这个变量的值即可。cpp view plaincopyprint?1. int SLLenght(SLType *SL) 2. 3. return(SL-ListLen); /返回顺序表的元素数量 4. int SLLenght(SLType *SL)return(SL-ListLen);/返回顺序表的元素数量 插入结点插入节点就是在线性表L的第i个位置上插入一个新的结点，使其后的结点编号依次加1。这时，插入一个新节点之后，线性表L的长度将变为n+1。插入结点操作的难点在于随后的每个结点数据都要向后移动，计算机比较大，示例代码如下：cpp view plaincopyprint?1. int SLInsert(SLType *SL,int n,DATA data) 2. 3. int i; 4. if(SL-ListLen=MAXLEN) /顺序表结点数量已超过最大数量 5. 6. cout顺序表已满，不能插入结点！endl; 7. return 0; /返回0表示插入不成功 8. 9. if(nSL-ListLen) /插入结点的序号不合法 10. 11. cout插入序号错误！ListLen;i=n;i-) /将顺序表中的数据向后移动 15. 16. SL-ListDatai+1=SL-ListDatai; 17. 18. SL-ListDatan=data; 19. SL-ListLen+; 20. return 1; 21. int SLInsert(SLType *SL,int n,DATA data)int i;if(SL-ListLen=MAXLEN)/顺序表结点数量已超过最大数量cout顺序表已满，不能插入结点！endl;return 0;/返回0表示插入不成功 if(nSL-ListLen)/插入结点的序号不合法 cout插入序号错误！ListLen;i=n;i-)/将顺序表中的数据向后移动SL-ListDatai+1=SL-ListDatai;SL-ListDatan=data;SL-ListLen+;return 1; 在程序中首先判断顺序表结点数量时候已超过最大数量，以及插入点的序号是否正确。前面条件都瞒住以后，便将顺序表中的数据向后移动，同时插入结点，并更新结点数量ListLen。追加结点追加结点就是在顺序表的尾部插入结点，因此不必进行大量数据的移动，代码实现与插入结点相比就要简单的多。cpp view plaincopyprint?1. int SLAdd(SLType * SL,DATA data) 2. 3. if(SL-ListLen=MAXLEN) 4. 5. cout顺序表已满，不能再添加结点了！ListData+SL-ListLen=data; 9. return 1; 10. int SLAdd(SLType * SL,DATA data)if(SL-ListLen=MAXLEN)cout顺序表已满，不能再添加结点了！ListData+SL-ListLen=data;return 1;删除结点删除结点就是删除线性表L中的第i个结点，使得其后的所有节点编号依次减1.这是，删除一个结点之后，线性表L的长度将变为n-1。删除结点和插入结点类似，都需要进行大量数据的移动。cpp view plaincopyprint?1. int SLDelete(SLType *SL,int n) /删除顺序表中的数据元素 2. 3. int i; 4. if(nSL-ListLen) /删除结点的序号不合法 5. 6. cout删除序号错误！endl; 7. return 0; 8. 9. for(i=n;iListLen;i+)/将顺序表中的数据向前移动 10. 11. SL-ListDatai=SL-ListDatai+1; 12. 13. SL-ListLen-; /顺序表元素数量减1 14. return 1; /成功删除返回1 15. int SLDelete(SLType *SL,int n)/删除顺序表中的数据元素int i;if(nSL-ListLen)/删除结点的序号不合法 cout删除序号错误！endl;return 0;for(i=n;iListLen;i+)/将顺序表中的数据向前移动 SL-ListDatai=SL-ListDatai+1; SL-ListLen-;/顺序表元素数量减1 return 1;/成功删除返回1 查找结点查找节点就是在线性表L中查找值为x的结点，并返回该节点在线性表L中的位置。如果在线性表中没有找到值为x的结点，则返回一个错误标志。根据x的类型不同，查找结点可以分为：按照序号查找结点对于一个顺序表，序号就是数据元素在数组中的位置，也就是数组的下标标号。按照序号查找结点是顺序表查找结点最常用的方法，这是因为顺序表的存储本身就是一个数组，示例代码如下：cpp view plaincopyprint?1. DATA * SLFindByNum(SLType *SL,int n)/根据呼号返回数据元素 2. 3. if(nSL-ListLen) /查询结点的序号不合法 4. 5. cout查询序号错误！ListDatan); 9. DATA * SLFindByNum(SLType *SL,int n)/根据呼号返回数据元素if(nSL-ListLen)/查询结点的序号不合法 cout查询序号错误！ListDatan); 按照关键字查找结点关键字可以是数据元素中的任意一项。这里以key关键字为例进行介绍，例如，可以通过key查找学生的信息。示例代码如下：cpp view plaincopyprint?1. int SLFindByCont(SLType * SL,char *key)/按关键字查询结点 2. 3. int i; 4. for(i=1;iListLen;i+) 5. 6. if(strcmp(SL-ListDatai.key,key)=0)/如果找到结点 7. 8. return i; 9. 10. 11. return 0; /在整个表中都没有找到，返回0 int SLFindByCont(SLType * SL,char *key)/按关键字查询结点 int i;for(i=1;iListLen;i+)if(strcmp(SL-ListDatai.key,key)=0)/如果找到结点 return i;return 0;/在整个表中都没有找到，返回0 显示所有的结点示例代码如下cpp view plaincopyprint?1. void SLALL(SLType *SL) 2. 3. int i; 4. for(i=1;iListLen;i+) 5. 6. coutkey:ListDatai.keyendl; 7. coutname:ListDendl; 8. coutage:ListDatai.ageendl; 9. cout=endl; 10. 11. void SLALL(SLType *SL)int i;for(i=1;iListLen;i+)coutkey:ListDatai.keyendl;coutname:ListDendl;coutage:ListDatai.ageendl;cout=endl; 顺序表操作完整示例：基本上就是把上面的函数放到一块，集中展示了一下功能，代码有些长，请耐心阅读.cpp view plaincopyprint?1. #include 2. #include 3. using namespace std; 4. #define MAXLEN 100 /定义顺序表的最大长度 5. /*顺序表的定义部分*/ 6. struct DATA 7. 8. string key; /结点的关键字 9. string name; 10. int age; 11. ; 12. struct SLType /定义顺序表结构 13. 14. DATA ListDataMAXLEN+1;/保存顺序表的结构数组 15. int ListLen; /顺序表已存结点的数量 16. ; 17. /*顺序表的初始化函数*/ 18. void SLInit(SLType * SL) /初始化顺序表 19. 20. SL-ListLen=0; 21. 22. /*计算线性表的长度*/ 23. int SLLenght(SLType *SL) 24. 25. return(SL-ListLen); /返回顺序表的元素数量 26. 27. /*插入结点*/ 28. int SLInsert(SLType *SL,int n,DATA data) 29. 30. int i; 31. if(SL-ListLen=MAXLEN) /顺序表结点数量已超过最大数量 32. 33. cout顺序表已满，不能插入结点！endl; 34. return 0; /返回0表示插入不成功 35. 36. if(nSL-ListLen) /插入结点的序号不合法 37. 38. cout插入序号错误！ListLen;i=n;i-) /将顺序表中的数据向后移动 42. 43. SL-ListDatai+1=SL-ListDatai; 44. 45. SL-ListDatan=data; 46. SL-ListLen+; 47. return 1; /成功插入，返回1 48. 49. /*追加结点*/ 50. int SLAdd(SLType * SL,DATA data) 51. 52. if(SL-ListLen=MAXLEN) 53. 54. cout顺序表已满，不能再添加结点了！ListData+SL-ListLen=data; 58. return 1; 59. 60. /*删除结点*/ 61. int SLDelete(SLType *SL,int n) /删除顺序表中的数据元素 62. 63. int i; 64. if(nSL-ListLen) /删除结点的序号不合法 65. 66. cout删除序号错误！endl; 67. return 0; 68. 69. for(i=n;iListLen;i+)/将顺序表中的数据向前移动 70. 71. SL-ListDatai=SL-ListDatai+1; 72. 73. SL-ListLen-; /顺序表元素数量减1 74. return 1; /成功删除返回1 75. 76. /*按照序号查找结点*/ 77. DATA * SLFindByNum(SLType *SL,int n)/根据序号返回数据元素 78. 79. if(nSL-ListLen) /查询结点的序号不合法 80. 81. cout查询序号错误！ListDatan); 85. 86. /*按照关键字查找结点*/ 87. DATA *SLFindByCont(SLType * SL,string name)/按关键字查询结点 88. 89. int i; 90. for(i=1;iListLen;i+) 91. 92. if(SL-ListD=name)/如果找到结点 93. 94. return &(SL-ListDatai); 95. 96. 97. return 0; /在整个表中都没有找到，返回0 98. 99. /*显示所有的结点*/ 100. void SLALL(SLType *SL) 101. 102. int i; 103. for(i=1;iListLen;i+) 104. 105. coutkey:ListDatai.key,name:ListD,age:ListDatai.ageendl; 106. 107. 108. int main() 109. 110. int i; 111. SLType SL; /定义顺序表变量 112. DATA data; /定义结点保存数据类型变量 113. DATA *pdata;/定义指向结点的指针变量 114. string name; 115. cout顺序表操作演示：endl; 116. SLInit(&SL);/初始化顺序表 117. do 118. /循环添加结点数据 119. data.age; 121. if(data.age) /若年龄不为0 122. 123. if(!SLAdd(&SL,data)/若添加结点失败 124. 125. break; /退出循环 126. 127. else 128. 129. break; 130. 131. while(1); 132. cout顺序表中的结点顺序为： endl; 133. SLALL(&SL); /显示所有的结点 134. couti; 136. pdata=SLFindByNum(&SL,i);/按序号查找结点 137. if(pdata) 138. 139. cout第i个结点为：key:key,name:name,age:ageendl; 140. 141. coutname; 143. pdata=SLFindByCont(&SL,name); 144. if(pdata) 145. 146. coutkey:key,name:name,age:ageendl; 147. 148. couti; 150. if(SLDelete(&SL,i) 151. 152. cout数据删除成功endl; 153. SLALL(&SL); 154. 155. couti; 157. cout请输入第i号结点的key，name，以及data.age; 159. if(SLInsert(&SL,i,data) 160. 161. cout插入数据成功endl; 162. SLALL(&SL); 163. 164. return 0; 165. #include#includeusing namespace std;#define MAXLEN 100/定义顺序表的最大长度/*顺序表的定义部分*/ struct DATAstring key;/结点的关键字 string name;int age;structSLType/定义顺序表结构 DATA ListDataMAXLEN+1;/保存顺序表的结构数组int ListLen;/顺序表已存结点的数量 ; /*顺序表的初始化函数*/ void SLInit(SLType * SL)/初始化顺序表SL-ListLen=0; /*计算线性表的长度*/int SLLenght(SLType *SL)return(SL-ListLen);/返回顺序表的元素数量 /*插入结点*/int SLInsert(SLType *SL,int n,DATA data)int i;if(SL-ListLen=MAXLEN)/顺序表结点数量已超过最大数量cout顺序表已满，不能插入结点！endl;return 0;/返回0表示插入不成功 if(nSL-ListLen)/插入结点的序号不合法 cout插入序号错误！ListLen;i=n;i-)/将顺序表中的数据向后移动SL-ListDatai+1=SL-ListDatai;SL-ListDatan=data;SL-ListLen+;return 1; /成功插入，返回1 /*追加结点*/ int SLAdd(SLType * SL,DATA data)if(SL-ListLen=MAXLEN)cout顺序表已满，不能再添加结点了！ListData+SL-ListLen=data;return 1;/*删除结点*/ int SLDelete(SLType *SL,int n)/删除顺序表中的数据元素int i;if(nSL-ListLen)/删除结点的序号不合法 cout删除序号错误！endl;return 0;for(i=n;iListLen;i+)/将顺序表中的数据向前移动 SL-ListDatai=SL-ListDatai+1; SL-ListLen-;/顺序表元素数量减1 return 1;/成功删除返回1 /*按照序号查找结点*/DATA * SLFindByNum(SLType *SL,int n)/根据序号返回数据元素if(nSL-ListLen)/查询结点的序号不合法 cout查询序号错误！ListDatan); /*按照关键字查找结点*/DATA *SLFindByCont(SLType * SL,strin