文档介绍：中南大学
数据结构试验报告
题目实验一
学生姓名王云鹏
学号
指导老师郑瑾
学院计算机学院
专业班级物联网1802
完成时间
指导老师评定签名
实验一
需求分析
1．单向链表操作的实现（验证性实验）
问题描述
(1) 用头插法（或尾插法）建立带头结点的单向链表。
(2) 对已建立的单向链表实现插入、删除、查找等基本操作。
2．城市链表（设计性实验）
问题描述
将若干城市的信息存入一个带头结点的单向链表。结点中的城市信息包括城市名、城市的位置坐
标。要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。
基本要求
(1) 给定一个城市名，返回其位置坐标。
(2) 给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市。
测试数据
由读者依据软件工程的测试技术自己确定。注意测试边界数据
4．长整数运算（综合性实验）
问题描述
设计一个程序实现两个任意长的整数求和运算。
基本要求
利用双向循环链表实现长整数的存储，每个结点含一个整型变量。任何整型变量的范围是
−(215−1)～(215−1)。输入和输出形式：每4位一组，组间用逗号隔开。
测试数据
(1) 0和0，应输出“0”。
(2) −2345,6789，−7654,3211，应输出“−1,0000,0000”。
(3) −9999,9999，1,0000,0000,0000，应输出“9999,0000,0001”。362 附录
(4) 1,0001,000，−1,0001,0001，应输出“0”。
(5) 1,0001,0001，−1,0001,0000，应输出“1”。
实现提示
(1) 每个结点中可以存放的最大整数为215−1＝32 767，这样才能保证两数相加不会溢出。但若按
32 768进制数存放，在十进制数与32768进制数之间的转换十分不方便，故可以在每个结点中仅存放十
进制数的4位，即不超过9 999的非负整数，整个链表视为万进制数。
(2) 可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点数目。相加过程
中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。不能给
长整数位数规定上限。
概要设计
验证性实验
函数：
设计性实验
函数：
综合性实验
函数：
详细设计
验证性实验
#include <>
#include <>
typedef struct node //节点
{
    int data;
    struct node *next;
} node;
int length(node *head)
{ //返回链表长度，算上头节点
    int len = 0;
    node *p = head;
    while (p != NULL)
    {
        len++;
        p = p->next;
    }
    return len;
}
void Init(node *head)
{                                        //带头节点
    if (head == NULL)
    {
        printf("malloc fail in main\n");
        return;
    }
    head->data = 0; //头节点存链长，且头节点不计入链长
    // printf("%d",head->data);
    head->next = NULL;
}
void Insert(node *head, int e, int pos)
{                                      //在第pos个节点后插入新节点
    if (pos > length(head) || pos < 0) //不合法位置