当前位置:   article > 正文

SCAU8579、SCAU8580、SCAU8581 链式表的基本操作_scau 8580

scau 8580

这篇文章是一份纯代码分享。

代码包含了线性表的链式实现时的基本函数,包括:

CreateLinkList、DestroyLinkList、ClearLinkList、LinkListEmpty、LinkListLength

GetElem、LocateElem、PriorElem、NextElem、LinkListInsert、LinkListDelete、Traverse

以及为完成SCAU8579、SCAU8580、SCAU8581的必要函数和代码段。

  1. //此项目功能:完成链式表的基本操作以及OJ给出的三道题:8579、8580、8581
  2. #include <stdio.h>
  3. #include <malloc.h>
  4. #define ElemType int
  5. #define Status int
  6. #define OK 1
  7. #define ERROR 0
  8. #define TRUE 1
  9. #define FALSE 0
  10. typedef struct LNode
  11. {
  12. ElemType data;
  13. struct LNode *next;
  14. } LNode, *LinkList;
  15. Status CreateLinkList(LinkList &L, int n)
  16. {
  17. LinkList tail, p;
  18. ElemType e;
  19. L = new LNode;
  20. L->data = 0;
  21. L->next = NULL;
  22. tail = L;
  23. for (int i = 0; i < n; i++)
  24. {
  25. scanf("%d", &e);
  26. p = new LNode;
  27. p->data = e;
  28. p->next = NULL;
  29. tail->next = p;
  30. tail = p;
  31. L->data++;
  32. }
  33. return OK;
  34. }
  35. Status DestroyLinkList(LinkList &L)
  36. {
  37. LinkList p = L->next, q;
  38. L->next = NULL;
  39. while (p)
  40. {
  41. q = p->next;
  42. delete p;
  43. p = q;
  44. }
  45. delete L;
  46. return OK;
  47. }
  48. Status ClearLinkList(LinkList &L)
  49. {
  50. LinkList p = L->next, q;
  51. L->next = NULL;
  52. while (p)
  53. {
  54. q = p->next;
  55. delete p;
  56. p = q;
  57. }
  58. return OK;
  59. }
  60. Status LinkListEmpty(LinkList L)
  61. {
  62. if (L->next)
  63. return FALSE;
  64. else
  65. return TRUE;
  66. }
  67. int LinkListLength(LinkList L)
  68. {
  69. return L->data;
  70. }
  71. Status GetElem(LinkList L, int i, ElemType &e)
  72. {
  73. if (i > L->data || i < 1)
  74. return ERROR;
  75. else
  76. {
  77. LinkList p = L;
  78. for (int j = 0; j < i; j++)
  79. p = p->next;
  80. e = p->data;
  81. }
  82. return OK;
  83. }
  84. int LocateElem(LinkList L, ElemType e)
  85. {
  86. int i = 1;
  87. LinkList p = L->next;
  88. for (; p; p = p->next)
  89. {
  90. if (p->data == e)
  91. return i;
  92. i++;
  93. }
  94. return 0;
  95. }
  96. Status PriorElem(LinkList L, ElemType cur_e, ElemType &pre_e)
  97. {
  98. int Location = LocateElem(L, cur_e);
  99. if (Location == 0 || Location == 1)
  100. return ERROR;
  101. else
  102. GetElem(L, Location - 1, pre_e);
  103. return OK;
  104. }
  105. Status NextElem(LinkList L, ElemType cur_e, ElemType &next_e)
  106. {
  107. int Location = LocateElem(L, cur_e);
  108. if (Location == 0 || Location == L->data)
  109. return ERROR;
  110. else
  111. GetElem(L, Location + 1, next_e);
  112. return OK;
  113. }
  114. Status LinkListInsert(LinkList &L, int i, ElemType e)
  115. {
  116. if (i < 1 || i > L->data + 1)
  117. return ERROR;
  118. else
  119. {
  120. LinkList p = new LNode;
  121. p->data = e;
  122. p->next = NULL;
  123. LinkList q = L;
  124. for (int j = 1; j < i; j++)
  125. q = q->next;
  126. p->next = q->next;
  127. q->next = p;
  128. L->data++;
  129. }
  130. return OK;
  131. }
  132. Status LinkListDelete(LinkList &L, int i, ElemType &e)
  133. {
  134. if (i < 1 || i > L->data)
  135. return ERROR;
  136. else
  137. {
  138. LinkList p = L;
  139. for (int j = 1; j < i; j++)
  140. p = p->next;
  141. LinkList q = p->next;
  142. e = q->data;
  143. p->next = q->next;
  144. delete q;
  145. L->data--;
  146. }
  147. return OK;
  148. }
  149. Status Traverse(LinkList L)
  150. {
  151. if (LinkListEmpty(L))
  152. {
  153. printf("The List is empty!\n");
  154. return ERROR;
  155. }
  156. else
  157. {
  158. //printf("The LinkList is:");
  159. LinkList p = L->next;
  160. while (p)
  161. {
  162. printf("%d ", p->data);
  163. p = p->next;
  164. }
  165. printf("\n");
  166. }
  167. return OK;
  168. }
  169. void PreMerge(LinkList &C, LinkList &A)
  170. {
  171. ElemType x;
  172. LinkListDelete(A, 1, x);
  173. LinkListInsert(C, C->data + 1, x);
  174. }
  175. void Merge(LinkList &C, LinkList &A, LinkList &B)
  176. {
  177. while (A->data && B->data)
  178. {
  179. if (A->next->data == B->next->data)
  180. {
  181. PreMerge(C, A);
  182. PreMerge(C, B);
  183. }
  184. else if (A->next->data < B->next->data)
  185. PreMerge(C, A);
  186. else
  187. PreMerge(C, B);
  188. }
  189. while (A->data || B->data)
  190. {
  191. while (A->data)
  192. PreMerge(C, A);
  193. while (B->data)
  194. PreMerge(C, B);
  195. }
  196. }
  197. void TurnLinkList(LinkList &L)
  198. {
  199. for (int i = 0; i < L->data; i++)
  200. {
  201. ElemType x;
  202. LinkListDelete(L, 1, x);
  203. LinkListInsert(L, L->data + 1 - i, x);
  204. }
  205. }
  206. void FuctionsTest(LinkList &L)
  207. {
  208. int a, i;
  209. ElemType e, x;
  210. ElemType cur_e, pre_e, next_e;
  211. while (1)
  212. {
  213. scanf("%d", &a);
  214. switch (a)
  215. {
  216. case 1:
  217. CreateLinkList(L, 0);
  218. break;
  219. case 2:
  220. ClearLinkList(L);
  221. break;
  222. case 3:
  223. scanf("%d", &i);
  224. if (!GetElem(L, i, e))
  225. printf("GetElem Error.\n");
  226. else
  227. printf("%d\n", e);
  228. break;
  229. case 4:
  230. scanf("%d", &e);
  231. if (!LocateElem(L, e))
  232. printf("LocateElem Error.\n");
  233. else
  234. printf("%d\n", LocateElem(L, e));
  235. break;
  236. case 5:
  237. scanf("%d", &cur_e);
  238. if (!PriorElem(L, cur_e, pre_e))
  239. printf("No cur_e or no pre_e.\n");
  240. else
  241. printf("%d\n", pre_e);
  242. break;
  243. case 6:
  244. scanf("%d", &cur_e);
  245. if (!NextElem(L, cur_e, next_e))
  246. printf("No cur_e or no next_e.\n");
  247. else
  248. printf("%d\n", next_e);
  249. break;
  250. case 7:
  251. scanf("%d%d", &i, &x);
  252. if (!LinkListInsert(L, i, x))
  253. printf("Insert Error!\n");
  254. else
  255. printf("The Element %d is Successfully Inserted!\n", x);
  256. break;
  257. case 8:
  258. scanf("%d", &i);
  259. if (!LinkListDelete(L, i, e))
  260. printf("Delete Error!\n");
  261. else
  262. printf("The Element %d is Successfully Deleted!\n", e);
  263. break;
  264. case 9:
  265. Traverse(L);
  266. break;
  267. case 0:
  268. return;
  269. }
  270. }
  271. }
  272. int main()
  273. {
  274. /*SCAU 8579
  275. LinkList T;
  276. int a,n,i;
  277. ElemType x, e;
  278. printf("Please input the init size of the linklist:\n");
  279. scanf("%d",&n);
  280. printf("Please input the %d element of the linklist:\n", n);
  281. if(CreateLinkList(T,n))
  282. {
  283. printf("A Link List Has Created.\n");
  284. Traverse(T);
  285. }
  286. while(1)
  287. {
  288. printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n");
  289. scanf("%d",&a);
  290. switch(a)
  291. {
  292. case 1: scanf("%d%d",&i,&x);
  293. if(!LinkListInsert(T,i,x)) printf("Insert Error!\n");
  294. else printf("The Element %d is Successfully Inserted!\n", x);
  295. break;
  296. case 2: scanf("%d",&i);
  297. if(!LinkListDelete(T,i,e)) printf("Delete Error!\n");
  298. else printf("The Element %d is Successfully Deleted!\n", e);
  299. break;
  300. case 3: Traverse(T);
  301. break;
  302. case 0: return 1;
  303. }
  304. }
  305. /*
  306. /*SCAU 8580
  307. LinkList A,B,C;
  308. CreateLinkList(A,0);
  309. CreateLinkList(B,0);
  310. CreateLinkList(C,0);
  311. int a,b;
  312. scanf("%d", &a);
  313. for (int i = 0; i < a; i++)
  314. {
  315. int x;
  316. scanf("%d", &x);
  317. LinkListInsert(A,A->data+1,x);
  318. }
  319. scanf("%d", &b);
  320. for (int i = 0; i < b; i++)
  321. {
  322. int x;
  323. scanf("%d", &x);
  324. LinkListInsert(B,B->data+1,x);
  325. }
  326. printf("List A:");
  327. Traverse(A);
  328. printf("List B:");
  329. Traverse(B);
  330. Merge(C,A,B);
  331. printf("List C:");
  332. Traverse(C);
  333. */
  334. /*SCAU 8581
  335. LinkList L;
  336. CreateLinkList(L,0);
  337. int n;
  338. scanf("%d", &n);
  339. for (int i = 0; i < n; i++)
  340. {
  341. int x;
  342. scanf("%d", &x);
  343. LinkListInsert(L,L->data+1,x);
  344. }
  345. printf("The List is:");
  346. Traverse(L);
  347. TurnLinkList(L);
  348. printf("The turned List is:");
  349. Traverse(L);
  350. */
  351. /*
  352. LinkList L;
  353. FuctionsTest(L);
  354. */
  355. return 0;
  356. }

欢迎讨论交流。

声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop】
推荐阅读
相关标签
  

闽ICP备14008679号