数据结构-3.线性表

2023-12-14 09:22:41

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总结回顾

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

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

在这里插入图片描述

文章来源:https://blog.csdn.net/weixin_51297735/article/details/132740748
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。