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

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

一、线性表

文章目录

​​一、线性表​​

​​:heart:顺序表的实现---静态分配:heart:​​​​:heart:顺序表-静态数组的基本操作---插入:heart:​​​​:heart:顺序表的实现---动态分配:heart:​​​​:heart:顺序表的基本操作---删除:heart:​​​​:heart:顺序表的按值查找:heart:​​​​:heart:带头结点的单链表:heart:​​​​:heart:单链表的插入操作:heart:​​​​:heart:单链表的删除操作:heart:​​

​​:heart:双链表的初始化（带头结点）:heart:​​​​:heart:双链表的插入:heart:​​​​:heart:双链表的删除:heart:​​​​:heart:循环单链表:heart:​​​​:heart:循环双链表:heart:​​

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

顺序表的创建和初始化

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

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

#include #define MaxSize 10//定义最大长度typedef struct{ int data[MaxSize]; int length;}SqList;void InitList(SqList &L){ fot(int i=0;i=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 #define MaxSize 10//定义最大长度typedef struct{ int data[MaxSize]; int length;}SqList;void InitList(SqList &L){ fot(int i=0;iL.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 #include #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

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

#include #define MaxSize 10//定义最大长度typedef struct{ int data[MaxSize]; int length;}SqList;void InitList(SqList &L){ fot(int i=0;iL.length) return FALSE; e=L.data[i-1];//将被删除的元素赋值给e for(int j=i;j

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

#include #define InitSize 10typedef struct{ ElemType *data; int MaxSize; int length;}SeqList;//在顺序表L中查找第一个元素值等于e的元素，并返回其次序int LocateElem(SeqList L,ElemType e){ for(int i=0;i

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

#include 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 typedef struct LNode{//定义单链表结点 ElemType data; struct LNode *next;}LNode,*LinkList;//在第i个位置插入元素ebool ListInsert(LinkList &L,int i,int e){ if(i<1) return FALSE; LNode *p; int j=0; p=L; while(p!=null&&jnext; 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 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&&jnext; 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结点之后插入元素ebool 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 #include 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&&jnext; j++; } //直接返回封装代码：后插操作 return InsrertNextNode(p,e); }//后插操作，在p结点之后插入元素ebool 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结点之前插入结点sbool 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&&jnext; 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 #include //双链表的初始化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 #include //双链表的初始化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 #include //双链表的初始化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 #include //定义循环单链表结点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 #include //定义一个循环双链表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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。