單向鍊表
| 單向鍊表 |
單向鍊表（單鍊表）是鍊表的一種，其特點是鍊表的鏈接方向是單向的，對鍊表的訪問要通過順序讀取從頭部開始。 通過指針連接起來，但是只能單向遍歷的內存塊。由於它是單向的，或者說不可逆的，所以我們可以把它比作我們的人生：小學->中學->大學->工作->養老。
目錄
如何實現
鍊表是一種重要的 數據結構，該結構由 節點組成。每個節點包含兩部分數據，第一部分是節點本身的數據，第二部分是指向下一個節點的 指針。對於單向鍊表，鍊表中存在兩個特殊的節點，分別為「頭節點」和「尾節點」。頭節點本身沒有數據，只存儲下一個節點的指針，尾節點只存儲數據。結點的定義及對 線性表的操作如下：
首先，定義一個結點類用於對結點的描述。其中，私有成員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;
}