线性表（数据结构及其算法，可当作复习资料）

2024-01-09 07:08
文章标签 算法 数据结构 当作 线性表 复习资料

本文主要是介绍线性表（数据结构及其算法，可当作复习资料），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

线性表

线性结构是最常用，最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且有限的。
在这里插入图片描述

线性表的逻辑结构

线性表的定义

由n个数据元素（结点）组成的有限序列，该序列中所有结点具有相同的数据类型。

线性表的逻辑结构

线性表中的数据元素所代表的具体含义随具体应用的不用而不同，在线性表的定义中，只不过是一个抽象的表示符号。

线性表的抽象数据类型定义
ADT List{数据对象；数据关系；基本操作：InitList(&L)ListLength(L)......GetElem(L,i.&e)ListInsert(L,i.&e)......
}ADT List

线性表的顺序储存

线性表的顺序储存

顺序储存：把线性表的结点按逻辑结构依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。
除了用数组来存储线性表的元素外，还应该有表示线性表的长度属性，所以用结构类型来定义顺序表类型。`

#define OK 1
#define ERROR -1
#define MAX_SIZE 100
typedef int Static;
typedef int ElemType;
typedef struct sqlist
{ElemType Elem_array[MAX_SIZE];int length;
}SqList;
顺序表的基本操作
顺序线性表初始化
Static Init_Sqlist(SqList *L)
{L -> Elem_array == (ElemType *)malloc(MAX_SIZE * sizeof(ElemType));if (!L->Elem_array) return ERROR;else { L->length = 0; return OK; }
}
顺序线性表的插入
Static Insert_Sqlist(SqList *L, int i, ElemType e)
{int j;if (i<0 || i>L->length - 1)return ERROR;if (L->length >= MAX_SIZE) {printf("线性表溢出！\n");return ERROR;}for (j = L->length; j >= i - 1; --j)L->Elem_array[j + 1] = L->Elem_array[j];L->Elem_array[i - 1] = e;L->length++;return OK;
}
顺序线性表的删除
ElemType Delete_SqList(SqList *L, int i)
{int k; ElemType x;if (L->length == 0){printf("线性表L为空\n");return ERROR;}else if (i<1 || i>L->length) {printf("要删除的数据元素不存在！\n");return ERROR;}else {x = L->Elem_array[i - 1];for (k = i; k < L->length; k++) {L->Elem_array[k - 1] = L->Elem_array[k];L->length--;return (x);}}
}
顺序线性表的查找定位删除
Static Locate_Delete_Sqlist(SqList *L, ElemType x)
{int i = 0, k;while (i < L->length){if (L->Elem_array[i] != x)i++;else {for (k = i + 1; k < L->length; k++)L->Elem_array[k - 1] = L->Elem_array[k];L->length--;break;}}if (i > L->length) {printf("要删除的数据元素不存在！\n");}return OK;
}

线性表的链式储存

线性表的链式储存结构

链式存储：在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的).

结点的描述
typedef struct Lnode
{ElemType data;struct Lnode *next;
}LNode;
结点的实现

动态分配

p = (LNode*)malloc(sizeof(LNode));

动态释放

free(p)
结点的赋值
LNode *p;
p = (LNode*)malloc(sizeof(LNode));
p->data = 20; p->next = NULL;
单线性链式的基本操作
建立单链表

有两种常用方法：头插法；尾插法
（假设结点的数据类型是整型，以6789作为结束标志）
头插法

LNode *create_LinkList(void)
{int data;LNode *head,*p;head = (LNode*)malloc(sizeof(LNode));head->next = NULL;while (1){scanf("%d", &data);if (data == 6789)break;p= (LNode*)malloc(sizeof(LNode));p->next = data;p->next = head->next;head->next = p;}return (head);
}

尾插法

LNode *create_LinkList(void)
{int data;LNode *head,*p,*q;head = (LNode*)malloc(sizeof(LNode));p->next = NULL;while (1){scanf("%d", &data);if (data == 6789)break;q= (LNode*)malloc(sizeof(LNode));q->data = data;q->next = p->next;p->next = q;p = q;}return (head);
}
单链表的查找

（1）按序号查找

ElemType Get_Elem(LNode *L, int i)
{int j;LNode *p;p = L->next;j = 1;while (p != NULL && j < i) {p = p->next;j++;}if (j != i)return (-6789);elsereturn (p->data);
}

（2）按值查找

LNode *Locate_Node(LNode *L, int key)
{LNode *p = L->next;while (p != NULL && p->data != key)p = p->next;if (p->data == key) return p;else{printf("你所要查找的结点不存在！！\n");return (NULL);}
}
单链表的插入
void Insert_LNode(LNode *L, int i,ElemType e)
{int j = 0; LNode *p, *q;p = L->next;while (p != NULL && j < i - 1) {p = p->next; j++;}if (j != i - 1)printf("i太大或i为0！！\n");else {q = (LNode*)malloc(sizeof(LNode));q->data = e;q->next = p->next;p->next = q;}
}
单链表的删除

（1）按序号删除

void Delete_LinkList(LNode *L, int i)
{int j = 0; LNode *p, *q;p = L; q = L->next;while (p->next != NULL && j < i) {p = q; q = q->next; j++;}if (j != i) printf("i太大或i为0！！\n");else {p->next = q->next;free(q);}
}

（2）按值删除

void Delete_LinkList(LNode *L, int k)
{LNode *p = L, *q = L->next;while (q!=NULL && q->data!=key){p = q; q = q->next;}if (q->data == key) {p->next = q->next;free(q);}elseprintf("所要删除的结点不存在！！\n");
}
单链表的合并
LNode *Merage_LinkList(LNode *La, LNode *Lb)
{LNode *Lc, *pa, *pb, *pc, *ptr;Lc = La; pc = La; pa = La->next;while (pa!=NULL && pb!=NULL){if (pa->data < pb->data) {pc->next = pa; pa = pa; pa = pa->next;}if (pa->data > pb->data) {pc->next = pb; pc = pb; pb = pb->next;}if (pa->data == pb->data) {pc->next = pa; pc = pa; pa = pa->next;ptr = pb; pb = pb->next; free(ptr);}	}if (pa != NULL) pc->next = pa;else pc->next = pb;free(Lb);return (Lc);
}
循坏链表

循坏链表是一种头尾相接的链表。其特点是最后一个结点的指针域指向链表的头结点，整个链表的指针域连接成一个环。

双向链表

双向链表指的是构成链表的每个结点中设立两个指针域，一个指向前驱的指针域prior，一个指向其直接后继的指针域next。

双向链表的结点及其类型定义
typedef struct Doublenode
{ElemType data;struct Doublenode *prior, *next;
}DoubleNode;
双向链表的基本操作

1：双向链表的插入：将值为e的结点插入双向链表中。
（1）：插入时仅仅指出直接前驱结点，钩链时必须注意先后次序“先右后左”。部分语句组如下：

S = (Double *)malloc(sizeof(DulNode));
S->data = e;
S->next = p->next; p->next->prior = S;
p->next = S; S->prior = p;

（2）插入时同时指出直接前驱点p和直接后继结点p,钩链时无须注意先后次序。部分语句组如下：

S = (Double *)malloc(sizeof(DulNode));
S->data = e;
p->next = S; S ->next=q;
S->prior = S; q->prior = S;

2：双向链表的结点删除：部分语句组如下：

p->prior->next = p->next;
p->next->prior = p->prior;
free(p);

一元多项式的表示和相加

一元多项式的表示

（1）顺序存储表示的类型

typedef struct {float coef;/*系数部分*/int expn;/*指数部分*/
}ElemType;

（2）链式存储表示的类型

typedef struct poly{float coef;/*系数部分*/int expn;/*指数部分*/struct poly *next;
}Poly;
一元多项式的相加

（1）顺序存储表示的相加

typedef struct {ElemType a[MAX_SIZE];int length;
}Sqlist;

（2）链式存储表示的相加

Poly *add_poly(poly *La, poly *Lb)
{ploy *Lc, *pc, *pa, *pb, *ptr; float x;Lc = pc = La; pa = La->next;while (pa != NULL && pb != NULL){if (pa->expn < pb->expn) {pc->next = pb; pc = pb;pa=pa->next}if (pa->expn > pb->expn) {pc->next = pb; pc = pb; pb = pb->next}else {x = pa->coef + pb->coef;if (abs(x) <= 1.0e-6) {ptr = pa; pa = pa->next; free(ptr);ptr = pb; pb = pb->next; free(ptr);}else {pc->next = pa; pa->coef = x;pc = pa; pa = pa->next;ptr = pb; pb = pb->next;free(pb);}}}if (pa == NULL)pc->next = pb;else pc->next = pa;return (Lc);
}

这篇关于线性表（数据结构及其算法，可当作复习资料）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/586296。

相关文章

使用雪花算法产生id导致前端精度缺失问题解决方案

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面：本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.
阅读更多...
Springboot实现推荐系统的协同过滤算法

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品（如商品、电影、音乐等）的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法（Collaborativ
阅读更多...
openCV中KNN算法的实现

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库，它提供了各
阅读更多...
springboot+dubbo实现时间轮算法

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n
阅读更多...
C#数据结构之字符串(string)详解

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》：本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘
阅读更多...
SpringBoot实现MD5加盐算法的示例代码

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.
阅读更多...
Java时间轮调度算法的代码实现

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组（时间轮）和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时
阅读更多...
如何通过Golang的container/list实现LRU缓存算法

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣：146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.
阅读更多...
golang字符串匹配算法解读

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt（KMP）算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串（称为
阅读更多...
通俗易懂的Java常见限流算法具体实现

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》：本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2