devbox
黑客灵魂
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

＜顺序表＞题目练习《数据结构(C语言版)》_数据结构c语言版编程题

作者：黑客灵魂 | 2024-07-15 12:18:31

赞

踩

数据结构c语言版编程题

目录

题目：

【编程题】

1.顺序表的增删查改

2..合并两个有序数组。OJ链接

3.删除排序数组中的重复项。OJ链接 

解析：

后记：●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                                                                           ——By 作者：新晓·故知

题目：

【编程题】

1.顺序表的增删查改

2..合并两个有序数组。OJ链接

3.删除排序数组中的重复项。OJ链接 

解析：

1.

  1. // SeqList.h
  2. #pragma once
  3. #include <stdio.h>
  4. #include <assert.h>
  5. #include <stdlib.h>
  6.  
  7. typedef int SLDateType;
  8. typedef struct SeqList
  9. {
  10. 	SLDateType* a;
  11. 	size_t size;
  12. 	size_t capacity; // unsigned int
  13. }SeqList;
  14.  
  15. // 对数据的管理:增删查改 
  16. void SeqListInit(SeqList* ps);
  17. void SeqListDestory(SeqList* ps);
  18.  
  19. void SeqListPrint(SeqList* ps);
  20. void SeqListPushBack(SeqList* ps, SLDateType x);
  21. void SeqListPushFront(SeqList* ps, SLDateType x);
  22. void SeqListPopFront(SeqList* ps);
  23. void SeqListPopBack(SeqList* ps);
  24.  
  25. // 顺序表查找
  26. int SeqListFind(SeqList* ps, SLDateType x);
  27. // 顺序表在pos位置插入x
  28. void SeqListInsert(SeqList* ps, size_t pos, SLDateType x);
  29. // 顺序表删除pos位置的值
  30. void SeqListErase(SeqList* ps, size_t pos);
  1. // SeqList.c
  2. #include "SeqList.h"
  3.  
  4. void SeqListInit(SeqList* ps)
  5. {
  6. 	assert(ps);
  7.  
  8. 	ps->a = NULL;
  9. 	ps->size = 0;
  10. 	ps->capacity = 0;
  11. }
  12.  
  13. void SeqListDestory(SeqList* ps)
  14. {
  15. 	assert(ps);
  16. 	free(ps->a);
  17. 	ps->a = NULL;
  18. 	ps->size = ps->capacity = 0;
  19. }
  20.  
  21. void SeqListPrint(SeqList* ps)
  22. {
  23. 	assert(ps);
  24.  
  25. 	for (size_t i = 0; i < ps->size; ++i)
  26. 	{
  27. 		printf("%d ", ps->a[i]);
  28. 	}
  29.  
  30. 	printf("%\n");
  31. }
  32.  
  33. void CheckCacpity(SeqList* ps)
  34. {
  35. 	if (ps->size == ps->capacity)
  36. 	{
  37. 		size_t newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
  38. 		ps->a = (SLDateType*)realloc(ps->a, newcapacity*sizeof(SLDateType));
  39. 		ps->capacity = newcapacity;
  40. 	}
  41. }
  42.  
  43. // 以下几个接口先讲不复用Insert和Erase的实现，最后再讲复用实现
  44. void SeqListPushBack(SeqList* ps, SLDateType x)
  45. {
  46. 	//assert(ps);
  47. 	//CheckCacpity(ps);
  48.  
  49. 	//ps->a[ps->size] = x;
  50. 	//ps->size++;
  51.  
  52. 	SeqListInsert(ps, ps->size, x);
  53. }
  54.  
  55. void SeqListPushFront(SeqList* ps, SLDateType x)
  56. {
  57. 	assert(ps);
  58.  
  59. 	/*CheckCacpity(ps);
  60.  
  61. 	size_t end = ps->size;
  62. 	while (end > 0)
  63. 	{
  64. 		ps->a[end] = ps->a[end - 1];
  65. 		--end;
  66. 	}
  67.  
  68. 	ps->a[0] = x;
  69. 	++ps->size;*/
  70.  
  71. 	SeqListInsert(ps, 0, x);
  72. }
  73.  
  74. void SeqListPopFront(SeqList* ps)
  75. {
  76. 	assert(ps);
  77.  
  78. 	//size_t start = 0;
  79. 	//while (start < ps->size-1)
  80. 	//{
  81. 	//	ps->a[start] = ps->a[start + 1];
  82. 	//	++start;
  83. 	//}
  84. 	//size_t start = 1;
  85. 	//while (start < ps->size)
  86. 	//{
  87. 	//	ps->a[start-1] = ps->a[start];
  88. 	//	++start;
  89. 	//}
  90.  
  91. 	//--ps->size;
  92. 	SeqListErase(ps, 0);
  93. }
  94.  
  95. void SeqListPopBack(SeqList* ps)
  96. {
  97. 	assert(ps);
  98.  
  99. 	//ps->a[ps->size - 1] = 0;
  100. 	//ps->size--;
  101. 	SeqListErase(ps, ps->size-1);
  102. }
  103.  
  104. int SeqListFind(SeqList* ps, SLDateType x)
  105. {
  106. 	for (size_t i = 0; i < ps->size; ++i)
  107. 	{
  108. 		if (ps->a[i] == x)
  109. 		{
  110. 			return i;
  111. 		}
  112. 	}
  113.  
  114. 	return -1;
  115. }
  116.  
  117. // 顺序表在pos位置插入x
  118. void SeqListInsert(SeqList* ps, size_t pos, SLDateType x)
  119. {
  120. 	assert(ps);
  121. 	assert(pos <= ps->size);
  122.  
  123. 	CheckCacpity(ps);
  124.  
  125. 	//int end = ps->size - 1;
  126. 	//while (end >= (int)pos)
  127. 	//{
  128. 	//	ps->a[end + 1] = ps->a[end];
  129. 	//	--end;
  130. 	//}
  131.  
  132. 	size_t end = ps->size ;
  133. 	while (end > pos)
  134. 	{
  135. 		ps->a[end] = ps->a[end - 1];
  136. 		--end;
  137. 	}
  138.  
  139.  
  140. 	ps->a[pos] = x;
  141. 	ps->size++;
  142. }
  143.  
  144. // 顺序表删除pos位置的值
  145. void SeqListErase(SeqList* ps, size_t pos)
  146. {
  147. 	assert(ps && pos < ps->size);
  148.  
  149. 	//size_t start = pos;
  150. 	//while (start < ps->size-1)
  151. 	//{
  152. 	//	ps->a[start] = ps->a[start + 1];
  153. 	//	++start;
  154. 	//}
  155.  
  156. 	size_t start = pos+1;
  157. 	while (start < ps->size)
  158. 	{
  159. 		ps->a[start-1] = ps->a[start];
  160. 		++start;
  161. 	}
  162.  
  163. 	ps->size--;
  164. }

2.

解1：

  1. /*
  2. 解题思路：从最大值开始合并，所以合并从两个数组的末尾元素开始合并，依次把最大的元素放到末尾即可。
  3. */
  4. void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
  5.     //end1:nums1的末尾
  6.     //end2:nums2的末尾
  7.     //end:合并之后整个数组的末尾
  8.      int end1 = m-1;
  9.      int end2 = n-1;
  10.      int end = m+n-1;
  11.     
  12.     while(end1 >= 0 && end2 >= 0)
  13.     {   //选出尾最大的元素，存放到整个数组的末尾
  14.         //每存放一个元素，尾向前移动一个位置
  15.         if(nums1[end1] > nums2[end2])
  16.         {
  17.             nums1[end--] = nums1[end1--]; 
  18.         }
  19.         else
  20.         {
  21.             nums1[end--] = nums2[end2--];
  22.         }
  23.     }
  24.     //剩余元素依次向末尾存放
  25.     while(end1 >= 0)
  26.     {
  27.         nums1[end--] = nums1[end1--];
  28.     }
  29.     
  30.     while(end2 >= 0)
  31.     {
  32.         nums1[end--] = nums2[end2--];
  33.     }
  34. }

解2：

  1. int cmp(int* a, int* b)
  2.  {
  3.     return *a - *b;
  4.  }
  5.  
  6. void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
  7.  {
  8.     for (int i = 0; i != n; ++i) 
  9. {
  10.         nums1[m + i] = nums2[i];
  11.     }
  12.     qsort(nums1, nums1Size, sizeof(int), cmp);
  13. }

3.

解1：

  1. /*
  2. 解题思路：大致思路同上题，用非重复的元素去覆盖重复元素
  3. */
  4. int removeDuplicates(int* nums, int numsSize){
  5.     int src1 = 0, src2 = 1;
  6.     int dst = 0;
  7.     // 跟上题的思路一致，相同的数只保留一个，依次往前放
  8.     while(src2 < numsSize)
  9.     {
  10.         nums[dst] = nums[src1];
  11.         ++dst;
  12. 		//如果两个指针指向的元素不重复，则指针同时向后移动
  13.         if(nums[src1] != nums[src2])
  14.         {
  15.             ++src1;
  16.             ++src2;
  17.         }
  18.         else
  19.         {
  20.             //如果重复，找到第一个不重复的元素
  21.             while(src2 < numsSize && nums[src1] == nums[src2])
  22.             {
  23.                 ++src2;
  24.             }
  25.             //更新指针
  26.             src1 = src2;
  27.             ++src2;
  28.         }
  29.     }
  30.  
  31.     if(src1 < numsSize)
  32.     {
  33.             nums[dst] = nums[src1];
  34.             ++dst;
  35.     }
  36.  
  37.  
  38.     return dst;
  39. }

解2：

  1. int removeDuplicates(int* nums, int numsSize)
  2. {
  3.     if (numsSize == 0)
  4.     {
  5.         return 0;
  6.     }
  7.     int fast = 1, slow = 1;
  8.     while (fast < numsSize)
  9.     {
  10.         if (nums[fast] != nums[fast - 1])
  11.         {
  12.             nums[slow] = nums[fast];
  13.             ++slow;
  14.         }
  15.         ++fast;
  16.     }
  17.     return slow;
  18. }

后记：
●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                                                                           ——By 作者：新晓·故知

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

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号