线性表

定义:

由n(n>=0)个 数据特性相同的元素构成的有限序列称为线性表。
线性表中元素的个数n(n>=0)定义为线性表的长度,n=0时称为空表。

分类:

顺序表(线性表的顺序存储表示):

定义:

用一组地址连续的存储单元依次存储线性表的数据元素。

特点:

  • 逻辑上相邻的数据元素,其物理次序也是相邻的。
  • 线性表的顺序存储结构是一种随机存取的存储结构。
  • 由于数组类型也有随机存储的特性,因此,通常用数组来描述数据结构中的顺序存储结构。
  • 顺序表的存储结构:
1
2
3
4
5
#define MAXSIZE 100			//顺序表可能达到的最大长度
typedef struct{
ElemType *elem; //存储空间的基地址
int length; //当前长度
}SqList;

顺序表中基本操作的实现:

顺序表的初始化:

  • 要求:构造一个空的顺序表
  • 设计:
    a:为顺序表L动态分配一个预定义大小的数组空间,使 elem 指向这段空间的基地址
    b:将表的当前长度设为0
  • 源代码实现:
1
2
3
4
5
6
Status InitList_Sq(SqList &L){			
L.elem=new ElemType[MAXSIZE]; //为顺序表分配一个大小为MAXSIZE的数组空间
if(!L.elem) exit(OVERFLOW); //存储分配失败
L.length=0; //空表长度为0
return OK;
}

取值:

  • 要求:根据指定的位置序号i,获取顺序表中第i 个顺序表中第i 个数据元素的值
  • 设计:
    a:判断指定的位置序号i值是否合理(1<=i<=L.length),若不合理,则返回ERROR
    b:若i值合理,则将第i个数据元素L.elem[i-1]赋给参数e,通过e返回第i个数据元素的值
  • 源代码实现:
1
2
3
4
5
6
Status GetElem (SqList L,int I,ElemType &e)
{
if (i<1||i>L.length) return ERROR; //判断i值是否合理,若不合理,返回error
e=L.elem[i-1]; //elem[i-1]单元存储第i个数据元素
return OK;
}

查找:

  • 要求:根据指定的元素值e,查找顺序表中第1个与e相等的元素。若查找成功,返回该元素在表中的位置序号;若查找失败,则返回0
  • 设计:
    a:从第一个元素起,依次和e相比较,若找到与e相等的元素L.elem[i],则返回该元素的序号i+1
    b:若查遍整个顺序表都没有找到,则查找失败,返回0
  • 源代码实现:
1
2
3
4
5
int LocateElem_Sq(SqList L,ElemType e){		
for(int i=0;i<L.length;i++)
if(L.elem[i]==e) return i+1;
return 0;
}

插入:

  • 要求:在表的第i个位置插入一个新的数据元素e
  • 设计:
    a:判断插入位置i是否合法(i值的合法范围是1<=i<=n+1),若不合法则返回ERROR
    b:判断顺序表的存储空间是否已满,若满则返回ERROR
    c:将第n个至第i个位置的元素依次向后移动一个位置,空出第i个位置(i=n+1时无需移动)
    d:将要插入的新元素e放入第i个位置
    e:表长加1
  • 源代码实现:
1
2
3
4
5
6
7
8
9
Status ListInsert_Sq(SqList L,int i,ElemType e){		
if(i<1 || i>L.length+1) return ERROR; //i值不合法
if(L.length==MAXSIZE) return ERROR; //当前存储空间已满
for(int 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;
}

删除:

  • 要求:将表的第i个元素删去
  • 设计:
    a:判断删除位置i是否合法(合法值为1<=i<=n),若不合法,则返回ERROR
    b:将第i+1个至第n个的元素依次向前移动一个位置(i=n是无需移动)
    c:表长减1
  • 源代码实现:
1
2
3
4
5
6
7
8
Status ListDelete_Sq(SqList &L,int i,ElemType &e){		
if(i<1 || i>L.length) return ERROR; //i值不合法
e=L.elem[i-1]; //将欲删除的元素保留在e中
for(int j=i;j<=L.length;j++)
L.elem[j-1]=L.elem[j]; //被删除元素之后的元素前移
--L.length; //表长减1
return OK;
}

线性表操作实例:

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
#include<iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status; //Status 是函数返回值类型,其值是函数结果状态代码。
typedef int ElemType; //ElemType 为可定义的数据类型,此设为int类型

#define MAXSIZE 100 //顺序表可能达到的最大长度

typedef struct{
ElemType *elem; //存储空间的基地址
int length; //当前长度
}SqList;

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

int LocateElem_Sq(SqList L,ElemType e){ //算法2.2 顺序表的查找
//顺序表的查找
for(int i=0;i<L.length;i++)
if(L.elem[i]==e) return i+1;
return 0;
}

Status ListInsert_Sq(SqList &L,int i,ElemType e){ //算法2.3 顺序表的插入
//在顺序表L中第i个位置之前插入新的元素e
//i值的合法范围是1<=i<=L.length+1
if(i<1 || i>L.length+1) return ERROR; //i值不合法
if(L.length==MAXSIZE) return ERROR; //当前存储空间已满
for(int 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;
}

Status ListDelete_Sq(SqList &L,int i,ElemType &e){ //算法2.4 顺序表的删除
//在顺序表L中删除第i个元素,并用e返回其值
//i值的合法范围是1<=i<=L.length
if(i<1 || i>L.length) return ERROR; //i值不合法
e=L.elem[i-1]; //将欲删除的元素保留在e中
for(int j=i;j<=L.length;j++)
L.elem[j-1]=L.elem[j]; //被删除元素之后的元素前移
--L.length; //表长减1
return OK;
}
//求线性表最大数
Status MaxElem_Sq (SqList L, ElemType Max) {
int i; //定义循环变量
Max= L.elem[0]; //定义Max变量,并将数组内的第一个元素 赋给它
for (i = 1; i<L.length; i++) {
if (L.elem[i]>Max)
Max = L.elem[i]; //从第二个元素开始,将其与max进行比较,如果大于max,则将max赋给该元素
}
return Max;
}
int main()
{
SqList L;
int i,res,temp,a,b,c,e,choose,max,Max;
cout<<"1. 建立顺序表\n";
cout<<"2. 输入数据\n";
cout<<"3. 查找\n";
cout<<"4. 插入\n";
cout<<"5. 删除\n";
cout<<"6. 输出数据\n";
cout<<"7.求线性表最大数\n";
cout<<"0. 退出\n\n";

choose=-1;
while(choose!=0)
{
cout<<"请选择:";
cin>>choose;
switch(choose)
{
case 1:
if(InitList_Sq(L)) //创建顺序表
cout<<"成功建立顺序表\n\n";
else
cout<<"顺序表建立失败\n\n";
break;
case 2: //输入10个数
cout<<"请输入10个数:\n";
for(i=0;i<10;i++)
cin>>L.elem[i];
cout<<"输入成功!";
L.length=10;
cout<<endl;
break;
case 3: //顺序表的查找
cout<<"请输入所要查找的数:";
cin>>e; //输入e,代表所要查找的数值
temp=LocateElem_Sq(L,e);
if(temp!=0)
cout<<e<<" 是第 "<<temp<<"个数.\n\n";
else
cout<<"查找失败!没有这样的数\n\n";
break;
case 4: //顺序表的插入
cout<<"请输入两个数,分别代表插入的位置和插入数值:";
cin>>a>>b; //输入a和b,a代表插入的位置,b代表插入的数值
if(ListInsert_Sq(L,a,b))
cout<<"插入成功.\n\n";
else
cout<<"I插入失败.\n\n";
break;
case 5: //顺序表的删除
cout<<"请输入要删除的数的位置:";
cin>>c; //输入c,代表要删除数的位置
if(ListDelete_Sq(L,c,res))
cout<<"删除成功.\n被删除的数是:"<<res<<endl<<endl;
else
cout<<"删除失败.\n\n";
break;
case 6: //顺序表的输出
cout<<"当前顺序表为:\n";
for(i=0;i<L.length;i++)
cout<<L.elem[i]<<" ";
cout<<endl<<endl;
break;
case 7:
cout << "当前顺序表中的最大数为:";
max=MaxElem_Sq(L,Max); //函数调用
cout << max;
}
}
return 0;
}

##单链表(线性表的链式存储结构):

定义:

用一组任意的存储单元存储线性表的数据元素。

特点:

  • 存储直接后继存储位置的域称为指针域,存储数据元素信息的域成为数据域
  • 指针域中存储的信息称作指针或链。
  • 用单链表表示线性表时,数据元素之间的逻辑关系是由结点中的指针指示的。
  • 单链表是非随机存取的存取结构
  • 单链表的存储结构:
1
2
3
4
5
typedef struct LNode
{
ElemType data; //结点的数据域
struct LNode *next; //结点的指针域
}LNode,*LinkList; //LinkList为指向结构体LNode的指针类型

单链表基本操作的实现:

初始化:

  • 要求:构造一个空的单链表L
  • 设计:
    a:生成新结点作为头结点,用头指针L指向头结点。
    b:头结点的指针域置空
  • 源代码实现:
1
2
3
4
5
Status InitList_L(LinkList &L){				
L=new LNode; //生成新结点作为头结点,用头指针L指向头结点
L->next=NULL; //头结点的指针域置空
return OK;
}

取值:

  • 要求:在带头结点的单链表L中查找第i个元素
  • 设计:
    a:用指针p指向首元结点,用j做计数器初值赋为1
    b:从首元结点开始依次顺着链域next向下访问,只要指向当前结点的指针P不为空(NULL),并且没有到达序号为i的结点,则循环执行以下操作:
    1) p指向下一个结点;
    2) 计数器j相应加1.

    c:退出循环时,如果指针p为空,或者计数器j大于i,说明指定的序号i值不合法(i大于表长n或i小于等于0),取值失败返回ERROR;否则取值成功,此时j=i时,p所指的结点就是要找的第i个结点,用参数e保存当前结点的数据域,返回OK.

  • 源代码实现:
1
2
3
4
5
6
7
8
9
10
11
Status GetElem_L(LinkList L,int i,ElemType &e){		
int j;
LNode *p;
p=L->next;j=1; //初始化,p指向第一个结点,j为计数器
while(j<i&&p){ //顺链域向后扫描,直到p指向第i个元素或p为空
p=p->next;++j;
}
if(!p || j>i) return ERROR; //第i个元素不存在
e=p->data; //取第i个元素
return OK;
}

单链表的按值查找:

  • 要求:在带头结点的单链表L中查找值为e的元素
  • 设计:
    a:用指针p指向首元结点
    b:从首元结点开始依次顺着链域next向下查找,只要指向当前结点的指针p不为空,并且p所指结点的数据域不等于给定值e,则循环执行以下操作:p指向下一个结点。
    c:返回p.若查找成功,p此时即为结点的地址值,若查找失败,p的值即为NULL。

  • 源代码实现:

1
2
3
4
5
6
7
LNode *LocateElem_L(LinkList L,ElemType e){			
LNode *p;
p=L->next;
while(p&&p->data!=e)
p=p->next; //寻找满足条件的结点
return p; //返回L中的值为e的数据元素的位置,查找失败返回NULL
}

插入:

  • 要求:在带头结点的单链表L中第i个位置之前插入元素e
  • 设计:
    a:查找结点ai-1 ,并由指针p指向该结点
    b:生成一个新结点s
    c:将新结点
    s的数据域置为e
    d:将新结点s的指针域指向结点ai
    e:将结点
    p 的指针域指向新结点 *s
  • 源代码实现:
1
2
3
4
5
6
7
8
9
10
11
12
Status ListInsert_L(LinkList &L,int i,ElemType &e){	
int j;
LNode *p,*s;
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;
}

删除:

  • 要求:在带头结点的单链表L中,删除第i个元素
  • 设计:
    a:查找结点ai-1并由指针p指向该结点
    b:临时保存待删除结点ai的地址在q中,以备释放
    c:将结点*p 的指针域指向ai的直接后继结点
    d:释放结点ai的空间
  • 源代码实现:
1
2
3
4
5
6
7
8
9
10
11
Status ListDelete_L(LinkList &L,int i,ElemType &e){	
LNode *p,*q;
int j;
p=L;j=0;
while(p->next && j<i-1){p=p->next;++j;} //寻找第i-1个结点
if(!(p->next) || j>i-1) return ERROR; //i大于表长+1或者小于1
q=p->next; //临时保存被删结点的地址以备释放
p->next=q->next; //改变删除结点前驱结点的指针域
delete q; //释放删除结点的空间
return OK;
}

前插法创建单链表:

  • 要求:逆位序输入n个元素的值,建立带表头结点的单链表L
  • 设计:
    a:创建一个只有头结点的空链表
    b:根据待创建链表包括的元素个数n,循环n次执行以下操作:

     ① 生成一个新结点p
     ② 输入元素值赋给新结点
    p的数据域
     ③ 将新结点*p插入到头结点之后  

  • 源代码实现:
1
2
3
4
5
6
7
8
9
10
11
void CreateList_F(LinkList &L,int n){			
LNode *p;
L=new LNode;
L->next=NULL; //先建立一个带头结点的空链表
cout<<"请输入 "<<n<<" 个数:\n";
for(int i=n;i>0;--i){
p=new LNode; //生成新结点
cin>>p->data; //输入元素值
p->next=L->next;L->next=p; //插入到表头
}
}

后插法创建单链表:

  • 要求:正位序输入n个元素的值,建立带表头结点的单链表L
  • 设计:
    a:创建一个只有头结点的空链表
    b:尾指针r初始化,指向头结点
    c:根据创建链表包括的元素个数n,循环n次执行以下操作:

  ① 生成一个新结点p
 ② 输入元素值赋给新结点
p的数据域
 ③ 将新结点p插入到头结点之后
 ④ 尾指针r指向新的尾结点
p

单链表操作实例:

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
167
168
169
170
171
172
173
174
175
#include<iostream>
using namespace std;

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status; //Status 是函数返回值类型,其值是函数结果状态代码。
typedef int ElemType; //ElemType 为可定义的数据类型,此设为int类型

typedef struct LNode
{
ElemType data; //结点的数据域
struct LNode *next; //结点的指针域
}LNode,*LinkList; //LinkList为指向结构体LNode的指针类型


Status InitList_L(LinkList &L){ //算法2.5 单链表的初始化
//构造一个空的单链表L
L=new LNode; //生成新结点作为头结点,用头指针L指向头结点
L->next=NULL; //头结点的指针域置空
return OK;
}

Status GetElem_L(LinkList L,int i,ElemType &e){ //算法2.6 按序号查找
//在带头结点的单链表L中查找第i个元素
int j;
LNode *p;
p=L->next;j=1; //初始化,p指向第一个结点,j为计数器
while(j<i&&p){ //顺链域向后扫描,直到p指向第i个元素或p为空
p=p->next;++j;
}
if(!p || j>i) return ERROR; //第i个元素不存在
e=p->data; //取第i个元素
return OK;
} //GetElem_L

LNode *LocateElem_L(LinkList L,ElemType e){ //算法2.7 按值查找
//在带头结点的单链表L中查找值为e的元素
LNode *p;
p=L->next;
while(p&&p->data!=e)
p=p->next; //寻找满足条件的结点
return p; //返回L中的值为e的数据元素的位置,查找失败返回NULL
} //LocateElem_L

Status ListInsert_L(LinkList &L,int i,ElemType &e){ //算法2.8 单链表的插入
//在带头结点的单链表L中第i个位置之前插入元素e
int j;
LNode *p,*s;
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

Status ListDelete_L(LinkList &L,int i,ElemType &e){ //算法2.9 单链表的删除
//在带头结点的单链表L中,删除第i个位置,并由e返回值
LNode *p,*q;
int j;
p=L;j=0;
while(p->next && j<i-1){p=p->next;++j;} //寻找第i-1个结点
if(!(p->next) || j>i-1) return ERROR; //i大于表长+1或者小于1
q=p->next; //临时保存被删结点的地址以备释放
p->next=q->next; //改变删除结点前驱结点的指针域
e=q->data; //保存删除结点的数据域
delete q; //释放删除结点的空间
return OK;
} //ListDelete_L

void CreateList_F(LinkList &L,int n){ //算法2.10 前插法创建单链表
//逆位序输入n个元素的值,建立到头结点的单链表L
LNode *p;
L=new LNode;
L->next=NULL; //先建立一个带头结点的空链表
cout<<"请输入 "<<n<<" 个数:\n";
for(int i=n;i>0;--i){
p=new LNode; //生成新结点
cin>>p->data; //输入元素值
p->next=L->next;L->next=p; //插入到表头
}
} //CreateList_F

void CreateList_L(LinkList &L,int n){ //算法2.11 后插法创建单链表
//正位序输入n个元素的值,建立到头结点的单链表L
LNode *r,*p;
L=new LNode;
L->next=NULL; //先建立一个带头结点的空链表
r=L; //尾指针r指向头结点
cout<<"请输入 "<<n<<" 个数:\n";
for(int i=0;i<n;i++){
p=new LNode; //生成新结点
cin>>p->data; //输入元素值
p->next=NULL;r->next=p; //插入到表尾
r=p; //r指向新的尾结点
}
} //CreateList_L

int main()
{
int res,a,b,choose;
LNode *L,*p;
cout<<"1. 建立链表\n";
cout<<"2. 输入数据\n";
cout<<"3. 按位置查找\n";
cout<<"4. 按值查找\n";
cout<<"5. 链表的插入\n";
cout<<"6. 链表的删除\n";
cout<<"7. 输出数据\n";
cout<<"0. 退出\n\n";

choose=-1;
while(choose!=0)
{
cout<<"请选择:";
cin>>choose;
switch(choose)
{
case 1: //建立一个单链表
if(InitList_L(L))
cout<<"成功建立链表!\n\n";
break;
case 2: //使用后插法创建单链表
CreateList_L(L,10);
cout<<"成功创建链表!\n\n";
break;
case 3: //单链表的按序号查找
cout<<"请输入一个位置用来查找:";
cin>>a;
if(GetElem_L(L,a,res))
cout<<"查找成功!第"<<a<<"个数是:"<<res<<"\n\n";
else
cout<<"查找失败\n\n";
break;
case 4: //单链表的按值查找
cout<<"请输入一个数值用来查找:";
cin>>b;
if(LocateElem_L(L,b)!=NULL)
cout<<"查找成功\n\n";
else
cout<<"查找失败! "<<b<<" 没有找到\n\n";
break;
case 5: //单链表的插入
cout<<"请输入两个数分别代表插入的位置和数值:";
cin>>a>>b;
if(ListInsert_L(L,a,b))
cout<<"成功将"<<b<<"插在第"<<a<<"个位置\n\n";
else
cout<<"插入失败!\n\n";
break;
case 6: //单链表的删除
cout<<"请输入一个位置用来删除:";
cin>>a;
if(ListDelete_L(L,a,res))
cout<<"删除成功!被删除的数是:"<<res<<"\n\n";
else
cout<<"删除失败!\n\n";
break;
case 7: //单链表的输出
cout<<"现在链表里的数分别是:\n";
p=L->next;
while(p)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
break;
}
}
return 0;
}
-------------The End-------------