数据结构与算法笔记 cp2-1：线性表

  • 2019 年 11 月 7 日
  • 筆記

线性表

1.1 定义：

List，由零个或多个数据特性相同的元素构成的有限序列。个数 n 称为线性表的长度，n=0 的时候称为空表。比如说，十二星座就是一个线性表，它的“第一个”和“最后一个”元素都是唯一的，并且中间的元素均只有一个前驱、一个后继。

1.2 抽象数据类型

ADT List{      Data:.......      Operation:          InitList(&L): 初始化，建立一个空的线性表L          ClearList(&L): 清空线性表L          GetElem(L,i,&e): 将L中第i个位置元素值返回给e          LocateElem(L,e): 在L中查找与e相等的元素          ListInsert(&L,i,e): 在L中第i个位置插入新元素e          ListDelete(&L,i,&e): 删除L中第i个位置元素，并用e返回其值          ListLength(L): 返回L长度  } ADT List

线性表的顺序存储结构 / 顺序表

2.1 定义：

指的是用一段地址连续的存储单元依次存储线性表的数据元素。

各个元素的地址之间构成等差数列，因此，知道了某一个元素的地址，就可以随时推导出其它元素的地址，也就是说不管取出还是存入哪一个元素，花费的时间都一样，是一个常数(O(1))，这种特性的存储结构就叫随机存取结构。

一维数组可以实现线性表的顺序存储结构，不过要注意数组下标从0开始，而说线性表的时候说的是位序，是从1开始的。

2.2 基本操作

(1) 初始化：

首先定义线性表顺序存储结构：

typedef struct Table{      int * head;//声明了一个名为head的长度不确定的数组，也叫“动态数组”      int length;//记录当前顺序表的长度      int size;//记录顺序表分配的存储容量  }table;

第一个操作是初始化，包括：给head申请足够大小的物理空间；给size和length赋初值：

#define Size 5 //对Size进行宏定义，表示顺序表申请空间的大小  table initTable(){      table t;      t.head=(int*)malloc(Size*sizeof(int));//构造一个空的顺序表，动态申请存储空间      if (!t.head) //如果申请失败，作出提示并直接退出程序      {          printf("初始化失败");          exit(0);      }      t.length=0;//空表的长度初始化为0      t.size=Size;//空表的初始存储空间为Size      return t;  }

(2) 取值： 找某一个位序的元素，只需要判断位序的合法性，之后返回数组[位序-1]即可。

(3) 查找/修改： 遍历数组元素，与目标元素比较，相等则返回。如果要修改，重新赋值即可。

(4) 删除： 找到目标元素，让后续元素整体前移一个位置，之后长度减一即可。

table delTable(table t,int add){      if (add>t.length || add<1) {          printf("被删除元素的位置有误");          exit(0);      }      //删除操作      for (int i=add; i<t.length; i++) {          t.head[i-1]=t.head[i];      }      t.length--;      return t;  }

比如说要删除5个元素中的第三个，那么 add 就是 3，而 t.head[3] 就是第四个元素，从这个元素开始依次向前移动并覆盖前面的元素。

(5) 插入： 找到目标位置，将该位置对应元素以及后续元素整体后移一个位置，之后长度加一即可。

//插入函数，其中，elem为插入的元素，add为插入到顺序表的位置  table addTable(table t,int elem,int add)  {      //判断插入本身是否存在问题      if (add>t.length+1||add<1) {          printf("插入位置有问题");          return t;      }      //线性表长度等于数组长度，没有多余空间容纳新插入的元素，此时需要申请      if (t.length==t.size) {          t.head=(int *)realloc(t.head, (t.size+1)*sizeof(int));          if (!t.head) {              printf("存储分配失败");              return t;          }          t.size+=1;      }      for (int i=t.length-1; i>=add-1; i--) {          t.head[i+1]=t.head[i];      }      t.head[add-1]=elem;      t.length++;      return t;  }

  • 首先要注意范围的判断，add 作为目标位置，至少也得等于1，此时是插在最前面；同时，add 可以等于 length+1，此时是插在最后面，但不能比 length+1 更大了，否则会出现空隙。
  • 接着要注意是从后往前遍历的，因为如果是从前往后的话就会发生覆盖。
  • 可以不做“目标位置是否在表尾”的判断，这样会直接绕过for循环，执行赋值。

这里可以发现，线性表的插入和删除元素操作往往需要移动大量的元素。

VirMach 便宜 VPS

QNews

QNews