鏈表的一些操作（新建，輸出，刪除，插入，查找，逆序，排序，釋放鏈表，鏈表長度計算，查找倒數(shù)第k節(jié)點的元素）

一. 鏈表的概念

1、鏈表是物理存儲單元上非連續(xù)的、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表的指針地址實現(xiàn)，有一系列結(jié)點（地址）組成，結(jié)點可動態(tài)的生成。

2、結(jié)點包括兩個部分：
一、存儲數(shù)據(jù)元素的數(shù)據(jù)域（內(nèi)存空間）
二、存儲指向下一個結(jié)點地址的指針域。
3、相對于線性表順序結(jié)構(gòu)，操作復(fù)雜。

二.鏈表的作用

1、實現(xiàn)數(shù)據(jù)元素的存儲按一定順序儲存，允許在任意位置插入和刪除結(jié)點。

2、包括單向結(jié)點，雙向結(jié)點，循環(huán)接點

3、C/C++/Java都可以實現(xiàn)

三.鏈表的優(yōu)缺點

優(yōu)點：鏈表實現(xiàn)數(shù)據(jù)元素儲存的順序儲存，是連續(xù)的

缺點：因為含有大量的指針域，所以占用空間大，同時因為只有頭結(jié)點（后面說明）是明確知道地址的，所以查找鏈表中的元素需要從頭開始尋找，非常麻煩。

四.建立一個鏈表結(jié)點結(jié)構(gòu)

struct linked_list
{
    int num;
    linked_list *next;
};

五.對鏈表的操作

介于本人初學(xué)鏈表，只能對單鏈表進行一些基礎(chǔ)操作

1.新建鏈表（新建一個長度為n的鏈表）

linked_list* create(linked_list *head,int n)
{
    linked_list *ptr,*tail=NULL;
    head=NULL;
    for(int i=0;i<n;i++)
    {
        ptr=(linked_list*)malloc(sizeof(linked_list));
        scanf("%d",&ptr->num);
        ptr->next=NULL;
        if(!head)
            head=ptr;//對首節(jié)點進行賦值
        else
            tail->next=ptr;//新增鏈表尾部
        tail=ptr;//尾節(jié)點移動 
    }
    return head;
}//新建一個長度為n的鏈表并返回首節(jié)點的地址

2.刪除（釋放）鏈表

在單鏈表中我們在程序的最后加上一個釋放內(nèi)存的方法或者操作，這是一個很好的習(xí)慣。（我對這個操作其實不是很懂，有問題請指出，以下是我對代碼）

void release(linked_list *head)
{
    linked_list *ptr=head;
    while(head)
    {   
        ptr=head;
        head=head->next;
        free(ptr);
    }
    free(head); 
    if(!head)
        cout<<"鏈表已刪除，請重新輸入鏈表長度\n"; 
}//刪除整個鏈表 

3.插入一個數(shù)據(jù)到鏈表中的某個位置

linked_list* insert(linked_list* head, linked_list* ptr, int n, int l)
{
    linked_list* h = head;
    if (n == 1)//插入到第一個位置
    {
        ptr->next = head;
        head = ptr;
    }
    else
    {
        for (int i = 0;i < n - 2;i++)
            h = h->next;
        ptr->next = h->next;
        h->next = ptr;
    }
    return head;
}//插入某個數(shù)據(jù)到n位置 ，并返回首節(jié)點

4.刪除鏈表中的第n個位置的的節(jié)點

我用的方法是覆蓋法
當(dāng)需要刪除一個節(jié)點p時，只需要將p的前一個節(jié)點的next賦為p->next,但是由于是單向的，只知道p，無法知道p前一個節(jié)點，所以需要轉(zhuǎn)換思路。將p下一個的節(jié)點覆蓋到p節(jié)點即可，這樣就等效于將p刪除了。（當(dāng)然呢我這并沒有把那個節(jié)點給釋放掉，不知道會不會出問題）

linked_list* del(linked_list* head, int l, int n)
{
    linked_list* h = head;
    if (l == 1)//刪除首節(jié)點
        head = head->next;
    else//刪除中間節(jié)點
    {
        for (int i = 0;i < l - 2;i++)
            h = h->next;
        h->next = h->next->next;
    }
    return head;
}//刪除第l個位置的節(jié)點，并返回首節(jié)點

5.對單向鏈表第a到第b位置的節(jié)點反轉(zhuǎn)

思路是這樣的：
要求將一帶鏈表頭List head的單向鏈表逆序。

分析：

1). 若鏈表為空或只有一個元素，則直接返回；

2). 設(shè)置兩個前后相鄰的指針p,q. 將p所指向的節(jié)點作為q指向節(jié)點的后繼；

3). 重復(fù)2),直到q為空

4). 調(diào)整鏈表頭和鏈表尾

Alt

linked_list* reverse(linked_list *head,int a,int b,int n)
{
    linked_list *p=head,*q=head->next,*s=NULL,*h=head;
    if(a>b)
    {
        int temp=a;
        a=b;
        b=temp;
    }
    
    int qq=b-a,t=a-2;
    if(head==NULL||head->next==NULL||a==b)//當(dāng)鏈表為空或者鏈表只有一個節(jié)點或者a==b時候，直接返回head 
        return head;

    if(a==1&&b>1)//a==1時候?qū)︽湵韆到b進行逆序 
    {
        b--;
        while(b--)
        {
            s=q->next;
            q->next=p;
            p=q;
            q=s;
        }
        head->next=q;
        head=p;
        return head;
    }
    
    //a!=1的時候?qū)到b位置進行逆序 
    a--;
    
    while(a--)
    {
        p=p->next;
        q=q->next;
    }//p移動到第a個位置，q移動到a+1個位置
    while(t--)
        h=h->next;//h是p的前一個位置
    
    while(qq--)//對第a個位置到第b個位置的鏈表進行倒序 
    {
        s=q->next;
        q->next=p;
        p=q;
        q=s;
    }
    h->next->next=q;
    h->next=p;
    return head;
}//對鏈表a到b位置的數(shù)據(jù)逆序并返回head的位置； 

6.查找鏈表中數(shù)據(jù)為a的第一個節(jié)點的位置

int find(linked_list *head,int a,int n)
{
    int sum=1;
    while(head)
    {
        if(head->num==a)
            break;
        sum++;
        head=head->next;
    }
    if(sum>n)
        return -1;
    return sum;
}//查找數(shù)據(jù)為a的節(jié)點的位置 

7.鏈表排序操作

linked_list* linked_listsort(linked_list *head,int p)//p判斷進行升序還是降序操作 
{
    linked_list *slow=head,*fast=NULL;
    int temp;
    if(p==1)//升序排序 
    {
        while(slow)//冒泡思想，就不解釋了 
        {
            fast=slow->next;
            while(fast)
            {
                if(fast->num<slow->num)
                {
                    temp=slow->num;
                    slow->num=fast->num;
                    fast->num=temp;
                }
                fast=fast->next;
            }
            slow=slow->next;
        } 
        cout<<"你已進行了升序排序，查看排序結(jié)果請輸入1\n"; 
    }
    else//降序排序 
    {
        while(slow)
        {
            fast=slow->next;
            while(fast)
            {
                if(fast->num>slow->num)
                {
                    temp=slow->num;
                    slow->num=fast->num;
                    fast->num=temp;
                }
                fast=fast->next;
            }
            slow=slow->next;
        } 
        cout<<"你已進行了降序排序，查看排序結(jié)果請輸入1\n"; 
    }
    return head;
}

8.計算鏈表長度

int lengthofLinklist(linked_list *head) 
{
    int len = 0;
    while(head)
    {
        head=head->next;
        len++;
    }
    return len;
}//計算鏈表長度

9.查找鏈表倒數(shù)第k個元素

//兩次遍歷查找倒數(shù)第k元素
linked_list* findKthTail(linked_list *head, int k) 
{
    if (head==NULL || k<=0) return NULL; 
    int len = 0;
    linked_list *root=head;
    while (head) 
    {
        head=head->next;
        len++;
    }
    if (len<k) return NULL;
    int countdown = len-k;
    while (countdown--)
        root=root->next;
    return root;
}

//快慢指針 查找倒數(shù)第k元素
linked_list* findKthTail2(linked_list* head, int k) 
{
    if (head == NULL || k <= 0) return NULL;
    linked_list *slow = head;
    linked_list *fast = head;
    for(int i=0;i<k;i++) 
    {  //快指針先走k步
        if(fast) 
            fast = fast->next;
        else 
            return NULL;//如果k>鏈表長度 返回NULL； 
    }
    while(fast) //相當(dāng)于slow移動了 鏈表長度len - k步； 
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

10.代碼整合

#include<bits/stdc++.h>
using namespace std;
struct linked_list
{
    int num;
    linked_list* next;
};

linked_list* reverse(linked_list* head, int a, int b, int n)
{
    linked_list* p = head, * q = head->next, * s = NULL, * h = head;
    if (a > b)
    {
        int temp = a;
        a = b;
        b = temp;
    }

    int qq = b - a, t = a - 2;
    if (head == NULL || head->next == NULL || a == b)//當(dāng)鏈表為空或者鏈表只有一個節(jié)點或者a==b時候，直接返回head 
        return head;

    if (a == 1 && b > 1)//a==1時候?qū)︽湵韆到b進行逆序 
    {
        b--;
        while (b--)
        {
            s = q->next;
            q->next = p;
            p = q;
            q = s;
        }
        head->next = q;
        head = p;
        return head;
    }

    //a!=1的時候?qū)到b位置進行逆序 
    a--;

    while (a--)
    {
        p = p->next;
        q = q->next;
    }//p移動到第a個位置，q移動到a+1個位置
    while (t--)
        h = h->next;//h是p的前一個位置

    while (qq--)//對第a個位置到第b個位置的鏈表進行倒序 
    {
        s = q->next;
        q->next = p;
        p = q;
        q = s;
    }
    h->next->next = q;
    h->next = p;
    return head;
}//對鏈表a到b位置的數(shù)據(jù)逆序并返回head的位置； 

//head是首節(jié)點，l是待刪除位置，n是鏈表長度
//這個函數(shù)的l和n和上個插入函數(shù)的不大一樣，無傷大雅吧，嘿嘿
linked_list* del(linked_list* head, int l, int n)
{
    linked_list* h = head;
    if (l == 1)//刪除首節(jié)點
        head = head->next;
    else//刪除中間節(jié)點
    {
        for (int i = 0;i < l - 2;i++)
            h = h->next;
        h->next = h->next->next;
    }
    return head;
}//刪除第l個位置的節(jié)點，并返回首節(jié)點

//head是首節(jié)點，ptr是存放待插入數(shù)據(jù)的節(jié)點，l是鏈表長度，n是待插入的位置
linked_list* insert(linked_list* head, linked_list* ptr, int n, int l)
{
    linked_list* h = head;
    if (n == 1)//插入到第一個位置
    {
        ptr->next = head;
        head = ptr;
    }
    else
    {
        for (int i = 0;i < n - 2;i++)
            h = h->next;
        ptr->next = h->next;
        h->next = ptr;
    }
    return head;
}//插入某個數(shù)據(jù)到n位置 ，并返回首節(jié)點


void release(linked_list* head)
{
    linked_list* ptr = head;
    while (head)
    {
        ptr = head;
        head = head->next;
        free(ptr);
    }
    free(head);
    if (!head)
        cout << "鏈表已刪除，請重新輸入鏈表長度\n";
}//刪除整個鏈表 

linked_list* create(linked_list* head, int n)
{
    linked_list* ptr, * tail = NULL;
    head = NULL;
    for (int i = 0;i < n;i++)
    {
        ptr = (linked_list*)malloc(sizeof(linked_list));
        cin >> ptr->num;
        ptr->next = NULL;
        if (!head)
            head = ptr;//對首節(jié)點進行賦值
        else
            tail->next = ptr;//新增鏈表尾部
        tail = ptr;//尾節(jié)點移動 
    }
    return head;
}//新建一個長度為n的鏈表并返回首節(jié)點的地址

int find(linked_list* head, int a, int n)
{
    int sum = 1;
    while (head)
    {
        if (head->num == a)
            break;
        sum++;
        head = head->next;
    }
    if (sum > n)
        return -1;
    return sum;
}//查找數(shù)據(jù)為a的節(jié)點的位置 

int lengthofLinklist(linked_list* head)
{
    int len = 0;
    while (head)
    {
        head = head->next;
        len++;
    }
    return len;
}//計算鏈表長度

linked_list* linked_listsort(linked_list* head, int p)//p判斷進行升序還是降序操作 
{
    linked_list* slow = head, * fast = NULL;
    int temp;
    if (p == 1)//升序排序 
    {
        while (slow)//冒泡思想，就不解釋了 
        {
            fast = slow->next;
            while (fast)
            {
                if (fast->num < slow->num)
                {
                    temp = slow->num;
                    slow->num = fast->num;
                    fast->num = temp;
                }
                fast = fast->next;
            }
            slow = slow->next;
        }
        cout << "你已進行了升序排序，查看排序結(jié)果請輸入1\n";
    }
    else//降序排序 
    {
        while (slow)
        {
            fast = slow->next;
            while (fast)
            {
                if (fast->num > slow->num)
                {
                    temp = slow->num;
                    slow->num = fast->num;
                    fast->num = temp;
                }
                fast = fast->next;
            }
            slow = slow->next;
        }
        cout << "你已進行了降序排序，查看排序結(jié)果請輸入1\n";
    }
    return head;
}

//兩次遍歷查找倒數(shù)第k元素
linked_list* findKthTail(linked_list* head, int k)
{
    if (head == NULL || k <= 0) return NULL;
    int len = 0;
    linked_list* root = head;
    while (head)
    {
        head = head->next;
        len++;
    }
    if (len < k) return NULL;
    int countdown = len - k;
    while (countdown--)
        root = root->next;
    return root;
}
//快慢指針 查找倒數(shù)第k元素
linked_list* findKthTail2(linked_list* head, int k)
{
    if (head == NULL || k <= 0) return NULL;
    linked_list* slow = head;
    linked_list* fast = head;
    for (int i = 0;i < k;i++)
    {  //快指針先走k步
        if (fast)
            fast = fast->next;
        else
            return NULL;//如果k>鏈表長度 返回NULL； 
    }
    while (fast) //相當(dāng)于slow移動了 鏈表長度len - k步； 
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

int main()
{
    int n, q, op, a, b, p, k;
    cout << "請輸入鏈表長度\n";
    while (cin >> n)
    {
        linked_list* head;
        head = (linked_list*)malloc(sizeof(linked_list));
        cout << "請輸入" << n << "個數(shù)據(jù)存入鏈表\n";
        head = create(head, n);
        cout << "請輸入你要進行的操作:\n";
        cout << "1.輸出鏈表\n";
        cout << "2.刪除鏈表第q個位置的數(shù)據(jù)\n";
        cout << "3.輸入一個數(shù)據(jù)插入到第q個位置\n";
        cout << "4.對鏈表a到b位置的數(shù)據(jù)進行逆序\n";
        cout << "5.查找某個元素所在節(jié)點的位置\n";
        cout << "6.對鏈表進行排序\n";
        cout << "7.查找鏈表導(dǎo)數(shù)第k個元素\n";
        cout << "8.刪除并釋放鏈表\n";
        while (1)
        {
            linked_list* h = head;
            cin >> op;
            if (op == 1)
            {
                h = head;
                cout << "長度為" << lengthofLinklist(h) << "的鏈表為:\n";
                while (h)
                {
                    cout << h->num << " ";
                    h = h->next;
                }
                cout << endl << endl << "你還要進行什么操作？" << endl;
            }
            else if (op == 2)
            {
                cout << "請輸入你要刪除的位置:";
                cin >> q;
                head = del(head, q, n);
                cout << "你已刪除第" << q << "位置的數(shù)據(jù)，要看輸出結(jié)果請輸入1\n";
                n--;//鏈表長度-1 
            }
            else if (op == 3)
            {
                linked_list* ptr = NULL;
                ptr = (linked_list*)malloc(sizeof(linked_list));
                cout << "請輸入待插入的數(shù)據(jù):";
                cin >> ptr->num;
                ptr->next = NULL;
                cout << "你要將" << ptr->num << "這個數(shù)據(jù)插入哪個位置？\n" << "請輸入待插入的位置:";
                cin >> q;
                head = insert(head, ptr, q, n);
                cout << "要看輸出結(jié)果請輸入1\n";
                n++;//鏈表長度+1； 
            }
            else if (op == 4)
            {
                cout << "請輸入a和b，對鏈表第a位置和第b位置的鏈表反轉(zhuǎn)\n";
                cin >> a >> b;
                head = reverse(head, a, b, n);
                cout << "已對鏈表第" << a << "到第" << b << "位置的數(shù)據(jù)進行了反轉(zhuǎn)\n";
                cout << "要看輸出結(jié)果請輸入1\n";
            }
            else if (op == 5)
            {
                cout << "請輸入你要查找的元素:";
                cin >> a;
                int node = find(head, a, n);
                if (node < 0)
                    cout << "鏈表中沒有這個元素\n";
                else
                    cout << a << "在第" << node << "個位置\n";
                cout << endl << "你還要進行什么操作？" << endl;
            }
            else if (op == 6)
            {
                cout << "你要進行升序（1）排序還是降序（2）排序？請輸入你選擇的排序方法:";
                cin >> p;
                head = linked_listsort(head, p);

            }
            else if (op == 7)
            {
                cout << "請輸入你想查找鏈表中倒數(shù)第幾個節(jié)點位置的值：";
                cin >> k;
                if (k > lengthofLinklist(head))
                {
                    cout << "輸入的長度不合法，此時鏈表長度為：" << lengthofLinklist(head);
                    cout << "請重新輸入7 進行此操作\n";
                }
                else
                {
                    linked_list* q = findKthTail(head, k);
                    cout << "鏈表中倒數(shù)第" << k << "個位置節(jié)點的值為：" << q->num << endl << "你還要進行什么操作？" << endl;
                }
            }
            else if (op == 8)
            {
                release(head);
                break;
            }
            else
                cout << "輸入的操作不對哦！\n請重新輸入\n";
        }
    }
    return 0;
}

在借鑒了好多大牛寫的博客之后，寫出了我第一篇博客；
希望有任何問題大家可以指出，我會改進的?。?！