目录
- 前言
- 一、链表的定义
- 二、链表的 C 语言描述
- 三、链表中基本操作的实现
- 3.1构造一个带头结点的空链表
- 3.2取第i个数据元素
- 3.3在链表中查找值为e的元素
- 3.3.1返回值类型是节点的地址
- 3.3.2返回值类型是节点的位置(序号)
- 3.4在第i位插入数据元素
- 3.5删除第i个数据元素
- 3.6 前插建立具有n的元素链表
- 3.7尾插建立具有n的元素链表
- 3.8线性表置空
- 3.9销毁链表
- 3.10判断链表是否为空
- 3.11求链表的表长
- 3.12遍历链表
- 四、链表代码实现
- 五、测试结果
- 六、总结
- 带有头结点的链表的基本操作
链表是一种动态分配空间的存储结构，能更有效地利用存储空间，通过对单链表基本操作的代码实现，我深刻领悟到以“指针”指示元素的后继，在插入或删除元素时不需要移动元素。但是与此同时，由于链表是“顺序存取”的结构，给随机存取元素和在表尾插入等操作带来不便。，所以接下来我将学习尾指针表示的单链表，双向链表以及循环链表等。
前言
本文参考王卓老师的数据结构视频和严蔚敏老师的《数据结构》
一、链表的定义
用一组地址任意的存储单元存放线性表中的数据元素。
结点 = 数据元素+指针(指后继元素存储位置)
二、链表的 C 语言描述
代码如下（示例）：
//带头结点的单链表
typedef struct LNode {
int data;
struct LNode* next;
}Lnode,*LinkList;
三、链表中基本操作的实现
3.1构造一个带头结点的空链表
c++中用new来动态的开辟空间，而c中则是用malloc来开辟空间
我使用new来动态开辟空间
注意:参数是引用型的
代码如下(示例):
void InitList(LinkList& L)
{
L = new Lnode;//L=(LinkList)malloc(sizeof(LNode))
L->next = NULL;
}
3.2取第i个数据元素
结束条件：链表走到空或者i的大小不对，比1小
则while语句判断条件为：while(p&&j<i) p表示当前节点不为空，j<i表示传进来的i是正确的，并且到该点
当此时p为空或者j>i，则返回0，表示未找到
否则把此时节点的data传给引用型参数data，并返回1
代码如下(示例):
int GetElem_L(LinkList L, int i, int& data)
{
int j = 1;
Lnode* p;
p = L->next;
while (p && j < i)
{
p = p->next;
j++;
}
if (!p || j > i) return 0;
data = p->data;
return 1;
}
3.3在链表中查找值为e的元素
时间效率分析：查找次数与位置有关，O(n)
注意，可以按照具体情况来写函数的返回值类型
比如，返回值类型可以是节点的地址，也可以是节点的位置
3.3.1返回值类型是节点的地址
代码如下(示例):
Lnode* LocationElem(LinkList L, int e)
{
Lnode* p = L->next;
while (p && p->data != e)
{
p = p->next;
}
return p;
}
3.3.2返回值类型是节点的位置(序号)
代码如下(示例):
int LocateElem_L(LinkList L, int e)
{
int j = 1;
Lnode* p = L->next;
while (p && p->data != e)
{
p = p->next;
j++;
}
if (p) return j;
else return 0;
}
3.4在第i位插入数据元素
修改指针的时间O(1),但是不知道插在哪里，所以需要查找，查找时间O(n)
代码如下(示例):
void ListInsert_L(LinkList& L, int i, int e)
{
int j = 0;
Lnode* p = L;
while (p && j < i - 1)//即找到i-1的位置
{
p = p->next;
j++;
}
if (!p || j > i - 1)
{
printf("i值错误,i小于1或大于表长\n");
return;
}
Lnode* s = new Lnode;
s->data = e;
s->next = NULL;
s->next = p->next;
p->next = s;//注意两行不能调换位置，否则s指向自己，错误
printf("插入成功\n");
}
3.5删除第i个数据元素
修改指针的时间O(1),但是不知道删除位置，所以需要查找，查找时间O(n)
代码如下(示例):
void ListDelete(LinkList& L, int i, int& e)
{
Lnode* p = L,*q;
int j = 0;
while (p->next && j < i - 1)//找到i-1的节点
{
p = p->next;
j++;
}
if (!(p->next) || j > i - 1)
{
printf("未找到要删除的节点\n");
return;
}
q = p->next;
e = q->data;
p->next = q->next;
delete q;//释放空间
printf("成功删除\n");
}
3.6 前插建立具有n的元素链表
时间复杂度：O(n)
逆序输入
确保结果与想要的是一致的（与尾插结果一致）
代码如下(示例):
void CreateList_F(LinkList& L, int t[],int n)
{
//创建n个节点
L = new Lnode;
L->next = NULL;
for(int i=n-1;i>=0;i--)
{
Lnode* p =new Lnode;
p->data=t[i];
p->next = L->next;
L->next = p;
}
}
3.7尾插建立具有n的元素链表
正序输入
时间复杂度：O(n)
代码如下(示例):
void CreateList_L(LinkList& L,int a[],int n)
{
//尾指针指向尾节点
L = new Lnode;
L->next = NULL;
Lnode* r = L;//尾指针，开始也指向头节点
for (int i = 0; i < n; i++)
{
Lnode* p = new Lnode;
p->data=a[i];
p->next = NULL;
r->next = p;
r = p;//把尾指针更新到新节点的位置
}
}
3.8线性表置空
从首元节点开始删除，保存了头指针和头节点
头节点的next赋值为空
代码如下(示例):
void CleanList(LinkList& L)
{
Lnode* p = L->next;
Lnode* q;
while (p)
{
q = p->next;
delete p;
p = q;
}
L->next = NULL;
}
3.9销毁链表
所有节点，包括头节点也删掉
代码如下(示例):
void DestoryList(LinkList& L)
{
Lnode* p;
while (L)
{
p = L;
L = L->next;
delete p;
}
}
3.10判断链表是否为空
头节点和头指针还在算空表，返回1
当头节点的next值不为空，即起码有个首元节点，则不算空表，返回0
代码如下(示例):
int isEmpty(LinkList L)
{
if (L->next == NULL)
return 1;
return 0;
}
3.11求链表的表长
用一个int型的length来计算，在循环中，当tmp未走到空的时候，每次都加1
代码如下(示例):
int ListLength(LinkList L)
{
Lnode* tmp = L->next;
int length = 0;
while (tmp != NULL)
{
length++;
tmp = tmp->next;
}
return length;
}
3.12遍历链表
当链表未走到空的时候，依次把所有节点的数据都输出
代码如下(示例):
void ListTraverse(LinkList L)
{
Lnode *tmp=L->next;
int i=0;
while(tmp!=NULL)
{
cout<<"第"<<i+1<<"个元素的数据:"<<tmp->data<<endl;
i++;
tmp=tmp->next;
}
}
四、链表代码实现
代码如下(示例):
#include <iostream>
using namespace std;
const int N=101;
//带头结点的单链表
typedef struct LNode {
int data;
struct LNode* next;
}Lnode,*LinkList;
//链表初始化
//构造一个带头结点的空链表
void InitList(LinkList& L)
{
L = new Lnode;//L=(LinkList)malloc(sizeof(LNode))
L->next = NULL;
}
//判断链表是否为空
//头节点和头指针还在（空表）
int isEmpty(LinkList L)
{
if (L->next == NULL)
return 1;
return 0;
}
//销毁链表
//所有节点，包括头节点也删掉
void DestoryList(LinkList& L)
{
Lnode* p;
while (L)
{
p = L;
L = L->next;
delete p;
}
}
//清空单链表
//清空元素,从首元节点开始删除
void CleanList(LinkList& L)
{
Lnode* p = L->next;
Lnode* q;
while (p)
{
q = p->next;
delete p;
p = q;
}
L->next = NULL;
}
//求链表的表长
int ListLength(LinkList L)
{
Lnode* tmp = L->next;
int length = 0;
while (tmp != NULL)
{
length++;
tmp = tmp->next;
}
return length;
}
//求第i个元素的值
int GetElem_L(LinkList L, int i, int& data)
{
int j = 1;
Lnode* p;
p = L->next;
while (p && j < i)
{
p = p->next;
j++;
}
if (!p || j > i) return 0;
data = p->data;
return 1;
}
//按值查找 返回地址
//时间效率分析：查找次数与位置有关，O(n)
Lnode* LocationElem(LinkList L, int e)
{
Lnode* p = L->next;
while (p && p->data != e)
{
p = p->next;
}
return p;
}
//按值查找，返回位置序号
int LocateElem_L(LinkList L, int e)
{
int j = 1;
Lnode* p = L->next;
while (p && p->data != e)
{
p = p->next;
j++;
}
if (p) return j;
else return 0;
}
//在第i个元素之前插入值为e的节点
//修改指针的时间O(1),但是不知道插在哪里，所以需要查找，查找时间O(n)
void ListInsert_L(LinkList& L, int i, int e)
{
int j = 0;
Lnode* p = L;
while (p && j < i - 1)//即找到i-1的位置
{
p = p->next;
j++;
}
if (!p || j > i - 1)
{
printf("i值错误,i小于1或大于表长\n");
return;
}
Lnode* s = new Lnode;
s->data = e;
s->next = NULL;
s->next = p->next;
p->next = s;//注意两行不能调换位置，否则s指向自己，错误
printf("插入成功\n");
}
//删除 删除第i个节点
//修改指针的时间O(1),但是不知道删除位置，所以需要查找，查找时间O(n)
void ListDelete(LinkList& L, int i, int& e)
{
Lnode* p = L,*q;
int j = 0;
while (p->next && j < i - 1)//找到i-1的节点
{
p = p->next;
j++;
}
if (!(p->next) || j > i - 1)
{
printf("未找到要删除的节点\n");
return;
}
q = p->next;
e = q->data;
p->next = q->next;
delete q;//释放空间
printf("成功删除\n");
}
//头插法建立单链表 时间复杂度：O(n) 逆序输入
void CreateList_F(LinkList& L, int t[],int n)
{
//创建n个节点
L = new Lnode;
L->next = NULL;
for(int i=n-1;i>=0;i--)
{
Lnode* p =new Lnode;
p->data=t[i];
p->next = L->next;
L->next = p;
}
}
//尾插法 正序输入 时间复杂度：O(n)
void CreateList_L(LinkList& L,int a[],int n)
{
//尾指针指向尾节点
L = new Lnode;
L->next = NULL;
Lnode* r = L;//尾指针，开始也指向头节点
for (int i = 0; i < n; i++)
{
Lnode* p = new Lnode;
p->data=a[i];
p->next = NULL;
r->next = p;
r = p;//把尾指针更新到新节点的位置
}
}
//遍历
void ListTraverse(LinkList L)
{
Lnode *tmp=L->next;
int i=0;
while(tmp!=NULL)
{
cout<<"第"<<i+1<<"个元素的数据:"<<tmp->data<<endl;
i++;
tmp=tmp->next;
}
}
void menu()
{
cout<<"*******************************************"<<endl;
cout<<"1.构造一个带头结点的空链表 "<<endl;
cout<<"2.建立具有n的元素链表"<<endl;
cout<<"3.取第i个数据元素"<<endl;
cout<<"4.在链表中查找值为e的元素"<<endl;
cout<<"5.在第i位插入数据元素"<<endl;
cout<<"6.删除第i个数据元素"<<endl;
cout<<"7.求链表的表长"<<endl;
cout<<"8.判断链表是否为空"<<endl;
cout<<"9.清空链表"<<endl;
cout<<"10.销毁链表"<<endl;
cout<<"11.遍历链表"<<endl;
cout<<"12.退出"<<endl;
cout<<"*******************************************"<<endl;
}
int main()
{
int choice;
LinkList L;
int i2,e2,e,i1,e1;
int t,n,x1;
int x,data;
while(1)
{
menu();
cout<<"请输入你的选择"<<endl;
cin>>choice;
switch(choice)
{
case 1:
InitList(L);
cout<<"成功初始化"<<endl;
break;
case 2:
cout<<"请选择你想要创建链表的方法"<<endl;
cout<<"1.是头插法\t2.是尾插法"<<endl;
cin>>t;
if(t==1)
{
int a1[N];
cout<<"请输入需要多少个节点"<<endl;
cin>>n;
for(int i=0;i<n;i++)
{
cout<<"请输入第"<<i+1<<"个节点的数据"<<endl;
cin>>a1[i];
}
CreateList_F(L,a1,n);
}
else
{
int a2[N];
cout<<"请输入需要多少个节点"<<endl;
cin>>n;
for(int i=0;i<n;i++)
{
cout<<"请输入第"<<i+1<<"个节点的数据"<<endl;
cin>>a2[i];
}
CreateList_L(L,a2,n);
}
break;
case 3:
cout<<"输入要查找的位置"<<endl;
cin>>x;
GetElem_L(L,x,data);
cout<<"第"<<x+1<<"个元素的值为："<<data<<endl;
break;
case 4:
cout<<"输入值"<<endl;
cin>>e;
x1=LocateElem_L(L,e);
cout<<"位置为："<<x1<<endl;
break;
case 5:
cout<<"请输入要插入哪里跟节点的数据"<<endl;
cin>>i1>>e1;
ListInsert_L(L,i1,e1);
break;
case 6:
cout<<"请输入要删除哪个节点"<<endl;
cin>>i2;
ListDelete(L,i2,e2);
cout<<"删除成功，原来的节点的数据为"<<e2<<endl;
break;
case 7:
cout<<"长度为"<<ListLength(L)<<endl;
break;
case 8:
if(isEmpty(L)) cout<<"链表为空"<<endl;
else cout<<"链表不为空"<<endl;
break;
case 9:
CleanList(L);
cout<<"清空成功"<<endl;
break;
case 10:
DestoryList(L);
cout<<"销毁成功"<<endl;
break;
case 11:
ListTraverse(L);
break;
case 12:
cout<<"成功退出"<<endl;
exit(0);
default:
cout<<"请重新输入"<<endl;
break;
}
}
}
五、测试结果
测试样例：创建4个节点 数据分别为1、2、3、4 其余测试基于以上4个节点
图一
图二
图三
图四
图五
图六
图七
图八
图九
图十
图11
图十二
六、总结
链表是一种动态分配空间的存储结构，能更有效地利用存储空间，通过对单链表基本操作的代码实现，我深刻领悟到以“指针”指示元素的后继，在插入或删除元素时不需要移动元素。但是与此同时，由于链表是“顺序存取”的结构，给随机存取元素和在表尾插入等操作带来不便。，所以接下来我将学习尾指针表示的单链表，双向链表以及循环链表等。
带有头结点的链表的基本操作
#ifndef _LIST_h_
#define _LIST_h_
//链表中的数据结构
typedef struct Link_data
{
int a;
int b;
}Node_data;
//链表节点结构
typedef struct Link_node
{
Node_data data;
struct Link_node *pNext;
}Node;
Node* CreateList(void);
Node* FindNodeByGlobalIndex(Node *pHead, int iGlobalIndex);
Node* Insert2ListTail(Node *pHead, Node_data *pAutoInfo);
int RemoveList(Node *pHead);
void PrintList(Node *pHead);
int DeleteList (Node *pHead,int x);
void ReverseList(Node *pHead);
void SortList(Node *pHead);
#endif
#include <string.h>
#include <malloc.h>
#include<stdio.h>
#include"list.h"
/*************************************************
Function : CreateList
Description : 创建链表头节点
Return : 链表的头指针
*************************************************/
Node* CreateList(void)
{
Node *pHead = NULL;
//申请的头指针
pHead = (Node *)malloc(sizeof(Node));
//判断是否申请成功
if (NULL == pHead)
{
return NULL;
}
//针对具体结构进行初始化
pHead->data.a = 0;
pHead->data.b = 0;
pHead->pNext = NULL;
return pHead;
}
/*************************************************
Function : FindNodeByGlobalIndex
Description : 根据指定参数，查找某个节点
Input : pHead 链表的头节点指针
要查找的学生ID
Return : 正确:返回指定节点的指针
失败:返回空指针
*************************************************/
Node* FindNodeByGlobalIndex(Node *pHead, int iGlobalIndex)
{
Node *pNode = NULL;
if ((NULL == pHead) || (iGlobalIndex < 0))
{
return NULL;
}
pNode = pHead->pNext;
while ((NULL != pNode))
{
if (pNode->data.a == iGlobalIndex)
{
break;
}
pNode = pNode->pNext;
}
return pNode;
}
/*************************************************
Function : Insert2ListTail
Description : 向链表中尾部插入某个节点
Input : pHead 链表的头节点指针
pStudentInfo 学生信息
Return : 正确:返回头节点指针
失败:返回空指针
*************************************************/
Node* Insert2ListTail(Node *pHead, Node_data *pAutoInfo)
{
Node* pNode = NULL;
Node* pNewNode = NULL;
if ((NULL == pHead) || (NULL == pAutoInfo))
{
return NULL;
}
pNode = pHead;
while (pNode->pNext != NULL)
{
pNode = pNode->pNext;
}
pNewNode = (Node *)malloc(sizeof(Node));
if (NULL == pNewNode)
{
return NULL;
}
pNode->pNext = pNewNode;
pNewNode->pNext = NULL;
memcpy(&(pNewNode->data), pAutoInfo, sizeof(Node_data ));
return pHead;
}
/*************************************************
Function : RemoveList
Description : 删除整个链表
Input : pHead 链表的头节点指针
Return : 正确: 1
失败: 0
*************************************************/
int RemoveList(Node *pHead)
{
Node *pNode = NULL;
Node *pb = NULL;
if (NULL == pHead)
{
return 0;
}
pNode = pHead;
pb = pNode->pNext;
if (NULL == pb)
{
free(pNode);
}
else
{
while (NULL != pb)
{
free(pNode);
pNode = pb;
pb = pb->pNext;
}
free(pNode);
}
pNode = NULL;
return 1;
}
/*************************************************
Function : PrintList
Description : 打印整个链表
Input : pHead 链表的头节点指针
Return :
*************************************************/
void PrintList(Node *pHead)
{
Node *pNode = NULL;
if (NULL == pHead)
{
return ;
}
pNode = pHead->pNext;
while ((NULL != pNode))
{
printf("\r\n a is %d b is %d",pNode->data.a,pNode->data.b);
pNode = pNode->pNext;
}
return ;
}
/*************************************************
Function : DeleteList
Description : 删除链表的一个结点，删除条件该节点的a值与x相同
Input :
Return :
*************************************************/
int DeleteList (Node *pHead,int x)
{
Node *pNode = NULL;
Node *pre = NULL;
if (NULL == pHead )
{
return 0;
}
pNode = pHead->pNext;
pre = pHead;
while(pNode)
{
if(pNode->data.a == x)//删除条件
{
pre->pNext = pNode->pNext;
free(pNode);
return 1;
}
else
{
pre = pNode;
}
pNode = pNode->pNext;
}
return 0;
}
/*************************************************
Function : ReverseList
Description : 链表反转
Input :
Return :
*************************************************/
void ReverseList(Node *pHead)
{
Node* p = pHead->pNext;
Node* q = p->pNext;
Node* t = NULL;
if(NULL == pHead || NULL == pHead->pNext)
{
return;
}
while(NULL != q)
{
t = q->pNext;
q->pNext = p;
p = q;
q = t;
}
pHead->pNext->pNext = NULL;
pHead->pNext = p;
}
/*************************************************
Function : SortList
Description : 按a值排序
Input :
Return :
*************************************************/
void SortList(Node *pHead)
{
Node* pi = pHead->pNext;
Node* pj = pi->pNext;
Link_data temp;
memset(&temp,0,sizeof(Link_data));
if(NULL == pHead || NULL == pHead->pNext)
{
return;
}
for(;pi != NULL;pi=pi->pNext)
{
for(pj = pi->pNext;pj != NULL;pj=pj->pNext)
{
if(pj->data.a < pi->data.a)
{
temp = pj->data;
pj->data = pi->data;
pi->data = temp;
}
}
}
}
#include<stdio.h>
#include<string.h>
#include"list.h"
Node * g_LinkHead = NULL;
int main()
{
Node_data data1;
Node_data data2;
Node_data data4;
Node *data3 = NULL;
memset(&data1, 0, sizeof(Node_data));
memset(&data2, 0, sizeof(Node_data));
memset(&data4, 0, sizeof(Node_data));
data1.a=3;
data1.b=3;
data2.a=2;
data2.b=4;
data4.a=5;
data4.b=6;
g_LinkHead=CreateList();
Insert2ListTail(g_LinkHead,&data1);
Insert2ListTail(g_LinkHead,&data2);
Insert2ListTail(g_LinkHead,&data4);
PrintList(g_LinkHead);
//data3 = FindNodeByGlobalIndex(g_LinkHead, 2);
//printf("\r\n data3.a %d data3.b %d",data3->data.a,data3->data.b);
printf("\n\n");
//(void) ReverseList(g_LinkHead);
(void) SortList(g_LinkHead);
PrintList(g_LinkHead);
/*if(DeleteList (g_LinkHead,4))
{
PrintList(g_LinkHead);
}
PrintList(g_LinkHead);*/
/*if(RemoveList(g_LinkHead))
{
g_LinkHead = NULL;
}
PrintList(g_LinkHead);*/
return 0;
}
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
评论(0)