• 更新中…

typedef struct LNode
{
ElemType data;
LNode *next;

{
if (!L)//存储分配失败
exit(OVERFLOW);
L->next = L;//指针域指向头结点
}
{
//销毁线性表
p = L->next;//p指向头结点
while (p != L)//没到表尾
{
q = p->next;
free(p);
p = q;
}
free(L);
L = NULL;
}
{
//将表置空
L = L->next;//L指向头结点
p = L->next;//p指向第一个结点
while (p != L)//没到表尾
{
q = p->next;
free(p);
p = q;
}
L->next = L;//头结点指针域指向自身
}
{
if (L->next == L)//空
return TRUE;
else
return FALSE;
}
{
int i = 0;
while (p != L)
{
i++;
p = p->next;
}
return i;
}
Status GetElem(LinkList L, int i, ElemType &e)
{
int j = 1;//初始化，j为计数器
if (i <= 0 || i > ListLength(L))//第i个元素不存在
return ERROR;
while (j<i)
{
p = p->next;
j++;
}
e = p->data;
return OK;
}
int LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType))
{
//返回L中第1个与e满足关系compare()的数据元素的位序
//若这样的元素不存在，则返回0
int i = 0;
while (p != L->next)
{
i++;
if (compare(p->data, e))
return i;
p = p->next;
}
return 0;
}
Status PriorElem(LinkList L, ElemType cur_e, ElemType &pre_e)
{
//若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义
q = p->next;
while (q != L->next)//p没到表尾
{
if (q->data == cur_e)
{
pre_e = p->data;
return TRUE;
}
p = q;
q = q->next;
}
return FALSE;//操作失败
}
Status NextElem(LinkList L, ElemType cur_e, ElemType &next_e)
{
//若cur_e是L的数据元素，且不说最后一个，则用next_e返回它的后继
//否则操作失败，next_e无定义
while (p != L)//p没到表尾
{
if (p->data == cur_e)
{
next_e = p->next->data;
return TRUE;
}
p = p->next;
}
return FALSE;
}
Status ListInsert(LinkList &L, int i, ElemType e)
{
//在L的第i个位置之前插入元素e
int j = 0;
if (i<0 || i>ListLength(L))
return ERROR;
while (j < i - 1)//寻找第i-1个结点
{
p = p->next;
j++;
}
s->data = e;
//插入L中
s->next = p->next;
p->next = s;
if (p == L)
{
L = s;
}
return OK;
}
Status ListDelete(LinkList &L, int i, ElemType &e)
{
//删除L的第i个元素，并由e返回其值
int j = 0;
if (i<0 || i>ListLength(L))
return ERROR;
while (j < i - 1)//寻找第i-1个结点
{
p = p->next;
j++;
}
q = p->next;//q指向待删除结点
e = q->data;
p->next = q->next;
if (L == q)
L = p;
free(q);
return OK;
}
{
//依次对L的每个数据元素调用函数vi()
while (p != L->next)//p不指向头结点
{
vi(p->data);
p = p->next;
}
printf("\n");
}

//两个仅设表尾指针的循环链表的合并
{
//将Lb合并到La的表尾，由La指示新表
Lb->next = La->next;
La->next = p->next;
free(p);
La = Lb;
}

展开全文
• 尾插法构建单链表，设置尾指针8.头插法构建单链表9.单链表长度，返回长度10.单链表按位查找，返回该节点11.单链表按值查找，返回该节点12.单链表在某一节点处插入13.单链表在某一位置处插入14.单链表删除某一结点15....

# 前言

上一节的动态分配内存的顺序表
前一篇文章，动态分配内存的顺序表

# 一、链表

链表的一种。一本文提供了一种带表头指针的单链表的简单实现。参考了数据结构（严蔚敏C语言版）教材。
有些判断输入是否合法的说明就跳过了，代码中可能没有体现，读者可以自行补充，
不带表头的指针的代码类似，由于带表头指针比较方便，所以就写了这个。
其中仍然是省略了部分判断输入合法性的操作，读者可以自行补全。部分函数为方便起见进行了简化，读者可以自行改写。
代码仅供参考，学习，
运行环境是Visual Studio 2019

# 二、代码部分

## 1.头文件

建立是cpp文件，用c文件也可以，只是需要改变一下读写数据的操作。

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
using namespace std;

## 2.预定义

预先定义一些内容，方便后续操作
这里追求方便，定义了ElemType为int类型，读者可以自己更改为其他类型。如果更改了，之后的判断是否相等需要重写，C++可以重载==运算符。

#define OK 1 //返回OK，代表操作成功
#define ERROR 0 //返回ERROR，代表操作失败
typedef int ElemType;  //之后出现的ElemType为int类型，本代码默认数据类型是int

## 3.定义存储结构

使用结构体定义了存储结构。
这里相当于
typedef struct Lnode Lnode;
这样两行代码，读者可以自行理解一下

typedef struct LNode
{
ElemType data;
struct LNode* next;

## 4.初始化带头结点的单链表

初始化需要给头结点分配内存空间，注意强制类型转换。
将头结点的next指向空即可。

{
L = (LNode*)malloc(sizeof(LNode));
if (L == NULL)
{
return false;
}
L->next = NULL;
return true;
}

## 5.判断是否为空

只需要看首元结点的next是不是NULL即可

{
if (L->next == NULL)
{
cout << "空链表" << endl;
return true;
}
else
{
cout << "不是空链表" << endl;
return false;
}
}

## 6.打印链表

很简单，判断一下是否是空表就行，不多做说明

{
cout << "单链表如下：" << endl;
LNode* p;
p = L->next;
if (p != NULL)
{
cout << p->data;
p = p->next;
}
else
{
return ERROR;
}
while (p != NULL)
{
cout << " " << p->data;
p = p->next;
}
cout << endl;
return OK;
}

## 7.尾插法构建单链表，设置尾指针

步骤1：尾指针r初始化，指向头结点
步骤2：根据链表的元素个数进行循环
1.生成新节点s；
2.输入元素值赋给新节点
s的数据域;
3.将新节点s插入到尾结点r之后
4尾指针r指向新的尾结点*s

{
int n;
cout << "请输入要插入元素的个数" << endl;
cin >> n;
cout << "请输入要插入的元素" << endl;
LNode* s, *r;
r = L;
for (int i = 0; i < n; i++)
{
s = (LNode*)malloc(sizeof(LNode)); //生成新节点
cin >> s->data;    //新节点数据域赋值
r->next = s;    //此时上一次的尾结点的下一个结点就是s
r = s; //s就是新的尾结点
}
r->next = NULL;
return OK;
}

## 8.头插法构建单链表

和尾插法类似，不过不需要设置尾指针
步骤1：根据链表的元素个数进行循环
1.生成新节点s；
2.输入元素值赋给新节点
s的数据域;
3.将新节点*s插入到头结点之前

{
LNode* s;
int n;
cout << "请输入要插入元素的个数" << endl;
cin >> n;
cout << "请输入要插入的元素" << endl;
for (int i = 0; i < n; i++)
{
s = (LNode*)malloc(sizeof(LNode)); //生成新节点
cin >> s->data;
s->next = L->next;
L->next = s;
}
return OK;
}

## 9.单链表长度，返回长度

很简单，相当于遍历一遍链表，但不输出

{
int count = 0;
while (p->next != NULL)
{
count++;
p = p->next;
}
return count;
}

## 10.单链表按位查找，返回该节点

利用循环找到位置，返回节点，不是很难。

{
LNode* p;
p = L->next;
int j = 1;
while (p != NULL && j < index)
{
p = p->next;
j++;
}
cout << "第" << index << "个元素是" << p->data << endl;
return p;
}

## 11.单链表按值查找，返回该节点

和遍历操作类似，不过需要在while循环里面加一个判断条件，找不到就返回NULL

{
LNode* p=L->next;
int j = 1;
while (p != NULL && p->data != e)
{
p = p->next;
j++;
}
if (p == NULL)
{
cout << "未找到" << endl;
}
else
{
cout << "值为" << e << "的结点为第" << j << "个" << endl;
}
return p;
}

## 12.单链表在某一节点处插入

注意输入的参数是结点的指针

int InsertNextNode(LinkList& L, LNode* p, ElemType e)
{
LNode* s = (LNode*)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}

## 13.单链表在某一位置处插入

复用了之前的代码，方便操作

int ListInsert(LinkList& L, int i, ElemType e)
{
LNode* p = GetElem(L, i - 1);
return InsertNextNode(L, p, e);
}

## 14.单链表删除某一结点

和插入操作类似，注意释放内存空间

{
LNode* q = p->next;
p->data = p->next->data;
p->next = q->next;
free(q);
return OK;
}

## 15.单链表删除某一位置的元素

和插入操作类似，注意释放内存空间

{
LNode* p = GetElem(L, i);
return DeleteNode(L, p);
}

## 16.单链表销毁

看看就好

{
if (!L)
{
cout << "表不存在" << endl;
return ERROR;
}
while (q != NULL) {     //当q结点不为空时一直进入循环
free(L);          //释放L结点
L = q;            //将q结点赋值给L结点
q = L->next;      //将q结点赋值给L结点以后使q结点指向L的下一个结点
}
free(L);    //此时q的值为NULL，L指向尾结点，将其释放
L = NULL;
}

## 17.主函数

测试用的

int main()
{
InitList(L);
IsEmpty(L);
PrintList(L);
cout << ListLength(L) << endl;
LNode* s=GetElem(L, 2);
cout << s->data << endl;
s = LocateElem(L, 3);
cout << s->data << endl;
ListInsert(L, 2, 4);
ListInsert(L, 2, 4);
PrintList(L);
ListDelete(L, 5);
PrintList(L);
return 0;
}

# 总结

只要理解了各个结点的指针变化就很简单了

展开全文
• c语言实现单链表 二级指针单链表的使用

## c语言实现单链表

用C语言实现链表的头插，头删，尾插，尾删，查找节点，任意节点插入，和任意节点删除等功能
此代码运用的是二级指针实现单链表，所以在写代码时要注意参数类型。

### 关于二级指针和一级指针：

一级指针变量指向的内容是普通变量的值，二级指针变量指向的内容是一级指针变量的地址。
当你想对一个地址做修改的时候，就要用到二级指针。

### 完整代码

#define __CRT_SECURE_NO_WARNRINGS 1
#include "slist.h"

//初始化链表
assert(ppList);
*ppList = NULL;
}
//打印链表
void PrintList(ListNode* pList){
ListNode* cur = pList;
while (cur){
printf("%d ", cur->data);
cur= cur->next;
}
printf("\n");
return;
}
//申请一个新节点
ListNode* newNode = NULL;
newNode = (ListNode*)malloc(sizeof(ListNode));//开辟新节点，强制类型转换
if (newNode == NULL){
printf("out of memory \n");//溢出
}
else{
newNode->data = x;
newNode->next = NULL;
}
return newNode;
}
//尾插
void PushBack(ListNode** ppList, DataType x){
assert(ppList);
if (*ppList == NULL){
}
else{
ListNode* ppcur = NULL;
ppcur = *ppList;
while (ppcur->next)
{
ppcur = ppcur->next;
}
}
}
//尾删
void PopBack(ListNode** ppList){
assert(ppList);
ListNode* cur = *ppList;
if (cur == NULL){
return ;
}
if (cur->next==NULL){
free(cur);
cur = NULL;
}
else{
while (cur->next->next){
cur = cur->next;
}
free(cur->next);
cur->next = NULL;
}
}
//头插
void PushFront(ListNode** ppList, DataType x){
assert(ppList);
ListNode* pFirst=NULL;
if (*ppList==NULL){
}
else{
pFirst->next = *ppList;
*ppList = pFirst;
}
}
//头删
void PopFront(ListNode** ppList){
assert(ppList);
if (*ppList == NULL){
return;
}
else{
ListNode* cur = *ppList;
*ppList = (*ppList)->next;
free(cur);
cur = NULL;
}

}
//查找表中元素x
ListNode* Find(ListNode* pList, DataType x){
assert(pList);
ListNode* cur = pList;
//if (cur == NULL){
//  return ;
//}
while (cur){
if (cur->data == x)
break;
cur = cur->next;
}
return cur;
}

// 在pos的前面插入一个节点x
void Insert(ListNode** ppList, ListNode* pos, DataType x){
assert(ppList);
assert(pos);
DataType tmp=0;
if (*ppList == NULL){
PushBack(ppList, x);
}
else if (pos == NULL){
return;
}
else{
newnode->next =pos->next;
pos->next = newnode;
tmp = pos->data;
pos->data = newnode->data;
newnode->data = tmp;
}
}
//删除pos前一位置节点
void Erase(ListNode** ppList, ListNode* pos){
assert(ppList);
assert(pos);
ListNode* cur = *ppList;
if (cur == NULL){
return;
}
else{
while (cur->next!=pos&&cur){
cur = cur->next;
}
cur->next = pos->next;
free(pos);
pos = NULL;
}
}

测试函数

#include "slist.h"
//测试

void test1()
{
ListNode *list;
printf("插入数据\n");
PushBack(&list, 1);
PushBack(&list, 2);
PushBack(&list, 3);
PushBack(&list, 4);
PushBack(&list, 5);
PushBack(&list, 6);
PrintList(list);
printf("从尾部删除数据后\n");
PopBack(&list);
PopBack(&list);
PrintList(list);
ListNode* _find;
_find=Find(list, 2);
printf("找到节点pos：%d\n", _find->data);
ListNode* pos = _find;
printf("在pos前插入节点:\n");
Insert(&list,pos, 7);
PrintList(list);
printf("删除pos前节点:\n");
Erase(&list, pos);
PrintList(list);
}
void test2()
{
ListNode* List;
printf("头插数据\n");
PushFront(&List, 1);
PushFront(&List, 2);
PushFront(&List, 3);
PushFront(&List, 4);
PrintList(List);
printf("头删数据后");
PopFront(&List);
PopFront(&List);
PopFront(&List);
PopFront(&List);
PrintList(List);

}
int main()
{

test1();
//test2();
system("pause");
return 0;
}

头文件

#define __CRT_SECURE_NO_WARNRINGS 1
#ifndef __SLIST_H__
#define __SLIST_H__
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int DataType;
typedef struct ListNode
{
DataType data;
struct ListNode* next;
}ListNode;

void PrintList(ListNode* pList);
void PushBack(ListNode** ppList, DataType x);
void PopBack(ListNode** ppList);
void PushFront(ListNode** ppList, DataType x);
void PopFront(ListNode** ppList);
ListNode* Find(ListNode* pList, DataType x);

// 在pos的前面插入一个节点x
void Insert(ListNode** ppList, ListNode* pos, DataType x);
void Erase(ListNode** ppList, ListNode* pos);

#endif //__SLIST_H__

### 测试结果：

test1:

test2:

展开全文
• 尾指针循环单链表带尾指针循环单链表基本操作定义存储结构类型尾插法创建带尾指针循环单链表头插法创建带尾指针循环单链表将两个带尾指针循环单链表合并遍历尾指针循环单链表测试代码 带尾指针循环单链表基本操作 ...

## 带尾指针循环单链表基本操作

### 定义存储结构类型

typedef struct LNode
{
int data;
struct LNode *next;

### 尾插法创建带尾指针循环单链表

//尾插法
{
LNode *p,*q;   //p是指向头结点指针  q是指向新节点指针
int i;
p = q = (LinkList)malloc(sizeof(LNode));   //为头结点开辟空间，并让p、q同时指向它
printf("为单链表输入%d个元素：",n);
for(i=0;i<n;i++)
{
q = q->next;   //q指针向前移，指向新结点
scanf("%d",&q->data);
q->next = p;    //新结点next指向头结点，形成一个循环
*L = q;      //尾指针指向新结点，直至链尾
}
}

### 头插法创建带尾指针循环单链表

//头插法
{
int i;
printf("为单链表输入%d个元素：",n);
scanf("%d",&((*LTail)->data));   //为尾结点输入数据
for(i=0;i<n-1;i++)
{
scanf("%d",&tmp_node->data);
}
}

### 将两个带尾指针循环单链表合并

{
LNode *tmp_node = La->next;     //先保存La链头结点指针
La->next = Lb->next->next;      //La链尾 连接Lb链首元结点
free(Lb->next);            //释放Lb链内存单元
Lb->next = tmp_node;           //与上一步不能颠倒，将Lb链连接La链头结点
}

### 遍历尾指针循环单链表

//遍历
{
if(head == L) return ERROR;   //空链表(即当前头结点next域指向自己)  返回ERROR
{
}
return OK;
}

### 测试代码

#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0

typedef int Status;

typedef struct LNode
{
int data;
struct LNode *next;

//尾插法
{
LNode *p,*q;   //p是指向头结点指针  q是指向新节点指针
int i;
p = q = (LinkList)malloc(sizeof(LNode));   //为头结点开辟空间，并让p、q同时指向它
printf("为单链表输入%d个元素：",n);
for(i=0;i<n;i++)
{
q = q->next;   //q指针向前移，指向新结点
scanf("%d",&q->data);
q->next = p;    //新结点next指向头结点，形成一个循环
*L = q;      //尾指针指向新结点，直至链尾
}
}

//头插法
{
int i;
printf("为单链表输入%d个元素：",n);
scanf("%d",&((*LTail)->data));   //为尾结点输入数据
for(i=0;i<n-1;i++)
{
scanf("%d",&tmp_node->data);
}
}

//遍历
{
if(head == L) return ERROR;   //空链表(即当前头结点next域指向自己)  返回ERROR
{
}
return OK;
}

//合并
{
LNode *tmp_node = La->next;     //先保存La链头结点指针
La->next = Lb->next->next;      //La链尾 连接Lb链首元结点
free(Lb->next);            //释放Lb链内存单元
Lb->next = tmp_node;           //与上一步不能颠倒，将Lb链连接La链头结点
}

int main()
{
printf("------尾插法录入数据-------\n");
CreateList_R(&La,3);
printf("当前La链: ");
print(La);
printf("\n");
printf("------头插法录入数据-------\n");
CreateList_H(&Lb,4);
printf("当前Lb链: ");
print(Lb);
printf("\n");
printf("----带尾指针循环链表合并-----\n");
Union(La,Lb);
printf("当前合链: ");
print(Lb);
}

展开全文
• 在VC6.0环境下实现了使用尾指针创建循环单链表，输出第一个和最后一个节点的值
• 利用尾指针连接两个单链表
• 问题：假设一个没有指针单链表。一个指针指向此单链表中间的一个节点（既不是第一个，也不是最后一个节点），请将该节点从单链表中删除。 p->data = p->next->data; p->next = p->next->next; firee(p-...
• 单链表的头指针、头节点与节点 头指针为NULL时，则该单链表为空链表；等于在内存中没有分配节点内存。 链表从头节点开始存储数据。节点同样数据，但指向下一节点的地址为空。 下面从头到尾打印单链表的值的...
• 这里可以两种方法做： 1.头插法且双指针 2.改变指针指向且三指针 两方法共同点： 头结点还是作为头结点。第一个结点作为节点。 单链表的存储结构： typedef struct LinkList{ int data; LinkList * next; } ...
• 在上篇博客 数据结构与算法：单链表（超详细实现）中用C语言实现了单链表的相关算法，不过却局限性 只能针对某一种数据类型还是不够强大。C语言中没有C++中的模板 那如何来实现 类似模板的效果呢？可以针对任意...
• 问题：设一个没有头结点指针单链表。一个指针指向此单链表中间的一个结点（不是第一个，也不是最后一个结点），将该结点从单链表中删除，要求时间复杂度O（1） &nbsp; &nbsp; &nbsp; &nbsp;...
• 问题描述：假设一个没有指针单链表。一个指针指向此单链表中间的一个节点（不是第一个，也不是最后一个节点），请将该节点从单链表中删除。一般链表的删除需要顺着头结点向下找到当前待删节点的前驱节点，然后...
• 删除一个单链表的非结点，并且不能遍历链表，所以我们可以尝试删除其他结点以代替此节点，在这里，我们用要删除的结点的下一个结点来代替此节点，删除下一个结点之前，先将这个节点保存起来，再把此结点的值域和...
• 1.删除一个无头单链表的非节点 2.从到头打印单链表首先，给出节点信息#include #include <cassert>typedef int DataType; typedef struct ListNode { DataType _val; ListNode* _pNext; }Node, *PNode; 1....
• 单链表实现如下功能： void InitList(List *list); //初始化单链表 bool push_back(List *list,ElemType x); //尾插法 void show_seqlist(List *list); //显示链表内容 bool push_front(List *list,ElemType x);//...
• 1.删除一个无头单链表的非节点，时间复杂度为...一个链表的每个节点，一个指向next指针指向下一个节点，还有一个random指针指向这个链表中的一个随机节点或者NULL，现在要求实现复制这个链表，返回复制后的新链表。
• 我这里使用带头尾指针单链表来模拟队列的功能，采用这种方法较为方便，其入队出队操作可以分别使用单链表的尾插，头删（或者头插，尾删）来实现。先看结点和队列的结构体定义： typedef int Qdatatype; //结点 ...
• 两个循环单链表,链表头指针分别为h1和h2,编写一个函数将链表h2链接到链表h1之后,要求链接后的链表仍保持循环链表形式 #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef struct ...
• 删除一个无头单链表的非节点
• 18,两个循环单链表,链表头指针分别为h1和h2,编写一个函数将链表h2链接到链表h1之后,要求链接后的链表仍保持循环链表形式。 思路：两个链表都找到最后一个节点，然后再链接 #include<iostream> #...
• ## 单链表双指针实现

千次阅读 2015-05-20 20:14:46
单链表的实现思想和双指针的应用方法在前面博客中都已阐述，在本文将实现双指针实现单链表的初始化，插入，删除，打印。 【测试代码1】#include #include<stdlib.h>typedef struct Node{ int data; struct Node *...
• //初始化以尾指针表示的循环单链表 int ListInit(LinkList &L){ L=new Lnode; if(!L) exit(ERROR); L->next=L; return OK; } //头插法建立以尾指针表示的循环单链表 void HCreatInsert(LinkList &L,int n){ Lnode *...
• ——因为如果是带头节点的单链表，假设要删除的是第一个节点，头节点是没有数据域的只有指针域，因此要想使用以下的方法就不能实现。 算法思想 我的代码 #include<iostream> using namespace std; ...
• 到头打印单链表 1.将所有节点压如栈中，利用栈的先进后出原则来实现 2.也可以用递归来实现 struct ListNode { int _value; ListNode* _pNext; };void ReversePrintfList(ListNode* pHead) { std::stack*> ...
• //L1接到L2头,L2接到L1头 LinkList* p1 = L1->next; LinkList* p2 = L2->next; while(p1->next!=L1) p1 = p1->next; p1->next = L2;//L1接到L2头节点 while(p2->next!=L2