数据结构上机实验---第二周 problem 2

第二周的数据结构上机实验中，problem 2要求我们实现一个简单的链表数据结构，并且实现一些基本的操作，比如插入、删除、查找等。

首先，我们需要定义一个节点结构，包括数据和指向下一个节点的指针。然后我们需要实现插入操作，通过遍历链表找到插入位置，然后改变指针的指向来插入新节点。接着是删除操作，同样需要遍历找到要删除的节点，并且改变指针的指向来删除节点。最后是查找操作，遍历链表找到特定的值，并返回节点的位置。

在实现这些基本操作的同时，我们还需要考虑一些边界情况，比如链表为空的情况、插入或删除的节点在链表两端的情况等。

除了实现基本操作，我们还需要在实验报告中写出代码的详细分析，包括每个操作的时间复杂度、空间复杂度，以及一些优化的方法。

在实验过程中，我们可能会遇到一些问题，比如指针操作的错误、边界情况考虑不周等，但通过仔细调试和思考，我们可以逐步解决这些问题，最终完成实验要求。

总的来说，这次实验让我们对链表这种常见的数据结构有了更深入的理解，通过实践操作，我们对数据结构的应用也更加熟练。

相关问题

西电数据结构上机考试题目

### 关于西安电子科技大学数据结构课程上机考试题目

#### TSP问题简介
TSP问题是旅行商问题(Traveling Salesman Problem)的简称，属于组合优化领域中的经典难题之一。此问题描述如下：给定一组城市以及每对城市之间的距离，要求找到一条经过所有城市的最短路径并且回到起点[^1]。

##### 构建邻接矩阵
为了表示各个城市间的连接关系及相应代价，在解决TSP问题时通常会先建立一个图模型，并通过邻接矩阵来存储这些信息。对于n个城市而言，可以创建大小为nxn的二维数组A，其中A[i][j]代表从第i个城市前往第j个城市的费用或路程长度；如果两座城之间不存在直达路线，则设该项值无穷大或者特定标记值表示不可达状态。

##### 寻找最优解的方法
针对TSP这类NP难问题，目前尚无多项式时间内能够精确求得全局最优解的有效算法。实践中常用启发式方法近似计算较优方案，比如贪心法、动态规划、分支限界等策略均能在一定程度内提供满意的结果。此外遗传算法、模拟退火等随机化搜索技术也被广泛应用于探索更高质量可行解集内的潜在最佳选项。

#### 查找马鞍点的任务说明
另一个具体的编程实践案例涉及到了如何在一个指定范围内定位满足特殊条件的数据项——即所谓的“马鞍点”。具体来说就是在m×n阶矩形区域内寻找那些既小于等于同行其他成员又大于等于同列其余部分数值的关键位置。按照输入样例的要求，程序应当接收用户给出的一系列整数构成多维表单形式后执行逻辑判断从而得出结论[^2]。

#include <stdio.h>
#define MAX_SIZE 100 

int main() {
    int matrix[MAX_SIZE][MAX_SIZE];
    int rows, cols;
    
    scanf("%d %d", &rows, &cols);
    for (int i = 0; i < rows; ++i){
        for(int j=0;j<cols;++j){
            scanf("%d",&matrix[i][j]);
        }
    }

    for (int i = 0; i < rows; ++i) {
        int minRowElementIndex = 0;

        // Find the minimum element index of row 'i'
        for (int k = 1; k < cols; ++k)
            if (matrix[i][minRowElementIndex] > matrix[i][k])
                minRowElementIndex = k;

        bool isSaddlePoint = true;
        
        // Check whether this column's elements are all greater than or equal to it.
        for (int l = 0; l < rows && isSaddlePoint ;++l)
           if(matrix[l][minRowElementIndex]>matrix[i][minRowElementIndex]){
               isSaddlePoint=false;
           }  

        if(isSaddlePoint){
             printf("The saddle point found at position (%d,%d)\n", i,minRowElementIndex );
         }
     }
     
     return 0;
}