数据结构之线性表

简介:

一、线性表定义:

   线性表是一个线性结构,它是一个含有n≥0个结点的有限序列,其中的结点,有且仅有一个开始结点(第一元素)没有前驱但有一个后继结点,有且仅有一个终端结点(最后节点)没有后继但有一个前驱结点,其它的结点都有且仅有一个前驱和一个后继结点。一般地,一个线性表可以表示成一个线性序列:k1,k2,…,kn,其中k1是开始结点,kn是终端结点。

   上述定义可以用下列图像记忆

    如一对有序序列(A,B,C,............Z)

图表示为

^A(第一节点,没有前驱但有一个后继结点),B,C ……(其它的结点都有且仅有一个前驱和一个后继结点)……….Z(最后节点,没有后继但有一个前驱结点),^

   总结:凡是符合上图特点的均可以认为是线性表。


二、线性表的顺序表示链式表示区别

顺序表


存储图如下

182155988.jpg

特点:

   一、逻辑上相邻的数据元素,物理存储位置也相邻。(逻物一致)

   二、顺序表的存储空间需要预先分配。    

 优点:

  (1)方法简单,各种高级语言中都有数组,容易实现。(语言通用性)

  (2)不用为表示节点间的逻辑关系而增加额外的存储开销。(内存节约性)

  (3)顺序表具有按元素序号随机访问的特点。(逻物一致性)

缺点:

  (1)在顺序表中做插入、删除操作时,平均移动表中的一半元素,因此对n较大的顺序表效率低。(操作低效率)

  (2)需要预先分配足够大的存储空间,估计过大,可能会导致顺序表后部大量闲置;预先分配过小,又会造成溢出。(内存固定性)


链式表

存储图如下


182840238.jpg

182727761.jpg


182727669.jpg



特点:

一、逻辑上相邻的数据元素,物理存储位置不一定相邻。(逻物不一定一致)

二、它使用指针实现元素之间的逻辑关系。并且,链表的存储空间是动态分配的。

链表的最大特点是:插入、删除运算方便。(插入、删除方便)

   优点:

(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,如需转载请自行联系原作者

相关文章
|
7月前
|
存储 算法 Java
52.【Java 数据结构——线性表】(一)
52.【Java 数据结构——线性表】
55 0
|
22天前
|
存储 C语言
【数据结构】线性表的链式存储结构
【数据结构】线性表的链式存储结构
16 0
|
26天前
|
存储 设计模式 算法
【C/C++ 数据结构 线性表】深入理解与实现栈:从基础到应用的全面探索
【C/C++ 数据结构 线性表】深入理解与实现栈:从基础到应用的全面探索
52 0
|
5月前
|
存储 C语言
【数据结构】第八站:线性表的变化
【数据结构】第八站:线性表的变化
32 0
|
1月前
|
存储
数据结构——lesson2线性表和顺序表
数据结构——lesson2线性表和顺序表
|
1月前
|
存储 C语言
数据结构— —线性表的顺序表示和实现
数据结构— —线性表的顺序表示和实现
32 0
|
3月前
|
存储
数据结构——线性表之顺序表
数据结构——线性表之顺序表
41 0
|
3月前
|
存储 缓存 算法
Algorithms_基础数据结构(02)_线性表之链表_单向链表
Algorithms_基础数据结构(02)_线性表之链表_单向链表
38 0
|
3月前
|
存储 人工智能 NoSQL
Algorithms_基础数据结构(01)_线性表之数组&数组的应用案例分析
Algorithms_基础数据结构(01)_线性表之数组&数组的应用案例分析
40 0
|
4月前
数据结构课程_01.线性表
数据结构课程_01.线性表
25 0

热门文章

最新文章