数据结构与算法~线性表总结

博主： Xherlock
发布时间：2021 年 09 月 22 日
511 次浏览
暂无评论
5751字数
分类：数据结构与算法

# 线性表

## 顺序表

### 顺序存储结构

用一段地址连续的存储单元依次存储线性表的数据元素，即在内存中找了一块内存地址，通过占位的形式，占用一定内存空间，然后把相同数据类型的数据元素依次存储在该空间，顺序表逻辑上相邻的元素在物理上也是相邻的，每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数，（逻辑和物理上都相邻）只要确定了第一个元素的起始位置，线性表中的任意一个元素都可以随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构；数组即为这种顺序存储结构，数组的长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的。

线性表--顺序存储-->顺序表

### C语言动态分布函数<stdlib.h>

* malloc(m): 开辟m字节的地址空间，并返回这段空间的首地址
* sizeof(x): 计算变量x的长度
* free(p): 释放指针p所指变量的存储空间，及彻底删除某个变量

### 顺序表基本操作

#### 结构定义

~~~C
#define  MAXSIZE 100     //最大长度
typedef  struct 
{
 	 ElemType  *elem;      //指向数据元素的基地址
  	int  length;                 //线性表的当前长度                      
 }SqList；
~~~

#### 初始化

1. 为顺序表L动态分配一个一个预定义大小的数组空间
2. 将表的当前长度设为0

#### 取值

1. 判断指定位置序号i是否合理(1<=i<=L.length),若不符合，返回ERROR
2. 若合理，将第i个数据元素的值赋给参数e，通过e返回传值

时间复杂度：O(1)

#### 查找

1. 从第一个元素开始依次比较e（指定值），找到返回序号i+1
2. 若遍历全部无，查找失败返回0

时间复杂度：O(n);        f(n)=(n+1)/2

#### 插入

1. 判断插入位置合理（1<=i<=n+1）
2. 判断存储空间是否已满
3. 将从第n个到第i个位置的元素以此后移一位，空出第i个位置（i=n+1无需移动）
4. 插入元素放入
5. 表长加一

时间复杂度：O(n)

#### 删除

1. 判断插入位置合理（1<=i<=n）
2. 将第i+1个至第n个的元素依次向前移动一个位置（i=n时无需移动）
3. 表长减一

时间复杂度：O(n)

### 顺序表优缺点

#### 优点

* 快速存取表中任一元素，存取效率高
* 内存空间连续，空间利用率高
* 尾插或者尾删元素时效率较高

#### 缺点

* 在顺序表中间插入或者删除元素时需要移动大量元素，效率低
* 需要预先分配足够大的空间，过大导致空间闲置，过小造成溢出

### 随机存取法

* 利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即**线性表的逻辑结构与存储结构一致**
* 在访问线性表时，可以快速的计算出任何一个数据元素的存储地址，因此可以粗略认为，**访问每个元素多花时间相等**

## 链表

### 链式存储结构

采用一组任意的连续或非连续存储单元存储线性表的元素；为了表示每个元素x~i~与其直接后继a~i~+1的逻辑关系，链式存储不仅需要存储元素本身，还要存储一个指向其直接后继元素的地址，这种存储结构被称之为**结点**（node），**存储元素数值数据**的叫**数据域**，**存储后继结点地址**的叫**指针域**，结点元素的逻辑顺序称之为线性链表或单链表，（逻辑上相邻的数据元素在物理上不一定相邻）因为第一个结点没有直接前驱结点，因此需要一个头指针指向它，为了方便操作放在第一个元素结点之前一个结点称之为头结点，头指针变为指向头结点，其数据域可以存放如线性表长度等信息，而指针域则存放第一个元素结点的地址信息，若该链表为空，则头结点指针域为空；因为，最后一个元素没有直接后继元素，所以将其指针域设置为“Null”空，对于插入或删除数据越频繁的操作，单链表的效率就越明显。

* 头指针：指向链表中第一个结点的指针
* 首元结点：链表中存储第一个数据元素的结点
* 头结点：在链表的首元结点之前辐射的一个结点，数据域内只放空表标志和表长等信息

表示空表：有头结点时，当头结点的指针域为空时表示空表

![9DA05C1E80A162EAA2C9859529FAB403.png][1]

设置头结点的好处：

（1）便于首元结点的处理：

```
首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其他位置一致，无需进行特殊处理
```

（2）便于空表和非空表的统一处理：

```
无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了
```

* 单链表（线性链表）：结点只有一个指针域的链表
* 双链表：有两个指针域的链表
* 循环链表：首尾相接的链表

### 顺序存取法

* 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
* 访问时只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等

### 链表优缺点

#### 优点

* 数据元素的个数可以自由扩充
* 插入、删除等操作不必移动数据，只需修改链接指针，修改效率高

#### 缺点

* 存储密度小
* 存取效率不高，必须采用顺序存取，及存取数据元素时，只能按链表的顺序进行访问

### 单链表

#### 结构定义

~~~C
typedef struct Lnode
{
     ElemType   data;       //数据域
     struct LNode  *next;   //指针域
}LNode,*LinkList;   
// *LinkList为Lnode类型的指针
~~~

指针变量p：表示结点地址	LinkList p

结点变量*p：表示一个结点	LNode *p

#### 初始化

1. 生成新结点作为头结点，用头指针指向头结点
2. 头结点的指针域置空

#### 建立

##### 前插法

1. 创建一个只有头结点的空链表
2. 开始循环，生成新结点\*p
3. 输入元素值赋给新结点\*p的数据域
4. 将新结点\*p插入到头结点之后

因为每次插入在链表的表头，所以输入顺序和输出顺序（逻辑顺序）相反

~~~C
void CreateList_F(LinkList &L,int n){ 
     L=new LNode; 
      L->next=NULL; //先建立一个带头结点的单链表 
      for(i=n;i>0;--i){ 
        p=new LNode; //生成新结点 
        cin>>p->data; //输入元素值 
        p->next=L->next;L->next=p; 	//插入到表头 
     } 
}//CreateList_F 
~~~

时间复杂度：O(n)

##### 后插法

1. 创建一个只有头结点的空链表
2. 尾指针q初始化指向头结点
3. 开始循环，生成新结点\*p
4. 输入元素值赋给新结点\*p的数据域
5. 将新结点\*p插入到尾结点\*r之后
6. 尾指针r指向新的尾结点\*p

输入顺序与输出顺序（逻辑顺序）相同

~~~C
void CreateList_L(LinkList &L,int n){ 
      //正位序输入n个元素的值，建立带表头结点的单链表L 
      L=new LNode; 
      L->next=NULL; 
      q=L; 	                                //尾指针r指向头结点 
      for(i=0;i<n;++i){ 
        p=new LNode;	　	       //生成新结点 
        cin>>p->data;   		       //输入元素值 
        p->next=NULL; 
        q->next=p;       //插入到表尾 
        q=p; 	                                  //r指向新的尾结点 
      } 
}//CreateList_L 
~~~

时间复杂度：O(n)

#### 销毁

链表销毁后不存在，头指针和头结点都不存在

1. 指针p指向头结点，头结点指向下一结点
2. 释放p结点，循环直至头结点指向为空

~~~C
Status DestoryList(LinkList& L)
{
	LinkList p;
	while(L!=NULL)
	{
		p=L;
		L=L->next;
		free(p);
	}
	return OK;
}
~~~

#### 清空

链表仍存在，单链表五元素，称为空链表，头指针和头结点仍存在

1. 指针p指向首元结点
2. 引入新结点q指向p的下一结点，并释放p结点，循环至p为空

~~~C
int ClearList(LinkList& L)
{
	LinkList P=L->next;
	while(p!=NULL)
	{
		LinkList q=p->next;
		delete p;//删除p本身（指针p本身并没有撤销，它自己仍然存在，该指针所占内存空间并未释放）
		p=q;
	}
	L->next=NULL;
	return 0;
}
~~~

#### 求表长

1. 指针p指向首元节点，定义整型变量cnt用于计数
2. 指针p依次指向各个结点，cnt++，若p指向的结点为空，则停止

~~~C
int ListLength(LinkList L)
{
	LinkList p=L->next;
	int i=0;
	while(p!=NULL)//当首元结点为空时，表长为0
	{
		i++;
		p=p->next;
	}
	return i;
}
~~~

#### 判断链表是否为空

1. 判断头指针的指针域是否为空
2. 为空则返回0，不空返回1

~~~C
int EmptyList(LinkList L)
{
	if(L->next!=NULL)//非空
		return 1;
	else 
		return 0;
~~~

#### 取值

1. 指针p指向首元结点，用cnt作为计数器赋初值为1
2. 从首元点依次顺着链域向下访问，只要指向当前结点的指针p不为空且未达到i，每次循环cnt++，p指向下一个结点
3. 退出循环后，若指针p为空挥着计数器cnt>i，则取值失败；否则成功

~~~C
Status GetElem_L(LinkList L,int i,ElemType &e){ 
    p=L->next;
    cnt=1; //初始化
     while(p&&cnt<i){	//向后扫描，直到p指向第i个元素或p为空 
       p=p->next; 
       cnt++; 
     } 
     if(!p || cnt>i)
         return ERROR; //第i个元素不存在 
     e=p->data; //取第i个元素 
     return OK; 
}//GetElem_L 
~~~

**注意**：若e为数值型数据，则上述方法没问题；若e为字符型，则必须使用strcpy(p->data, e)进行赋值，直接赋值会报“表达式必须是可修改的左值”的错误，同理后面的比较值用strcmp(p->data, e)

时间复杂度：一般来说我们认为是O(n),这种情况是**已知头结点的链表，找到第i个取值**，需要从头向后遍历，找到后改变指针指向，需要O(1)的时间，总的就是O(n)

但当给出头结点同时给出要求元素的地址，比如在[数据结构与算法~单链表 - 404！v|+_+|v 404！](http://120.78.215.15/index.php/archives/9/)这篇文章中给出的实验例子就是LocateNode函数返回结点地址，此时时间复杂度就为O(1)

#### 查找

1. 指针p指向首元结点
2. 依次指向下一结点，取数值域与e的值比较，若等于则返回p的地址
3. 循环完后没有找到则返回NULL

~~~C
LNode *LocateELem_L (LinkList L，Elemtype e) {
 //返回L中值为e的数据元素的地址，查找失败返回NULL
  p=L->next;
  while(p &&p->data!=e)  
        p=p->next;                	
  return p; 
} 
~~~

也可设成返回位置序号，但因为是链表，这样不太好，毕竟是动态分配的

时间复杂度：O(n) 按顺序存取的方式查找

#### 插入

将新结点插入到第i个结点的位置上，即插入到a~i-1~与a~i~之间

1. 找到a~i-1~存储的位置并由指针p指向该结点
2. 生成一个新结点\*s
3. 将\*s的数据域设为e
4. 将新结点*s的指针域指向结点a~i~
5. 将结点\*p的指针域指向新结点\*s

~~~C
Status ListInsert_L(LinkList &L,int i,ElemType e){ 
     p=L;j=0; 
      while(p&&j<i−1){p=p->next;++j;}	//寻找第i−1个结点 
      if(!p||j>i−1)return ERROR;	//i大于表长 + 1或者小于1  
      s=new LNode;			//生成新结点s 
      s->data=e;      		           //将结点s的数据域置为e 
      s->next=p->next;	   	          //将结点s插入L中 
      p->next=s; 
      return OK; 
}//ListInsert_L 
~~~

时间复杂度：O(n) /O(1) 与取值同理

**但是**

#### 删除

将表的第i个结点删除

1. 找到a~i-1~存储的位置并由指针p指向该结点
2. 临时保存a~i~的地址在q中，以备释放
3. 令p->next指向a~i~->next即q->next
4. 释放q的存储空间

~~~C
 Status ListDelete_L(LinkList &L,int i,ElemType &e){
    p=L;j=0; 
    while(p->next &&j<i-1){                  //寻找第i个结点，并令p指向其前驱 
        p=p->next; ++j; 
    } 
    if(!(p->next)||j>i-1) 
        return ERROR; //删除位置不合理 
    q=p->next;                                        //临时保存被删结点的地址以备释放 
    p->next=q->next; 	                  //改变删除结点前驱结点的指针域 
    e=q->data; 	                                //保存删除结点的数据域 
    delete q; 	                                //释放删除结点的空间 
 return OK; 
}//ListDelete_L 
~~~

时间复杂度：O(n) /O(1) 与取值同理

### 循环链表

表中的最后一个结点的指针域指向头结点，整个链表形成一个环

从任一结点出发均可找到表中其他结点

和单链表的不同在于判断尾结点时判断条件为：p!=L or p->next!=L

有时候不给出头指针而给出尾指针，可以更方便地找到第一个和最后一个结点

#### 合并

将第一个表的尾指针指向第二个表的第一个结点，第二个表的尾指针指向第一个表的头结点，然后释放第二个表的头结点

![image-20210922175650061.png][2]

### 双链表

貌似不是重点，就借用老师ppt的截图了，大概了解

#### 定义结构

![image-20210922231938784.png][3]
![image-20210922232038800.png][4]

#### 插入

![image-20210922232300594.png][5]

~~~C
Status ListInsert_DuL(DuLinkList &L,int i,ElemType e){
   if(!(p=GetElemP_DuL(L,i))) 
       return ERROR;
   s=new DuLNode; 
   s->data=e;
   s->prior=p->prior;  
   p->prior->next=s;
   s->next=p;  
   p->prior=s;
   return OK;
}
~~~

#### 删除

![image-20210922232454984.png][6]

## 顺序表和链表对比

![image-20210922233140045.png][7]

[1]: http://120.78.215.15/usr/uploads/2021/09/1747384053.png
[2]: http://120.78.215.15/usr/uploads/2021/09/3027908418.png
[3]: http://120.78.215.15/usr/uploads/2021/09/2062554900.png
[4]: http://120.78.215.15/usr/uploads/2021/09/3955049315.png
[5]: http://120.78.215.15/usr/uploads/2021/09/3713393582.png
[6]: http://120.78.215.15/usr/uploads/2021/09/95334711.png
[7]: http://120.78.215.15/usr/uploads/2021/09/3419489504.png

最后修改：2021 年 10 月 25 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

Reverse（十一）
浏览次数: 2629
Win11新机鼓捣记录
浏览次数: 2382
栈~数制转换
浏览次数: 1604
C++学习
浏览次数: 1603
Python实现文件管理系统（重命名和删除）
浏览次数: 1575

顶点软件
你写得非常清晰明了，让我很容易理解你的观点。
mars
博主你好，请问怎么知道的alloc函数属于Buffer下的方法...
lj
该评论仅登录用户及评论双方可见
Mr.Guan
:@(赞一个)
Typecho
欢迎加入 Typecho 大家族

机器学习1
浏览次数: 432
机试day4
浏览次数: 317
彩色打字效果
浏览次数: 565
ASCII艺术签名绘图
浏览次数: 855
文件管理
浏览次数: 454

数据结构与算法~线性表总结

Xherlock • 2021 年 09 月 22 日

# 线性表

## 顺序表

### 顺序存储结构

线性表--顺序存储-->顺序表

### C语言动态分布函数<stdlib.h>

* malloc(m): 开辟m字节的地址空间，并返回这段空间的首地址
* sizeof(x): 计算变量x的长度
* free(p): 释放指针p所指变量的存储空间，及彻底删除某个变量

### 顺序表基本操作

#### 结构定义

#### 初始化

1. 为顺序表L动态分配一个一个预定义大小的数组空间
2. 将表的当前长度设为0

#### 取值

1. 判断指定位置序号i是否合理(1<=i<=L.length),若不符合，返回ERROR
2. 若合理，将第i个数据元素的值赋给参数e，通过e返回传值

时间复杂度：O(1)

#### 查找

1. 从第一个元素开始依次比较e（指定值），找到返回序号i+1
2. 若遍历全部无，查找失败返回0

时间复杂度：O(n);        f(n)=(n+1)/2

#### 插入

时间复杂度：O(n)

#### 删除

1. 判断插入位置合理（1<=i<=n）
2. 将第i+1个至第n个的元素依次向前移动一个位置（i=n时无需移动）
3. 表长减一

时间复杂度：O(n)

### 顺序表优缺点

#### 优点

* 快速存取表中任一元素，存取效率高
* 内存空间连续，空间利用率高
* 尾插或者尾删元素时效率较高

#### 缺点

* 在顺序表中间插入或者删除元素时需要移动大量元素，效率低
* 需要预先分配足够大的空间，过大导致空间闲置，过小造成溢出

### 随机存取法

## 链表

### 链式存储结构

表示空表：有头结点时，当头结点的指针域为空时表示空表

![9DA05C1E80A162EAA2C9859529FAB403.png][1]

设置头结点的好处：

（1）便于首元结点的处理：

```
首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其他位置一致，无需进行特殊处理
```

（2）便于空表和非空表的统一处理：

```
无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了
```

* 单链表（线性链表）：结点只有一个指针域的链表
* 双链表：有两个指针域的链表
* 循环链表：首尾相接的链表

### 顺序存取法

### 链表优缺点

#### 优点

* 数据元素的个数可以自由扩充
* 插入、删除等操作不必移动数据，只需修改链接指针，修改效率高

#### 缺点

* 存储密度小
* 存取效率不高，必须采用顺序存取，及存取数据元素时，只能按链表的顺序进行访问

### 单链表

#### 结构定义

~~~C
typedef struct Lnode
{
     ElemType   data;       //数据域
     struct LNode  *next;   //指针域
}LNode,*LinkList;   
// *LinkList为Lnode类型的指针
~~~

指针变量p：表示结点地址	LinkList p

结点变量*p：表示一个结点	LNode *p

#### 初始化

1. 生成新结点作为头结点，用头指针指向头结点
2. 头结点的指针域置空

#### 建立

##### 前插法

1. 创建一个只有头结点的空链表
2. 开始循环，生成新结点\*p
3. 输入元素值赋给新结点\*p的数据域
4. 将新结点\*p插入到头结点之后

因为每次插入在链表的表头，所以输入顺序和输出顺序（逻辑顺序）相反

时间复杂度：O(n)

##### 后插法

输入顺序与输出顺序（逻辑顺序）相同

时间复杂度：O(n)

#### 销毁

链表销毁后不存在，头指针和头结点都不存在

1. 指针p指向头结点，头结点指向下一结点
2. 释放p结点，循环直至头结点指向为空

~~~C
Status DestoryList(LinkList& L)
{
	LinkList p;
	while(L!=NULL)
	{
		p=L;
		L=L->next;
		free(p);
	}
	return OK;
}
~~~

#### 清空

链表仍存在，单链表五元素，称为空链表，头指针和头结点仍存在

1. 指针p指向首元结点
2. 引入新结点q指向p的下一结点，并释放p结点，循环至p为空

#### 求表长

1. 指针p指向首元节点，定义整型变量cnt用于计数
2. 指针p依次指向各个结点，cnt++，若p指向的结点为空，则停止

~~~C
int ListLength(LinkList L)
{
	LinkList p=L->next;
	int i=0;
	while(p!=NULL)//当首元结点为空时，表长为0
	{
		i++;
		p=p->next;
	}
	return i;
}
~~~

#### 判断链表是否为空

1. 判断头指针的指针域是否为空
2. 为空则返回0，不空返回1

~~~C
int EmptyList(LinkList L)
{
	if(L->next!=NULL)//非空
		return 1;
	else 
		return 0;
~~~

#### 取值

#### 查找

1. 指针p指向首元结点
2. 依次指向下一结点，取数值域与e的值比较，若等于则返回p的地址
3. 循环完后没有找到则返回NULL

也可设成返回位置序号，但因为是链表，这样不太好，毕竟是动态分配的

时间复杂度：O(n) 按顺序存取的方式查找

#### 插入

将新结点插入到第i个结点的位置上，即插入到a~i-1~与a~i~之间

时间复杂度：O(n) /O(1) 与取值同理

**但是**

#### 删除

将表的第i个结点删除

1. 找到a~i-1~存储的位置并由指针p指向该结点
2. 临时保存a~i~的地址在q中，以备释放
3. 令p->next指向a~i~->next即q->next
4. 释放q的存储空间

时间复杂度：O(n) /O(1) 与取值同理

### 循环链表

表中的最后一个结点的指针域指向头结点，整个链表形成一个环

从任一结点出发均可找到表中其他结点

和单链表的不同在于判断尾结点时判断条件为：p!=L or p->next!=L

有时候不给出头指针而给出尾指针，可以更方便地找到第一个和最后一个结点

#### 合并

将第一个表的尾指针指向第二个表的第一个结点，第二个表的尾指针指向第一个表的头结点，然后释放第二个表的头结点

![image-20210922175650061.png][2]

### 双链表

貌似不是重点，就借用老师ppt的截图了，大概了解

#### 定义结构

![image-20210922231938784.png][3]
![image-20210922232038800.png][4]

#### 插入

![image-20210922232300594.png][5]

#### 删除

![image-20210922232454984.png][6]

## 顺序表和链表对比

![image-20210922233140045.png][7]

发表评论 取消回复

数据结构与算法~线性表总结

发表评论取消回复