数据结构之线性表的链式存储结构（C语言）

以你之姓@ 2023-02-12 05:45 2阅读 0赞

### 文章目录 ###

*   *   *  引言
         *  线性表链式存储结构定义
         *  头指针与头结点的异同
         *  线性链表存储结构代码秒描述
         *   *  单链表的读取
             *   *  获得链表第i个数据的算法思路
             *  单链表的插入
             *   *  单链表第i个数据插入结点的算法思路
             *  单链表的删除
             *   *  单链表第i个数据删除结点的算法思路
         *  整体代码

### 引言 ###

线性表的顺序存储结构，它是有缺点的，最大的缺点就是插入和删除时需要移动大量的数据元素，这显然需要耗费时间。

### 线性表链式存储结构定义 ###

特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的。也可以是不连续的。这就意味着这些数据元素可以存在内存内存未被占用的任意位置。  
![在这里插入图片描述][20200524194027151.png]在顺序存储结构中，每个数据元素只需要存储数据元素信息就可以了。现在链式结构中，**除了要存储数据元素信息之外，还要存储它的后继元素的存储地址。**  
**为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，对元素ai来说，除了存储其本身的信息之外，还需要存储一个指示其直接后继的信息（即直接后继的存储位置）。把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域汇中存储的信息称作指针或链。这两部分信息组成数据元素ai的存储映像，称为结点（Node）**  
\*\*n个结点（ai的存储映像）链接成一个链表，即为线性链表（a1,a2,……an,）的链式存储结构，因此链表的每个结点只包含一个指针域， 所以叫单链表。 \*\*  
![在这里插入图片描述][20200524200440838.png]  
**我们把链表第一个结点的存储位置叫做头指针**，那么整个链表的存取就必须从头指针进行。之后的每一个结点，其实就是上一个的后继指针指向的位置。最后一个结点指针为空（NULL或^符号表示）。  
![在这里插入图片描述][20200524201113950.png]  
有时候为了方便对链表进行操作，**会在单链表的第一个结点前附设一个结点，称为头结点**。头结点的数据域可以不存储任何信息（可以存储线性表的长度等附加信息），头结点的指针域存储指向第一个结点的指针。  
![在这里插入图片描述][20200524201652786.png]

### 头指针与头结点的异同 ###

头指针是只链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针，头指针具有标识作用，所以常用头指针冠以链表的名字，无论链表是否为空，头指针均不为空。头指针是链表的必要元素。

头结点是为了操作方便的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义。有了头结点对在一个元素结点前插入点和删除第一个结点，其操作与其他结点的操作就统一了。头结点不一定是链表必要元素。

### 线性链表存储结构代码秒描述 ###

若线性表为空，则头结点的指针域为空。  
![在这里插入图片描述][20200524203020879.png]  
线性表中数据元素及数据元素之间的逻辑关系。  
![在这里插入图片描述][20200524203226943.png]  
带有头结点的单链表。  
![在这里插入图片描述][20200524203255225.png]  
空链表。  
![在这里插入图片描述][20200524203318947.png]  
单链表中，可以用结构指针描述（C语言）

typedef struct Node
    {
        
        ElemType data;
        struct Node *next;
    }Node;
    typedef struct Node *LinkList; /* 定义LinkList */

结点由存放数据元素的数据域存放后继结点地址的指针域组成。  
假设p是指向线性表第i个元素的指针，则该节点ai的数据域，我们我们可以用p->data来表示，p->data的值是一个数据元素，结点ai的指针域可用p->next来表示，p->next的值是一个指针。p->next指向第i+1个元素，即指向ai+1的指针。  
如果p->data =ai,那么p->next->data=ai+1.  
![在这里插入图片描述][20200525115157989.png]

#### 单链表的读取 ####

##### 获得链表第i个数据的算法思路 #####

1、声明一个结点p指向链表第一个结点，初始化j从1开始。  
2、当j < i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1。  
3、若链表末尾p为空，则说明第i个元素不存在。  
4、否则查找成功，返回结点p的数据。

/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
    /* 操作结果：用e返回L中第i个数据元素的值 */
    Status GetElem(LinkList L,int i,ElemType *e)
    {
        
    	int j;
    	LinkList p;		/* 声明一结点p */
    	p = L->next;		/* 让p指向链表L的第一个结点 */
    	j = 1;		/*  j为计数器 */
    	while (p && j<i)  /* p不为空或者计数器j还没有等于i时，循环继续 */
    	{
           
    		p = p->next;  /* 让p指向下一个结点 */
    		++j;
    	}
    	if ( !p || j>i ) 
    		return ERROR;  /*  第i个元素不存在 */
    	*e = p->data;   /*  取第i个元素的数据 */
    	return OK;
    }

从头开始找，直到第i个元素为止，由于这个算法的时间复杂度取决于i的位置，i=1时，则不需要遍历，第一个就取出数据了，i=n时，需要遍历n-1次才可以，因此最坏情况下的时间复杂度为O(n)。

#### 单链表的插入 ####

假设存储元素e的结点为s，要实现结点p，p->next和s之间逻辑关系的变化，只需要将结点s插入到结点p和p->next之间即可，问题是怎么插入？  
![在这里插入图片描述][20200525121544516.png]不需要一定其他的结点，只需要让s->next和p->next的指针做一点改变即可。

s->next = p->next;
    p->next = s;

就是让p的后继结点改成s的后继结点，再把结点s变成p的后继结点。  
![在这里插入图片描述][20200525122005407.png]  
考虑一下这两句的顺序的可不可以交换？  
如果先p->next = s;在s->next = p->next;会怎么样？  
此时的第一句使得p->next给覆盖成s的地址了。那么s->next=p->next，其实就等于s->next =s.

插入结点s后，链表如图  
![在这里插入图片描述][20200525122614905.png]  
对于单链表的表头和表尾的特殊情况，操作是想相同的。  
![在这里插入图片描述][20200525122658207.png_400x100]

##### 单链表第i个数据插入结点的算法思路 #####

1、声明一结点p指向链表第一个结点，初始化j从1开始。  
2、当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1。  
3、若到链表末尾p为空，则说明第i个元素不存在。  
4、否则查找成功，在系统生成一个空结点s。  
5、将数据元素e赋值给s->data。  
6、单链表的插入标准语句s->next = p->next;p->next = s;  
7、返回成功。

/* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */
    /* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
    Status ListInsert(LinkList *L,int i,ElemType e)
    {
         
    	int j;
    	LinkList p,s;
    	p = *L;   
    	j = 1;
    	while (p && j < i)     /* 寻找第i个结点 */
    	{
        
    		p = p->next;
    		++j;
    	} 
    	if (!p || j > i) 
    		return ERROR;   /* 第i个元素不存在 */
    	s = (LinkList)malloc(sizeof(Node));  /*  生成新结点(C语言标准函数) */
    	s->data = e;  
    	s->next = p->next;      /* 将p的后继结点赋值给s的后继  */
    	p->next = s;          /* 将s赋值给p的后继 */
    	return OK;
    }

malloc函数作用就是生成一个新的结点，其类型与node是一样的。实质就是在内存中找了一小块空地，准备用来存放e数据s的结点。

#### 单链表的删除 ####

假设存储ai的结点q，要实现将结点q删除单链表的操作。其实就是将它的前驱结点的指针绕过，指向它的后继结点即可。  
![在这里插入图片描述][20200525124412315.png]我们需要做的就是一步  
p->next=p->next->next，用q来取代p->next

q = p->next;
    p->next = q->next;

就是让p的后继的后继结点改成p的后继结点。

##### 单链表第i个数据删除结点的算法思路 #####

1、声明一结点p指向链表第一个结点，初始化j从1开始。  
2、当j<i时，就遍历链表，就让p的指针向后移动，不断指向下一个结点，j累加1。  
3、若到链表末尾p为空，则说明第i个元素不存在。  
4、否则查找成功，将想删除的结点p->next赋值给q。  
5、单链表的删除语句q = p->next;p->next = q->next。  
6、将q结点中的数据赋值给e，作为返回。  
7、释放q结点。  
8、返回成功。

/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
    /* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
    Status ListDelete(LinkList *L,int i,ElemType *e) 
    {
         
    	int j;
    	LinkList p,q;
    	p = *L;
    	j = 1;
    	while (p->next && j < i)	/* 遍历寻找第i个元素 */
    	{
        
            p = p->next;
            ++j;
    	}
    	if (!(p->next) || j > i) 
    	    return ERROR;           /* 第i个元素不存在 */
    	q = p->next;
    	p->next = q->next;			/* 将q的后继赋值给p的后继 */
    	*e = q->data;               /* 将q结点中的数据给e */
    	free(q);                    /* 让系统回收此结点，释放内存 */
    	return OK;
    }

函数free作用就是让嗅探回收一个Node结点，释放内存。

### 整体代码 ###

#include "stdio.h"    
    #include "string.h"
    #include "ctype.h"      
    #include "stdlib.h"   
    #include "io.h"  
    #include "math.h"  
    #include "time.h"
    
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    
    #define MAXSIZE 20 /* 存储空间初始分配量 */
    
    typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
    typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
    
    
    Status visit(ElemType c)
    {
        
        printf("%d ",c);
        return OK;
    }
    
    typedef struct Node
    {
        
        ElemType data;
        struct Node *next;
    }Node;
    typedef struct Node *LinkList; /* 定义LinkList */
    
    /* 初始化顺序线性表 */
    Status InitList(LinkList *L) 
    {
         
        *L=(LinkList)malloc(sizeof(Node)); /* 产生头结点,并使L指向此头结点 */
        if(!(*L)) /* 存储分配失败 */
                return ERROR;
        (*L)->next=NULL; /* 指针域为空 */
    
        return OK;
    }
    
    /* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
    Status ListEmpty(LinkList L)
    {
         
        if(L->next)
                return FALSE;
        else
                return TRUE;
    }
    
    /* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
    Status ClearList(LinkList *L)
    {
         
    	LinkList p,q;
    	p=(*L)->next;           /*  p指向第一个结点 */
    	while(p)                /*  没到表尾 */
    	{
        
    		q=p->next;
    		free(p);
    		p=q;
    	}
    	(*L)->next=NULL;        /* 头结点指针域为空 */
    	return OK;
    }
    
    /* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */
    int ListLength(LinkList L)
    {
        
        int i=0;
        LinkList p=L->next; /* p指向第一个结点 */
        while(p)                        
        {
        
            i++;
            p=p->next;
        }
        return i;
    }
    
    /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
    /* 操作结果：用e返回L中第i个数据元素的值 */
    Status GetElem(LinkList L,int i,ElemType *e)
    {
        
    	int j;
    	LinkList p;		/* 声明一结点p */
    	p = L->next;		/* 让p指向链表L的第一个结点 */
    	j = 1;		/*  j为计数器 */
    	while (p && j<i)  /* p不为空或者计数器j还没有等于i时，循环继续 */
    	{
           
    		p = p->next;  /* 让p指向下一个结点 */
    		++j;
    	}
    	if ( !p || j>i ) 
    		return ERROR;  /*  第i个元素不存在 */
    	*e = p->data;   /*  取第i个元素的数据 */
    	return OK;
    }
    
    /* 初始条件：顺序线性表L已存在 */
    /* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
    /* 若这样的数据元素不存在，则返回值为0 */
    int LocateElem(LinkList L,ElemType e)
    {
        
        int i=0;
        LinkList p=L->next;
        while(p)
        {
        
            i++;
            if(p->data==e) /* 找到这样的数据元素 */
                    return i;
            p=p->next;
        }
    
        return 0;
    }
    
    
    /* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */
    /* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
    Status ListInsert(LinkList *L,int i,ElemType e)
    {
         
    	int j;
    	LinkList p,s;
    	p = *L;   
    	j = 1;
    	while (p && j < i)     /* 寻找第i个结点 */
    	{
        
    		p = p->next;
    		++j;
    	} 
    	if (!p || j > i) 
    		return ERROR;   /* 第i个元素不存在 */
    	s = (LinkList)malloc(sizeof(Node));  /*  生成新结点(C语言标准函数) */
    	s->data = e;  
    	s->next = p->next;      /* 将p的后继结点赋值给s的后继  */
    	p->next = s;          /* 将s赋值给p的后继 */
    	return OK;
    }
    
    /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
    /* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
    Status ListDelete(LinkList *L,int i,ElemType *e) 
    {
         
    	int j;
    	LinkList p,q;
    	p = *L;
    	j = 1;
    	while (p->next && j < i)	/* 遍历寻找第i个元素 */
    	{
        
            p = p->next;
            ++j;
    	}
    	if (!(p->next) || j > i) 
    	    return ERROR;           /* 第i个元素不存在 */
    	q = p->next;
    	p->next = q->next;			/* 将q的后继赋值给p的后继 */
    	*e = q->data;               /* 将q结点中的数据给e */
    	free(q);                    /* 让系统回收此结点，释放内存 */
    	return OK;
    }
    
    /* 初始条件：顺序线性表L已存在 */
    /* 操作结果：依次对L的每个数据元素输出 */
    Status ListTraverse(LinkList L)
    {
        
        LinkList p=L->next;
        while(p)
        {
        
            visit(p->data);
            p=p->next;
        }
        printf("\n");
        return OK;
    }
    
    /*  随机产生n个元素的值，建立带表头结点的单链线性表L（头插法） */
    void CreateListHead(LinkList *L, int n) 
    {
        
    	LinkList p;
    	int i;
    	srand(time(0));                         /* 初始化随机数种子 */
    	*L = (LinkList)malloc(sizeof(Node));
    	(*L)->next = NULL;                      /*  先建立一个带头结点的单链表 */
    	for (i=0; i<n; i++) 
    	{
        
    		p = (LinkList)malloc(sizeof(Node)); /*  生成新结点 */
    		p->data = rand()%100+1;             /*  随机生成100以内的数字 */
    		p->next = (*L)->next;    
    		(*L)->next = p;						/*  插入到表头 */
    	}
    }
    
    /*  随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法） */
    void CreateListTail(LinkList *L, int n) 
    {
        
    	LinkList p,r;
    	int i;
    	srand(time(0));                      /* 初始化随机数种子 */
    	*L = (LinkList)malloc(sizeof(Node)); /* L为整个线性表 */
    	r=*L;                                /* r为指向尾部的结点 */
    	for (i=0; i<n; i++) 
    	{
        
    		p = (Node *)malloc(sizeof(Node)); /*  生成新结点 */
    		p->data = rand()%100+1;           /*  随机生成100以内的数字 */
    		r->next=p;                        /* 将表尾终端结点的指针指向新结点 */
    		r = p;                            /* 将当前的新结点定义为表尾终端结点 */
    	}
    	r->next = NULL;                       /* 表示当前链表结束 */
    }
    
    int main()
    {
                
        LinkList L;
        ElemType e;
        Status i;
        int j,k;
        i=InitList(&L);
        printf("初始化L后：ListLength(L)=%d\n",ListLength(L));
        for(j=1;j<=5;j++)
                i=ListInsert(&L,1,j);
        printf("在L的表头依次插入1～5后：L.data=");
        ListTraverse(L); 
    
        printf("ListLength(L)=%d \n",ListLength(L));
        i=ListEmpty(L);
        printf("L是否空：i=%d(1:是 0:否)\n",i);
    
        i=ClearList(&L);
        printf("清空L后：ListLength(L)=%d\n",ListLength(L));
        i=ListEmpty(L);
        printf("L是否空：i=%d(1:是 0:否)\n",i);
    
        for(j=1;j<=10;j++)
                ListInsert(&L,j,j);
        printf("在L的表尾依次插入1～10后：L.data=");
        ListTraverse(L); 
    
        printf("ListLength(L)=%d \n",ListLength(L));
    
        ListInsert(&L,1,0);
        printf("在L的表头插入0后：L.data=");
        ListTraverse(L); 
        printf("ListLength(L)=%d \n",ListLength(L));
    
        GetElem(L,5,&e);
        printf("第5个元素的值为：%d\n",e);
        for(j=3;j<=4;j++)
        {
        
                k=LocateElem(L,j);
                if(k)
                        printf("第%d个元素的值为%d\n",k,j);
                else
                        printf("没有值为%d的元素\n",j);
        }
        
    
        k=ListLength(L); /* k为表长 */
        for(j=k+1;j>=k;j--)
        {
        
                i=ListDelete(&L,j,&e); /* 删除第j个数据 */
                if(i==ERROR)
                        printf("删除第%d个数据失败\n",j);
                else
                        printf("删除第%d个的元素值为：%d\n",j,e);
        }
        printf("依次输出L的元素：");
        ListTraverse(L); 
    
        j=5;
        ListDelete(&L,j,&e); /* 删除第5个数据 */
        printf("删除第%d个的元素值为：%d\n",j,e);
    
        printf("依次输出L的元素：");
        ListTraverse(L); 
    
        i=ClearList(&L);
        printf("\n清空L后：ListLength(L)=%d\n",ListLength(L));
        CreateListHead(&L,20);
        printf("整体创建L的元素(头插法)：");
        ListTraverse(L); 
        
        i=ClearList(&L);
        printf("\n删除L后：ListLength(L)=%d\n",ListLength(L));
        CreateListTail(&L,20);
        printf("整体创建L的元素(尾插法)：");
        ListTraverse(L); 
    
    
        return 0;
    }

[20200524194027151.png]: https://img-blog.csdnimg.cn/20200524194027151.png
[20200524200440838.png]: https://img-blog.csdnimg.cn/20200524200440838.png
[20200524201113950.png]: https://img-blog.csdnimg.cn/20200524201113950.png
[20200524201652786.png]: https://img-blog.csdnimg.cn/20200524201652786.png
[20200524203020879.png]: https://img-blog.csdnimg.cn/20200524203020879.png
[20200524203226943.png]: https://img-blog.csdnimg.cn/20200524203226943.png
[20200524203255225.png]: https://img-blog.csdnimg.cn/20200524203255225.png
[20200524203318947.png]: https://img-blog.csdnimg.cn/20200524203318947.png
[20200525115157989.png]: https://img-blog.csdnimg.cn/20200525115157989.png
[20200525121544516.png]: https://img-blog.csdnimg.cn/20200525121544516.png
[20200525122005407.png]: https://img-blog.csdnimg.cn/20200525122005407.png
[20200525122614905.png]: https://img-blog.csdnimg.cn/20200525122614905.png
[20200525122658207.png_400x100]: https://img-blog.csdnimg.cn/20200525122658207.png?=400x100
[20200525124412315.png]: https://img-blog.csdnimg.cn/20200525124412315.png