数据结构线性表实验报告：C语言实现与应用

实验目的

通过实验掌握数据结构线性表的基本概念和实现方法，能够应用线性表对数据进行存储和处理。

实验内容

1. 熟悉线性表的基本概念和实现方法。
2. 了解线性表的各种算法及其应用场景。
3. 设计一个线性表的实现程序，并测试其各种算法的正确性和效率。

实验步骤

1. 定义线性表的数据结构。
2. 实现线性表的各种操作，包括插入、删除、查找、排序等。
3. 设计一个测试程序，测试线性表的各种操作的正确性和效率。
4. 对测试结果进行分析，总结线性表的优缺点和应用场景。

实验代码

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 100

typedef struct {
  int data[MaxSize];
  int length;
} SqList;

void InitList(SqList *L) {
  L->length = 0;
}

void Insert(SqList *L, int i, int x) {
  if (L->length == MaxSize) {
    printf('List is full!\n');
    return;
  }

  if (i < 1 || i > L->length + 1) {
    printf('Position is illegal!\n');
    return;
  }

  for (int j = L->length; j >= i; j--) {
    L->data[j] = L->data[j - 1];
  }

  L->data[i - 1] = x;
  L->length++;
}

void Delete(SqList *L, int i) {
  if (L->length == 0) {
    printf('List is empty!\n');
    return;
  }

  if (i < 1 || i > L->length) {
    printf('Position is illegal!\n');
    return;
  }

  for (int j = i - 1; j < L->length - 1; j++) {
    L->data[j] = L->data[j + 1];
  }

  L->length--;
}

int Search(SqList *L, int x) {
  for (int i = 0; i < L->length; i++) {
    if (L->data[i] == x) {
      return i + 1;
    }
  }

  return 0;
}

void Sort(SqList *L) {
  for (int i = 0; i < L->length - 1; i++) {
    for (int j = 0; j < L->length - 1 - i; j++) {
      if (L->data[j] > L->data[j + 1]) {
        int temp = L->data[j];
        L->data[j] = L->data[j + 1];
        L->data[j + 1] = temp;
      }
    }
  }
}

void PrintList(SqList *L) {
  for (int i = 0; i < L->length; i++) {
    printf('%d ', L->data[i]);
  }

  printf('\n');
}

int main() {
  SqList *L = (SqList *)malloc(sizeof(SqList));

  InitList(L);

  Insert(L, 1, 1);
  Insert(L, 2, 3);
  Insert(L, 3, 2);
  Insert(L, 4, 4);

  PrintList(L);

  Delete(L, 2);

  PrintList(L);

  int pos = Search(L, 2);

  if (pos == 0) {
    printf('Not found!\n');
  } else {
    printf('Found at position %d!\n', pos);
  }

  Sort(L);

  PrintList(L);

  return 0;
}

实验结果分析

通过测试程序，验证了线性表各种操作的正确性和效率。线性表是一种简单高效的数据结构，它能够方便地存储和处理数据，但其缺点是插入和删除操作需要移动大量的元素，效率较低。在实际应用中，需要根据具体情况选择合适的数据结构。

总结

本次实验加深了对线性表基本概念和实现方法的理解，掌握了线性表常用操作的实现方法，为后续学习更复杂的数据结构打下了基础。