在实现单链表时要注意对单链表的逻辑存储、物理存储有清晰的概念。
如上图链表已经完成，其逻辑结构如上。当需要对其进行操作，比如插入、删除，通常需要引
入指针，如上的ptr1、ptr2。在编程时一定要注意通过ptr1、ptr2对链表结构的操作是正确的。
而不仅仅是你觉得正确的。
下面给大家看下我的单链表的实现，错误之处还请指正。
1、VC6实现，包括三个文件:sll.h、sll.c、main.c
2、sll.h单链表类、结点类的说明
#ifndef _SLL_H_
#define _SLL_H_ //加以下两句是为了使链表中包含的数据类型可以更灵活
#define dataType int
#define endOfData 0 //单链表的节点
class node
{
public:
dataType data;
node *next;
}; //单链表,其中保存的元素为整数
class sll
{
public:
sll(); //构造函数
~sll(); //析构函数
void create(); //建立一个链表
int getLength(); //获取链表长度
void reverse(); //链表倒置
bool insert(int pos,dataType num); //插入某一位置的某一值.插入成功返回true;否则返回false.位置从0开始向上累加
void del(dataType num); //删除某一所有值
node* getHead(); //获取链表头
void print(); //打印所有元素
int find(dataType num); //在链表中寻找num.若找到返回首次找到的下标,若找不到则返回-1
dataType getNum(int pos); //根据pos找到对应结点的data域的值,若找不到则返回endOfData private:
node *head; //链表头指针
}; #endif
3、sll.c单链表类成员函数的实现
#include <iostream>
#include "sll.h"
using namespace std; sll::sll() //构造函数
{
head = NULL;
} sll::~sll() //析构函数
{
node *ptrNode = head;
node *ptrNodeTmp = NULL; while(ptrNode != NULL)
{
ptrNodeTmp = ptrNode->next;
delete ptrNode;
ptrNode = ptrNodeTmp;
}
} void sll::create()
{
node *ptrNode = new node;
ptrNode->data = endOfData;
head = ptrNode; //保存头结点指针 bool flag = true; //flag=true继续建单链表,flag=false链表建立完成
bool flagNumOne = true; //flagNumOne表示是链表的第一个元素
dataType data = endOfData; //dataType和endOfData在sll.h中定义 while(flag)
{
cout<<"输入节点数据: "; //一个一个的输入结点
cin>>data; if(data != endOfData)
{ //没有输入建链表结束标志endOfData,则继续建链表
if(!flagNumOne)
{
node *tmpPtr = new node; ptrNode->next = tmpPtr;
ptrNode = tmpPtr;
} ptrNode->data = data; flagNumOne = false;
}
else
{ //输入结束标志endOfData,则结束建链表
flag = false;
ptrNode->next = NULL;
}
} if(head->data == endOfData) //链表为空的情况
{
head = NULL;
delete ptrNode; //如果链表中没有元素,则要释放程序申请的唯一结点
}
} int sll::getLength()
{
int num = 0;
node *ptrNode = head; while(ptrNode != NULL)
{
num++; //未到链表结尾则继续累加
ptrNode = ptrNode->next; //链表延展
} return num;
} void sll::del(dataType num)
{
//ptrNodeMain和ptrNodeAssit在起始时是指向同一结点的,以后都是指向一前一后的两个点,ptrNodeAhead在前(更接近链表结束)
node *ptrNodeAhead = head;
node *ptrNodeFellow = ptrNodeAhead; while(ptrNodeAhead != NULL) //链表要从头找到尾,删除链表中所有等于num的结点
{
while(ptrNodeAhead->data != num && ptrNodeAhead->next != NULL) //未找到num结点,也未到链表结尾,指针向下扩展
{
ptrNodeFellow = ptrNodeAhead;
ptrNodeAhead = ptrNodeAhead->next;
} if(ptrNodeAhead->data == num) //找到num结点
{
if(ptrNodeAhead == head) //如果num节点是头结点
{
head = ptrNodeAhead->next;
delete ptrNodeAhead;
ptrNodeAhead = head;
ptrNodeFellow = ptrNodeAhead;
}
else //如果num节点不是头结点
{
ptrNodeFellow->next = ptrNodeAhead->next;
delete ptrNodeAhead;
ptrNodeAhead = ptrNodeFellow->next;
}
}
else //链表搜索结束也未找到num结点
{
ptrNodeAhead = NULL;
}
}
} bool sll::insert(int pos,dataType num)
{
if(pos < 0 || pos >= getLength()) //判断插入结点的正确位置是(0 ~ getLength()-1)
{
return false;
} node *ptrNodeAhead = head;
node *ptrNodeFollow = NULL;
int tmpNum = 0;
while(1) //获取插入位置的指针,ptrNodeAhead指向待插入的位置,ptrNodeFollow指向带插入位置的下一结点
{
if(tmpNum++ == pos)
{
break;
} ptrNodeFollow = ptrNodeAhead;
ptrNodeAhead = ptrNodeAhead->next;
} //以下两句将待插入结点的数据准备好
node *ptrTmpNode = new node;
ptrTmpNode->data = num; if(ptrNodeAhead == head) //如果是插入头结点
{
ptrTmpNode->next = head;
head = ptrTmpNode;
}
/*
else if(ptrNodeAhead->next == NULL)
{
ptrNodeAhead->next == ptrTmpNode;
ptrTmpNode->next = NULL;
}
*/
else //插入中间节点,此种方法永远也不能插入尾结点,插入是前向的
{
ptrNodeFollow->next = ptrTmpNode;
ptrTmpNode->next = ptrNodeAhead;
} return true;
} node* sll::getHead()
{
return head; //返回链表头结点指针
} void sll::reverse()
{
node *ptrNodeAhead = head;
node *ptrNodeFllow = NULL;
node *ptrTmp = NULL; while(ptrNodeAhead != NULL)
{
ptrTmp = ptrNodeAhead->next;
ptrNodeAhead->next = ptrNodeFllow;
ptrNodeFllow = ptrNodeAhead;
ptrNodeAhead = ptrTmp;
} head = ptrNodeFllow;
} void sll::print()
{
node *ptrNode = head; while(ptrNode != NULL)
{
cout<<ptrNode->data<<" "; ptrNode = ptrNode->next;
}
cout<<endl;
} int sll::find(dataType num)
{
node *ptrNode = head;
int index = 0; while(ptrNode != NULL)
{
if(ptrNode->data == num)
{
return index; //返回第一个num结点的下标
} ++index;
ptrNode = ptrNode->next; //链表向下延展
} return -1; //未找到num结点返回-1
} dataType sll::getNum(int pos)
{
if(pos < 0 || pos >= getLength()) //判断pos的正确位置是(0 ~ getLength()-1)
{
return endOfData;
} int index = 0;
node *ptrNode = head; while(1)
{
if(index++ == pos)
{
return ptrNode->data;
} ptrNode = ptrNode->next;
}
}
4、main.c
#include <iostream>
#include "sll.h"
using namespace std; int main()
{
sll exp; exp.create(); cout<<"The len of sll: "<<exp.getLength()<<endl;
exp.print(); exp.del(2);
exp.print(); exp.insert(2,999);
exp.print(); exp.reverse();
exp.print(); cout<<"2的位置在: "<<exp.find(2)<<endl; cout<<exp.getNum(3)<<endl; return 0;
}
5、测试结果