1. Toy模板网首页
  2. > Toy博客

线性表的基本操作（初始化、创建、增、删、查）

9月前 作者：柯西从不收敛 分类：Toy博客 阅读(42) 违法举报

这篇具有很好参考价值的文章主要介绍了线性表的基本操作（初始化、创建、增、删、查）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

目录

顺序表

顺序表的定义和初始化

顺序表的基本操作

1.求表长

2.判空操作

3.创建顺序表

4.输出操作

5.插入操作

6.删除操作

7.按位查找操作

8.按值查找操作

单链表

单链表的定义

单链表的初始化

求表长

判空操作

 尾插法建立单链表

头插法建立单链表

输出操作

前插操作

后插操作

插入结点操作

按位查找

删除位序i的节点

指定结点删除

顺序表

线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻

第1个元素存储在线性表的起始位置，第i个元素的存储位置后面紧接着存储的是第i+1个元素，称 i为线性表中的位序

顺序表的定义和初始化

#define _CRT_SECURE_NO_WARNINGS

#include<stdlib.h>
#include<stdio.h>
#include<iostream>

using namespace std;

//顺序表

/*
//静态分配
#define MaxSize 50       //定义顺序表的最大长度

typedef struct {         
	int data[MaxSize];   //顺序表的元素
	int length;          //顺序表的当前长度
}Sqlist;                 //顺序表的类型定义

// 静态顺序表的初始化
void InitList_1(Sqlist& L) {
	L.length = 0;
	printf("顺序表初始化完成\n");
}
*/

//动态分配
#define InitSize 100     //表长度的初始定义

typedef struct {
	int* data;
	int MaxSize, length;
}Sqlist;

//动态顺序表初始化
void Initlist(Sqlist& L) {
	
	//L.data = (int*)malloc(sizeof(int) * InitSize);    //C语言动态分配

	L.data = new int(InitSize);  //C++动态分配
	L.length = 0;
	L.MaxSize = InitSize;
	printf("顺序表初始化完成\n");
}

一维数组静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据就会产生溢出，进而导致程序崩溃。

而在动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数组空间的目的，而不需要为线性表一次性地划分所有空间。 

注意：动态分配并不是链式存储，它同样属于顺序存储结构，物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时动态决定。

顺序表的基本操作

1.求表长

//求表长：返回线性表工的长度，即L中数据元素的个数
int Length(Sqlist L) {
	return L.length;
}

2.判空操作

//判空操作：若L为空表，则返回true,否则返回false
bool Empty(Sqlist L) {
	if (L.length == 0)
		return true;
	else
		return false;
}

3.创建顺序表

//创建顺序表：传值
void CreatList(Sqlist &L) {
	int n;
	printf("请传入顺序表数值个数：");
	scanf("%d", &n);
	printf("请输入顺序表数值：");
	for (int i = 0; i < n; i++)
	{
		cin >> L.data[i];
		L.length++;
	}
}

4.输出操作

//输出操作：打印顺序表
void PrintList(Sqlist L) {
	printf("目前顺序表的数据元素为：");
	for (int i = 0; i < L.length; i++)
		printf("%d ", L.data[i]);
	printf("\n");
}

5.插入操作

//插入操作：顺序表的第i个位置插入新元素e
bool ListInsert(Sqlist& L, int i, int e) {
	if (i<1 || i>L.length + 1)             //判断i的范围是否有效
		return false;
	if (L.length >= L.MaxSize)             //若存储空间已满，不能插入
		return false;
	for (int j = L.length; j >= i; j--) {  //将第i个元素及之后的元素后移
		L.data[j] = L.data[j - 1];
	}
	L.data[i-1] = e;                       //在位置i处放入e
	L.length++;                            //顺序表长 + 1
	return true;

}

6.删除操作

//删除操作：删除顺序表L中第i个位置的元素，用引用变量e返回
bool ListDelete(Sqlist& L, int i, int& e) {
	if (i<1 || i>L.length)                 //判断i的范围是否有效
		return false;
	e = L.data[i - 1];                     //被删除的元素赋值给e
	for (int j = i; j < L.length; j++)     //将第i个元素之后的元素前移
		L.data[i - 1] = L.data[i];
	L.length--;                            //顺序表长 - 1
	return true;
}

7.按位查找操作

//按位查找操作：获取表L中第i个位置的元素的值
int GetElem(Sqlist L, int i) {
	if (i<1 || i>L.length)                 //判断i的范围是否有效
		return 0;
	return L.data[i - 1];
}

8.按值查找操作

//按值查找操作：在表L中查找第一个等于给定关键字值的元素，返回其位序
int LocateElem(Sqlist L, int e) {
	for (int i = 0; i < L.length; i++) {
		if (L.data[i] == e)
			return i + 1;
	}
	return 0;                              //未找到，返回0
}

单链表

线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息外，还需要存放一个指向其后继的指针

通常用头指针来标识一个单链表，如单链表L。为了操作上的方便，在单链表第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点

头结点和头指针的区分：不管带不带头结点，头指针都始终指向链表的第一个结点，而头结点是带头结点的链表中的第一个结点，结点内通常不存储信息

单链表的定义

typedef struct LNode{                   //定义单链表节点类型
	int data;                           //数据域
	struct LNode* next;                 //指针域
}LNode,*LinkList;


//struct LNode*  == LinkList
//强调节点  用LNode
//强调链表  用LinkList
//

单链表的初始化

//单链表初始化(不带头结点)
void InitLink(LinkList& L) {
	L = NULL;
	printf("单链表初始化完成\n");
}

//单链表初始化(带头结点)
void InitLink_1(LinkList& L) {
	L = (LinkList)malloc(sizeof(LNode));
	if (L == NULL)
		printf("单链表初始化失败");
	else {
		L->next = NULL;
		printf("单链表初始化完成");
	}
}

求表长

//求单链表长度（不带头结点）
int Length(LinkList L) {
	int len = 0;
	LNode* p = L;
	while (p) {
		len++;
		p = p->next;
	}
	return len;
}


//求单链表长度（带头结点不包括头结点）
int Length(LinkList L) {
	int len = 0;
	LNode* p = L->next;
	while (p) {
		len++;
		p = p->next;
	}
	return len;
}

判空操作

//判空操作(不带头结点)
bool Empty(LinkList L) {
	if (L == NULL)
		return true;
	else
		return false;
}

//判空操作(带头结点)
bool Empty_1(LinkList L) {
	if (L->next == NULL)
		return true;
	else
		return false;
}

 尾插法建立单链表

//尾插法建立单链表(不带头结点）
LinkList List_TailInsert(LinkList& L) {
	int x;
	printf("尾插法输入数据元素(以-1作为输入结束)\n");
	cin >> x;
	if (x != -1) {
		L = new LNode;                //先创建第一个数据元素结点(作用似头结点)
		L->data = x;                  //下面同带头结点
		LNode* s, * r = L;
		cin >> x;
		while (x != -1) {
			s = new LNode;
			s->data = x;
			s->next = NULL;
 			r->next = s;
			r = s;
			cin >> x;
		}
	}
	
	return L;
}

//尾插法建立单链表(带头结点）
LinkList List_TailInsert_1(LinkList& L) {
	L = new LNode;                         //创建头结点
	LNode* s, * r = L;                     //r为尾指针
	int x;
	printf("尾插法输入数据元素(以-1作为输入结束)\n");
	cin >> x;
	while (x != -1) {
		s = new LNode;                 
		s->data = x;
		s->next = NULL;                    //尾结点指向NULL
		r->next = s;                       //插入新结点
		r = s;                             //更新尾指针
		cin >> x;
	}
	return L;
}

头插法建立单链表

//头插法建立单链表(不带头结点）
LinkList List_HeadInsert(LinkList& L) {
	LNode* s;
	int x;
	printf("头插法输入数据元素(以-1作为输入结束)\n");
	cin >> x;
	while (x != -1) {
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = L;
		L = s;
		cin >> x;
	}
	return L;
}

//头插法建立单链表(带头结点）
LinkList List_HeadInsert_1(LinkList& L) {
	int x;
	LNode* s;
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;
	printf("头插法输入数据元素(以-1作为输入结束)\n");
	cin >> x;
	while (x != -1) {
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = L->next;
		L->next = s;
		cin >> x;
	}
	return L;
}

输出操作

//输出操作：打印单链表(不带头结点)
void PrintLink(LinkList L) {
	LNode* p = L;
	while (p) {
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

//输出操作：打印单链表(带头结点)
void PrintLink_1(LinkList L) {
	LNode* p = L->next;            //不打印头结点
	while (p) {
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

前插操作

//前插操作，在结点p前插入元素e
bool InsertPriorNode(LNode* p, int e) {
	if (!p) 
        return false;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (!s) 
        return false;
	s->next = p->next;                     //将*s结点插入到*p结点之前
	p->next = s;
	s->data = p->data;
	p->data = e;
	return true;
}

后插操作

//后插操作，在结点p之后插入元素e
bool InsertNextNode(LNode* p, int e) {
	if (!p) 
        return false;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (!s) 
        return false;
	s->data = e;                        //将*s结点插入到*p结点之后
	s->next = p->next;               
	p->next = s;
	return true;
}

插入结点操作

//插入结点操作(不带头结点)
bool LinkInsert(LinkList& L, int i, int e) {
	if (i < 1) return false;
	if (i == 1) {
		LNode* s = (LNode*)malloc(sizeof(LNode));
		s->data = e;
		s->next = L;
		L = s;
		return true;
	}
	LNode* p = L;
	int j = 1;
	while (p!= NULL && j < i - 1)         //循环找到第i-1个结点 = GetElem(L, i-1);
	{                                     //LNode* p = GetElem(L, i-1);
		p = p->next;
		j++;
	}
	if (p == NULL)                          //i值不合法
		return false;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;                           //插入结点s到p之后 
	return true;
}

//插入结点操作(带头结点)
bool LinkInsert_1(LinkList& L, int i, int e) {
	if (i < 1) return false;
	LNode* p = L;
	int j = 0;
	while (p != NULL && j < i - 1)         //循环找到第i-1个结点 = GetElem_1(L, i-1);
	{
		p = p->next;
		j++;
	}
	if (p == NULL)                          //i值不合法
		return false;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;                           //插入结点s到p之后 
	return true;
}

按位查找

//按位查找，返回第i个数据结点(不带头结点)
LNode* GetElem(LinkList L, int i) {
	if (i < 1)
		return NULL;
	int j = 1;
	LNode* p = L;
	while (p && j < i) {
		p = p->next;
		j++;
	}
	return p;
}

//按位查找，返回第i个数据结点(带头结点)
LNode* GetElem_1(LinkList L, int i) {
	if (i < 0)                             //i=0表示头结点
		return NULL;
	int j = 0;
	LNode* p = L;
	while (p && j < i) {
		p = p->next;
		j++;
	}
	return p;
}

按值查找文章来源地址https://www.toymoban.com/news/detail-715257.html

//按值查找，找到数据域等于e的结点(不带头结点)
LNode* LocateElem(LinkList L, int e) {
	LNode* p = L;
	while (p) {                            //找到返回p
		if (p->data == e)
			return p;
		p = p->next;
	}
	return NULL;                          //找不到返回NULL
}

//按值查找，找到数据域等于e的结点(带头结点)
LNode* LocateElem_1(LinkList L, int e) {
	LNode* p = L->next;
	while (p) {
		if (p->data == e)
			return p;
		p = p->next;
	}
	return NULL;
}

删除位序i的节点

//删除位序i的节点，用e返回该结点的值(不带头结点)
bool LiskDelete(LinkList& L, int i, int& e) {
	if (L == NULL) {                         //空表
		e = -1;
		return false;
	}
	if (i < 1) 
		return false;
	else if (i > 1) {
		LNode* p = GetElem(L, i - 1);         //按位序查找找到要删除的前一个结点
		if (p == NULL) return false;          //i值不合法 
		if (p->next == NULL) return false;    //第i-1个节点之后没有其他节点 
		LNode* q = p->next;                   
		e = q->data;
		p->next = q->next;                    //删除结点q
		free(q);
	}
	else {
		if (L->next == NULL) {                //i=1 && L只有一个结点
			e = L->data;
			L = NULL;
		}
		else {                                //i=1 && L不只一个结点
			e = L->data;
			L = L->next;
		}
	}
	return true;
}

//删除位序i的节点，用e返回该结点的值(带头结点)
bool LiskDelete_1(LinkList& L, int i, int& e) {
	if (i < 1) 
		return false;
	LNode* p = GetElem(L, i - 1);         //按位序查找找到要删除的前一个结点
	if (p == NULL) return false;          //i值不合法 
	if (p->next == NULL) return false;    //第i-1个节点之后没有其他节点 
	LNode* q = p->next;
	e = q->data;
	p->next = q->next;
	free(q);
	return true;
}

 指定结点删除

//指定结点删除
bool DeleteNode(LNode* p) {
	if (p == NULL) 
		return false;
	LNode* q = p->next;                    //q指向*p的后继节点 
	p->data = p->next->data;               //p的后继节点数据赋值给p 
	p->next = q->next;                     //q节点从链中断开 
	free(q);                               //释放 
	return true;
}

到了这里，关于线性表的基本操作（初始化、创建、增、删、查）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • C语言 队列（循环队列和链队初始化进出队等基本操作）

    C语言 队列（循环队列和链队初始化进出队等基本操作）

    目录 一、队列的定义  二、循环队列 1、 循环队列的储存结构 2、初始化 3、输出队列元素 4、入队 5、出队 6、取队头元素 7、求队列长度 8、源代码 三、链式队列 1、队列的链式存储结构表示 2、初始化 3.输出队列元素 4.入队 5.出队 6.取队头元素 7. 源代码 总结 队列 （Queue）

    2024年02月07日
    浏览(38)
  • 【数据结构】顺序栈和链栈的基本操作（定义，初始化， 入栈，出栈，取栈顶元素，遍历，置空）

    【数据结构】顺序栈和链栈的基本操作（定义，初始化， 入栈，出栈，取栈顶元素，遍历，置空）

    🎊专栏【数据结构】 🍔喜欢的诗句：更喜岷山千里雪 三军过后尽开颜。 🎆音乐分享【勋章】 大一同学小吉，欢迎并且感谢大家指出我的问题🥰   目录 ⭐栈的分类 ✨顺序栈 🎈优点： 🎈缺点： ✨链栈 🎈优点： 🎈缺点： ⭐基本概念 ✨栈： ✨栈顶： ✨栈顶： ✨图片理

    2023年04月22日
    浏览(54)
  • 顺序栈的基本操作（存储结构设计、初始化、判空、判满、入栈、出栈、取栈顶元素、遍历输出栈内元素）

    顺序栈的基本操作（存储结构设计、初始化、判空、判满、入栈、出栈、取栈顶元素、遍历输出栈内元素）

    以上为总的代码，对于栈满时存在一些问题待改进 ———————————————————————————————————————— 以下为代码编写过程，有参考网上大佬的代码   创建栈后报错，在scanf_s处缺少符号  会执行两遍创建栈？   在主函数里边确实有两

    2024年02月05日
    浏览(41)
  • 【C++】【数据结构】循环队列的基本操作（初始化、入队、出队、取队头元素、遍历输出队列、求队列长度）顺序队列的算法实现【附全代码】

    【C++】【数据结构】循环队列的基本操作（初始化、入队、出队、取队头元素、遍历输出队列、求队列长度）顺序队列的算法实现【附全代码】

    使用c++完成数据结构循环队列的基本操作，包括（初始化、入队、出队、取队头元素、遍历输出队列、求队列长度等），可直接编译运行。 队列 又称为 “先进先出” (FIFO)线性表。限定插入操作只能在队尾进行，而删除操作只能在队首进行。 循环队列 ——采用 顺序存储结构

    2023年04月16日
    浏览(51)
  • 线性表的定义和基本操作

    线性表的定义和基本操作

    一、线性表的定义 线性表（Linear List）是具有相同数据类型的n(n=0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为 ai 是线性表中的“第i个”元素线性表中的 位序 a1是表头元素；an是表尾元素。 除第一个元素外，每个元素

    2024年02月06日
    浏览(49)
  • 数据结构 2.1 线性表的定义和基本操作

    数据结构 2.1 线性表的定义和基本操作

    数据结构三要素——逻辑结构、数据的运算、存储结构（物理结构） 线性表是具有 相同数据类型 的n（n=0）个数据元素的 有限序列 ，其中n为表长，当n=0时，线性表是一个空表。 每个数据元素所占空间一样大，有次序。 几个概念 1.ai是线性表中的第i个 i表示元素线性表中的

    2024年02月07日
    浏览(49)
  • 【数据结构】线性表（一）线性表的定义及其基本操作（顺序表插入、删除、查找、修改）

    【数据结构】线性表（一）线性表的定义及其基本操作（顺序表插入、删除、查找、修改）

    目录 一、线性表 1. 线性表的定义 2. 线性表的要素 二、线性表的基本操作 三、线性表的顺序存储结构 1. 定义 2. 顺序表的操作       a. 插入操作 b. 删除操作 c. 查找操作 d. 修改操作 e. 代码实例          一个线性表是由零个或多个 具有相同类型的结点 组成的有序集合。

    2024年02月03日
    浏览(64)
  • 数据结构 线性表的定义和基本操作（以顺序表为例）

    数据结构 线性表的定义和基本操作（以顺序表为例）

    名人说：一花独放不是春，百花齐放花满园。——《增广贤文》 作者：Code_流苏(CSDN) （一个喜欢古诗词和编程的Coder😊） 以下代码个人分享出来，仅供学习交流，且仅在CSDN平台发布，未经授权禁止二次转发。 〇、线性表是什么？ 1、定义 线性表 是具有 相同数据类型 的 n（

    2024年02月12日
    浏览(57)

  • 线性表的基本操作及在顺序存储及链式存储的实现

    一个数据结构的基本操作是指其最核心、最基本的操作。其他较复杂的操作可通过其基本操作来实现。线性表的主要操作如下 注意：1：基本操作的实现取决于采用哪种存储结构，存储结构不同，算法的实现也不同 2：“” 表示c++中的引用调用。若存入的变量是指针变量，且

    2024年02月13日
    浏览(40)

  • 链表的初始化、取值、查找、插入、删除

    链表是一种常见的数据结构，它的节点不像数组一样是连续的，而是通过指针链接在一起的。下面是链表的初始化、取值、查找、插入和删除的示例代码，均使用C语言实现，并带有标头。 链表初始化代码： 以上代码中，定义了一个`ListNode`结构体，其中`val`表示节点的值，

    2024年02月07日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包