C语言数据结构之线性表

第五课:线性表的本色 

线性表(List)是零个或者是四只数据元素的集合 

小心(这个要求爆发三三两两类似于数组,可是同数组是有分此外,不要混淆): 

  1. 线性表中的数量元素中是一成不变的 

  2. 线性表中的数码元素的个数是零星的 

  3. 线性表中的多少元素的花色必须一律
     
    丝性表的科班定义:  

线性表是具有同样档次的n(n≥0)个数据元素的一定量连串  (a1, a2, …. an)

an是表项, n代表长度
 
  线性表的性质: 

  1. a0是线性表的第一单元素,只出一个继;

  2. an是线性表的结尾一个素,只生一个前任; 

  3. 除此之外a0和an之外的别元素ai,既来前人,也暴发后;

  4. 线性表可以逐项访问同一一存取   

1. 赢得线性表中的元素的操作 

1.1 判断线性表是否合法 

1.2 判断地方是否合法

1.3 直接通过数组下标的法取元素

示范代码:

  char Get(List list, int pos)
  {
   char ret = -1;
   //判断线性表和位置是否合法
   if((list != NULL) && (0 <= pos) && (pos < list->length))
   {
    //获取元素
    ret = list->node[pos];
   }
   return ret;
  }

第七课:线性表的顺序存储结构(数组的艺术贯彻) 

顺序存储的概念: 
线性表的顺序存储结构,是用相同段子地址连续的存储单元依次存储线性表的数量元素
— 这有点近乎于数组 

譬如:从地址0xAABBCCDD起先储存线性表的n个元素: 

a1 。。。。ak 。。。。。。an

  所以,在C语言中,线性表的顺序存储结构得以据此同样维数组来落实

  需要厘清的要领:

  1. 囤空间的前奏地方

  2. 线性表的但是老容量:MAXSIZE

  3.线性表的即长:length

  示例:

  #define MAXSIZE 20
  typedef struct _tag_List
  {
   char node[MAXSIZE];
   int length; 
  } List;

  相关操作的切切实实贯彻: 

3. 去除元素 

3.1 判断线性表时候合法 

3.2 判断删除地点是不是合法 

3.3 将元素取出

3.4 将去地点后的元素分别上移动一个职务 

3.5 线性表长度减1

 示例代码:

  char Delete(List list, int pos)
  {
   char ret = -1;
   int i = 0;

   // 1 判断线性表时候合法
   // 2 判断删除位置是否合法
   if((list != NULL) && (0 <= pos) && (pos <= list->length))
   {
    // 3 将元素取出
    ret = list->node[pos];

    // 4 将删除位置后的元素分别向前移动一个位置
    for(i=pos+1; i<list->length; i++)
    {
     list->node[i-1] = list->node[i];
    }
    // 5 线性表长度减1
    list->length--;
   }
   return ret;
  }

 
顺序存储结构的败笔: 

每当插入和去元素的时候,有时候要走大量之要素, 

譬如说,倘若这顺序表来几十万单数据,要插入或是要去除的的元素是在线性表的极前面,

那么就是待把即刻几十万独要素依次前移或是依次后移,这会降程序的推行功能

 

一个完的以身作则:

SeqList.h

#ifndef _SEQ_LIST_H_

#define _SEQ_LIST_H_

typedef void SeqList;
typedef void SeqListNode;


SeqList *SeqList_Create(int capactiy);//创建并返回一个容量为capactiy的空的线性表

int SeqList_Capactiy(SeqList *list);//返回线性表的最大容量

void SeqList_Destory(SeqList *list);//销毁一个已经存在的线性表(应该在内部进行检查,如果线性表不存在,要报错)

void SeqList_Clear(SeqList *list);//清空线性表中的额所有元素,使线性表恢复到创建时的状态

int SeqList_Insert(SeqList *list, SeqListNode *node, int pos);//在位置pos处插入一个新的元素node,返回值为1表示插入成功, 0表示插入失败

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

SeqListNode *SeqList_Get(SeqList *list, int pos);//获得位置pos处的元素,返回值是pos处的元素,NULL表示获取失败

int SeqList_Length(SeqList *list);//返回线性表中所有元素的个数

//还可以添加一个修改元素的函数 和一个查询函数(增 删 改 查)

#endif

SeqList.c

#include <stdio.h>
#include <malloc.h>    //用于动态申请释放内存
#include "SeqList.h"


typedef unsigned int TSeqListNode;//把线性表中的数据元素定义为unsigned int,是为了能够复用,

typedef struct _tag_SeqList
{
    int capacity;    //线性表的最大容量
    int length;        //线性表的长度
    TSeqListNode *node;
}TSeqList;



SeqList *SeqList_Create(int capactiy)//创建并返回一个空的线性表
{
    TSeqList *ret = NULL;

    if (capactiy >= 0)//判断参数是否合法
    {
        // 申请的内存空间为什么要加上sizeof(TSeqListNode) * capactiy,因为线性表要存储数据,结构体中的第三个元素只是是一个指针,
        // 它指向的是实际的数据的存储空间的地址,这样可以把线性表的属性(容量,长度,数据)和实际数据进行分开处理
        ret = (TSeqList *)malloc(sizeof(TSeqList) + sizeof(TSeqListNode) * capactiy);

        if (ret != NULL)//判断申请的空间是否成功
        {
            ret->capacity = capactiy;//
            ret->length = 0;    //刚开始创建,还没有数据,长度就是0
            ret->node = (TSeqListNode *)(ret + 1);
        }
        //printf("%p\n", ret);
    } 

    //if (ret != NULL)//判断申请的空间是否成功
    //{
    //    ret->capacity = capactiy;//
    //    ret->length = 0;    //刚开始创建,还没有数据,长度就是0
    //    ret->node = (TSeqListNode *)(ret + 1);
    //}
    return ret;
}

void SeqList_Clear(SeqList *list)//清空线性表中的额所有元素,使线性表恢复到创建时的状态
{
    TSeqList *slist = (TSeqList *)list;    //做一次强制类型转换

    if (slist != NULL)
    {
        slist->length = 0;
    }
}

int SeqList_Length(SeqList *list)//返回线性表中所有元素的个数
{
    int ret = -1;
    TSeqList *slist = (TSeqList *)list;    //做一次强制类型转换

    if (slist != NULL)
    {
        ret = slist->length;
    }
    return ret;
}

int SeqList_Capactiy(SeqList *list)//返回线性表的最大容量
{
    int ret = -1;
    TSeqList *slist = (TSeqList *)list;    //做一次强制类型转换

    if (slist != NULL)
    {
        ret = slist->capacity;
    }
    return ret;
}

int SeqList_Insert(SeqList *list, SeqListNode *node, int pos)//在位置pos处插入一个新的元素node,返回值为1表示插入成功, 0表示插入失败
{
    TSeqList *slist = (TSeqList *)list;    //做一次强制类型转换

    int ret = (slist != NULL);
    int i = 0;

    ret = ret && (slist->length+1 <= slist->capacity);// 插入之后的线性表的长度应该要小于或等于线性表的最大长度
    ret = ret && (pos >= 0);//判断插入的位置是否合法

    if (ret)
    {
        if (pos >= slist->length)    //如果待插入的位置大于线性表的长度,把要插入的元素直接放在线性表的最后一个位置
        {
            pos = slist->length;
        }

        for (i = slist->length; i > pos; i--)//挪动元素位置,这一步可能是最耗时的
        {
            slist->node[i] = slist->node[i-1];
        }

        slist->node[i] = (TSeqListNode)node;  // 在空出来的地方插入元素
        slist->length++;    //线性表的长度要加1
    }

    return ret;
}

SeqListNode *SeqList_Delete(SeqList *list, int pos)//删除pos位置处的一个元素,返回值为被删除的元素, NULL表示删除失败
{
    TSeqList *slist = (TSeqList *)list;    //做一次强制类型转换
    SeqListNode *ret = SeqList_Get(list, pos);    //先取出要删除的元素

    int i = 0;

    if (ret != NULL)
    {
        for (i = pos+1; i<slist->length; i++)
        {
            slist->node[i-1] = slist->node[i];
        }
        slist->length--;
    }

    return ret;
}

SeqListNode *SeqList_Get(SeqList *list, int pos)//获得位置pos处的元素,返回值是pos处的元素,NULL表示获取失败
{
    TSeqList *slist = (TSeqList *)list;    //做一次强制类型转换

    SeqListNode *ret = NULL;    //这里需要注意

    if ((slist != NULL) && (0 <= pos) && (pos <= slist->length))
    {
        ret = (SeqListNode *)(slist->node[pos]);
    }

    return ret;
}

void SeqList_Destory(SeqList *list)//销毁一个已经存在的线性表(应该在内部进行检查,如果线性表不存在,要报错)
{
    free(list);
}

 

main.c

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

int main(int argc, char *argv[])
{
    // 1. 顺序存储测试程序:
    int i=0, j=1, k=2, x=3, y=4, z=5;
    int index = 0;
    SeqList *list = SeqList_Create(10000);

    SeqList_Insert(list, &i, 0);
    SeqList_Insert(list, &j, 0);
    SeqList_Insert(list, &k, 0);
    SeqList_Insert(list, &x, 0);
    SeqList_Insert(list, &y, 0);
    SeqList_Insert(list, &z, 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_Destory(list);

    // 2. 链式存储测试代码:


    return 0;
}

 

2. 安插元素算法 

2.1 判断线性表时候合法 

2.2 判断插入地方是不是合法 

2.3 把最终一个因素一向顶插入地方的要素顺序后换一个职 

2.4 将新元素插入 

2.5 线性表长度加1 

演示代码:

  int Insert(List list, char c, int pos)
  {
   // 1 判断线性表时候合法
   int i = 0;
   int ret = (list != NULL);

   // 2 判断插入位置是否合法
   ret = ret && (list->length + 1 <= MAXSIZE);
   ret = ret && (0 <= pos);

   if(ret)
   {
    if(pos >= list->length)
    {
     pos = list->length;
    }
    // 3 把最后一个元素一直到插入位置的元素顺序后移一个位置
    for(i=list->legth; i>pos; i--)
    {
     list->node[i] = list->node[i-1];
    }
    // 4 将新元素插入
    list->node[i] = c;
    // 5 线性表长度加1
    list->length++;
   }
   return ret;
  }

 

第六征缴:线性表的连带操作 

常用操作: 

  1. 创制丝性表

  2. 销毁线性表

  3. 清空线性表

  4. 在线性表中插入元素 

  5. 起线性表中删除元素

  6. 获取线性表中某个元素的地点

  7. 取线性表的长短
     
      问题:咋样超过后中表述和使用线性表?
     
     
    线性表在次中表现为同样栽万分的数据类型,相应的操作,在次中显现呢同组函数
     
      示例:

    List List_Create();
    void List_Destory(List ist);
    void List_Clear(List list);
    int List_Insert(List list, ListNode node, int pos);
    ListNode List_Delete(List list, int pos);
    ListNode ListGet(List list, int pos);
    int List_Length(List list);

  问题:

  1. 线性表的依次函数是怎么兑现之?

  2. 发两种植线性表的实现形式为?

  3. 每种实现情势的得失是啊?