01（数据结构考研）线性表相关操作代码-阿里云开发者社区

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

顺序表的创建和初始化

#include <stdio.h>
#define MaxSize 10//定义最大长度
typedef struct{
    int data[MaxSize];
    int length;
}SqList;
void InitList(SqList &L){
    fot(int i=0;i<MaxSize;i++)
        L.data[i]=0;
    L.length=0;
}
int main()
{
   SqList L;
   InitList(L);
   return 0;
}

❤️顺序表-静态数组的基本操作—插入❤️

#include <stdio.h>
#define MaxSize 10//定义最大长度
typedef struct{
    int data[MaxSize];
    int length;
}SqList;
void InitList(SqList &L){
    fot(int i=0;i<MaxSize;i++)
        L.data[i]=0;
    L.length=0;
}
void ListInsert(SqList &L,int i,int e){
    for(int j=L.length;j>=i;j--)//将第i个元素及之后的元素后移
        L.data[j]=L.data[j-1];
    L.data[i-1]=e;//在位置i处放入e
    L.length++;
}
int main()
{
   SqList L;
   InitList(L);
   ListInsert(L,5,3);
   return 0;
}

考虑到插入操作代码的健壮性，我们修改一下：

判断i的范围是否有效
判断存储空间能不能插入

#include <stdio.h>
#define MaxSize 10//定义最大长度
typedef struct{
    int data[MaxSize];
    int length;
}SqList;
void InitList(SqList &L){
    fot(int i=0;i<MaxSize;i++)
        L.data[i]=0;
    L.length=0;
}
void 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-1]=e;//在位置i处放入e
    L.length++;
}
int main()
{
   SqList L;
   InitList(L);
   ListInsert(L,5,3);
   return 0;
}

❤️顺序表的实现—动态分配❤️

顺序表的创建和初始化，增加动态数组的长度功能

#include <stdio.h>
#include <stdlib.h>
#define InitSize 10//定义最大长度
typedef struct{
    int *data;
    int MaxSize;
    int length;
}SqList;
void InitList(SqList &L){
  //用malloc函数申请一片连续的内存空间
  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));
    for(int i=0;i<L.lenght;i++){
        L.data[i]=p[i];//将数据复制到新区域
    }
    L.MaxSize=L.MaxSize+len;//将顺序表的最大长度增加len
    free(p);
}
int main()
{
   SqList L;
   InitList(L);
   IncreaseSize(L,5);
   return 0;
}

❤️顺序表的基本操作—删除❤️

#include <stdio.h>
#define MaxSize 10//定义最大长度
typedef struct{
    int data[MaxSize];
    int length;
}SqList;
void InitList(SqList &L){
    fot(int i=0;i<MaxSize;i++)
        L.data[i]=0;
    L.length=0;
}
bool ListDelete(SqList &L,int i,int &e){
    if(i<||i>L.length)
        return FALSE;
    e=L.data[i-1];//将被删除的元素赋值给e
    for(int j=i;j<L.length;j++){//将第i个位置后的元素前移动
        L.data[j-1]=L.data[j];
    L.length--;
    return true;
    }
}
int main()
{
   SqList L;
   InitList(L);
   if(ListDelete(L,3,e);){
       printf("已经删除第三个元素：%d\n",e);
   }else{
       printf("删除失败");
   }
   return 0;
}

❤️顺序表的按值查找❤️

#include <stdio.h>
#define InitSize 10
typedef struct{
    ElemType *data;
    int MaxSize;
    int length;
}SeqList;
//在顺序表L中查找第一个元素值等于e的元素，并返回其次序
int LocateElem(SeqList L,ElemType e){
    for(int i=0;i<L.length;i++)
        if(L.data[i]==e)
            return i+1;//数组下标为i的元素等于e，返回其次序为i+1
    return 0;
}
int main()
{
    SeqList L;
    InitList(L);
    LocateElem(L,5);
    return 0;
}

❤️带头结点的单链表❤️

#include <stdio.h>
typedef struct LNode{//定义单链表结点的类型
    ElemType data;//数据域
    struct LNode *next;//指向下一个结点的指针
}LNode,*LinkList;
//初始化一个单链表
bool InitList(LinkList &L){
    L=(LNode *)malloc(sizeof(Lnode));//申请空间后分配一个头结点
    if(L==NULL)//查看内存是否申请失败
        return FALSE;
    L-next=NULL;//头结点之后暂时还没有结点
    return TRUE;
}
//单链表判空操作
void Empty(LinkList L){
    if(L->next==null)
        return TRUE;
    else
        return FALSE;
}
int main()
{
    LinkList L;
    InitList(L);
    Empty(L);
    return 0;
}

❤️单链表的插入操作❤️

按位序插入（带头结点）

#include <stdio.h>
typedef struct LNode{//定义单链表结点
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;
//在第i个位置插入元素e
bool ListInsert(LinkList &L,int i,int e){
    if(i<1)
        return FALSE;
    LNode *p;
    int j=0;
    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;
}
int main()
{
    LinkList L;
    ListInsert(L);
    return 0;
}

按位序插入（不带头结点）

就是插入到第i个位置

#include <stdio.h>
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;
bool ListInsert(LinkList &L,int i,int 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;//p指向第一个结点，不是头结点
    while(p!=null&&j<i-1){//循环找到第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;//插入成功
        
}
int main()
{
    LinkList L;
    ListInsert(L);
    return 0;
}

在上述代码中，我们可以单独封装插入操作部分的代码，用来体现封装的思想。也就是说，在我们找到第i-1个结点后，我们要对其进行 后插操作，代码：

//后插操作：在p结点之后插入元素e
bool InsrertNextNode{
    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;
}

把这段代码封装一下：

#include <stdio.h>
#include <stdlib.h>
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;
bool ListInsert(LinkList &L,int i,int 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;//p指向第一个结点，不是头结点
    while(p!=null&&j<i-1){//循环找到第i-1个结点
        p=p->next;
        j++;
    }
    //直接返回封装代码：后插操作
   return InsrertNextNode(p,e);
        
}
//后插操作，在p结点之后插入元素e
bool InsrertNextNode{
    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;
}
int main()
{
    LinkList L;
    ListInsert(L);
    return 0;
}

同上，指定结点的前插操作代码：

//前插操作：在p结点之前插入结点s
bool InsertPriorNode(LNode *p,LNode *s){
    if(p==null||s==null)
        return FALSE;
    s->next=p->next;
    p->next=s;
    ElemType temp=p->data;
    p->data=s->data;
    s->data=temp;
    return TRUE;
}

❤️单链表的删除操作❤️

按位序删除（带头结点）

就是删除第i个值

bool ListDelete(LinkList &L,int i,int e){
    if(i<1)
        return FALSE;
    LNode *p;
    int j=0;
    p=L;
    while(p!=null&&j<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;
}

❤️双链表的初始化（带头结点）❤️

#include <stdio.h>
#include <stdlib.h>
//双链表的初始化
typedef struct DNode{
    ElemType data;
    struct Dnode *prior,*next;
}DNode,*DLinklist;
//初始化双链表
bool InitDLinkList(DLinklist &L){
    L=(DNode *)malloc(sizeof(DNode));//分配一个头结点
    if(L==NULL)//内存分配失败，返回false
        return FALSE;
    L->prior=NULL;
    L->next=NULL;
    return TRUE;
}
int main()
{
    //定义双链表
    DLinklist L; 
    //初始化双链表
    InitDLinkList(L);
    return 0;
}

❤️双链表的插入❤️

#include <stdio.h>
#include <stdlib.h>
//双链表的初始化
typedef struct DNode{
    ElemType data;
    struct Dnode *prior,*next;
}DNode,*DLinklist;
//双链表的插入
bool InsertNextNode(DLinklist &L,DNode *s){//s为需要插入的链表
    if(L==null||s==null)
        return FALSE;
    s->next=L->next;
    if(L->next!=null)//如果l结点后面有后继结点
        L->next->prior=s;
    s->prior=p;
    p->next=s;
    return TRUE;
}
int main()
{
    //定义双链表
    DLinklist L; 
    //初始化双链表
    InitDLinkList(L);
    //双链表的插入
    InsertNextNode(L);
    return 0;
}

❤️双链表的删除❤️

#include <stdio.h>
#include <stdlib.h>
//双链表的初始化
typedef struct DNode{
    ElemType data;
    struct Dnode *prior,*next;
}DNode,*DLinklist;
//双链表的删除
void DestoryList(DLinklist &L){
    //循环释放各个结点
    while(p->next!=null)
        DeleteNextDNode(L);
    free(L);//头结点释放掉
    L=null;
}
//删除p结点的后继结点
bool DeleteNextDNode(DNode *p){
    if(p==null)
        return FALSE;
    DNode *q=p->next;
    if(q==null)
        return FALSE;
    p->next=q->next;//1
    if(q->next!=null)
        q->next->prior=p;//2
    free(q);
    return TRUE;
}
int main()
{
    //定义双链表
    DLinklist L; 
    //初始化双链表
    InitDLinkList(L);
    //双链表的插入
    InsertNextNode(L,s);
    //双链表的删除
    DestoryList(L);
    return 0;
}

❤️循环单链表❤️

#include <stdio.h>
#include <stdlib.h>
//定义循环单链表结点
typedef struct LNode{
    ElemType data;
    struct LNode *next;//指针指向下一个结点
}LNode,*LinkList;
//初始化一个循环单链表
bool InitList(LinkList &L){
    L=(LNode *)malloc(sizeof(LNode));
    if(L==NULL)
        return FALSE;
    L->next=L;
    return true;
}
//判断循环单链表是否为空（也是判断是否为循环单链表的表尾结点）
bool Empty(LinkList &L){
    if(L->next==L)//判断为空的条件
        return true;
    else
        return FALSE;
}
int main()
{
    //定义循环单链表
    LNode L;
    //初始化一个循环单链表
    InitList(L);
    //判断循环单链表是否为空
    Empty(L);
    return 0;
}

❤️循环双链表❤️

#include <stdio.h>
#include <stdlib.h>
//定义一个循环双链表
typedef struct DNode{
    ElemType data;
    struct DNode *prior,*next;
}DNode,*DLinkList;
//初始化一个循环双链表
bool DLinkList(DLinkList &L){
    L=(DNode *)malloc(sizeof(DNode));
    if(L==NULL)
        return FALSE;
    L->next=L;
    L->prior=L;
    return TRUE;
    
}
//循环双链表判空操作(判断p结点是否为表尾结点同代码)
bool Empty(DLinkList &L){
    if(L->next==L)
        return TRUE;
    else
        return FALSE;
}
int main()
{
   //定义一个循环双链表
   DNode L;
   //初始化一个循环双链表
   InitDLinkList(L);
   //循环双链表判空操作
   Empty(L);
    return 0;
}

01（数据结构考研）线性表相关操作代码

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

❤️顺序表-静态数组的基本操作—插入❤️

❤️顺序表的实现—动态分配❤️

❤️顺序表的基本操作—删除❤️

❤️顺序表的按值查找❤️

❤️带头结点的单链表❤️

❤️单链表的插入操作❤️

❤️单链表的删除操作❤️

❤️双链表的初始化（带头结点）❤️

❤️双链表的插入❤️

❤️双链表的删除❤️

❤️循环单链表❤️

❤️循环双链表❤️

热门文章

最新文章

相关课程

相关电子书