单链表

单链表用结构体实现

typedef struct Node * LinkList;
typedef struct Node 
{
    int data;
    LinkList next;
} node;

node 代表 struct Node
LinkList 代表 sturct Node * 结构体指针
1 链表的建立
建立一个头指针里面没有数据 待会指向第一个节点
q 刚开始也指向第一个节点 第二个节点建立 q就指向第二个节点 然后q = p q移动到下一个节点 最后的要注意让q->next = NULL

LinkList creat()
{
    LinkList head, p, q;
    head = new node;
    head->next = NULL;
    int n, x;
    cin>>n;
    for(int i = 0; i < n; i++)
    {
        cin>>x;
        p = new node;
        p->data = x;
        p->next = NULL;
        if(head->next == NULL)
            head->next = p;
        else 
            q->next = p;
        q = p;
    }
    q->next = NULL;
    return head;
}

2 插入算法 在第index-1位置插入element
创建一个指针指向第一个节点用一个循环找到index-1的位置 如果p == NULL 说明没找到 index的范围是 [1,节点总数]
创造一个s节点 让element存储在里面
要在p 节点 和 p->next 节点中插入 s
先让s->next 指向p->next 节点再让 p->next指向s
如果先让 p->next 指向s s->next 指向p->next
那么s->next的节点就指向s本身了
考虑特殊情况
index == 1
则头指针指向新的s节点
s节点指向原来的第一个头节点p
两者顺序可以调换

void insert(LinkList head, int index, int element)
{
    LinkList p = head->next, q;
    int j = 1;
    while( j < index -1 && p != NULL)
    {
        p = p->next;
        j++;
    }//p 是index-1的位置  j 是index - 1
    if(index == 1)
    {
    LinkList s;
    s = new node;
    s->data = element;
    head->next = s;
    s->next = p;
    return;
    }
    else if( j > index  || !p)
        return;
    LinkList s;
    s = new node;
    s->data = element;
    s->next = p->next;
    p->next = s; 
}

3 打印函数 就是普通的遍历

void show(LinkList head)
{
    LinkList p = head->next;
    while(p!=NULL)
    {
        cout<<p->data<<' ';
        p = p->next;
    }
}

接下来完整代码

#include<iostream>
using namespace std;
typedef struct Node * LinkList;
typedef struct Node 
{
    int data;
    LinkList next;
} node;
LinkList creat()
{
    LinkList head, p, q;
    head = new node;
    head->next = NULL;
    int n, x;
    cin>>n;
    for(int i = 0; i < n; i++)
    {
        cin>>x;
        p = new node;
        p->data = x;
        p->next = NULL;
        if(head->next == NULL)
            head->next = p;
        else 
            q->next = p;
        q = p;
    }
    q->next = NULL;
    return head;
}
void insert(LinkList head, int index, int element)
{
    LinkList p = head->next, q;
    int j = 1;
    while( j < index -1 && p != NULL)
    {
        p = p->next;
        j++;
    }//p 是index-1的位置 j 是index - 1
    if(index == 1)
    {
    LinkList s;
    s = new node;
    s->data = element;
    s->next = p;
    head->next = s;
    return;
    }
    else if( j > index  || !p)
        return;
    LinkList s;
    s = new node;
    s->data = element;
    s->next = p->next;
    p->next = s; 

}
void show(LinkList head)
{
    LinkList p = head->next;
    while(p!=NULL)
    {
        cout<<p->data<<' ';
        p = p->next;
    }
}
int main()
{
    LinkList head;
    head = creat();
    int index, element;
    cin>>index;
    cin>>element;
    insert(head, index, element);
    show(head);
    return 0;
}