单链表基本操作实现(高质量 精心coding )
时间:2008-06-12 15:10:02
来源:论坛整理 作者: 编辑:chinaitzhe
欢迎大家来为单链表算法操作盖楼啊
qq:549693023
benson88921@yahoo.com.cn
/ *********************单链表基本操作实现*************/
/ **********************Author：~For_*****************/
#include <iostream>
using namespace std;
typedef long DataType; //可以是其他数据类型
//定义单链表结构体
typedef struct node
{
DataType data;
struct node* Next;
}LinkList,*PLinkList;
/ ****************创建空单链表***********************/
PLinkList Create_Linklist()
{
PLinkList PLinkListPoint;
PLinkListPoint=new LinkList;
if(!PLinkListPoint)
{
cout < <"分配内存失败！" < <endl;
return (NULL);
}
else
{
PLinkListPoint->Next=NULL;
return (PLinkListPoint);
}
}
/ ****************头插法创建并填充链表****************/
PLinkList Create_ReverseLinkList()
{
PLinkList H,preview;
int NodeCount=0; //结点总数初始化为0
H=new LinkList;
if(!H)
{
cout < <"分配内存失败！" < <endl;
return (NULL);
}
else
{
H->Next=NULL; //========初始化时头结点Next为NULL
}
cout < <"请输入你想创建链表结点总数：";
cin>>NodeCount;
cout < <"请输入各结点数据（注：头插法创建，存储数据将与实际数据相反）" < <endl;
for(int i=1;i <=NodeCount;i )
{
preview=new LinkList;
cin>>preview->data; //填充结点数据
preview->Next=H->Next; //=========H-Next第一次为NULL以后为前一个结点地址，第一个加入的preview即为最后一个结点
H->Next=preview; //=========H头结点指向新加入的结点
}
return (H);
//$$横等线应非凡注重理解
}
/ ****************尾插法创建并填充链表****************/
PLinkList Create_SeqLinkList()
{
//辅助变量
PLinkList H,preview,current; //H为头结点，preview前一个结点, current当前结点
int NodeCount=0; //结点总数初始化为0
H=new LinkList;
if(!H)
{
cout < <"分配内存失败！" < <endl;
return (NULL);
}
else
{
H->Next=NULL; //=======================================
}
cout < <"请输入你想创建链表结点总数：";
cin>>NodeCount;
cout < <"请输入各结点数据（注：尾插法创建，存储数据将与实际数据顺序一致）" < <endl;
preview=H; //preview指向表头，注重理解 ============================
for(int i=1;i <=NodeCount;i )
{
current=new LinkList;
if(!current)
{
cout < <"分配空间失败！" < <endl;
return (NULL);
}
preview->Next=current; //preview指向current，把前一个节点指向当前节点,连接所有链表=======
cin>>current->data;
current->Next=NULL; //将最后的元素Next指向空======================================
preview=current; //preview后移到current========================================
}
return (H);
//$$横等线应非凡注重理解
}
/ ****************销毁链表操作****************************/
bool Destory_LinkList(PLinkList* PLinkListPoint)
{
if(!*PLinkListPoint)
{
cout < <"表不存在！" < <endl;
return (false);
}
PLinkList p=*PLinkListPoint,q;
while(p)
{
q=p;
p=p->Next;
delete q;
}
return (true);
}
//=================================================================================//
//链表操作
/ ****************求链表长度操作**********************/
int Length_LinkList(PLinkList PlinkListPoint)
{
//返回参数：-1表不存在，nCount表长
if(!PlinkListPoint)
{
cout < <"表不存在！" < <endl;
return (-1);
}
int nCount=-1;
PLinkList p;
p=PlinkListPoint;
while(p)
{
nCount ;
p=p->Next;
}
return (nCount);
}
/ ****************按位置检索操作**********************/
PLinkList Locate_LinkList(PLinkList PLinkListPoint ,int i)
{
PLinkList p=PLinkListPoint;
int j=0;
while(p&&j <i)
{
p=p->Next;
j ;
}
if(j!=i ¦ ¦!p)
{
cout < <"查找位置不合法！或单链表不存在！" < <endl;
return (NULL);
}
return (p);
}
/ ***************按元素检索操作**********************/
PLinkList Locate_LinkList(PLinkList PLinkListPoint ,DataType DataX)
{
PLinkList p=PLinkListPoint;
if(p)
{
while(p->data!=DataX && p )
{
p=p->Next;
}
if(!p)
{
cout < <"此表中，没有该数据！" < <endl;
return (NULL);
}
return (p);
}
else
{
cout < <"表不存在!" < <endl;
return (NULL);
}
}
/ ****************按位置删除结点操作******************/
int Del_LinkList(PLinkList PLinkListPoint ,int i)
{
//返回值：-1表不存在，-2删除位置不合法，1成功
if(!PLinkListPoint)
{
cout < <"表不存在！" < <endl;
return (-1);
}
PLinkList p=Locate_LinkList(PLinkListPoint,i-1); //查找要删除位置的前一个结点
PLinkList q;
if(!p)
{
cout < <"删除位置不合法！" < <endl;
return (-2);
}
q=p->Next;
p->Next=q->Next;
delete q;
return (1);
}
网友回复:
/ ****************插入操作****************************/
int Insert_LinkList(PLinkList PLinkListPoint,int i,DataType DataX)
{
//返回参数：-1表不存在，-2分配空间失败,1成功
if(!PLinkListPoint)
{
cout < <"表不存在！" < <endl;
return (-1);
}
PLinkList p=Locate_LinkList(PLinkListPoint,i);
PLinkList NodeAdd=new LinkList;
if(!NodeAdd)
{
cout < <"分配空间失败！" < <endl;
return (-2);
}
NodeAdd->data=DataX;
NodeAdd->Next=p->Next;
p->Next=NodeAdd;
return (1);
}
/ ****************逆置操作****************************/
//算法思路：首先将单链表拆开成一个空表和一个不带头结点的单链表，然后将不带头结点的从第一个元素依次取出，
//将其插入到H单链表的第一个位置
PLinkList Reverse_LinkList(PLinkList PLinkListPoint)
{
//返回参数：NULL链表不存在，成功返回逆置后的链表
if(!PLinkListPoint)
{
return (NULL);
}
PLinkList p,q;
p=PLinkListPoint->Next;
PLinkListPoint->Next=NULL;
while(p)
{
q=p;
p=p->Next;
q->Next=PLinkListPoint->Next;
PLinkListPoint->Next=q;
}
return (PLinkListPoint);
}
/ ****************返回指定序号结点元素值**************/
int ReturnValue_LinkList(PLinkList PLinkListPoint,int i)
{
//返回值：指定序号结点元素值
PLinkList p=Locate_LinkList(PLinkListPoint,i);
return p->data;
}
//
int ModifyData_LinkList(PLinkList PLinkListPoint,int i,DataType DataX)
{
//返回参数：-1表不存在,1成功
if(!PLinkListPoint)
{
cout < <"表不存在！" < <endl;
return (-1);
}
PLinkList p=Locate_LinkList(PLinkListPoint,i 1);
p->data=DataX;
return (1);
}
/ 检查单链表是否为空*****************@/
int CheckEmpty_LinkList(PLinkList PLinkListPoint)
{
//返回参数：-1表不存在,0不为空，1空
if(!PLinkListPoint)
{
cout < <"表不存在！" < <endl;
return (-1);
}
if(!PLinkListPoint->Next)
{
cout < <"链表为空！" < <endl;
return (1);
}
else
{
cout < <"链表不为空！" < <endl;
return (0);
}
}
/ 打印(遍历)链表操作******************/
void Print_LinkListData(PLinkList H)
{
if(!H)
{
cout < <"链表不存在！" < <endl;
}
PLinkList current=H->Next;
while(current)
{
cout < <current->data < <'\t';
current=current->Next;
}
cout < <endl;
}
//////////////////////////////////////////////////////////////////////////////
//main for test
int main()
{
int i=-1,j=-1,choice;
long data=0;
PLinkList PLinkListPoint1,PLinkListPoint2;
cout < <"//主本程序主要用于实现单链表操作，请先执行1或2操作，建立单链表，否则将出现非法操作，感谢使用本程序！" < <endl;
cout < <"\t***************************************** \n";
cout < <" ¦ 单链表操作及其实现 ¦\n";
cout < <" ¦ ¦\n";
cout < <" ¦************************* ¦\n";
cout < <" ¦ 1.头插法创建并填充链表 ¦\n";
cout < <" ¦ 2.尾插法创建并填充链表 ¦\n";
cout < <" ¦ 3.检查该链表是否为空 ¦\n";
cout < <" ¦ 4.按位置检索操作 ¦\n";
cout < <" ¦ 5.按元素检索操作 ¦\n";
cout < <" ¦ 6.按位置插入结点操作 ¦\n";
cout < <" ¦ 7.按位置删除结点操作 ¦\n";
cout < <" ¦ 8.修改指定序号结点元素值 ¦\n";
cout < <" ¦ 9.返回指定序号结点元素值 ¦\n";
cout < <" ¦ 10.逆置链表操作 ¦\n";
cout < <" ¦ 11.求链表长度操作 ¦\n";
cout < <" ¦ 12.打印(遍历)链表操作 ¦\n";
cout < <" ¦ 13.销毁链表操作 ¦\n";
cout < <" ¦ 0.退出程序 ¦\n";
cout < <" *************************** \n";
cout < <" ¦ Code By ~For_ ¦\n";
cout < <"\t***************************************** \n";
while(1)
{
cout < <"请输入你想要实现的操作：";
cin>>choice;
switch(choice)
{
//1.头插法创建并填充链表,2.尾插法创建并填充链表
case 1:
case 2:
if(choice==1)
{
PLinkListPoint1=Create_ReverseLinkList();
break;
}
else
{
PLinkListPoint1=Create_SeqLinkList();
break;
}
case 3:
CheckEmpty_LinkList(PLinkListPoint1);
break;
//按位置查找数据
case 4:
cout < <"请输入你要查找元素的位置：";
cin>>i;
PLinkListPoint2=Locate_LinkList(PLinkListPoint1,i);
if(PLinkListPoint2)
{
cout < <"要查找的元素为：" < <PLinkListPoint2->data < <endl;
}
i=-1;
break;
//按位数查找
case 5:
cout < <"请输入你要查找元素的值：";
cin>>j;
PLinkListPoint2=Locate_LinkList(PLinkListPoint1,j);
if(PLinkListPoint2)
{
cout < <"要查找的元素为：" < <&PLinkListPoint2 < <endl;
}
j=-1;
break;
//按位置插入结点操作
case 6:
cout < <"请输入你想插入结点的位置，元素值：";
cin>>i>>data;
if(Insert_LinkList(PLinkListPoint1,i,data)==1)
{
cout < <"插入成功！" < <endl;
}
i=-1;
data=0;
break;
//按位置删除结点操作
case 7:
cout < <"请输入你想删除结点的位置：";
cin>>i;
if(Del_LinkList(PLinkListPoint1 , i)==1)
{
cout < <"删除成功！" < <endl;
}
i=-1;
break;
//修改指定序号结点元素值
case 8:
cout < <"请输入你想修改的指定元素序号和新的元素值！";
cin>>i>>data;
if(ModifyData_LinkList(PLinkListPoint1,i,data)==1)
{
cout < <"修改成功！" < <endl;
}
i=-1;
data=0;
break;
//返回指定序号结点元素值
case 9:
cout < <"请输入你想返回元素值的指定序号：";
cin>>i;
cout < <"指定序号元素值为：" < <ReturnValue_LinkList(PLinkListPoint1,i) < <endl;
i=-1;
break;
//逆置链表操作
case 10:
Reverse_LinkList(PLinkListPoint1);
cout < <"逆置链表成功！" < <endl;
break;
//求链表长度操作
case 11:
if(Length_LinkList(PLinkListPoint1)!=-1)
{
cout < <"链表长度：" < <Length_LinkList(PLinkListPoint1) < <endl;
}
break;
//打印(遍历)链表操作
case 12:
Print_LinkListData(PLinkListPoint1);
break;
//销毁链表操作
case 13:
if(Destory_LinkList(&PLinkListPoint1))
{
cout < <"销毁单链表成功！" < <endl;
}
//退出程序
case 0:
exit(0);
break;
default:
cout < <"输入参数错误！" < <endl;
break;
}
}
return 0;
}
网友回复:精心编写啊。。··
网友回复:look look
网友回复:虽然不想打击你的积极性，但是写的不怎么样，没有体现C 语言的特点。还是看STL的链表吧。
网友回复:怎么是用struct定义的啊？？！
网友回复:楼主，有以下不足：
1，没有很好的封装数据；
2，没有实现人机交互操作与数据处理相分离；
3，居然没用泛型编程……
看list源代码。
呵呵，说说而已~
网友回复:谢谢6楼。。
我发出来就是需要你们这样的很直接的提出我的不足。。
因为是学C语言版的教程，这个是一个实验，我开始并没有非凡想把他用类给封装起来。（课比较多，有点忙）
以后我都尽量用类给他封装起来。
2，没有实现人机交互操作与数据处理相分离；
这个是为什么，我的主函数人机交互操作很差，由于刚接触数据结构这么课程，主要在dos下面测试，6楼能不能给点意见。。
什么样的才是一个好的。。实现人机交互操作与数据处理相分离；
3居然没用泛型编程…… 看list源代码
这个我都没听过饿。。- -。。俺比较菜。。大二。。
什么是泛型编程，list源代码。。是什么东西？
真的很想知道。。
谢谢。。期待你们的回复啊。
网友回复:更改：
2，没有实现人机交互操作与数据处理相分离；
这个是为什么，我的主函数人机交互操作很差吗？
我感觉很可以哈。。
什么样的才是比较好的哇。。
网友回复:
扯不上边。
既然是小师弟，那就帮忙评价一下：
主要方面
1、你应当用class来将一个链表封装起来，而不是用一大堆函数。这不是C 语言的特点。假如说C来写，这个倒是不错。
2、用template，相关的东西可以查书。
3、你的菜单什么和程序的链表操作，还有输入输出混在一起，没有将输入输出和计算分离。
4、出错用抛出异常。
次要方面：
1、报错用cerr而不是cout。
网友回复:结论：假如说是初学者，质量的确不错。但是假如老板看到这种代码，程序员的饭碗肯定不保。
网友回复:幸好我是初学者。。
被打击了哈。。。
原来是c的，我就把printf换成cout。。scanf换成cin了。。
能不能给个示例。。
怎麽样的才是好的，高质量的
网友回复:先打好基础再说，以你现在的水平还看不懂STL的list
网友回复:呵呵，刚开始的话，还不错啦！
不过离程序员的水平还很远，多多学习呀!
去看一看STL的源码，对你帮助会很大的。
网友回复:我自己写了个玩：
- C/C code
Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ struct Node { unsigned int uiValue; Node* pNext; }; struct List { public: List(void) { this->init(); } ~List(void) { this->freeAll(); this->end(); } private: bool init(void); bool end(void); public: bool freeAll(void); bool freeOne(Node* pNode); bool insert(Node* pNode); bool updata(Node* pNode){return false;}; Node* find(Node* pNode){return false;}; private: Node* PHead; // 表头 Node* PTail; // 指向表尾元素 }; bool List::init() { PHead = new Node; PHead->pNext = 0; PTail = PHead; return true; } bool List::end() { PTail = 0; delete PHead; PHead = 0; return true; } bool List::freeAll() { Node* ptemp = 0; if(!PHead) return true; if(PHead ->pNext == 0) return true; ptemp = PHead->pNext; while(ptemp) { Node* pTempNex = ptemp->pNext; if(ptemp) { delete ptemp; ptemp = 0; } ptemp = pTempNex; } PTail = PHead; PHead ->pNext = 0; return true; } bool List::freeOne(Node* pNode) { if(pNode == PHead) return false; Node* ptemp = 0; Node* pPre = 0; ptemp = PHead->pNext; pPre = PHead; while(ptemp) { if(ptemp == pNode)break; pPre = ptemp; ptemp = ptemp->pNext; } if(ptemp) { pPre->pNext = ptemp->pNext; delete ptemp; ptemp = 0; return true; } return false; } bool List::insert(Node* pNode) { pNode->pNext = 0; if(PHead ->pNext == 0) { PTail = PHead->pNext = pNode; } else { Node* pPre = PTail; PTail = 0; PTail = pPre->pNext = pNode; } return true; }
网友回复:Node* find(Node* pNode){return false;};
=》
Node* find(Node* pNode){return 0;};
网友回复:1,把数据打包成对象，封装起来，这个失眠下你个对喜爱难过的基础，当然，你这是C语言，也不要求了……
2，我觉得很重要，最好现在就应该有这个熟悉：数据处理——人机交互——分离！
一方面这么分离可以方便的修改，比如，我需要修改一个算法，这样我只要修改数据处理这一块就可以了，再比如，我需要做一个更方便的人机交互，这样我只要修改人机交互这一块就可以了。这样，两个模块相互分离，只通过函数接口相互接触，两者耦合性大大降低，代码维护性更高，软件才可以持续开发。
以后，应该学会把数据、资源等做成Dll，甚至Com控件，真正实现模块化。
你才大二，慢慢学习吧。
一家之言，拍砖无视~呵呵
网友回复:
无视COM控件，应当编译成.lib.so
网友回复:分离
实现
高内聚，低耦合~
好。·很好~。。
知道这个好的想法就好了。。被启发了。。
谢谢~
网友回复:学习下 ，面向对象~~
网友回复:用C 封装的链栈类。。
http://topic.csdn.net/u/20080525/15/2cc03660-0e51-446d-bc3a-0a0e2acf2f65.html
去看哈。。
谢谢
关键字：链表,基本,操作,实现,质量,
下一篇：下面没有链接了
文章评论
共有 0 位网友发表了评论 此处只显示部分留言 点击查看完整评论页面