掌握链表的基本操作-建立、查找、插入和删除
问题遇到的现象和发生背景
基础操作：设计整数单链表的基本运算程序，并用相关数据进行测试
（1）输入一组长度不超过20的整数元素，使用头插法建立一个带头结点的单向链表
（2）遍历显示单链表，并显示单链表的长度
（3）显示第3个位置的值，显示链表中某个元素是第几个位置
（4）删除第4个位置元素，然后往第4个位置插入元素10，显示单链表
（5）根据上述数组使用尾插法建立一个带头结点的单链表，重复上述（2）、（3）、（4）操作
用代码块功能插入代码，请勿粘贴截图
有链表的基本操作，如建立、查找、插入和删除等基础源码，需要调用
我想要达到的结果
链表的基本操作，如建立、查找、插入和删除等基础源码
#include
#include
using namespace std;
typedef int ElemType;
typedef struct node
{ ElemType data; //数据域
struct node *next; //指针域
} SLinkNode; //单链表类型
void InitList(SLinkNode *&L) //初始化单链表L
{ L=(SLinkNode )malloc(sizeof(SLinkNode)); //创建头结点L
L->next=NULL;
}
void DestroyList(SLinkNode *&L) //销毁单链表L
{ SLinkNode *pre=L,*p=pre->next;
while (p!=NULL)
{ free(pre);
pre=p; p=p->next; //pre、p同步后移
}
free(pre);
}
int GetLength(SLinkNode *L) //求单链表L的长度
{ int i=0;
SLinkNode *p=L->next;
while (p!=NULL)
{ i++;
p=p->next;
}
return i;
}
int GetElem(SLinkNode *L,int i,ElemType &e) //求第i个结点值e
{ int j=0;
SLinkNode *p=L; //p指向头结点，计数器j置为0
if (i<=0) return 0; //参数i错误返回0
while (p!=NULL && j
{ j++;
p=p->next;
}
if (p==NULL)
return 0; //未找到返回0
else
{ e=p->data;
return 1; //找到后返回1
}
}
int Locate(SLinkNode *L,ElemType e) //求第一个值为e的结点的逻辑序号
{ SLinkNode *p=L->next;
int j=1; //p指向第一个数据结点，j置为其序号1
while (p!=NULL && p->data!=e)
{ p=p->next;
j++;
}
if (p==NULL) return(0); //未找到返回0
else return(j); //找到后返回其序号
}
int InsElem(SLinkNode &L,ElemType x,int i) //插入结点值为x的结点
{ int j=0;
SLinkNode p=L,s;
if (i<=0) return 0; //参数i错误返回0
while (p!=NULL && j
{ j++;
p=p->next;
}
if (p==NULL)
return 0; //未找到第i-1个结点时返回0
else //找到第i-1个结点
{ s=(SLinkNode )malloc(sizeof(SLinkNode));
s->data=x; //创建存放元素x的新结点s
s->next=p->next; //将s结点插入到p结点之后
p->next=s;
return 1; //插入运算成功,返回1
}
}
int DelElem(SLinkNode *&L,int i) //删除第i个结点
{ int j=0;
SLinkNode p=L,q;
if (i<=0) return 0; //参数i错误返回0
while (p!=NULL && j
{ j++;
p=p->next;
}
if (p==NULL)
return 0; //未找到第i-1个结点时返回0
else //找到第i-1个结点
{ q=p->next; //q指向被删结点
if (q==NULL)
return 0; //没有第i个结点时返回0
else
{ p->next=q->next; //从单链表中删除q结点
free(q); //释放其空间
return 1;
}
}
}
void DispList(SLinkNode *L) //输出单链表
{ SLinkNode *p=L->next;
while (p!=NULL)
{ printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
//采用头插法建表的算法
void CreateListF(SLinkNode *&L,ElemType a[],int n)
{ SLinkNode s; int i;
L=(SLinkNode )malloc(sizeof(SLinkNode)); //创建头结点
L->next=NULL; //头结点的next域置空，表示一个空单链表
for (i=0;i
{ s=(SLinkNode *)malloc(sizeof(SLinkNode));
s->data=a[i]; //创建存放a[i]元素的新结点
s->next=L->next; //将s插在头结点之后
L->next=s;
}
}
//采用尾插法建表的算法
void CreateListR(SLinkNode *&L,ElemType a[],int n)
{ SLinkNode s,tc; int i;
L=(SLinkNode )malloc(sizeof(SLinkNode)); //创建头结点
tc=L; //tc始终指向尾结点,开始时指向头结点
for (i=0;i
{ s=(SLinkNode *)malloc(sizeof(SLinkNode));
s->data=a[i]; //创建存放a[i]元素的新结点
tc->next=s; //将s插入tc之后
tc=s;
}
tc->next=NULL; //尾结点next域置为NULL
}
void basic_action()
{
}
void expand_action()
{
}
int main()
{
}
供参考：
#include <malloc.h>
#include <stdio.h>
//using namespace std;
typedef int ElemType;
typedef struct node
{
ElemType data; //数据域
struct node* next; //指针域
} SLinkNode; //单链表类型
void InitList(SLinkNode*& L) //初始化单链表L
{
L = (SLinkNode*)malloc(sizeof(SLinkNode)); //创建头结点L
L->next = NULL;
}
void DestroyList(SLinkNode*& L) //销毁单链表L
{
SLinkNode* pre = L, * p = pre->next;
while (p != NULL)
{
free(pre);
pre = p;
p = p->next; //pre、p同步后移
}
free(pre);
}
int GetLength(SLinkNode* L) //求单链表L的长度
{
int i = 0;
SLinkNode* p = L->next;
while (p != NULL)
{
i++;
p = p->next;
}
return i;
}
int GetElem(SLinkNode* L, int i, ElemType& e) //求第i个结点值e
{
int j = 0;
SLinkNode* p = L; //p指向头结点，计数器j置为0
if (i <= 0) return 0; //参数i错误返回0
while (p != NULL && j < i)
{
j++;
p = p->next;
}
if (p == NULL)
return 0; //未找到返回0
else
{
e = p->data;
return 1; //找到后返回1
}
}
int Locate(SLinkNode* L, ElemType e) //求第一个值为e的结点的逻辑序号
{
SLinkNode* p = L->next;
int j = 1; //p指向第一个数据结点，j置为其序号1
while (p != NULL && p->data != e)
{
p = p->next;
j++;
}
if (p == NULL) return(0); //未找到返回0
else return(j); //找到后返回其序号
}
int InsElem(SLinkNode*& L, ElemType x, int i) //插入结点值为x的结点
{
int j = 0;
SLinkNode* p = L, * s;
if (i <= 0) return 0; //参数i错误返回0
while (p != NULL && j < i - 1) //查找第i-1个结点*p
{
j++;
p = p->next;
}
if (p == NULL)
return 0; //未找到第i-1个结点时返回0
else //找到第i-1个结点p
{
s = (SLinkNode*)malloc(sizeof(SLinkNode));
s->data = x; //创建存放元素x的新结点s
s->next = p->next; //将s结点插入到p结点之后
p->next = s;
return 1; //插入运算成功,返回1
}
}
int DelElem(SLinkNode*& L, int i) //删除第i个结点
{
int j = 0;
SLinkNode* p = L, * q;
if (i <= 0) return 0; //参数i错误返回0
while (p != NULL && j < i - 1) //查找第i-1个结点
{
j++;
p = p->next;
}
if (p == NULL)
return 0; //未找到第i-1个结点时返回0
else //找到第i-1个结点p
{
q = p->next; //q指向被删结点
if (q == NULL)
return 0; //没有第i个结点时返回0
else
{
p->next = q->next; //从单链表中删除q结点
free(q); //释放其空间
return 1;
}
}
}
void DispList(SLinkNode* L) //输出单链表
{
SLinkNode* p = L->next;
while (p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
//采用头插法建表的算法
void CreateListF(SLinkNode*& L, ElemType a[], int n)
{
SLinkNode* s;
int i;
L = (SLinkNode*)malloc(sizeof(SLinkNode)); //创建头结点
L->next = NULL; //头结点的next域置空，表示一个空单链表
for (i = 0; i < n; i++) //遍历a数组所有元素
{
s = (SLinkNode*)malloc(sizeof(SLinkNode));
s->data = a[i]; //创建存放a[i]元素的新结点s
s->next = L->next; //将s插在头结点之后
L->next = s;
}
}
//采用尾插法建表的算法
void CreateListR(SLinkNode*& L, ElemType a[], int n)
{
SLinkNode* s, * tc;
int i;
L = (SLinkNode*)malloc(sizeof(SLinkNode)); //创建头结点
tc = L; //tc始终指向尾结点,开始时指向头结点
for (i = 0; i < n; i++)
{
s = (SLinkNode*)malloc(sizeof(SLinkNode));
s->data = a[i]; //创建存放a[i]元素的新结点s
tc->next = s; //将s插入tc之后
tc = s;
}
tc->next = NULL; //尾结点next域置为NULL
}
void basic_action()
{
;
}
void expand_action()
{
;
}
int main()
{
SLinkNode* L = NULL, * L1 = NULL;
ElemType n, a[20] = { 0 }, i, e;
scanf("%d", &n);
for (i = 0; i < n; i++)//（1）输入一组长度不超过20的整数元素
scanf("%d", &a[i]);
//***使用头插法建立一个带头结点的单链表***
CreateListF(L, a, n);//（1）使用头插法建立一个带头结点的单向链表
printf("L:");
DispList(L); //（2）显示单链表
printf("L的长度:%d\n", GetLength(L)); //（2）显示单链表的长度
i = 3;
GetElem(L, i, e);
printf("第%d个位置的值:%d\n", i, e); //（3）显示第3个位置的值
e = 5;
printf("元素%d的位置:%d\n", e, Locate(L, e));//（3）显示链表中某个元素是第几个位置
i = 4; e = 10;
DelElem(L, i); //（4）删除第4个位置元素
InsElem(L, e, i);//（4）往第4个位置插入元素10
printf("L:");
DispList(L); //（4）显示单链表
//***使用尾插法建立一个带头结点的单链表***
printf("\n");
CreateListR(L1, a, n);//（1）使用尾插法建立一个带头结点的单向链表
printf("L1:");
DispList(L1); //（2）显示单链表
printf("L1的长度:%d\n", GetLength(L1)); //（2）显示单链表的长度
i = 3;
GetElem(L1, i, e);
printf("第%d个位置的值:%d\n", i, e); //（3）显示第3个位置的值
e = 5;
printf("元素%d的位置:%d\n", e, Locate(L1, e));//（3）显示链表中某个元素是第几个位置
i = 4; e = 10;
DelElem(L1, i); //（4）删除第4个位置元素
InsElem(L1, e, i);//（4）往第4个位置插入元素10
printf("L1:");
DispList(L1); //（4）显示单链表
return 0;
}
- 这篇文章讲的很详细，请看：数据结构——堆的基本操作（堆的建立、插入、删除等）详解