单链表的操作？链表（带头结点）基本操作实验

：暂无数据 2026-07-24 11:40:05 ：0

大家好，链表操作相信很多的网友都不是很明白，包括单链表的操作也是一样，不过没有关系，接下来就来为大家分享关于链表操作和单链表的操作的一些知识点，大家可以关注收藏，免得下次来找不到哦，下面我们开始吧！

本文目录

单链表的操作
链表（带头结点）基本操作实验
java 中如何实现链表操作
链表操作
单链表的基本操作
数据结构单链表的基本操作与运算任务背景是什么
为什么链表操作时参数要用二级指针

单链表的操作

1.单链表的类型定义

typedef struct Node *PNode; /* 结点指针类型 */

struct Node /* 单链表结点结构 */

{

DataType data; /* 值域 */

struct Node *next; /* 指针域 */

};

为提高可读性,可定义单链表类型如下:

typedef struct Node *LinkList;

LinkList list; /* 定义一单链表list */

PNode p; /* 定义一单链表结点指针

则指针p所指结点的两个域表示为：

值　域： p-》data

指针域： p-》next

注：设置表头结点的目的是统一空链表与非空链表的操作，简化链表操作的实现。带头结点的空链表表示为：list-》next==NULL;而不带头结点的空链表只能表示为list==NULL;

单链表的常用算法(带头结点)

算法 1 创建空单链表LinkList createNullist_link( void )

分析：申请一表头结点的存储空间，并将该结点指针域置空

LinkList CreateNullist_link(void)

{

LinkList list=(LinkList)malloc(sizeof(struct Node));

　　　　　　　　　　　　　　　//申请表头结点存储空间

if( list != NULL) list-》next=NULL;

else printf(“Out of space!\n”); //创建失败

return(list);

}

注：算法中malloc为内存申请函数，需头文件stdlib.h支持。

算法 2 单链表的插入 int insert_link( LinkList list, PNode p, DataType x )

插入结点算法：

　　　首先生成待插入结点q,将其值域置为x，然后通过修正指针将结点q插入到结点p之后。

插入实现：

q-》data=x; //生成待插入结点

q-》next=p-》next;

p-》next=q;

算法 3 单链表结点的删除 int delete_link(LinkList list, DataType x )

删除结点算法：　　首先在list 带有头结点的单链表中找到第一个值为x的结点q，并记录其前驱结点的位置p,然后通过指针修正删除结点q。

删除实现：

q=p-》next;

p-》next=q-》next;

free(q);

单链表的删除操作是指删除第i个结点，返回被删除结点的值。删除操作也需要从头引用开始遍历单链表，直到找到第i个位置的结点。如果i为1，则要删除第一个结点，则需要把该结点的直接后继结点的地址赋给头引用。对于其它结点，由于要删除结点，所以在遍历过程中需要保存被遍历到的结点的直接前驱，找到第i个结点后，把该结点的直接后继作为该结点的直接前驱的直接后继。删除操作如图
单链表的删除操作示意图
删除操作的算法实现如下：
public T Delete(int i)
{
if (IsEmpty()|| i 《 0)
{
Console.WriteLine("Link is empty or Position is error!");
return default(T);
}
Node q = new Node();
if (i == 1)
{
q = head;
head = head.Next;
return q.Data;
}
Node p = head;
int j = 1;
while (p.Next != null&& j 《 i)
{
++j;
q = p;
p = p.Next;
}
if (j == i)
{
q.Next = p.Next;
return p.Data;
}
else
{
Console.WriteLine("The ith node is not exist!");
return default(T);
}
}
算法的时间复杂度分析：单链表上的删除操作与插入操作一样，时间主要消耗在结点的遍历上。如果表为空则不进行遍历。当表非空时，删除第i个位置的结点， i等于1遍历的结点数最少（1个），i等于n遍历的结点数最多（n个，n为单链表的长度），平均遍历的结点数为n/2。所以，删除操作的时间复杂度为O（n）。

java 中如何实现链表操作

class Node {
Object data;
Node next;//申明类Node类的对象叫Next
public Node(Object data) { //类Node的构造函数
setData(data);
}
public void setData(Object data) {
this.data = data;
}
public Object getData() {
return data;
}
}
class Link {
Node head;//申明一个Node类的一个对象 head
int size = 0;
public void add(Object data) {
Node n = new Node(data); //调用Node类的构造函数
链表是一种重要的数据结构，在程序设计中占有很重要的地位。C语言和C＋＋语
言中是用指针来实现链表结构的，由于Java语言不提供指针，所以有人认为在
Java语言中不能实现链表，其实不然，Java语言比C和C＋＋更容易实现链表结构
。Java语言中的对象引用实际上是一个指针（本文中的指针均为概念上的意义，
而非语言提供的数据类型），所以我们可以编写这样的类来实现链表中的结点。
class Node
{
Object data;
Node next;//指向下一个结点
}
将数据域定义成Object类是因为Object类是广义超类，任何类对象都可以给
其赋值，增加了代码的通用性。为了使链表可以被访问还需要定义一个表头，表
头必须包含指向第一个结点的指针和指向当前结点的指针。为了便于在链表尾部
增加结点，还可以增加一指向链表尾部的指针，另外还可以用一个域来表示链表
的大小，当调用者想得到链表的大小时，不必遍历整个链表。下图是这种链表的
示意图：
链表的数据结构
我们可以用类List来实现链表结构，用变量Head、Tail、Length、Pointer
来实现表头。存储当前结点的指针时有一定的技巧， Pointer并非存储指向当前
结点的指针，而是存储指向它的前趋结点的指针,当其值为null时表示当前结点是
第一个结点。那么为什么要这样做呢？这是因为当删除当前结点后仍需保证剩下
的结点构成链表，如果Pointer指向当前结点，则会给操作带来很大困难。那么如
何得到当前结点呢，我们定义了一个方法cursor(),返回值是指向当前结点的指
针。类List还定义了一些方法来实现对链表的基本操作，通过运用这些基本操作
我们可以对链表进行各种操作。例如reset()方法使第一个结点成为当前结点。
insert(Object d)方法在当前结点前插入一个结点，并使其成为当前结点。
remove()方法删除当前结点同时返回其内容，并使其后继结点成为当前结点，如
果删除的是最后一个结点，则第一个结点变为当前结点。
链表类List的源代码如下：
import java.io.*;
public class List
{
/*用变量来实现表头*/
private Node Head=null;
private Node Tail=null;
private Node Pointer=null;
private int Length=0;
public void deleteAll()
/*清空整个链表*/
{
Head=null;
Tail=null;
Pointer=null;
Length=0;
}
public void reset()
/*链表复位，使第一个结点成为当前结点*/
{
Pointer=null;
}
public boolean isEmpty()
/*判断链表是否为空*/
{
return(Length==0);
}
public boolean isEnd()
/*判断当前结点是否为最后一个结点*/
{
if(Length==0)
throw new java.lang.NullPointerException();
else if(Length==1)
return true;
else
return(cursor()==Tail);
}
public Object nextNode()
/*返回当前结点的下一个结点的值，并使其成为当前结点*/
{
if(Length==1)
throw new java.util.NoSuchElementException();
else if(Length==0)
throw new java.lang.NullPointerException();
else
{
Node temp=cursor();
Pointer=temp;
if(temp!=Tail)
return(temp.next.data);
else
throw new java.util.NoSuchElementException();
}
}
public Object currentNode()
/*返回当前结点的值*/
{
Node temp=cursor();
return temp.data;
}

public void insert(Object d)
/*在当前结点前插入一个结点，并使其成为当前结点*/
{
Node e=new Node(d);
if(Length==0)
{
Tail=e;
Head=e;
}
else
{
Node temp=cursor();
e.next=temp;
if(Pointer==null)
Head=e;
else
Pointer.next=e;
}
Length＋＋;
}
public int size()
/*返回链表的大小*/
{
return (Length);
}
public Object remove()
/*将当前结点移出链表，下一个结点成为当前结点，如果移出的结点是最后
一个结点，则第一个结点成为当前结点*/
{
Object temp;
if(Length==0)
throw new java.util.NoSuchElementException();
else if(Length==1)
{
temp=Head.data;
deleteAll();
}
else
{
Node cur=cursor();
temp=cur.data;
if(cur==Head)
Head=cur.next;
else if(cur==Tail)
{
Pointer.next=null;
Tail=Pointer;
reset();
}
else
Pointer.next=cur.next;
Length－－;
}
return temp;
}
private Node cursor()
/*返回当前结点的指针*/
{
if(Head==null)
throw new java.lang.NullPointerException();
else if(Pointer==null)
return Head;
else
return Pointer.next;
}
public static void main(String args)
/*链表的简单应用举例*/
{
List a=new List ();
for(int i=1;i《=10;i＋＋)
a.insert(new Integer(i));
System.out.println(a.currentNode());
while(!a.isEnd())
System.out.println(a.nextNode());
a.reset();
while(!a.isEnd())
{
a.remove();
}
a.remove();
a.reset();
if(a.isEmpty())
System.out.println("There is no Node in List \n");
System.in.println("You can press return to quit\n");
try
{
System.in.read();
//确保用户看清程序运行结果
}
catch(IOException e)
{}
}
}
class Node
/*构成链表的结点定义*/
{
Object data;
Node next;
Node(Object d)
{
data=d;
next=null;
}
}
读者还可以根据实际需要定义新的方法来对链表进行操作。双向链表可以用
类似的方法实现只是结点的类增加了一个指向前趋结点的指针。
可以用这样的代码来实现：
class Node
{
Object data;
Node next;
Node previous;
Node(Object d)
{
data=d;
next=null;
previous=null;
}
}
当然，双向链表基本操作的实现略有不同。链表和双向链表的实现方法，也
可以用在堆栈和队列的实现中，这里就不再多写了，有兴趣的读者可以将List类
的代码稍加改动即可。

链表操作

//class CNode.h
#ifndef __CNODE_H__
#define __CNODE_H__
#include 《iostream》
using namespace std;
struct stData //出生年月结构
{
int m_nYear;
int m_nMonth;
int m_nDay;
};
struct stResult //五门课成绩结构
{
double m_dSubject_1; //自己改成绩的名称
double m_dSubject_2;
double m_dSubject_3;
double m_dSubject_4;
double m_dSubject_5;
};
struct stStudent //声明学生信息的结构
{
string m_strNumber; //学生学号
string m_strName; //姓名
char m_chSex; //性别
struct stData m_stData; //出生年月
string m_strAppearance; //政治面貌
struct stResult m_stResult; //五门课成绩
};
typedef class CNode
{
private:
struct stStudent m_stStudent;
CNode* m_Next;
public:
CNode(); //构造函数
~CNode(); //析构函数
void SetNodeData(); //设置结点内容的函数成员
stStudent GetNodeData(); //获取结点内容的函数成员
void SetNodeNext(CNode* _Next); //设置结点Next指针的函数成员
void ShowNodeData(); //输出结点内容的函数成员
CNode* GetNodeNext(); //获取结点Next指针的函数成员
}LinkNode;
#endif
//class CLinkList
#ifndef __CLINKLIST_H__
#define __CLINKLIST_H__
#include "CNode.h"
typedef class CLinkList
{
private:
LinkNode* m_Head; //链表的头指针
LinkNode m_Node; //链表的头结点
public:
CLinkList(); //构造函数
~CLinkList(); //析构函数
void CreateList(); //初始化链表的函数成员
LinkNode* GetListNode(int _nIndex); //按位置查找指定位结点的成员函数
void InsertList(int _nIndex); //插入结点的成员函数
void DeleteList(int _nIndex); //删除某一结点的成员函数
LinkNode* GetHeadList(); //获取头指针的成员函数
void SetListData(int _nIndex); //设置链表中某一结点的值的成员函数
void ShowListData(int _nIndex); //这个是现实链表中某一结点值的函数成员
void DestroyList(int _nIndex); //销毁某一位置以后链表的成员函数
void ShowList(); //显示链表的成员函数
}LinkList;
#endif
//class CLinkList
#include "CLinkList.h"
#include "CNode.h"
CLinkList::CLinkList()
{
cout 《《 "这个是构造函数"《《 endl;
m_Head = &m_Node; //链表的头指针指向头结点
m_Node.SetNodeNext(NULL); //将头结点的Next指针设置为NULL;
}
CLinkList::~CLinkList()
{
cout 《《 "这个是析构函数" 《《 endl;
}
void CLinkList::CreateList() //以向后追加的方式创建一个链表，输入0退出
{
int nTemp = 0; //定义一个临时变量用于标志程序结束
cout 《《 "欢迎来创建链表 !" 《《 endl;
CNode * pTemp = NULL; //定义一个临时结点指针，用来增加新结点用
CNode * pNode = m_Head; //定义一个标记指针，首先叫其指向头结点
while(1)
{
pTemp = new LinkNode;
cout 《《 "请输入下一个结点的内容!" 《《 endl;
pTemp-》SetNodeData(); //设置链表中结点的内容

cout 《《 "如果想继续输入下一个学生的信息请输入 1，否则输入 0" 《《 endl;
cin 》》 nTemp;
if (’0’ == nTemp)
{
break;
}
pNode-》SetNodeNext(pTemp); //让链尾的Next指向新建的结点
pNode = pTemp; //将结尾元素向后移
}
cout 《《 "创建链表结束" 《《 endl;
}
LinkNode* CLinkList::GetListNode(int _nIndex)
{
cout 《《 "这个是按位置查找指定位结点的成员函数" 《《 endl;
LinkNode* pNode = m_Head-》GetNodeNext(); //定义一个临时的结点指针,初始化指向头结点
int Temp = 0; //定义一个临时的变量，用来标记已检查结点的个数的
if(-1 == _nIndex) //返回头结点（即头指针）
{
return m_Head;
}
if(_nIndex 《 -1) //_nIndex控制条件
{
cout 《《 "您输入的是错误的位置！" 《《 endl;
return 0;
}
while(pNode != NULL)
{
if(_nIndex == Temp)
{
return pNode;
}
pNode = pNode-》GetNodeNext(); //临时结点向后移动
++Temp;
}

return pNode; //没找到结点就返回NULL
}
void CLinkList::ShowListData(int _nIndex);
void CLinkList::InsertList(int _nIndex) //插入结点的函数成员
{
cout 《《 "这个是插入结点的成员函数" 《《 endl;
LinkNode* pNode = GetListNode(_nIndex - 1); //定义一个结点类的指针，指向的是要插入位置的前一指针
LinkNode* pTemp = new CNode; //定义一个临时结点指针，用来增加新结点用
pTemp-》SetNodeData(); //设置插入结点的内容
pTemp-》SetNodeNext(pNode-》GetNodeNext());
pNode-》SetNodeNext(pTemp);
}
void CLinkList::DeleteList(int _nIndex)
{
cout 《《 "这个是删除某一结点的成员函数" 《《 endl;
LinkNode* pNode = GetListNode(_nIndex - 1); //定义一个结点类的指针，指向的是要删除位置的前一指针
LinkNode* pTemp = NULL; //定义一个临时结点指针，用来指向要删除的结点
pTemp =pNode-》GetNodeNext(); //把pTemp指向要删除的结点
pNode-》SetNodeNext(pTemp-》GetNodeNext()); //把pNode指向要删除的结点的后一个结点
delete pTemp; //删除结点
pTemp = NULL;
}
LinkNode* CLinkList::GetHeadList()
{
cout 《《 "这个是获取头指针的成员函数" 《《 endl;
return m_Head;
}
void CLinkList::SetListData(int _nIndex)
{
cout 《《 "这个是设置链表中某一结点的值的成员函数" 《《 endl;
CNode *pNode = GetListNode(_nIndex); //定义一个结点类的指针，指向的是要修改内容位置的结点
pNode-》SetNodeData(); //修改内容
}
void CLinkList::ShowListData(int _nIndex)
{
cout 《《 "这个是显示链表中某一结点值的成员函数" 《《 endl;
CNode *pNode = GetListNode(_nIndex); //定义一个结点类的指针，指向的是要获取内容位置的结点
pNode-》ShowNodeData(); //返回想要得到位置的结点内容
}
void CLinkList::DestroyList(int _nIndex)
{
cout 《《 "这个是销毁某一位置以后链表的成员函数" 《《 endl;
LinkNode* pTemp = GetListNode(_nIndex - 1); //定义一个结点指针，指向要销毁位置的前一结点
LinkNode* pNode = pTemp-》GetNodeNext(); //定义一个结点指针，指向要销毁位置的结点

while(pTemp-》GetNodeNext() != NULL) //销毁动作的结束条件或初始条件
{
pTemp-》SetNodeNext(pNode-》GetNodeNext()); //把需要销毁的位置的前结点的Next指向销毁位置的下一个结点
delete pNode; //销毁结点
pNode = pTemp-》GetNodeNext(); //把pNode重新指向要销毁位置的结点
}
}

void CLinkList::ShowList()
{
cout 《《 "这个是显示链表的成员函数" 《《 endl;
int nTemp = 0; //定义一个临时的整形变量用来控制输入的个数
LinkNode* pTemp = m_Head-》GetNodeNext(); //定义一个结点类指针，指向第0位的结点
if(NULL == pTemp)
{
cout 《《 "这是个空链" 《《 endl;
}
while(pTemp != NULL)
{
pTemp-》ShowNodeData();
++nTemp;
if(0 == nTemp % 5 && nTemp != 0) //控制每行只能输出5个结点的内容
{
cout 《《 endl;
}

pTemp = pTemp-》GetNodeNext();
}
}
//class CNode
#include "CNode.h"
CNode::CNode() //构造函数
{
//m_stStudent = {0};
m_Next = NULL;
}
CNode::~CNode() //析构函数
{
}
void CNode::SetNodeData()
{
char* pNumber = new char; //用来接收字符串的临时变量
char* pName = new char;
char* pAppearance = new char;
cout 《《 "学生学号: " 《《 endl;
cin 》》 pNumber;
m_stStudent.m_strNumber = pNumber;
cout 《《 "姓名: " 《《 endl;
cin 》》 pName;
m_stStudent.m_strName = pName;
cout 《《 "性别: " 《《 endl;
cin 》》 m_stStudent.m_chSex;
cout 《《 "出生年月: " 《《 endl;
cout 《《 "m_stData.m_nYear" 《《 endl;
cin 》》 m_stStudent.m_stData.m_nYear;
cout 《《 "m_stData.m_nMonth" 《《 endl;
cin 》》 m_stStudent.m_stData.m_nMonth;
cout 《《 "m_stData.m_nDay" 《《 endl;
cin 》》 m_stStudent.m_stData.m_nDay;
cout 《《 "政治面貌: " 《《 endl;
cin 》》 pAppearance;
m_stStudent.m_strAppearance = pAppearance;
cout 《《 "五门课成绩: " 《《 endl;
cout 《《 "m_dSubject_1: " 《《 endl;
cin 》》 m_stStudent.m_stResult.m_dSubject_1;
cout 《《 "m_dSubject_2: " 《《 endl;
cin 》》 m_stStudent.m_stResult.m_dSubject_2;
cout 《《 "m_dSubject_3: " 《《 endl;
cin 》》 m_stStudent.m_stResult.m_dSubject_3;
cout 《《 "m_dSubject_4: " 《《 endl;
cin 》》 m_stStudent.m_stResult.m_dSubject_4;
cout 《《 "m_dSubject_5: " 《《 endl;
cin 》》 m_stStudent.m_stResult.m_dSubject_5;
delete pNumber; //释放内存
pNumber = NULL; //指针置空
delete pName; //释放内存
pName = NULL;
delete pAppearance; //释放内存
pAppearance = NULL;
}
stStudent CNode::GetNodeData() //返回结点内容（即学生信息）
{
return m_stStudent;
}
void CNode::SetNodeNext(CNode* _Next)
{
m_Next = _Next;
}
void CNode::ShowNodeData()
{
const char* pNumber = m_stStudent.m_strNumber.c_str(); //用来接收字符串的临时变量
const char* pName = m_stStudent.m_strNumber.c_str();
const char* pAppearance = m_stStudent.m_strAppearance.c_str();
cout 《《 "学生学号: " 《《 pNumber 《《 ’\t’ 《《 "姓名: " 《《 pName 《《 ’\t’ 《《 "性别: " 《《 m_stStudent.m_chSex;
cout 《《 "出生年月: " 《《 m_stStudent.m_stData.m_nYear 《《 ’,’ 《《 m_stStudent.m_stData.m_nMonth 《《 ’,’ 《《 m_stStudent.m_stData.m_nDay;
cout 《《 "政治面貌: " 《《 pAppearance 《《 "五门课成绩: " 《《 endl;
cout 《《 "m_dSubject_1: "《《 m_stStudent.m_stResult.m_dSubject_1《《 endl;
cout 《《 "m_dSubject_2: "《《 m_stStudent.m_stResult.m_dSubject_2《《 endl;
cout 《《 "m_dSubject_3: "《《 m_stStudent.m_stResult.m_dSubject_3《《 endl;
cout 《《 "m_dSubject_4: "《《 m_stStudent.m_stResult.m_dSubject_4《《 endl;
cout 《《 "m_dSubject_5: "《《 m_stStudent.m_stResult.m_dSubject_5《《 endl;
}
CNode* CNode::GetNodeNext()
{
return m_Next;
}
#include "CLinkList.h"
#include "CNode.h"
void Text(); //测试函数声明
int main()
{
cout 《《 "这是mian函数" 《《 endl;
Text();
return 0;
}
void Text()
{
cout 《《 "这个是测试函数" 《《 endl;
LinkList* pList = new LinkList; //创建一个内存链表对象
cout 《《 "------------------CreateList-----------------------------" 《《 endl;
pList-》CreateList(); //初始化链表的函数成员
pList-》ShowList();
cout 《《 endl;
cout 《《 "------------------GetListNode-----------------------------" 《《 endl;
LinkNode* pNode = NULL; //定义一个临时的结点类指针用于检测查找函数成员
pNode = pList-》GetListNode(3); //按位置查找指定位结点的成员函数的测试
if(pNode)
{
cout 《《 "用按位置查找的方法找到了指定位结点" 《《 endl;
}
else
{
cout 《《 "对不起，用按位置查找的方没有找到指定位结点" 《《 endl;
}
cout 《《 endl;

cout 《《 "------------------InsertList-----------------------------" 《《 endl;
pList-》InsertList(0); //插入结点的成员函数的测试
pList-》ShowList();
cout 《《 endl;
cout 《《 "------------------DeleteList-----------------------------" 《《 endl;
pList-》DeleteList(0); //删除某一结点的成员函数的测试
pList-》ShowList();
cout 《《 endl;
cout 《《 "------------------GetHeadList-----------------------------" 《《 endl;
pNode = NULL;
pNode = pList-》GetHeadList(); //获取头指针的成员函数的测试
if(pNode)
{
cout 《《 "已经返回了头指针" 《《 endl;
}
else
{
cout 《《 "对不起，头指针为空" 《《 endl;
}
cout 《《 endl;
cout 《《 "------------------GetHeadList-----------------------------" 《《 endl;
pList-》SetListData(3); //设置链表中某一结点的值的成员函数的测试
pList-》ShowList();
cout 《《 endl;
cout 《《 "------------------GetListData-----------------------------" 《《 endl;
cout 《《 "pList-》ShowListData(3) =";
pList-》ShowListData(3); //获取链中某一结点值的成员函数的测试
cout 《《 endl;
cout 《《 "------------------DestroyList(3)-----------------------------" 《《 endl;
pList-》DestroyList(3); //销毁第3位置以后链表的成员函数的测试
pList-》ShowList();
cout 《《 endl;
cout 《《 "------------------DestroyList(0)-----------------------------" 《《 endl;
pList-》DestroyList(0); //销毁第0位置以后链表的成员函数的测试
pList-》ShowList();
cout 《《 endl;
delete pList; //释放内存
pList = NULL; //指针置空
}
你自己改下变量名好不？我实在是很忙，没时间搞，如果你改完有什么问题，再找我吧，

单链表的基本操作

#include "stdafx.h"
#include 《stdio.h》
#include 《malloc.h》
typedef char ElemType;
struct LNode
{
ElemType data;
struct LNode *next;
};
//***********************************************************置空表setnull()
void setnull(struct LNode **p)
{
*p=NULL;
}
//************************************************************求长度length()
int length(struct LNode **p)
{
int n=0;
struct LNode *q=*p;
while (q!=NULL)
{
n++;
q=q-》next;
}
return(n);
}
//*************************************************************取结点get()
ElemType get(struct LNode **p,int i)
{
int j=1;
struct LNode *q=*p;
while (j《i && q!=NULL) /**//*查找第i个结点*/
{
q=q-》next;j++;
}
if (q!=NULL) /**//*找到了第i个结点*/
return(q-》data);
else
{
printf("位置参数不正确!\n");
return NULL;
}
}
//************************************************************按值查找locate()
int locate(struct LNode **p,ElemType x)
{
int n=0;
struct LNode *q=*p;
while (q!=NULL && q-》data!=x) /**//*查找data域为x的第一个结点*/
{
q=q-》next;
n++;
}
if (q==NULL) /**//*未找到data域等于x的结点*/
return(-1);
else /**//*找到data域等于x的结点*/
return(n+1);
}
//**********************************************************插入结点insert()
void insert(struct LNode **p,ElemType x,int i)
{
int j=1;
struct LNode *s,*q;
s=(struct LNode *)malloc(sizeof(struct LNode)); /**//*建立要插入的结点s*/
s-》data=x;
q=*p;
if (i==1) /**//*插入的结点作为头结点*/
{
s-》next=q;
*p=s;
}
else
{
while (j《i-1 && q-》next!=NULL) /**//*查找第i-1个结点*/
{
q=q-》next;j++;
}
if (j==i-1) /**//*找到了第i-1个结点,由q指向它*/
{
s-》next=q-》next; /**//*将结点s插入到q结点之后*/
q-》next=s;
}
else
printf("位置参数不正确!\n");
}
}
//*********************************************************删除结点del()
void del(struct LNode **p,int i)
{
int j=1;
struct LNode *q=*p,*t;
if (i==1) /**//*删除链表的头结点*/
{
t=q;
*p=q-》next;
}
else
{
while (j《i-1 && q-》next!=NULL) /**//*查找第i-1个结点*/
{
q=q-》next;j++;
}
if (q-》next!=NULL && j==i-1) /**//*找到第i-1个结点,由q指向它*/
{
t=q-》next; /**//*t指向要删除的结点*/
q-》next=t-》next; /**//*将q之后的结点删除*/
}
else printf("位置参数不正确!\n");
}
if (t!=NULL) /**//*在t不为空时释放该结点*/
free(t);
}
//********************************************************显示链表display()
void display(struct LNode **p)
{
struct LNode *q;
q=*p;
printf("单链表显示:");
if (q==NULL) /**//*链表为空时*/
printf("链表为空!");
else if (q-》next==NULL) /**//*链表只有一个结点时*/
printf("%c\n",q-》data);
else { /**//*链表存在一个以上的结点时*/
while (q-》next!=NULL) /**//*显示前面的结点*/
{
printf("%c→",q-》data);q=q-》next;
}
printf("%c",q-》data); /**//*显示最后一个结点*/
}
printf("\n");
}
void main()
{
struct LNode *head;
setnull(&head);
insert(&head,’a’,1);
insert(&head,’b’,2);
insert(&head,’a’,2);
insert(&head,’c’,4);
insert(&head,’d’,3);
insert(&head,’e’,1);
display(&head);
printf("单链表长度=%d\n",length(&head));
printf("位置:%d 值:%c\n",3,get(&head,3));
printf("值:%c 位置:%d\n",’a’,locate(&head,’a’));
printf("删除第1个结点:");
del(&head,1);
display(&head);
printf("删除第5个结点:");
del(&head,5);
display(&head);
printf("删除开头3个结点:");
del(&head,3);
del(&head,2);
del(&head,1);
display(&head);
}
/**//*
运行结果：
单链表显示:e→a→a→d→b→c
单链表长度=6
位置:3 值:a
值:a 位置:2
删除第1个结点:单链表显示:a→a→d→b→c
删除第5个结点:单链表显示:a→a→d→b
删除开头3个结点:单链表显示:b
*/

数据结构单链表的基本操作与运算任务背景是什么

，基本运算
1，单链表，双链表的定义：
设计链式存储结构时，每个逻辑节点存储单独存储。
2，单链表的基本结构：
头节点在前，首节点在后。
3，顺序表与链表间存储密度的差异：
顺序表的存储密度为1，而链表的存储密度小于1。
4，
typedef struct LNode
{
ElemType data; //存放元素值
struct LNode *next; //指向后继节点
}LinkNode //单链表节点类型
登录后复制
一个是数据域部分，一个是指向后继节点的指针域。
5，特点：
6，插入节点：
s→next=p→next
p→next=s
登录后复制
p指针指向一个节点。
如图7所示，删除节点：
p→next=p→next→next
登录后复制
二，基本算法
如图1所示，头插法建表
void CreatListF(LinkNode *&L,ElemType a,int n)
{
LinkNode *s;
L=(LinkNode *)malloc(sizeof(LinkNode));
L→next=NULL; //创建头节点，其next域置为NULL
for(int i=0;i《n;i++) //循环建立数据节点s
{
s=(LinkNode *)malloc(sizeof(LinkNode));
s→data=a; //创建数据节点s
s→next=L→next; //将s插入到原首节点之前、头节点之后
L→next=s;
}
}
登录后复制
这个算法的时间复杂度为O（N）。
链表的节点顺序和逻辑顺序正好相反。
2，尾插法建表
void CreateListR(ListNode *&L,ElemType a,int n)
{
LinkNode *s,*r;
L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
r=L; //r始终指向尾结点，初始时指向头结点
for(int i=0;i《n;i++) //循环建立数据结点
{
s=(LinkNode *)malloc(s

为什么链表操作时参数要用二级指针

你好，其实这个问题我当时也迷糊了，后来想想其实也不难，呵呵，我们分析一下：
如果用c语言描述单链表如下：
typedef
struct
node{
datatype
data;//节点的数据域
struct
node
*next;//节点的指针域
}listnode;
typedef
listnode
*linklist;
listnode
*p;//p是节点
linklist
head;//head是头指针
注意最后一句："linklist
head",这是定义了一个头结点，前面已经用typedef定义了linklist，既“typedef
listnode
*linklist;”这句，这就说明linklist
head
定义后
head实际上是一个linknode类型的指针，这是我们单单看最后两句的定义而忽略其字面意思而言的话，p和head实际上是同一种类型的变量，都是listnode类型的指针，只不过最后一句linklist类型是用typedef定义的，所以没有“*”号。
因为删除或者插入操作有时会修改实参的指针（比如头结点为空的时候插入节点，这是就修改了头结点），那么就必须将相应的形参说明为指针的指针，函数电泳时将实参指针的地址传递给相应的形参。例如：刚刚初始化的时候头结点head为空，如果这时插入节点p（由上可知p是listnode*类型的，是个指针，把它当做地址）时应该是head=p;这就改变了head的地址，所以在传参数的时候，函数的形参一般都是"insert(linklist
*head,datatype
x)",
注意：head是listnode*类型的，所以*head
是listnode**类型的，不知道我说的楼主认为可以吗？