单向链表查看源代码讨论查看历史
| 单向链表 |
单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。 通过指针连接起来，但是只能单向遍历的内存块。由于它是单向的，或者说不可逆的，所以我们可以把它比作我们的人生：小学->中学->大学->工作->养老。
如何实现
链表是一种重要的 数据结构，该结构由 节点组成。每个节点包含两部分数据，第一部分是节点本身的数据，第二部分是指向下一个节点的 指针。对于单向链表，链表中存在两个特殊的节点，分别为“头节点”和“尾节点”。头节点本身没有数据，只存储下一个节点的指针，尾节点只存储数据。结点的定义及对 线性表的操作如下：
首先，定义一个结点类用于对结点的描述。其中，私有成员Value用于储存节点本身的数据，Next用于存储下一个节点的指针，Previous用于存储上一个节点的指针。对于链表的操作，无非是进行节点的查找、插入和删除操作。代码如下：
// 结点类
publicclassListNode { publicListNode(intNewValue)//,intNewCurrent) { Value=NewValue; } //前一个 publicListNodePrevious; //后一个 publicListNodeNext; //值 publicintValue; ////指针 //publicintCurrent; } 然后定义了一个Clist类，主要对线性表基本操作的编程。其中包括，Head、Tail、Current三个指针和Append、MoveFrist、MovePrevious、MoveNext、MoveLast、Delete、InsertAscending、InsertUnAscending、Clear、 GetCurrentValue方法，用于实现移动、添加、删除、升序插入、降序插入、清空链表、取得当前的值等操作。代码如下：
/定义结点之后，开始类线性表的操作编程了.在ClIST类中,采用了，Head,Tail, Current，三个指针，使用Append，MoveFrist,MovePrevious，MoveNext,MoveLast,Delete,InsertAscending,InsertUnAscending,Clear实现移动，添加、删除,升序插入，降序插入，清空链表操作，GetCurrentValue（）方法取得当前的值。 publicclassClist { ///<summary> ///初始化线性表 ///</summary> publicClist() { //构造函数 //初始化 ListCountValue=0; Head=null; Tail=null; } //头指针 privateListNodeHead; //尾指针 privateListNodeTail; //当前指针 privateListNodeCurrent; //链表数据的个数 privateintListCountValue; 在链表尾部添加数据的代码如下：
///尾部添加数据 ///</summary> ///<paramname="DataVal ue"></param> publicvoidAppend(intDataValue)//,intDataCurrent) { ListNodeNewNode=newListNode(DataValue);//,DataCurrent); if(IsNull()) //如果头指针为空 { Head=NewNode; Tail=NewNode; } else { Tail.Next=NewNode; NewNode.P revious=Tail; Tail=NewNode; } Current=NewNode; //链表数据个数加一 ListCountValue+=1; } 删除当前位置的结点的代码如下：
///删除当前的数据 ///</summary> publicvoidDelete() { //若为空链表 if(!IsNull()) { //若删除头 if(IsBof()) { Head=Current.Next; Current=Head; ListCountValue-=1; return; } //若删除尾 if(IsEof()) { Tail=Current.Previous; Current=Tail; ListCountValue-=1; return; } //若删除 中间数据 Current.Previous.Next=Current.Next; Current=Current.Previous; ListCountValue-=1;
向后移动一个结点的代码如下：
//向后移动一个数据 ///</summary> publicvoidMoveNext() { if(!IsEof())Current=Current.Next; } 向前移动一个结点的代码如下：
///向前移动一个数据 ///</summary> publicvoidMoveP revious() { if(!IsBof())Current=Current.Previous; } 移动到第一个结点的代码如下：
///移动到第一个数据 ///</summary> publicvoidMoveFrist() { Current=Head; } 移动到最后一个结点的代码如下：
///移动到最后一个数据 ///</summary> publicvoidMoveLast() { Current=Tail; } 判断链表是否为空的代码如下：
///判断是否为空链表 ///</summary> ///<returns></returns> publicboolIsNull() { if(ListCountValue==0) returntrue; returnfalse; } 判断是否为链表的尾部的代码如下：
///判断是否为到达尾 ///</summary> ///<returns></returns> public boolIsEof() { if(Current==Tail) returntrue; returnfalse; } 判断是否为链表的头部的代码如下：
///判断是否为到达头部 ///</summary> ///<returns></returns> public boolIsBof() { if(Current==Head) returntrue; returnfalse; } 获取当前位置的值的代码如下：
///<summary> ///获取当前位置的值 ///</summary> ///<returns></returns> public intGetCurrentValue() { returnCurrent.Value; } 获取链表的结点数的代码如下：
///取得链表的数据个数 ///</summary> public intListCount { { returnListCountValue; } } 清空链表的代码如下：
//清空链表
///<summary>
///清空链表
///</summary>
publicvoidClear()
{
MoveFrist();
while(!IsNull())
{
//若不为空链表,从尾部删除
Delete();
}
}
在当前位置前插入结点的代码如下：
//在当前位置前插入数据
///<summary>
///在当前位置前插入数据
///</summary>
///<paramname="DataValue"></param>
publicvoidInsert(intDataValue)
{
ListNodeNewNode=newListNode(DataValue);
if(IsNull())
{
//为空表，则添加
Append(DataValue);
return;
}
if(IsBof())
{
//为头部插入
NewNode.Next=Head;
Head.Previous=NewNode;
Head=NewNode;
Current=Head;
ListCountValue+=1;
return;
}
//中间插入
NewNode.Next=Current;
NewNode.Previous=Current.Previous;
Current.Previous.Next=NewNode;
Current.Previous=NewNode;
Current=NewNode;
ListCountValue+=1;
}
进行升序插入的代码如下：
//进行升序插入
///<summary>
///进行升序插入
///</summary>
///<paramname="InsertValue"></param>
publicvoidInsertAscending(intInsertValue)
{
//参数：InsertValue插入的数据
//为空链表
if(IsNull())
{
//添加
Append(InsertValue);
return;
}
//移动到头
MoveFrist();
if((InsertValue<GetCurrentValue()))
{
//满足条件，则插入，退出
Insert(InsertValue);
return;
}
while(true)
{
if(InsertValue<GetCurrentValue())
{
//满族条件，则插入，退出
Insert(InsertValue);
break;
}
if(IsEof())
{
//尾部添加
Append(InsertValue);
break;
}
//移动到下一个指针
MoveNext();
}
}
进行降序插入的代码如下：
//进行降序插入
///<summary>
///进行降序插入
///</summary>
///<paramname="InsertValue"></param>
publicvoidInsertUnAscending(intInsertValue)
{
如何编辑
建立
- include "stdio.h"
- include "stdlib.h"
struct node
{
int num;
struct node * next;
};//定义一个接点，包括一个指向下一个接点的指针以及一个值num
struct node * creat()//一个函数返回的是指向结构体的一个指针
{
struct node * p,* head,* tail;//定义一个指向接点的指针 p head tail
int i;
head=tail=NULL;//开始都初始化是NULL
printf("input a number\n");
while(scanf("%d",&i)==1)//因为scanf（）函数的返回值是成功赋值的个数，此处只要是成功的赋值，就对了
{
p=(struct node *)malloc(sizeof(struct node));//动态的构造一块内存空间，返回的是指向接点的指针
p->num=i;//赋值
p->next=NULL;
if(head==NULL)
head=tail=p;//在头指针是NULL时候也就是说是一个空的单链，那么头尾都赋值是指针p
else
tail=tail->next;//当头指针不是指向NULL时候的话，就是说这个链是存在的，现在是加进去尾指针就向下进一个
tail->next=p;//把尾指针的下一个赋值是新建的这个指针（创建单向链表）
}
return head;//返回的是一个头指针，这也是单向链表的一个定义这个指针是指向接点的，头结点
}
插入 struct node * inlink(struct node * head,int a,int b)//定义一个函数和上面一样返回的东西一样，插入接点存储的值是b，这题目的意思是在接点的前面进行插入，或者是后面也可以，最好把题目意思告诉我
{
struct node * p1,* p2,* s;
s=(struct node *)malloc(sizeof(struct node));
s->num=b;
if(head==NULL)//假如一开始的时候单向链表是空的话
{
head=s;//头接点指针就被赋值为新建的这个接点
s->next=NULL;//接点内的指向下一个接点的指针就被赋值为NULL
}
if(head->num==a)//若头指针里面的值是a
{
s->next=head;//进行插入
head=s;
}
else//若不是a的大前提下
{
p1=head;
while((p1->num!=a)&&(p1->next!=NULL))//p1里面的值不是a，同时p1的下一个不是空的
{
p2=p1;
p1=p1->next;
}
if(p1->num==a)//若找到存在a的这个点的话，这种情况下在p1前插入新建的接点，
{
p2->next=s;
s->next=p1;
}
else//否则在p1后面插入
{
p1->next=s;
s->next=NULL;
}
}
return head;
}
删除
struct node * delink(struct node * head,int c)//删除接点
{
struct node * p,* q;
if(head==NULL)
printf("Error\n");
else if(head->num==c)//若头接点中的存储数字是c，就会删
{
p=head;
head=head->next;
}
else
{
p=head;
while((p->num!=c)&&(p->next!=NULL))
{
q=p;
p=p->next;
}
if(p->num!=c)
printf("can not find %d\n",c);
else//假如是找到这个c的话
{
q->next=p->next;
free(p);
}
}
return head;
}
void main()
{
struct node * ptr,* q,* r;
int i,j;
q=creat();
ptr=NULL;
while(q)
{
printf("%d->",q->num);
ptr=q->next ;
free(q);
q=ptr;
}//输出链表
printf("input the number to be inlinked\n");
scanf("%d",&i);
scanf("%d",&j);
r=inlink(creat(),i,j);//r为从头指针开始的
while(r)
{
printf("%d->",r->num);
ptr=r->next ;
free(r);//这里不对 因为上面是以r为循环结束与否否认一个判断条件的，你都把r给释放了，在哪来判定更别提输出，这个编译的时候是查不出的
r=ptr;//q=ptr;//应该是r=ptr;
}
printf("input the number to be dellinked\n");
scanf("%d",&i);
r=delink(creat(),i);
while(r)
{[1]
printf("%d->",r->num);
ptr=r->next ;
free(r);
r=ptr;//q=ptr;//同样这里也是r=ptr;
}