从零开始数据结构的生活(二)

Wangxs

2020 年 07 月 31 日

926 次浏览

暂无评论

3821字数

杂七杂八

# 从零开始数据结构的生活(二)

## 线性表

### 一、什么线性表

线性表就是具有<font color="red">**相同的数据类型**</font>的n(n≥0)个元素的有限序列，除了表头和表尾都具有唯一的前驱和后继。

#### 1.特点

- 个数有限
     - 逻辑上拥有顺序性，表中元素有先后顺序
     - 都是数据元素
     - 数据类型相同

#### 2.基本操作

- InitList(&L): 初始化表。构建一个空的线性表
- Length(L): 求表长。
- LocateElem(L, e)：按值查找元素，e为要查找的值
- getElem(L,i)：按位查找操作。获取表L的第i个位置的元素的值
- ListInsert(&L, i, e): 插入操作
- ListDelete(&L, i, &e)：删除操作
- PrintList(L): 输出操作。按前后顺序输出线性表L的所有元素值
- Empty(L)：判空操作
- DestoryList(&L)：销毁操作

### 二、顺序表

#### 1. 定义

以地址连续的存储单元依次存储线性表中的数据元素称为顺序表

#### 2. 特点

- 随机访问，通过首元素和元素序号可以O(1)内找到指定元素
- 存储密度高，每个节点只存储数据元素
- 逻辑上和物理上元素都相邻，所以插入和删除操作需要移动大量的元素

### 四、链表

#### 1. 定义

以链式存储的线性表称为单链表，除了表结点外还要有一个指向t后继的指针

```c++
typeof struct LNode{    //定义单链表结点类型
    ElemTyppe data;     //数据域
    struct LNode *next; //指针域
}LNode, *LinkList;
```

##### 带头结点的指针

**优点**

- 首结点的操作和其他操作一致，比如删除，插入等
- 空和非空链表不用特殊处理，不是这样如果空要进行空间释放

#### 2. 单链表的实现

- 采用头插法建立单链表

![](https://wangxblog.oss-cn-hangzhou.aliyuncs.com/20200731143819.png)

```c++
  LinkList List_HeadInsert(LinkList &L) {
      LNode *s; int x;
      L = (LinkList)malloc(sizeof(LNode)); //创建头结点
      L->next = NULL; //初始化空链表
      scanf("%d", &x); //输入结点的值
      while(x!=9999){ //输入9999表示结束
          s = (LNode*)malloc(sizeof(LNode)); //创建新节点
          s->data = x;
          s->next = L->next; //图中操作①
          L->next = s; //图中操作②
          scanf("%d", &x);
      }
      return L;
  }
  ```

使用头插法输入的元素是顺序相反的，你最早输入的在最后，最晚输入的最前面。每个结点插入的时间复杂度是O(1),设链表长为n,则总时间复杂度为O(n)。

- 采用尾插法建立单链表

![](https://wangxblog.oss-cn-hangzhou.aliyuncs.com/20200731150226.png)

```c++
  LinkList List_TailInsert(LinkList &L) {
      int x;
      L = (LinkList)malloc(sizeof(LNode));
      LNode *s, *r = L; //r为表尾指针
      scanf("%d", &x);  //输入结点的值
      while(x!=9999) {
          s = (LNode *)malloc(sizeof(LNode));
          s->data=x;
          r->next=s;
          r=s;
          scanf("%d", &x);
      }
      r->next=NULL;
      return L;
  }
  ```

- 按序号查找结点值

```c++
  LNode *GetElem(LinkList L, int i) {
      int j = 1; // 计数初始值为1
      LNode *p = L->next; //头结点指针赋给p
      if(i==0)
          return L; //若i等于0，则返回头结点
      if(i<1)
          return NULL; //若i无效，则返回NULL
      while(p&&j<i) {
          p=p->next;
          j++;
      }
      return p; //返回第i个结点的指针，若i大于表长返回NULL
  }
  ```

- 按值查找结点值

```c++
  Lnode *LocateElem(LinkList L,ElemType e){
      LNode *p = L->next;
      while(p!=NULL&&p->data!=e) 
          p=p->next;
      return p;
  }
  ```

- 插入结点操作

```c++
  void insertElem(LinkList &L, int i, LNode s){
      LNode *p = getElem(L, i-1);
      s->next=p->next;
      p=>next=s;
  }
  ```

- 删除结点操作

```c++
  void deleteElem(LinkList &L,int i){
      LNode *p = getElem(L, i);
      LNode *q = p->next;
      p->next = q->next;
      free(q);
  }
  ```

- 求表长操作

```c++
  int lenLinkList(LinkList L){
      int n = 0;
      LNode *p = L->next;
      while(p!=NULL){
          p = p->next;
          n++;
      }
      return n;
  }
  ```

#### 3. 双链表

![](https://wangxblog.oss-cn-hangzhou.aliyuncs.com/20200731162125.png)

```c++
typedef struct DNode{
    ElemType data; //数据域
    struct DNode *prior, *next; //前驱和后继指针
}DNode, *DLinkList;
DNode getElem(int i, DLinkList L){
    int j = 1; //计数
    DNode *p = L->next;
    if(i==0)
        return L;
    if(i<0)
        return NULL;
    while(p!=NULL && j<i) {
        p = p->next;
    }
    return p;
}
//插入操作
void insertDLinkList(DLinkList &L, int i,LNode s) {
    DNode *p = getElem(i-1,L);
    s->next = p->next;
    p->next->prior=s;
    s->prior=p;
    p->next=s;
}
//删除操作
void deleteDNode(DLinkList &L,int i) {
    DNode *p = getElem(i, L);
    DNode *q = p->next;
    p->next = q->next;
    q->next =->prior=p;
    free(q); //释放空间结点
}
```

### 五、顺序表和链表的区别

- 读写方式
  - 顺序表可以顺序读取也可以随机读取
  - 链表只能顺序读取
- 逻辑结构和物理结构
  - 顺序表逻辑结构上相邻，物理结构上也相邻连续
  - 链表逻辑结构上相邻，但物理结构上分散
- 查找、插入和删除操作
  - 顺序表
    - 按值查找有序时使用折半查找为O(logn),无序时为O(n)
    - 按序号查找为O(1)
    - 插入、删除均为O(n)
  - 链表
    - 按值和按序号均为O(n)
    - 插入和删除均为O(1)
- 空间分配
  - 顺序表：连续的一部分空间，会造成外部碎片，需要预分配，可能会溢出
  - 链表：不连续的空间，利用空间充分

从零开始数据结构的生活(二)