C语言|数据结构——线性结构（线性表及其实现）

短命女 2024-04-01 11:15 90阅读 0赞

## 线性表（Linear List） ##

--------------------

由同种数据元素构成有序序列的线性结构

*  表中元素个数称为线性表的长度
 *  线性表没有元素时，称为空表
 *  表起始位置称表头，结束位置称表尾

### 抽象数据类型描述 ###

--------------------

**类型名称**：线性表(List)

**数据对象集**：n(>=0)个元素构成的有序序列

**操作集**：假定线性表类型为List，其中具体的一个线性表为L，里面有个元素类型为ElementType的x，主要操作有：

1.  List MakeEmpty():初始化一个空线性表L
2.  ElementType FindKth(int K,list L):根据位序k，返回相应元素
3.  int Find(ElementType X,List L):在线性表L中查找X的第一次出现位置：
4.  void insert(ElementType X, int i, List L):在位序i前插入一个新元素X
5.  void Delete(int i, List L):删除指定位序i的元素
6.  int Length(List L):返回线性表L的长度n

### 线性表的存储 ###

--------------------

#### 顺序存储 ####

利用数组的连续存储空间顺序存放线性表的各元素

由于是连续，所以要定义一个Last来存储最后一个元素，表明结尾的位置

typedef struct LNode*List;
    struct LNode{
            ElementType Data[MAXSIZE];
            int Last;
    };
    struct LNode L;
    List PtrL;

### **主要操作的实现** ###

#### **初始化** ####

List MakeEmpty()
    {
        List PtrL;
        PtrL = (List)malloc(sizeof(struct LNode));
        ptrL->Last = -1;
        return PtrL;
    }

#### 查找 ####

int Find(ElementType X,List PtrL)
    {
        int i = 0;
        while(i<=PtrL->Last && PtrL->Data[i]!= X )
            i++;
        if(i>PtrL->Last)
            return -1;
        else return i;
    }

这种查找成功的平均比较此时为(n+1)/2,平均时间性能为O(n)

### 线性表推广 ###

### 广义表（Generalized List） ###

对于线性表 n个元素都是基本的单元素

对于广义表 这些元素不仅可以是单元素也可以是另一个广义表

typedef struct GNode *Glist;
    struct GNode{
        int Tag;                /*标志域：0表示节点是单元素，1表示结点是广义表*/
        union {
            ElemenType Data;    /*子表指针域Sublist与单元素数据域Data复用，即共用存储空间*/
            GList SubList;
            }URegion;
            GList Next;        /*指向后继结点*/
    };

## 多重链表 ##

广义表实际上就是多重链表

多重链表中的结点可能同时隶属多个链

指针域会有多个，例如上面代码行中的Next和SubList两个指针域

但双向链表中包含两个指针域，并不是多重链表

### 用途 ###

基本上树、图这样相对复杂的数据结构都可以采用多重链表方式实现存储。

#### 矩阵 ####

采用典型的多重链表——**十字链表**来代替二维数组来**存储稀疏矩阵**

（二维数组存储稀疏矩阵缺点：1.会造成大量空间浪费

2.数组大小需要事先确定）

*  **只存储矩阵非0元素项**