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

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);

}



上一篇:【java】数组(包含冒泡排序)


下一篇:kotlin更多语言结构——>空安全