天天看点
返回

数据结构笔记——2. 线性表（1）. 线性表的本质（2）. 线性表的顺序存储结构（3）. 线性表的链式存储结构（4）. 小结

文章目录

  • （1）. 线性表的本质
  • （2）. 线性表的顺序存储结构
  • （3）. 线性表的链式存储结构
  • （4）. 小结

（1）. 线性表的本质

  线性表可用于描述“队列类型”关系的问题

  1. 线性表的定义
    1. 线性表（List）是零个或多个数据元素的集合
    2. 线性表中的数据元素之间是有顺序的
    3. 线性表中的数据元素个数是有限的
    4. 线性表中的数据元素的类型必须相同
  2. 线性表的性质
    1. a0为线性表的第一个元素，只有一个后继
    2. an为线性表的最后一个元素，只有一个前驱
    3. 除a0和an外的其他元素ai，既有前驱，又有后继
    4. 线性表能够逐项访问和顺序存取

（2）. 线性表的顺序存储结构

  1. 顺序存储定义

      线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

  2. 部分功能实现
    1. 存储实现 
      typedef struct _tag_SeqList
{
    int capacity;       // 线性表存储容量
    int length;         // 线性表当前长度
    TSeqListNode* node; // 存储空间起始地址
} TSeqList;
    2. 创建线性表操作
      数据结构笔记——2. 线性表（1）. 线性表的本质（2）. 线性表的顺序存储结构（3）. 线性表的链式存储结构（4）. 小结
      SeqList* SeqList_Create(int capacity) 
{
    TSeqList* ret = NULL;
    
    // 1. 创建存储空间
    if (capacity >= 0)
    {
        ret = (TSeqList*)malloc(sizeof(TSeqList) + sizeof(TSeqListNode) * capacity);
    }
    
    // 2. 初始化线性表
    if (ret != NULL)
    {
        ret->capacity = capacity;
        ret->length = 0;
        // 3. 指针操作
        ret->node = (TSeqListNode*)(ret + 1);
    }
    
    return ret;
}
    3. 插入元素操作
      数据结构笔记——2. 线性表（1）. 线性表的本质（2）. 线性表的顺序存储结构（3）. 线性表的链式存储结构（4）. 小结
      int SeqList_Insert(SeqList* list, SeqListNode* node, int pos)
{
    // 1. 判断线性表是否合法
    TSeqList* sList = (TSeqList*)list;
    int ret = (sList != NULL);
    int i = 0;
    
    // 2. 判断插入位置是否合法
    ret = ret && (sList->length + 1 <= sList->capacity);
    ret = ret && (0 <= pos);
    
    if (ret)
    {
        // 3. 若插入位置大于当前长度，则将元素放在最后
        if (pos >= sList->length)
        {
            pos = sList->length;
        }
        
        // 4. 从最后一个元素开始到第pos个元素，分别将他们都向后移动一个位置
        for (i = sList->length; i > pos; i--)
        {
            sList->node[i] = sList->node[i-1];
        }
        
        // 5. 将新元素插入
        sList->node[i] = (TSeqListNode)node;
        
        // 6. 长度加1
        sList->length++;
    }
    
    return ret;
}
    4. 删除元素操作
      数据结构笔记——2. 线性表（1）. 线性表的本质（2）. 线性表的顺序存储结构（3）. 线性表的链式存储结构（4）. 小结
      SeqListNode* SeqList_Delete(SeqList* list, int pos)
{
    // 1. 进行位置合法性检测与删除元素获取
    TSeqList* sList = (TSeqList*)list;
    SeqListNode* ret = SeqList_Get(list, pos);
    int i = 0;
    
    // 2. 判断线性表是否合法
    if (ret != NULL)
    {
         // 3. 把删除位置pos后的元素分别向前移动一个位置
        for (i = pos + 1; i < sList->length; i++)
        {
            sList->node[i - 1] = sList->node[i];
        }
        
        // 4. 长度减1
        sList->length--;
    }
    
    return ret;
}
  3. 优缺点：
    1. 优点：
      • 无需为线性表中的逻辑关系增加额外的空间
      • 可以快速的获取表中合法位置的元素
    2. 缺点：
      • 插入和删除操作需要移动大量元素
      • 当线性表长度变化较大时难以确定存储空间的容量
  4. 工程实例
    1. 头文件 
      #ifndef _SEQLIST_H_
#define _SEQLIST_H_

typedef void SeqList;
typedef void SeqListNode;

/*
    该方法用于创建并且返回一个空的线性表
*/
SeqList* SeqList_Create(int capacity);

/*
    该方法用于销毁一个线性表list
*/
void SeqList_Destroy(SeqList* list);

/*
    该方法用于将一个线性表list中的所有元素清空
    使得线性表回到创建时的初始状态
*/
void SeqList_Clear(SeqList* list);

/*
    该方法用于返回一个线性表list中的所有元素个数
*/
int SeqList_Length(SeqList* list);

/*
    该方法用于返回一个线性表list中最大容量
*/
int SeqList_Capacity(SeqList* list);

/*
    该方法用于向一个线性表list的pos位置处插入新元素node
    返回值为1表示插入成功，0表示插入失败
*/
int SeqList_Insert(SeqList* list, SeqListNode* node, int pos);

/*
    该方法用于获取一个线性表list的pos位置处的元素
    返回值为pos位置处的元素，NULL表示获取失败
*/
SeqListNode* SeqList_Get(SeqList* list, int pos);

/*
    该方法用于删除一个线性表list的pos位置处的元素
    返回值为被删除的元素，NULL表示删除失败
*/
SeqListNode* SeqList_Delete(SeqList* list, int pos);

#endif
    2. 实现文件 
      #include <stdio.h>
#include <malloc.h>
#include "SeqList.h"

typedef unsigned int TSeqListNode;

typedef struct _tag_SeqList
{
    int capacity;
    int length;
    TSeqListNode* node;
} TSeqList;

SeqList* SeqList_Create(int capacity) 
{
    TSeqList* ret = NULL;
    
    // 1. 创建存储空间
    if (capacity >= 0)
    {
        ret = (TSeqList*)malloc(sizeof(TSeqList) + sizeof(TSeqListNode) * capacity);
    }
    
    // 2. 初始化线性表
    if (ret != NULL)
    {
        ret->capacity = capacity;
        ret->length = 0;
        // 3. 指针操作
        ret->node = (TSeqListNode*)(ret + 1);
    }
    
    return ret;
}

void SeqList_Destroy(SeqList* list) 
{
    free(list);
	list = NULL;
}

void SeqList_Clear(SeqList* list)
{
    TSeqList* sList = (TSeqList*)list;
    
    if( sList != NULL )
    {
        sList->length = 0;
    }
}

int SeqList_Length(SeqList* list)
{
    TSeqList* sList = (TSeqList*)list;
    int ret = -1;
    
    if( sList != NULL )
    {
        ret = sList->length;
    }
    
    return ret;
}

int SeqList_Capacity(SeqList* list)
{
    TSeqList* sList = (TSeqList*)list;
    int ret = -1;
    
    if( sList != NULL )
    {
        ret = sList->capacity;
    }
    
    return ret;
}

int SeqList_Insert(SeqList* list, SeqListNode* node, int pos)
{
    // 1. 判断线性表是否合法
    TSeqList* sList = (TSeqList*)list;
    int ret = (sList != NULL);
    int i = 0;
    
    // 2. 判断插入位置是否合法
    ret = ret && (sList->length + 1 <= sList->capacity);
    ret = ret && (0 <= pos);
    
    if (ret)
    {
        // 3. 若插入位置大于当前长度，则将元素放在最后
        if (pos >= sList->length)
        {
            pos = sList->length;
        }
        
        // 4. 从最后一个元素开始到第pos个元素，分别将他们都向后移动一个位置
        for (i = sList->length; i > pos; i--)
        {
            sList->node[i] = sList->node[i-1];
        }
        
        // 5. 将新元素插入
        sList->node[i] = (TSeqListNode)node;
        
        // 6. 长度加1
        sList->length++;
    }
    
    return ret;
}

SeqListNode* SeqList_Get(SeqList* list, int pos)
{
    TSeqList* sList = (TSeqList*)list;
    SeqListNode* ret = NULL;
    
    if ((sList != NULL) && (0 <= pos) && (pos < sList->length))
    {
		ret = (SeqListNode*)(sList->node[pos]);
    }
    
    return ret;
}

SeqListNode* SeqList_Delete(SeqList* list, int pos)
{
    // 1. 进行位置合法性检测与删除元素获取
    TSeqList* sList = (TSeqList*)list;
    SeqListNode* ret = SeqList_Get(list, pos);
    int i = 0;
    
    // 2. 判断线性表是否合法
    if (ret != NULL)
    {
         // 3. 把删除位置pos后的元素分别向前移动一个位置
        for (i = pos + 1; i < sList->length; i++)
        {
            sList->node[i - 1] = sList->node[i];
        }
        
        // 4. 长度减1
        sList->length--;
    }
    
    return ret;
}
    3. 测试文件 
      #include <stdio.h>
#include <stdlib.h>
#include "SeqList.h"

int main(int argc, char *argv[]) 
{
    SeqList* list = SeqList_Create(3);
    
    int i = 0;
    int j = 1;
    int k = 2;
    int x = 3;
    int index = 0;
    
    SeqList_Insert(list, &i, 0);
    SeqList_Insert(list, &j, 0);
    SeqList_Insert(list, &k, 0);
    SeqList_Insert(list, &x, 0);
    for(index=0; index<SeqList_Length(list); index++)
    {
        int* p = (int*)SeqList_Get(list, index);
        
        printf("%d\n", *p);
    }
    
    printf("\n");
    
    while( SeqList_Length(list) > 0 )
    {
        int* p = (int*)SeqList_Delete(list, 0);
        
        printf("%d\n", *p);
    }
    
    SeqList_Destroy(list);
    
    return 0;
}

（3）. 线性表的链式存储结构

  1. 链式存储定义

      为了表示每一个数据元素与其直接后继元素之间的逻辑关系，每个元素除了存储本身的信息外，还需要存储指示其直接后继的信息。

    数据结构笔记——2. 线性表（1）. 线性表的本质（2）. 线性表的顺序存储结构（3）. 线性表的链式存储结构（4）. 小结
  2. 部分功能实现
    1. 插入元素操作
      数据结构笔记——2. 线性表（1）. 线性表的本质（2）. 线性表的顺序存储结构（3）. 线性表的链式存储结构（4）. 小结
      int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)
    { 
        // 1. 线性表与插入位置合法性检测
        TLinkList* sList = (TLinkList*)list;
        int ret = (sList != NULL) && (pos >= 0) && (node != NULL);
        int i = 0;
        
        if( ret )
        {
            LinkListNode* current = (LinkListNode*)sList;
            
            // 2. 由表头开始通过next指针移动pos次后，当前元素的next指针即指向要插入的位置
            for(i=0; (i<pos) && (current->next != NULL); i++)
            {
                current = current->next;
            }
            
            // 3. 将新元素插入
            node->next = current->next;
            current->next = node;
            
            // 4. 线性表长度加1
            sList->length++;
        }
        
        return ret;
    }
    2. 删除元素操作
      数据结构笔记——2. 线性表（1）. 线性表的本质（2）. 线性表的顺序存储结构（3）. 线性表的链式存储结构（4）. 小结
      LinkListNode* LinkList_Delete(LinkList* list, int pos)
    {
        TLinkList* sList = (TLinkList*)list;
        LinkListNode* ret = NULL;
        int i = 0;
        
    	// 1. 线性表与删除位置合法性检测
        if( (sList != NULL) && (0 <= pos) && (pos < sList->length) )
        {
            LinkListNode* current = (LinkListNode*)sList;
    		
            // 2. 由表头开始通过next指针移动pos次后，当前元素的next指针即指向要删除元素的位置
            for(i=0; i<pos; i++)
            {
                current = current->next;
            }
            
    		// 3. 获取将删除的元素
            ret = current->next;
    		
    		// 4. 将元素舍弃
            current->next = ret->next;
            
    		// 5. 线性表长度减1
            sList->length--;
        }
        
        return ret;
    }
  3. 优缺点：
    1. 优点：
      • 无需一次性定制链表的容量
      • 插入和删除操作无需移动数据元素
    2. 缺点：
      • 数据元素必须保存后继元素的位置信息
      • 获取指定数据的元素操作需要顺序访问之前的元素
  4. 工程实例
    1. 头文件 
      #ifndef _LINKLIST_H_
#define _LINKLIST_H_

typedef void LinkList;
typedef struct _tag_LinkListNode LinkListNode;
struct _tag_LinkListNode
{
    LinkListNode* next;
};

/*
	该方法用于创建并且返回一个空的线性表
*/
LinkList* LinkList_Create();

/*
	该方法用于销毁一个线性表list
*/
void LinkList_Destroy(LinkList* list);

/*
	该方法用于将一个线性表list中的所有元素清空
	使得线性表回到创建时的初始状态
*/
void LinkList_Clear(LinkList* list);

/*
	该方法用于返回一个线性表list中的所有元素个数
*/
int LinkList_Length(LinkList* list);

/*
	该方法用于向一个线性表list的pos位置处插入新元素node
	返回值为1表示插入成功，0表示插入失败
*/
int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);

/*
	该方法用于获取一个线性表list的pos位置处的元素
	返回值为pos位置处的元素，NULL表示获取失败
*/
LinkListNode* LinkList_Get(LinkList* list, int pos);

/*
	该方法用于删除一个线性表list的pos位置处的元素
	返回值为被删除的元素，NULL表示删除失败
*/
LinkListNode* LinkList_Delete(LinkList* list, int pos);

#endif
    2. 实现文件 
      #include <stdio.h>
#include <malloc.h>
#include "LinkList.h"

typedef struct _tag_LinkList
{
    LinkListNode header;
    int length;
} TLinkList;

LinkList* LinkList_Create() 
{
    TLinkList* ret = (TLinkList*)malloc(sizeof(TLinkList));
    
    if( ret != NULL )
    {
        ret->length = 0;
        ret->header.next = NULL;
    }
    
    return ret;
}

void LinkList_Destroy(LinkList* list) 
{
    free(list);
	
	list = NULL;
}

void LinkList_Clear(LinkList* list) 
{
    TLinkList* sList = (TLinkList*)list;
    
    if( sList != NULL )
    {
        sList->length = 0;
        sList->header.next = NULL;
    }
}

int LinkList_Length(LinkList* list) 
{
    TLinkList* sList = (TLinkList*)list;
    int ret = -1;
    
    if( sList != NULL )
    {
        ret = sList->length;
    }
    
    return ret;
}

int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)
{ 
    TLinkList* sList = (TLinkList*)list;
    int ret = (sList != NULL) && (pos >= 0) && (node != NULL);
    int i = 0;
    
    if( ret )
    {
        LinkListNode* current = (LinkListNode*)sList;
        
        for(i=0; (i<pos) && (current->next != NULL); i++)
        {
            current = current->next;
        }
        
        node->next = current->next;
        current->next = node;
        
        sList->length++;
    }
    
    return ret;
}

LinkListNode* LinkList_Get(LinkList* list, int pos) 
{
    TLinkList* sList = (TLinkList*)list;
    LinkListNode* ret = NULL;
    int i = 0;
    
    if( (sList != NULL) && (0 <= pos) && (pos < sList->length) )
    {
        LinkListNode* current = (LinkListNode*)sList;
        
        for(i=0; i<pos; i++)
        {
            current = current->next;
        }
        
        ret = current->next;
    }
    
    return ret;
}

LinkListNode* LinkList_Delete(LinkList* list, int pos)
{
    TLinkList* sList = (TLinkList*)list;
    LinkListNode* ret = NULL;
    int i = 0;

    if( (sList != NULL) && (0 <= pos) && (pos < sList->length) )
    {
        LinkListNode* current = (LinkListNode*)sList;

        for(i=0; i<pos; i++)
        {
            current = current->next;
        }

        ret = current->next;

        current->next = ret->next;
        
        sList->length--;
    }
    
    return ret;
}
    3. 测试文件 
      #include <stdio.h>
#include <stdlib.h>
#include "LinkList.h"

struct Value
{
    LinkListNode header;
    int v;
};

int main(int argc, char *argv[]) 
{
    int i = 0;
    LinkList* list = LinkList_Create();
    
    struct Value v1;
    struct Value v2;
    
    v1.v = 1;
    v2.v = 2;

    LinkList_Insert(list, (LinkListNode*)&v1, LinkList_Length(list));
    LinkList_Insert(list, (LinkListNode*)&v2, LinkList_Length(list));

    
    for(i=0; i<LinkList_Length(list); i++)
    {
        struct Value* pv = (struct Value*)LinkList_Get(list, i);
        
        printf("%d\n", pv->v);
    }
    
    while( LinkList_Length(list) > 0 )
    {
        struct Value* pv = (struct Value*)LinkList_Delete(list, 0);
        
        printf("%d\n", pv->v);
    }
    
    LinkList_Destroy(list);
    
    return 0;
}

（4）. 小结

  1. 代码难点主要在于插入与删除的实现，后续代码实现会在此代码基础上进行修改或调用。
  2. 本文及以后代码实现，目的在于实现一种可复用的代码程序，故只保存具体数据元素的地址。
数据结构 线性表 顺序存储 链式存储 线性表本质
上一篇: case-服务超时排查
下一篇: CG 3. 线性表 顺序结构

继续阅读