关键词:
线性表总结
文章目录
线性表:线性表是由n个数据特性相同的元素组成的有限序列。它是学习其他数据结构的基础。线性表在计算机中可以用顺序存储和链式存储两种存储结构来表示。其中,用顺序存储结构表示的是顺序表,用链式存储结构表示的是链表。(链表又有单链表,双向链表,循环链表之分)
一些前提知识:
1,因为以后可能会对代码进行改变,所以可以提前定义好一些后期可能会变的量。
比如:数组的大小,arr[100]。那么可以在开头#define N 100.
比如:数组的数据类型,int arr[10]。那么可以在开头typedef int SQDataType
这样以后要改的话,就直接在宏定义上进行修改就可以了。
(类型的定义就用typedef,变量的定义就用define)
2,对线性表进行增删改查的时候用的都是接口函数。
3,结构体的定义:
//关于结构体的定义,假设原先结构体的名字是seq,你想改成S
结构体的定义:
Struct seq
;
还有简便的是:
Typedef struct seq
S;
Typedef struct seq S
;
这样都把原来的名字改成了自己想用的名字。
一,顺序表
顺序存储结构,是指用一段地址连续的存储单元依次存储线性表的数据元素。实际上我们是用数组来实现这种结构的。顺序表又分为静态顺序表和动态顺序表。静态顺序表的容量大小在开始时就是已经定义好了的。而动态顺序表的容量大小则是可以改变的。(本文中代码实现的是动态顺序表)
静态顺序表的缺点:容量必须在一开始定义好,如果定义少了不够用,如果定义多了用不完浪费,不能灵活控制。
1,头文件
可以先将头文件写好,这个头文件也就是起一个将条件准备完整的作用,
定义好简便的,可以及时修改的符号变量,(常变量是用const来修饰的)
定义好顺序表的结构体(类型名,数组的类型,大小)
定义好要等会要用的接口。然后在C文件中进行解释说明就行了。
代码实现:
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once//为了避免同一个头文件被包含(include)多次.
#include<assert.h>//因为C文件代码定义中使用了assert断言,引一下。
//常见的提前定义
//#define MAX_SIZE 10 如果是用静态数组实现的顺序表就可以用这个宏的定义,动态数组实现的顺序表就不需要定义最大值了。
#include<stdio.h>
#include<string.h>
#include<malloc.h>
#include<stdlib.h>
typedef int SQDataType;
//定义线性表
typedef struct SeqList
SQDataType* a;//数组
int size; //有效数据的个数
int capacity; //容量
SL;
//增删改查等接口函数
void SeqListInit(SL* ps);//初始化
void SeqListPrint(SL* ps);//打印
void SeqListDestroy(SL* ps);//销毁空间
void SeqListPushFront(SL* ps, SQDataType x);//头插
void SeqListPushBack(SL* ps, SQDataType x);//尾插
void SeqListPopFront(SL* ps);//头删
void SeqListPopBack(SL* ps);//尾删
void SeqLisInsert(SL* ps, int pos, SQDataType x);//任意pos前插入数据
void SeqListErase(SL* ps, int pos);//删除pos位置数据
int SeqListFind(SL* ps,SQDataType x);//查找x数据
void SeqListModify(SL* ps, int pos, SQDataType x);//修改数据
void SeqListCheckCapacity(SL* ps);//检查储存空间并扩充储存空间
2,C文件
c文件中主要是h中的接口的定义。
代码实现:
#include "SeqList.h"//引一下刚才定义好的头文件
void SeqListInit(SL* ps)//初始化
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
//刚开始可以不给空间,也可以给一点点空间,这里选择不给空间了。
void SeqListCheckCapacity(SL* ps)//检查储存空间并扩充储存空间
if (ps->size >= ps->capacity)//如果存的数据大于等于数组的容量,这个时候有两种情况,一种就是原先的capacity就是空,那么无论存不存数据都会使这个条件成立。还有一种情况就是存储的数据真的超过了容量。这两种情况都需要扩容。
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//新建一个容量的数据,判断如果原先的数据是空,那么就直接分配4个数据,如果不是空,那么就把原来的数据变成扩两倍。
SQDataType* tmp = (SQDataType*)realloc(ps->a, newcapacity * sizeof(SQDataType));//使用realloc函数新建一个指定容量大小的空间。
if (tmp == NULL)
printf("realloc fail\\n");
exit(-1);
else
ps->a = tmp;//将建好的空间赋给数组。
ps->capacity = newcapacity;//将新容量赋给旧r
void SeqListPushBack(SL* ps, SQDataType x)//尾插
SeqListCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
//SeqListInsert(ps, ps->size, x);
void SeqListPrint(SL* ps)//打印
for (int i = 0; i < ps->size; i++)
printf("%d ", ps->a[i]);
//数组是这个结构体的,这个数组不是单独的个体,必须配合着ps结构体指针使用。
printf("\\n");
void SeqListPushFront(SL* ps, SQDataType x)//头插
SeqListCheckCapacity(ps);
int end = ps->size - 1;
//循环三要素:
//1,初始条件,2,结束条件,3,迭代过程。
while (end >= 0)
ps->a[end + 1] = ps->a[end];
end--;
ps->a[0] = x;
ps->size++;
//用for也可以来实现:
/* SeqListCheckCapacity(ps);
for (int i = ps->size-1; i >= 0; i--)
ps->a[i+1] = ps->a[i];
ps->a[0] = x;
ps->size++;*/
//前面的可以都不用,直接
//SeqListInsert(ps,0,x);
void SeqListPopBack(SL* ps)//尾删
assert(ps->size > 0);
//这个断点的应用可以帮助找到在那一行出现的问题。
ps->size--;
//前面的可以都不用
//SeqListErase(ps,ps->size-1);
void SeqListPopFront(SL* ps)//头删
assert(ps->size > 0);
int start = 1;
while (start < ps->size)
ps->a[start - 1] = ps->a[start];
start++;
ps->size--;
/*这里也可以用for来实现
assert(ps->size > 0);
int i = 0;
for (i = 1; i <=ps->size; i++)
ps->a[i-1] = ps->a[i];
ps->size--;
*/
//SeqListErase(ps,0);
void SeqListInsert(SL* ps, int pos, SQDataType x)//从中间插入
assert(pos<ps->size);
SeqListCheckCapacity(ps);
int end = ps->size - 1;
while (pos <= end)
ps->a[end +1] = ps->a[end];
end--;
ps->a[pos] = x;
ps->size++;
void SeqListErase(SL* ps,int pos)//任意位置删除
assert(pos < ps->size);
int start = pos + 1;
while (start < ps->size)
ps->a[start - 1] = ps->a[start];
start++;
ps->size--;
void SeqListDestroy(SL* ps)//空间的销毁
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
int SeqListFind(SL* ps, SQDataType x)//查找
for (int i= 0; i < ps->size; i++)
if (ps->a[i] == x)
return i;
return -1;
void SeqListModify(SL* ps, int pos, SQDataType x)//修改
assert(pos < ps->size);
ps->a[pos] = x;
3,测试菜单文件(menu)
写了个相关的小菜单,实现了一点人机交互。
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h";
void menu()
printf("************************************\\n");
printf("1,尾插数据, 2,头插数据\\n");
printf("3,尾删数据, 4,头删数据\\n");
printf("5,在指定位置删数据, 6,在指定位置删除数据\\n");
printf("7,查找数据, 8,打印数据\\n");
printf("9,销毁表格, 0,修改表格\\n");
printf(" -1,退出\\n");
printf("请输入你的操作:\\n");
printf("************************************\\n");
int main()
SL sl;
SeqListInit(&sl);
int option = 0;
int x = 0;
while (option != -1)
menu();
scanf("%d", &option);
switch (option)
case 1:
printf("请输入你要在表头插入的数据,以-1结束\\n");
do
scanf("%d", &x);
if (x != -1)
SeqListPushBack(&sl, x);
while (x != -1);
printf("已插入******\\n");
break;
case 2:
printf("请输入你要在表头插入的数据,以-1结束\\n");
do
scanf("%d", &x);
if (x != -1)
SeqListPushFront(&sl, x);
while (x != -1);
printf("已插入******\\n");
break;
case 3:
printf("您确定要删除表尾的数据吗?1:确定||2:否定\\n");
int num1 = 0;
scanf("%d", &num1);
if (num1 == 1)
SeqListPopBack(&sl);
printf("已经删除******\\n");
break;
else
break;
case 4:
printf("您确定要删除表头的数据吗?1:确定||2:否定\\n");
int num2 = 0;
scanf("%d", &num2);
if (num2 == 1)
SeqListPopFront(&sl);
printf("已经删除******\\n");
break;
else
break;
break;
case 5:
printf("请输入您要插入元素的位置\\n");
int num5 = 0;
scanf("%d", &num5);
printf("您要插入的数据是:\\n");
SQDataType x;
scanf("%d", &x);
SeqListInsert(&sl, num5,x);
printf("已插入******\\n");
break;
case 6:
printf("请输入您要删除元素的位置\\n");
int num6 = 0;
scanf("%d", &num6);
SeqListErase(&sl, num6);
printf("已删除******\\n");
break;
case 7:
printf("请输入你要查找的数据:\\n");
int num3 = 0;
scanf("%d", &num3);
int num4 = SeqListFind(&sl, num3);
if (num4 != -1)
printf("表中确实存在该数据,它的下标是:%d\\n", num4);
break;
else
printf("抱歉,表中不存在该数据\\n");
break;
case 8:
SeqListPrint(&sl);
break;
case 9:
printf("您确定要销毁表格吗?1:确定||2:否定\\n");
int num9 = 0;
scanf("%d", &num9);
if (num9 == 1)
SeqListDestroy(&sl);
printf("已销毁******");
break;
else
break;
case 0:
printf("请输入您要修改的数据的位置:\\n");
int num0 = 0;
scanf("%d", &num0);
printf("您要修改为的数据是:");
SQDataType x1;
scanf("%d", &x1);
SeqListModify(&sl, num0, x1);
printf("修改完毕******");
break;
case -1:
break;
default:
break;
SeqListDestroy(&sl);
return 0;
4,顺序表的优缺点
优点:
1,无须为表示表中元素逻辑关系而增加额外的储存空间。
2,随机存取元素时可以达到O(1),效率高。
缺点:
1,插入和删除数据的时候需要移动大量的元素。
2,必须一开始就确定存储空间的容量。
3,如果空间不够了,增容。增容会付出一定性能的消耗,其次可能存在一定的空间浪费。(动态顺序表)
二,单链表
具体操作有:打印,尾插,头插,尾删,头删,在任意结点之前插入,删除任意结点,malloc一个新结点,在所给链表中查找数据x,并返回它的结点等。
标注的比较详细,可以借助注释食用哦。
分为三个项:(头文件,C文件,测试文件)
SList.h:包的引用和函数的声明
SList.c:各个操作的实现
Test.c:各个操作的实现
1,头文件
代码实现:
#pragma once//防止被重复包含
#include<stdio.h>
#include<stdlib.h>
typedef int SLTDataType;
struct SListNode
SLTDataType data; //链表的数据
struct SListNode* next; //链表的指针
;
typedef struct SListNode SLTNode;//改个名字
//实现一些接口
void SListPrint(SLTNode* phead);//打印
void SListPushBack(SLTNode** pphead,SLTDataType);//尾插
void SListPushFront(SLTNode** pphead, SLTDataType x);//头插
void SListPopBack(SLTNode** pphead);//尾删
void SListPopFront(SLTNode** pphead);//头删
void SListInsert(SLTNode** pphead, int pos, SLTDataType x);//在任意位置插入
void SListErase(SLTNode** pphead, int pos);//在任意位置删除
SLTNode* BuySListNode(SLTDataType x);//malloc一个结点
SLTNode* SListFind(SLTNode*phead, SLTDataType x);//在所给链表中查找数据x,并返回它的结点
2,C文件
代码实现:
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"//引一下头文件
void SListPrint(SLTNode* phead)//打印,这个就是边遍历边打印
SLTNode* cur = phead;//因为要通过指针遍历,所以就创建一个可移动的指针出来。
while (cur != NULL)
printf("%d->", cur->c语言数据结构线性表(代码片段)
线性表线性表功能以及线性表的接口实现线性表功能以及线性表有动态线性表和静态线性表,线性表本质是有限序列。线性表和数组的区别:数组的大小是有限的不可动态增加或减少。数组的访问可以直接下标引用,... 查看详情
c语言严蔚敏数据结构线性表之链表实现(代码片段)
...近在考成都大学皇家计算机科学与技术专业,复习专业课数据结构,正好学习到线性结构中的线性表用链表这种存储结构来实现。 首先,数据结构包括1、数据的操作2、逻辑结构3、存储结构(数据结构三要素。 直接上代... 查看详情
数据结构与算法线性表的重要基本操作与代码实现c语言版(代码片段)
目录线性表的重要基本操作1、初始化初始化线性表L(参数用引用)初始化线性表L(参数用指针)销毁、清空线性表L求线性表L的长度、判断线性表L是否为空2、取值获取线性表L中的某个数据元素的内容3、查找在... 查看详情
c语言数据结构线性表(代码片段)
线性表线性表功能以及线性表的接口实现线性表功能以及线性表有动态线性表和静态线性表,线性表本质是有限序列。线性表和数组的区别:数组的大小是有限的不可动态增加或减少。数组的访问可以直接下标引用,... 查看详情
数据结构第四篇——(一般)线性表(基于c语言)(代码片段)
前言以下描述内容以C语言为主,Java只是作为实现的补充。 一、线性表的定义及性质线性表是由n(n>=O)个数据类型相同的元素构成的有限序列。线性表中元素的个数n(n>=O)定义为表长,n=O时称为空表。线性表... 查看详情
数据结构第四篇——(一般)线性表(基于c语言)(代码片段)
前言以下描述内容以C语言为主,Java只是作为实现的补充。 一、线性表的定义及性质线性表是由n(n>=O)个数据类型相同的元素构成的有限序列。线性表中元素的个数n(n>=O)定义为表长,n=O时称为空表。线性表... 查看详情
c语言实现通讯录管理系统(结构体+枚举+动态内存开辟+文件操作+线性表存放数据)(代码片段)
...c;动态内>存开辟和文件操作等。这里存放数据的结构是线性表。博主码云gitee链接:https://gitee.com/byte-binxin(需要源码自取)先给大家展示一张效果图文章目录通讯录菜单栏实现线性表的创建初始化通讯录ma 查看详情
课本总结:1:线性表(代码片段)
...表的链式存储结构章节导读:最简单且最常用的一种数据结构1.线性表的逻辑结构1.1:定义由一组具有相同属性的数据元素构成在一些复杂的的线性表中& 查看详情
c语言数据结构7--串的实现(代码片段)
串一、什么是串串就是我们常说的字符串,它同样是一个线性表。可能有人认为串就是元素为字符的线性表,但这种说法是不准确的。对于普通的线性表,它们关注的往往是单个元素,每个单独的元素都有独立的... 查看详情
c语言数据结构7--串的实现(代码片段)
串一、什么是串串就是我们常说的字符串,它同样是一个线性表。可能有人认为串就是元素为字符的线性表,但这种说法是不准确的。对于普通的线性表,它们关注的往往是单个元素,每个单独的元素都有独立的... 查看详情
数据结构与算法线性表的链式表示和实现,超详细c语言版(代码片段)
目录链式存储结构与链式存储有关的术语头指针、头结点和首元结点讨论1.如何表示空表?2.在链表中设置头结点有什么好处?3.头结点的数据域内装的是什么?链表(链式存储结构)的特点链表的优缺点优点... 查看详情
常见数据结构与算法整理总结(上)
数据结构是以某种形式将数据组织在一起的集合,它不仅存储数据,还支持访问和处理数据的操作。算法是为求解一个问题需要遵循的、被清楚指定的简单指令的集合。下面是自己整理的常用数据结构与算法相关内容,如有错误... 查看详情
纯c语言实现线性表(代码片段)
1#include<stdio.h>2#include<stdlib.h>3#defineMAXSIZE10045typedefintElemType;67typedefstruct8ElemTypedata[MAXSIZE];9intlength;10SqList;1112SqList*InitList(SqList*L);//初始化13voidDestroyList 查看详情
数据结构c语言版使用线性表的顺序储存结构定义(静态)实现线性表的初
数据结构c语言版使用线性表的顺序储存结构定义(静态)实现线性表的初始化、插入、删除和显示功能直接上源码吧。/*线性表功能的实现*/#include<stdio.h>//定义常量存储空间的初始化分配#defineMAXSIZE20#defineTRUE1#defineERROR-1#defineFAL... 查看详情
深夜爆肝:万字长文3种语言实现huffman树(强烈建议三连)(代码片段)
文章目录一、C语言能干大事1.C语言下Huffman树的计算过程分析2.C语言下Huffman树的编程二、C#语言也不赖1.C#下Huffman类的设计2.C#中界面设计3.建立测试数据并显示Huffman树4.输入任意一组数据,完成构造Huffman树三、JavaScript语言不... 查看详情
深夜爆肝:万字长文3种语言实现huffman树(强烈建议三连)(代码片段)
文章目录一、C语言能干大事1.C语言下Huffman树的计算过程分析2.C语言下Huffman树的编程二、C#语言也不赖1.C#下Huffman类的设计2.C#中界面设计3.建立测试数据并显示Huffman树4.输入任意一组数据,完成构造Huffman树三、JavaScript语言不... 查看详情
线性表(数组链表队列栈)详细总结(代码片段)
线性表是一种十分基础且重要的数据结构,它主要包括以下内容:数组链表队列栈接下来,我将对这四种数据结构做一个详细的总结,其中对链表实现了十几种常见的操作。希望对你有所帮助。1.数组数组(Array)是一种线性表数据... 查看详情
数据结构线性表的动态分配顺序存储结构算法c语言具体实现和算法时间复杂度分析
#include<stdio.h>#include<stdlib.h>//线性表的动态分配顺序存储结构#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量//函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#def 查看详情