数据结构-线性表（顺序表和链表）

大纲：

  1. 理解线性表的逻辑结构
  2. 掌握线性表的顺序存贮结构和链式存贮结构；掌握线性表基本操作的实现。
  3. 了解线性表的应用。

线性表的定义和基本操作

  1. 线性表的定义

    具有相同数据类型的n（n>=0）个数据元素的有限序列

    线性表的特点：

    • 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继
    • 表中元素的个数有限
    • 表中元素具有逻辑上的顺序性
    • 表中每个元素都是数据元素，每个元素都是单个元素
    • 表中元素的数据类型都相同，即每一个元素占有相同大小的存储空间
    • 表中元素具有抽象性，即只关注于逻辑结构，不关注于元素表示什么内容
  • 线性表示一种逻辑结构，表示元素之间一对一的相邻关系；顺序表和链表是存储结构，表示物理结构
  1. 线性表的基本操作

    InitList(&L)：初始化表
    Length(L)：求表长
    LocateElem(L,e)：按值查找操作
    GetElem(L,i)：按位查找操作
    ListInsert(&L,e)：插入操作
    ListDelete(&L,i,&e)：删除操作
    PrintList(L)：输出操作
    Empty(L)：判空操作
    DestroyList(&L)：销毁操作

线性表的顺序表示

  1. 顺序表的定义

    用一组连续的存储单元，依次存储线性表中的数据元素，使得逻辑上相邻的数据元素在物理位置上也相邻。

    结构体描述：

    //数组空间静态分配
#define MaxSize 50  //数组最大长度
typedef struct{
  ElemType data[MaxSize];  //顺序表的元素  
  int length;  //顺序表当前长度
}SqList;  //静态分配数组顺序表的类型定义

//数组空间动态分配
#define InitSize 100  //表长度的初始定义
typedef struct{
  ElemType *data;
  int MaxSize,length;
}SeqList;  //动态分配数组顺序表的类型定义
    • C的初始动态分配语句
      L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
    • 顺序表的特点是随机访问，并且存储密度高。但是增删操作需要移动大量元素

  2. 基本操作相关代码
    2.1 插入操作

    bool ListInsert(SqList &L,int i,ElemType e){
  if(i<1 || i>L.length)  //判断插入范围是否有效
    return false;
  if(i.length>=MaxSize)  //判断存储空间是否已满
    return false;
  for(int j=L.lengt;j>=i;j--)  //将i之后的元素依次向后移动
    L.data[j]=L.data[j-1];
  L.data[i-1]=e;  //在i位置上赋值，注意，i是位置序号，i-1是数组下标
  L.length++;  // 长度加一
  return true;
}
    • 移动节点平均次数为n/2，时间复杂度为O(n)

    2.2 删除操作

    bool ListDelete(SqList &L,int i,ElemType &e){
  if(i<0 || i>L.length)  //判断删除范围是否有效
    return false;
  for(int j=i;j<L.length;j++)  //将i之后的值依次前移
    L.data[j-1]=L,data[j];
  L.length--;  //长度减一
  return false;
}
    • 移动节点平均次数(n-1)/2，时间复杂度为O(n)

    2.3 按值查找

    int LocateElem(SqList L,ElemType e){
  //实现查找顺序表中值为e的元素，查找成功则返回元素位序，否则返回0
  int i;
  for(i=0;i<L>length;i++)
    if(L.data[i]==e)
      return i+1;  //下标为i的元素值为e，其位置为i+1
  return 0;
}
    • 移动节点平均次数为(n+1)/2，时间复杂度为O(n)

线性表的链式表示

单链表

  1. 单链表的定义

    通过一组任意的存储单元来存储线性表中的数据元素，每个链表节点除了存放自身的信息之外，还要存放一个指向后继的指针。其中data为数据域，next为指针域。

    结点类型定义

    typedef struct LNode{
  ElemType data;
  struct LNode *next;
}LNode,*LinkList;
    • LinkList L==LNode *L
    • 单链表中的元素是离散地分布在存储空间中的，所以是非随机存取存储结构，想找到某个元素必须从头遍历
    • 通常用头指针标识一个单链表，此外，在单链表的第一个结点之前附加一个结点，称为头结点。头结点中可以不加任何信息，也可以记录表长等信息。
    • 引入头结点的优点：
      • 开始结点放在头结点的指针域中，所以链表的第一个位置上的操作与其他位置上的操作一致，不需要特殊处理
      • 若链表为空，头指针是指向头结点的非空指针（头结点的指针域为空），所以空表与非空表的处理统一
    • 单链表解决了顺序表需要大量连续存储空间的缺点，但是单链表附加指针域，也存在浪费存储空间的缺点

  2. 基本操作相关代码
    2.1 建立单链表

    //头插法
LinkList CreatList1(LinkList &L){
  //从表尾到表头逆向建立单链表L，每次均在头结点之后插入元素
  LNode *s;
  int x;
  L=(LinkList)malloc(sizeof(LNode));  //创建头结点
  L->next=NULL;  //初始空链表
  scanf("%d",&x);  //输入结点中的元素
  while(x!=999){
    s=(LNode*)malloc(sizeof(LNode));  //创建新的结点
    //下面三条代码为头插法的插入细则
    s->data=s;
    s->next=L->next;
    L->next=s;
    scanf("%d",&x);
  }
  return L;
}

//尾插法
LinkList CreatList2(LinkList &L){
  //从表头到表尾正向建立单链表L，每次均在表尾插入元素
  LNode *s,*r=L;  //除了s这个新结点的指针，还建立了一个指向尾结点的r指针
  int x;
  L=(LinkList)malloc(sizeof(LNode));
  L->next=NULL;
  scanf("%d",&x);
  while(x!=999){
    s=(LNode*)malloc(sizeof(LNode));
    //以下三条代码为尾插法的插入细则
    s->data=s;
    r->next=s;
    r=s;  //r指向新的尾结点
    scanf("%d",&x);
  }
  r->next=NULL;
  return L;
}
    • 头插法建立单链表，读入数据的顺序与生成的链表中的元素的顺序是相反的；尾插法建立单链表，读入数据的顺序与生成的链表中的元素的顺序是相同的
    • 两种方法的时间复杂度都为O(n)

    2.2 按序号查找结点值

    LNode *GetElem(LinkList L,int i){
  int j=1;  //计数器
  LNode *p=L->next;  //p指向头结点指针
  if(i==0)
    return L;
  if(i<1)
    return NULL;
  while(p&&j<i){  //从第一个结点开始找，查找第i-1个结点
    p=p->next;
    j++;
  }
  return p;  //返回第i个结点的指针，如果i大于表长，p=NULL，直接返回p即可
}
    • 时间复杂度为O(n)

    2.3 按值查找

    LNode *LocateElem(LinkList L,ElemType e){
  LNode *p=L->next;
  while(p!=NULL&&p->data!=e)
    p=p->next;
  return p;
}
    • 时间复杂度为O(n)

    2.4 插入结点主要代码片段

    p=GetElem(L,i-1);  //查找插入位置的前驱结点
s->next=p->next;
p->next=s;
    • 时间复杂度为O(1)
    • 单链表一般都是后插操作，但可以通过如下方式将前插操作转化为后插操作 
      //将s结点插入到p结点之前的主要代码片段
s->next=p->next;
p->next=s;
temp=p->data;  //交换数据域
p->data=s->data;
s->data=temp;

    2.5 删除结点操作

    //删除当前指针下一个结点
p=GetElem(L,i-1);
q=p->next;
p->next=q->next;
free(p);

//删除当前指针所在结点
q=p->next;
p->data=p->next->data;
p->next=q->next;
free(q);
    • 第一个删除操作时间复杂度为O(n)；第二个删除操作时间复杂度为O(1)

双链表

双链表是在单链表只有一个指向后继结点的指针next的基础上，增加了一个指向前驱结点的指针prior

  • 单链表想访问某个结点的前驱结点时，只能从头遍历，访问后继结点的时间复杂度为O(1)，访问前驱结点的时间复杂度O(n)

结点类型定义

typedef struct DNode{
  ElemType data;
  struct DNode *prior,*next;
}DNode,*LinkList;
  • 插入操作主要代码片段
s->next=p->next;
p->next-prior=s;
s->prior=p;
p->next=s;
  • 删除操作主要代码片段
p->next=q->next;
q->next->prior=p;
free(p);

循环链表

循环单链表： 在单链表的基础上，表中最后一个结点的指针不是NULL，而是改为指向头结点，整个链表形成一个环

  • 因为没有指针域为NULL的结点，所以，循环单链表的判空条件不是头结点的指针是否为空，而是它是否等于头指针。
  • 插入，删除操作算法与单链表一致，只是在表尾操作有所不同，需维持环的状态。且，任何位置插入，删除操作都是等价的，所以不需要判断表尾

循环双链表：在双链表的基础上，表中最后一个结点的指针不是NULL，而是改为指向头结点，整个链表形成一个环

  • 判空条件为头结点的prior域和next域都等于头结点

静态链表

静态链表是借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next，不过这里的指针域指的是数组下标（游标）

结点类型定义

#define MaxSize  //静态链表的最大长度
typedef struct{
  ElemType data;
  int next;   //下一个元素的数组下标
}SLinkList[MaxSize];
  • 同顺序表一样，需要预先分配一块连续的内存空间
  • 静态链表以next=-1作为其结束的标志

顺序表和单链表的比较

  1. 存取方式
    顺序表可以顺序存取，也可以随机存取；链表只能顺序存取
  2. 逻辑结构和物理结构
    顺序表，逻辑上相邻的元素，物理位置上也相邻；链表，逻辑上相邻的元素，物理位置上不一定相邻
  3. 查找，插入和删除操作时间复杂度
    按值查找：顺序表无序时，两者时间复杂度都是O(n)；当顺序表有序时，可以采用折半查找，时间复杂度为O(log₂n)
    按位查找：顺序表支持随机访问，时间复杂度为O(1)；链表平均时间复杂度为O(n)
    插入，删除的时间内复杂度见上
  4. 空间分配
    顺序表易造成空间浪费，链表则不会
  • 实际中，应基于存储，运算，环境的多方面考虑，恰当地选择存储结构
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 200,841评论 5赞 472
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 84,415评论 2赞 377
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 147,904评论 0赞 333
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,051评论 1赞 272
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,055评论 5赞 363
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,255评论 1赞 278
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,729评论 3赞 393
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,377评论 0赞 255
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,517评论 1赞 294
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,420评论 2赞 317
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,467评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,144评论 3赞 317
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,735评论 3赞 303
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,812评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,029评论 1赞 256
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,528评论 2赞 346
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,126评论 2赞 341