链表

不带头结点单链表

• 使用头指针为全局变量

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

typedef int ElemType; //假设线性表中数据元素类型为整形

//单链表的表示与实现
//储存结构
struct Node
{
    ElemType data;        //存储数据
    struct Node* next; //存储指针
};

typedef struct Node Node;    //看似是一句废话，但是如果不写，每次引用结构体都要加一个struct，很繁琐

struct Node* head;    //头指针：在这里声明是使head能够被全局调用，但是一般我们不这样使用

void Insert(int x){
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = x;

    //常规做法就是这样，先创建一个结点使其指针next指向NULL
    //1、如果head为空，即temp是链表第一个结点，直接让head = temp即可
    //2、如果head不为空，即temp不是链表第一个结点，根据头插法原则，需要让这个新插入的temp结点先指向head指向的结点，再让head指向自己
    // temp->next = NULL;
    // if (head != NULL)
    // {
    //     temp->next = head;
    // }

    //简化写法，每次都让temp指向head，因为如果你是第一个结点，指向head，即temp->next=NULL,所以过程都是一样的
    temp->next=head;

    head=temp;
}

void Print(){
    Node* temp =  head;
    printf("List:");
    while (temp != NULL)
    {
        printf(" %d",temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int main(){
    head = NULL;    //初始化头指针        也可以写函数Init，操作相同
    printf("how many numbers?\n");
    int n,i,x;
    scanf("%d",&n);
    for (i = 0; i < n; i++)
    {
        printf("please enter your num\n");
        scanf("%d",&x);
        Insert(x);
        Print();
    }
}

• 使用头指针为局部变量

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

typedef int ElemType; //假设线性表中数据元素类型为整形

//单链表的表示与实现
//储存结构
struct Node
{
    ElemType data;        //存储数据
    struct Node* next; //存储指针
};

typedef struct Node Node;    //看似是一句废话，但是如果不写，每次引用结构体都要加一个struct，很繁琐

void Insert(Node** head,int x){    
    //这里为什么使用**    ： 首先插入元素肯定是要在我定义的链表中进行操作，因此我传入了头指针的地址
    //第一个*，是解析该地址对应的变量——此时的head表示一个指针
    //第二个*，与Node组合表示 —— *head 是一个Node型的指针
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = x;

    //常规做法就是这样，先创建一个结点使其指针next指向NULL
    //1、如果head为空，即temp是链表第一个结点，直接让head = temp即可
    //2、如果head不为空，即temp不是链表第一个结点，根据头插法原则，需要让这个新插入的temp结点先指向head指向的结点，再让head指向自己
    // temp->next = NULL;
    // if (*head != NULL)
    // {
    //     temp->next = *head;
    // }

    //简化写法，每次都让temp指向head，因为如果你是第一个结点，指向head，即temp->next=NULL,所以过程都是一样的
    temp->next=*head;
    *head=temp;
}

void Print(Node* head){
    printf("List:");
    while (head != NULL)
    {
        printf(" %d",head->data);
        head = head->next;
    }
    printf("\n");
}

int main(){
    Node* head = NULL;    //初始化头指针        也可以写函数Init，操作相同
    printf("how many numbers?\n");
    int n,i,x;
    scanf("%d",&n);
    for (i = 0; i < n; i++)
    {
        printf("please enter your num\n");
        scanf("%d",&x);
        Insert(&head,x);
        Print(head);
    }
}

• 实现指定位置插入操作

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

typedef int ElemType; //假设线性表中数据元素类型为整形

//单链表的表示与实现
//储存结构
struct Node
{
    ElemType data;        //存储数据
    struct Node* next; //存储指针
};

typedef struct Node Node;    //看似是一句废话，但是如果不写，每次引用结构体都要加一个struct，很繁琐

struct Node* head;    //头指针：在这里声明是使head能够被全局调用，但是一般我们不这样使用

//指定位置插入元素
void Insert_Index(int data,int n){
    Node* temp1 = (Node*)malloc(sizeof(Node));    //新建插入的结点
    temp1->data = data;
    temp1->next = NULL;

    if (n==1)    //如果是第一个结点
    {
        temp1->next = head;
        head = temp1;
        return;
    }
    
    if (n==2)
    {
        temp1->next = head->next;
        head->next = temp1;
        return;
    }
    
    Node* temp2 = head;    //新建一个结点指针用来遍历链表
    for (int i = 0; i < n-2; i++)    //要找到插入位置的前一个元素，即n-1，则temp = temp->next需要执行n-2次
    {
        temp2 = temp2->next;
    }

    temp1->next = temp2->next;
    temp2->next = temp1;
}

void Print(){
    Node* temp =  head;
    printf("List:");
    while (temp != NULL)
    {
        printf(" %d",temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int main(){
    head = NULL;
    Insert_Index(2,1);
    Insert_Index(3,2);
    Insert_Index(4,1);
    Insert_Index(5,2);
    Print();
}

• 实现指定位置删除操作

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

typedef int ElemType; //假设线性表中数据元素类型为整形

//单链表的表示与实现
//储存结构
struct Node
{
    ElemType data;       //存储数据
    struct Node *next; //存储指针
};

typedef struct Node Node; //看似是一句废话，但是如果不写，每次引用结构体都要加一个struct，很繁琐

struct Node *head; //头指针：在这里声明是使head能够被全局调用，但是一般我们不这样使用

void Insert(int x)
{
    //这里为什么使用**    ： 首先插入元素肯定是要在我定义的链表中进行操作，因此我传入了头指针的地址
    //第一个*，是解析该地址对应的变量——此时的head表示一个指针
    //第二个*，与Node组合表示 —— *head 是一个Node型的指针
    Node *temp = (Node *)malloc(sizeof(Node));
    temp->data = x;

    //常规做法就是这样，先创建一个结点使其指针next指向NULL
    // 1、如果head为空，即temp是链表第一个结点，直接让head = temp即可
    // 2、如果head不为空，即temp不是链表第一个结点，根据头插法原则，需要让这个新插入的temp结点先指向head指向的结点，再让head指向自己
    // temp->next = NULL;
    // if (head != NULL)
    // {
    //     temp->next = head;
    // }

    //简化写法，每次都让temp指向head，因为如果你是第一个结点，指向head，即temp->next=NULL,所以过程都是一样的
    temp->next = head;
    head = temp;
}

//指定位置删除
void Delete(int n)
{
    Node *temp1 = head;
    if (n == 1)
    {
        head = temp1->next;
        free(temp1);
        return;
    }
    else
    {
        int i;
        for (i = 0; i < n - 2; i++)
            temp1 = temp1->next;
        //使temp1指向 n-1 这个位置
        Node *temp2 = temp1->next;
        temp1->next = temp2->next;
        free(temp2); // C++ 写法： delete temp2
    }
}

void Print()
{
    Node *temp = head;
    printf("List:");
    while (temp != NULL)
    {
        printf(" %d", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int main()
{
    head = NULL;
    Insert(2);
    Insert(4);
    Insert(6);
    Insert(5); // List: 2,4,6,5
    Print();
    int n;
    printf("Enter a position\n");
    scanf("%d", &n);
    Delete(n);
    Print();
}

• 逆转单链表

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

typedef int ElemType; //假设线性表中数据元素类型为整形

//单链表的表示与实现
//储存结构
struct Node
{
    ElemType data;       //存储数据
    struct Node *next; //存储指针
};

typedef struct Node Node; //看似是一句废话，但是如果不写，每次引用结构体都要加一个struct，很繁琐

struct Node *head; //头指针：在这里声明是使head能够被全局调用，但是一般我们不这样使用

void Insert(int x)
{
    //这里为什么使用**    ： 首先插入元素肯定是要在我定义的链表中进行操作，因此我传入了头指针的地址
    //第一个*，是解析该地址对应的变量——此时的head表示一个指针
    //第二个*，与Node组合表示 —— *head 是一个Node型的指针
    Node *temp = (Node *)malloc(sizeof(Node));
    temp->data = x;

    //常规做法就是这样，先创建一个结点使其指针next指向NULL
    // 1、如果head为空，即temp是链表第一个结点，直接让head = temp即可
    // 2、如果head不为空，即temp不是链表第一个结点，根据头插法原则，需要让这个新插入的temp结点先指向head指向的结点，再让head指向自己
    // temp->next = NULL;
    // if (head != NULL)
    // {
    //     temp->next = head;
    // }

    //简化写法，每次都让temp指向head，因为如果你是第一个结点，指向head，即temp->next=NULL,所以过程都是一样的
    temp->next = head;
    head = temp;
}

//方式一：逆转输出序列
void Reverse(){
    Node *next,*prev,*current;
    current = head;
    prev = NULL;
    while (current != NULL)
    {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    head = prev;
}

//递归打印输出单链表
void DPrint(Node *head){    //先递归再打印的输出顺序和先打印再递归的输出顺序不一样，可以实现逆转输出
    if (head == NULL)
        return;
    DPrint(head->next);
    printf("%d ",head->data);
}

//递归逆转单链表
void DReverse(Node *p){
    if (p->next == NULL)
    {
        head = p;
        return;
    }
    DReverse(p->next);

    Node *q = p->next;
    q->next = p;
    p->next = NULL;
    // p->next->next = p;
}

void Print()
{
    Node *temp = head;
    printf("List:");
    while (temp != NULL)
    {
        printf(" %d", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int main()
{
    head = NULL;
    Insert(2);
    Insert(4);
    Insert(6);
    Insert(5); // List: 2,4,6,5
    Print();
    Reverse();
    Print();
    
    // DPrint(head);
    // DReverse(head);
    // Print(head);
}

双向链表

#include <stdio.h>
#include <stdlib.h>
#define ElemType int

//双向链表结点类型定义
typedef struct Dnode
{
    ElemType data;
    struct Dnode *prior, *next;
} Dnode;

//定义全局变量：头指针
struct Dnode *head;

/*
知识点：
    应用内存板块有：stack(栈)、heap(堆)、global/static(全局静态)
    一个函数被调用时，会从栈上分配一些内存供该函数执行，该内存部分称为该函数的栈帧
    该函数中所申明的所有局部变量都会存放到栈帧中去，在函数调用结束后，栈帧被回收 —— 栈中该元素的生命周期到此结束
    即使我们返回了指向这个栈帧中变量位置的指针，但是栈帧已经不见了，知道位置毫无意义。

    问题：为什么申明结点需要用到malloc呢？
    回答：malloc函数会在堆中申明一个空间用于存放结点，
    重点：堆中申明的变量我们不能直接使用，访问堆中变量的唯一方法是通过指针，如果指针丢失，则该节点逻辑上也丢失了

    因此我返回指向这个堆中变量位置的指针，可以通过该指针指向的位置来访问这个结点，逻辑上这个结点就申明成功了
*/

//此函数动态的在heap(堆)中申明了一个node，执行完之后将指向node的指针返回，在heap中的变量，不会在函数执行后释放
Dnode *GetNewNode(int x)
{
    Dnode *newNode = (Dnode *)malloc(sizeof(Dnode));
    (*newNode).data = x;
    newNode->next = NULL;
    newNode->prior = NULL;
    return newNode;
}
//第二种写法是错误的，因为在函数体里面申明的变量存储到栈中的栈帧里，执行完函数堆栈会释放，其存储的变量也会相应释放
// Dnode* GetNewNode(int x)
// {
//     Dnode newNode;
//     newNode.data = x;
//     newNode.next = NULL;
//     newNode.prior = NULL;
//     return &newNode;
// }

void InsertAtHead(int x)
{
    Dnode *newNode = GetNewNode(x);
    if (head == NULL)
    {
        head = newNode;
        return;
    }
    head->prior = newNode;
    newNode->next = head;
    head = newNode;
}

void Print()
{
    Dnode* temp = head;
    printf("遍历：");
    while (temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

void ReversePrint()
{
    Dnode* temp = head;
    if (head == NULL)
    {
        return;
    }
    while (temp->next != NULL)
    {
        temp = temp->next;
    }
    printf("遍历：");
    while (temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->prior;
    }
    printf("\n");
}

int main()
{
    head = NULL;
    InsertAtHead(2);    Print();    ReversePrint();
    InsertAtHead(4);    Print();    ReversePrint();
    InsertAtHead(6);    Print();    ReversePrint();
}

栈

数组实现

#include<stdio.h>
#define MAX_SIZE 101
int A[MAX_SIZE];
int top = -1;

void Push(int x){
    if (top == MAX_SIZE - 1)
    {
        printf("stack is full\n");
        return;
    }
    top++;
    A[top]=x;
}

void Pop(){
    if (top == - 1)
    {
        printf("stack is empty\n");
        return;
    }
    top--;
}

int Top(){
    return A[top];
}

void Print(){
    int i;
    printf("Stack: ");
    for (i = 0; i <= top; i++)
    {
        printf("%d ",A[i]);
    }
    printf("\n");
}

int main(){
    Push(2);    Print();
    Push(5);    Print();
    Push(10);   Print();
    Pop();      Print();
    Push(12);   Print();
}

单链表实现

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

struct Node
{
    int data;
    struct Node* link;   
};

typedef struct Node Node;

Node* top = NULL;

void Push(int x){
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = x;
    temp->link = top;
    top = temp;
}

void Pop(){
    Node* temp;
    if (top == NULL)
    {
        return;
    }
    temp = top;
    top = top->link;
    free(temp);       
}

int Top(){
    return top->data;
}

void Print(){
    printf("Stack:\n");
    Node* p = top;
    while (p != NULL)
    {
        printf("%d ",p->data);
        p = p->link;
    }
    printf("\n");
}

int main(){
    Push(2);    Print();
    Push(5);    Print();
    Push(10);   Print();
    Pop();      Print();
    Push(12);   Print();
    int A = Top();
    printf("%d",A);
}

栈表逆置(C++)

#include
#include //stack标准库
#include
#include

using namespace std;

// class Stack
// {
// private:
//     char A[101];
//     int top;
// public:
//     void Push(int x);
//     void Pop();
//     int Top();
//     bool IsEmpty();
// };

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

Node* head=NULL;

void Push_Num(int x){
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = x;
    temp->next = head;
    head = temp;
}

void Reverse(char C[],int n){   //C++中数组C[] 也可以写为 *C
    stack S;
    //压栈
    for (int i = 0; i < n; i++)
    {
        S.push(C[i]);
    }
    
    //弹栈
    for (int i = 0; i < n; i++)
    {
        C[i] = S.top();
        S.pop();
    }
}

void Reverse(){
    if (head == NULL)
    {
        return;
    }
    stack S;
    Node* temp = head;
    while (temp != NULL)
    {
        S.push(temp);
        temp = temp->next;
    }

    temp = S.top();
    head = temp;    //头指针指向栈顶元素，即原栈的栈底元素
    S.pop();
    while (!S.empty())
    {
        temp->next=S.top();     //上一个栈顶元素 指向 弹出后的 下一个栈顶元素
        S.pop();
        temp=temp->next;
    }
    temp->next = NULL;
}

void Print(){
    printf("Stack:\n");
    Node* p = head;
    while (p != NULL)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

int main(){
    // char C[51];
    // printf("Enter a String:\n");
    // gets(C);
    // Reverse(C,strlen(C));
    // printf("OutPut = %s",C);
    Push_Num(2);   Print();
    Push_Num(5);    Print();
    Push_Num(10);  Print();
    Push_Num(12);   Print();

    Reverse();  Print();
}