链表操作？单链表的基本操作

本文目录

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

链表操作

//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*/

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

单链表的删除操作是指删除第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）。

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

，基本运算1，单链表，双链表的定义：设计链式存储结构时，每个逻辑节点存储单独存储。2，单链表的基本结构： 头节点在前，首节点在后。3，顺序表与链表间存储密度的差异：顺序表的存储密度为1，而链表的存储密度小于1。4，typedef struct LNode{ ElemType data; //存放元素值 struct LNode *next; //指向后继节点}LinkNode //单链表节点类型登录后复制一个是数据域部分，一个是指向后继节点的指针域。5，特点：6，插入节点：s→next=p→nextp→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语言描述单链表如下：typedefstructnode{datatypedata;//节点的数据域structnode*next;//节点的指针域}listnode;typedeflistnode*linklist;listnode*p;//p是节点linklisthead;//head是头指针注意最后一句："linklisthead",这是定义了一个头结点，前面已经用typedef定义了linklist，既“typedeflistnode*linklist;”这句，这就说明linklisthead定义后head实际上是一个linknode类型的指针，这是我们单单看最后两句的定义而忽略其字面意思而言的话，p和head实际上是同一种类型的变量，都是listnode类型的指针，只不过最后一句linklist类型是用typedef定义的，所以没有“*”号。因为删除或者插入操作有时会修改实参的指针（比如头结点为空的时候插入节点，这是就修改了头结点），那么就必须将相应的形参说明为指针的指针，函数电泳时将实参指针的地址传递给相应的形参。例如：刚刚初始化的时候头结点head为空，如果这时插入节点p（由上可知p是listnode*类型的，是个指针，把它当做地址）时应该是head=p;这就改变了head的地址，所以在传参数的时候，函数的形参一般都是"insert(linklist*head,datatypex)",注意：head是listnode*类型的，所以*head是listnode**类型的，不知道我说的楼主认为可以吗？

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类的代码稍加改动即可。

单链表的操作

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);