首页 > 其他分享 >数据结构-线性表

数据结构-线性表

时间：2024-03-06 18:44:05浏览次数：15  
标签：NULL 线性表 void next assert length SListNode 数据结构

image

线性表

由n（n>=0）个数据特性相同的元素构成的有限序列，称为线性表。他是最基本、最简单、也是最常用的一种数据结构。线性表结构中，数据元素之间通过一对一首尾相接的方式连接起来。

特点：

  1. 存在唯一一个被称为“第一个”的数据元素
  2. 存在唯一一个被成为“最后一个”的数据元素。
  3. 除了第一个元素以外，结构中的每一个元素均只有一个前驱
  4. 除了最后一个元素以外，结构中的每个元素均只有一个后继

1.顺序表

使用一段物理地址连续的存储单元一次存储数据元素的顺序存储结构或顺序映像，被称为顺序表（Sequential List）。

1.1 特点

  • 存在唯一的一个被称作“第一个”和“最后一个”的数据元素。
  • 除第一个和最后一个之外，其余元素有且仅有一个直接先驱和一个直接后继。
  • 数据元素直接的逻辑关系是“一对一”

优点：

  1. 逻辑上相邻的元素，物理位置也相邻。
  2. 可随机访问

缺点：

  1. 插入，删除操作需要移动大量的元素，效率低
  2. 需要预先分配足够大的储存空间，占据空间大

1.2 静态、动态分配

静态： 定义数组的时候，指定了输出长度

区别：定义elem时，静态使用的是数组，而动态使用的是指针，然后通过动态分配存储空间函数malloc或者new来分配一块数组空间，并将起始地址赋给elem，指针elem就会指向这个空间。

// 静态
# define MAXSIZE 100

typedef struct {
    ElemType elem[MAXSIZE];			// ElemType 是为了描述统一而自定的
    int length;
} SqList;
SqList L;

// 动态
typedef struct {
    ElemType *elem;
    int length;
} SqList;

1.3 接口实现

头文件SeqList.h，接下来的内容在SeqList.c中实现。

#pragma once		// 防止被二次引用

#ifndef SEQLIST_SEQLIST_H
#define SEQLIST_SEQLIST_H

#endif //SEQLIST_SEQLIST_H

#pragma once
#include "stdio.h"
#include "assert.h"
#include "stdlib.h"

typedef int DataType;
typedef struct  {
    DataType *elem;
    int length;
    int capacity;
} SeqList;

void Init(SeqList *l);							// 初始化
void Destroy(SeqList *l);						// 销毁
void PrintList(SeqList *l);						// 打印顺序表
void PushBack(SeqList *l, DataType x);			// 尾插
void PopBack(SeqList *l);						// 尾删
void FrontPop(SeqList *l);						// 头删
void FrontPush(SeqList *l, DataType x);			// 头插
int Find(SeqList *l, DataType x);				// 查找指定值是否存在
void Insert(SeqList *l, int pos, DataType x);	// 指定位置插入数据
int ShowLength(SeqList *l);						// 返回顺序表长度
初始化顺序表

初始化其实就是创建一个空的顺序表，断言防止传入空指针。

void InitSeqList(SeqList *l) {
    assert(l != NULL);
    
    l->elem = NULL;
    l->length = 0;
    l->capacity = 0;
    
    // 如果采用静态的话就是这样：
    // l->elem = (DataType*)malloc(MAXSIZE*sizeof(DataType));
    // l->length = 0;
    // l->capacity = MAXSIZE;
}
销毁
void Destroy(SeqList *l) {
    assert(l!=NULL);
    
    free(l->elem);
    l->length = 0;
    l->elem = NULL;
}
扩容

当顺序表的容量满了之后，一次次增加空间太过于麻烦且消耗的代价很大，通常会选择一次性增容 2倍，2倍只是一个折中的数，为了不造成空间的浪费。

void CheckCapacity(SeqList *l) {
    assert(l != NULL);
    
    if (l->length <span style="font-weight: bold;" class="mark"> l->capacity) {
        int newCapacity;
        if (l->capacity </span> 0) {
            newCapacity = l->capacity = 4;		// 原来为0，扩充为4
        } else {
            newCapacity = 2*l->capacity;		// 原来不为0，扩充为2倍
        }
        DataType *x = (DataType*)realloc(l->elem, newCapacity*sizeof(DataType));
        if (x == NULL) {
            perror("realloc");
            exit(-1);
        }
        l->elem = x;		// x不为空，则说明开辟成功
        l->capacity = newCapacity;		// 更新容量
    }
}
打印顺序表

断言之后要先判断是否为空。

void PrintList(SeqList *l){
    assert(l!=NULL);
    if (l->lenth == 0) {
        printf("The seqList is null");
        return;
    }
    
    int i;
    for (i = 0; i < l->length; i++) {
        printf(" %d", l->elem[i]);
    }
    printf("\n");
}
尾插
void PushBack(SeqList *l, DataType x) {
    assert(l != NULL);
    CheckCapacity(l);	// 插入之前先检查顺序表是否容量已经满了
	
    l->elem[l->length] = x;
    l->length++;
}
尾删
void PopBack(SeqList *l) {
    assert(l != NULL);
    if (l->length == 0) {
        printf("the list is empty, delete from back is invalid");
        return;
    }
    
    // 因为不知道这个DataType是什么类型，不能贸然赋值为0
    // l->elem[l->length-1] = 0;
    l->length--;
}
头插
void FrontPush(SeqList *l, DataType x){
    assert(l != NULL);
    CheckCapacity(l);	// 插入之前先检查顺序表是否容量已经满了
    
    int i;
    for (i = l->length-1; i >= 0; i--) {
		l->elem[i+1] = l->elem[i]; 
    }
    l->elem[0] = x;
    l->length++;
}
头删
void FrontPop(SeqList *l) {
     assert(l != NULL);
     assert(l->length > 0);
    
    int i;
    for (i = 1; i < l->length-1; i++) {
        l->elem[i-1] = l->elem[i];
    }
    l->length--
}
查找指定值是否存在
int Find(SeqList *l, DataType x){
    assert(l != NULL);
    assert(l->length > 0);
    
    int i;
    for (i= 0; i < l->length; i++) {
        if (l->elem[i] == x) {
            return i;
        }
    }
    return -1;
}
在指定位置插入数据
void Insert(SeqList *l, int pos, DataType x) {
    assert(l != NULL);
    assert(l->length > 0);
    assert(pos >= 0 && pos <= l->length);		// 传入的pos必须合法
    
    CheckCapacity(l);	// 插入之前先检查顺序表是否容量已经满了
    
    int i;
    for (i = l->length; i > pos; i--) {
        l->elem[i] = l->elem[i-1]
    }
    l->elem[pos] = x; 
    l->length++;
}
删除指定位置的数据
void Delete(SeqList *l, int pos) {
    assert(l != NULL);
    assert(pos >= 0 && pos <= l->length);
    
	int i;
    for (i = pos; i < length-1; i++) {
		l->elem[i-1] = l->elem[i];
    }
    l->length--;
}
返回顺序表长度

在数据结构中有一个约定，如果要访问或修改数据结构中的数据，不要直接去访问。通过函数来访问和修改更加的规范和安全，也方便检查是否出现了越界等等报错情况。

int Find(SeqList *l, DataType x) {
	assert(l != NULL);
    
	return l->length;
}
修改指定下标位置的数据
void Alter(SeqList *l, int pos, DataType x) {
    assert(l != NULL);
    assert(l->length > 0);
    assert(pos >= o && pos < l->length);
    
    l->elem[pos] = x; 
}

因此头插法那里可以这样调用：

void FrontPush(SeqList *l, DataType x) {
	Alter(l, 0, x);
}
判空
bool IsEmpty(SeqList *l) {
    return l->length <span style="font-weight: bold;" class="mark"> 0 ? true : false;
}

2.链表

一种物理存储结构上不连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的，可以实现更加灵活的动态内存管理。

链表的结点由两部分组成：

数据域：存放数据元素信息

指针域：存放后继或前驱的地址

  • 链表可分为：

单链表：只包含一个指针域next，指向后继

双链表：包含两个指针域：next指向后继

2.1 单链表

2.1.1 存储结构

最后一个结点的指针为空（NULL），设置一个头指针H指向第一个结点，通常在第一个结点之前附设一个结点，称为头结点。

首元结点，是指链表中存储的第一个数据元素a1的结点，

头结点，是首元结点之前附设的一个结点，其指针域指向首元结点，可以不储存任何信息

头指针，是指向链表中第一个结点的指针，若有头结点则指向头结点，无则指向首元结点

要访问单链表中任一元素必须从头指针出发，故单链表是“顺序存取”。单链表可由头指针唯一确定==（也就是说，一个单链表可简单理解成是一个头指针，而头指针就是结点指针，故单链表类型是结点指针类型）

2.1.2 接口实现

定义头文件SinglyLinkedList.h

typedef int DataType;

typedef struct SListNode {
    DataType data;
    struct SListNode *next;
} SListNode;

SListNode* ApplyNode(DataType x);
动态申请一个节点
SListNode* ApplyNode(DataType x) {
	SListNode* node = (SListNode*)malloc(sizeof(SListNode));
    if (node == NULL) {
        perror("malloc");
        return;
    }
    node->data = x;
    node->next = NULL;
    
    return node;
}
销毁
// **pHead是一个指向单链表头结点指针的指针
void Destroy(SListNode **pHead) {
    assert(pHead);

    // cur指向当前要释放的节点，即单链表的头结点
    SListNode *cur = *pHead;
    while(cur != NULL) {
        // 指向cur的下一个节点
        SListNode *next = cur->next;
        free(cur);
        cur = next;
    }
    *pHead = NULL;
}
打印
void PrintList(SListNode *phead) {
    while (*phead != NULL) {
        printf("%d->", *phead->data);
        *phead = *phead->next;
    }
    printf("NULL\n");
}
头插
void FrontPush(SListNode **ppHead, DataType x) {
	assert(ppHead);
    assert(*ppHead);
  
    SListNode *newnode = ApplyNode(x);
  
    newnode->next = *ppHead;
    *ppHead = newcode;
}
头删
void FrontPop(SListNode **pphead) {
    assert(*pphead);
    
    SListNode *cur = *pphead;
    *pphead = cur->next;
    free(cur);
}
尾插
void BackPush(SListNode **pphead, DataType x) {
    assert(pphead);

    SListNode *newnode = ApplyNode(x);
    if (*pphead == NULL) {
		*pphead = newnode;
    } else {
        SListNode *tail = *pphead;
        while (tail->next != NULL) {
            tail = tail->next;
        }
        tail->next = newnode;
    }
}
尾删
void BackPop(SListNode **pphead) {
    assert(pphead);
    assert(*pphead);
    
    SListNode *tail = *pphead;
    if ((*pphead) == NULL) {
        free(*phead);
        *phead = NULL;
    } else {
		SListNode *prev = *pphead;
        while (tail->next) {
            prev = tail;
            tail = tail->next;
        }
        prev->next = NULL;
        free(tail);
    }
}
查找相应的数据
SListNode* Find(SListNode *phead, DataType x) {
	SListNode *ptr = phead;
    while (ptr != NULL) {
		if (ptr->data == x) {
            return ptr;
        }
        ptr = ptr->next;
    }
    return NULL;
}
在指定位置之后插入
void InsertAfter(SListNode *position, DataType x) {
	SListNode *newnode = ApplyNode(x);
    
    newnode->next = position->next;
    postion->next = newnode;
}

void Insert(SListNode **pphead, DataType x) {
    SListNode *position = Find(*pphead, 4);
    if (position) {
		InsertAfter(position, x);
    } else {
        printf("Number provided not found!\n");
    }
}
删除指定位置的节点
void Delete(SListNode **pphead, SListNode *position) {
    assert(pphead);
    assert(*pphead);
    assert(position);
    
    if (position == *pphead) {
        // 说明是在首部，直接采用头删法即可
        FrontPop(pphead);
    } else {
        // 否则为中间结点
        SListNode *prev = *pphead;
        while (prev->next != position) {
            prev = prev->next;
        }
        prev->next = position->next;
        free(position);
        position = NULL;	// 置空以避免悬空指针，防止意外的程序崩溃
    }
}
删除指定位置之后的节点
void DeleteAfter(SListNode *position) {
    assert(position);
    assert(position->next);		// 不能为尾结点
    
    SListNode *behind = position->next;
    position->next = behind->next;
    free(behind);
    behind = NULL;
}
求链表的长度
int GetLength(SListNode *pphead) {    
    SListNode *ptr = pphead;
    int counter = 0;
   	while (ptr != NULL) {
		ptr = ptr->next;
        counter++;
    }
    return counter;
}
判空
bool IsEmpty(SListNode *phead) {
	return phead <span style="font-weight: bold;" class="mark"> NULL;
    
    // 第二种写法
    // return phead </span> NULL ? true : false;
}

所有的测试代码

void test2() {
    SListNode *plist = NULL;

    BackPush(&plist, 1);
    BackPush(&plist, 4);
    BackPush(&plist, 5);
    BackPush(&plist, 7);
    BackPop(&plist);
    FrontPop(&plist);
    FrontPush(&plist, 12);
    if (Find(plist, 12) != NULL) {
        printf("Find it!\n");
    } else {
        printf("Number not found!\n");
    }
    Insert(&plist, 99);

    Delete(&plist, Find(plist, 4));
    DeleteAfter(Find(plist, 99));

    PrintList(plist);
    printf("length for singleLinkedList: %d", GetLength(plist));
    Destroy(plist);
}

2.2 双链表

标签：NULL,线性表,void,next,assert,length,SListNode,数据结构
From： https://www.cnblogs.com/bktown/p/18057294/linear-table-ze4igh

相关文章

  • 使用数组实现一个线性表
    线性表的存储结构顺序表：静态存储分配，编译时确定容量（相当于数组，如Javanewint[5])，用一段地址连续的存储单元依此存储线性表的数据元素如何实现一个线性表方法接口对于线性表中一些常用的方法，这些方法是线性表中经常使用的publicinterfaceListMethods<T>{voidclear......
  • 2024 年春节集训 _ 第二课 - 数据结构优化动态规划
    【例题\(1\)】递增子序列\(\color{white}{link}\)考虑\(dp.\)\(dp[i][j]\)表示以元素\(i\)为结尾，长度为\(k\)的方案数。那么显而易见就有一个转移方程：\[dp[i][j]=\sum_{a[k]<a[i],\k<i}dp[k][j-1]\]先抛去第二维度的\(j\)，这是可以做一个关于\(a[i]\)值的大......
  • P5609 [Ynoi2013] 对数据结构的爱
    题面传送门好像搞了个神秘做法。考虑离线扫描线，用一个fhq-Treap维护所有的询问现在长什么样，然后每次操作就整体加\(A_i\)，\(\geqp\)的减去\(p\)，这个可以分裂之后打整体标记，然后用那个值域相交的fhq-Treap合并实现。然后你发现这样就过了。构造一下卡不掉，于是考虑给这个......
  • [数据结构] 树、森林及二叉树的应用
    树、森林树的存储结构双亲表示法双亲表示法的存储结构#defineMAX_TREE_SIZE100typedefstruct{intdata;intparent;}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];intn;}PTree;【注】区别树的顺序存储结构与二叉树的顺序存储结......
  • [数据结构] 树与二叉树
    树的基本概念树的定义树是由\(n(n\geq0)\)个节点组成的有限集。当\(n=0\)时，称为空树。任意一棵非空树应满足以下两点：（1）有且仅有一个特定的称为根的节点；（2）当\(n>1\)时，其余节点可分为\(m(m>0)\)个互不相交的有限集\(T_1,T_2,\dots,T_m\)，其中每个集合本身又是一棵树，称为......
  • 现有Sketch数据结构|持续更新|菜鸟学习
    写在前面比较简略，偏差之类的理论推导建议去读论文，如果有误麻烦指出套话Sketch的基础是概要数据结构（SummaryDataStructure），它是一种可以以较小的内存消耗来表示和估计大规模数据集的某些属性的数据结构。概要数据结构通过对原始数据进行压缩、聚合或采样，以及使用一些统计方法......
  • 现有Sketch数据结构|持续更新|菜鸟学习
    写在前面比较简略，偏差之类的理论推导建议去读论文，如果有误麻烦指出套话Sketch的基础是概要数据结构（SummaryDataStructure），它是一种可以以较小的内存消耗来表示和估计大规模数据集的某些属性的数据结构。概要数据结构通过对原始数据进行压缩、聚合或采样，以及使用一些统计方法......
  • 现有Sketch数据结构|持续更新|菜鸟学习
    现有Sketch数据结构基本原理写在前面比较简略，偏差之类的理论推导建议去读论文，如果有误麻烦指出套话由GPT生成Sketch的基础是概要数据结构（SummaryDataStructure），它是一种可以以较小的内存消耗来表示和估计大规模数据集的某些属性的数据结构。概要数据结构通过对原始数据进行......
  • 向量的线性表示
    前言典例剖析【2024高一专项】在正方形\(ABCD\)中，\(M\)是\(BC\)的中点，若\(\overrightarrow{AC}\)\(=\)\(\vec{m}\)，\(\overrightarrow{AM}\)\(=\)\(\vec{n}\)，则\(\overrightarrow{BD}\)=【\(\qquad\)】$A.4\vec{m}-3\vec{n}$$B.4\vec{m}+3\vec{n}$$C.......
  • 数据结构总纲
    一概述Java集合，也叫作容器，主要是由两大接口派生而来：一个是Collection接口，主要用于存放单一元素；另一个是Map接口，主要用于存放键值对。对于Collection接口，下面又有三个主要的子接口：List、Set和QueueJava集合框架如下图所示： ListArrayList：Object[]数组。Vector：O......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99