2021-12-18 数据结构——线性表(上) (c++代码和c代码)_线性表的实现代码 c++

线性表是最基本、最简单、也是最常用的一种数据结构。==线性表（linear list)==是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。

1.基本概念

线性表：零个或多个数据元素的有限序列。
线性表：包括顺序表和链表
顺序表（数组）：里面元素的地址是连续的，
链表：链表里面节点的地址不是连续的，是通过指针连起来的。
表中元素个数称为线性表的长度
线性表没有元素时，称为空表
表起始位置称为表头，表结束位置称表尾

2. 线性表的抽象数据类型

类型名称：线性表（List）
操作集：线性表 L ∈ List，整数 i 表示位置，元素 X ∈ ElementType
线性表基本操作主要有：
c格式

线性表基本操作主要有：
List MakeEmpty()： 初始化一个空线性表 L
ElementType FindKth(int K,List L)：根据位序 K，返回相应元素
int Find(ElementType X,List L)：在线性表 L 中查找 X 的第一次出现位置
void Insert(ElementType X,int i,List L)：在位序 i 前插入一个新元素 X
void Delete(int i,List L)：删除指定位序 i 的元素
int Length(List L)：返回线性表 L 的长度 n
1
2
3
4
5
6
7

c++格式
ADT 线性表(List)
Data
线性表的数据对象集合为{a1,a2,…,an},每个元素的类型均为DataType。其中，除了第一个元素a1外，每一个元素有且只有一个直接前驱元素，除最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

    InitList(*L):初始化操作，建立一个空的线性表。
    ListEmpty(L):若线性表为空，返回true，否则返回false。
    ClearList(*L):线性表清空。
    GetElem(L,i,*e):将线性表L中第i个位置元素返回给e。
    LocateElem(L,e):在线性表L中查找与给定值e相等的元素，如果查找成功,返回该元素在表中的序列号；否则，返回0表示失败。
    ListInsert(*L,i,e):在线性表的第i个位置插入元素e。
    ListDelete(*L,i,*e):删除线性表L中的第i个元素，并用e返回其值
    ListLength(L):返回线性表L的元素个数。
    PrintList(L):打印线性表
1
2
3
4
5
6
7
8
9

3. 线性表的顺序存储

注意：

3.1 顺序存储的定义

顺序表就是用数组实现，事实上就是在内存中找个初始地址，然后通过占位的形式，把一定连续的内存空间给占了，然后把相同数据类型的数据元素依次放在这块空地中。
顺序存储的大小有两种方式：一是静态分配，二是动态扩展

3.2 实现方式

c++模板代码：

const int MaxSize = 100;
template <class DataType>  //主要用于c＋＋的重用性方面：template是模板的定义名称，<>号中class不是类的定义，而是相当于变量名前的类型名一样
class SeqList
{
public:
    SeqList(){length=0;}            //无参数构造方法
    SeqList(DataType a[],int n);    //有参数构造方法
    ~SeqList(){}                    //析构函数
    int Length(){return length;}    //线性表长度
    DataType Get(int i);            //按位查找
    int Locate(DataType x);         //按值查找
    void Insert(int i,DataType x);  //插入
    DataType Delete(int i);         //删除
    void PrintList();               //遍历
private:
    DataType data[MaxSize];         //顺序表使用数组实现
    int length;                     //存储顺序表的长度
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

c语言模板代码：

#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 100  // MAXSIZE 定义为 Data 数组的大小
typedef int ElementType;  // ElementType 可定义为任意类型
typedef struct LNode *List; 
struct LNode{
   ElementType Data[MAXSIZE]; 
   int Last;  // Last 定义线性表的最后一个元素
};
List L;
//访问下标为 i 的元素：L->Data[i]
//线性表的长度：L->Last+1

List MakeEmpty(); //初始化顺序表 
int Find(ElementType X,List L); //查找 X 第一次出现的下标 
void Insert(ElementType X,int i,List L); //在下标为 i 的地方插入 X 
void Delete(int i,List L);   //删除下标为 i 的当前值 
ElementType FindKth(int K,List L);  //返回下标为 K 的当前值
int Length(List L);  //返回顺序表的长度

//表长
int Length(List L){
	return L->Last+1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

顺序表的封装需要三个属性：
1.存储空间的起始位置。数组data的存储位置就是线性表存储空间的存储位置
2.线性表的最大存储容量。数组长度MAXSIZE
3.线性表的当前长度。length

MAXSIZE和length二者区别：数组的长度与线性表的长度是不一样的。数组的长度是存放线性表的存储空间的总长度，一般初始化后不变。而线性表的当前长度是线性表中元素的个数，是会改变的。

下面我们将实现顺序表的各个功能：

3.2.1 初始化

创建一个长度为n的顺序表，需要将给定的数组元素作为线性表的数据元素传入顺序表中，并将传入的元素个数作为顺序表的长度。
  
c++

template <class DataType>
SeqList<DataType>::SeqList(DataType a[],int n)
{
    if(n>MaxSize) throw "wrong parameter";
    for(int i=0;i<n;i++)
        data[i]=a[i];
    length=n;
}
1
2
3
4
5
6
7
8

c语言

struct LNode{
   ElementType Data[MAXSIZE]; 
   int Last;  // Last 定义线性表的最后一个元素
};
//初始化 
List MakeEmpty(){
    List L;
    L = (List)malloc(sizeof(struct LNode));
    L->Last = -1;
    return L;
}
//访问下标为 i 的元素：L->Data[i]
//线性表的长度：L->Last+1
1
2
3
4
5
6
7
8
9
10
11
12
13

3.2.2 按位查找

按位查找的时间复杂度为O(1) 。

template <class DataType>
DataType SeqList<DataType>::Get(int i)
{
    if(i<1 && i>length) throw "wrong Location";
    else return data[i-1];
}
1
2
3
4
5
6

// 按序查找
ElementType FindKth(int K,List L){
	if(K < 0 || L->Last < K){  //位置越界
        printf("L->Data[%d]不存在元素",K);
        return;
    }
    return L->Data[K];
}
1
2
3
4
5
6
7
8

3.2.2 按值查找

按值查找，需要对顺序表中的元素依次进行比较，时间复杂度为O(n) 。

template <class DataType>
int SeqList<DataType>::Locate(DataType x)
{
    for(int i=0;i<length;i++)
        if(data[i]==x) return i+1;
    return 0;
}
1
2
3
4
5
6
7

// 按值查找 
int Find(ElementType X,List L){
    int i=0;
    while(i <= L->Last && L->Data[i] != X)  
        i++;
    if(L->Last < i)  //如果没找到，返回 -1
        return -1; 
    else    // 找到后返回下标 
        return i;
}
1
2
3
4
5
6
7
8
9
10

3.2.3 插入

插入的过程中需要注意元素移动的方向，==必须从最后一个元素开始移动，如果表满了，则引发上溢；==如果插入位置不合理，则引发位置异常
  

template <class DataType>
void SeqList<DataType>::Insert(int i,DataType x)  //i不是下标，是第几个元素
{
    if(length>=MaxSize) throw "Overflow";
    if(i<1 || i>length+1) throw "Location";  //排除两边插入
    for(int j=length;j>=i;j--)
        data[j]=data[j-1];
    data[i-1]=x;
    length++;
}
1
2
3
4
5
6
7
8
9
10

// 插入
void Insert(ElementType X,int i,List L){
    int j;
    if(L->Last == MAXSIZE-1){  //位置已满 
        printf("表满");
        return;
    }
    if(i < 0 || L->Last+1 < i){  //位置越界，如果将数插入 L->Data[L->Last+1]，下面都不用腾位置了 ，排除两边插入
        printf("位置不合法");
        return;
    }
    for(j=L->Last;j>=i;j--)   // 从后往前依次向后挪一个，给 a[i]腾出位置     
        L->Data[j+1] = L->Data[j];   
    L->Data[i] = X;    //新元素插入
    L->Last++;    // Last仍然指向最后元素
    return;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3.2.4 删除

注意算法中元素移动方向，移动元素之前必须取出被删的元素，如果表为空则发生下溢，如果删除位置不合理，则引发删除位置异常。

template <class DataType>
DataType SeqList<DataType>::Delete(int i)  //i是第几个元素
{
    int x;
    if(length==0) throw "Underflow";  //一个元素也没有
    if(i<1 || i>length) throw "Location"; //越界了
    x = data[i-1];
    for(int j=i;j<length;j++)
        data[j-1] = data[j];
    length--;
    return x;
}
1
2
3
4
5
6
7
8
9
10
11
12

//删除
void Delete(int i,List L){
    int j;
    if(i < 0 || L->Last <i){  //位置越界，而删除最多到 L->Data[L->Last]
        printf("L->Data[%d]不存在元素",i);
        return;
    }
    for(j=i;j<=L->Last;j++)   // 从前往后依次向前挪一个，将 a[i] 覆盖了 
        L->Data[j-1] = L->Data[j];
    L->Last--;  // Last仍然指向最后元素
    return;
}
1
2
3
4
5
6
7
8
9
10
11
12

3.2.5 遍历

按下标依次输出各元素

template <class DataType>
void SeqList<DataType>::PrintList()
{
    for(int i=0;i<length;i++)
        cout<<data[i]<<endl;
}
1
2
3
4
5
6

for(i=0;i<Length(L);i++)
		printf("%d ",L->Data[i]);
1
2

3.2.6 实战

int main()
{
    SeqList<int> p;
    p.Insert(1,5);
    p.Insert(2,9);
    p.PrintList();
    p.Insert(2,3);
    cout<<p.Length()<<endl;
    p.PrintList();
    cout<<p.Get(3)<<endl;
    p.Delete(2);
    p.PrintList();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

int main(){
	int i=0;
	L = MakeEmpty();
	Insert(11,0,L);
	printf("在线性表L-Data[0]插入11\n");
	Insert(25,0,L);
	printf("在线性表L-Data[0]插入25\n");
	Insert(33,0,L);
	printf("在线性表L-Data[0]插入33\n");
	Insert(77,0,L);
	printf("在线性表L-Data[0]插入77\n");
	printf("此时的线性表为："); 
	for(i=0;i<Length(L);i++)
		printf("%d ",L->Data[i]);
	printf("\n");
	printf("查找值为12的下标是：%d\n",Find(12,L));
	printf("下标为3的线性表的值是：%d\n",FindKth(3,L));
	Delete(2,L);
	printf("删除线性表中下标为2的元素\n");
	Delete(2,L);
	printf("删除线性表中下标为2的元素\n");
	printf("此时的线性表为："); 
	for(i=0;i<Length(L);i++)
		printf("%d ",L->Data[i]);
	printf("\n"); 
	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

4.顺序存储的优缺点

优点：
随机访问特性，查找O(1)时间，存储密度高；
逻辑上相邻的元素，物理上也相邻；
无须为表中元素之间的逻辑关系而增加额外的存储空间；
缺点：
插入和删除需移动大量元素；
当线性表长度变化较大时，难以确定存储空间的容量；
造成存储空间的“碎片”