單鏈表的創建

　　1.單鏈表的定義

typedef struct listNode//定義鏈表結構體
{
    int data;
    struct listNode* next;
    int length;
}listNode , *LinkList;
void init(LinkList& l)//初始化鏈表
{
    l = (LinkList)malloc(sizeof(listNode*));
    l->next = nullptr;
}

　　2.頭插法構建單鏈表

void create_LinkList_head(LinkList& l, const int x)//頭插法創建鏈表
{
    listNode* new_node;
    new_node = (listNode*)malloc(sizeof(listNode));
    new_node->next = l->next;
    l->next = new_node;
    new_node->data = https://www.cnblogs.com/ljz-gy/p/x;
    l->length++;
}

　　3.尾插法構建單鏈表

void create_LinkList_tail(LinkList& l, const int x)//尾插法創建鏈表
{
    listNode* new_node;
    listNode* tail_node;
    new_node = (listNode*)malloc(sizeof(listNode));
    tail_node = l;
    while (tail_node->next)
    {
        tail_node = tail_node->next;
    }
    new_node->data = https://www.cnblogs.com/ljz-gy/p/x;
    new_node->next = nullptr;
    tail_node->next = new_node;
    l->length++;
}

　　4.在指定位置插入元素

void insert_x_pos(LinkList& l, const int x,  int pos)//在鏈表的指定位置插入元素
{
    listNode* now_node;
    listNode* new_node;
    new_node = (listNode*)malloc(sizeof(listNode));
    new_node->data = https://www.cnblogs.com/ljz-gy/p/x;
    now_node = l;
    while (pos-- > 1)
    {
        now_node = now_node->next;
    }
    new_node->next = now_node->next;
    now_node->next = new_node;
    l->length++;
}

　　5.洗掉某個位置的元素

int delete_pos(LinkList& l, const int pos)//洗掉某個位置的元素
{
    listNode* tem_node;
    listNode* del_node;
    tem_node = l;
    int elem;
    for(int x = 1; x < pos; x++)
    {
        tem_node = tem_node->next;
    }
    elem = tem_node->next->data;
    del_node = tem_node->next;
    tem_node->next = tem_node->next->next;
    free(del_node);
    l->length--;
    return elem;
}

　　6.更改某個位置的元素

void update_x_pos(LinkList& l, const int x, const int pos)//改變某個位置的元素
{
    listNode* tem_node;
    tem_node = l;
    for(int i = 1; i < pos; i++)
    {
        tem_node = tem_node->next;
    }
    tem_node->next->data = https://www.cnblogs.com/ljz-gy/p/x;
}

　　7.查找某個位置的元素

int find_pos(LinkList& l, const int pos)//查找某個位置的元素
{
    listNode* tem_node;
    tem_node = l;
    for(int i = 1; i < pos; i++)
    {
        tem_node = tem_node->next;
    }
    return tem_node->next->data;
}

　　8.列印鏈表

void print_LinkList(LinkList& l)//列印鏈表
{
    listNode* now_node;
    now_node = l;
    while(now_node->next)
    {
        std::cout<<now_node->next->data<<" ";
        now_node = now_node->next;
    }
    std::cout<<std::endl;
}

　　9.獲取鏈表的長度

int get_lenght(const LinkList&l)
{
    return l->length;
}

　　完整代碼

//list_with_pointer.h
#ifndef _LIST_WITH_POINTER_
#define _LIST_WITH_POINTER_
#include<malloc.h>
typedef struct listNode//定義鏈表結構體
{
    int data;
    struct listNode* next;
    int length;
}listNode , *LinkList;
void init(LinkList& l)//初始化鏈表
{
    l = (LinkList)malloc(sizeof(listNode*));
    l->next = nullptr;
}
void create_LinkList_head(LinkList& l, const int x)//頭插法創建鏈表
{
    listNode* new_node;
    new_node = (listNode*)malloc(sizeof(listNode));
    new_node->next = l->next;
    l->next = new_node;
    new_node->data = https://www.cnblogs.com/ljz-gy/p/x;
    l->length++;
}
void create_LinkList_tail(LinkList& l, const int x)//尾插法創建鏈表
{
    listNode* new_node;
    listNode* tail_node;
    new_node = (listNode*)malloc(sizeof(listNode));
    tail_node = l;
    while (tail_node->next)
    {
        tail_node = tail_node->next;
    }
    new_node->data = x;
    new_node->next = nullptr;
    tail_node->next = new_node;
    l->length++;
}
void insert_x_pos(LinkList& l, const int x,  int pos)//在鏈表的指定位置插入元素
{
    listNode* now_node;
    listNode* new_node;
    new_node = (listNode*)malloc(sizeof(listNode));
    new_node->data = x;
    now_node = l;
    while (pos-- > 1)
    {
        now_node = now_node->next;
    }
    new_node->next = now_node->next;
    now_node->next = new_node;
    l->length++;
}
int delete_pos(LinkList& l, const int pos)//洗掉某個位置的元素
{
    listNode* tem_node;
    listNode* del_node;
    tem_node = l;
    int elem;
    for(int x = 1; x < pos; x++)
    {
        tem_node = tem_node->next;
    }
    elem = tem_node->next->data;
    del_node = tem_node->next;
    tem_node->next = tem_node->next->next;
    free(del_node);
    l->length--;
    return elem;
}
void update_x_pos(LinkList& l, const int x, const int pos)//改變某個位置的元素
{
    listNode* tem_node;
    tem_node = l;
    for(int i = 1; i < pos; i++)
    {
        tem_node = tem_node->next;
    }
    tem_node->next->data = x;
}
int find_pos(LinkList& l, const int pos)//查找某個位置的元素
{
    listNode* tem_node;
    tem_node = l;
    for(int i = 1; i < pos; i++)
    {
        tem_node = tem_node->next;
    }
    return tem_node->next->data;
}
void print_LinkList(LinkList& l)//列印鏈表
{
    listNode* now_node;
    now_node = l;
    while(now_node->next)
    {
        std::cout<next->data<<" ";
        now_node = now_node->next;
    }
    std::cout<<std::endl;
}
int get_lenght(const LinkList&l)
{
    return l->length;
}
#endif

　//list_with_pointer.cpp

#include<iostream>
#include"list_with_pointer.h"
using namespace std;
void test(LinkList& l)
{
    init(l);
    int x;
    cout<<"請輸入你想插入的元素(int):";
    cin>>x;
    while (x != -1)
    {
        create_LinkList_head(l, x);//頭插法創建
        //create_LinkList_tail(l, x)尾插法創建
        cout<<"請輸入你想插入的元素(int):";
        cin>>x;
    }
    cout<<"鏈表中的元素:";
    print_LinkList(l);
    int insert_x, insert_pos;
    cout<<"請輸你想插入的元素(int)和位置([1,l.length+1])";
    cin>>insert_x>>insert_pos;
    insert_x_pos(l, insert_x, insert_pos);
    cout<<"在第"<<insert_pos<<"個位置插入"<<insert_x<<"后鏈表中的元素:";
    print_LinkList(l);
    int delete_x, pos;
    cout<<"你想洗掉第幾個位置([1,l.length]):";
    cin>>pos;
    delete_x = delete_pos(l, pos);
    cout<<"洗掉該位置的元素后,鏈表中的元素:";
    print_LinkList(l);
    int updata_x, updata_pos;
    cout<<"請輸入想更新的元素(int)和它所在的位置([1,l.length]):";
    cin>>updata_x>>updata_pos;
    update_x_pos(l, updata_x, updata_pos);
    cout<<"更新后鏈表中的元素:";
    print_LinkList(l);
    int pos_find;
    cout<<"你想查找第幾個元素([1,l.lenght]):";
    cin>>pos_find;
    cout<<"該位置的元素為:"<<find_pos(l, pos_find)<<endl;
}
int main()
{
    LinkList l;
　　 test(l);
    return 0;
}

標籤：C++

上一篇：BoostAsio超時方法

下一篇：數論