1.将两个递增有序的顺序表A,B进行合并，合并后仍然有序，并求中位数。 2.给定一个升序排列的顺序表，请删除重复出现的元素，使每个元素只出现一次，并输出新的顺序表的信息。注:删除元素后顺序表保持升序

1. 合并两个递增有序的顺序表A和B，可以使用双指针法。首先创建一个新的空表C作为结果。然后设置两个指针i和j分别指向A和B的头部。比较两个指针所指的元素，将较小的那个添加到结果表C，并移动对应的指针。当其中一个列表遍历完后，直接将另一个列表剩余的部分复制到结果表C的剩余位置。最后，对结果表C进行遍历即可得到排序后的顺序表。 ```c typedef struct Node { int data; struct Node* next; } Node; void merge(Node** A, Node** B) { Node* C = NULL; Node* tail = NULL; while (*A && *B) { if ((*A)->data <= (*B)->data) { if (C == NULL) { C = *A; tail = C; } else { tail->next = *A; tail = tail->next; } (*A)++; } else { if (C == NULL) { C = *B; tail = C; } else { tail->next = *B; tail = tail->next; } (*B)++; } } // 如果有一个列表还有剩余元素，直接添加到结果表尾部 while (*A) { tail->next = *A; tail = tail->next; (*A)++; } while (*B) { tail->next = *B; tail = tail->next; (*B)++; } } double findMedianSortedList(Node* list) { int length = 0; Node* slow = list, *fast = list; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; length++; } if (length % 2 != 0) { return (double)(slow->data); } else { return (double)(slow->data + fast->data) / 2.0; } } ``` 2. 删除升序顺序表中的重复元素，可以先创建一个新的空表D，然后遍历原表。对于每个元素，如果它比当前表头大或为空，则将其添加到新表D；若相等则跳过。遍历完成后，新表D即为去重后的顺序表。 ```c void removeDuplicates(Node** A) { Node* D = NULL; Node* D_tail = NULL; for (Node* temp = *A; temp != NULL; temp = temp->next) { if (D_tail && D_tail->data < temp->data) { D_tail->next = temp; D_tail = D_tail->next; } else if (D == NULL || temp->data > D_tail->data) { if (D != NULL) { D_tail->next = temp; } else { D = temp; } D_tail = temp; } } *A = D; } ```

### C语言实现线性表的链式存储结构 #### 查找操作 在链式存储结构中，查找某个特定元素的操作通常通过遍历整个单链表完成。由于链表中的节点不连续存储，因此无法像数组那样直接访问指定位置的数据项。 以下是基于单链表的查找函数实现： ```c typedef struct Node { int data; struct Node* next; } Node; Node* find(Node* head, int target) { Node* current = head; while (current != NULL && current->data != target) { current = current->next; // 移动到下一个节点 } return current; // 如果找到返回指针，未找到则返回NULL } ``` 此方法的时间复杂度为O(n)[^1]，其中n是链表长度。 --- #### 插入操作 对于单链表，在给定位置插入新节点需要调整前后节点之间的链接关系。如果是在头结点之前插入，则需特别处理头指针的变化。 下面是向单链表头部插入一个新节点的例子： ```c void insert_head(Node** head_ref, int new_data) { Node* new_node = (Node*)malloc(sizeof(Node)); new_node->data = new_data; new_node->next = *head_ref; // 新节点指向原头节点 *head_ref = new_node; // 更新头指针 } ``` 上述代码展示了如何动态分配内存创建新节点，并将其作为新的头节点连接至原有链表前端。 --- #### 删除操作 删除指定值的第一个匹配节点时，同样要先定位目标节点及其前驱节点的位置。之后修改前驱节点的`next`字段即可移除目标节点。 下面是一个简单的例子用于演示这一过程： ```c void delete_node(Node** head_ref, int key) { Node* temp = *head_ref, *prev = NULL; if (temp != NULL && temp->data == key) { // 若头节点就是要删掉的那个 *head_ref = temp->next; // 修改头指针 free(temp); // 释放旧头节点空间 return; } while (temp != NULL && temp->data != key) { prev = temp; temp = temp->next; } if (temp == NULL) return; // 节点不存在的情况 prev->next = temp->next; // 断开待删除节点 free(temp); } ``` 这里需要注意的是当被删除的目标位于列表开头或者中间/结尾的不同情况下的特殊处理逻辑。 --- #### 约瑟夫环问题求解 约瑟夫环问题是经典的循环淘汰类题目，可以通过模拟的方式借助双向或单向链表解决。每次迭代都从当前剩余人员集合里按照固定步长挑选一个人出局直到剩下最后一位幸存者为止。 一种可能的解决方案如下所示： ```c #include <stdio.h> #include <stdlib.h> struct Person { int id; struct Person* next; }; // 创建初始圈形链表 Person* create_circle(int n){ Person* first = malloc(sizeof(Person)), *last=first,*p; last ->id=1; for(int i=2;i<=n;i++){ p=(Person *)malloc(sizeof(Person)); p->id=i; last->next=p; last=p; } last->next=first;//形成闭环 return first; } int main(){ int m,n,k,i,j; scanf("%d%d",&m,&k); Person *circle=create_circle(m),*pre=circle,*cur=circle; for(i=m;i>1;i--){ for(j=1;j<k&&cur!=NULL;j++) pre=cur , cur=cur->next ; printf("%d ",cur->id ); pre->next=cur->next ;free(cur); cur=pre->next ; } printf("\nThe survivor is %d\n",cur->id ); return 0;} ``` 以上程序片段实现了基本功能框架，但并未考虑边界条件以及错误输入情形下应有的健壮性和鲁棒性的提升措施[^2]。 --- #### 大整数加法运算 大整数相加可以采用字符串形式保存每一位数字并通过逐位累加的方式来计算结果。考虑到进位因素的影响，还需要额外设置变量记录每一轮产生的进位量。 示例代码如下： ```c char* addStrings(char* num1, char* num2) { int carry = 0; int len1 = strlen(num1)-1; int len2 = strlen(num2)-1; int max_len = fmax(len1,len2)+2; char res[max_len]; memset(res,'0',sizeof(res)); while(len1 >=0 ||len2>=0||carry ){ int sum = ((len1<0)?'0':num1[len1]) - '0'+((len2<0)?'0':num2[len2]-'0')+carry; res[--max_len]=sum%10+'0'; carry=sum /10; --len1;--len2; } return strdup(&res[max_len]); } ``` 这段代码定义了一个辅助函数用来执行任意精度的大整数加法规则[^4]。 --- #### 单链表归并排序 归并将两个已有序序列组合成一个新的整体顺序排列的过程称为归并。针对单链表而言，我们可以递归地把其拆分成更小的部分再逐步合并回去得到最终完全排好序的新链条。 核心部分伪码描述如下： ```plaintext MergeSort(headRef) If list size equals to one or zero then Return. Divide the unsorted list into two sublists of about half the size. Call MergeSort recursively on both halves until each sublist contains only one element. Then merge those sorted lists back together using helper function `merge`. End Function. HelperFunction Merge(listA,listB) Create dummy node as start point and set tail pointer initially pointing at it also. While neither A nor B becomes empty do following steps: Compare heads from either side pick smaller value append after tail move corresponding iterator forward accordingly update tail reference too. Endwhile loop once any part exhausts attach rest portion directly behind previous attachment place. Return newly formed ordered chain starting address stored inside dummy's next field member variable now. ``` 具体实现细节省略此处仅提供思路指引[^3]。 ---