考研&复试数据结构：02线性表的链式表示以及约瑟夫环

线性表的链式表示
文章目录

线性表的链式表示
- 1、单链表
- - 1、节点声明以及初始化
  - 2、查找操作
  - - （1）按下标查找---时间复杂度O(n)
    - （2）按值查找---时间复杂度O(n)
  - 3、插入操作
  - - （1）尾插
    - （2）头插
    - （3）带头结点的尾插入
    - （4）不带头结点的尾插
    - （5）指定节点的前插操作
  - 4、删除操作
  - - (1)按照节点删除
    - (2)按照值删除
    - 测试：
  - 5、约瑟夫环
- 2、静态链表

顺序表可以随时读取表中的任意一个元素，他的存储位置可以用一个简单直观的公式直接表示，但插入和删除操作需要移动大量元素。链式存储线性表时，不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理上也相邻。
1、单链表 1、节点声明以及初始化

#include#includetypedef struct LNode{	int data;	struct LNode* next;}LNode,*LinkList;void InitList(LinkList L) {	L->data = https://tazarkount.com/read/0;	L->next = NULL;}

2、查找操作（1）按下标查找—时间复杂度O(n)

//得到下标为i的节点bool GetNode(LinkList L, int i, LNode* &node) {	if (i < 0) {return false;	}	LNode* p;	int j = 0;	p = L;	while (p != NULL && j < i) {//找到第i个节点p = p->next;j++;	}	if (p == NULL) {//这是链表长度不够i+1跳出循环的时候才进入这个判断return false;	}	node = p;	return true;}

（2）按值查找—时间复杂度O(n)

//得到值为value的节点bool GetNodeValue(LinkList L, int value, LNode*& node) {	LNode* p;	p = L;	while (p!=NULL&&p->data !=value) {p = p->next;	}	if (p == NULL) {//这是没找到return false;	}	node = p;	return true;}

关于修改操作：能查就能改，我就不多写了。
3、插入操作插入操作的时间复杂度也多数来自于找节点上了，插的时候倒是不复杂也不用移动节点。
（1）尾插

bool InsertNextNode(LNode* p, int e) {	LNode* s = (LNode*)malloc(sizeof(LNode));	s->data = https://tazarkount.com/read/e;	s->next = p->next;//s指向p后一个节点	p->next = s;//p指向s	return true;}

（2）头插

bool InsertHead(LNode* p, int e) {	LNode* s = (LNode*)malloc(sizeof(LNode));	s->data = https://tazarkount.com/read/e;	s->next = p;//s指向p后一个节点	p = s;//p指向s	return true;}

基本上下面的插入也都是从这两个延伸出来的
（3）带头结点的尾插入

//带头结点的尾插入：在下标为i的节点处插入值ebool ListInsert1(LinkList& L, int i, int e) {	LNode* p = nullptr;//先GetNode查找到i的上一个节点-----时间复杂度O(n)	if (GetNode(L, i - 1, p)) {//在调用InsertNextNode插入到i的上一个节点后面if (InsertNextNode(p, e)) {return true;}return false;	}	return false;}

（4）不带头结点的尾插

bool ListInsert2(LinkList& L, int i, int e) {	//因为是尾插法所以i = 0 得用头插法写,其余一样	if (i == 0) {if (InsertHead(L, e)) {return false;}	}	LNode* p = nullptr;	if (GetNode(L, i - 1, p)) {if (InsertNextNode(p, e)) {return true;}return false;	}	return false;}

（5）指定节点的前插操作这一步如果比较难理解可以对照下图来看：

//指定节点的前插操作bool InsertPriorNode(LNode* p, int e) {	if (p == NULL) {return false;	}	//这个方法可以不用去找父节点，时间复杂度O（1）	LNode* s = (LNode*)malloc(sizeof(LNode));	s->next = p->next;	p->next = s;	s->data = https://tazarkount.com/read/p->data;	p->data = https://tazarkount.com/read/e;	return true;}

测试：

int main() {	LinkList L = (LNode*)malloc(sizeof(LNode));	//插入	int num = 0;	for (int num = 1; num <= 10; num++) {//带头结点的尾插入ListInsert1(L, num, num * num);	}for (int i = 1; i <= 10; i++) {//打印出来LNode* node = nullptr;GetNode(L, i, node);printf("->%d", node->data);	}	return 0;}

4、删除操作删除操作的时间复杂度也是消耗在查找上了
删除步骤如下图所示
(1)按照节点删除

bool ListDelet(LinkList& L, int i) {	//得到i节点保存至p中	LNode* p;	if (GetNode(L, i, p)) {//得到i-1节点保存至pparent中LNode* pparent;if (GetNode(L, i - 1, pparent)) {//step1:修改i-1节点的next指针：pparent->next = p->next;//step2:释放 i节点free(p);return true;}return false;	}	return false;}

(2)按照值删除

bool ListDeletValue(LinkList& L, int value) {	//得到i节点保存至p中	LNode* p;	if (GetNodeValue(L, value, p)) {//首先排除p是头结点没父亲的情况：if (p == L) {L = L->next;free(p);return true;}//找父亲：LNode* pparent = L;while (pparent != NULL && pparent->next != p) {pparent = pparent -> next;}if (pparent == NULL) {//没找到--基本不可能，除非程序出bug了return false;}//找到了父亲：//step1:修改i-1节点的next指针：pparent->next = p->next;//step2:释放 i节点free(p);return true;	}	return false;}

测试：

int main() {	LinkList L = (LNode*)malloc(sizeof(LNode));	//插入	int num = 0;	for (int num = 1; num <= 10; num++) {//带头结点的尾插入ListInsert1(L, num, num * num);	}for (int i = 1; i <= 10; i++) {//打印出来LNode* node = nullptr;GetNode(L, i, node);printf("->%d", node->data);	}	printf("\n------指定节点的前插操作:---------------\n");	//指定节点的前插操作:	LNode* p = nullptr;	GetNode(L, 10, p);	InsertPriorNode( p, 999);	for (int i = 1; i <= 11; i++) {//打印出来LNode* node = nullptr;GetNode(L, i, node);printf("->%d", node->data);	}	printf("\n--------按照值删除：---------------\n");	//按照值删除：	ListDeletValue(L, 999);	for (int i = 1; i <= 10; i++) {//打印出来LNode* node = nullptr;GetNode(L, i, node);printf("->%d", node->data);	}	return 0;}

5、约瑟夫环约瑟夫问题是个著名的问题：N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。
例如有八个人，他们围成一圈，从1开始报数，假设报4的人被杀掉
死亡顺序：4->8->5->2->1->3->7,最后活下来的是6 。
代码实现步骤：

每个人设置一个kill属性标记：已死亡就设置为true;默认为false;

//约瑟夫环#include#includetypedef struct Human { int num; bool kill; struct Human* next;}*HumanList;

每隔M次循环一圈。只是跳出外面的小循环大循环不跳出。
最后只剩下一个人了就跳出外面的大循环
使用循环链表实现。

//这是先创建一个环bool createRing(HumanList& HL, int n) {	if (n < 1) {return false;	}	Human* human = (Human*)malloc(sizeof(Human));	human = HL;	human->num = 1;	human->next = HL;	for (int i = 2; i <= n; i++) {Human* humanNext = (Human*)malloc(sizeof(Human));humanNext->num = i;humanNext->next = human->next;human->next = humanNext;human = humanNext;	}	return true;}//这是杀一圈人得出结果的环int JosephRing(HumanList HL, int M) {	Human* human = (Human*)malloc(sizeof(Human));	int i = 1;	int j = 0;//累计看看杀掉几个人了 。human = HL;	while (1) {if (human->kill == true) {//如果这个人已经被杀死了就越过他 。human = human->next;continue;}if (i == M) {human->kill = true;i = 1;//重新开始计数j++;if (j == M - 1) {//这时候就只剩下一个人了，就跳出整个循环了break;}continue;}human = human->next;i++;	}	while (human->kill == true) {human = human->next;	}	//跳出循环的条件是碰到有一个人没被杀死	//返回这个人的序号	return human->num;}

测试

int main() {	//创建一个N = 8的约瑟夫环	HumanList HL1 = (Human*)malloc(sizeof(Human));	createRing(HL1, 8);	//运行看看谁剩下	int M = 4;	printf("%d", JosephRing(HL1, M));}

最后输出结果是：6，和预期一样。
2、静态链表静态链表是借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next,与前面所讲的链表中的指针不同的是，这里的指针式节点的相对地址（数组下标），又称游标。和顺序表一样，静态链表也要预先分配一块连续的内存空间。
应用：文件分配表FATMN
【考研&复试数据结构：02线性表的链式表示以及约瑟夫环】

#define MaxSize 10typedef struct Node{	ElemType data;	int next;//游标};void testLinkList(){	struct Node a[MaxSize];//数组a作为静态链表}

考研&amp;复试数据结构：02线性表的链式表示以及约瑟夫环

考研&复试数据结构：02线性表的链式表示以及约瑟夫环