一、数组实现单链表用数组模拟单链表操作有初始化、增、删、改、查用数组模拟必须理解数组的知识如下标从0开始在a[5]实际上有效数据是a[0]~a[4]。先用结构体去模拟单链表此后只需要声明一个结构体即可完成#define maxx 20 typedef struct array { int* data;//利用指针开辟数组 //或者用 int data[maxx] int size;//记录数组元素个数同时也是作为下标的位置 }array;1增——按顺序插入尾插法array rear_add(array a, int k){ //if (a.size maxx) 需要判满因为是按数组模拟所以存储是从下标0开始 a.data[a.size] k; a.size; return a; }1增——在指定位置下标位置插入array insert(array a, int n, int k){ //n为下标位置 //if (a.size maxx) 每次插入需要判满因为数组模拟空间是固定的如果有需要可以把空间开大 for (int i a.size ; i n; i--) //倒序移动腾出位置 { a.data[i] a.data[i-1]; } a.data[n] k;//把该位置的元素修改成k a.size;//代表增加了一个元素 return a; }2查——查找数据的下标位置int find(array a, int k){ for (int i 0; i a.size; i)//正序查找从下标0开始 { if (a.data[i] k) { return i; //i就是当前元素k的下标 } } return -1;//规定-1是未查找到 }3删——删除数据k array delet(array a, int k){ int n find(a, k);//查询数组中是否有元素k if (n -1) { cout 无此数无法删除\n; return a; } for (int i n; i a.size; i)//元素进行前移动覆盖删去的元素 { a.data[i] a.data[i 1]; } a.size--; return a; }4改——把数据x修改成k array amend(array a, int x, int k){ int n find(a, x); //查询当前元素中是否存在xn为查询元素x的下标位置 if (n -1) { cout 无此数无法修改 endl; return a; } a.data[n] k; return a; }二、单向链表 而在单链表中就真正用到了指针等操作也是初始化、增、删、查、改单链表也需要用到结构体typedef struct Node{ int data; //数据域 struct Node* next; //指针域 }node,*Linknode; //*Linkndoe node* ,我们这样用是为了声明一个头指针且增强可读性1初始化——即声明一个头指针Linknode Init(){ Linknode st new node;//申请的是头指针数据域不作要求 st-next NULL;//头指针不属于真正链接中的元素结点由于开始并没有结点所以头指针指向NULL return st; }2增——头插法node* insert(Linknode st,int k){ node* s new node; //申请一个新的结点 s-data k; //因为st是头结点使用头插法时需要把新的结点先指向头结点原来指向的结点防止后面结点的丢失 s-next st-next; st-next s; //再把头结点指向新的结点 return st; }2增——尾插法node* back(Linknode st,int k){ node* pst; //申请一个新的结点先指向头结点为了之后方便用p查找尾结点 while(p-next!NULL)//即p是尾结点 { p p-next; } node* snew node; s-data k; s-next NULL; //因为尾插法是直接在最后的结点插入新结点则直接把新结点的指针域指向空 p-next s; //再把原来尾结点的指针域指向新的尾结点 return st; }2增——指定数据x后插入新的结点node* clinsert(Linknode st,int x,int k){ //在数据x后插入k node* p find(st,x); //用p去查找数据x的结点地址 if(pNULL) { cout 无此数\n; return st; } node* snew node; s-data k; s-next p-next; //使新结点指向数据x所在结点原来指向的结点 p-next s; //再把x所在结点指向新的结点 return st; }3查——查找数据所在的结点位置node* find(Linknode st,int x){ //因为我们是找数据所以我们不同于尾结点(尾结点是直接指向头结点因为要判断此结点的指针域是不是指向空)而找数据我们直接指向头指针指向的位置。 node* pst-next; //如果链表中不存在结点则p指向的是NULL同时也是为了防止头指针的数据恰好等于需要查找的数据 while(p!NULLp-data!x) { p p-next; } return p;//返回时存在俩中情况当p等于NULL正说明当前链表不存在数据x否则返回的是数据x结点地址 }4删——删除数据k所在的结点node* delet(Linknode st,int k){ node* pfind(st,k); //先查找数据k所在的结点地址 if(pNULL) { cout 无此数\n; return st; } node* sst; //此时用s去查找数据k结点的上一个结点此方式与尾插法寻找尾结点相似 while(s-next!p) { s s-next; } s-next p-next; //我们直接用数据k结点的上一个结点指向数据k结点的下一个结点就相当于删除了元素k delete p; //最后释放数据k所在的结点因为结点都是在堆中申请的不用后必须释放 p NULL; //使指针p指向NULL防止成为野指针 return st; }5改——把数据x替换成knode* tihuan(Linknode st,int x,int k){ //把数据x替换成k node* pfind(st,x); //还是先寻找数据x的结点地址 if(pNULL) { cout 无此数\n; return st; } p-data k; //找到后直接把x所在的结点的数据域修改成k return st; }三、双向链表双链表与单链表类似其不同是增加了一个指向上一个结点的指针域pre。typedef struct Node{ int data; //数据域 struct Node* next; //指针域指向下一个结点 struct Node* pre; //指针域指向上一个结点 }node,*Linknode; //*Linkndoe node* ,我们这样用是为了声明一个头指针且增强可读性1初始化头指针Linknode Init(){ Linknode st new node;//申请的是头指针数据域不作要求 st-next NULL; st-pre NULL; return st; }2增——头插法node* insert(Linknode st,int k){ node* s new node; s-data k; s-next st-next; if(st-next!NULL) //头插法必须注意如果头指针后有结点存在我们必须要用头指针指向的结点的pre指针指向新的结点 { st-next-pre s; } s-pre st; //新结点的pre指针指向头结点 st-next s; return st; }2增——尾插法node* back(Linknode st,int k){ node* pst; while(p-next!NULL)//即p是尾结点 { p p-next; } node* snew node; s-data k; s-next NULL; s-pre p; //使新结点的pre指针指向p p-next s; //因为尾插法找的是尾结点尾结点后必然是空所以没有p-next-pres;这个操作 return st; }2增——指定数据x后插入新结点node* clinsert(Linknode st,int x,int k){ //在数据x处插入k node* p find(st,x); //去寻找数据x所在的结点地址 if(pNULL) { cout 无此数\n; return st; } node* snew node; s-data k; s-next p-next; if(p-next!NULL) //注意我们需要判断查到到的结点是不是处于尾结点如果处于尾结点明显就没有下一个操作 { p-next-pre s; //说明数据x结点的下一个结点(假如是r)存在需要把r的pre指针指向插入的结点 } s-pre p; p-next s; return st; }3查——查找数据x所在的结点//由于查询操作与单链表一样即直接cv工程 node* find(Linknode st,int x){ //因为我们是找数据所以我们不同于尾结点(尾结点是直接指向头结点因为要判断此结点的指针域是不是指向空)而找数据我们直接指向头指针指向的位置。 node* pst-next; //如果链表中不存在结点则p指向的是NULL同时也是为了防止头指针的数据恰好等于查找的数据 while(p!NULLp-data!x) { p p-next; } return p;//返回时存在俩中情况当p等于NULL正说明当前链表不存在数据x否则返回的是数据x结点地址 }4删——删除数据k所在的结点node* delet(Linknode st,int k){ node* pfind(st,k); //查询k所在的结点地址 if(pNULL) { cout 无此数\n; return st; } //因为是双向链表我们可以用p的pre指针找到p的上一个结点 p-pre-next p-next; if(p-next!NULL) //如果p的下一个结点存在我们也必须使p的下一个结点指向p的上一个结点 { p-next-pre p-pre; } delete p; //用完后必须释放p p NULL; //防止成为野指针 return st; }5改——把数据x替换成k//同理双链表的替换操作与单链表一样 node* tihuan(Linknode st,int x,int k){ //把数据x替换成k node* pfind(st,x); //还是先寻找数据x的结点地址 if(pNULL) { cout 无此数\n; return st; } p-data k; //找到后直接把x所在的结点的数据域修改成k return st; }四、循环单链表循环单链表其实是把尾结点的指针指向头结点其余与单链表并无差别。typedef struct Node{ int data; //数据域 struct Node* next; //指针域 }node,*Linknode; //*Linkndoe node* ,我们这样用是为了声明一个头指针且增强可读性1初始化——即声明一个头指针Linknode Init(){ Linknode st new node;//申请的是头指针数据域不作要求 st-next st; //循环链表中不存在NULL直接使头指针指向自己 return st; }2增——头插法node* insert(Linknode st,int k){ node* s new node; //申请一个新的结点 s-data k; //因为st是头结点使用头插法时需要把新的结点先指向头结点原来指向的结点防止后面结点的丢失 s-next st-next; st-next s; //再把头结点指向新的结点 return st; }2增——尾插法node* back(Linknode st,int k){ node* pst; while(p-next!st)//因为在循环链表中没有NULL我们的判断条件为p-next是否指向头结点 { p p-next; } node* snew node; s-data k; s-next p-next; //这里我们不能写s-nextNULL,但是可以写成s-nextst p-next s; return st; }2增——指定数据x后插入新结点node* clinsert(Linknode st,int x,int k){ //在数据x后插入k node* p find(st,x); //用p去查找数据x的结点地址 if(pst) { cout 无此数\n; return st; } node* snew node; s-data k; s-next p-next; //使新结点指向数据x所在结点原来指向的结点 p-next s; //再把x所在结点指向新的结点 return st; }3查——查找数据x所在的结点node* find(Linknode st,int x){ //因为我们是找数据所以我们不同于尾结点(尾结点是直接指向头结点因为要判断此结点的指针域是不是指向头结点且避免头结点数据域混淆答案)而找数据我们直接指向头指针指向的位置。 node* pst-next; //循环链表中如果链表中不存在结点则p指向的是头结点同时也是为了防止头指针的数据恰好等于需要查找的数据 while(p!stp-data!x) { p p-next; } return p;//返回时存在俩中情况当p等于st正说明当前链表不存在数据x否则返回的是数据x结点地址 }4删——删除数据k所在的结点node* delet(Linknode st,int k){ node* pfind(st,k); //先查找数据k所在的结点地址 if(pst) { cout 无此数\n; return st; } node* sst; //此时用s去查找数据k结点的上一个结点此方式与尾插法寻找尾结点相似 while(s-next!p) { s s-next; } s-next p-next; //我们直接用数据k结点的上一个结点指向数据k结点的下一个结点就相当于删除了元素k delete p; //最后释放数据k所在的结点因为结点都是在堆中申请的不用后必须释放 p NULL; //使指针p指向NULL防止成为野指针 return st; }5改——把数据x替换成knode* tihuan(Linknode st,int x,int k){ //把数据x替换成k node* pfind(st,x); //还是先寻找数据x的结点地址 if(pst) { cout 无此数\n; return st; } p-data k; //找到后直接把x所在的结点的数据域修改成k return st; }五、循环双链表循环双链表也是把尾结点的next指针指向头结点把头结点的pre指针指向尾结点。typedef struct Node{ int data; //数据域 struct Node* next; //指针域指向下一个结点 struct Node* pre; //指针域指向上一个结点 }node,*Linknode; //*Linkndoe node* ,我们这样用是为了声明一个头指针且增强可读性1初始化——声明一个头指针Linknode Init(){ Linknode st new node;//申请的是头指针数据域不作要求 st-next st; //循环链表中不存在NULL开始next、pre指针都指向自己 st-pre st; return st; }2增——头插法node* insert(Linknode st,int k){ node* s new node; s-data k; s-next st-next; /*if(st-next!NULL) 因为循环链表中不会存在NULL所以不同于普通双链表没有此判断条件 { st-next-pre s; }*/ st-next-pre s; //头结点指向的下一个结点的pre指向新结点 s-pre st; //新结点的pre指针指向头结点 st-next s; return st; }2增——尾插法node* back(Linknode st,int k){ node* pst; while(p-next!st)//即p是尾结点 { p p-next; } node* snew node; s-data k; s-next st; st-pre s; //注意需要把头结点的pre更新到新的尾结点 这个其实相当于p-next-pres,因为p-next指向的就是st头节点 s-pre p; //使新结点的pre指针指向p p-next s; return st; }2增——指定数据x后插入新结点node* clinsert(Linknode st,int x,int k){ //在数据x处插入k node* p find(st,x); //去寻找数据x所在的结点地址 if(pst) { cout 无此数\n; return st; } node* snew node; s-data k; s-next p-next; /*if(p-next!NULL) 同理循环链表中不用判断这个条件 { p-next-pre s; }*/ p-next-pre s; s-pre p; p-next s; return st; }3查——查找数据x所在的结点//循环双链表操作与循环单链表操作一样 node* find(Linknode st,int x){ //因为我们是找数据所以我们不同于尾结点(尾结点是直接指向头结点因为要判断此结点的指针域是不是指向头结点且避免头结点数据域混淆答案)而找数据我们直接指向头指针指向的位置。 node* pst-next; //循环链表中如果链表中不存在结点则p指向的是头结点同时也是为了防止头指针的数据恰好等于需要查找的数据 while(p!stp-data!x) { p p-next; } return p;//返回时存在俩中情况当p等于st正说明当前链表不存在数据x否则返回的是数据x结点地址 }4删——删除数据k所在的结点node* Delet(Linknode* st, int k){ Node* p find(st, k); //先查找数据k所在的结点 if (p st) { cout 数据不存在无法删除\n; return st; } p-pre-next p-next; p-next-pre p-pre; delete p; p NULL; return st; }5改——把数据x替换成k//循环双链表的修改操作和循环单链表操作一样 node* tihuan(Linknode st,int x,int k){ //把数据x替换成k node* pfind(st,x); //还是先寻找数据x的结点地址 if(pst) { cout 无此数\n; return st; } p-data k; //找到后直接把x所在的结点的数据域修改成k return st; }