数据结构三

一、关于线性表中单链表的头插法和尾插法

#include "stdio.h"
#include "stdlib.h"

struct LNode{
    int data;
    struct LNode* next;
};
//创建一个节点
struct LNode* CreateNode(int e){
    struct LNode* p=(struct LNode*) malloc(sizeof(struct LNode));
    if(p==NULL){
        printf("No enough memory to allocate!\n");
        exit(0);
    }
    p->data=e;
    p->next=NULL;
    return p;
}
//尾插法插入元素
struct LNode* ListTailInsert(struct LNode* L){
    struct LNode* p=L,*s=NULL;
    int x=-1;
    scanf("%d",&x);
    while (x!=9999){
        s= CreateNode(x);
        p->next=s;
        p=s;
        scanf("%d",&x);
    }
    p->next=NULL;
    return L;
}
//头插法插入元素
struct LNode* ListHeadInsert(struct LNode* L){
    struct LNode* p=L,*s=NULL;
    int x=-1;
    scanf("%d",&x);
    while (x!=9999){
        s= CreateNode(x);
        s->next=p->next;
        p->next=s;
        scanf("%d",&x);
    }
    return L;
}
//遍历所有元素的值
void ListDisplay(struct LNode* L){
    struct LNode* p=L->next;
    int j=1;
    while (p!=NULL){
        printf("The single-linked-list which has head has %dth node which data is %d.\n",j,p->data);
        p=p->next;
    }
}
//释放所有的元素
void DeleteMemory(struct LNode* L){
    struct LNode* p=L,* pr=NULL;
    while (p!=NULL){
        pr=p;
        p=p->next;
        free(pr);
    }
}
int main(){
    printf("-----------Head insertion-------------\n");
    struct LNode* L= NULL;//声明一个指向单链表的指针
    //1.创建带头节点的单链表
    L=CreateNode(0);//初始化空的单链表
    //2.尾插法进行操作
    L= ListTailInsert(L);
    //3.遍历输出所有节点信息
    ListDisplay(L);
    //4.释放所有节点
    DeleteMemory(L);
    printf("-----------Tail insertion-------------\n");
    struct LNode* S=NULL;//声明一个指向单链表的指针
    //1.创建带头节点的单链表
    S= CreateNode(0);
    //2.头插法进行操作
    S=ListHeadInsert(S);
    //3.遍历输出所有的元素
    ListDisplay(S);
    //4.释放内存空间
    DeleteMemory(S);
    return 0;
}

实现结果：

D:\project\clion\ch1\cmake-build-debug\single_linked_list_created.exe
-----------Head insertion-------------
1
2
3
5
9999
The single-linked-list which has head has 1th node which data is 1.
The single-linked-list which has head has 1th node which data is 2.
The single-linked-list which has head has 1th node which data is 3.
The single-linked-list which has head has 1th node which data is 5.
-----------Tail insertion-------------
3
5
2
10
9999
The single-linked-list which has head has 1th node which data is 10.
The single-linked-list which has head has 1th node which data is 2.
The single-linked-list which has head has 1th node which data is 5.
The single-linked-list which has head has 1th node which data is 3.

Process finished with exit code 0

注：头插法的一个重要应用就是链表的逆序输出