数据结构-3.线性表

3 线性表

3.0前记

typedef //重命名
typedef int elemtype;

#define //宏定义
#define maxsize 20

elemtype //抽象数据类型，理解为int即可

3.1什么是线性表？

“线”：有顺序的，串连起来的。

线性表 (List ):零个或多个数据元素的有限序列。

典型地分为两类：数组与指针，即顺序表与链表

前驱：该元素前面的那个元素。

后继：该元素后面的那个元素。

例如，a1没有前驱，a1的后继是a[2]，ai的前驱是a[i-1],后继是a[i+1]

线性表元素的个数n(n>0)定义为线性表的长度，当n=0时，称为空表。

注意区分数组长度与线性表的长度

线性表分类：顺序表和链表

3.2线性表的顺序存储结构及相关操作

顺序存储：一维数组。

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

而对于任何表或者说对于任何数据结构而言，你需要掌握的无非就是：增删改查，而前提就是定义、初始化、异常情况的判断。

3.2.1定义顺序表

#define maxsize 20 //数组最大长度为20
#define true 1
#define false 0

typedef struct 
{
    int data[maxsize];//定义数组最大长度
    int length;		  //定义顺序表长度
}List;

3.2.2初始化顺序表

void InitList(List *A)//初始化操作
{
    printf("输入线性表的长度\n");
    scanf("%d",&A->length);

    for(int i = 0;i<A->length;i++)
    {
        printf("输入第%d个值：",i+1);
        scanf("%d",&A->data[i]);
    }
    
}

3.2.3判断顺序表是否为空

int ListEmpty(List *A)//判断是否为空
{
    if(A->length==0)
    {
        return false;
    }
    else
        return true;
}

3.2.4清空顺序表

void ClearList(List *A)//将顺序表清空
{
    A->length = 0;
}

3.2.5返回元素

int GetElem(List *A,int i,int *e)//将线性表中第i个元素返回给e
{
    if(i<1||i>A->length)
    {
        printf("获取位置不合法\n");
        return 0;
    }
    return e = A->data[i-1];
}

3.2.6查找元素

int LocateElem(List *A,int e)//查找顺序表中与e相同的元素
{
    
        for(int i = 0;i<A->length;i++)
        {
            if(A->data[i] == e)
            {
                printf("找到了");
                return true;
            }
        }
        printf("没找到");
        return false;
}

3.2.7插入元素

void ListInsert(List *A,int i,int e)//在第i个位置插入e
{
    if(i<1||i>A->length + 1)//位置不合法
    {
        printf("位置不合法");
        return;
    }
    for(int j = A->length;j>=i;j--)//从后往前
    {
        A->data[j] = A->data[j-1];
    }
    A->data[i-1] = e;
    A->length++;
}

3.2.8删除元素

int ListDelete(List *A,int i,int *e)//删除第i个元素，并返回给e
{
    if(i<1||i>A->length+1)//位置不合法
    {
        printf("位置不合法");
        return;
    }
    e = A->data[i-1];
    for(int j = i-1;j<A->length-1;j++)
    {
        A->data[j] = A->data[j+1];
    }
    A->length--;
}

3.2.9返回元素个数

int ListLength(List *A)//返回线性表中元素的个数
{
    return A->length;
}

3.2.10打印输出

void PrintList(List *A)//打印输出顺序表
{
    for(int i = 0;i<A->length;i++)
    {
        printf("%d ",A->data[i]);
    }
}

3.2.11插入和删除的时间复杂度

分类讨论：最好情况和最坏情况

最好情况：只插入和删除一次，即头部或尾部，此时为O(1)

最坏情况：插入到第一个位置或删除第一个元素。此时所有的元素都要动，时间复杂度为O(n)

最终其时间复杂度为O(n)。而对于读取数据，查找数据，时间复杂度都为O(1)

3.2.12测试样例

注意函数中的==&==

int main()
{
    List A;
    InitList(&A);//初始化


    int e;
    ListDelete(&A,2,&e);//删除第二个元素

    ListInsert(&A,2,2);//在第二个位置插入e

    PrintList(&A);
    return 0;
}

3.3顺序表的 优缺点

3.4线性表的链式存储结构

顾名思义，什么叫链式存储结构：指针，我们简称为链表。通过指针将物理地址链接起来，逻辑上连续，但物理上不连续。

所以链表有两部分，一个用来存数，一个用来存地址，我们称为数据域与指针域。

我们把链表第一个结点的存储位置叫做头指针。

为了方便操作，我们会在第一个结点前设一个结点，称为头结点，不存储任何信息。当然，你也可以不设置头结点。

因此，对于一个链表，简化形式如下：

若带有头结点，则为：

那么怎么看链表是否为空呢？

头结点指向的是否为空，即L->next ==NULL;

3.5单链表的相关操作

什么是单链表：只有一个指针的线性表叫做单链表（数据与数据之间只通过一个指针进行连接起来）

3.5.1定义单链表

typedef struct 
{
    int data;
    struct LNode *next;//递归的思想
}LNode,*LinkList;

对于next和data，分别对应单链表中的什么结构呢

3.5.1初始化单链表

//malloc的作用是开辟内存空间，具体用法如下：
指针自身 = (指针类型*)malloc(sizeof(指针类型)*数据数量)

//初始化
void InitList(LinkList *L)
{
    LinkList p,r;//p和r均为LNode类型的指针，注意仅仅是指针。p用来存储数据地址,r用来存储指针域
    *L = (LinkList)malloc(sizeof(LNode));//利用malloc开辟内存空间。
    r = *L;//头指针

    int n;
    printf("请输入元素个数：");
    scanf("%d",&n);
    int arr[n];
    for(int i = 0;i<n;i++)
    {
        printf("请输入第%d个元素",i+1);
        scanf("%d",&arr[i]);
        p = (LinkList)malloc(sizeof(LNode));//开辟内存空间	
		p ->data = arr[i];//赋值
		r ->next = p;	  //指针指向该节点
		r = p;			  //移动到当前位置
    }
    r->next = NULL;//最后指针指向空，表示单链表结束
}

r->next = p;

r = p;

3.5.2 判断单链表是否为空

//判断是否为空表
int IsEmpty(LinkList *L)
{
    LinkList temp = L;
    if(temp->next == NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
}

3.5.3清空单链表

void clearList(LinkList *L)
{
    LinkList temp = L;
    while(temp->next)
    {
        temp = temp->next;
        free(L);
        *L = temp;
    }
    temp->next = NULL;
}

3.5.4查找元素

//查找第i个元素的值
void FindList(LinkList *L,int i)
{
    LinkList temp = L;
    temp = temp->next;//首先指向第一个结点，否则会“错位”
    int j = 1;
    while(j<i)
    {
        temp = temp->next;
        j++;
    }
    printf("第%d个元素的值为%d\n",i,temp->data);
}

3.5.5插入元素（重点）

//插入元素
void InsertList(LinkList *L,int i,int e)
{
    LinkList temp = L;
    int j = 1;
    while(j<i)//找到第i个的位置
    {
        temp = temp->next;
        j++;
    }
    LinkList p = (LinkList)malloc(sizeof(LNode));//申请内存空间
    //三者的顺序不能换
    p->data = e;
    p->next = temp->next;
    temp->next = p;
}

3.5.6删除元素

//删除元素
void DeleteList(LinkList *L,int i)
{
    LinkList temp = L;
    int j = 1;
    while(j<i)//找到位置
    {
        temp = temp->next;
        j++;
    }
    LinkList p = temp->next;
    temp->next = p->next;//不可以是p->next->next
    free(p);
}

3.5.7输出单链表

//输出元素
void Print(LinkList *L)
{
    LinkList temp = L;
	//temp = L;
	printf("表中的元素为:\n");
	while(temp->next)//当指针域不为空时，一直继续下去
	{
		temp = temp->next;
		printf("%d ",temp->data);
    }
    printf("\n");
}

3.5.6测试样例

注意函数中的==&==

int main()
{
    LNode *A;
    InitList(&A);
    Print(A);

    DeleteList(A,2);//删除第二个位置的元素
    Print(A);

    InsertList(A,2,3);//在第二个位置插入3
    Print(A);

    FindList(A,2);//查找第二个位置的元素值
    Print(A);
    return 0;
}

3.6单链表与顺序表的优缺点

• 若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。
• 当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样可以不需要考虑存储空间的大小问题。而如果事先知道线性表的大致长度，用顺序存储结构效率会高很多。

3.7静态链表

? 我们都知道，链表与顺序表唯一的不同就在于：使用了指针，使得逻辑上连续但物理上不是连续的。而对于高级语言，如Java，或者C++而言，是没有指针这么一说的，有的只是**“引用”**，特别是c++，因为指针可能太绕了。

? 而对于古老的语言，如basic等，也没有指针这个功能，所以，如何在没有指针的情况下，依旧能使用链表呢？静态链表。

用数组描述的链表叫做静态链表。

3.8静态链表的组成与结构

两部分：数据域和游标，数据域是用来存储数据data的，游标cur就相当于一个指针，指向下一个数据域的数组下标。

数组的第一个位置，也就是arr[0]不存放数据，只存放游标，且这个游标指向的是下一个能存放数据的数组下标。

由于第一个位置不存放数据，所以存放的数据就与数组下标相对应了，即，第一个元素就存放在第一个位置arr[1]，第二个就存放在arr[2]。不需要去像过去的减一

静态链表为空：arr[0].cur = 0;

静态链表的最后一个位置的游标指向0：arr[maxsize -1].cur = 0;

关键就是理解清楚游标是时刻指向下一个数据的数组下标的。

3.9静态链表的相关操作

3.9.1定义静态链表

#define maxsize 20
typedef struct
{
    int data;
    int cur;
}Component;

本质：结构体类型的数组

3.9.2初始化静态链表

静态链表为什么要初始化呢，因为需要使得游标将数据域连起来

void InitArr(Component *A)
{
    for(int i = 0;i<maxsize;i++)
    {
        A[i].data = 0;//数据域全为0
        A[i].cur = i+1;//游标指向下一个数组的下标
    }
    A[maxsize-1].cur = 0;//最后一个元素的下标指向0，也就是第一个（头结点）
}

3.9.2静态链表的赋值

void AddArr(Component *A)
{
    int n;
    printf("请输入你想添加的数据成员的数量：");
    scanf("%d",&n);

    for(int i = 0;i<n;i++)
    {
        printf("请输入第%d个元素:",i+1);
        scanf("%d",&A[i+1].data);//从第一个开始赋值
    }
    A[n].cur = 0; //最后一个为0
    A[0].cur = n+1;//最后一个结点的游标为0
    A[maxsize-1].cur=1;//末尾结点的游标为1，连起来
}

3.9.3插入元素

//在第i个位置插入e
void InsertArr(Component *A,int i,int e)
{

    if(A[i].data==0)//优先插入
    {
        A[i].data = e;
        return ;
    }
    int temp = A[0].cur;//保存下一个能够插入数据的数组下标
    A[i].cur = temp;//指向插入元素的下标
    A[temp].data = e;//插入位置的数据 = 插入数据
    A[temp].cur = i+1;//指向下一个数组下标
    A[0].cur++;
}

插入元素，记住一点即可，不要因为他是数组就觉得需要移动一堆元素去实现插入。

静态链表是一个链表，所以，无论是如何插，都是尾插，只需要改变相应的数组下标即可。

3.9.4删除元素

//删除元素
void DeleteArr(Component *A,int i)
{
    //注意前后下标的变化
    int temp = A[i].cur;
    A[i].data = 0;
    A[i+1].cur = A[i-1].cur;
    A[i-1].cur = temp;
}

3.9.5输出链表

//输出链表
void Print(Component *A)
{
    for(int i = 0;i<A[0].cur-1;i++)
    {
        printf("%d ",A[i+1].data);
    }
}

3.9.6测试样例

int main(int argc, char const *argv[])
{
    Component A[maxsize];
    InitArr(A);//初始化
    AddArr(A);//赋值

    DeleteArr(A,3);//删除第三个位置的元素
    InsertArr(A,3,7);//在第三个位置上插入7
    
    Print(A);
    return 0;
}

3.10静态链表的优缺点

3.11循环链表

什么是循环链表？

? 首先看单链表，所谓的单链表就是一个指针从头到尾串下来，而循环链表就是使这个链表“循环”了。形成了一个环

? 在单链表中，我们有了头结点时，我们可以用O(1)的时间访问第一个结点，但对于要访问到最后一个结点，却需要O(n)时间，因为我们需要将单链表全部扫描-一遍。加入尾指针之后，O(1)即可访问到终端节点

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表( circuar linkedlist)。

对于空的循环链表：

尾指针：rearA

rearA->next 指向的是头结点

合并两个循环链表

①p = rearA->next; //保存A的头结点

②rearA->next = rearB->next->next;//将B的第一个节点，注意不是头结点，赋值给A的next，链接起来

③rearB->next = p;//B尾指针的next指向A的头结点，实现一个循环

3.12双向链表

? 我们在单链表中，有了next 指针，这就使得我们要查找下一结点的时间复杂度为O(1)。可是如果我们要查找的是上-一结点的话，那最坏的时间复杂度就是0(n)了，因为我们每次都要从头开始遍历查找。

? 为了克服单向性这一缺点，我们的老科学家们，设计出了双向链表。**双向链表(double linked list)是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。**所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

对于空的双向链表

对于某一结点P，他的后继的前驱就是他自己。

p->next->prior = p = p->prior->next;

定义双向链表

typedef struct Node{
    struct Node *pre;//前驱结点
    int data;//数据域
    struct Node *next;//后继结点
}Node;

关于双向链表的插入与删除

对于插入：

设插入的元素值为e，结点为s，则

①s->prior = p;//s的前驱指向p

②s->next = p->next;//s的后继指向p的后继结点

③p->next->prior = s;//p的原来的后继结点的前驱指向s

④p->next = s;//p的后继指向s

关键在于它们的顺序，由于第⒉步和第3步都用到了p->next。 如果第4步先执行，则会使得p->next提前变成了s，使得插入的工作完不成。

①先搞定s的前驱和后继

②再搞定后结点的前驱，

③最后解决前结点的后继。

void Insert(DNode *p, int i,int data)
{
	DNode *p1 = p;
	int j = 1;
	while (j < i)
	{
		p1 = p1->next;
	}
	DNode *p2 = (DNode *)malloc(sizeof(DNode));
	p2->data = data;
	p2->priv = p1;
	p2->next = p1->next;
	p1->next = p2;
}

对于删除：

①p->prior->next = p->next;//把前结点的后继指向p的后继

②p->next->prior = p->prior；//把后结点的前驱指向p的前驱

void Delete(DNode *p,int i)
{
	DNode *p1 = p;
	int j = 1;
	while (j < i)
	{
		p1 = p1->next;
	}
	p1->priv->next = p1->next;
	p1->next->priv = p1->priv;
	free(p1);
}

以空间换取时间

3.13总结回顾

? 先谈了它的定义，线性表是零个或多个具有相同类型的数据元素的有限序列。然后谈了线性表的抽象数据类型，如它的一些基本操作。
? 之后我们就线性表的两大结构做了讲述，先讲的是比较容易的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。通常我们都是用数组来实现这一结构。
? 后来是我们的重点，由顺序存储结构的插入和删除操作不方便，引出了链式存储结构。它具有不受固定的存储空间限制，可以比较快捷的插入和删除操作的特点。

? 然后我们分别就链式存储结构的不同形式，如单链表、循环链表和双向链表做了讲解，另外我们还讲了若不使用指针如何处理链表结构的静态链表方法。
总的来说，线性表的这两种结构其实是后面其他数据结构的基础，把它们学明白了，对后面的学习有着至关重要的作用。