首页 > 其他分享 >数据结构（第二章）

数据结构（第二章）

时间：2023-03-25 21:55:15浏览次数：32  
标签：结点 第二章 return LNode int next 数据结构 data

数据结构（第二章）

一、线性表

  • 概念：线性表是具有相同数据类型的n(n>0)个数据元素的有序数列。
  • 第一个元素没有直接前驱，最后一个元素没有直接后继。
  • 表中元素的个数有限
  • 表中元素具有逻辑上的顺序性，表中元素有其先后顺序。
  • 表中元素都是数据元素，每个元素都是单个元素。
  • 表中元素的数据类型相同，这意味着每个元素占有相同大小的存储空间。
  • 表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

二、线性表的顺序表示

  • 定义：线性表的顺序存储又称顺序表，顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。
  • 线性表的顺序存储结构是一种随机存取的存取结构。
  • 线性表中元素的位序是从1开始的，而数组中元素的下标是从0开始的。
  • 特点：1. 随机访问（通过首地址和元素序号可在O（1）内找到指定的元素） 2. 存储密度高，每个结点只存储数据元素。3. 顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。

顺序表的基本实现

  1. 初始化
//静态分配数组空间
typedef  struct {
ElemType data[MaxSize];
int length;
}SqList;

//动态分配数组空间
typedef  struct {
    ElemType  *data;
    int MaxSize, length;
}SqList;
  1. 插入操作
bool ListInsert(SqList L, int i,ElemType e){

    if(i<1||i>L.length+1)
        return false;
    if(L.length>MaxSize)
        return false;
    for (int j = L.length; j >=i ; j--)
        L.data[j]=L.data[j-1];
        L.data[i-1]=e;
        L.length++;
    return true;
}
  1. 删除操作
bool DeleteList(SqList L , int i){
    if(i<1||i>L.length)
        return false;
    for (int j = i; j <=L.length ; j++)
        L.data[j-1]=L.data[j];
        L.length--;

    return true;
}
  1. 创建顺序表
SqList CreateList(SqList L){
    L.data=(ElemType *) malloc(sizeof (ElemType)*MaxSize);
    L.length=0;
    int x;
    for (int i = 0; i < MaxSize; ++i) {
        scanf("%d",&x);
        if(x==9999)
            break;
        L.data[i]=x;
        L.length++;
    }
    return L;
}
  1. 查找元素
ElemType  LocateElem(SqList L ,ElemType e){
    int i;
    for ( i = 0; i < L.length; i++)
        if(L.data[i]==e)
            return i+1;
    return 0;
}
  1. 完整项目
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define  MaxSize 10

typedef  int ElemType;

//静态分配
//typedef  struct {
//ElemType data[MaxSize];
//int length;
//}SqList;

//动态分配数组空间
typedef  struct {
    ElemType  *data;
    int InitSize, length;
}SqList;

//插入操作
bool ListInsert(SqList L, int i,ElemType e){


    if(i<1||i>L.length+1)
        return false;
    if(L.length>=MaxSize)
        return false;
    for (int j = L.length; j >=i ; j--)
        L.data[j]=L.data[j-1];
        L.data[i-1]=e;
        L.length++;

    return true;
}

//删除操作
bool DeleteList(SqList L , int i){
    if(i<1||i>L.length)
        return false;
    for (int j = i; j <=L.length ; j++)
        L.data[j-1]=L.data[j];
        L.length--;

    return true;
}

//初始化链表
void InitList(SqList L)
{
    L.data=(ElemType *) malloc(sizeof (ElemType)*MaxSize);
    L.length=0;
}
//创建链表
SqList CreateList(SqList L){
    L.data=(ElemType *) malloc(sizeof (ElemType)*MaxSize);
    L.length=0;
    int x;
    for (int i = 0; i < MaxSize; ++i) {
        scanf("%d",&x);
        if(x==9999)
            break;
        L.data[i]=x;
        L.length++;
    }
    return L;
}

//遍历顺序表

bool Scan(SqList L){

    for (int i = 0; i < MaxSize; ++i) {
        printf("%d\t",L.data[i]);
    }
    return true;
}

//查找元素
ElemType  LocateElem(SqList L ,ElemType e){
    int i;
    for ( i = 0; i < L.length; i++)
        if(L.data[i]==e)
            return i+1;
    return 0;
}

int main(){
    //初始化顺序表
    SqList L;
    InitList(L);
    L=CreateList(L);
    printf("顺序表中的数据为： ");
    Scan(L);
    printf("\n");
    printf("插入值是否正确 T-1 F-0： %d",ListInsert(L,3,23));
    printf("\n");
   printf("插入新元素后的顺序表中的数据为： ");
   Scan(L);
    printf("\n");
    printf("查找到的元素的位置为： %d",LocateElem(L,5)) ;
}

图解流程关系

  • 插入操作

image-20230319083646280

image-20230319083913628

比方说，元素P想插入到i位置，则原先i位置的元素和其后面的元素都要向后移动。为了保证元素不被覆盖，应该从最后一个元素开始向后移动，如果从i位置开始移动，从i位置开始就会将元素覆盖。

  • 删除操作

image-20230319084537123

image-20230319084636756

删除元素p，有两种方式(一、是可以查找该元素的下标删除二、传入该元素值，然后遍历寻找，进行删除)。

删除操作，就是将i位置的元素删除，此时i位置就是空的，所以需要将i位置以后的元素向前移动。

到这里，顺序表的基本概念就基本介绍完成了，我们可以发现，顺序表是直接在内存中截取的一段连续存储空间进行数据存储的，数据是连续的，非常方便查找，但是插入和删除操作的时间复杂度都是O（n）,耗时都是非常大的。所以为了方便进行插入和删除操作，就引出了链表。

三、线性表的链式表示

  • 概念：线性表的链式存储又称单链表，它是通过一组任意的存储单元来存储线性表中的数据元素。

单链表的结构特点：

image-20230319093045301

单链表的存储结构除了包含，存放当前元素的结点以外，还包含一个指针用于存放后继元素的地址。其中data为数据域，next为指针域，存放其后继结点的地址。

  • 特点：由于单链表的元素离散地分布在存储空间中，所以单链表是非随机存取的存储结构，即不能直接找到表中某个特定的特点。查找某个特定的结点时，需要从表头开始遍历，依次查找。

  • 这里通常使用一个头结点L来标识一个单链表

image-20230319171456225

头结点不用来存储数据，只是用来标识单链表的，头结点的指针域指向线性表的第一个元素结点。

优点：

  1. 带头结点后，第一个位置上的操作和其他位置上数据的操作一样，不需要进行特殊处理了。
  2. 无论链表是否为空，头指针都是指向头结点的非空指针（空表头结点的指针域为空），因此非空表和空表的处理也就得到了统一。

单链表的基本实现

  1. 定义单链表
typedef  struct LNode{
    ElemType   data;  //数据域
    struct LNode *next; //指针域

}LNode ,*LinkList;
  1. 头插法创建单链表
 //头插法创建单链表
 LinkList List_Insert(LinkList L )
 {
     LNode *p;
     int x;
     InitList(L);
     scanf("%d",&x);
     while(x!=9999){
         p->data=x;
         p->next=L->next;
         L->next=p;
         scanf("%d",&x);
     }
     return L;
 }
  • 图解：

image-20230320081909565

  1. 尾插法创建单链表
 LinkList List_Tail(LinkList L)
 {
     InitList(L);
     LNode *p,*r=L;
     int x;
     scanf("%d",&x);
     while(x!=9999){
         p->data=x;
         r->next=p;
         r=p;
         scanf("%d",&x);
     }
     r->next=NULL;
     return L;
 }
  • 图解:

image-20230320082936848

  1. 初始化
 LinkList InitList(LinkList L){
     L=(LinkList) malloc(sizeof (LNode));
     L->next=NULL;
 }
  1. 按位查找结点
 LNode *GetElem(LinkList L , int i){
     int j=1;
     LNode *p=L->next;
     if(i<0)
         return FALSE;
     if(i==0)
         return L;
     while(p&&j<i){
         p=p->next;
         j++;
     }
     return p;
 }
  1. 按元素查找结点
 LNode *LocateElem(LinkList L , ElemType e){
     LNode  *p=L->next;
     while(p!=NULL&&p->data!=e)
         p=p->next;
     return p;
 }
  1. 插入结点操作
int InsertLNode(LinkList L ,int i ,ElemType e){
     LNode *p,*s;
     p=GetElem(L,i-1);
     s=(LNode *) malloc(sizeof (LNode));
     s->next=NULL;
     s->data=e;
     s->next=p->next;
     p->next=s;
     return TRUE;
 }
  • 图解：

image-20230320083953260

注：这里我们必须明白一点，我们向链表中插入元素的时候，需要保证链表不断，所以我们进行的第一步必须是存储插入位置后继结点的指针域（如上述中的p->next）,只有先进行这一步才能保证链表不断，如果先进行第一步，这是a1中存储后继结点的指针域就变成了s指向的地址，a3处的地址就会丢失，链表断裂

这里：我们需要想清楚为什么第一步需要先存储插入位置的后继结点的地址，就是为了保证链表不断，明白这一点对于后继链表的插入操作的帮助非常重要！

  1. 对链表中的元素进行就地逆置

就地逆置：就是不能开辟新的存储空间，空间复杂度为O（1）

  • 8-1 头插法进行就地逆置
 LinkList  ConptaryList(LinkList L){
     LNode *p,*q;
     p=L->next;
     L->next=NULL;
     while(p){
         q=p->next;
         p->next=L->next;
         L->next=p;
         p=q;
     }
     return L;
 }
  • 图解：

image-20230320090631809

  • 8-2元素直接逆置连接
 LinkList  ConptrayList2(LinkList L){
     LNode *pre , *p=L->next,*r=p->next;
     p->next=NULL;
     while(r){
         pre=p;
         p=r;
         r=r->next;
         p->next=pre;
     }
     L->next=p;
     return L;
 }
  • 图解：

image-20230320144102493

以上就是现今能够用到的两种逆置的方法

  1. 第一种通过头插法的思想（头插法创建的链表是和输入元素刚好想反的）将元素依次插入到头结点之后，进而实现就地逆置，时间复杂度O(n).
  2. 第二种是直接将元素调头，将三个相邻的元素，进行掉头，通过对第三个元素进行遍历，来进行判断。

这里通过书面表达，还是不方便理解，这里建议读者可以通过相应的视频，以及通过作图来加深自己的理解。

  1. 删除结点操作
ElemType DeleteLNode(LinkList L ,int i){
    LNode *p,*q;
    ElemType e;
    p= GetElem(L,i-1);
    q=p->next;
    e=q->data;
    p->next=q->next;
    free(q);
    return  e;
}
  1. 求单链表的长度
int HeightList(LinkList L)
{
    int length=0;
    LNode *p=L->next;
    while(p!=NULL){
        p=p->next;
        length++;
    }
    return length;
}
  1. 遍历打印单链表中的数据
 _Bool ScanList(LinkList L){
    LNode *p=L->next;
    while(p){
        printf("%d ",p->data);
        p=p->next;
    }
    return TRUE;
}
  1. 完整项目程序
#include <stdio.h>
#include <stdlib.h>

#define FALSE 0;
#define TRUE 1;

typedef  int ElemType;
typedef  struct LNode{
    ElemType   data;  //数据域
    struct LNode *next; //指针域

}LNode ,*LinkList;

//初始化
LinkList InitList(LinkList L){
    L=(LinkList) malloc(sizeof (LNode));
    L->next=NULL;
}

//头插法创建单链表
LinkList List_Insert(LinkList L )
{
    LNode *p;
    int x;
    InitList(L);
    scanf("%d",&x);
    while(x!=9999){
        p->data=x;
        p->next=L->next;
        L->next=p;
        scanf("%d",&x);
    }
    return L;
}

//尾插法创建单链表
LinkList List_Tail(LinkList L)
{
    InitList(L);

    LNode *p,*r=L;
    int x;
    scanf("%d",&x);
    while(x!=9999){
        p=(LNode *) malloc(sizeof (LNode));
        p->data=x;
        r->next=p;
        r=p;
        scanf("%d",&x);
    }
    r->next=NULL;
    return L;
}

//按位查找单链表
LNode *GetElem(LinkList L , int i){
    int j=1;
    LNode *p=L->next;
    if(i<0)
        return FALSE;
    if(i==0)
        return L;
    while(p&&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;
}

//插入结点操作
int InsertLNode(LinkList L ,int i ,ElemType e){
    LNode *p,*s;
    p=GetElem(L,i-1);
    s=(LNode *) malloc(sizeof (LNode));
    s->next=NULL;
    s->data=e;
    s->next=p->next;
    p->next=s;
    return TRUE;
}

//对元素进行就地逆置  空间复杂度O(1)
//1-1头插法就地逆置
LinkList  ConptaryList(LinkList L){
    LNode *p,*q;
    p=L->next;
    L->next=NULL;
    while(p){
        q=p->next;
        p->next=L->next;
        L->next=p;
        p=q;
    }
    return L;
}
//1-2
LinkList  ConptrayList2(LinkList L){
    LNode *pre , *p=L->next,*r=p->next;
    p->next=NULL;
    while(r){
        pre=p;
        p=r;
        r=r->next;
        p->next=pre;
    }
    L->next=p;
    return L;
}

//删除结点操作
ElemType DeleteLNode(LinkList L ,int i){
    LNode *p,*q;
    ElemType e;
    p= GetElem(L,i-1);
    q=p->next;
    e=q->data;
    p->next=q->next;
    free(q);
    return  e;
}

//求单链表的长度

int HeightList(LinkList L)
{
    int length=0;
    LNode *p=L->next;
    while(p!=NULL){
        p=p->next;
        length++;
    }
    return length;
}

//遍历表中元素
 _Bool ScanList(LinkList L){
    LNode *p=L->next;
    while(p){
        printf("%d ",p->data);
        p=p->next;
    }
    return TRUE;
}
int main(){

    LinkList L;
    printf("向单链表中输入元素： ");
   L= List_Tail(&L);
    printf("打印表中顺序： ");
    ScanList(L);
    printf("\n");
    printf("头插法就地逆置为： ");
    ConptaryList(L);
    ScanList(L);
    printf("\n");
    printf("向单链表中插入结点： ");
    InsertLNode(L,3,66);
    ScanList(L);
    printf("\n");
    printf("删除单链表中的结点： ");
    DeleteLNode(L,3);
    ScanList(L);
    printf("\n");
    printf("单链表中的长度： ");
    printf("%d ",HeightList(L));

    return 0;
}

双链表的基本实现

  1. 概念：通过上述代码，我们可以看到，单链表结点中只有一个指向其后继的指针，使得单链表只能从头结点依次顺序的向后遍历。在进行插入和删除操作时，需要先遍历某个结点的前驱结点，因此平均时间复杂度为O（n）,为了克服这个缺点进而引入了双链表。
  2. 定义双链表
typedef struct DNode{
    int data; //数字域
    struct DNode *prior,*next; //前驱结点 ， 后继结点
}DNode, *DLinkList;

双链表示意图：

image-20230324112239107

  1. 双链表的插入操作
//将x插入到双链表L中*p结点的下一个结点
void Insert(DLinkList L, DNode *p, int x){
    DNode *s = (DNode *)malloc(sizeof(DNode));
    s->data = x;
    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p->next = s;
}

图解：

image-20230324113556679

这里的双链表插入和单链表类似，不过多了一个前驱指针，用来访问前驱结点，这也是区别于单链表的优点。

  1. 双链表的删除操作
//删除操作:将双链表中的第i个结点删除
void Delete(DLinkList L, int i){
if(i<1 || i>Length(L)){
    printf("delete failed: index is wrong.\n");
return;
}
DNode *p = GetElem(L,i-1);
DNode *q = p->next;
p->next = q->next;
q->next->prior = p;
free(q);
}

图解：

image-20230324114454782

  1. 完整项目
#include<stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct DNode{
    int data; //数字域
    struct DNode *prior,*next; //前驱结点 ， 后继结点
}DNode, *DLinkList;

//初始化
void InitList(DLinkList L){
L = (DNode *)malloc(sizeof(DLinkList));
L->prior = NULL;
L->next = NULL;
}

//遍历操作
void PrintList(DLinkList L){
    DNode *p = L->next;
    while(p){
        printf("循环遍历的值为：%d",p->data);
        p = p->next;
    }
    printf("\n");
}

//求双链表的长度
int Length(DLinkList L){
    DNode *p = L->next;
    int len = 0;
    while(p){
        len++;
        p = p->next;
    }
    return len;
}

//头插法建立双链表
DLinkList HeadInsert(DLinkList L){
InitList(L); //初始化
int x;
    scanf("%d",&x);
    while(x!=9999){
    DNode *s = (DNode *)malloc(sizeof(DNode));
    s->data = x;
    if(L->next == NULL){
    s->next = NULL;
    s->prior = L;
    L->next = s;
    }else{
    s->next = L->next;
    L->next->prior = s;
    s->prior = L;
    L->next = s;
    }
        scanf("%d",&x);
    }
return L;
}

//尾插法建立双链表
DLinkList TailInsert(DLinkList L){
InitList(L);
DNode *s,*r=L;
int x;
    scanf("%d",&x);
    while(x!=9999){
    s = (DNode *)malloc(sizeof(DNode));
    s->data = x;
    s->next = NULL;
    s->prior = r;
    r->next = s;
    r = s;
        scanf("%d",&x);
    }
return L;
}

//按值查找：查找x在L中的位置
DNode *LocateElem(DLinkList L, int x){
    DNode *p = L->next;
    while(p && p->data != x){
        p = p->next;
    }
    return p;
}

//按位查找：查找在双链表L中第i个位置的结点
DNode *GetElem(DLinkList L, int i){
    int j=1;
    DNode *p = L->next;
    if(i==0)return L;
    if(i<1)return NULL;
    while(p && j<i){
        p = p->next;
        j++;
    }
    return p; //如果i大于表长，p=NULL,直接返回p即可
}

//将x插入到双链表L中*p结点的下一个结点
void Insert(DLinkList L, DNode *p, int x){
    DNode *s = (DNode *)malloc(sizeof(DNode));
    s->data = x;
    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p->next = s;
}

//删除操作:将双链表中的第i个结点删除
void Delete(DLinkList L, int i){
if(i<1 || i>Length(L)){
    printf("delete failed: index is wrong.\n");
return;
}
DNode *p = GetElem(L,i-1);
DNode *q = p->next;
p->next = q->next;
q->next->prior = p;
free(q);
}

//判空操作
bool Empty(DLinkList L){
    if(L->next == NULL){
        printf("L is null");
        return true;
    }else{
        printf("L is not null");
        return false;
    }
}


int main(){
    //尾插法建立双链表，并遍历单链表
    DLinkList L = TailInsert(L);
    printf("L: ");
    PrintList(L);

    DNode *p;
    //按值查找
    p = LocateElem(L,2);

    printf("值为2的结点的下一个结点值是：%d",p->next->data);
    printf("值为2的结点的上一个结点值是：%d",p->prior->data);
    //按位查找
    p = GetElem(L,3);

    printf("第三个结点值是：%d",p->data);

    //插入操作
    Insert(L,p,7);
    printf("在第三个结点后面插入值为7的结点后L： ");
    PrintList(L);

    //删除操作
    Delete(L, 5);
    printf("删除第五个结点后L： ");
    PrintList(L);

    //求表长
    printf("表长为：%d",Length(L));

    //判空
    Empty(L);
    return 0;
}

循环链表的基本实现

  1. 循环单链表

循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL，而是改为指向头结点，从而将链表转换成一个环形。

此时：

r->next=L; //不存在空的指针域结点

此时判断表是否为空是看头结点的指针是否等于头指针

L->next=L; //此时就是空表

此时判断表是否为满是看尾结点的指针是否等于头指针

r->next=L;//此时就是链表已满

其基本操作和单链表基本相同这里，就不展开赘述了。

标签：结点,第二章,return,LNode,int,next,数据结构,data
From： https://www.cnblogs.com/wfy-studying/p/17255716.html

相关文章

  • 数据结构-哈希表
     哈希表hashtable数据结构dictht是hashtable的数据结构，dictEntry是每个entry元素的数据结构。typedefstructdictht{//指针数组，这个hash的桶dictEntry*......
  • 数据结构与算法-目录
    数组头文件定义：链接初始化数组、清空销毁数组结构：链接输入元素创建数组、打印数组：链接数组扩容：链接在数组尾部追加元素：链接插入元素：链接删除元素：链接删除元素X：链接......
  • 第二章 DC-DC变换器设计与磁学基础
    对于DCDC变换器，只有电感这一个磁性元件需要考虑，它通常需要我们自行设计。2.1直流传递函数开关导通期间，电感中的电流在电压的作用下呈现一定的斜率上升，增量为：\[\triangle......
  • 第二章：3、数据传输方式脑图
    ......
  • 第二章：4、数据交换技术脑图
    ......
  • 第二章：5、信道复用技术脑图
                                         信道复用的概念......
  • 数据结构-->单链表OJ题--->讲解_02
    老铁们，本期讲解反转单链表双指针法代码如下所示:>现在附上测试环节:>以及最终实现的图样链表，如下：另外，别忘了对“Reverse_SLT”反转函数于头文件中声明！！这就是采用双指针......
  • 数据结构-->单链表OJ题--->讲解_01
    老铁们，本期我们开讲单链表OJ题的讲解：删除单链表中给定的val值，并将剩余的链表进行链接本题中val的值是11，删除后的图示链接为:>显然，我们需要指针cur移动来寻找指定数值val......
  • 数据结构合集
    链表链表是一种本身并不常用的数据结构。然而其衍生出的许多数据结构如块状链表和链式前项星等却十分甚至九分的常用。链表简介顾名思义，链表就是使用链连接在一起的数......
  • LevelDb-基本数据结构
    目录SliceArenaskiplist跳表本质时空复杂度插入，删除数据（如何维护索引）极端情况分析：不维护索引极端情况分析：每次插入都维护插入效率和查找效率取舍删除对比红黑树的优势leve......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99