首页 > 其他分享 >数据结构C语言之线性表

数据结构C语言之线性表

时间：2023-11-16 20:48:40浏览次数：21  
标签：线性表 int next length C语言 SqList 数据结构 LinkNode

发现更多计算机知识，欢迎访问Cr不是铬的个人网站

1.1线性表的定义

线性表是具有相同特性的数据元素的一个有限序列
对应的逻辑结构图形：

file

从线性表的定义中可以看出它的特性：

（1）有穷性：一个线性表中的元素个数是有限的

（2）一致性：一个线性表中所有元素的性质相同，即数据类型相同

（3）序列性：各个元素的相对位置是线性的

1.2线性表的抽象数据类型描述

（如下图所示）

file

那为什么要引进这个数据结构呢？那就不得不谈谈它的作用了。

线性表的作用体现在两个方面：

a. 当一个线性表实现后，程序员加油直接使用它来存放数据，即作为存放数据的容器

b.使用线性表的基本运算来完成更复杂的运算

2.1线性表的顺序存储结构——顺序表

线性表的顺序存储结构简称为顺序表

file

（如图为线性表到顺序表的映射）

需要注意的是顺序表采用数组进行实现，但是不是任意数组可以作为一个顺序表，二者运算是不同的

​ 下图为顺序表的存储示意图

file

2.2顺序表的基本运算实现

（1）结构体SqList定义

//数据元素
typedef int ElemType;
//结构体
typedef struct
{
	ElemType data[MaxSize];
    //数据长度
	int length;
}SqList;

（2）建立顺序表

//建立顺序表
void CreateList(SqList*& L, ElemType a[], int n)
{
	int i = 0, k = 0;
	//记得一定要分配内存空间 
	L = (SqList*)malloc(sizeof(SqList));
	while (i < n)
	{
        //将a[i]存储到L中
		L->data[k] = a[i];
		k++; i++;
	}
	L->length = k;
}

（3）初始化线性表

void InitList(SqList*& L)
{
	L = (SqList*)malloc(sizeof(SqList));
	L->length = 0; //置空线性表的长度为0
}

(4)销毁线性表

void DestroyList(SqList*& L)
{
	free(L);//释放L所指的顺序表空间
}

(5)判断是否为空

bool ListEmpty(SqList* L)
{
	return(L->length == 0);
}

(6)求线性表长度

int ListLength(SqList* L)
{
	return (L->length);
}

（7）求表中某个值

bool GetElem(SqList* L, int i, ElemType& e)
{
	if (i<1 || i > L->length)
		return false;
	e = L->data[i - 1];
	return true;	//成功找到元素返回true
}

（8）按照元素值查找

int LocateElem(SqList* L,ElemType e)
{
	int i = 0;
	while (i < L->length && L->data[i] != e)
		i++;
	if (i >= L->length)
		return 0;
	else
		return i + 1;		//返回逻辑序号
}

（9）输出线性表

void DisplayList(SqList* L)
{
	for (int i = 0; i < L->length; i++)
		printf("%d", L->data[i]);
	printf("\n");
}

(10)完整代码

#include<iostream>
using namespace std;
const int MaxSize = 1005;
typedef int ElemType;
typedef struct
{
	ElemType data[MaxSize];
	int length;
}SqList;

//建立顺序表
void CreateList(SqList*& L, ElemType a[], int n)
{
	int i = 0, k = 0;
	//记得一定要分配内存空间 
	L = (SqList*)malloc(sizeof(SqList));
	while (i < n)
	{
		L->data[k] = a[i];
		k++; i++;
	}
	L->length = k;
}
//初始化线性表
void InitList(SqList*& L)
{
	L = (SqList*)malloc(sizeof(SqList));
	L->length = 0; //置空线性表的长度为0
}
void DestroyList(SqList*& L)
{
	free(L);//释放L所指的顺序表空间
}
bool ListEmpty(SqList* L)
{
	return(L->length == 0);
}

int ListLength(SqList* L)
{
	return (L->length);
}
void DisplayList(SqList* L)
{
	for (int i = 0; i < L->length; i++)
		printf("%d", L->data[i]);
	printf("\n");
}
bool GetElem(SqList* L, int i, ElemType& e)
{
	if (i<1 || i > L->length)
		return false;
	e = L->data[i - 1];
	return true;	//成功找到元素返回true
}
int LocateElem(SqList* L,ElemType e)
{
	int i = 0;
	while (i < L->length && L->data[i] != e)
		i++;
	if (i >= L->length)
		return 0;
	else
		return i + 1;		//返回逻辑序号
}
bool ListInsert(SqList*& L, int i, ElemType e)
{
	int j;
	if (i < 1 || i >L->length + 1 || L->length == MaxSize)
		return false;
	i--;
	for (j = L->length; j > i; j--)
		L->data[j] = L->data[j - 1];
	L->data[i] = e;
	L->length++;
	return true;
}
bool ListDelete(SqList*& L, int i, ElemType& e)
{
	int j;
	//特判是否符合 
	if (i < 1 || i>L->length)
		return false;
	i--;
	for (int j = i; j < L->length - 1; j++)
		L->data[j] = L->data[j + 1];
	L->length--;
	return true;
}
void delnodel(SqList*& L, ElemType x)
{
	int k = 0;
	for (int i = 0; i < L->length; i++)
		if (L->data[i] != x)
		{
			L->data[k] = L->data[i];
			k++;
		}
	L->length = k;
}

}
int main() {
	SqList* L;
	int a[10] = { 7,5,7,7,9,1,6,2,4,8 };
	CreateList(L, a, 10);

	DisplayList(L);
}

2.3线性表的链式存储结构——链表

线性表的链式存储就是链表，每个链表存储点不仅包括数据域，还有指针域。

链表示意图如下：

file

2.4 单链表算法实现

（1）数据结构声明

typedef int ElemType;
typedef struct LinkNode
{
	ElemType data;		//存放元素值
	struct LinkNode* next;	//指向后继结点

}LinkNode;

建立单链表有两种方法：头插法和尾插法

(2)头插法

//建立单链表
void CreatListF(LinkNode*& L, ElemType a[], int n)
{
	LinkNode* s;
	//创建头结点 
	L = (LinkNode*)malloc(sizeof(LinkNode));
	L->next = NULL;	//头结点指针域置NULL
	for (int i = 0; i < n; i++)
	{
		s = (LinkNode*)malloc(sizeof(LinkNode));//重新分配空间
		s->data = a[i];
		s->next = L->next;
		L->next = s;
	}
}

(3)尾插法

void CreatListR(LinkNode*& L, ElemType a[], int n)
{
	LinkNode* s, * r;
	//创建头结点
	L = (LinkNode*)malloc(sizeof(LinkNode));
	r = L;						//r始终指向尾结点，初始时指向头结点
	for (int i = 0; i < n; i++)
	{
		s = (LinkNode*)malloc(sizeof(LinkNode));//重新分配空间
		s->data = a[i];
		r->next = s;
		r = s;
	}
	//尾结点的nextt域置为NULL
	r->next = NULL;			
}

(4)初始化

void InitList(LinkNode*& L)
{
	L = (LinkNode*)malloc(sizeof(LinkNode));
	L->next = NULL;
}

(5)销毁表

void DestroyList(LinkNode*& L)
{
	LinkNode* pre = L, * p = L->next;	//pre指向p的前驱结点
	while (p != NULL)
	{
		free(pre);
		pre = p;
		p = pre->next;
	}
	free(pre);		//循环结束时p为NULL，pre指向尾结点
}

(6)输出表

void DispList(LinkNode* L)
{
	LinkNode* p = L->next;//指向头结点
	while (p!=NULL)
	{
		printf("%d", p->data);
		p = p->next;
	}
	printf("\n");
}

重点！！！

（7）链表的插入

bool ListInsert(LinkNode*& L, int i, ElemType e)
{
	int j = 0;
	LinkNode* p = L, * s;
	if (i <= 0)return false;//首结点的次序是一
	while (j < i - 1 && p != NULL)//找到第i-1个结点
	{
		j++;
		p = p->next;
	}
	if (p == NULL)
		return false;
	else
	{
		s = (LinkNode*)malloc(sizeof(LinkNode));
		//典中典
		s->data = e;
		s->next = p->next;
		p->next = s;
		return true;
	}
}

(8)删除某个元素

bool ListDelete(LinkNode*& L, int i, ElemType& e)
{
	int j = 0;
	LinkNode* p = L, * q;
	if (i <= 0)return false;//头结点是不计入其中的
	while (j < i - 1 && p != NULL)
	{
		j++;
		p = p->next;
	}		
	if (p == NULL)
		return false;
	else {
		q = p->next;
		if (q == NULL)
			return false;
		e = q->data;
		p->next = q->next;
		free(q);
		return true;
	}
}

最后介绍一下双链表

2.5双链表

(1)建立双链表

typedef int ElemType;
// 定义DlinkNode结构体
struct DlinkNode {
    int data;           // 数据域
    DlinkNode* prior;   // 前驱指针
    DlinkNode* next;    // 后继指针
};

同样的，双链表的建立也有头插法和尾插法

（2）头插法

// 定义CreateListF函数
void CreateListF(DlinkNode*& L, ElemType a[], int n)
{
    DlinkNode* s;
    L = (DlinkNode*)malloc(sizeof(DlinkNode)); // 创建头结点
    L->prior = L->next = NULL; // 先后指针域置NULL
    for (int i = 0; i < n; i++) // 循环创建数据结点
    {
        s = (DlinkNode*)malloc(sizeof(DlinkNode)); // 创建数据结点s
        s->data = a[i];
        s->next = L->next; // 将S插到头结点之后
        if (L->next != NULL)
            L->next->prior = s;
        L->next = s;
        s->prior = L;
    }
}

(3)尾插法

void CreateListR(DlinkNode*& L, ElemType a[], int n)
{
    DlinkNode* s,*r;
    L = (DlinkNode*)malloc(sizeof(DlinkNode)); // 创建头结点
    r = L;          //r始终指向尾结点，开始时指向头结点
    for (int i = 0; i < n; i++) // 循环创建数据结点
    {
        s = (DlinkNode*)malloc(sizeof(DlinkNode)); // 创建数据结点s
        s->data = a[i];
        r->next = s; s->prior = r;      //将s结点插入到r结点之后
        r = s;                          //r指向尾结点
    }
    r->next = NULL;
}

2.6总结

线性表是一种基础且重要的数据结构,常见的线性表有三种实现方式:顺序表、单链表和双链表。

​ 本文对这三种线性表的实现方式及特点做一个简要总结:

一、顺序表顺序表是将逻辑顺序上相邻的数据元素存储在物理位置上也相邻的存储单元中,通常使用数组来实现。- 特点:定位直接,通过下标操作即可快速访问任一位置的节点;实现简单。

缺点:插入删除需要移动大量元素,效率低;存储空间固定,扩容不灵活。

二、单链表单链表通过链式存储结构实现,每个节点除存储数据外,还储存下一个节点的地址信息。

-特点:存储灵活,可动态扩展,插入删除简单,效率高。-

缺点:访问任一节点需要从头结点遍历,无法直接定位

三、双链表双链表相比单链表,每个节点增加一个指向前驱节点的指针,实现双向链表。-

特点:可双向遍历链表,操作更灵活。-

缺点:每个节点存储空间略大于单链表。

​ 综上,三种线性表各有特点,使用需根据具体场景需求选择合适的数据结构。顺序表操作简单,链表存储灵活,双链表可以双向访问。开发时需要权衡效率与实现难度,选择最优实现。

本文由博客一文多发平台 OpenWrite 发布！

标签：线性表,int,next,length,C语言,SqList,数据结构,LinkNode
From： https://www.cnblogs.com/xiaocrblog/p/17837211.html

相关文章

  • 实验4 C语言数组应用编程
    1实验任务1task1_1源代码1#include<stdio.h>2#defineN43voidtest1(){4inta[N]={1,9,8,4};5inti;6//输出数组a占用的内存字节数7printf("sizeof(a)=%d\n",sizeof(a));8//输出int类型数组a中每个元素的地址、值9for(i=0;i<N;......
  • c语言 函数参数个数影响
    参考：https://blog.csdn.net/Cheatscat/article/details/79306021https://blog.csdn.net/Dr_Haven/article/details/89383342一个函数的参数的数目过多（尤其是超过8个）显然是一种不可取的编程风格。参数的数目直接影响调用函数的速度，参数越多，调用函数越慢。参数的数目少，程序就显得......
  • c语言学习(文件)练习43
    需求:将10000以二进制的形式存入文件中#define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>intmain(){ inta=10000; FILE*pf=fopen("D:\\桌面\\test.txt","wb"); fwrite(&a,1,1,pf); fclose(pf); pf=NULL; return0;} ......
  • C语言劳动节祝福程序代码
    帮您编写一段祝福程序代码，以下是一个400字以上的C语言劳动节祝福程序代码示例：#include<stdio.h>intmain(){//定义劳动节祝福语char*greetings[]={"在劳动节来临之际，向辛勤工作的您致以最诚挚的祝福！","感谢您为国家、为社会做出的无私贡献，祝......
  • B站C语言第十三课——操作符
    1，/与%的应用intmain(){ inta=5/2;//商2余1 printf("a=%d\n",a); intb=5%2; printf("b=%d\n",b); return0;}2，移位操作符右移操作符1.算术右移右边丢弃，左边补原符号位2.逻辑右移右边丢弃，左边补0左移操作符左边丢弃，右边补0intmain(){ inta=5; a<<......
  • 第二章——线性表
    第二章——线性表 一、线性表简述1、什么是线性表？线性表（linearlist）是n个具有相同特性的数据元素的有限序列，是一种在实际中广泛使用的数据结构。像数组charbuf[5]={1,2,3,4,5},里面出现的元素都是char型的，不会是int、float等其他类型。2、常见的线性表顺序表、链表、......
  • c语言 常量字符串及其初始化
    @TOC前言一、常量字符串：常量字符串：需用双引号包着。例如："hello","你好".常量字符串的本质就是字符数组，该字符串就是数组的名字。访问常量字符串的个元素："hellowyy"[0]"hellowyy"[1]"hellowyy"[2]......访问各元素可以输出，但是不能赋值修改，因为这是常量字符。常量......
  • C语言转义字符
    在我们实际生活中，有一些特殊的字符，它们并没有实际的意义，但是我们需要用到它们，比如换行、制表符等。在C语言中，我们可以使用转义字符来表示这些特殊的字符。转义字符是以反斜杠\开头的字符，比如\n表示换行，\t表示制表符。下面是一些常用的转义字符：转义字符含义\n换行\t......
  • C语言中的关键字
    C语言中有32个关键字，关键字不能用作变量名、函数名、数组名等标识符。关键字的作用是用于定义变量、函数、结构体、联合体等。需要注意，这些关键字都是小写的。这些关键字分别是：auto：自动变量，用于定义自动变量。break：跳出循环，用于跳出循环。case：用于switch语句中，表示某个值......
  • 浙江大学数据结构陈越 第一讲 数据结构和算法
    数据结构数据结构是计算机科学中用来组织和存储数据的方式。它可以理解为一种组织数据的方式，能够有效地管理和操作数据，以及提供对数据进行存储、检索、更新和删除等操作的方法。常见的数据结构包括数组、链表、栈、队列、树和图等，它们各自适用于不同的应用场景，并且有着不同的特点和......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99