链表

头指针不能轻易改变。

#include<stdio.h>
#include<stdlib.h>

//声明节点
struct Node{
    int data;
    struct Node* next;
};
struct Node* head;  //全局变量，方便调用

//在头节点处 插入节点
void Insert(int x){
    struct Node* temp = (Node*)malloc(sizeof(struct Node));
    temp->data = x;

    temp->next = head;
//  注释的两行可缩写为上方的一行
//  temp->next = NULL;
//  if(head!=NULL) temp->next = head;

    head = temp;
}

// 遍历链表并打印
void print(){
    struct Node* temp= head;
    printf("链表是：");
    while(temp!=NULL){
        printf(" %d",temp->data);
        temp=temp->next;
    }
    printf("\n");
}

int main(){
    head = NULL;
    int i,n,x;
    printf("你想输入多少数字\n");
    scanf("%d",&n);
    for(i=0;i<n;i++){
        printf("请输入数字\n");
        scanf("%d",&x);
        Insert(x);
        print();
    }
    return 0;
}

// 在指定位置插入一个节点
// 第一个节点处为 n=1
void Insert(int data,int n){
    struct Node* temp1 = (Node*)malloc(sizeof(struct Node));
    temp1->data = data;
    temp1->next = NULL;
    if(n==1){
        temp1->next = head;
        head = temp1;
        return;
    }
    struct Node* temp2 = head;
    for(int i=0;i<n-2;i++){
        temp2 = temp2->next;
    }
    temp1->next = temp2->next;
    temp2->next = temp1;
}

// 在指定位置删除节点
void Delete(int n){
     struct Node* temp1 = head;
     if(n==1){
        head = temp1->next;
        free(temp1);
        return;
     }
    for(int i=0;i<n-2;i++){
             temp1=temp1->next;      
    }
    struct Node* temp2 = temp1->next;
    temp1->next = temp2->next;
    free(temp2);

}

// 迭代法反转链表
void Reverse(){
    struct Node *current,*prev,*next;
    current = head;
    prev = NULL;
    while(current!= NULL)
    {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    head = prev;
}

// 递归法打印链表
void Print(struct Node* p){
    if(p==NULL){
        printf("\n");
        return;
    }
    printf("%d ",p->data);
    Print(p->next);
}

// 用递归的方法倒序打印一个链表
// 具体看 BV1Fv4y1f7T1 的 p10的 09:16
// 与递归在内存堆栈中的实现相关
void ReversePrint(struct Node* p){
    if(p==NULL){
        return;
    }
    ReversePrint(p->next);
    printf("%d ",p->data);
}

// 用递归的方法倒转链表
void Reverse(struct Node* p){
    if(p->next==NULL){
        head = p;
        return;
    }
    Reverse(p->next);
    struct Node* p2 = p->next;
    p2->next = p;
    p->next = NULL;
}

// 双向链表
struct Node{
    int data;
    struct Node* next;
    struct Node* prev;
};

#include<stdio.h>
#include<stdlib.h>

struct Node{
    int data;
    struct Node* next;
    struct Node* prev;
};
struct Node* head;

struct Node* GetNewNode(int x){
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = x;
    newNode->prev = NULL;
    newNode->next = NULL;
}

void InsertAtHead(int x){
    struct Node* newNode = GetNewNode(x);
    if(head == NULL){
        head = newNode;
        return;
    }
    head->prev = newNode;
    newNode->next = head;
    head = newNode;
}
void InsertAtTail(int x){
    struct Node* newNode = GetNewNode(x);
    if(head == NULL){
        head = newNode;
        return;
    }
    struct Node* temp = head;
    while(temp->next !=NULL){
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
}

void Print(){
    struct Node* temp = head;
    printf("Link is:");
    while(temp != NULL){
        printf("%d ",temp->data);
        temp = temp->next;
    }
    printf("\n");
}
void ReversePrint(){
    struct Node* temp = head;
    if(temp == NULL) return;
    while(temp->next !=NULL){
        temp = temp->next;
    }
    printf("Reverse link is:");
    while(temp != NULL){
        printf("%d ",temp->data);
        temp = temp->prev;
    }
    printf("\n");
}

int main(){
    head = NULL;
    InsertAtHead(2); Print(); ReversePrint();
    InsertAtHead(3); Print(); ReversePrint();
    InsertAtHead(4); Print(); ReversePrint();
    InsertAtTail(3); Print(); ReversePrint();
    InsertAtTail(2); Print(); ReversePrint();
    return 0;
}