鏈表的基本操作

鏈表的基本操作：

1 創建鏈表 Linknode * createLink( int n )

2 求鏈表的長度 int lenthLink( Linknode *head )

3 鏈表的 插入 Linknode *insertNode( Linknode *head,int data,int key )

4 刪除鏈表的結點 Linknode *deleteNode(Linknode *head,int num);

5 鏈表的排序 Linknode *sortLink(Linknode *head);
6 鏈表的逆序 Linknode *invertLink(Linknode *head);

7 鏈表的某一個節點的查找 Linknode *locateN(Linknode *head,int num);
8 輸出鏈表 void printLink( Linknode *head )

1 創建鏈表

Linknode * createLink( int n )
{
int xValue;
Linknode *head,*p,*pre; //pre 和p建立連接的關系

cout<<"請輸入第1個數字： ";
cin>>xValue;
p=(Linknode*)malloc(sizeof(Linknode));
p->data=xValue;
p->next=NULL;
head=p;
pre=p;

for(int i=1;i<n;i++)
{
cout<<"請輸入第"<<i+1<<"個數字： ";
cin>>xValue;
p=(Linknode*)malloc(sizeof(Linknode));
p->data=xValue;
p->next=NULL;

pre->next=p;
pre=p;
}

printLink(head);
return head;
}

2 求鏈表的長度

int lenthLink( Linknode *head )
{
assert(head);
int num=0;
Linknode* p=head;

while(p)
{
num++;
p=p->next;
}

return num;
}

3 鏈表的 插入

Linknode *insertNode( Linknode *head,int data,int key )
{
assert(head!=NULL);
Linknode *s;
s=(Linknode*)malloc(sizeof(Linknode));
assert(s!=NULL);
s->data=data;
s->next=NULL;

Linknode *p=head;
//兩種結果： 1 找到執行插入） 2沒找到不執行插入）
while(p&&p->data!=key)
{
p=p->next;
}
if(p!=NULL&&p->data==key)
{
s->next=p->next;
p->next=s;
cout<<"插入成功了！！！"<<endl;
}
else
{
cout<<"插入失敗！！！"<<endl;
}

printLink(head);
return head;
}

4 刪除鏈表的結點

Linknode * deleteNode( Linknode *head,int num )
{
assert(head!=NULL);
Linknode *p=head;
Linknode *pre=head;
int n=1; //n=0 是不對的

while(p&&n<num)
{
n++;
pre=p;
p=p->next;
}
if(n!=num)
{
cout<<"刪除失敗！！！"<<endl;
}
else
{
pre->next=p->next;
free(p);
p=NULL;
cout<<"刪除成功！！！"<<endl;
printLink(head);
}
return head;
}

5 鏈表的排序

//排序的話，只要改變linknode->data就可以了，鏈接關系不用管的。
Linknode * sortLink( Linknode *head )
{
assert(head!=NULL);
//Linknode *p=head;
int tmp;
for(Linknode *p1=head;p1!=NULL;p1=p1->next)
{
for(Linknode *p2=p1->next;p2!=NULL;p2=p2->next)
{
//交換排序其實就是冒泡排序的了）
if(p1->data>p2->data)
{
tmp=p1->data;
p1->data=p2->data;
p2->data=tmp;
}
}
}

printLink(head);
return head;
}

6 鏈表的逆序

Linknode * invertLink( Linknode *head )
{
assert(head!=NULL);
Linknode *p,*pre,*tmp; //pre和p 建立連接的關系，q保持p的下一個移動的結點
p=head;
tmp=head;
pre=NULL;

while(p!=NULL)
{
tmp=p->next;
p->next=pre; //1 建立連接關系
pre=p; //2 pre和p）往後面移動
p=tmp;
}

head=pre;
printLink(head);
return head;
}

下面是 使用遞歸的方法來做到：

Linknode * invertLink_Recursive( Linknode *head )
{
    Linknode* new_head=head;
    if(head==NULL || head->next==NULL)
        return head;
                      
    new_head = invertLink_Recursive(head->next);
    cout<<"輸出"<<head->data<<endl;
    head->next->next=head;
    head->next=NULL;     //防止鏈表成為一個環,對於頭結點而言的
    return new_head;
}

直接逆序輸出 節點的數值

//1 退出條件  2 遞歸   3 最後的輸出
void printInverseLink( Linknode *head )
{
    if(head==NULL)
        return;
    //cout<<head->data<<endl;
    printInverseLink(head->next);
    cout<<head->data<<endl;
}

7 鏈表的某一個節點的查找

Linknode* locateN( Linknode *head,int num )
{
assert(head!=NULL);
Linknode *p=head;
int n=1; //int n=0 是錯誤的(好好考慮這一點)

while(p!=NULL&&n<num)
{
n++;
p=p->next;
}
if(n==num)
{
cout<<"查找成功！！！";
cout<<"該節點的數值是："<<p->data<<endl;
return p;
}
else
{
cout<<"查找失敗！！！"<<endl;
return NULL;
}
}

8 輸出鏈表

void printLink( Linknode *head )
{
Linknode* pNode=head;

cout<<"這個鏈表的數據是："<<endl;
while(pNode)
{
cout<<pNode->data<<endl;
pNode=pNode->next;
}
}

測試代碼為：

Linknode *theLink;
int numNode;
cout<<"請輸入創建的鏈表的個數";
cin>>numNode;
theLink=createLink(numNode);
cout<<"鏈表的長度是："<<lenthLink(theLink)<<endl;

//theLink=insertNode(theLink,6,2);
//theLink=deleteNode(theLink,3);
//theLink=sortLink(theLink);
//theLink=invertLink(theLink);
Linknode *p=locateN(theLink,3);