线性表的链式表示
1、单链表
1、节点声明以及初始化2、查找操作
（1）按下标查找---时间复杂度O(n)（2）按值查找---时间复杂度O(n) 3、插入操作
（1）尾插（2）头插（3）带头结点的尾插入（4）不带头结点的尾插（5）指定节点的前插操作 4、删除操作
(1)按照节点删除(2)按照值删除测试：
5、约瑟夫环
2、静态链表
顺序表可以随时读取表中的任意一个元素，他的存储位置可以用一个简单直观的公式直接表示，但插入和删除操作需要移动大量元素。链式存储线性表时，不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理上也相邻。
#include2、查找操作 （1）按下标查找—时间复杂度O(n)#include typedef struct LNode{ int data; struct LNode* next; }LNode,*linkList; void InitList(linkList L) { L->data = 0; L->next = NULL; }
//得到下标为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 = 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 = e;
s->next = p;//s指向p后一个节点
p = s;//p指向s
return true;
}
基本上下面的插入也都是从这两个延伸出来的
（3）带头结点的尾插入//带头结点的尾插入：在下标为i的节点处插入值e
bool 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 = p->data;
p->data = 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、删除操作
删除操作的时间复杂度也是消耗在查找上了
删除步骤如下图所示
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#include typedef 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
#define MaxSize 10
typedef struct Node{
ElemType data;
int next;//游标
};
void testlinkList(){
struct Node a[MaxSize];//数组a作为静态链表
}
