链表

数据结构

单链表

单链表即只能向一个方向的遍历的链表，换句话说，就是只有一个指针（域）（指向后面或前面），单链表是最简单的链表。
又因为在单链表中，每次读取元素，都要从头结点开始，故单链表是一种非随机存取的存储结构

结点定义

typedef struct LNodes
{
    ElemType data;
    struct LNodes *next;
} LNodes,*LinkList;

结点初始化

if (p!=NULL)
{
    p->data=10;
    p->next=NULL;
}

建立链表

LinkedList LinkedListInit() {  
    Node *L;  
    L = (Node *)malloc(sizeof(Node));   //申请结点空间   
    if(L == NULL) { //判断是否有足够的内存空间   
        printf("申请内存空间失败\n");  
    }  
    L->next = NULL;                  //将next设置为NULL,初始长度为0的单链表   
    return L;  
}  
//单链表的建立1，头插法建立单链表  
LinkedList LinkedListCreatH() {  
    Node *L;  
    L = (Node *)malloc(sizeof(Node));   //申请头结点空间  
    L->next = NULL;                      //初始化一个空链表  
    ElemType x;                         //x为链表数据域中的数据  
    while(scanf("%d",&x) != EOF) {  
        Node *p;  
        p = (Node *)malloc(sizeof(Node));   //申请新的结点   
        p->data = x;                     //结点数据域赋值   
        p->next = L->next;                    //将结点插入到表头L-->|2|-->|1|-->NULL   
        L->next = p;   
    }  
    return L;   
}   

遍历一个链表

访问函数

Status printElement(Elemtype e)
{
    printf("%c",e);     //假设是char类型
    return OK;
}

遍历函数

void TraverseLinkList(LinkList L,Status(*visit)(ElemType e))
{
    LNode *p;
    p=L;
    while (p!=NULL)
    {
        visit(p->data);
        p=p->next;
    }
}

我的测试代码

demo02

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status;
//结点定义 
typedef struct LNodes
{
    int data;
    struct LNodes *next;
} *LinkList;
LinkList chushihua()
{
     LNodes *L;
    L = (struct LNodes *) malloc (sizeof(struct LNodes));   //申请头结点空间  
    //L->data = 0;
    L->next = NULL;                      //初始化一个空链表  
    int x;                         //x为链表数据域中的数据  
    while (scanf_s("%d", &x) != EOF)
    {
        struct LNodes *p;  
        p = (struct LNodes *)malloc(sizeof(struct LNodes));   //申请新的结点   
        p->data = x;                     //结点数据域赋值   
        p->next = L->next;                    //将结点插入到表头L-->|2|-->|1|-->NULL   
        L->next = p;
    }
    return L;    
}
Status printElement(int e)
{
    printf("%d\n", e);     //假设是int类型
    return OK;
}
void bianli(struct LNodes *L)
{
    struct LNodes *p;
    p = L->next;
    while (p != NULL)
    {
        if (printElement(p->data))
            p = p->next;
    }
    free(L);
    free(p);
}
int main()
{
    struct LNodes *L;
    int n;
    L=chushihua();
    bianli(L);
    //printf("%d\n",scanf_s("%d",&n));
    return 0;
}

相关操作

判断是否为空

如何在其他没有指针的高级语言中使用链表？

这时我们应该借用一维数组来定义：

#define Maxsize 1000
typedef struct
{
    ElemType data;
    int cur;    //数组下标，来代替指针
}compnent,SLinkList[Maxsize];

这种链表，与前面的不一样为静态线性链表。

带头结点的单链表

典型应用

循环单链表

与单链表唯一的区别在于，最后一个结点的后继指向头结点，但就这一个区别，就会造成后后面有很多地方与单链表不同。

双链表

与单链表对应的，双链表是同时可以向前又可以向后遍历的链表，即同时具有两个指针（一前一后）

循环双链表