王道数据结构代码实现（C++）

王道数据结构代码实现（C++）

前言：基于王道书本的C++代码实现，配上流程图，它可以很好的帮助我们理清代码逻辑。并会加入一些自己的理解，以及易错点注解。

目录

第二章 线性表-常规代码

一、顺序表

1.顺序表存储结构定义

2.在顺序表L的第i个位置插入值为e的元素（1<=i<=L.length+1）

3. 删除表中第i个位置的元素，并引用变量e返回(1<=i<=L.length)

 4.相关代码实现及运行截图

二、链表（LinkList）

1.链表的定义、单链表基本操作

2.双链表

---

第二章 线性表-常规代码

一、顺序表

1.顺序表存储结构定义

2.在顺序表L的第i个位置插入值为e的元素（1<=i<=L.length+1）

1） j=i-1时，跳出循环，因为第i个元素的下标是i-1,移动完毕；

2）一定记得修改表长度！length

3）注意for循环的流程图，循环变量处于闭环中，开始画错了

3. 删除表中第i个位置的元素，并引用变量e返回(1<=i<=L.length)

 注意：先将被删除元素的值赋值给e保存，否则删除后元素值没了

 4.相关代码实现及运行截图

#include<stdlib.h>
#include<stdio.h>
#include <iostream>using namespace std;//顺序表的定义
#define Maxsize 50
typedef struct{int data[Maxsize];int length;
}Sqlist;//初始化顺序表
bool InitList(Sqlist &L){L.length=0;return true;
}//判断顺序表是否为空
bool ListEmpty(Sqlist &L){if(L.length==0)return true;elsereturn false;
}//求表长，即元素个数
void ListLength(Sqlist &L){cout<<"当前表中元素个数为："<<L.length<<endl;
}//在L的第i个位置（位序）插入值为e的数据元素
bool ListInsert(Sqlist &L,int i,int e){if(i<1 ||i>L.length+1)//判断i的合法性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;
}//打印列表
void PrintL(Sqlist &L){cout<<"表中当前的数据是：";for(int i=0;i<L.length;i++)cout<<L.data[i]<<" ";cout<<endl;
}//用e返回第i个元素的值
void GetElem(Sqlist L,int i){cout<<"当前表中第"<<i<<"个位置的元素值为："<<L.data[i-1];
}//删除第i个位置的数据元素，并用e返回
bool ListDelete(Sqlist &L,int i,int &e){if(i<1||i>L.length)return false;if(L.length==0)return false;e=L.data[i-1];for(int j=i;j<L.length;j++)L.data[j-1]=L.data[j];L.length--;return true;
}//返回第一个与e相等的元素的位序（查找值为e的元素的位序）
int LocateElem(Sqlist &L,int e){for(int i=0;i<L.length;i++){if(L.data[i]==e)return i+1;}return false;
}int main()
{Sqlist L;int i,e=10;InitList(L);//初始化顺序表ListEmpty(L);//判断顺序表是否为空cout<<"初始化结果是："<<InitList(L)<<endl;cout<<"判空结果是："<<ListEmpty(L)<<endl;cout<<endl<<"在表的第1个位置插入9："<<endl;ListInsert(L,1,9);//在线性表的第1个位置插入9ListLength(L);PrintL(L);cout<<endl<<"依次插入10~14后："<<endl;//依次插入10~14(批量插入规律的数字)for(i=2;i<6;i++){ListInsert(L,i,e);e++;}ListLength(L);PrintL(L);//9 10 11 12 13//接下来插入一些不规律的数据cout<<endl<<"再插入一些其他数据"<<endl;ListInsert(L,3,66);ListInsert(L,6,-88);ListInsert(L,2,-3);ListInsert(L,5,24);ListLength(L);PrintL(L);//9 -3 10 66 24 11 12 -88 13 至此，插入完成GetElem(L,8);cout<<endl;int x;ListDelete(L,4,x);cout<<endl<<"'删除第4个元素'"<<endl;cout<<"删除的值为："<<x<<endl;PrintL(L);cout<<"'查找值为12的元素位序'"<<endl;cout<<"值为12的元素位序为:"<<LocateElem(L,12)<<endl;
}

 图1、图2为运行截图

二、链表（LinkList）

1.链表的定义、单链表基本操作

（1）存储结构定义

写法1：好久没看，都想不起来，单链表定义中的*LinkList是什么意思了？

typedef struct LNode{int data;//数据域struct LNode* next;//指针域：指向LNode的指针
}LNode,*LinkList;

其实，这里的写法一与写法2等价，*LinkList其实就是定义了一个名为LinkList的指向struct LNode结构体类型变量的指针，把它看成struct LNode* LinkList会更加直观。有了它，我们就可以方便的定义一个单链表L，本质上和next一样，都是指向结点的指针，这个理解很关键。

LinkList L;    //等价于 struct LNode * L

写法2：

//单链表存储定义
struct LNode{int data;//数据域struct LNode* next;//指针域：指向LNode的指针
};
typedef struct LNode LNode;
typedef struct LNode* LinkList;//指向LNode的指针

（2）头插法建立单链表【逆序】List_HeadInsert(LinkList &L)

注意：这里有一个易错点，由于这是带头节点的单链表，初始化空表后，其实有一个节点，只不过它指向NULL，开始误写为s->next=L;L->next=s，但这应该属于不带头节点的写法；

正确的应该是s->next=L-next;虽然此时L->next指向空，可能会感觉找不到谁赋值给s->next,但是这里可以把NULL虚拟的看成一个结点，如上图所示，就很好理解啦。在链表里有了结点后，其他结点的插入也是如此。且最后一个结点的next肯定是指向NULL的。

（3）尾插法建立单链表【正序】List_TailInsert(LinkList &L)

注意：1.尾插法增加表尾指针r的目的：改链时能知道上一个结点的地址；

2.表尾指针初始时指向L；每插入一个结点的数据后要及时更新表尾指针r；不再插入结点后，需要将尾指针置空。

3.对于r->next=s;r=s两句的理解：即不断在表尾插入结点，然后更新表尾指针，最后当不再插入数据时，需要将尾结点（r->next）置空哦！

（4）按序号查找结点值：GetElem(LinkList L,int i):从第1个接结点开始，沿着指针next域逐个往后搜索，直到找到第i个结点为止，否则返回最后一个结点指针域NULL.

 注：1.i无效的条件时i<1，不是i<0.

2.跳出循环的条件：要么p指针移动到表尾，p=NULL;要么j=i,找到第i个结点。

相关代码及运行截图：

#include <cstdlib>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <typeinfo>using namespace std;//单链表存储定义-写法1
typedef struct LNode{int data;//数据域struct LNode* next;//指针域：指向LNode的指针
}LNode,*LinkList;//头插法插入结点
LinkList List_HeadInsert(LinkList &L){LNode* s;//定义指向插入节点的指针、接收插入数据的变量int x;L=(LinkList)malloc(sizeof(LNode));//创建头节点L->next=NULL;//初始化为空表cin>>x;while(x!=10000){s=(LNode*)malloc(sizeof(LNode));s->data=x;s->next=L->next;//改链操作L->next=s;cin>>x;}return L;
}//尾插法插入节点
LinkList List_TailInsert(LinkList &L){int x;L=(LinkList)malloc(sizeof(LNode));LNode* s;LNode* r=L;//表尾指针指向LL->next=NULL;cin>>x;while(x!=9999){s=(LNode*)malloc(sizeof(LNode));s->data=x;s->next=NULL;r->next=s;r=s;cin>>x;}r->next=NULL;return L;
}int ListLength(LinkList &L){LNode* p;int j=0;p=L->next;while(p){p=p->next;j++;}return j;
}//按值查找表结点
LNode* GetElem(LinkList L,int i){int j=1;LNode* p=L->next;if(i==0)return L;if(i<1)return NULL;while(p&&j<i){p=p->next;j++;}return p;
}//顺序打印当前表中的数据
void Print(LinkList L){LNode* p;p=L->next;cout<<"当前表中的数据为："<<endl;while(p!=NULL){cout<<p->data<<" ";p=p->next;}
}int main(){LinkList L1,L2;//定义名为L1、L2的单链表cout<<"头插法插入结点，请输入数据：（输入10000结束）"<<endl;List_HeadInsert(L1);cout<<"L1当前的表长为："<<ListLength(L1)<<endl;Print(L1);cout<<endl;cout<<endl<<"尾插法插入结点，请输入数据：(输入9999结束)"<<endl;List_TailInsert(L2);cout<<"L2当前的表长为："<<ListLength(L2)<<endl;Print(L2);cout<<endl;cout<<endl<<"表L1的第2个结点的值为："<<GetElem(L1,2)->data<<endl;cout<<"表L2的第4个结点的值为："<<GetElem(L2,4)->data<<endl;}

运行截图：

（5）按值找表中节点 LocateElem(LinkList L,int e)

 

（6）插入节点 ListInsert(LinkList &L,int x,int i);将值为x的新结点插入到第i个位置上

注意：由于之前已有按照序号查找结点的函数GetElem(LinkList L,int i),直接调用找到第i个结点的前驱结点，即可快速进行改链操作。注意改链前，需要先创建结点，并用s保存结点地址，以存入数据，和后续进行改链操作

（7）删除节点

（8）求表长

 注意：求表长时，若p指向第一个结点，则计数变量j的初值为0

（1）~（8）完整代码及运行结果如下：

#include <cstdlib>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <typeinfo>using namespace std;//单链表存储定义-写法1
typedef struct LNode{int data;//数据域struct LNode* next;//指针域：指向LNode的指针
}LNode,*LinkList;//头插法插入结点
LinkList List_HeadInsert(LinkList &L){LNode* s;//定义指向插入节点的指针、接收插入数据的变量int x;L=(LinkList)malloc(sizeof(LNode));//创建头节点L->next=NULL;//初始化为空表cin>>x;while(x!=10000){s=(LNode*)malloc(sizeof(LNode));s->data=x;s->next=L->next;//改链操作L->next=s;cin>>x;}return L;
}//尾插法插入节点
LinkList List_TailInsert(LinkList &L){int x;L=(LinkList)malloc(sizeof(LNode));LNode* s;LNode* r=L;//表尾指针指向LL->next=NULL;cin>>x;while(x!=9999){s=(LNode*)malloc(sizeof(LNode));s->data=x;s->next=NULL;r->next=s;r=s;cin>>x;}r->next=NULL;return L;
}void ListLength(LinkList &L){LNode* p;int j=0;p=L->next;while(p){p=p->next;j++;}cout<<"表当前的长度为："<<j<<endl;//return j;
}//按序号查找表结点
LNode* GetElem(LinkList L,int i){int j=1;LNode* p=L->next;if(i==0)return L;if(i<1)return NULL;while(p&&j<i){p=p->next;j++;}return p;
}//顺序打印当前表中的数据
void Print(LinkList L){LNode* p;p=L->next;cout<<"当前表中的数据为："<<endl;while(p!=NULL){cout<<p->data<<" ";p=p->next;}cout<<endl;
}//按值查找表结点，并返回结点p
LNode* LocateElem(LinkList L,int e)
{LNode* p=L->next;//指向头节点while(p!=NULL&&p->data!=e){p=p->next;}return p;
}bool ListInsert(LinkList &L,int x,int i){LNode *p,*s;if(i<1)return false;p=GetElem(L,i-1);if(p==NULL)return false;s=(LNode*)malloc(sizeof(LNode));s->data=x;s->next=p->next;p->next=s;return true;
}int ListDelete(LinkList &L,int i){LNode *p,*q;int e;if(i<1)return -1;//i的范围不合法，则返回错误标志-1；p=GetElem(L, i-1);//p指向待删结点的前驱节点q=p->next;//q指向待删节点；e=q->data;//保存待删数据p->next=q->next;//改链操作free(q);//释放被删结点的存储空间return e;
}int main(){LinkList L1,L2;//定义名为L1、L2的单链表int e;cout<<"【1-头插法创建表L1】"<<endl;cout<<"头插法插入结点，请输入数据：（输入10000结束）"<<endl;List_HeadInsert(L1);ListLength(L1);Print(L1);cout<<endl<<"【2-尾插法创建表L2】"<<endl;cout<<"尾插法插入结点，请输入数据：(输入9999结束)"<<endl;List_TailInsert(L2);ListLength(L2);Print(L2);cout<<endl<<"【3-按照序号查找表结点的数据】"<<endl;cout<<"表L1的第2个结点的值为："<<GetElem(L1,2)->data<<endl;cout<<"表L2的第4个结点的值为："<<GetElem(L2,4)->data<<endl;cout<<endl<<"【4-按值查找结点】"<<endl;cout<<"请输入想要在L1中查找的数据：";cin>>e;cout<<"数据e的结点地址为:"<<LocateElem(L1,e)<<endl;cout<<"请输入想要在L2中查找的数据:";cin>>e;cout<<"数据e的结点地址为:"<<LocateElem(L2,e)<<endl;cout<<endl<<"【5-在表L第i个位置插入数据x】"<<endl;cout<<"在L1的第3个位置插入100"<<endl;ListInsert(L1,100,3);Print(L1);ListLength(L1);cout<<endl<<"在L2的第5个位置插入-999"<<endl;ListInsert(L2,-999,5);Print(L2);ListLength(L2);cout<<endl<<"【6-删除表L第i个位置的数据，并返回其数据值】"<<endl;cout<<"删除L1第2个位置的数据，其值为："<<ListDelete(L1,2)<<endl;Print(L1);ListLength(L1);cout<<"删除L2第2个位置的数据，其值为："<<ListDelete(L2,2)<<endl;Print(L2);ListLength(L2);
}

开始运行...
【1-头插法创建表L1】
头插法插入结点，请输入数据：（输入10000结束）
1 2 3 4 5 6 7 8 9 10000
表当前的长度为：9
当前表中的数据为：
9 8 7 6 5 4 3 2 1 

【2-尾插法创建表L2】
尾插法插入结点，请输入数据：(输入9999结束)
88 66 99 520 77 666 22 1314 9999
表当前的长度为：8
当前表中的数据为：
88 66 99 520 77 666 22 1314 

【3-按照序号查找表结点的数据】
表L1的第2个结点的值为：8
表L2的第4个结点的值为：520

【4-按值查找结点】
请输入想要在L1中查找的数据：7
数据e的结点地址为:0x1d087b0
请输入想要在L2中查找的数据:520
数据e的结点地址为:0x1d08890

【5-在表L第i个位置插入数据x】
在L1的第3个位置插入100
当前表中的数据为：
9 8 100 7 6 5 4 3 2 1 
表当前的长度为：10

在L2的第5个位置插入-999
当前表中的数据为：
88 66 99 520 -999 77 666 22 1314 
表当前的长度为：9

【6-删除表L第i个位置的数据，并返回其数据值】
删除L1第2个位置的数据，其值为：8
当前表中的数据为：
9 100 7 6 5 4 3 2 1 
表当前的长度为：9
删除L2第2个位置的数据，其值为：66
当前表中的数据为：
88 99 520 -999 77 666 22 1314 
表当前的长度为：8

运行结束。

2.双链表

1.双链表VS单链表最大不同：每个结点多了prior前驱指针域，优点主要是：使得找当前结点的前驱结点变得容易；不过在【插入】和【删除】的改链操作时，注意顺序和前驱链接；

2.【单链表】是【双链表】的基础，基于单链表，大约30min左右就可以快速构建起双链表的完整体系。其实就是一种【知识迁移】【融会贯通】【对比学习】的技能提升

• 用尾插法创建初始化的双链表；（包含头节点创建、尾指针指向和更新、结点插入）；
• 按照序号查找结点值；
• 利用前驱、后继指针访问当前结点的上一个数据、下一个数据；
• 常规操作：双链表中的结点插入；
• 常规操作：双链表中的结点删除；

#include <cstdlib>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <typeinfo>using namespace std;//测试用例：1 2 3 4 5 6 7 8 9 9999
//2 0
//4 0
//6 0typedef struct DNode{int data;//数据DNode *prior,*next;//前驱和后继指针；
}DNode,*DLinkList;
//等价于 typedef struct DNode DNode;
//等价于 typedef struct DNode* DLinkList;//尾插法创建初始双链表
DLinkList DList_TailInsert(DLinkList &DL){int x;DL=(DLinkList)malloc(sizeof(DLinkList));DNode* s;DNode* r=DL;//表尾指针指向LDL->next=NULL;cin>>x;while(x!=9999){s=(DNode*)malloc(sizeof(DNode));s->data=x;s->next=NULL;s->prior=r;//记得加上s的前驱r->next=s;r=s;cin>>x;}r->next=NULL;return DL;
}//按位置查找结点
DNode* GetElem(DLinkList DL,int i){int j=1;DNode *p=DL->next;if(i==0)return DL;if(i<1)return NULL;while(p&&j<i){p=p->next;j++;}return p;
}//双链表插入
bool DListInsert(DLinkList &DL,int i,int x){DNode *p,*s;if(i<1)return false;s=(DNode*)malloc(sizeof(DNode));s->data=x;p=GetElem(DL,i-1);s->next=p->next;p->next->prior=s;s->prior=p;p->next=s;return true;
}//顺序打印当前表中的数据
void Print(DLinkList DL){DNode* p;p=DL->next;cout<<"当前表中的数据为："<<endl;while(p!=NULL){cout<<p->data<<" ";p=p->next;}cout<<endl;
}int DListDelete(DLinkList &L,int i){DNode *p,*q;//p为待删的前驱结点，q为待删结点int e;if(i<1)return -1;//i的范围不合法，则返回错误标志-1；p=GetElem(L, i-1);//p指向待删结点的前驱节点q=p->next;//q指向待删节点；q->prior=p;e=q->data;//保存待删数据p->next=q->next;//改链操作q->next->prior=p;free(q);//释放被删结点的存储空间return e;
}int main()
{DLinkList DL;//创建名为DL的双链表；cout<<"【1-创建名为DL的双链表,输入9999结束】"<<endl;DList_TailInsert(DL);cout<<endl<<"【2-按序号查找DL中的数据】"<<endl;cout<<"第5个数据为："<<GetElem(DL,5)->data<<endl;cout<<endl<<"【3-用前驱、后继指针访问前后】"<<endl;cout<<"它的前一个数据为："<<GetElem(DL,5)->prior->data<<endl;cout<<"它的后一个数据为："<<GetElem(DL,5)->next->data<<endl;cout<<endl<<"【4-在DL的第i个位置插入x】"<<endl;int i,x;cout<<"输入i和x(空格分隔),输入-1停止插入：";cin>>i>>x;while(i!=-1){DListInsert(DL,i,x);cout<<"输入i和x(空格分隔)：";cin>>i;if(i!=-1)cin>>x;}Print(DL);cout<<endl<<"【5-删除DL第j个位置的数据】"<<endl;int j;cout<<"输入j(输入-1停止删除)：";cin>>j;cout<<"删除的数据为："<<DListDelete(DL,j)<<endl;Print(DL);while(j!=-1){cout<<"输入j：";cin>>j;cout<<"删除的数据为："<<DListDelete(DL,j)<<endl;Print(DL);}
}

运行结果：（不好截图，直接复制过来啦）

开始运行...
【1-创建名为DL的双链表,输入9999结束】
1 2 3 4 5 6 7 8 9 9999【2-按序号查找DL中的数据】
第5个数据为：5【3-用前驱、后继指针访问前后】
它的前一个数据为：4
它的后一个数据为：6【4-在DL的第i个位置插入x】
输入i和x(空格分隔),输入-1停止插入：2 0
输入i和x(空格分隔)：4 0
输入i和x(空格分隔)：6 0
输入i和x(空格分隔)：-1
当前表中的数据为：
1 0 2 0 3 0 4 5 6 7 8 9 【5-删除DL第j个位置的数据】
输入j(输入-1停止删除)：2
删除的数据为：0
当前表中的数据为：
1 2 0 3 0 4 5 6 7 8 9 
输入j：3
删除的数据为：0
当前表中的数据为：
1 2 3 0 4 5 6 7 8 9 
输入j：4
删除的数据为：0
当前表中的数据为：
1 2 3 4 5 6 7 8 9 
输入j：-1
删除的数据为：-1
当前表中的数据为：
1 2 3 4 5 6 7 8 9 运行结束。

耶！线性表这章终于结束啦！敲完代码感觉透透的啦！