一、线性表定义:
线性表是一个线性结构，它是一个含有n≥0个结点的有限序列，其中的结点，有且仅有一个开始结点(第一元素)没有前驱但有一个后继结点，有且仅有一个终端结点（最后节点）没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。一般地，一个线性表可以表示成一个线性序列：k1,k2,…,kn，其中k1是开始结点，kn是终端结点。
上述定义可以用下列图像记忆
如一对有序序列(A,B,C,............Z)
图表示为
（^，A(第一节点，没有前驱但有一个后继结点),B,C ……(其它的结点都有且仅有一个前驱和一个后继结点)……….Z（最后节点,没有后继但有一个前驱结点），^）
总结：凡是符合上图特点的均可以认为是线性表。
二、线性表的顺序表示与链式表示的区别
顺序表
存储图如下
特点:
一、逻辑上相邻的数据元素，物理存储位置也相邻。（逻物一致）
二、顺序表的存储空间需要预先分配。
优点：
（1）方法简单，各种高级语言中都有数组，容易实现。（语言通用性）
（2）不用为表示节点间的逻辑关系而增加额外的存储开销。(内存节约性)
（3）顺序表具有按元素序号随机访问的特点。(逻物一致性)
缺点：
（1）在顺序表中做插入、删除操作时，平均移动表中的一半元素，因此对n较大的顺序表效率低。（操作低效率）
（2）需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。（内存固定性）
链式表
存储图如下
特点：
一、逻辑上相邻的数据元素，物理存储位置不一定相邻。（逻物不一定一致）
二、它使用指针实现元素之间的逻辑关系。并且，链表的存储空间是动态分配的。
链表的最大特点是：插入、删除运算方便。（插入、删除方便）
优点：
(1)插入、删除运算方便。（插入、删除方便）
(2)内存空间动态分配使得内存使用率高，内存不易溢出。(内存动态分配性)
缺点：
（1）要占用额外的存储空间存储元素之间的关系，存储密度降低。存储密度是指一个节点中数据元素所占的存储单元和整个节点所占的存储单元之比。(内存浪费或内存有效使用率低)
（2）链表不是一种随机存储结构，不能随机存取元素。（逻物不一致）
总结： 顺序表是一种牺牲cpu为代价但节省内存的数据存储方式，链式表是以牺牲内存代价的高效率的存储方式。
实践应用中怎样选取存储结构呢？
1).内存使用率
一般以一顺序存储为主，
但线性表的长度变化较大或者难以估计其存储规模时，宜采用动态链表作为存储结构。
2)基于运算的考虑（时间）
如果不对线性表频发插入或删除操作，以顺序表优先考虑；
否则以链式表优先考虑
三、 线性列表代码：
以顺序存储为例的代码如下：
|
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
|
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define ERROR 0
#define OK 1
#define OVERFLOW -2
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef
int
Status;
typedef
int
ElemType;
typedef
struct
{
int
*elem;
int
length;
int
listsize;
}SqList;
Status InitList_Sq(SqList &L)
{
L.elem = (ElemType *)
malloc
(LIST_INIT_SIZE *
sizeof
(ElemType));
if
(!L.elem)
exit
(OVERFLOW);
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return
OK;
}
//插入
Status ListInsert_Sq(SqList &L,
int
i, ElemType e)
{
ElemType *newbase, *q, *p;
if
(i < 1 || i > L.length + 1)
return
ERROR;
if
(L.length >= L.listsize)
{
newbase = (ElemType *)
realloc
(L.elem, (L.listsize + LISTINCREMENT) *
sizeof
(ElemType));
if
(!newbase)
exit
(OVERFLOW);
L.elem = newbase;
L.listsize += LISTINCREMENT;
}
q = &(L.elem[i - 1]);
for
(p = &(L.elem[L.length - 1]); p >= q; --p)
*(p+1) = *p;
*q = e;
++L.length;
return
OK;
}
//创建
Status CreateList_Sq(SqList &L,
int
n){
int
i; ElemType e;
printf
(
"Please input %d elements:\n"
, n);
for
(i = 1; i <= n; i++){
scanf
(
"%d"
,&e);
ListInsert_Sq(L, i, e);
}
return
OK;
}
//删除
Status DeleteList_Sq(SqList &L,
int
i, ElemType *e){
ElemType *p, *q;
if
(i <= 0 || i > L.length)
return
ERROR;
p = &L.elem[i-1];
*e = *p;
q = L.elem + L.length ;
for
(++p; p < q; ++p)
*(p - 1) = *p;
--L.length;
return
OK;
}
//查找
Status LocateElem(SqList L,
int
num){
int
i = 1;
ElemType *p;
p = L.elem;
while
(i <= L.length && *p != num )
{ ++i; ++p; }
if
(i < L.length)
return
i;
else
return
0;
}
//排序
Status ListAscend_Sq(SqList &L){
int
i, j, k;
ElemType t;
for
(i = 0; i < L.length; i++)
{
k = i;
for
(j = i+1; j < L.length; j++)
if
(L.elem[j] < L.elem[k])
k = j;
if
(k != i)
{
t = L.elem[i];
L.elem[i] = L.elem[k];
L.elem[k] = t;
}
}
return
OK;
}
//输出
void
Print_Sq(SqList L)
{
int
i;
for
(i = 0; i < L.length; i++)
printf
(
"%d "
,L.elem[i]);
printf
(
"\n"
);
}
void
main()
{
Status i, e, num, de, location, position, result;
SqList MyList;
InitList_Sq(MyList);
//初始化
CreateList_Sq(MyList, 10);
//创建
printf
(
"\n"
);
//插入
printf
(
"Please input the number's position and the number to be inserted:"
);
scanf
(
"%d,%d"
, &i, &e);
ListInsert_Sq(MyList,i, e);
printf
(
"\n"
);
printf
(
"Inserted list:\n"
);
Print_Sq(MyList);
printf
(
"\n"
);
//删除
printf
(
"Please input the position(to be deleted):"
);
scanf
(
"%d"
, &position);
result = DeleteList_Sq(MyList, position, &de);
if
(result == OK)
printf
(
"The %dth element %d has been deleted.\n"
, position, de);
Print_Sq(MyList);
//查找
printf
(
"\n"
);
printf
(
"Please input the located number:"
);
scanf
(
"%d"
,&num);
location = LocateElem(MyList, num);
if
(location < 1)
printf
(
"DO NOT EXIST!"
);
else
printf
(
"Location:%d"
,location);
printf
(
"\n\n"
);
ListAscend_Sq(MyList);
//排序
// printf("\n\n");
printf
(
"The sorted list by ascending:\n"
);
Print_Sq(MyList);
//输出
printf
(
"\n"
);
free
(MyList.elem);
//释放空间
}
|
以链式存储为例的代码如下：
|
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
|
#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef
int
Status;
typedef
int
ElemType;
typedef
struct
LNode {
//定义类型链式节点
ElemType data;
struct
LNode * next;
}LNode, *LinkList;
Status InitList_L(LinkList &L){
//初始化链表L，链表的节点个数初始化data = 0； next = null
L = (LinkList)
malloc
(
sizeof
(LNode));
//分配内存空间
if
(!L)
return
ERROR;
L->data = 0;
//节点个数,或称为表长（表的长度）
L->next = NULL;
return
OK;
}
Status Insert_L(LinkList &L,
int
i, ElemType e){
//向链表插入元素e
LNode *p, *q;
int
j = 0;
p = L;
while
(p && j < i - 1){
p = p->next; ++j;
}
if
(!p || j > i - 1)
return
ERROR;
q = (LinkList)
malloc
(
sizeof
(LNode));
q->data = e;
//insert element
q->next = p->next;
p->next = q;
L->data++;
//每插入也节点，表长自加1
return
OK;
}
Status Delete_L(LinkList &L,
int
i, ElemType e){
//删除节点e
LNode *p, *q;
p = L;
int
j = 0;
while
(p->next && j < i - 1){
p = p->next;
++j;
}
if
(!(p->next) || j > i - 1)
return
ERROR;
q = p->next;
p->next = q->next;
e = q->data;
free
(q);
L->data--;
//每删除一个节点，表长自减1
return
OK;
}
Status GetElem_L(LinkList L,
int
i, ElemType &e){
//获取第i个元素，赋值于e
LNode *p;
int
j = 1;
p = L->next;
while
(p && j < i){
p = p->next;
++j;
}
if
(!p || j > i)
return
ERROR;
e = p->data;
return
OK;
}
Status Create_L(LinkList &L){
//创建链表，赋值元素
ElemType temp;
printf
(
"Please input data<9999>ending\n"
);
scanf
(
"%d"
, &temp);
while
(temp != 9999){
Insert_L(L, L->data+1, temp);
scanf
(
"%d"
, &temp);
}
return
OK;
}
Status Traverse_L(LinkList L){
//遍历线性表
LNode *p = L->next;
printf
(
"List contains %d elements:\n"
,L->data);
while
(p){
printf
(
"%5d-->"
,p->data);
p = p->next;
}
printf
(
"NULL\n"
);
return
OK;
}
Status DeleteBet(LinkList &L, ElemType mink, ElemType maxk){
//删除值在(mink,maxk)之间的值
LinkList p, q;
p = L;
if
((mink >= maxk) ||(p->next == NULL))
exit
(ERROR);
while
(p){
if
(p->next->data > mink){
while
(p->next->data < maxk){
q = p->next;
p->next = p->next->next;
free
(q);
L->data --;
}
break
;
}
p = p->next;
}
return
OK;
}
void
main(){
LinkList L;
int
i, i1, i2, e, e1, e2, j1, j2;
InitList_L(L);
//初始化链表
Create_L(L);
//赋值链表
printf
(
"The length is:%d\n"
, L->data);
Traverse_L(L);
//遍历输出节点值
printf
(
"GetElem i:"
);
scanf
(
"%d"
, &i);
GetElem_L(L, i, e);
printf
(
"The NO.%d element is:%d \n"
, i, e);
printf
(
"InsertPosition:"
);
scanf
(
"%d"
, &i1);
printf
(
"Insert element:"
);
scanf
(
"%d"
, &e1);
Insert_L(L, i1, e1);
Traverse_L(L);
//遍历输出节点值
printf
(
"Delete position:"
);
scanf
(
"%d"
, &i2);
Delete_L(L, i2, e2);
Traverse_L(L);
//遍历输出节点值
printf
(
"\nDelete between(a,b):"
);
scanf
(
"%d,%d"
,&j1, &j2);
DeleteBet(L, j1, j2);
printf
(
"The result is:%d\n"
);
Traverse_L(L);
//遍历输出节点值
}
|
四、知识点回顾
线性表的链式存储及特点
–逻物不一定一致、顺序存取、空间利用充分、插删方便
• 单链表(线性链表)及C语言实现
• 头指针、头结点、首元结点
• 单链表的建立、查找、插入、删除、输出
• 单链表与顺序表的比较，及挑
本文转自lilin9105 51CTO博客，原文链接：http://blog.51cto.com/7071976/1206925，如需转载请自行联系原作者
