数据结构学习2

标签：链表 结点 cur 元素 next 学习 数据结构 指针

5、线性表的链式存储结构

①定义 链式存储: 用一组任意的存储单元存储线性表中的数据元素。 线性链表：用这种方法存储的线性表简称线性链表。

特点:结点在存储器中的位置是随意的,即在逻辑上相邻的数 据元素在物理上不一定相邻。

实现:为了正确表示结点间的逻辑关系,在存储每个结点值的 同时，还必须存储指示其直接后继结点的地址(或位置)，称为 指针或链,这两部分组成了链表中的结点结构

数据域: 存放数据元素信息的域 指针域：存放直接后继的域

图形表示

②单链表 每一个结点只包含一个指针域的链表称为单链表

第一个结点:存储线性表中第一个数据元素ai的结点 头指针：指向链表中第一个结点 头结点:在链表的第一个结点前附设的一个结点:数据域内只放空表标志和表长等信息,不计入表长度。

示意图如下：

头指针与头节点的异同 头指针是指链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指 针 头指针具有标识作用,所以常用头指针冠以链表的名字 无论链表是否为空，头指针均要存在。头指针是链丧的必要元素

头结点是未来操作的统一和方便而设立的,放在第一元素的结点之前,其数据域 一般无意义（也可以放链表的长度) 有了头结点,对在第一元素结点前插入结点和删除第一结点,其操作域其它结点 的操作就统一了 头结点不一定是链表必须要素

单链表存储结构代码描述

typedef struct Node
{
    ElemType data;      // 数据域
    struct Node *next;  // 指针域
}Node;
typedef struct Node "LinkList;/*定义LinkList */

③单链表的读取

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

代码

/*操作结果：用e返回L中第i个数据元素的值*/
Status GetElem(LinkList L,int i.ElemType *e)
{
    int j;
    LinkList p;     /*声明一指针p*/
    p=L->next;      /*让p指向链表L的第一个结点*/
    j=1;            /*j为计数器*/
    while (p&&j<i) /*p不为空或者计数器还没有等于i时，循环继续*/
    {
        p->next;/* 让p指向下一个结点*/
        ++j;
    }   
    if (!p || j>i)
        return ERROR;/* 第i个元素不存在*/
    *e=p->data; /*取第i个元素的数据*/
    return OK;
}

③单链表的插入

/*操作结果:在L中第i个位置之前插入新的数据元素e, L的长度加1*/
Status Listinsert(LinkList *L,int i,ElemType e)
{
    int j;
    LinkList p,s;
    p= *L;
    j= 1;
    while (p &&j <i) /*寻找第i-1个结点*/
    {
        p=p->next;
        ++j;
    }
   if (!p||j>i)
        return ERROR;/*第i个元素不存在*/
    s = (LinkList)malloc(sizeof(Node));
    s->data =e;     /*生成新结点*/
    s->next=p->next;/*将p的后继结点赋值给s的后继*/
    p->next=s;      /*将s赋值给p的后继*/
    return OK;
}

④单链表的删除

代码

/*操作结果:删除L的第i个数据元素,并用e返回其值, L的长度减1*/
Status ListDelete(LinkList *L,int iElemType *e)
{   
    int j;
    LinkList p,q;
    p=*L;
    j =1;
    while (p->next &&j<i) /*遍历寻找第i-1个元素*/
    {
        p=p->next;
        ++j;
    }
    if (!(p->next) |j>i)
        return ERROR;   /*第i个元素不存在*/
    q=p->next;
    p->next=q->next;    /*将q的后继赋值给p的后继*/
    *e= q->data;        /*将q结点中的数据给e*/
    free(q):            /*让系统回收此结点，释放内存*/
    return OK;
}

⑤单链表的整表创建

思路 头插法： 1.建立一个空的带头结点的单链表 2.随机生成新的结点， 3.把每个新结点插入到头结点域前一新结点之间,就是始终让新结点在第一的位置 尾插法: 和头插法的区别在于;始终让新结点在链表最后的位置。

代码

/*随机产生n个元素的值,建立带表头结点的单链线性表L(头插法)*/
void CreateListHead(LinkList *L, int n)
{
    LinkList p;
    int i;
    srand(time(0));     /*初始化随机数种子*/
    *L= (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    for (i=0; i<n; i++) /*先建立一个带头结点的单链表*/
    {
        p=(LinkList)malloc(sizeof(Node));/* 生成新结点*/
        p->data=rand()%100+1;   /* 随机生成数字 */
        p->next = (*L)->next;
        (*L)->next = p;/*       插入到表头*/
    }
​
}
​
​
/*随机产生n个元素的值,建立带表头结点的单链线性表L(尾插法) */
void CreateListTail(LinkList *L, int n)
{
    LinkList p,r,int i;
    srand(time(0));     /* 初始化随机数种子*/
    *L= (LinkList)malloc(sizeof(Node)); /* L为整个线性表*/
    r=*L;       /*r为指向尾部的结点*/
    for (i=0; i<n; i++)
    {
        p= (Node *)malloc(sizeof(Node)); /*生成新结点*/
        p->data=rand()%100+1; /*随机生成数字*/
        r->next=p;  /*将表尾终端结点的指针指向新结点*/
        r=p;        /*将当前的新结点定义为表尾终端结点*/
    }
    r->next = NULL; /*表示当前链表结束*/
}

⑥单链表的整表删除

思路 1·从第一个结点(如果有头结点从头结点)开始,依次往后删除结点,并释放空间,直到最后一个元素。

代码

/*初始条件:顺序线性表L已存在,操作结果:将L重置为空表*/
Status ClearList(LinkList *L)
{
    LinkList p,q;
    p=(*L)->next;   /* p指向第一个结点*/
    while(p)        /* 没到表尾*/
    {
        q=p->next;
        free(p);
        p=q;
    }
    (*L)->next=NULL;/*头结点指针域为空*/
    return OK;
}

⑦单链表与顺序链表储存结构优缺点

 

6、静态链表的定义

①静态链表的定义 定义 静态链表:我们让数组的元素都是由两个数组域组成, data和cur。也就是说,数组的每个下标都对应一个data和一个cur。数据域data,用来存放数据元素,也就是我们通常要处理的数据,而cur相当于单链表中的next指针,存放该元素的后继在数组 中的下标,我们把cur叫做游标。这种把数组描述的链表叫做静态链表。 这种描述方法还有起名叫做游标实现法。

结构实现代码

#define MAXSIZE 1000 /*存储空间初始分配量*/
/*线性表的静态链表存储结构*/
typedef struct
{
    ElemType data;      // 数据
    int cur;            /*游标(Cursor) ,为0时表示无指向*/
}Component,StaticLinkList[MAXSIZE];

关键点 1·为了方便插入数据,我们通常会把数组建立得大一些,以便有一些空闲空间可以便于插入时不至于溢出。 2.把未使用的数组元素称为备用链表 3.数组第一个元素和最后一个元素做特殊处理,不存数据 4.数组第一个元素(下标为0的元素)的cur存放着备用链表的第一个结点的下标 5,数组最后一个元素的cur存放着第一个有数值元素的下标,相当于单链表中的头结点作用。

示意图

初始化 代码：

/*将一维数组space中各分量链成一个备用链表, space[0].cur为头指针,
"0"表示空指针*/
Status InitList(StaticLinkList space)
{
    int i;
    for (i=0; i<MAXSIZE-1; i++)
        space[i].cur =i+1;
​
    space[MAXSIZE-1].cur= 0;/*目前静态链表为空，最后一个元素的cur为0*/
    return OK;
}

②静态链表的插入

插入 代码：

/*在L中第i个元素之前插入新的数据元素e */
Status ListInsert(StaticLinkList L, int i, ElemType e)
{
    int j, k, l;
    k= MAXSIZE-1; /*注意k首先是最后一个元素的下标*/
    if (i<1||i> ListLength(L) + 1)
        return ERROR;
    j=Malloc_SSL(L); /*获得空闲分量的下标*/
​
    if (j)
    {
        L[i].data =e; /*将数据赋值给此分量的data*/
        for(l=1;1<=i-1;I++) /*找到第i个元素之前的位置*/
            k=L[k].cur;
        L[j].cur= L[k].cur; /*把第i个元素之前的cur赋值给新元素的cur*/
        L[k].cur =j;/*把新元素的下标赋值给第i个元素之前元素的ur*/
        return OK;
    }
    return ERROR;
}

③静态链表的删除

代码：

/*删除在L中第i个数据元素*/
Status ListDelete(StaticLinkList L, int i)
{
    int j, k;
    if (i <1 ||i> ListLength(L))
        return ERROR;
    k = MAXSIZE - 1;
    for (j = 1;j <=i-1;j++)
        k= L[k].cur;
    j= L[k].cur;
    L[k].cur= L].cur;
    Free_SSL(L, j);
    return OK;
}
​
/*将下标为k的空闲结点回收到备用链表*/
void Free_SSL(StaticLinkList space, int k)
{
    space[k].cur = space[0].cur;    /*把第一个元素的cur值赋给要删除的分量cur*/
    space[0].cur =k;/*把要删除的分量下标赋值给第一个元素的cur*/
}

④静态链表的优缺点

7、循环链表

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

②特点 从表中任一结点出发均可找到表中其他结点,提高查找效率。为了是空表和非空表的处理一致，循环链表中也可以设置一个头结点。

操作与单链表基本一致,循环条件不同 循环链表判断循环结束的条件是p->next等于头结点 单链表: p->nextnull 循环链表: p->nexthead

尾指针 在循环链表中,除了头指针head外,有时还加了一个尾指针rear,尾指针 rear指向最后一结点,从最后一个结点的指针又可立即找到链表的第一个 结点。在实际应用中,使用尾指针代替头指针来进行某些操作,往往更简 单。 例:将两个循环链表首尾相接。rearA为第一个循环链表表尾指针, rearB 为第二个循环链表表尾指针。合并后rearB为新链表的尾指针。

void merge(slnodetype *rearA,sInodetype * rearB)
{
    slnodetype *p;
    p= rearB->next;
    rearB->next= rearA->next;
    rearA->next=p->next;
    free(p);
}

③循环链表的插入与删除

注意：最后一个元素的后继指针

④双向链表

定义 双向链表是在单链表的每个结点中,在设置一个指向其前驱结点的指针域 特点 构成链表的每个结点中有两个指针域：一个指向其直接前驱，一个指向直接后继。

结点结构定义

typedef struct DulNode
{   
    ElemType data;              // 数据域
    struct DuLNode* prior;      // 直接前驱
    struct DuLNode* next;       // 直接后继
}

插入操作 1.s->prior = p; 2.s->next = p->next; 3.p->next->prior =s; 4.p->next = s;

删除操作 1.p->prior->next = p->next; 2.p->next->prior=p-> prior; 3.free(p);

应用 Windows和Linux操作系统大量应用双向链表 比如： 应用层PEB

Windows内核也大量采用这种链表: EProcess EThread 驱动对象 设备对象 等待对象

8、栈的顺序存储结构

①栈的定义

定义 限定仅在表尾进行插入和删除操作的线性表

特点 后进先出(Last In First Out)，简称LIFO

一些概念 栈顶(top)： 栈底(bottom) 进栈(push)： 出栈(pop)： 空栈:

②栈的抽象数据类型

ADT 栈(stack) Data 同线性表 Operation InitStack(S);//初始化操作,建立一个空栈S DestroyStack();//若栈存在,则销毁它。 ClearStack(S);//将栈清空 StackEmpty(S);//若栈为空，返回true,否则返回false GetTop(S,e);//若栈存在且非空,用e返回S的栈顶元素 Push(S,e);//若栈存在，插入新元素e到栈S中并成为栈顶元素 Pop(S,*e);//删除栈S中栈顶元素,并用e返回其值 StackLength(S);//返回栈S的元素个数 endADT

③栈的顺序存储结构及实现

定义 栈的顺序存储结构简称顺序栈,和线性表类似,用一维数组来存储栈

栈不存在的条件: bottom=NULL 只有一个元素的栈： bottom = top 栈为空的条件： bottom=top 栈满的条件: top-base= StackSize

栈结构代码定义

#define MAXSIZE 20 /*存储空间初始分配量*/
​
/* 顺序栈结构*/
typedef struct
{
    SElemType data[MAXSIZE];    // MAXSIZE-1即为StackSize
    int top; /*用于栈顶指针(简化版,用数组下标代替)*/
}SqStack;

进栈操作 代码：

/*插入元素e为新的栈顶元素*/
Status Push(SqStack *S,SElemType e)
{
    if(S->top == MAXSIZE-1) /* 栈满*/
    {
        return ERROR;   
    }
    S->top++;           /* 栈顶指针增加一*/
    S->data[S->top]=e; /*将新插入元素赋值给栈顶空间*/
    return OK;
}

出栈操作 代码：

/*若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回
ERROR*/
Status Pop(SqStack *S,SElemType *e)
{
    if(S->top==-1)
        return ERROR;
    *e=S->data[S->top]; /*将要删除的栈顶元素赋值给e*/
    S->top--;       /*栈顶指针减一*/
    return OK;
}

④两栈共享内存

为什么要共享空间 顺序栈由于只能从栈顶进出,所以不存在栈顶插入和删除要移动大量数据的问题 不过,数据如果存满了,需要扩展数组的容量就比较麻烦了。如果有两个栈，他们存储是数据类型一样，一个栈存满了,另外一个栈还有很多空闲的空间,这时就可以使两个栈共享空间。

怎么共享空间 1·用1个数组表示两个栈,栈1和栈2 2.数组始端是栈1的栈底(bottom1),数组末端是栈2的栈底(bottom2) 3.top1和top2表示栈1和栈2的栈顶指针 4.top1+1=top2表示两个栈都满，不能继续插入数据 5·否则栈没有满,可以继续插入数据

应用场景： 一般用在两个栈,一个栈插入数据时,另外一个栈就要删除一个数据。

标签：链表,结点,cur,元素,next,学习,数据结构,指针
From： https://www.cnblogs.com/cyxyrq-code-loading/p/17547829.html