当前位置:   article > 正文

数据结构(Data Structure)——线性表ADT(C/C++语言)_返回l中第1个与e满足关系compore()的数据元素的位序。 若这样的数据元素不存

返回l中第1个与e满足关系compore()的数据元素的位序。 若这样的数据元素不存

1.线性表定义:

       线性表(linear list)是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号,其具体含义在不同的情况下一般不同。
       在稍复杂的线性表中,一个数据元素可由多个数据项(item)组成,此种情况下常把数据元素称为记录(record),含有大量记录的线性表又称文件(file)。
       线性表中的个数n定义为线性表的长度,n=0时称为空表。在非空表中每个数据元素都有一个确定的位置,如用ai表示数据元素,则i称为数据元素ai在线性表中的位序。

       线性表的相邻元素之间存在着序偶关系。如用(a1,…,ai-1,ai,ai+1,…,an)表示一个顺序表,则表中ai-1领先于ai,ai领先于ai+1,称ai-1是ai的直接前驱元素,ai+1是ai的直接后继元素。当i=1,2,…,n-1时,ai有且仅有一个直接后继,当i=2,3,…,n时,ai有且仅有一个直接前驱。

初期工作:

  1. #define OK 1
  2. #define ERROR 0
  3. #define OVERFLOW -1
  4. #define TRUE 1
  5. #define FALSE 0
  6. #define List_INIT_SPACE 100 //存储空间初始分配量
  7. #define List_INC_SPACE 10 //存储空间分配增量
  8. typedef int ElemType;//指定顺序表中数据类型
  9. typedef int Status;

线性表定义:

  1. typedef struct
  2. {
  3. ElemType *elem; //存储空间基址
  4. int length; //当前长度
  5. int listsize; //当前分配的存储容量(以sizeof(ElemType)为单位)
  6. }List;

2.基本操作:

单个线性表的构造、销毁、清空、判空、返回长度、返回定位、返回前驱、返回后继、插入、删除、遍历。

  1. /*操作结果:构造一个空的线性表。*/
  2. Status InitList(List &L);
  3. /*初始条件:线性表L已存在。*/
  4. /*操作结果:销毁线性表L。*/
  5. Status DestroyList(List &L);
  6. /*初始条件:线性表L已存在。*/
  7. /*操作结果:将L置为空表。*/
  8. Status ClearList(List &L);
  9. /*初始条件:线性表L已存在。*/
  10. /*操作结果:若L为空,则返回TRUE,否则返回FALSE。*/
  11. Status ListEmpty(List &L);
  12. /*初始条件:线性表L已存在。*/
  13. /*操作结果:返回L中数据元素个数。*/
  14. Status ListLength(List &L);
  15. /*初始条件:线性表L已存在,1≤i≤ListLength(L)。*/
  16. /*操作结果:用e返回L中第i个元素的值。*/
  17. Status GetElem(List L, int i, Status &e);
  18. /*初始条件:线性表L已存在,compare()是数据元素判断函数。*/
  19. /*操作结果:返回L中第1个与e满足关系compaer()的数据元素的位序。若这样的数据元素不存在,则返回0。*/
  20. Status LocateElem(List L, Status e, Status(*compare)(const void *, const void *));
  21. /*初始条件:线性表L已存在。*/
  22. /*操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败,pre_e无定义。*/
  23. Status PriorElem(List L, Status cur_e, Status &pre_e);
  24. /*初始条件:线性表L已存在。*/
  25. /*操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后续,否则操作失败,next_e无定义。*/
  26. Status NextElem(List L, Status cur_e, Status &next_e);
  27. /*初始条件:线性表L已存在,1≤i≤ListLength(L)+1。*/
  28. /*操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1。*/
  29. Status ListInsert(List &L, int i, Status e);
  30. /*初始条件:线性表L已存在且非空,1≤i≤ListLength(L)。*/
  31. /*操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1。*/
  32. Status ListDelete(List &L, int i, Status &e);
  33. /*初始条件:线性表L已存在。*/
  34. /*操作结果:依次对L的每个数据元素调用函数visit()。一旦visit()操作失败,则操作失败。*/
  35. Status ListTraverse(List L, Status(*visit)());

3.具体函数的实现:

构造一个空的线性表L:

  1. /*构造一个空的线性表L*/
  2. /*操作结果:构造一个空的线性表。*/
  3. Status InitList(List &L)
  4. {
  5. L.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
  6. if (!L.elem) exit(OVERFLOW);//内存申请失败,异常退出
  7. L.length = 0;//空表长度为0
  8. L.listsize = LIST_INIT_SIZE;
  9. printf("构造一个空的线性表L成功!\n");
  10. return OK;
  11. }


销毁线性表L:

  1. /*销毁线性表L*/
  2. /*初始条件:线性表L已存在。*/
  3. /*操作结果:销毁线性表L。*/
  4. Status DestroyList(List &L)
  5. {
  6. if (L.elem)free(L.elem);//释放内存空间
  7. L.elem = NULL;
  8. L.length = 0;
  9. L.listsize = 0;
  10. return OK;
  11. }


将L置为空表:

  1. /*初始条件:线性表L已存在。*/
  2. /*操作结果:将L置为空表。*/
  3. Status ClearList(List &L)
  4. {
  5. L.length = 0;
  6. return OK;
  7. }


判断线性表L是否为空:

  1. /*判断线性表是否为空*/
  2. /*初始条件:线性表L已存在。*/
  3. /*操作结果:若L为空,则返回TRUE,否则返回FALSE。*/
  4. Status ListEmpty(List &L)
  5. {
  6. if (!L.length)return TRUE;
  7. else return FALSE;
  8. }


返回L中数据元素个数:

  1. /*初始条件:线性表L已存在。*/
  2. /*操作结果:返回L中数据元素个数。*/
  3. Status ListLength(List &L)
  4. {
  5. return L.length;
  6. }

用e返回L中第i个元素的值:

  1. /*初始条件:线性表L已存在,1≤i≤ListLength(L)。*/
  2. /*操作结果:用e返回L中第i个元素的值。*/
  3. Status GetElem(List L, int i, Status &e)
  4. {
  5. if (i<1 || i>L.length)return ERROR;
  6. else
  7. {
  8. e = L.elem[i - 1];
  9. return OK;
  10. }
  11. }

返回L中第1个与e满足关系compaer()的数据元素的位序:

  1. /*初始条件:线性表L已存在,compare()是数据元素判断函数。*/
  2. /*操作结果:返回L中第1个与e满足关系compaer()的数据元素的位序。若这样的数据元素不存在,则返回0。*/
  3. Status LocateElem(List L, Status e, Status(*compare)(ElemType, ElemType))
  4. {
  5. ElemType i, *p;
  6. i = 1; //i的初值为第一个元素的位序
  7. p = L.elem; //p的初值为第一个元素的存储位置
  8. while (i <= L.length&&!(*compare)(*p++, e)) ++i;
  9. if (i <= L.length)return i;
  10. else return 0;
  11. }

返回指定元素的前驱:

  1. /*初始条件:线性表L已存在。*/
  2. /*操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败,pre_e无定义。*/
  3. Status PriorElem(List L, Status cur_e, Status &pre_e)
  4. {
  5. for (int i = 1; i < L.length; i++)
  6. {
  7. if (L.elem[i]==cur_e)
  8. {
  9. pre_e = L.elem[i - 1];
  10. return OK;
  11. }
  12. else
  13. {
  14. if (i >= L.length) return ERROR;
  15. }
  16. }
  17. }

返回指定元素的后继:

  1. /*初始条件:线性表L已存在。*/
  2. /*操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后续,否则操作失败,next_e无定义。*/
  3. Status NextElem(List L, Status cur_e, Status &next_e)
  4. {
  5. for (int i = 0; i < L.length-1; i++)
  6. {
  7. if (L.elem[i] == cur_e)
  8. {
  9. next_e = L.elem[i + 1];
  10. return OK;
  11. }
  12. else
  13. {
  14. if (i >= L.length-1)
  15. {
  16. return ERROR;
  17. }
  18. }
  19. }
  20. }


在L中第i个位置之前插入新的数据元素e:

  1. /*初始条件:线性表L已存在,1≤i≤ListLength(L)+1。*/
  2. /*操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1。*/
  3. Status ListInsert(List &L, int i, Status e)
  4. {
  5. ElemType *q, *p, *newbase;
  6. if (i<1 || i>L.length + 1) return ERROR;//i值不合法
  7. if (L.length>=L.listsize) //当前存储空间已满,增加分配
  8. {
  9. newbase = (ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT)*sizeof(ElemType));
  10. if (!newbase) exit(OVERFLOW); //存储分配失败
  11. L.elem = newbase; //新基址
  12. L.listsize += LISTINCREMENT; //增加存储容量
  13. }
  14. q = &(L.elem[i - 1]); //q为插入位置
  15. for (p = &(L.elem[L.length - 1]); p >= q; --p)
  16. {
  17. *(p + 1) = *p; //将插入位置及之后的元素右移
  18. }
  19. *q = e; //插入e
  20. ++L.length; //表长增1
  21. return OK;
  22. }

删除L的第i个数据元素:

  1. /*初始条件:线性表L已存在且非空,1≤i≤ListLength(L)。*/
  2. /*操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1。*/
  3. Status ListDelete(List &L, int i, Status &e)
  4. {
  5. ElemType *q, *p;
  6. if (i<1 || i>L.length)return ERROR; //i值不合法
  7. p = &(L.elem[i - 1]); //p为被删除元素位置
  8. e = *p; //将删除元素的值赋给e
  9. q = L.elem + L.length - 1; //表尾元素的位置
  10. for (++p; p <= q; ++p) //将被删除元素之后的元素左移
  11. {
  12. *(p - 1) = *(p);
  13. }
  14. --L.length; //表长减1
  15. return OK;
  16. }

依次对L的每个数据元素调用函数visit():

  1. /*初始条件:线性表L已存在。*/
  2. /*操作结果:依次对L的每个数据元素调用函数visit()。一旦visit()操作失败,则操作失败。*/
  3. Status ListTraverse(List L, Status(*visit)(List L))
  4. {
  5. (*visit)(L);
  6. return OK;
  7. }


4.完整程序:


  1. #include<stdlib.h>
  2. #include<stdio.h>
  3. #define OK 1
  4. #define ERROR 0
  5. #define OVERFLOW -1
  6. #define TRUE 1
  7. #define FALSE 0
  8. #define LIST_INIT_SIZE 100 //存储空间初始分配量
  9. #define LISTINCREMENT 10 //存储空间分配增量
  10. typedef int ElemType;//指定顺序表中数据类型
  11. typedef int Status;
  12. typedef struct
  13. {
  14. ElemType *elem; //存储空间基址
  15. int length; //当前长度
  16. int listsize; //当前分配的存储容量(以sizeof(ElemType)为单位)
  17. }List;
  18. /*构造一个空的线性表L*/
  19. /*操作结果:构造一个空的线性表。*/
  20. Status InitList(List &L)
  21. {
  22. L.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
  23. if (!L.elem) exit(OVERFLOW);//内存申请失败,异常退出
  24. L.length = 0;//空表长度为0
  25. L.listsize = LIST_INIT_SIZE;
  26. printf("构造一个空的线性表L成功!\n");
  27. return OK;
  28. }
  29. /*销毁线性表L*/
  30. /*初始条件:线性表L已存在。*/
  31. /*操作结果:销毁线性表L。*/
  32. Status DestroyList(List &L)
  33. {
  34. if (L.elem)free(L.elem);//释放内存空间
  35. L.elem = NULL;
  36. L.length = 0;
  37. L.listsize = 0;
  38. return OK;
  39. }
  40. /*初始条件:线性表L已存在。*/
  41. /*操作结果:将L置为空表。*/
  42. Status ClearList(List &L)
  43. {
  44. L.length = 0;
  45. return OK;
  46. }
  47. /*判断线性表是否为空*/
  48. /*初始条件:线性表L已存在。*/
  49. /*操作结果:若L为空,则返回TRUE,否则返回FALSE。*/
  50. Status ListEmpty(List &L)
  51. {
  52. if (!L.length)return TRUE;
  53. else return FALSE;
  54. }
  55. /*初始条件:线性表L已存在。*/
  56. /*操作结果:返回L中数据元素个数。*/
  57. Status ListLength(List &L)
  58. {
  59. return L.length;
  60. }
  61. /*初始条件:线性表L已存在,1≤i≤ListLength(L)。*/
  62. /*操作结果:用e返回L中第i个元素的值。*/
  63. Status GetElem(List L, int i, Status &e)
  64. {
  65. if (i<1 || i>L.length)return ERROR;
  66. else
  67. {
  68. e = L.elem[i - 1];
  69. return OK;
  70. }
  71. }
  72. /*初始条件:线性表L已存在,compare()是数据元素判断函数。*/
  73. /*操作结果:返回L中第1个与e满足关系compaer()的数据元素的位序。若这样的数据元素不存在,则返回0。*/
  74. Status LocateElem(List L, Status e, Status(*compare)(ElemType, ElemType))
  75. {
  76. ElemType i, *p;
  77. i = 1; //i的初值为第一个元素的位序
  78. p = L.elem; //p的初值为第一个元素的存储位置
  79. while (i <= L.length&&!(*compare)(*p++, e)) ++i;
  80. if (i <= L.length)return i;
  81. else return 0;
  82. }
  83. /*初始条件:线性表L已存在。*/
  84. /*操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败,pre_e无定义。*/
  85. Status PriorElem(List L, Status cur_e, Status &pre_e)
  86. {
  87. for (int i = 1; i < L.length; i++)
  88. {
  89. if (L.elem[i]==cur_e)
  90. {
  91. pre_e = L.elem[i - 1];
  92. return OK;
  93. }
  94. else
  95. {
  96. if (i >= L.length) return ERROR;
  97. }
  98. }
  99. }
  100. /*初始条件:线性表L已存在。*/
  101. /*操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后续,否则操作失败,next_e无定义。*/
  102. Status NextElem(List L, Status cur_e, Status &next_e)
  103. {
  104. for (int i = 0; i < L.length-1; i++)
  105. {
  106. if (L.elem[i] == cur_e)
  107. {
  108. next_e = L.elem[i + 1];
  109. return OK;
  110. }
  111. else
  112. {
  113. if (i >= L.length-1)
  114. {
  115. return ERROR;
  116. }
  117. }
  118. }
  119. }
  120. /*初始条件:线性表L已存在,1≤i≤ListLength(L)+1。*/
  121. /*操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1。*/
  122. Status ListInsert(List &L, int i, Status e)
  123. {
  124. ElemType *q, *p, *newbase;
  125. if (i<1 || i>L.length + 1) return ERROR;//i值不合法
  126. if (L.length>=L.listsize) //当前存储空间已满,增加分配
  127. {
  128. newbase = (ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT)*sizeof(ElemType));
  129. if (!newbase) exit(OVERFLOW); //存储分配失败
  130. L.elem = newbase; //新基址
  131. L.listsize += LISTINCREMENT; //增加存储容量
  132. }
  133. q = &(L.elem[i - 1]); //q为插入位置
  134. for (p = &(L.elem[L.length - 1]); p >= q; --p)
  135. {
  136. *(p + 1) = *p; //将插入位置及之后的元素右移
  137. }
  138. *q = e; //插入e
  139. ++L.length; //表长增1
  140. return OK;
  141. }
  142. /*初始条件:线性表L已存在且非空,1≤i≤ListLength(L)。*/
  143. /*操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1。*/
  144. Status ListDelete(List &L, int i, Status &e)
  145. {
  146. ElemType *q, *p;
  147. if (i<1 || i>L.length)return ERROR; //i值不合法
  148. p = &(L.elem[i - 1]); //p为被删除元素位置
  149. e = *p; //将删除元素的值赋给e
  150. q = L.elem + L.length - 1; //表尾元素的位置
  151. for (++p; p <= q; ++p) //将被删除元素之后的元素左移
  152. {
  153. *(p - 1) = *(p);
  154. }
  155. --L.length; //表长减1
  156. return OK;
  157. }
  158. /*初始条件:线性表L已存在。*/
  159. /*操作结果:依次对L的每个数据元素调用函数visit()。一旦visit()操作失败,则操作失败。*/
  160. Status ListTraverse(List L, Status(*visit)(List L))
  161. {
  162. (*visit)(L);
  163. return OK;
  164. }
  165. /*初始条件:线性表L已存在。*/
  166. /*操作结果:输出线性表*/
  167. Status VisitList(List L)
  168. {
  169. for (int i = 0; i < L.length; i++)
  170. {
  171. printf("%d ", L.elem[i]);
  172. }
  173. return OK;
  174. }
  175. /*初始条件:线性表L已存在。*/
  176. /*操作结果:小到大对顺序表进行排序*/
  177. Status SortList(List &L)
  178. {
  179. for (int i = 0; i < L.length - 1; i++)
  180. {
  181. for (int j = 0; j < L.length - i - 1; j++)
  182. {
  183. if (L.elem[j]>L.elem[j + 1])
  184. {
  185. int temp = L.elem[j];
  186. L.elem[j] = L.elem[j + 1];
  187. L.elem[j + 1] = temp;
  188. }
  189. }
  190. }
  191. return OK;
  192. }
  193. int main()
  194. {
  195. List L;
  196. ElemType e1, e2;
  197. Status k;
  198. int i, a, b, c, d, e, n, j;
  199. printf("******************\n");
  200. printf("请选择您所要进行的操作\n");
  201. printf("1.排序\n");
  202. printf("2.判断线性表是否为空\n");
  203. printf("3.线性表中元素的个数\n");
  204. printf("4.寻找表中第i个元素\n");
  205. printf("5.寻找指定值前驱\n");
  206. printf("6.寻找指定值后继\n");
  207. printf("7.删除元素\n");
  208. printf("8.遍历输出线性表\n");
  209. printf("9.清空线性表\n");
  210. printf("10.销毁线性表\n");
  211. printf("11.插入元素\n");
  212. printf("0.退出\n");
  213. printf("******************\n\n");
  214. //初始化线性表
  215. InitList(L);
  216. printf("初始化表元素个数:");
  217. scanf("%d", &n);//往线性表插入数据
  218. printf("输入所插入的数据:");
  219. for (i = 1; i <= n; i++)
  220. {
  221. scanf("%d", &a);
  222. ListInsert(L, i, a);
  223. }
  224. printf("请进行下一步的操作:");
  225. while (scanf("%d", &c) && c != 0)
  226. {
  227. switch (c)
  228. {
  229. case 1:
  230. SortList(L);
  231. printf("线性表成功由小到大进行排序\n");
  232. break;
  233. case 2:
  234. if (ListEmpty(L)) printf("线性表为空\n");
  235. else printf("线性表不为空\n");
  236. break;
  237. case 3:
  238. printf("线性表的元素个数为%d\n", ListLength(L));
  239. break;
  240. case 4:
  241. printf("输入要查找表中第i个值:");
  242. scanf("%d", &i);
  243. if (i<1 || i>ListLength(L)){
  244. printf("输入数值错误\n");
  245. break;
  246. }
  247. else{
  248. GetElem(L, i, e);
  249. printf("表中第%d个元素对应的数值为%d\n", i,e);
  250. }
  251. break;
  252. case 5:
  253. printf("输入要查找表中第i个值前驱:");
  254. scanf("%d", &i);
  255. if (i < 2 || i >= ListLength(L)) {
  256. printf("输入数值错误\n");
  257. break;
  258. }
  259. else{
  260. PriorElem(L, i, e);
  261. printf("表中第%d个元素对应的前驱数值为%d\n", i, e);
  262. }
  263. break;
  264. case 6:
  265. printf("输入要查找表中第i个值后继:");
  266. scanf("%d", &i);
  267. if (i <= 1 || i > ListLength(L)-1) {
  268. printf("输入数值错误\n");
  269. break;
  270. }
  271. else{
  272. NextElem(L, i, e);
  273. printf("表中第%d个元素对应的后继数值为%d\n", i, e);
  274. }
  275. break;
  276. case 7:
  277. printf("输入删除元素位序:");
  278. scanf("%d", &c);
  279. if (c<1 || c>L.length)
  280. printf("输入错误!!!元素不存在\n");
  281. else
  282. ListDelete(L, c, e);
  283. printf("删除第%d个元素成功,其值为%d\n", c, e);
  284. break;
  285. case 8:
  286. ListTraverse(L, VisitList);
  287. printf("\n遍历输出线性表成功!\n");
  288. break;
  289. case 9:
  290. ClearList(L);
  291. printf("清空成功!\n");
  292. break;
  293. case 10:
  294. DestroyList(L);
  295. printf("销毁成功!\n");
  296. break;
  297. case 11:
  298. printf("请输入您所想插入的位置以及元素值:");
  299. scanf("%d%d", &e, &d);
  300. if (ListInsert(L, e, d)) printf("插入成功!\n");
  301. else printf("插入失败!\n");
  302. break;
  303. default:
  304. break;
  305. }
  306. printf("请进行下一步的操作:");
  307. }
  308. printf("成功退出!\n");
  309. return 0;
  310. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/一键难忘520/article/detail/801663
推荐阅读
相关标签
  

闽ICP备14008679号