❤️顺序表的实现—静态分配❤️
顺序表的创建和初始化
#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; }
