考研数据结构基础——尽量全,用于预习与复习参考

发布于:2025-02-10 ⋅ 阅读:(35) ⋅ 点赞:(0)

第二章线性表

1.1线性表的定义和基本操作

定义:线性表时具有\textcolor{blue}{相同数据类型}的n(n≥0)个数据元素的\textcolor{blue}{有限序列},其中n为表长,当n=0时线性表是一个空表。若用L命名线性表,则其一般表示为:L=(a_1,a_2,...,a_i,a_{i+1},...,a_n).

涉及概念

1.a_i是线性表的“第i个”元素线性表中的位序。(位序是从一开始,但是数组是从0开始的)

2.a_1是表头元素,a_n是表尾元素。

3.除第一个元素外,每个元素有且仅有一个直接前驱;除最后一个元素外,每个元素有且仅有一个直接后继。

线性表的基本操作:

当需要将参数修改结构带回来时。加上“&”。

InitList(&L):初始化表。构造一个新的空线性表L,分配内存空间。

DestroyList(&L):销毁操作。

ListInsert(&L,i,e):插入操作。在第i个位置插入元素e。

ListDetele(&L,i,&e):删除操作。在第i个位置删除元素e。

LocateElem(L,e):按值查找元素。

GetElem(L,i):按位查找元素。

其他操作:

Length(L):求表长。返回线性表长度。

PrintList(L):输出操作。

Empty(L):判空操作。如果L为空表,返回true。

注:为什么要使用这些封装函数?

1.定义的数据结构方便别人使用;2.避免重复工作,降低出错风险。

1.2线性表的顺序存储

顺序表定义:用顺序存储的方式实现线性表的顺序存储。

顺序表操作的实现:

顺序表的实现——静态分配

//静态的大小一旦生成就不可变了

#define MaxSize = 10
typedef struct{
    int data[MaxSize];  //用静态的数组存放数据元素  
    int length;         //顺序表当前的长度
}SqList;                //顺序表的类型定义

初始化函数

void InitList(SqList &L){
    for(int i=0;i<MaxSize;i++)
        L.data[i]=0;
    L.length=0;
}

插入函数

bool ListInsert(SqList &L,int i,int e){
    if(i<1||i>L.length+1)       return false;
    if(L.length>=MaxSize)       return false;
    for(int j=L.length;j>=i;J--)    //第i个元素及之后的元素后移
        L.data[j]=L.data[j-1];
    L.data[i]=e;            //给第i个赋值
    L.length++;             //长度+1
    return true;
}

        这个函数的的最好情况是0,最坏情况是n,因此平均时间复杂度为。

删除函数

bool ListDelete(SqList &L,int i,int &e){    //这里的e是用来存储删除的那个元素的值的
    if(i<1||i>L.length)     return false;
    e=L.data[i-1];          //位序跟数组不一样
    for(int j=i;j<L.length;j++)     //注意这里是<,不是≤.
        L.data[j-1]=L.data[j];
    L.length--;
    return true;
}

        这个函数的的最好情况是0,最坏情况是n-1,因此平均时间复杂度为。

按位序查找元素函数

int GetElem(SqList L,int i){
    return L.data[i-1];
}

按值查找元素函数

int Locate(SqList L,int e){
    for(int i=0;i<L.length-1;i++)
        if(L.data[i]==e)
            return i+1;
    return 0;
}
顺序表的实现——动态分配
#define InitSize = 10
typedef struct{
    ElemType *data;     //指示动态分配数组的指针
    int MaxSize;        //顺序表的最大容量
    int length;         //顺序表当前的长度
}SqList;                //顺序表的类型定

这里面就涉及了怎么申请空间,并让data指过去,在C/C++中动态申请和释放内存空间的函数

C   ——  malloc、free函数
        L.data = (ElemType *)malloc(sizeof(ElemType)*InitSize) //后面的*是乘号的意思
C++ ——  new、delete关键字

初始化函数

void InitList(SqList &L){
	L.data=(int *)malloc(InitSize*sizeof(int));
    L.length=0;
    L.MaxSize=InitSize;
}

//增加动态数组长度的函数
void IncreaseSize(SqList &L,int len){
    int* p=L.data;
    L.data=(int *)malloc((L.Maxsize+len))*sizeof(int));	//data指向新产生的空间
    for(int i=0;i<L.length;i++){
        L.data[i]=p[i];				//将数据复制到新区域
    }
    L.MaxSize=L.MaxSize+len;
    free(p);
}

顺序表的特点:

1.随机访问,可以在O(1)时间内找到第i个元素。

2.存储密度高,每个节点只存储数据元素。

3.拓展容量不方便(即便采用动态分配的方式实现,拓展长度的时间复杂度也比较高)

4.插入、删除操作不方便,需要移动大量的数据

本章节有个关于结构类型的知识点:

即在C语言中两个结构类型的变量是不是直接用“==”来比较是否相等的,需要另外定义一个函数逐项比较结构体中每一个元素。在C++中可以定义一个重载来实现。

1.3线性表的链式存储

优点:不要求大片连续空间,改变容量方便;缺点:不能随机存取。

单链表的定义

typedef	struct LNode{
    ElemType data;			//每个节点存放一个数据元素
    struct LNode *next;  //指针域,指向下一个节点
}LNode,*LinkList;

//要表示一个链表时,只需要声明一个头指针L,指向单链表的第一个结点。
LNode * L;或LinkList L;  		//都是声明一个指向单链表第一个结点的指针
//

        需要说明的是:LNode * L强调的是这是一个结点,LinkList L强调的是这是一个单链表。

不带头结点的单链表

初始化函数

bool InitList(LinkList &L){
    L = NULL;		//空表,暂时还没有任何结点
    return true;
}

判断链表是否为空

bool Empty(LinkList L){
    return (L==NULL);
}

按位序插入函数: //根据这个可以知道,不带头结点的单链表,当i=1的时候需要重新设定一个头结点.

bool ListInsert(LinkList &L,int i,ElemType e){
    if(i<1)		return false;
    if(i==1){
        LNode *s = (LNode*)malloc(sizeof(LNode));
        s->data=e;
        s->next=L;
        L=s;		//头指针指向新结点
        return true;
    }
    LNode *p;
    int j=1;
    p = L;
    while(p!=NULL && j<i+1){
        p=p->next;
        j++;
    }
    if(p=NULL)	return false;
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;		//头指针指向新结点
    return true;
}
带头结点的单链表: //更方便

尾插法建立单链表: //建立表尾结点

LinkList List_TailInsert(LinkList &L){
    int x;					
    L = (LinkList)malloc(sizeof(LNode));	//建立头结点
    LNode *s,*r = L;		//r为表尾指针
    scanf("%d",&x);			//输入插入结点的值
    while(x != '#'){
        s=(LNode*)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;				//r指向新的表尾结点
        scanf("%d",&x);
    }
    r-next = NULL;
    return L;
}

头插法建立单链表: //

LinkList List_HeadInsert(LinkList &L){
	LNode *s;
	int x;
	L = (LinkList)malloc(sizeof(LNode));	//头指针
	L->next = NULL;				//初始化为空
	scanf("%d",&x);
	while(x!='#'){
		s = (LinkList)malloc(sizeof(LNode));
		s->data = x;
		s->next = L->next;
		L->next = s;
		scanf("%d",&x);
	}
	return L;
}

初始化函数

bool InitList(LinkList &L){
    L = (LNode *)malloc(sizeof(LNode));
    if(L == NULL)
        return false;
    L->next = NULL;
    return true;
}

判断链表是否为空

bool Empty(LinkList L){
    return (L->next==NULL);
}

按位序查找函数

LNode* GetElem(LinkList L,int i){
    if(i<0)		return NULL;
    LNode *p;
    int j=0;
    p = L;
    while(p!=NULL && j<i){
        p = p->next;
        j++;
    }
    return p;
}

按值查找函数

LNode* LocateElem(LinkList L,ElemType e){
    LNode *p = L->next;
    while(p!=NULL && p->data != e)
        p =	p->next;
    return p;
}

按位序插入函数

bool ListInsert(LinkList &L,int i,ElemType e){	//在第i个位置插入元素e
    if(i<1)		return false;
    LNode *p;	//指针p指向当前扫描到的结点
    int j = 0;
    p = L;
    while(p!=NULL && j < i-1){					//循环找到第i-1个结点
        p = p->next;
        j++;
    }
    if(p==NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));	//s结点为新加的代码
    s->data = e;
    s->next=p->next;
    p->next=s;
    return true;
}

后插操作: //在p结点后插入元素e

bool InsertNextNode(LNode *p,ElemType e){
    if(p == NULL)	return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if(s==NULL)		return false;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

前插操作

bool InsertPriorNode(LNode *p,ElemType e){
    if(p==NULL)		return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if(s==NULL)		return false;
    s->next = p->next;
    p->next = s;
    s->data = p->data;
    p->data = e;
    return true;
}

删除操作

//删除指定位置的结点
bool ListDelete(LinkList &L,int i,ElemType &e){
    if(i<1)		return false;
    LNode *p;
    int j = 0;
    p = L;
    while(p!=NULL && j < i-1){					//循环找到第i-1个结点
        p = p->next;
        j++;
    }
    if(p==NULL)
        return false; 
    if(p->next==NULL)	return false;
    LNode *q=p->next;
    e = q->data;
    p->next=q->next;
    free(q);
    return true;
}
//删除指定结点
bool DeleteNode(LNode *p){
    if(p == NULL)	return false;
    LNode *q=p->next;
    p->data = p->next->data;//这段代码是有问题的,没有考虑到p是最后一个结点的情况,但这是单链表的局限性。
    p->next = q->next;
    free(q);
    return true;
}

        删除指定结点的代码受限于单链表的局限是有问题,需要注意。

双链表

                //增加了前驱结点

typedef struct DNode{
    ElemType data;
    struct DNode* prior,*next;
}DNode , *DLinkList;

初始化双链表

bool InitDLinkList(DLinkList &L){
    L = (DNode *)malloc(sizeof(DNode));
    if(L==NULL)		return false;
    L->prior = NULL;
    L->next = NULL;
    return true;
}

双链表的插入(后插): //如何前插,只需要从该结点找到前驱结点,对前驱结点执行后插操作

bool InsertNextDNode(DNode *p,DNode *s){
    if(p == NULL||s == NULL)	return false;
    s->next = p->next;
    if(p->next != NULL)		p->next->prior = s;
    s->prior = p;
    p->next = s;
    return true;
}

双链表的删除

void DeleteNextDNode(DNode *p){
    if(p == NULL)	return false;
    DNode *q = p->next;
    if(q == NULL)	return false;
    p->next = q->next;
    if(q->next!=NULL)	q->next->prior = p;
    free(q);
    return true;
}LNode,*LinkList;

循环单链表

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}

初始化循环单链表

bool InitLinkList(LinkList &L){
    L = (LNode *)malloc(sizeof(LNode));
    if(L == NULL)	return false;
    L->next = L;		//在最后要指向头指针
    return true;
}

循环单链表是否为空

bool EmptyLinkList(LinkList L){
    return(L->next == L);
}

循环双链表

初始化循环双链表

bool InitLinkList(LinkList &L){
    L = (LNode *)malloc(sizeof(LNode));
    if(L == NULL)	return false;
    L->next = L;		//后继在最后要指向头指针
    L->prior = L;		//前驱在最后要指向头指针
    return true;
}

静态链表:

定义:分配一整片连续的内存空间,各个结点集中安置。

#define MaxSize 10
typedef struct{
    ElemType data;		//存储数据元素
    int next;			//下一个元素的数组下标
}SLikList[MaxSize];

在物理上相邻但是地址空间里面的数值不一定相邻,其容量是固定不可变的。

总结:

顺序表和链表比较:

1.逻辑结构:都是一对一的线性结构;

2.存储结构:顺序表是连续空间,存储密度高;链表空间分散,但是存储密度略低。

3.应用场景:顺序表适用于表长可估计、查询操作较多的场景;链表适用于表长难以估计、插入/删除频繁的场景。

4.基本操作:顺序表插入/删除需要移动元素,时间复杂度高,但是查找方便;链表反之。

# 声明

        以上内容时根据现有最新的课程学习总结而成,包含必要的代码,适合基础复习使用。


网站公告

今日签到

点亮在社区的每一天
去签到