线性表，作为大家学习数据结构的第一课，也是数据结构学习过程中的第一座大山，虽然数据结构就是一山连着一山。本文中的代码内容同时给出c、c++、java的版本，对于新手来说，c语言独特的结构可以更好地理解数据结构，而c++版本则更加适合竞赛，java版本则是由学Java的同学学习。新手也可以多看看其他语言，以便后面选择语言精通。（注：数据结构不挑语言，多数后端语言都有方式实现现在及后面所学的数据结构，另，由于java不适合结构化拆分，因此只在最后给出总代码及注释）
顺序表
顺序表，用一组地址连续的存储单元来存储数据元素。最常见的顺序表是我们的老朋友——数组。鉴于常用语言都有数组，所以无论是考试还是日常使用都直接用数组即可，因此我们对顺序表的教学止步于此。
链表
链表，用一组任意的存储单元存储数据元素。（您的第一难来了）
单向链表（单链表）
单链表中分为有无头结点两种，有头结点的单链表会方便使用很多，因此我们主要教这种。（如果你想找罪受也不是不可以反正除了难用其他都差不多）
基本操作
定义结点
C
//结点定义
typedef struct LNode{
//结点的数据域，一般结点要储存的数据都在这里定义，int可以替换成需要的数据类型，如char之类的
int data;
//结点的指针域，一般结点指针在这里定义。
struct LNode* next;
}LNode,*LinkList;//LinkList为指向结构体LNode的指针类型C++
//结点定义
typedef struct LNode{
//结点的数据域，一般结点要储存的数据都在这里定义，int可以替换成需要的数据类型，如char之类的
int data;
//结点的指针域
struct LNode* next;
//构造函数用于创建结点（初始化）
LNode(int x) :
//设置结点的值为x，设置结点的下一个结点为null
data(x), next(NULL){
}
};然后我们来看看链表的基本操作
初始化
C
//构造一个空的单链表(Status和OK不是c语言自带的，实际使用可以根据实际进行改变)
Status InitList(LinkList &L){
//生成的新结点作为头结点，用头指针L指向头节点
L = new LNode;
//头结点的指针域置空
L->next = NULL;
return OK;
}c++的初始化操作在上面的结点定义中已指出
取值
C
//在带头结点的单链表L中根据获取第i个数，用e返回该数
int* GetElem(LinkList L, int i, int &e){
//初始化，让头结点指向p
LNode* p = L->next;
//计数器j初值赋为1
int j = 1;
//顺链查找，知道p为空或p指向第i个元素
while(p && j < i)
{
//p指向下一结点
p = p -> next;
//计数器+1
++j;
}
//判断i值是否合法（-1有的时候会是我们要存到链表里的数，这个要选一个与需求无关的数来定义成失败，如：我们确定要存的是正数就可以用负数或0来赋予其失败的含义）
if(!p || j > i)
return -1;
//e即为第i个数
e = p -> data;
return e;
}C++
//在带头结点的单链表L中根据获取第i个数，用e返回该数
int* getElement(LNode* L, int i, int &e)
{
LNode* p = L->next;
int j = 1;
while (j != i && p != NULL)//当前结点不是目标结点，并且不为空时就继续搜索
{
j++;
p = p->next;
}
e = p -> data;
return p;//返回结果查找
C
//查找单链表中有没有i
LNode* LocateElem(LinkList L, int i)
{
//初始化
LinkList p = L -> next;
//顺链查找
while(p && p -> data != i){
//p指向下一结点
p = p -> next;
}
//返回i所在的地址
return p;
}C++
LNode* listLocate(LNode* L, int x)
{
LNode* p = L->next;//p初始指向首元素结点
while (p != NULL && p->data != x)//p指元素结点，又不是目标节点，继续搜索下一目标
{
p = p->next;
}
return p;插入
C
//在位置i插入e
void ListInsert(LinkList &L, int i, int e){
LinkList p = L;
int j = 0;
//将p挪到位置i的前一个结点
while(p && j < i-1){
p = p -> next;
++j;
}
//创建要插入的结点
LNode s;
s -> data = e;
//让新结点指向原来的i结点
s -> next = p -> next;
//让i-1结点指向新的i结点
p -> next = s;
}C++
bool listInsert(LNode* L, int i, int e)
{
LNode* p = L;//p指针指向头节点
LNode* S;
int j = 0;
//将p挪到位置i的前一个结点
while (j != i - 1 && p != NULL)
{
p = p->next;
j++;
}
if (p == NULL)
{
return false;//p为空指针，说明插入位置i无效，返回false
}
else
{
//此时，k=i-1，p为ei-1结点的指针
S = new LNode;//动态申请内存，创建一个新节点，即要插入的结点
S->data = e;
//让新结点指向原来的i结点
S->next = p->next;
//让i-1结点指向新的i结点
p->next = S;
return true;//正确插入返回true
}删除
C
//删除第i个元素
void ListInsert(LinkList &L, int i){
LinkList p = L;
int j = 0;
//将p挪到位置i的前一个结点
while(p && j < i-1){
p = p -> next;
++j;
}
//s指向要删除的元素
LNode s = p -> next;
//让i-1结点指向原来的i+1结点
p -> next = s -> next;
//删除i结点
delete s;
}C++
bool listInsert(LNode* L, int i, int e)
{
LNode* p = L;//p指针指向头节点
LNode* S;
int j = 0;
//将p挪到位置i的前一个结点
while (j != i - 1 && p != NULL)
{
p = p->next;
j++;
}
if (p == NULL)
{
return false;//p为空指针，说明插入位置i无效，返回false
}
else
{
//此时，p为i-1结点的指针
S = new LNode;//动态申请内存，创建一个新节点，即要插入的结点
S = p->next;//s指向要删除的元素
//让i-1结点指向原来的i+1结点
p->next = S->next;
//删除i结点
delete S;
return true;//正确插入返回true
}前插法创建单链表
C
void CreateList_H(LinkList &L, int n){
L = new LNode;
L->next = NULL;
for(i = 0; i < n; i++){
LinkList p;
scanf("%d", &p->data);
p->next = L->next;
L->next = p;
}
}C++
void createListH(LNode*& L)
{
LNode* u;
elementType x;//存放元素数值
L = new node;
L->next = NULL;
cout << "请输入元素数据（整数，9999退出）：" << endl;//以9999为例
cin >> x;
while (x != 9999)
{
u = new node;//动态申请内存，产生新结点
u->data = x;
u->next = L->next;//新结点链接到表头，使成为首元素结点
L->next = u;
cin >> x;//读入下一个键盘输入数据
}
}后插法创建单链表
C
void CreateList_R(LinkList &L, int n){
L = new LNode;
L->next = NULL;
LNode* r = L;
for(i = 0; i < n; ++i){
LinkList p;
scanf("%d", &p->data);
p->next = NULL;
r->next = p;
r = p;
}
}C++
void createList(LNode*& L)
{
int i, n;//n为结点个数，不含头结点
int x;//x为数据元素值
node* u, * R;//R为尾结点指针
L = new node;//产生头结点
L->next = NULL;//头结点的指针域为空
R = L;//设置尾指针
cout << "请输入元素结点个数（整数）" << endl;
cin >> n;
cout << "请输入元素数据（整数）" << endl;
for (i = n; i > 0; i--)
{
u = new node;//动态申请内存，产生新结点
cin >> x;
u->data = x;//元素数据装入新结点
u->next = NULL;
R->next = u;//新结点链接到表尾
R = u;
}
评论区