木道寻08

这个屌丝很懒，什么也没留下！

热门标签

数据结构（二）——详解单链表与链式存储结构的增改删查的实现_利用线性表的链式储存结构,建立一个整型单链表,分别实现数据的增删改查

作者：木道寻08 | 2024-07-15 13:36:12

踩

利用线性表的链式储存结构,建立一个整型单链表,分别实现数据的增删改查

文章目录

一.单链表
二.单链表的实现
三.单链表增改删查完整代码实现：
- 3.1 头插法实现：
- 3.2 尾插法实现：
3.3 适用类模板实现：
四.小结

一.单链表

1.1单链表：线性表的链接存储结构。

存储思想：用一组任意的存储单元存放线性表的元素。
其中，任意的含义为：连续、不连续、零散分布
例如：(a1, a2 ,a3, a4)的存储示意图如下：
在这里插入图片描述
由图可以发现单链表的存储特点：

逻辑次序和物理次序不一定相同，即每个内存可以在内存表中任意存放。
元素之间的逻辑关系用指针表示。

1.2单链表的结点结构

单链表是由若干结点构成的，单链表的结点只有一个指针域。
在这里插入图片描述
单链表的结点结构的定义如下：

template <class DataType>
struct Node
{
     DataType data;
     Node<DataType> *next;
}; 
1
2
3
4
5
6

当申请结点时，采用$s=new Node ;的形式即可申请一个新结点

1.3定义头结点

头结点定义：在单链表的第以一个元素结点之前附设一个类型相同的结点，以便空表和非空表处理统一。
例如，空表和非空表的头结点如下，即第一个结点不存放任何元素，只作为一个地址来引出链表：在这里插入图片描述

二.单链表的实现

2.1单链表的实现——遍历操作

核心操作（关键操作）：工作指针后移。从头结点（或开始结点）出发，通过工作指针的反复后移而将整个单链表“审视”一遍的方法称为扫描（或遍历）,如图所示：
在这里插入图片描述

代码实现如下：

template <class DataType>
void LinkList<DataType> :: PrintList( )
{
     p = first->next; 
     while (p != NULL)
     {
         cout << p->data;
         p = p->next;   
     }
}
1
2
3
4
5
6
7
8
9
10

先让p指针指向单链表的头结点的下一个结点，即 p = first->next;，然后遍历这个链表，让p指针不为空时（因为单链表最后一个结点的地址为空），输出p指针所指向的该结点的数据部分，然后让p指向下一个结点即可，这样便能遍历整个单链表

2.2单链表的实现——求表长

在这里插入图片描述
求表长的伪代码如下：

工作指针p初始化; 累加器count初始化;
重复执行下述操作，直到p为空：
2.1 工作指针p后移;
2.2 count++;
返回累加器count的值；

如上图所示，与遍历单链表类似，先让p指针指向单链表的头结点的下一个结点，然后定义count长度为1，然后遍历该单链表，每当p指向下一个结点时，便让count长度+1，最后返回count长度即可啦
代码实现如下：

template <class DataType>
int LinkList<DataType> :: Length( )
{
     p = first->next; count = 1;     
     while (p != NULL)
     {
         p = p->next;
         count++;
     }
     return count;     //注意count的初始化和返回值之间的关系
}
1
2
3
4
5
6
7
8
9
10
11

2.3单链表的实现——按位取值与按值查找

2.3.1按位取值

算法思想：先让p指针指向单链表的头结点的下一个结点，即第一个结点，然后利用while循环，让p指针不断后移，知道第i个结点为止，最后返回该节点处的元素值 p->data即可实现
代码实现如下：

template <class DataType>
DataType LinkList<DataType> :: Get(int i)
{
     p = first->next; count = 1;     
     while (count!=i)
     {
         p = p->next;
         count++;
     }
     return p->data;    // 返回第i位元素的值
}
1
2
3
4
5
6
7
8
9
10
11

2.3.2按值查找

算法思想：先让p指针指向单链表的头结点的下一个结点，即第一个结点，然后同样利用while循环，遍历单链表的所有元素，当该结点处的数据值与要找的数据值相同是，返回该节点的位置，否则让p指向下一个结点；如果遍历完都没有找到该数值，便返回0.
代码实现如下：

template <class DataType>  
int LinkList<DataType> :: Locate(DataType x) 
{
    p = first->next;  count = 1;         
    while (p != NULL)    
    {
        if (p->data == x) return count;     //查找成功，返回序号
        p = p->next;                   
        count++;
    }
    return 0;                                          //退出循环表明查找失败
}
1
2
3
4
5
6
7
8
9
10
11
12

2.4单链表的实现———插入

在这里插入图片描述
如图所示，假如我们想将结点s插入到结点p之后，我们应该怎么做呢？
首先，我们先定义结点s，s=new Node;
然后，初始化结点s处的数据为x：s->data=x;
接下来让s的下一个结点指向 $a_i$ ，也就是指向p原本的下一个结点p->next：s->next=p->next;
最后，我们修改p的下一个结点，不让它指向 $a_i$ 了，指向插入的新结点s即可：p->next=s;
同时我们分析边界情况，当插入的结点为表头或者表尾时：
在这里插入图片描述
我们发现和插在表中的做法一致，因此不需要更改~
算法描述——伪代码如下：

工作指针p初始化；
查找第i-1个结点并使工作指针p指向该结点；
若查找不成功，则插入位置不合理，抛出插入位置异常；
否则，
3.1 生成一个元素值为x的新结点s；
3.2 将新结点s插入到结点p之后；

代码实现如下：

template <class DataType>  
 void LinkList<DataType> :: Insert(int i, DataType x)
 {
      p = first ; count = 0;             //工作指针p应指向头结点
      while (p != NULL && count < i - 1)     //查找第i – 1个结点
     {
          p = p->next;                   
          count++;
     }
     if (p == NULL) throw "位置";      //没有找到第i – 1个结点
    else { 
        s = new Node;  s->data = x;         //申请一个结点s
        s->next = p->next; p->next = s;   //结点s插入结点p之后
    }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

我们在第i个结点处插入元素x，先找到第i-1个结点，然后申请结点s，利用上面的分析插入即可。

2.5单链表的实现———构造函数

构造单链表有两种方法，分别为头插法和尾插法。

2.5.1 头插法：将待插入结点插在头结点的后面

例如我们要构造的线性表如下：
在这里插入图片描述
首先，我们初始化结点:

first=new Node<DataType>; 
first->next=NULL; 
1
2

然后，我们插入第一个元素结点s：
在这里插入图片描述

s=new Node<DataType>; 
s->data=a[0];
s->next=first->next;
first->next=s; 
1
2
3
4

即先初始化结点s，让结点s的数据值为a[0]，然后让s的下一个结点指向之前头结点指向的下一个结点，也就是空节点，再让头结点的下一个结点指向s结点即可。
然后我们依次插入每一个结点：在这里插入图片描述

s=new Node<DataType>; 
s->data=a[1];
s->next=first->next;
first->next=s; 
1
2
3
4

代码实现如下：

template <class DataType>  
LinkList<DataType> :: LinkList(DataType a[ ], int n)
{
    first = new Node; first->next = NULL;     
    for (i = 0; i < n; i++)
    { 
         s = new Node; s->data = a[i]; 
         s->next = first->next; 
         first->next = s;
    }
}
1
2
3
4
5
6
7
8
9
10
11

2.5.2 尾插法：将待插入结点插在终端结点的后面。

同样是上面那个数组，我们采用尾插法来构造单链表：
在这里插入图片描述
同样是先初始化：

与头插法不同，我们新定义一个结点rear，让他等于头结点

first=new Node<DataType>; 
rear=first;
1
2

然后我们插入第一个元素结点
在这里插入图片描述
这时，我们申请一个结点s，然后让rear的下一个结点指向s（即头结点的下一个结点），再让rear等于结点s，这时rear指向的也是s结点了

s=new Node<DataType>; 
s->data=a[0];
rear->next=s;
rear=s;
1
2
3
4

然后依次插入每一个结点：
在这里插入图片描述

s=new Node<DataType>; 
s->data=a[1];
rear->next=s;
rear=s;
1
2
3
4

最后一个结点插入后，让rear的下一个结点为NUL即为空即可：

rear->next=NULL
1

在这里插入图片描述
代码实现如下：

template <class DataType>  
LinkList<DataType> :: LinkList(DataType a[ ], int n)
{
    first = new Node;                        //生成头结点
    r = first;                                       //尾指针初始化
    for (i = 0; i < n; i++)
    { 
        s = new Node; s->data = a[i];        
        r->next = s; r = s;                 
    }
    r->next = NULL;        
}
1
2
3
4
5
6
7
8
9
10
11
12

2.6单链表的实现———删除

在这里插入图片描述
如上图所示，假如我们要删除结点q，我们该怎么做呢？
首先，我们应该定义结点q为p的下一个结点：q=p->next;
然后，用x存入要删除的结点q的数据：x=q->data;
接下来让结点p的下一个结点不指向q，指向q的下一个结点即可：p->next=q->next;
最后，我们删除结点q: delete q;
分析特殊情况，假如要删除的是表头或表尾：
在这里插入图片描述
表尾有特殊情况：虽然被删结点不存在，但其前驱结点却存在，因此我们发现同样适用于上述方法。
算法描述——伪代码如下：

1.工作指针p初始化；
2. 查找第i-1个结点并使工作指针p指向该结点；
3. 若p不存在或p不存在后继结点，则抛出位置异常；
否则，
3.1 暂存被删结点和被删元素值；
3.2 摘链，将结点p的后继结点从链表上摘下；
3.3 释放被删结点；
3.4 返回被删元素值；

代码实现如下：

template <class DataType>  
DataType LinkList<DataType> :: Delete(int i)
{
     p = first ; count = 0;            
     while (p != NULL && count < i - 1)
     {
         p = p->next;
         count++;
     }
     if (p == NULL || p->next == NULL)  throw "位置"; 
     else {
         q = p->next; x = q->data;         
         p->next = q->next;              
         delete q; return x;
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.7单链表的实现——析构函数

析构函数将单链表中所有结点的存储空间释放。
在这里插入图片描述
让q指向头结点，然后让结点指向a1，删除结点q，重复该操作即可

q = first; 
first = first->next;
delete q;
1
2
3

具体代码实现如下：

template <class DataType>
LinkList<DataType> :: ~LinkList( )
{
     while (first != NULL)
     {
         q = first;                 
         first = first->next;         
         delete q;    
     }
}
1
2
3
4
5
6
7
8
9
10

三.单链表增改删查完整代码实现：

3.1 头插法实现：

具体代码如下：

#include <iostream>
using namespace std ;

#define ERROR -1
#define CORRECT 1

//定义
struct LNode {
    int data ;
    LNode *next ;
} ;


LNode *LinkList ;

//查找
LNode *SearchLinkList (LNode *L , int i)
{
    int j ;
    LNode *p ;

    p = L ;
    j = 1 ;
    while (p &&j < i)
    {
        p = p -> next ;
        j++ ;
    }
    if (!p || j>i)
    {
        return (p) ;
    }
}

//插入
int InsertLinkList (LNode *L , int e , int i)
{
    //在链表L中第i个位置插入元素e
    LNode *p , *s ;
    p = SearchLinkList (L , i-1) ;
    if (!p)
    {
        return (ERROR) ;
    }
    s = new LNode ;
    //节点插入L中
    s -> data = e ;
    s -> next = p -> next ;
    p -> next = s ;

    return (CORRECT) ;
}

//表单创建, 如果输入的值是65535,代表创建单链表结束
LNode *CreateLinkList (int *r , int n)
{
    int j ;
    LNode *L , *p , *s ;

    if (n <= 0)
    {
        return (NULL) ;
    }
    cout << "Create No.1 Item : "<<endl;
    s = new LNode ;
    s -> data = r[1] ;
    s -> next = NULL ;
    L = s ;
    p = L ;
    for (j = 2 ; j <= n ; j++)
    {   cout <<" Create No." << j <<" Item : "<<endl;

        s = new LNode ;
        s -> data = r[j] ;
        s -> next = NULL ;
        p -> next = s;
        p = s ;


       //InsertLinkList (L , r[j] , j) ;
    }

    return (L) ;
}

//删除
int DeleteLinkList (LNode *L , int i)
{
    //在表中删除第i个位置
    int e ;
    LNode *p , *q ;

    p = SearchLinkList (L , i-1) ;
    if (!p)
    {
        return (ERROR) ;
    }
    q = p -> next ;
    p -> next = p -> next -> next ;    //不可用q，因为q是用来指示将要删除的内存
    e = q -> data ;
    delete (q) ;

    return (e) ;
}

//结果输出
int ShowLinkList (LNode *L)
{
    LNode *p ;

    if (!L)
    {
        return (ERROR) ;
    }
    cout << "The list : " <<endl     ;
    p = L ;
    while (p -> next)
    {
        cout << p -> data <<" " ;
        p = p -> next ;
    }
    cout << p -> data << endl ;
    return (CORRECT) ;
}

int main (int argc , char * argv[])
{
    int  r[100], i ,SampleNum , SearchPos , NewPos , NewItem , DelPos ;
    LNode *p ;
    cout << "Please input the ListLen : "<<endl  ;
    cin >> SampleNum ;

   cout<<endl;

    for (i = 1 ; i <= SampleNum ; i++)
    {   cout << "Please input No." << i <<" Item : "<<endl;;
        cin >> r[i] ;
    }
    LinkList = CreateLinkList (r , SampleNum) ;
    ShowLinkList (LinkList) ;
    cout << "请输入你想查找的位置: "<<endl  ;
    cin >> SearchPos ;
    p = SearchLinkList (LinkList , SearchPos) ;
    if(p)
        cout <<"Search Item: "<< p -> data << endl ;
    else
       cout <<"Search pos not exist: "<<endl;

    cout << "请输入你想插入的位置: " <<endl ;
    cin >> NewPos ;
    cout << "请输入你想插入的数据: " <<endl ;
    cin >> NewItem ;
    InsertLinkList (LinkList , NewItem , NewPos) ;
    cout << "After Insert : " ;
    ShowLinkList (LinkList) ;
    cout << "请输入你想删除的位置: " ;
    cin >> DelPos ;
    DeleteLinkList (LinkList , DelPos) ;
    cout << "After delete : " ;
    ShowLinkList (LinkList) ;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164

实验结果如下：在这里插入图片描述

3.2 尾插法实现：

具体代码如下：

#include <iostream>
#define random(x) (rand()%x)+1
using namespace std ;

#define ERROR -1
#define CORRECT 1

//定义
struct LNode {
    int data ;
    LNode *next ;
} ;
LNode *LinkList ;

//查找
LNode *SearchLinkList (LNode *L , int i)
{
    int j ;
    LNode *p ;

    p = L ;
    j = 1 ;
    while (p &&j < i)
    {
        p = p -> next ;
        j++ ;
    }
    if (!p || j>i)
    {
        return (p) ;
    }
}

//插入
int InsertLinkList (LNode *L , int e , int i)
{
    //在链表L中第i个位置插入元素e
    LNode *p , *s ;
    p = SearchLinkList (L , i-1) ;
    if (!p) 
    {
        return (ERROR) ;
    }
    s = new LNode ;
    //节点插入L中
    s -> data = e ;
    s -> next = p -> next ;
    p -> next = s ;

    return (CORRECT) ;
}

//单链表创建,尾插法
LNode *CreateLinkList( )
{
    int value,j=1 ;
    LNode *L , *p , *s ;

    
    cout<<"Please input No . "<<j<<" node "<<endl;
	cin>>value;
	s = new LNode ;
	L=s;
    p=s;
	while(value!=65535)
    {  s -> data = value;
       s -> next = NULL ;
	   p->next=s;
       p=s;
	   j=j+1;
	   s = new LNode ;
       cout<<"Please input No . "<<j<<" node "<<endl;
   	   cin>>value;
    }  
    s->next=NULL;
    return (L) ;
}

//删除
int DeleteLinkList (LNode *L , int i)
{
    //在表中删除第i个位置
    int e ;
    LNode *p , *q ;

    p = SearchLinkList (L , i-1) ;
    if (!p)
    {
        return (ERROR) ;
    }
    q = p -> next ;
    p -> next = p -> next -> next ;    //不可用q，因为q是用来指示将要删除的内存
    e = q -> data ;
    delete (q) ;

    return (e) ;
}

//结果输出
int ShowLinkList (LNode *L)
{
    LNode *p ;

    if (!L)
    {
        return (ERROR) ;
    }
    p = L ;
    while (p -> next)
    {
        cout << p -> data <<" " ;
        p = p -> next ;
    }
    cout << p -> data << endl ;
    return (CORRECT) ;
}

int main (int argc , char * argv[])
{
    int SearchPos , NewPos , NewItem , DelPos ;
    LNode *p;

    cout << "Create Link ...."<<endl  ;
    LinkList = CreateLinkList () ;
    ShowLinkList (LinkList) ;
    cout << "Create Link  Success! "<<endl  ;
    cout << "Please input the search pos : "<<endl  ;
    cin >> SearchPos ;
    p = SearchLinkList (LinkList , SearchPos) ;
    if(p)
        cout <<"Search Item: "<< p -> data << endl ;
    else
       cout <<"Search pos not exist: "<<endl;

    cout << "Please input the NewPos where you want to insert : " <<endl ;
    cin >> NewPos ;
    cout << "Please input the NewItem where you want to insert : " <<endl ;
    cin >> NewItem ;
    InsertLinkList (LinkList , NewItem , NewPos) ;
    cout << "After Insert : " ;
    ShowLinkList (LinkList) ;
    cout << "Please input the DelPos where you want to delete : " ;
    cin >> DelPos ;
    DeleteLinkList (LinkList , DelPos) ;
    cout << "After delete : " ;
    ShowLinkList (LinkList) ;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

实验结果如下：
在这里插入图片描述

3.3 适用类模板实现：

具体代码如下：

#include<iostream>   //引用输入输出流库函数的头文件
#define random(x) (rand()%x+1)
using namespace std;
#ifndef LinkList_H
#define LinkList_H

template <class DataType>
struct Node
{
      DataType data;
      Node<DataType> *next;  
};

template <class DataType>
class LinkList
{
   public:
	LinkList( );                     //无参构造函数，建立只有头结点的空链表
	LinkList(DataType a[ ], int n);      //有参构造函数，建立有n个元素的单链表
	~LinkList( );                    //析构函数
	int Locate(DataType x);           //按值查找。在单链表中查找值为x的元素序号
	void Insert(int i, DataType x);      //插入操作，第i个位置插入元素值为x的结点
	DataType Delete(int i);           //删除操作，在单链表中删除第i个结点
	void PrintList( );                 //遍历操作，按序号依次输出各元素
   private:
	Node<DataType> *first;                     //单链表的头指针
};
#endif

template <class DataType>
LinkList<DataType> :: LinkList( )
{
	first = new Node<DataType>;                        //生成头结点
	first->next = NULL;                      //头结点的指针域置空
}

template <class DataType>  
LinkList<DataType> :: LinkList(DataType a[ ], int n)
{
	Node<DataType> *r, *s;
	first = new Node<DataType>;                    //生成头结点
	r = first;                            //尾指针初始化
	for (int i = 0; i < n; i++)
	{ 
		s = new Node<DataType>; s->data = a[i];        //为每个数组元素建立一个结点
		r->next = s; r = s;                 //将结点s插入到终端结点之后
	}
	r->next = NULL;        //单链表建立完毕，将终端结点的指针域置空
}

template <class DataType>
LinkList<DataType> :: ~LinkList( )
{
	Node<DataType> *q;
	while (first != NULL)        //释放单链表的每一个结点的存储空间
	{
		q = first;                 //暂存被释放结点
		first = first->next;         // first指向被释放结点的下一个结点
		delete q;    
	}
}

template <class DataType>  
void LinkList<DataType> :: Insert(int i, DataType x)
{
	Node<DataType> *p = first, *s;
	int count = 0;               //工作指针p应指向头结点
    while (p != NULL && count < i - 1)  //查找第i - 1个结点
    {
		p = p->next;                   //工作指针p后移
		count++;
    }
    if (p == NULL) throw "位置";      //没有找到第i - 1个结点
    else {
		s = new Node<DataType>;  s->data = x;     //申请一个结点s，其数据域为x
		s->next = p->next; p->next = s;   //将结点s插入到结点p之后
    }
}

template <class DataType>  
DataType LinkList<DataType> :: Delete(int i)
{
	Node<DataType> *p, *q;
	DataType x;
	int count = 0; 
	p = first;               //注意工作指针p要指向头结点
	while (p != NULL && count < i - 1)  //查找第i-1个结点
	{
		p = p->next;
		count++;
	}
	if (p == NULL || p->next == NULL)  //结点p不存在或p的后继结点不存在
		throw "位置"; 
	else {
		q = p->next; x = q->data;         //暂存被删结点
		p->next = q->next;              //摘链
		delete q; 
		return x;
	}
}

template <class DataType>  
int LinkList<DataType> :: Locate(DataType x) 
{
	Node<DataType> *p = first->next;
	int count = 1;         //工作指针p和累加器count初始化
	while (p != NULL)    
	{
		if (p->data == x) return count;     //查找成功，结束函数并返回序号
		p = p->next;                   
		count++;
	}
	return 0;                        //退出循环表明查找失败
}

template <class DataType>
void LinkList<DataType> :: PrintList( )
{
	Node<DataType> *p = first->next;                 //工作指针p初始化
	while (p != NULL)
	{
		cout << p->data<<"  ";
		p = p->next;                 //工作指针p后移，注意不能写作p++
	}
	cout<<endl;
}


void main( )
{
		int r[6];
		for(int i=0;i<6;i++)
			r[i]=random(100);
		LinkList<int> L(r, 6);
		cout<<"执行插入操作前数据为："<<endl;
		L.PrintList( );                  //显示链表中所有元素
		try
		{
			L.Insert(5, 99);
		}
		catch (char *s)
		{
			cout<<s<<endl;
		}
		cout<<"执行插入操作后数据为："<<endl;
		L.PrintList( );                  //显示链表中所有元素
		cout<<endl;
		cout<<"值为99的元素位置为:";
		cout<<L.Locate(99)<<endl;        //查找元素5，并返回在单链表中位置
		cout<<endl;
		cout<<"执行删除操作前数据为："<<endl;     
		L.PrintList( );   
		cout<<endl;
		//显示链表中所有元素
		try
		{
			L.Delete(1);                    //删除元素4
		}
		catch (char *s)
		{
			cout<<s<<endl;
		}
		cout<<"执行删除操作后数据为："<<endl;     
		L.PrintList( );                  //显示链表中所有元素
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166

实验结果如下：
在这里插入图片描述

四.小结

链式存储结构不光有单链表，还有双链表、循环链表、静态链表等等，在此不详细说明了。

4.1> 算法设计的一般步骤：

与此同时，我们可以得到算法设计的一般过程如下：

第一步：确定入口（已知条件）、出口（结果）；
第二步：根据一个小实例画出示意图；
第三步：
①正向思维：选定一个思考问题的起点，逐步提出问题、解决问题
② 逆向思维：从结论出发分析为达到这个结论应该先有什么；
③ 正逆结合；
第四步：写出顶层较抽象算法，分析边界情况；
第五步：验证第四步的算法；
第六步：写出具体算法；
第七步：进一步验证，手工运行。

4.2顺序表和链表的比较

4.2.1存储分配方式比较：

顺序表采用顺序存储结构，即用一段地址连续的存储单元依次存储线性表的数据元素，数据元素之间的逻辑关系通过存储位置来实现。
链表采用链接存储结构，即用一组任意的存储单元存放线性表的元素，用指针来反映数据元素之间的逻辑关系。

4.2.2时间性能比较

时间性能是指实现基于某种存储结构的基本操作（即算法）的时间复杂度。
按位查找：
 顺序表的时间为Ｏ(1)，是随机存取；
 链表的时间为Ｏ(n)，是顺序存取。
插入和删除：
 顺序表需移动表长一半的元素，时间为Ｏ(n)；
 链表不需要移动元素，在给出某个合适位置的指针后，插入和删除操作所需的时间仅为Ｏ(1)。

4.2.3空间性能比较

空间性能是指某种存储结构所占用的存储空间的大小。
定义结点的存储密度：
在这里插入图片描述
结点的存储密度：
 顺序表：结点的存储密度为1（只存储数据元素），没有浪费空间；
 链表：结点的存储密度<1（包括数据域和指针域），有指针的结构性开销。

结构的存储密度：
 顺序表：需要预分配存储空间，如果预分配得过大，造成浪费，若估计得过小，又将发生上溢；
链表：不需要预分配空间，只要有内存空间可以分配，单链表中的元素个数就没有限制

4.3 结论

⑴若线性表需频繁查找却很少进行插入和删除操作，或其操作和元素在表中的位置密切相关时，宜采用顺序表作为存储结构；若线性表需频繁插入和删除时，则宜采用链表做存储结构。
⑵当线性表中元素个数变化较大或者未知时，最好使用链表实现；而如果用户事先知道线性表的大致长度，使用顺序表的空间效率会更高。
总之，线性表的顺序实现和链表实现各有其优缺点，不能笼统地说哪种实现更好，只能根据实际问题的具体需要，并对各方面的优缺点加以综合平衡，才能最终选定比较适宜的实现方法。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/木道寻08/article/detail/829636