第二章线性表

2.0、回顾

数据结构

2.1、线性表的定义和特点

线性表的定义

线性表是n(n >= 0)个数据元素(结点) a~1~, a~2~, … a~i-1~, a~i~，a~i+1~, … a~n~ 组成的有限序列。

n = 0时称为空表

线性表的特点：

对于非空的线性表或线性结构：

存在唯一的一个被称作"第一个"的数据元素
存在唯一的一个被称作"最后一个"的数据元素
除第一个之外，结构中的每一个数据元素均只有一个前驱
除最后一个之外，结构中的每一个数据元素均只有一个后继

2.2、线性表的类型定义

抽象数据类型线性表的定义：

ADT List{
  数据对象: D = {ai | ai in ElemtSet, i = 1, 2, ... ,n, n >= 0 };
  数据关系: R = {<ai-1, ai> | ai-1, ai in D, i = 2, ... ,n};
  基本操作: 
      InitList(&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中的第i个数据元素的值;
      LocateElem(L, e);
          初始条件: 线性表L已存在,
          操作结果: 返回L中的第1个值和e相等的元素在L中的位置。若这样的元素不存在，则返回值为0;
      PriorElem(L, 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) + 1;
          操作结果: 在L中第i个位置之前插入新的数据元素e,L的长度+1;
      ListDelete(&L, i);
          初始条件: 线性表L已存在且非空, 且1 <= i <= ListLength(L);
          操作结果: 删除L中第i个数据元素,L的长度-1;
      TraverseList(L);
          初始条件: 线性表L已存在;
          操作结果: 对线性表L进行遍历，在遍历过程中对L的每个结点访问一次。
}ADT List

2.3、线性表的顺序表示和实现

2.3.1、线性表的顺序存储和表示

顺序存储的定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。

顺序表中元素存储位置的计算：

线性表的每个元素需占用 l 个存储单元

线性表中的第i+1个数据元素和第i个数据元素的存储位置为：$LOC(a_i+_1) = LOC(a_i) + l$
线性表的第i个数据元素a~i~的存储位置为：$LOC(a_i) = LOC(a_1) + (i - 1) \times l$

顺序表（元素）：

地址连续
依次存放
随机存取
类型相同

:black_circle:顺序表的存储结构：

#define MAX 100;                                    // 线性表存储空间的初始分配量
typedef struct {
  ElemType *elem;                                    // 存储空间的基地址
  int length;                                            // 当前长度
}SqList;                                                  // 顺序表的结构类型为SqList

:black_circle:多项式的顺序存储结构类型：

#define MAX 100                        // 多项式可能达到的最大长度

typedef struct {                    // 多项式非零项的定义
  float p;                                // 系数
  int e;                                    // 指数
}Pal;

typedef struct{
  Pal *elem;                            // 存储空间的基地址
  int length;                            // 多项式中当前项的个数
}SqList;                                    // 多项式的顺序存储结构类型为SqList

:black_circle:图书表的顺序存储结构：

#define MAXSIZE 10000                 // 图书表可能达到的最大长度

typedef struct {                            // 图书信息定义
  char no[20];                                // 图书ISBN
  char name[50];                            // 图书名字
  float price;                                // 图书价格
}Book;

typedef struct {
  Book *elem;                                    // 存储空间的基地址
  int length;                                    // 图书表中当前图书个数
}SqList;                                            // 图书表的顺序存储结构类型为SqList

补充一：C语言的内存动态分配需加载头文件<stdlib.h>

SqList L;
L.data = (ElemType*)malloc(sizeof(ElemType)*MaxSize);

malloc(m)函数：开辟m字节长度的地址空间，并返回这段空间的首地址

sizeof(x)运算：计算变量x的长度

free(p)函数：释放指针p所指变量的存储空间，即彻底删除一个变量

补充二：C++中的参数传递

函数调用时传送给形参表的实参必须与形参三个一致：类型、个数、顺序
参数传递有两种方式
传值方式（参数为整型、实型、字符型等）

传地址

参数为指针变量

#include<iostream>
void swap(float *m, float *n) {
  float t;
  t = *m;
  *m = *n;
  *n = t;
}
void main() {
  float a, b, *p1, *p2;
  cin >> a >> b;
  p1 = &a;
  p2 = &b;
  swap(p1, p2);
  cout << a << endl << b << endl;
}

参数为引用类型

#include<iostream>
void swap(float& m, float& n) {
  float temp;
  temp = m;
  m = n;
  n = temp;
}
void main() {
  float a, b;
  cin >> a >> b;
  swap(a, b);
  cout << a << endl << b << endl;
}

参数为数组名

2.3.2、线性表基本操作的实现

补充：操作算法中用到的预定义常量和类型：

// 函数结果状态代码

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

#define OVERFLOW -2

// Status是函数的类型，其值是函数结果状态代码

typedef int Status;

typedef char ElemType;

1、线性表的L的初始化（参数用引用）

为顺序表L动态分配一个预定义大小的数组空间，使elem指向这段空间的基地址
将表的当前长度设为0

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

2、销毁线性表

使用delete 释放存储空间即可

void DestroyList(SqList &L) {
  if (L.elem) delete L.elem;            // 释放存储空间
}

3、清空线性表L

将线性表的长度设置为0

void ClearList(SqList &L) {
  L.length = 0;                            // 将线性表的长度设置为0
}

补充：销毁与清空线性表的最大区别在于线性表是否还暂用存储空间

4、求线性表的长度

int GetLength(SqList L) {
  return (L.length);
}

5、判断线性表是否为空

int IsEmpty(SqList L) {
  if (L.length == 0) return 1;
  else return 0;
}

6、顺序表的取值（根据指定的位置序号i，获取第i个数据元素的值）

判断i值是否合理（1 <= i <= L.length），若不合理返回ERROR
若i值合理，则将第i个数据元素L.elem[i - 1]赋给参数e，通过e返回第i个数据元素的传值。

int GetElem(SqList L, int i, ElemType &e) {
  if (i < 1 || i > L.length) return ERROR;        // 判断i值是否合理，若不合理返回ERROR
  e = L.elem[i - 1];                                                    // 第i - 1的单元存储着第i个数据
  return OK;
}

7、顺序表的查找

从第一个元素起，依次和e比较相等的元素L.elem[i]，则查找成功，返回该元素的序号i + 1；
若查遍整个顺序表都没有找到，则查找失败，返回0

int LocateElem(SqList L, ElemType e) {            // 在顺序表中查找值为e的数据元素，返回其序号
  for (int i = 0; i < L.length; i++)                
    if (L.elem[i] == e) return i + 1;                // 查找成功，返回序号i + 1
  return 0;                                                                    // 查找失败，返回0
}

// while循环
int LocateElem(SqList L, ElemType e) {                            // 在线性表L中查找值为e的数据元素，返回其序号
  i = 0;
  while (i < L.length && L.elem[i] != e) i++;
  if (i < L.length) return i + 1;                                        // 若查找成功，返回序号
  return 0;                                                                                    // 查找失败，返回0
}

8、顺序表的插入

判断插入位置i是否合法（i值的合法范围是1 <= i <= n + 1），若不合法则返回ERROR。
判断顺序表的存储空间是否已满，若满则返回ERROR
将第n个至第i - 1个位置的元素依次向后移动一个位置，空出第i个位置（i = n + 1时无需移动）
将要插入的新元素e放入第i个位置
表长加1

Status ListInsert(SqList &L, int i, ElemType e) {
  // 在顺序表L中的第i个位置插入新元素e，i值的合法范围是1 <= i <= L.length + 1
  if ((i < 1) || (i > L.length)) return ERROR;         // i值不合法
  if (L.length == MAXSIZE) return ERROR;                    // 当前存储空间已满
  for (j = L.length - 1; j >= i - 1; j--)                 
    L.elem[j + 1] = L.elem[j];                                        // 插入位置之后的元素后移
  L.elem[i - 1] = e;                                                            // 将新元素e放入第i个位置
  ++L.length;                                                                            // 表长加1
  return OK;
}

9、顺序表的删除

判断删除位置i是否合法（和法值为1 <= i <= n），若不合法则返回ERROR
将第i + 1个至第n个的元素依次向前移动一个位置（i = n时无须移动）
表长减1

Status ListDelete(SqList &L, int i) {
  // 在顺序表中删除第i个元素，i值的合法范围是1 <= i <= L.length
  if ((i < 1) || (i > L.length)) return ERROR;                // i值不合法
  for (j = i; j <= L.length - 1; j++)
    L.elem[j - 1] = L.elem[j];                                                // 被删除元素之后的元素前移
  --L.length;                                                                                    // 表长减1
  return OK;
}

小结：顺序表（线性表的顺序存储结构）的特点

利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构一致
在访问线性表时，可以快速的计算出任何一个数据元素的存储地址。
基本操作：重点：查找、插入、删除操作
算法分析：
- 时间复杂度：插入、查找、删除算法的平均时间复杂度为$O(n)$
- 空间复杂度：顺序表操作算法的空间复杂度$S(n) = O(1)$
顺序表的缺点：
- 在插入、删除某一个元素时，需要移动大量元素
- 浪费存储空间
- 静态存储形式，数据元素的个数不能自由扩充

顺序表的代码实现（C语言、Java）

C语言：

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

#define MAXSIZE 100     // 定义顺序表的最大长度

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

/**初始化顺序表*/
void InitList(SqList *L)
{
    L ->length = 0;
}

/**建立顺序表*/
int CreateList(SqList *L, int a[], int n)
{
    if (n > MAXSIZE)
    {
        printf("空间不足，无法建立顺序表。\n");
        return 0;
    }
    for (int i = 0; i < n; i++)
    {
        L->data[i] = a[i];
    }
    L->length = n;
    return 1;
}

/**判断顺序表是否为空*/
int IsEmpty(SqList *L)
{
    if (L->length == 0)
        return 1;
    else return 0;
}

/**清空顺序表*/
void ClearList(SqList *L)
{
    L->length = 0;
}

/**求线性表的长度*/
int GetLength(SqList *L)
{
    return (L->length);
}

/**打印顺序表*/
void PrintfList(SqList *L)
{
    for (int i = 0; i < L->length; i++)
        printf("%d ", L->data[i]);
}

/**顺序表的取值*/
int GetElem(SqList *L, int i, int e)
{
    if (i < 1 || i > L->length) return 0;
    e = L->data[i - 1];
    return 1;
}

/**按值查找*/
int LocateElem(SqList *L, int x)
{
    for (int i = 0; i < L->length; i++)
        if (L->data[i] == x) return i + 1;
    return 1;
}

/**按位置查找*/
int GetLocate(SqList *L, int x, int *prt)
{
    if (x < 1 || x > L->length)
    {
        printf("查找位置非法，查找错误。\n");
        return 0;
    }
    else
    {
        *prt = L->data[x];
        return 1;
    }
}


/**插入操作*/
int ListInsert(SqList *L, int i, int x)
{
    if (L->length > MAXSIZE)
    {
        printf("上溢错误。\n");
        return 0;
    }
    if (i < 1 || i > L->length)
    {
        printf("插入位置错误!\n");
        return 0;
    }
    for (int k = L->length; k > i; k--)
    {
        L->data[k] = L->data[k - 1];
    }
    L->data[i] = x;
    L->length++;
    return 1;
}

/**顺序表的删除*/
int DeleteElem(SqList *L, int i, int *prt)
{
    if ((i < 1) || (i > L->length))
    {
        printf("删除位置错误!\n");
        return 0;
    }
    if (L->length == 0)
    {
        printf("顺序表为空删除失败！");
        return 0;
    }
    *prt = L->data[i - 1];
    for (int k = i; k <= L->length - 1; k++)
    {
        L->data[k - 1] = L->data[k];
    }
    L->length--;
    return 1;
}


int main()
{
    int a[5] = {1, 2, 3, 4, 5};
    int i, x;
    SqList list;
    InitList(&list);
    if (IsEmpty(&list))
    {
        printf("初始化顺序表成功！\n");
    }
    printf("给顺序表赋值：1 2 3 4 5\n");
    CreateList(&list, a, 5);
    PrintfList(&list);
    printf("\n在第三位后插入一个20：\n");
    ListInsert(&list, 3, 20);
    PrintfList(&list);
    if (DeleteElem(&list, 4, &x) == 1)
    {
        printf("\n把第四位删除，删除值是%d\n", x);
        PrintfList(&list);
    }
    return 0;
}

Java语言：

package struct;

import java.util.Arrays;

/**
 * @author java小豪
 * @version 1.0.0
 * @description 顺序表的实现
 */
public class SqList {
  
    /**存储数据的空间*/
    private int[] data;
    /**有效数据的长度*/
    private int length;

    public SqList() {
        this.data = new int[10];
    }

    /**
     * 顺序表的插入
     * @param pos 插入位置
     * @param x 插入的数据
     */
    public void add(int pos, int x) {
        // 判断顺序表是否为满
        if (this.data.length == length) {
            System.out.println("顺序表满了，扩充");
            this.data = Arrays.copyOf(this.data, this.data.length * 2);
        }
        // 判断插入位置是否合法
        if (pos < 0 || pos > this.length) {
            System.out.println("插入位置不合法");
        }
        // 插入元素
        for (int i = this.length - 1; i >= pos; i--) {
            this.data[i + 1] = this.data[i];
        }
        this.data[pos] = x;
        length++;
    }

    /**
     * 查找元素
     * @param x 查找的元素
     * @return 返回该元素的位置
     */
    public int search(int x) {
        // 判断顺序表是否为空
        if (this.length == 0 ) {
            throw new RuntimeException("顺序表为空");
        }
        // 查找该元素的位置
        for (int i = 0; i < this.data.length; i++) {
            if (this.data[i] == x) {
                return i;
            }
        }
        return -1;
    }


    public void delete(int x) {
        // 判断是否含有该元素
        int index = search(x);
        if (index == -1) {
            System.out.println("删除的元素不存在");
        }
        // 删除元素
        for (int i = index; i < this.length; i++) {
            this.data[i] = this.data[i + 1];
        }
        length--;
    }

    /**
     * 修改顺序表中的元素
     * @param pos 修改元素的位置
     * @param x 修改后的值
     */
    public void modify(int pos, int x) {
        // 判断顺序表是否为空
        if (this.length == 0) {
            throw new RuntimeException("顺序表为空");
        }
        // 判断pos位置有效性
        if (pos < 0 || pos > this.length) {
            throw new RuntimeException("删除位置不和法");
        }
        // 修改元素
        this.data[pos] = x;
    }

    /**
     * 打印顺序表
     */
    public void print() {
        for (int i = 0; i < this.length; i++) {
            System.out.print(this.data[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        SqList sqList = new SqList();
        sqList.add(0, 1);
        sqList.add(0, 2);
        sqList.add(0, 3);
        sqList.add(0, 4);
        sqList.add(0, 5);
        System.out.println("=====================查找====================");
        sqList.print();
        System.out.println("查找元素下标为:" + sqList.search(1));
        System.out.println("查找元素下标为:" + sqList.search(3));
        System.out.println("查找元素下标为:" + sqList.search(5));
        System.out.println("=====================删除====================");
        sqList.delete(1);
        sqList.delete(5);
        sqList.print();
        System.out.println("=====================修改====================");
        sqList.modify(0,10);
        sqList.modify(1,20);
        sqList.print();


    }
}

数据结构（严蔚敏版）第二章 ——线性表（一）

第二章线性表

2.0、回顾

2.1、线性表的定义和特点

线性表的定义

线性表的特点：

2.2、线性表的类型定义

2.3、线性表的顺序表示和实现

2.3.1、线性表的顺序存储和表示

2.3.2、线性表基本操作的实现

1、线性表的L的初始化（参数用引用）

2、销毁线性表

3、清空线性表L

4、求线性表的长度

5、判断线性表是否为空

6、顺序表的取值（根据指定的位置序号i，获取第i个数据元素的值）

7、顺序表的查找

8、顺序表的插入

9、顺序表的删除

小结：顺序表（线性表的顺序存储结构）的特点

顺序表的代码实现（C语言、Java）

热门文章

最新文章

相关课程

相关电子书

数据结构（严蔚敏版）第二章 ——线性表（一）

第二章 线性表

2.0、回顾

2.1、线性表的定义和特点

线性表的定义

线性表的特点：

2.2、线性表的类型定义

2.3、线性表的顺序表示和实现

2.3.1、线性表的顺序存储和表示

2.3.2、线性表基本操作的实现

1、线性表的L的初始化（参数用引用）

2、销毁线性表

3、清空线性表L

4、求线性表的长度

5、判断线性表是否为空

6、顺序表的取值（根据指定的位置序号i，获取第i个数据元素的值）

7、顺序表的查找

8、顺序表的插入

9、顺序表的删除

小结：顺序表（线性表的顺序存储结构）的特点

顺序表的代码实现（C语言、Java）

热门文章

最新文章

相关课程

相关电子书

第二章线性表