数据结构之线性表(顺序表、单链表、双链表)(二)

本文涉及的产品
传统型负载均衡 CLB,每月750个小时 15LCU
应用型负载均衡 ALB,每月750个小时 15LCU
网络型负载均衡 NLB,每月750个小时 15LCU
简介: 数据结构之线性表(顺序表、单链表、双链表)

实例设计


1、编程实现如下任务:建立一个线性表,首先依次输入数据元素1, 2, 3,…,10,然后删除数据元素5,最后依次显示当前线性表中的数据元素。假设该线性表的数据元素个数在最坏情况下不会超过100个。要求使用顺序表。


#include<stdio.h>
#define MaxSize 100
typedef int ElemType;
#include"sequencelist.h"
void main(void)
{
    SequenceList myList; //声明 
    int i, x;
    ListInitialize(&myList); //初始化 
    for(i = 0; i<10; i++)
    {
        ListInsert(&myList, i, i+1); //插入 
    }
    ListDelete(&myList, 4, &x); //删除5即下标为4 
    for(i = 0; i<ListLength(myList); i++)
    {
        ListGet(myList, i, &x); //获取 
        printf("%d ", x);
    }
}

2、设计一个顺序表的删除函数,把顺序表L中的数据元素x删除。


//成功返回1,不成功返回0
int ListDeleteX(SequenceList *L, ElemType x)
{
    int i, j;
    for(i=0; i<L->size; i++)
    {
        if(x == L->list[i])
        {
            break; //找到x则退出循环 ,此时x下标已被记录
        }
    }
    if(i == L->size) return 0;
    for(j = i; j<L->size; j++)
    {
        L->list[j] = L->list[j+1];  //向前移动一位
    }
    L->size--;
    return 1;           
}

3、编写算法实现顺序表逆置,要求把顺序表A中数据元素序列(a0,a1,a2,…..an-1)逆置为(an-1, ….. a2, a1,a0)存储到顺序表B中。


void Converse(SequenceList la, SequenceList *lb)
{
    int i;
    ListInitialize(lb);
    for(i = 0; i<la.size; i++)
    {
        lb->list[i] = la.list[la.size-i-1];
        lb->size++;
    }
}

4、自身逆置


void ConverseSelf(SequenceList *la)
{
    SequenceList lb;
    int i, j;
    ListInitialize(&lb);
    for(i = 0; i<la->size; i++)
    {
        lb.list[i] = la->list[la->size-i-1];
        lb.size++;
    }
    for(j = 0; j<lb.size; j++)
    {
        la->list[j] = lb.list[j];
    }
}

4 线性表的链式表示和实现


单链表中,构成链表的结点只有一个指向直接后继结点的指针域。


单链表的表示方法:

image.png



单链表存储结构


可以定义单链表结点的结构体如下:


/*线性表的单链表存储结构*/

typedef int ElemType;

typedef struct Node

{

 ElemType data;

 struct Node *next;

} Node;

typedef struct Node *LinkList;

其中,data域用来存放数据元素,next域用来存放指向下一个结点的指针。单链表有带头结点结构和不带头结点结构两种。我们把指向单链表的指针称作头指针。头指针所指的不存放数据元素的第一个结点称作头结点。存放第一个数据元素的结点称作第一个数据元素结点。第一个数据元素结点在带头结点的单链表中是链表中的第二个结点,在不带头结点的单链表中是链表中的第一个结点。一个带头结点的单链表下图所示。

image.png



单链表空单链表空连和非空链和非空链


单链表的操作实现


1、C语言的动态申请内存空间函数


C语言提供了动态申请内存空间函数malloc()和动态释放函数内存空间的函数free()。这些函数包含在头文件malloc.h中。malloc()函数的原型是:


void malloc(unsigned size)`

malloc()函数用于向系统动态申请size个字节的内存单元空间,函数返回值为所申请内存空间的首地址。free()函数的原型是:


void free(void *p)

2、单链表的结点定义


单链表是由一个个结点链接而成的,单链表中每个结点的结构体定义如下:


typedef struct node

{ //结点类型定义

 DataType data; //结点的数据域

 struct node *next;//结点的指针域

}ListNode;

3、单链表的操作实现


在带头结点的单链存储结构下,线性表抽象数据类型定义的各个操作的具体实现方法如下。


单链表的创建

//初始化 
 int InitList(LinkList &L)
{
     //构造一个单链表
     L=new LNode;  //生成头结点,用头指针L指向头结点
     L->next =NULL;  
     return 1;  
 }

单链表的读取


在单链表中读取第i个元素,我们无法一开始知道,必须从头开始找。

typedef int DateType;
/*初始条件:顺序线性表L已经存在,1<=i<=ListLength(L)*/
/*操作结果:用e返回L中第i个数据元素的值*/
int GetDate(LinkList L, int i, DateType *x)
{
  int j;
  LinkList p;
  p = L->next;  /*让指针p指向链表L的第一个节点*/
  j = 1;
  while (p && j<i)  /*p不为空且计数器j还没有等于i时,循环继续*/
  {
    p = p->next;
    ++j;
  }
  if (!p || j > i)
  {
    return 0;   /*第i个节点不存在*/
  }
  *x = p->data;  /*取第i个节点的数据*/
  return 1;
}

单链表的插入


image.png

相关实践学习
使用CloudLens观测ALB下的网站访问情况
通过本实验,您可搭建网站,并使用ALB进行负载均衡,同时使用CloudLens for ALB一键采集ALB日志,进行ALB 7层日志分析、秒级监控指标分析、基于AIOps的自动异常巡检等操作。
负载均衡入门与产品使用指南
负载均衡(Server Load Balancer)是对多台云服务器进行流量分发的负载均衡服务,可以通过流量分发扩展应用系统对外的服务能力,通过消除单点故障提升应用系统的可用性。 本课程主要介绍负载均衡的相关技术以及阿里云负载均衡产品的使用方法。
相关文章
|
3天前
【数据结构OJ题】合并两个有序链表
力扣题目——合并两个有序链表
22 8
【数据结构OJ题】合并两个有序链表
|
5天前
【数据结构OJ题】链表中倒数第k个结点
牛客题目——链表中倒数第k个结点
9 1
【数据结构OJ题】链表中倒数第k个结点
|
2天前
【数据结构OJ题】链表分割
牛客题目——链表分割
3 0
【数据结构OJ题】链表分割
|
3天前
【数据结构OJ题】链表的回文结构
牛客题目——链表的回文结构
5 0
【数据结构OJ题】链表的回文结构
|
19天前
|
算法 C语言
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
|
13天前
|
存储 缓存 算法
堆和栈的区别及应用场景
堆和栈的区别及应用场景
|
19天前
|
存储 测试技术
【数据结构】操作受限的线性表,栈的具体实现
【数据结构】操作受限的线性表,栈的具体实现
27 5
|
19天前
|
算法 C语言
【数据结构与算法 经典例题】使用队列实现栈(图文详解)
【数据结构与算法 经典例题】使用队列实现栈(图文详解)
|
20天前
|
算法
【C/数据结构和算法】:栈和队列
【C/数据结构和算法】:栈和队列
23 1
|
8天前
|
API
用栈翻转字符串
用栈翻转字符串
14 0