专业网站制作流程,商标交易网,郑州软件外包公司,石家庄网站编辑王道中这章主讲了线性表的定义、基本操作、顺序表示、链式表示。下方内容主分了文字部分和代码部分#xff0c;便于记忆和整理。 在901中这章的要求集中在链表的基础操作中#xff0c;应用题大概会出问答题。 【当前每一小节的应用题待做#xff0c;先把选择题过完#xff…王道中这章主讲了线性表的定义、基本操作、顺序表示、链式表示。下方内容主分了文字部分和代码部分便于记忆和整理。 在901中这章的要求集中在链表的基础操作中应用题大概会出问答题。 【当前每一小节的应用题待做先把选择题过完预计1个月。每日15-20页】
7.3115-30页线性表、顺序表练习题8.131-45页单链表、双链表、循环链表、静态链表8.246-62页链表部分35道选择题review8.3 8.4预63-92页第三章
第二章 线性表
文字内容
问
线性表的特点元素个数 关系 形式 数据类型 表达含义线性表、顺序表、链表不同之处顺序表的特点 相对于链表而言一句话概括顺序表 静态分配优缺点顺序表动态分配的过程 和 链式存储的区别顺序表的优缺点链式存储与顺序表的不同 讨论存取删除插入操作单链表在存储空间上的优缺点单链表的存储结构是什么具体说明一下单链表如何查找特定结点头结点和头指针的关系引入头结点有什么优点两个一致双链表解决了单链表什么问题如何解决的循环单链表与单链表的区别【其插入 删除 算法与单链表一样吗】为什么会说有时对循环单链表仅设尾指针可以使得操作效率更高循环双链表与循环单链表的定义不同之处为空表时是怎样的
答
元素个数有限元素之间具有先后次序即顺序性均为数据元素每个元素都是单个元素数据类型都相同每个元素都占有相同的存储空间具有抽象性元素可以表达很多内容但主要考虑的是元素之间的逻辑关系。线性表是一种逻辑结构表示元素之间一对一的相邻关系。而顺序表和链表是存储结构。顺序表是顺序存储形式而链表是链式存储一般前者在代码中使用数组实现后者使用指针实现。逻辑顺序与其存储的物理顺序相同。对数组静态分配时因为数组的大小和空间事先已经固定所以一旦空间占满再加入新数据就会产生溢出进而导致程序崩溃。动态分配时存储数组的空间是在程序执行过程中通过动态存储分配语句分配的从而达到数组存储空间的目的而不需要为线性表一次性地划分所有的空间。但动态分配仍属于顺序存储结构物理结构没有改变依然是随机存取的方式只是分配的空间大小可以在运行时动态分配。优可进行随机访问通过首地址和元素序号可以在O(1)时间内找到指定元素存储密度高每个结点只存储数据元素缺元素的插入和删除需要移动大量的元素插入平均移动n/2删除平均移动(n-1)/2顺序存储分配需要一段连续的存储空间不够灵活。顺序表的存储位置可以用一个简单直观的公式表示它可以随机存取表中任意元素但插入和删除操作需要移动大量元素链式存储线性表时 不需要使用地址连续的存储单元即不要求逻辑顺序与物理位置顺序一致它通过“链”建立元素之间的逻辑关系因此插入和删除操作不需要移动元素只需要修改指针但也会失去顺序表可随机存取的优点。优点解决顺序表需要大量连续存储单元的缺点缺点附加的指针域也存在浪费存储空间的缺点。单链表的存储结构是非随机存取的是由于单链表的元素离散地分布在存储空间中所以不能直接找到表中的某个特定的结点。从表头开始遍历依次查找。头指针是一定存在的只不过区别在于单链表是否带头结点从而导致头指针指向结点不同 不管带不带头结点头指针都始终指向链表的第一个节点而头结点是带头结点的链表的第一个结点结点内通常不存储信息。①由于第一个数据结点的位置被存放在头结点的指针域中因此在链表的第一个位置上的操作和在表的其他位置上的操作一致无需进行特殊处理。②无论链表是否为空其头指针都是指向头结点的非空指针空表中的头结点的指针域为NULL因此空表和非空表的处理也得到了一致。单链表只有一个指向后继的指针使得单链表只能从前往后依次遍历如果要访问前驱只能从头开始访问前驱的时间复杂度为O(n)为了克服这个缺点引入了双链表。双链表中有两个指针prior 和 next分别指向了直接前驱和直接后继。单链表的尾部指向NULL循环单链表的尾部指向头结点从而整个链表形成一个环。在单链表中只能从头结点开始往后顺序遍历整个list但是循环单链表可以从表中的任意一个结点开始遍历整个list。【几乎一样这里你明白表尾不同就行他操作是一样的就算是表尾它的前驱结点指向它的next不就还是尾部结点指向头结点所以过程中无需判断是否为表尾。】若是设的头结点对在表尾插入元素需要O(n)的时间复杂度而若是设的是尾指针rr-next即为头指针对在表头或表尾插入元素都只需要O(1)的时间复杂度。头结点的prior指针指向尾结点尾结点的next指向头结点。当循环双链表为空表时head-prior head; head-next head;
挖
顺序表是用一组【】存储线性表中的【】从而使得逻辑上相邻的两个元素在【】也相邻。线性表的链式存储又称【】它是指通过一组【】来存储线性表中的【】。为了建立数据元素之间的【】关系对每个链表结点除存放元素自身的信息之外还需要存放【】。通常用【】来标识一个单链表指出链表的起始地址其为【】时是一个空表。头结点是【】其数据域【】。单链表带头结点时头指针head指向【】不带头结点时head指向【】。代码中设p为指向链表结点的结构体指针则*p表示【】访问数据域代码为【】其中.的左侧为【】-的左侧为【】得到下一个结点的存储数据【】。静态链表是用【】来描述线性表的链式存储结构结点也有指针域next和数据域data与之前的链表不同的是这里的指针是【】又称游标。和顺序表一样静态链表也要预先【】。顺序表和链表的比较
存取方式 逻辑结构和物理结构 插入、查找、删除操作 空间分配
空
地址连续的存储单元、数据元素、物理位置上单链表、任意的存储单元、数据元素、线性、一个指向其后继的指针头指针head or L、NULL单链表在第一个数据结点前附加的一个结点、可以不设置任何信息也可以记录表长等信息、头结点、第一个数据结点。这个结点本身、p-data or (*p).data、普通结构体变量、结构体指针、p-next-data or (*(*p).next).data数组、结点在数组中的相对地址数组下标、分配一块连续的内存空间。
存取方式顺序表顺序存取也可以随机存取链表只能从表头开始依次顺序存取。逻辑结构和物理结构顺序表中逻辑上相邻的两个元素对应的物理结构也相邻链表就不一定了其对应的逻辑关系是通过指针链表来表示的。插入、查找、删除操作按值查找顺序表无序O(n)有序时O(logn)【二分法】按位置查找顺序表支持随机访问O(1)链表的平均时间复杂度为O(n)。删除插入顺序表移动半个表长的元素链表只需要修改相关节点的指针域即可。空间分配顺序存储在静态分配的情况下装满就不能扩充若再加入新元素就会内存溢出因此需要实现分配足够大的存储空间这个很难把控过大造成闲置过小造成溢出顺序表的动态存储虽然存储空间可以扩充但需要移动大量元素造成操作效率降低而且若内存中没有更大块的连续存储空间会导致分配失败链表存储的节点空间只在需要时申请分配操作灵活、高效。由于链表的每个结点都需要指针域存储密度不够大。
选择仅错题缩放150%
2.2.3 试题精选 【错误答案】A or C 【思路】随机存取可以直接通过地址或下标在常数时间内访问数据的存取方式。而且线性表 顺序存储结构使用数组实现所以是 可以随机存取的存储结构 【补充】 索引存取通过索引类似目录或指针来查找和访问数据的存取方式。e.g.数据库的索引、B树、B树、哈希表。 链式结构应该是顺序存取的存储结构
【错误答案】A 【思路】随机存取和下标有关的选项 肯定是和n无关 所以BD先排除 A 需要遍历整个顺序表 因为不能根据值索引 C正确 故C 【错误答案】A 【思路】 Ⅰ SeqList.data[i] SeqList.data[i-1] Ⅱ len MaxSize 时 data[len] newnode Ⅲ 需要移动后面len-1个结点往前移位 和n有关 Ⅳ 移动len-i个节点 和n有关 所以ⅠⅡ时间复杂度O(1) 选C 【错误答案】A 【思路】顺序表的效率高于链表随机存取 Ⅰ 符合随机存取的能力链表还需要顺序查找到指向i结点的指针才能输出它的数据域 Ⅱ 交换值虽然交换动作二者比较不出但是链表还需要将指针移动到位置3所以还是顺序表效率高 Ⅲ 二者都需要遍历差不太多。所以C
2.3.7 尸体精选 试题精选
做题的时候确实已经可以直接把我脑子入土了错了好多没事巩固的知识也多 【错误答案】C 【思路】 结点内的存储单元地址≠结点的存储空间 结点内的存储单元地址是指在每个节点内部数据域和指针域的存储单元地址肯定是连续的。所以A 结点的存储空间是不连续的。链式存储链表 逻辑顺序和物理位置不一致 【错误答案】B 【思路】 Ⅰ顺序存储结构直接理解为数组也可以链式结构吧 静态链表 × Ⅱ 删除表尾元素需要知道这个尾结点的前驱结点但在单链表中需要遍历所以还是和表长有关的 × Ⅲ 带头节点的单循环链表为空表时head指向自己 Ⅳ 对我当时好像想成了数组可以折半查找所以O(logn) Ⅴ 队列 先进先出原则 进头插法 出应该是带尾指针的循环双链表吧不然尾结点的前驱找不到哇 × 判断完了才发现如果Ⅱ不对那只能选BCD Ⅴ肯定对 所以D 【补充知识】循环单链表表示队列对Ⅴ的判别错误是对单链表实现队列 分析有误 【错误答案】B 【思路】有序单链表首先将一维数组有序的话是O(nlogn)各种排序一般好像是快速排序然后分配空间建立链表O(n)所以D 【错误答案】C or B 选了B 我感觉C太笼统了:) 【思路】记住就好不增加头结点也会标识出结点中首结点的位置所以C。单链表中增加一个头结点的目的是方便运算的实现。 【错误答案】B 【思路】读题啊大哥 线性表所以分为链表和顺序表 如果顺序表 50 链表 0 所以D 【错误答案】D 无语死了 【思路】有序单链表插入一个新结点最低 头部 O(1) 最高 尾部 O(n) 所以B 【错误答案】D 【思路】循环单链表 欸 为空表 head-next head 所以头结点的指针域与L的值相等 【错误原因】L *L分别不清楚 【错误答案】C 【思路】末尾插入结点能快速指向尾部就节省时间尾指针或者循环头指针 删除结点能够随时遍历整个链表 要求最节省时间方便找前驱所以A 【错误答案】D 【思路】头尾相接的时间复杂度为O(1) 循环单链表 前一个链表的尾部改为指向后一个链表的头部 后一个链表的尾部改为指向前一个链表的头部。所以都指向尾部比较合适因为都要改变他们的尾部结点指向所以B。 【错误答案】B 【思路】看下图思路 选D 【错误答案】B 【思路】看下图所以选C
代码内容
注意一般可以忽略边界条件判断变量定义内存分配等细节主要体现算法思想。所以这里更要多过几遍以防考场上对于细节过于细究或者模糊浪费时间。纸质考试≠上机考
顺序表
静态分配一维数组的顺序表存储结构描述
#define MaxSize 50
typedef struct {ElemType data[MaxSize]; // 顺序表的元素int length; //顺序表当前长度
}SqList;//顺序表类型定义动态分配一维数组的顺序表存储结构描述
#define InitSize 100
typedef strcut{ElemType *data;//动态分配数组的指针int MaxSize,length;//数组的最大容量和当前个数
}SeqList;
//C 动态分配语句
L.data new ElemType(InirSize);
//C 动态分配语句
L.data (ElemType*)malloc(sizeof(ElemType)*InitSize);顺序表的初始化InitList(SqList L) or SeqList L
静态只需要设置length 动态对maxsize length data都需要进行设置或分配。
//声明一个顺序表SqList 静态分配
void InitList (SqList L){L.length 0;
}
//动态分配
void InitList(SeqList L){L.data (ElemType*)malloc(sizeof(ElemType)*MaxSize);L.length 0;L.MaxSize InitSize;
}顺序表的插入操作InsertList()
已知顺序表L 新元素e 插入为序i ---- 数组下标为i-1【如果搞不清则判断插入位置是否合法和for循环细节上就会搞错】
bool ListInsert(SqList L, int i, ElemType e) {// 判断i是否有效i的取值范围应该在1到L.length1之间if (i 1 || i L.length 1) { // 插入位置不合法return false;}// 当前存储空间已满if (L.length MaxSize) {return false;}// 从最后一个元素开始依次向后移动直到第i个位置for (int j L.length; j i; --j) {L.data[j] L.data[j - 1];}// 在第i个位置插入新元素L.data[i - 1] e;// 长度加1L.length;return true;
}顺序表的删除操作ListDelete()
已知顺序表 删除位置 删除元素的返回
bool ListDelete(SqList L , int i , ElemType e){//判断iif(i 0 || i L.length) return false;//不用判断当前长度e L.data[i-1];for(int j i-1 ; j L.length-1; j){L.data[j] L.data[j1];//j1不能越界 越length}L.length--;return true;
}顺序表的按值查找 LocateElem()
已知顺序表 查找元素 返回位序
int LocateElem(SqList L , ElmeType e){int i;for(i 0 ; i L.length ; i){if(L.data[i] e) return i1;}return 0;
}单链表 默认带头结点
存储结构描述LNode LinkList
typedef struct LNode{ElemType data;struct LNode *next;
}LNode , *LinkList;带头结点の单链表的初始化InitList()
bool InitList(LinkList head){head (LNode*)malloc(sizeof(LNode));head-next NULL;return true;
}不带头结点の单链表的初始化InitList()
bool InitList(LinkList head){head NULL;return true;
}单链表求表长Length()
//带头结点
int Length(LinkList L){int len 0;LNode *p L-next;while(p){pp-next;len ;}return len;
}orint Length(LinkList L){int len 0;LNode *p L;while(p-next){p p-next;len;}return len;
}单链表按序号查找结点GetElem()
已知L、第i个结点 如果i超过了表长返回NULL【书中写的小于表长那不就可以找到的吗】
LNode *GetElem(LinkList L , int i){LNode *p L;int j 0;while(p ! NULL j i){//我写成了p-next ji 错的家人们pp-next;j;}return p;
}单链表按值查找表结点LocateElem()
已知给定值e 当没有这个值返回NULL
LNode *LocateElem(LinkList head , ElemType e){LNode *p head-next;while( p ! NULL p-data ! e){p p-next;}return p;
}单链表插入结点操作ListInsert()【后插】
已知L、第i个结点处插入、data 为 e
bool ListInsert(LinkList head , int i , ElemType e){LNode *newNode (LNode*)malloc(sizeof(LNode));newNode-data e;//移动到i-1的位置LNode *p head;int j 0;while(p ! NULL ji-1){p p-next;}//!!!!!!判定i是否合法if(p NULL) return false;//插入结点newNode-next p-next; //颠倒的话需要多增加一个指针变量存储被覆盖的p-next;p-next newNode;return true;
}前插操作是p在位置i处的这个结点之前插入newNode.书上的思路结点上仍然是后插操作结束后将newNode与p内的数据域进行交换。
单链表删除结点操作ListDelete()
已知L、位置i、要返还的ElemType e
bool ListDelete(LinkList head , int i, ElemType e){LNode *p head;//移动至i-1处int j 0;while(p ! NULL ji-1){p p-next;j;}//判定i是否合法 比【插入】多一个条件if(p NULL || p-next NULL)return false;//删除操作 因为要释放被删除结点 所以新开一个指针LNode *q p-next;e q-data;p-next q-next;free(q);return true;
}扩展不知道他在干啥遇到了再说吧【坑 located in 电子版48页】
头插法建立单链表
LinkList List_HeadInsert(LinkList head){LNode *newNode ; int x;head (LNode*)malloc(sizeof(LNode));head-next NULL;scanf(%d,x);while(x ! 9999){//输入9999表示结束newNode (LNode*)malloc(sizeof(LNode));newNode-next head-next;newNode-data x;head-next newNode;scanf(%d ,x);}return head;
}尾插法建立单链表
LinkList List_TailInsert(LinkList head){LNode *newNode; int x;head (LNode*)malloc(sizeof(LNode));head-next NULL;LNode *p head;//尾指针scanf(%d,x);while(x!9999){newNode (LNode*)malloc(sizeof(LNode));newNode-next NULL;newNode-data x;p-next newNode;p p-next;scanf(%d ,x);}return head;
}书上
LinkList List_TailInsert(LinkList L){int x;L (LNode*)malloc(sizeof(LNode));LNode *s , *r;//r为尾指针 s为新结点scanf(%d ,x);while(x!9999){s (LNode*)malloc(sizeof(LNode));s-data x;r-next s;r s;scanf(%d,x);}r-next NULL;return L;
}双链表
要疯了本来以为就结束了结果才到35
存储结构描述DNode DLinkList
typedef struct DNode{ElemType data;strcut DNode *prior;strcut DNode *next;
}DNode, *DLinkList;插入操作 结点p后插入结点s p-next-prior s;s-prior p;s-next p-next;p-next s; 删除操作 结点p的后继结点q q-next-prior p;p-next q-next;free(q);静态链表
存储结构描述
以next -1 作为其结束的标志。删除插入与动态一致只需要修改指针不需要移动元素没有单链表方便。
#define MaxSize 50
typedef struct {ElemType data;int next;
}SLinkList(MaxSize);第三章 栈、队列和数组
文字内容
问
答
挖
空
选择仅错题
代码内容
