-
2021-07-05 20:38:35
(1)带头结点单链表:head->next==NULL;
(2)带头结点循环链表:head->next==head;
(3)不带头结点单链表:head==NULL;
更多相关内容 -
顺序表判断表满的条件
2016-05-27 09:22:26课本上判断表满是if(last==maxsize-1) //last 是最后一个元素的下标,maxsize是表最大可容纳元素的个数 是否可以替换为if(isFull()==true)?//isFull是判断表是否满的共有成员函数,如果满的话返回true -
数据结构之线性表(五)——单链表(2 初始化,判断空表,销毁,清空,求表长)
2021-05-23 01:22:491.单链表(带头结点)的初始化即,构造一个空表,如下图, 算法步骤:1.生成新结点作头结点,用头指针L指向头结点。2.将头指针的指针域置空。算法描述:Status InitList_L(LinkList& L){L = new LNode; //在C语言...1.单链表(带头结点)的初始化
即,构造一个空表,如下图,
算法步骤:
1.生成新结点作头结点,用头指针L指向头结点。
2.将头指针的指针域置空。
算法描述:
Status InitList_L(LinkList& L)
{
L = new LNode; //在C语言里,为 L=(LinkList)malloc(sizeof(LNode));
L->next = NULL;
return OK;
}
2.判断链表是否为空
空表:链表中无元素,但头指针和头结点仍然在。
算法思路:判断头结点的指针域是否为空。
算法描述:
int ListEmpty(LinkList L) //若L为空表,则返回1,否则返回0
{
if (L->next) //非空
return 0;
else
return 1;
}
3.单链表的销毁
销毁单链表:在内存中删除,链表销毁后,其头指针和头结点也不会存在。
算法思路:从头节点开始,依次释放所有结点。
怎么能让一个指针p指向变量a?
做法就是把a的地址赋给指针变量p,即p=&a。这样就定义了一个指向a的指针p。
1.先定义一个指针p,指向当前结点(一开始,p是指向头结点的指针),即,p=L
2.让L指向下一个结点,即,L=L->next,
3.删除当前结点p,即,delete p
4.回到第一步。
5.结束条件为:L=NULL
(循环条件为:L!=NULL或L)
算法描述:
Status DestroyList_L(LinkList& L) //销毁单链表L
{
Lnode* p; //或LinkList p;
while (L)
{
p = L; //指向当前结点(一开始指向的是头节点)
L = L->next; //使L指向下一结点
delete p; //删除当前结点
}
}
4.清空单链表
清空单链表:链表在内存中仍然存在(头指针和头结点仍然在),但链表中无元素。
算法思路:依次释放所有结点,并将头结点指针域设置为空。
怎么能让指针p指向首元结点?p=L; //p指向头结点
p=L->next; //p指向首元结点 1.先定义一个指针p,指向当前结点(一开始,p是指向首元结点的指针),即,p=L->next
2.在释放当前结点p之前,要先确定好下一结点的位置。所以需要再定义一个指针q,让其指向下一个结点,即,q=p->next。然后再释放p。
3.接下来反复执行p=q;q=q->next。
4.结束条件为:p=NULL
(循环条件为:p!=NULL
5.将头结点的指针域设置为空,即L->next=NULL
算法描述:
Status ClearList_L(LinkList& L) //将L设置为空表
{
Lnode *p,*q; //或LinkList p,q;
p = L->next; //p指向首元结点
while (p)
{
q = p->next; //q指向下一个结点
delete p; //删除当前结点
p = q; //将下一结点设置为当前结点
}
L->next = NULL; //头结点的指针域置空
return OK;
}
5.求单链表的长度
算法思路:从首元结点开始,依次计数所有结点。
怎么能让指向当前结点指针p指向下一结点? p=p->next; //p指向下一个结点,p往后移动一个结点
1.先定义一个指针p,指向当前结点(一开始,p是指向首元结点的指针),即,p=L->next。
2.若p不为空,则计1,再让p指向下一结点,即,p=p->next。
3.结束条件为:p=NULL
(循环条件为:p!=NULL
算法描述:
int ListLength_L(LinkList L) //返回L中数据元素的个数
{
Lnode *p; //或LinkList p;
p = L->next; //p指向首元结点
i = 0; //计数
while (p) //遍历单链表,统计结点数
{
i++;
p = p->next; //p指向下一个结点
}
return i;
}
-
Python实现顺序表
2020-01-18 18:41:17Python实现顺序表 关于顺序表的介绍,请参考:https://blog.csdn.net/weixin_43790276/article/details/103848039 Python 中的列表和元组都属于顺序表,下面根据顺序表的特性,自己来实现顺序表。 一、自定义一个...Python实现顺序表
关于顺序表的介绍,请参考:https://blog.csdn.net/weixin_43790276/article/details/103848039
Python 中的列表和元组都属于顺序表,下面根据顺序表的特性,自己来实现顺序表。
一、自定义一个顺序表类
在顺序表中,“表头”部分存储了当前顺序表的容量和已经有多少个数据。初始化一个顺序表时,需要按容量开辟一段内存来作为顺序表的数据存储空间,初始顺序表中的元素个数为0。
定义一个顺序表类 SequenceList ,初始化时可以指定顺序表的长度并开辟对应的存储空间,如默认长度为10,顺序表中的元素个数为0。
# coding=utf-8 class SequenceList(object): def __init__(self, max=10): self.max = max self.data = [None] * self.max self.num = 0
这样,就定义了一个顺序表类,实例化一个类对象就可以创建一个顺序表,只是还没有实现相应的功能。
二、实现顺序表的展示功能
def is_empty(self): return self.num is 0 def is_full(self): return self.num is self.max def show(self): print('<', end='') for i in range(0, self.num): if i != self.num-1: print(self.data[i], end=',') else: print(self.data[i], end='') print('>')
先实现判断顺序表是否为空的方法 is_empty() 和是否已满的方法 is_full(),这两个方法比较简单,如果顺序表中的数据是0个,则为空,如果数据数量已经达到了最大容量,则顺序表已满。
Python中的列表是用中括号,元组是小括号,所以也可以模仿,在展示自定义的顺序表时,使用尖括号,具体见 show() 方法。
if __name__ == '__main__': s = SequenceList() print("is_empty: ", s.is_empty()) print("is_full: ", s.is_full()) s.show()
运行结果:
is_empty: True is_full: False <>
三、实现顺序表中添加数据的功能
def add(self, value): for j in range(self.num, 0, -1): self.data[j] = self.data[j-1] self.data[0] = value self.num += 1 def append(self, value): self.data[self.num] = value self.num += 1 def insert(self, i, value): if not isinstance(i, int): raise TypeError if i < 0: self.add(value) if i > self.num: self.append(value) for j in range(self.num, i, -1): self.data[j] = self.data[j-1] self.data[i] = value self.num += 1 def count(self): return self.num
添加数据到顺序表中,可以从头部添加、从尾部添加或从指定位置添加。
add(value):从头部添加时,为了保证顺序表的顺序关系,原有的数据需要依次往后移动一个位置,所以从顺序表尾部开始遍历,将每个数据的索引值都加1,然后将添加的数据放在顺序表的第一个位置,添加完成后将顺序表的数量加1。
append(value):从尾部添加时,直接将数据添加在顺序表最后一个数据的后面,然后将顺序表的数量加1。
insert(i, value):在指定位置添加数据时,指定位置前面的数据不变,后面的数据都需要往后移动一个位置,所以从顺序表尾部开始遍历,将这些数据的索引值都加1,然后将添加的数据放在指定位置,再将顺序表的数量加1。
如果指定的位置是负数或超过了顺序表最大长度,则需要特殊处理,上面的处理是负数就在头部添加,超过最大长度就在尾部添加。也可以直接抛出 IndexError ,这个按需实现就可以了。
同时实现了查看顺序表长度的方法 count(),返回当前顺序表的数据个数。
s.add(1) s.add(10) s.append(2) s.append(3) s.append(4) s.show() s.insert(1, 20) s.show() print("顺序表长度:", s.count())
运行结果:
<10,1,2,3,4> <10,20,1,2,3,4> 顺序表长度: 6
四、实现顺序表的查询和修改功能
def is_exist(self, value): for j in range(self.num): if self.data[j] == value: return True else: return False def index(self, value): for j in range(self.num): if self.data[j] == value: return j else: return -1 def __getitem__(self, item): if not isinstance(item, int): raise TypeError if 0 <= item < self.num: return self.data[item] else: raise IndexError def __setitem__(self, key, value): if not isinstance(key, int): raise TypeError if 0 <= key < self.num: self.data[key] = value else: raise IndexError
在顺序表中添加数据后,就不再是一个空的表了。会有很多关于顺序表中的数据查询需求。
is_exist(value):判断一个数据是否存在顺序表中,遍历顺序表的每个数据,如果数据值与目标值相等,则说明顺序表中存在目标值。
index(value):返回一个数据在顺序表中的索引位置,与判断是否存在的实现方式一样,这里返回的是索引的值,如果顺序表中没有这个数据,则返回-1。
__getitem__(item):根据索引查询某个索引的数据,给定一个索引值,直接返回顺序表中该位置的数据即可,如果给的索引值超出了索引范围,应该直接抛出 IndexError 。这个方法之所以重写 Python 中的 __getitem__() 魔法方法,是因为 __getitem__() 实现了列表下标的方式来操作数据,支持 s[1] 这种类型的语法。这样写之后,既可以使用 s[1] 来获取顺序表中索引1的数据,也可以使用 s.__getitem__(1) ,结果相同。
__setitem__(key, value):修改指定位置的数据,先根据给定的索引值,找到顺序表中该索引的数据,然后修改。重写 __setitem__() 方法的原因与 __getitem__() 相同。
s.show() print(s.is_exist(200)) print(s.index(20)) print(s.__getitem__(1)) print(s[1]) s[2] = 30 s.__setitem__(3, 40) s.show()
运行结果:
<10,20,1,2,3,4> False 1 20 20 <10,20,30,40,3,4>
五、实现顺序表的删除功能
def remove(self, i): if not isinstance(i, int): raise TypeError if i < 0 or i >= self.num: raise IndexError for j in range(i, self.num): if j == self.num-1: self.data[j] = None else: self.data[j] = self.data[j+1] self.num -= 1 def delete(self, value): for i in range(self.num): if self.data[i] == value: self.remove(i) return def delete_all(self, value): for i in range(self.num): if self.data[i] == value: self.remove(i) self.delete_all(value)
对顺序表执行删除操作之后,依然要保证顺序表中的数据顺序关系。
remove(i):删除指定索引的数据,删除指定索引位置的数据之后,该索引后面的数据都要依次往前移动。所以从指定索引的位置开始,依次将后一个位置的数据赋值给前一个位置,就实现了数据的删除。如果到了最后一个位置,则直接将它赋值为空就可以了。删除之后,顺序表的数量减1。
delete(value):删除指定值的数据,先遍历顺序表,找到对应值的索引,然后调用上面按索引删除的方法,即可删除指定的数据。使用这个方法,如果顺序表中有多个满足条件的数据,只会删除最前面的一个数据。
delete_all(value):删除所有相等的值,如果顺序表中有多个数据与指定值相等,删除第一个数据后,顺序表中数据的数量 self.num 会减1,继续遍历顺序表,会出现删除不完全甚至程序出错的情况。所以在删除第一个数据之后,递归调用自身,这样重新遍历时使用的是减1之后的 self.num ,不会出现漏删或错误。(也可以自己使用其他方式实现)
s.show() s.remove(5) s.show() s.append(4) s.append(4) s.append(4) s.append(4) s.append(4) print("is_full: ", s.is_full()) s.show() print("s的长度:", s.count()) s.delete(4) s.show() s.delete_all(4) s.show()
运行结果:
<10,20,30,40,3,4> <10,20,30,40,3> is_full: True <10,20,30,40,3,4,4,4,4,4> s的长度: 10 <10,20,30,40,3,4,4,4,4> <10,20,30,40,3>
以上就是 Python 中顺序表及一些简单方法的实现。
上面的顺序表容量默认设置是10,如果超过10(可以改大)会报 IndexError ,使用时要注意。因为这个顺序表类中没有实现动态扩容的方法,不像 Python 中的列表有自动扩容的机制,如果需要的话可以继续实现扩容的方法。
-
顺序栈的基本操作实现---入栈、出栈、判断是否为空
2017-11-22 15:15:53顺序栈的基本操作实现---入栈、出栈、判断是否为空 栈本身就比较简单,栈的基本概念推荐文章:http://blog.csdn.net/hguisu/article/details/7674195 实现代码如下: stack.h 栈的头文件: #pragma once #...顺序栈的基本操作实现---入栈、出栈、判断是否为空
栈本身就比较简单,栈的基本概念推荐文章:http://blog.csdn.net/hguisu/article/details/7674195
实现代码如下:
stack.h 栈的头文件:
#pragma once #include <iostream> #define MAX 10 // 注意没有分号 class stack { private: int arr[MAX]; int top; public: stack() //构造函数 { top = -1; } void pop(int val); //入栈 int push();//出栈 bool isFull(); //判断是否栈满 bool isEmpty();//判断是否为空栈 };//有分号
stack.app 栈的子函数文件#include "stack.h" using namespace std; bool stack::isEmpty() { if(top == -1) { cout <<"is empty" << endl; return true; } else return false; } bool stack::isFull() { if(top == MAX) { cout <<"is full " << endl; return true; } else return false; } // 入栈,先判断是否满 void stack::pop(int val) { if(isFull() == 1) cout << "have full" << endl; else { top++; arr[top] = val; } } // 出栈,判断是否为空 int stack::push() { if(isEmpty() == 1) cout <<"have empty" <<endl; else { int data = arr[top]; arr[top] = NULL; top--; return data; } }
测试文件:
#include "stack.h" using namespace std; int main () { stack test; test.isEmpty(); test.pop(1); test.pop(2); test.pop(3); test.isFull(); int data1 = test.push (); cout <<"出栈数字为" << data1 << endl; int data2 = test.push (); cout <<"出栈数字为" << data2 << endl; system ("pause"); return 0; }
-
问题:链表,栈,队列(循环队列)判定满或者空的条件?急求
2019-07-01 20:29:561、为空条件 单链表:头结点指针域next == NULL 静态链表:数组最后一个元素值为0 循环链表:头结点的指针域指向它本身(循环查找时以p->next !=头结点作为遍历结束条件) 栈 顺序存储时:top == -1 链式存储时:... -
【数据结构入门】顺序表(SeqList)详解(初始化、增、删、查、改)
2021-08-18 13:18:42文章目录(1)线性表(2)顺序表1)什么是顺序表2)顺序表的定义2)顺序表的接口实现1、初始化顺序表2、销毁(释放)顺序表3、检查顺序表容量是否满了,好进行增容3、顺序表尾插4、顺序表尾删5、顺序表头插6、顺序... -
顺序表的相关操作
2018-03-11 14:05:02线性表是具有n个相同数据类型元素的有限序列,除了第一个元素无直接前驱,最后一个元素无直接后继...它是指,顺序表中的所有元素存放在一块地址连续的空间中,相邻元素间的物理地址连续,以达到其在逻辑结构上相邻的... -
Java 实现顺序表的基本操作
2019-06-08 17:12:38顺序表 静态顺序表:使用定长数组存储。 动态顺序表:使用动态开辟的数组存储。 接口 package com.github.sqlist; public interface ISequence { // 在 pos 位置插入 val boolean add(int pos, Object data); /... -
栈和队列的判断条件(顺序栈,链栈,环形队列,链队)
2020-08-18 16:16:21顺序栈 栈空:top==-1 栈满:top==maxsize-1 链栈 栈空:s->next==NULL 栈满:不存在 环形队列 队空:p->front==p->rear 队满:(p->rear+1)%maxsize==p->front 链队 队空:q->rear==NULL 队满:不... -
俩个有序顺序表的合并(好好学习)
2022-03-14 16:12:30顺序表的合并,你会感兴趣的。 -
对于一个头指针为head的带头结点的单链表,判定该表为空表的条件是()。 (4.0分)_学小易找答案
2021-03-13 20:32:27【判断题】链表中的头结点仅起到标识的作用。 (2.0分)【单选题】某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用()存储方式最节省运算时间。 (4.0分)【简答题】善于分析的【简答题... -
数据结构顺序表基本操作(C/C++实现)
2019-10-22 23:23:01判断顺序表L是否为空 输出顺序表L的第3个元素 输出元素a的位置 在第4个元素位置上插入f元素 输出顺序表L 删除顺序表L的第3个元素 输出顺序表L 释放顺序表L GitHub地址(包含.cpp文件和可执行程序exe) 我的数据结构... -
数据结构--顺序表的c语言实现(超详细注释/实验报告)
2021-09-17 17:25:37线性表是一种最基本、最常用的数据结构,它有两种存储结构——顺序表和链表。顺序表是由地址连续的的向量实现的,便于实现随机访问。顺序表进行插入和删除运算时,平均需要移动表中大约一半的数据元素,容量难以扩充... -
MySql当查询条件为空时不作为条件查询
2018-08-16 11:55:38这种情况下,需要去判断每个条件是不是为空,后来发现一个很有用的sql语句,能非常简单的解决这个问题。 我们先上表: CREATE TABLE `clazz` ( `id` INT(11) NOT NULL AUTO_INCREMENT CO... -
数据结构——顺序表的定义和实现
2021-01-24 22:46:49顺序表 顺序表是基于数组的顺序存储的一种线性结构,并且每一个表项的逻辑结构和物理存放顺序一致,其中包含了对表项(数据元素)进行的相关操作,例如增删改查等等操作。 那么顺序表有什么用呢?对于一般的数组而言... -
19、【顺序表】删除顺序表内所有指定元素(C++版)
2021-01-04 18:40:29对长度为n的顺序表L,编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法,该算法删除线性表中所有值为x的数据元素。 // 顺序表结构如下 typedef struct SeqList{ ElemType* data; int length,MaxSize; } SeqList;... -
顺序表插入数据
2019-07-21 13:28:331、创建顺序表 2、初始化顺序表 3、构建逻辑 存储结构: typedef struct{ ElemType *elem; int Length; int ListSize; }SqList; 函数:ListInsertSq(SqList &L,int Location,ElemType Elem) ... -
java数据结构与算法之顺序表与链表深入分析
2016-11-05 16:24:30开篇直接奔主题,无论是顺序表还是链表,它们都是线性表的一种,用比较官方的话来讲,线性表是其组成元素间具有线性关系的一种线性结构,而我们恰好可以采用顺序存储和链式存储结构来表示线性表。接下来将从以下几点... -
【数据结构基础笔记】第二章线性表之顺序表
2018-08-03 18:47:57第二章一共四小节,第二节讲的是顺序表的相关概念及实现,顺序表是线性表的顺序存储结构,是后续顺序存储的基础。在本节代码中,我会加上我大量的个人代码理解,包括我思考的一些问题和我自己得到的答案(问题加粗并... -
对顺序表中元素从小到大排序的算法
2017-12-29 22:37:21)编写一个对顺序表中元素从小到大排序的算法,函数接口如下: //初始条件:线性表L已经存在,且元素个数大于1 //操作结果:将L中的元素从小到大排序 Status ListSort_Sq(SqList &L); 然后,在main函数中调用... -
顺序表的建立、插入、删除、查找
2021-04-03 22:05:43顺序表L的长度length是表中所含元素的个数,初始值为0。Listsize是当前已分配的存储空间的容量,是以元素大小为单位的。 建立一个头文件SeqList.h,避免在后面的.c程序中代码冗余。.h文件一般包括程序中必须用到的... -
顺序表和链表实现图书管理系统
2019-10-10 08:25:39顺序表和链表实现图书管理系统 本次记录的是数据结构课程的实验,实验内容如下: 图书信息表包括如下常用的基本操作:图书信息表的创建和输出、排序(分别按图书名称、按图书价格排序)、修改、按名查找、最贵图书的... -
顺序表查找——顺序查找、有序表查找(多种方法)及次优查找树
2020-06-26 00:03:13查找8.2 顺序表8.2.1 顺序表的查找基本思想顺序存储结构下的顺序查找算法平均查找长度8.2.2 有序表的折半查找折半查找的算法思想折半查找算法一般代码二叉搜索树 8.2 顺序表 采用顺序存储结构的数据表称为顺序表。... -
【数据结构】线性表(顺序表、单链表、双链表、循环链表)的JAVA代码实现
2018-03-14 19:53:32它的实现方式有很多,下面用顺序表、单链表、双链表、循环链表来对它进行实现。 线性表的抽象数据类型 数据元素:可以为任意类型,只要同属于一种数据类型即可; 数据关系:数据元素之间呈线性关系; 数据... -
顺序表(笔记)
2021-04-20 07:53:05顺序表可以随机访问,即通过表头和元素编号进行访问。 #include <stdio.h> #include <stdlib.h> //定义顺序表的结构体 typedef struct vector{ int size; //顺序表总容量 int length //顺序表当前个... -
顺序表的实现以及力扣练习题
2021-10-28 21:52:13顺序表 顺序表的实现 顺序表的初始化 顺序表的销毁 顺序表的打印 顺序表检查是否要扩容 顺序表的尾插 顺序表的头插 顺序表的尾删 顺序表的头删 顺序表的查找 顺序表在pos位置插入x 顺序表删除pos位置的... -
数据结构——顺序表的逆置
2021-03-20 22:58:31题目:请写一个算法将顺序存储结构的线性表(a1...an)逆置为(an...a1),要求使用最少的附加空间。 解析:可以理解为一个线性表内的交换问题。当n为奇数时,将第一个元素与最后一个元素进行交换,第二个元素与倒数... -
顺序循环队列队满队空的两种判别方式
2020-07-29 19:34:31博主很喜欢的一句话花开堪折直须折,莫待无花空折枝:博主的理解是头一次为人,就应该做自己想做的事,做自己不后悔的事,做自己以后不会留有遗憾的事,做自己觉得有意义的事,不浪费这大好的青春年华。博主写博客... -
数据结构c语言版严蔚敏 顺序表
2019-02-21 21:13:40说来惭愧由于贪玩,数据结构挂科了,现在重新学一遍数据结构,...listsize代表这个顺序表的最大容量 可以随时扩容 length代表表中元素个数 应小于listsize 1.初始化 Status list_init(SqList &L) { L.elem...