数据结构之线性表

Bertha 。 2022-06-15 01:14 268阅读 0赞

## 基本概念 ##

线性表（List）：由零个或多个数据元素组成的有限序列。  
特征：  
1.线性表是一个序列。  
2.0个元素构成的线性表是空表。  
3.线性表中的第一个元素无前驱，最后一个元素无后继，其他元素有且只有一个前驱和后继。

4.线性表是有长度的，其长度就是元素个数，且线性表的元素个数是有限的，也就是说，线性表的长度是有限的。

# 线性表抽象数据类型 #

基于线性表的特征，线性表可以做如下操作：

*   InitList(\*L);//初始化操作，建立一个空的线性表
 *   ListEmpty(L);//若线性表为空，返回true,否则返回false
 *   ClearList(\*L);//清空线性表
 *   GetElem(L,i,\*e);//查找线性表中的第i个位置的元素值，并赋值给e
 *   LocateElem(L,e);//查找线性表L中与给定值e相等的元素，如果查找成功，则返回第一个相同的元素在L  //中的下标；否则，返回0表示失败
 *   ListInsert(\*L,i,e);//在线性表L的第i个位置插入元素e
 *   ListDelete(\*L,i,\*e);//删除线性表L中第i个位置元素，并用e返回其值
 *   ListLength();//返回线性表L的长度

线性表和线性表可以进行叠加操作，线性表La和线性表Lb的并集操作，结果保存在La中的伪代码如下：

**\[java\]**  [view plain][]   [copy][view plain]

[print][view plain] [?][view plain]

1.  //实现线性表La和线性表Lb的并集操作，结果保存在La中    
2.      **void** UnionList(\*La,Lb)    
3.  \{    
4.      //计算Lb长度    
5.      **int** lblength = ListLength(Lb);    
6.      //计算La长度    
7.      **int** laLength = ListLength(La);    
8.      **int** i ;    
9.      //便利Lb中所有元素，判断其是否在La中，若不在，则插入La中    
10.     **for** (i=0;i<length;i++)    
11.     \{    
12.         ElemType temp = GetElem(Lb,i,\*e);    
13.         **if** (LocateElem(La,temp)==0)    
14.         \{    
15.             ListInsert(La,++laLength,temp);    
16.         \}    
17.     \}    
18. \}

# 线性表的存储结构 #

根据其字面意思，线性表是顺序存储的，用一段地址连续的存储单元依次存储线性表的数据元素。

如：

**\[objc\]**  [view plain][]   [copy][view plain]

[print][view plain] [?][view plain]

1.  \#define MAXSIZE 20;//存储空间初始分配量为20    
2.  **typedef** **int** ElemType;//数据类型为int    
3.  type **struct**    
4.  \{    
5.      ElemType data\[MAXSIZE\];//数组存储数据元素    
6.      intlength;//线性表长度    
7.  \};

### 关于线性表地址长度的计算 ###

由于顺序存储结构是按照顺序存储的，所以每个数据元素的地址都可以根据第一个元素的地址推算出来。其计算公司LOC(ai) = LOC(a1)+ (i-1)\*c

![20161209100626996][]

# 线性表的基本操作 #

线性表基本操作包含基本的CRUD操作。

## 插入操作 ##

插入操作算法的思路是：  
1.如果插入位置不合理，抛出异常。  
2.如果线性表长度大于等于数组长度，则抛出异常或者增加数组长度。

例如：在线性表L的第i个位置插入元素e

**\[objc\]**  [view plain][]   [copy][view plain]

[print][view plain] [?][view plain]

1.  **int** ListInsert(**Sqlist** \*L, **int** i, ElemType e)  \{    
2.      //插入位置错误，返回0    
3.      **if** (i < 0 || i > L.Length)    
4.      \{    
5.          **return** 0;    
6.      \}    
7.      
8.      //线性表的长度大于等于数组的最大长度，返回0    
9.      **if** (L.Length >= MAXSIZE)    
10.     \{    
11.         **return** 0;    
12.     \}    
13.     
14.     **int** j = L.Length -1;    
15.     //从第i个元素到最后一个元素，每个元素后移一位    
16.     **while** (j >= i)    
17.      \{    
18.          L.data\[j+1\] = L.data\[j\];    
19.          j--;    
20.      \}    
21.     
22.     //第i个元素的位置放入e    
23.     L.data\[i\] = e;    
24.     
25.     //线性表长度加1    
26.     L.Length ++;     
27. \}

## 删除操作 ##

删除操作的思路是：  
1.如果删除位置不合理，抛出异常  
2.取出删除元素  
3.从删除位置开始遍历到最后一个元素，分别将她们都向前移动一个位置  
4.表长减1

例如：我们要删除一个线性表的某一个元素

**\[objc\]**  [view plain][]   [copy][view plain]

[print][view plain] [?][view plain]

1.  **int** ListDelete(**SqList** \*L,**int** i,**ElemType** \*e)  \{    
2.      //如果删除的位置不对，则返回0    
3.      **if** (i < 0 || i > L.Length -1)    
4.      \{    
5.          **return** 0;    
6.      \}    
7.          
8.      \*e = L.data\[i-1\];    
9.      
10.     **for** (j = i-1;i <L.Length\-2;j++ )    
11.     \{    
12.         L.data\[j\] = L.data\[j+1\];    
13.     \}    
14.     
15.     L.Length --;    
16.     **return** 1;     
17. \}

## 查询操作 ##

查询操作是比较简单的，例如：我们要在线性表中查询某个元素的位置。

**\[objc\]**  [view plain][]   [copy][view plain]

[print][view plain] [?][view plain]

1.  **int** GetElem(SqList L,**int** i, **ElemType** \* e)    
2.  \{    
3.      //线性表长度等于0或者获取元素位置错误返回0    
4.      **if** (L.Length == 0 || i < 0 || i > L.Length)    
5.      \{    
6.          **return** 0;    
7.      \}    
8.      
9.      返回第i个元素    
10.     \*e = L.data\[i-1\];    
11.     **return** 1;    
12. \}

### 线性表的缺点 ###

## 顺序表需要预分配一定长度的存储空间，不能动态增长，插入或删除比较麻烦。基于线性表的缺点，有了链式存储线性表。链式存储的特点： ##

**\[objc\]**  [view plain][]   [copy][view plain]

[print][view plain] [?][view plain]

1.  **typedef** **struct** Node    
2.  \{    
3.      ElemType data;    
4.      **struct** **Node** \*next;    
5.  \} Node;    
6.  **typedef** **struct** **Node** \*LinkList;

## 线性表查询 ##

算法思路是：  
1.声明一个节点p指向链表第一个节点，初始化j从1开始  
2.当j< i时，就遍历链表，让P的指针向后移动，不断指向下一个节点，j累加1  
3.若到链表末尾p为空，则说明第i个元素不存在  
4.否则查找成功，返回节点p的数据

**\[objc\]**  [view plain][]   [copy][view plain]

[print][view plain] [?][view plain]

1.  **int** GetElem(LinkList L,**int** i,**ElemType** \*e)    
2.  \{    
3.      **int** j;    
4.      LinkList p;    
5.      p = L->next;//p指向链表第一个节点    
6.      **while** (p && j < i )    
7.      \{    
8.          p = p->next;    
9.          j++;    
10.     \}    
11.     
12.     **if**(!p || count > i)    
13.         **return** 0;    
14.          
15.     \*e = p->data;    
16.     **return** 1;    
17. \}    
18.

[view plain]: http://blog.csdn.net/xiangzhihong8/article/details/53535160#
[20161209100626996]: /images/20220615/59cf456f0e1d403980e8105bf804d4a1.png