《数据结构》（C语言版）学习笔记——第2章线性表

2023-12-30 19:00:58

2.1 线性表的定义和特点

定义：

由n (n$\geqslant$0)个数据特性相同的元素构成的有限序列称为 线性表。

线性表中元素的个数n (n$\geqslant$0)定义为线性表的长度，n =0时称为空表。

对千非空的线性表或线性结构，其特点是：

(1) 存在唯一的一个被称作 “第一个＂的数据元素；
(2)存在唯一的一个被称作 “最后一个＂的数据元素；
(3)除第一个之外，结构中的每个数据元素均只有一个前驱；
(4)除最后一个之外，结构中的每个数据元素均只有一个后继。

2.2 案列引入

案例2.1

一个一元多项式 $P_n(x)$可按升幂写成：

\[P_n(x)=p_0+p_1x+p_2x^2+···+p_nx^n \]

要求：实现两个一元多项式的相加、相减和相乘的运算。

一元多项式可由$n+1$个系数唯一确定，因此，可以将一元多项式 $P_n(x)$抽象为一个由$n+1$个元素组成的有序序列，可用一个线性表$P$来表:

\[P=(p_0,p_1,p_2,···,p_n) \]

这时，每一项的指数$***i***$隐含在其系数$p_i$的序号中。

假设$Q_m(x)$是一元$m $次多项式，同样可用线性表$Q$来表示：

\[Q=(q_0,q_1,q_2,···,q_m) \]

不失一般性，设$m≤n$，则两个多项式相加的结果 $R_n(x)=P_n(x)+Q_n(x)$可用线性表 $R$表示：

\[R=(p_0+q_0,p_1+q_1,p_2+q_2,···,p_m+q_m,p_{m+1},···,p_n) \]

案例2.2：稀疏多项式的运算

在处理

\[S(x)=1+3x^{1000}+2x^{2000} \]

的多项式时，就要用一个长度为20001的线性表表示，而表中仅有3个元素，此时会造成存储空间的浪费。由于线性表的元素可以包含多个数据
项，由此可改变元素设定，对多项式的每一项，可用（系数，指数）唯一确定。

一般情况下的一元n次多项式可写成

\[P_n(x)=p_1x^{e_1}+p_2x^{e_2}+···+p_mx^{e_m} \]

其中，$p_i$是指数为$e_i$的项的非零系数，且满足

$0≤e_1<e_2<···<e_m=n$

若用一个长度为$m$且每个元素有两个数据项（系数项和指数项）的线性表

$((p_1,e_1),(p_2,e_2),···,(p_m,e_m))$

便可唯一确定多项式$P_n (x)$。在最坏情况下，$n+1(=m)$个系数都不为零，则比只存储每项系数的方案要多存储一倍的数据。但是，对千类似 $S(x)$的稀疏多项式，这种表示将大大节省空间。

案例2.3：图书信息管理系统

出版社有一些图书数据保存在一个文本文件 book.txt 中，为简单起见，在此假设每种图书只包括三部分信息：ISBN (书号）、书名和价格，文件中的部分数据。现要求实现一个图书信息管理系统，包括以下6个具体功能。

(1) 查找：根据指定的 ISBN 或书名查找相应图书的有关信息，并返回该图书在表中的位置序号。
(2) 插入：插入一种新的图书信息。
(3) 删除：删除一种图书信息。
(4) 修改：根据指定的 ISBN, 修改该图书的价格。
(5) 排序：将图书按照价格由低到高进行排序。
(6) 计数：统计图书表中的图书数最。
要实现上述功能，与以上案例中的多项式一样，我们首先根据图书表的特点将其抽象成一个线性表，每本图书作为线性表中的一个元素，然后可以采用适当的存储结构来表示该线性表，在此基础上设计完成有关的功能算法。具体采取哪种存储结构，可以根据两种不同存储结构的优缺点，视实际清况而定。

2.3 线性表的类型定义

线性表是一个相当灵活的数据结构，其长度可根据需要增长或缩短，即对线性表的数据元素不仅可以进行访问，而且可以进行插入和删除等操作。下面给出线性表的抽象数据类型定义：

ADT List{

数据对象：$D=\{a_i|A_i∈ElemSet,i=1,2,···,n,n≥0\}$

数据关系：$R=\{<a_{i-1},a_i>|a_{i-1},a_i ∈D,i=2,···，n\}$

基本操作：

InitList (&L);//操作结果：构造一个空的线性表L
DestroyList(&L);//初始条件：线性表L已存在
//操作结果：销毁线性表L
ClearList (&L);//初始条件：线性表L已存在
//操作结果：将L重置为空表
ListEmpty(L);//初始条件：线性表L已存在
//操作结果：若L为空表，则返回true, 否则返回false
ListLength(L); //初始条件：线性表L已存在
//操作结果：返回L中数据元素个数
GetElem(L,i,&e); //初始条件：线性表L巳存在，且1<=i<=ListLength(L)。
//操作结果：用e返回L中第1个数据元素的值
LocateElem(L,e); //初始条件：线性表L已存在
//操作结果：返回L中第1个值与e相同的元素在 L中的位置。若这样的数据元素不存在，则返回值为0。
PriorElem(r,,cur_e,&pre_e); //初始条件：线性表L已存在
//操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回其前驱，否则操作失败，pre_e无定义。
NextElem(L,cur_e,&next_e); //初始条件：线性表L已存在
//操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回其后继，否则操作失败，next_e无定义。
Listinsert(&L,i,e); //初始条件：线性表L已存在，且1<=i<=ListLength (L) +l
//操作结果：在 L中第1个位置之前插入新的数据元素 e, L的长度加1
ListDelete(&L,i); //初始条件：线性表L已存在且非空，且l<=i<=ListLength(L)
//操作结果：删除L的第1个数据元素，L的长度减1
TraverseList(L); //初始条件：线性表L已存在。
//操作结果：对线性表L进行遍历，在遍历过程中对 L的每个结点访问一次
}ADT List

(1)抽象数据类型仅是一个模型的定义，并不涉及模型的具体实现，因此这里描述中所涉及的参数不必考虑具体数据类型。在实际应用中，数据元素可能有多种类型，到时可根据具体需要选择使用不同的数据类型。
(2) 上述抽象数据类型中给出的操作只是基本操作，由这些基本操作可以构成其他较复杂的操作。例如，2.2节中的两个应用实例，不论是一元多项式的运算还是图书的管理，首先都需要将数据元素读入，生成一个包括所需数据的线性表，这属于线性表的创建。这项操作可首先调用基本操作定义中的lnitList(&L)构造一个空的线性表L, 然后反复调用Listlnsert(&L,i,e)在表中插入元素e, 就可以创建一个需要的线性表。同样，对
于一元多项式的运算可以看作是线性表的合并，合并过程需要不断地进行元素的插入操作。其他如求线性表的拆分、复制等操作也都可以利用上述基本操作的组合来实现。
(3)对于不同的应用，基本操作的接口可能不同。例如，案例2.2的删除操作，如果要求删除图书表中ISBN为x的图书，首先需要根据x确定该图书在线性表中的位置，然后再利用ListDelete(&L,i)基本操作将该种图书记录从表中删除。
(4)由抽象数据类型定义的线性表，可以根据实际所采用的存储结构形式，进行具体的表示和实现。

2.4 线性表的顺序表示和实现

2.4.1 线性表的顺序存储表示

2.4.2 顺序表中基本操作的实现

可以看出，当线性表以上述定义的顺序表表示时，某些操作很容易实现。因为表的长度是顺序表的一个 “属性”，所以可以通过返回length的值实现求表长的操作，通过判断length的值是否为0 判断表是否为空，这些操作算法的时间复杂度都是O(1)。下面讨论顺序表其他几个主要操作的实现。

1.初始化

顺序表的初始化操作就是构造一个空的顺序表。

算法2.1 顺序表的初始化

【算法步骤】

①为顺序表L动态分配一个预定义大小的数组空间，使elem指向这段空间的基地址。

②将表的当前长度设为0。

【算法描述】

Status InitList(SqList &L)
{
  L.elem= new ElemType[MAXSIZE];  //为顺序表分配一个大小为MAXSIZE的数组空间
  if (! L. elem) exit (OVERFLOW); //存储分配失败退出
  L.length=O;                     //空表长度为0
  return OK; 
}

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

#define MAXSIZE 20

/*定义顺序表*/
typedef struct {
  int date[MAXSIZE];
  int length;
}SqList;

/*初始化顺序表*/

int InitList(SqList &L)
{
  
  if(!L.date) 
  { 
    printf("初始化失败！\n");
    return 0;
  }
  L.length = 0;
  printf("初始化成功！\n");
  return 1;
}

/*建立顺序表*/
int CreatList(SqList L, int a[], int n)
{
  if (n > MAXSIZE) 
  {
    printf("空间不足，无法建立顺序表！ \n");
    return 0;
  }
    
  for (int i = 0; i < n; i++)
    L.date[i] = a[i];
  L.length = n;
  return 1;
}
/*遍历操作*/
void PrintList(SqList L)
{
  for (int i = 0; i < L.length; i++)
    printf("%d ", (L.date[i]));
}

/*取值（按位查找）*/
int Getdate(SqList L,int i,int *e)
{
  if (i<1 || i>L.length)
  {
    printf("查找位置非法，查找错误\n");
    return 0;
  }
  else
  {
    *e = L.date[i];
    printf("%d", e);
    return 1;
  }
}
/*查找（按值查找）*/
int Locatedate(SqList L, int e)
{
  for(int i = 0; i < L.length; i++)
    if (L.date[i] == e) return i + 1;
    return 0;
}

/*插入*/
int ListInsert(SqList L, int i, int e)
{
  if ((i < 1) || (i > L.length + 1)) return 0;
  if (L.length == MAXSIZE) return 0;
  for (int j = L.length - 1; j >= i - 1; j--)
    L.date[j + 1] = L.date[j];
  L.date[i - 1] = e;
  ++L.length;
  return 1;
}
/*删除*/
int ListDelete(SqList L, int i)
{
  if ((i < 1) || (i > L.length)) return 0;
  for (int j = i; j <= L.length - 1; j++)
    L.date[j - 1] = L.date[j];
    --L.length;
    return 1;
}
int main()
{
  int a[5] = { 1,2,3,4,5 };
  int* p=new int;
  SqList List1;
  InitList(List1);//初始化
  printf("给顺序表赋值：1 2 3 4 5\n遍历并输出顺序表：\n");
  CreatList(List1, a, 5);//建立
  PrintList(List1);//遍历输出此顺序表
  printf("\n取第三位的值：\n");
  Getdate(List1, 3, p);

}

码农公寓