目录
顺序表、单向链表、单向循环链表、顺序栈、链式栈、循环队列、链式队列、双向链表、双向循环链表
1）逻辑结构：线性结构
2）存储结构：顺序、链式
3）特点：一对一、每一个节点最多有一个前驱和一个后继，首节点无前驱，尾节点无后继
1.顺序表
特点：内存连续（数组）
1）逻辑结构：线性结构
2）存储结构：顺序存储
3）操作：增删改查
函数名命名规则：
下滑线法：create_empty_seqlist
小驼峰法：createEmptySeqList
大驼峰法：CreateEmptySeqList
1.1数组的插入删除操作
练习：
int a[100]={1,2,3,4,5,6,7,8};
//1)向数组的第几个位置插入数据
int *p //保存的数组的首地址
int n//n代表的是数组中有效的元素个数（非数组的长度size 100）8
int post;//位置 代表的是第几个位置，数组元素下标 位置的编号从0开始 position
int data;//插入到数组中的数据
void insertIntoA (int *p,int post,int data,int n)
{
1.将n-1 ~ post 位置的所有数据整体向后移动一个位置
2..将新数据data 赋值到post位置
}
//删除数组指定位置的数据
void deleteFromA(int *p, int n, int post)
{
//将post+1 ----->n-1位置所有数据向前移动一个位置，覆盖删除
}
//遍历打印数组元素
void show(int *p,int n)
{}
arr.c
#include <stdio.h>
void insertIntoA(int *p, int post, int data, int n)
{
int i;
// 1.将n - 1 ~post 位置的所有数据整体向后移动一个位置
for (i = n - 1; i >= post; i--)
p[i + 1] = p[i];
// 2.将新数据data 赋值到post位置
p[post] = data;
}
// 删除数组指定位置的数据
void deleteFromA(int *p, int n, int post)
{
// 将post+1 ----->n-1位置所有数据向前移动一个位置，覆盖删除
for (int i = post + 1; i <= n - 1; i++)
p[i - 1] = p[i];
}
// 遍历打印数组元素
void show(int *p, int n)
{
for (int i = 0; i < n; i++)
printf("%d ", p[i]);
printf("\n");
}
int main(int argc, char const *argv[])
{
int a[100] = {1, 2, 3, 4, 5, 6, 7, 8};
show(a, 8);
insertIntoA(a, 1, 200, 8);
show(a, 9);
deleteFromA(a, 9, 1);
show(a, 8);
return 0;
}
1.2修改为last版本
arr_last.c
#include <stdio.h>
int last=7;//最后一个有效元素的下标 last == n-1
void insertIntoA(int *p, int post, int data)
{
int i;
// 1.将last ~post 位置的所有数据整体向后移动一个位置
for (i = last; i >= post; i--)
p[i + 1] = p[i];
// 2.将新数据data 赋值到post位置
p[post] = data;
//3.最后一个有效元素的下标+1
last++;
}
// 删除数组指定位置的数据
void deleteFromA(int *p,int post)
{
//1.将post+1 ----->last位置所有数据向前移动一个位置，覆盖删除
for (int i = post + 1; i <= last; i++)
p[i - 1] = p[i];
// 2.最后一个有效元素的下标-1
last--;
}
// 遍历打印数组元素
void show(int *p)
{
for (int i = 0; i <= last; i++)
printf("%d ", p[i]);
printf("\n");
}
int main(int argc, char const *argv[])
{
int a[100] = {1, 2, 3, 4, 5, 6, 7, 8};
show(a);
insertIntoA(a, 1, 200);
show(a);
deleteFromA(a,1);
show(a);
return 0;
}
1.3顺序表的相关操作
#ifndef _SEQLIST_H__
#define _SEQLIST_H__
#include <stdio.h>
#include <stdlib.h>
#define N 5
typedef struct seq
{
int data[N];
int last;
}seqlist_t;
//1.创建一个空的顺序表
seqlist_t *CreateEpSeqlist();//返回的是申请空间的首地址
//2.向顺序表的指定位置插入数据
int InsertIntoSeqlist(seqlist_t *p, int post,int data);//post第几个位置，data插入的数据
//3.遍历顺序表sequence 顺序 list 表
void ShowSeqlist(seqlist_t *p);
//4.判断顺序表是否为满,满返回１ 未满返回０
int IsFullSeqlist(seqlist_t *p);
//5.判断顺序表是否为空
int IsEpSeqlist(seqlist_t *p);
//6.删除顺序表中指定位置的数据post删除位置
int DeletePostSeqlist(seqlist_t *p, int post);
//7.清空顺序表
void ClearSeqList(seqlist_t *p);
//8.修改指定位置的数据
int ChangePostSeqList(seqlist_t *p,int post,int data);//post被修改的位置，data修改成的数据
//9.查找指定数据出现的位置
int SearchDataSeqList(seqlist_t *p,int data);//data代表被查找的数据
#endif
seqlist.c
#include "seqlist.h"
//1.创建一个空的顺序表
seqlist_t *CreateEpSeqlist()//返回的是申请空间的首地址
{
//1.动态申请一个结构体大小的空间
seqlist_t * p =(seqlist_t *)malloc(sizeof(seqlist_t));
if(p==NULL)
{
perror("CreateEpSeqlist err");
return NULL;
}
//2.对last初始化
p->last = -1;//表示当前数组为空，有效元素个数为0
return p;
}
//4.判断顺序表是否为满,满返回１ 未满返回０
int IsFullSeqlist(seqlist_t *p)
{
return p->last == N-1;
}
//2.向顺序表的指定位置插入数据
int InsertIntoSeqlist(seqlist_t *p, int post,int data)//post第几个位置，data插入的数据
{
//0.容错判断
if( post < 0 || post > p->last+1 || IsFullSeqlist(p))
{
perror("InsertIntoSeqlist err");
return -1;
}
//1.将last---post位置整体向后移动一个位置
for(int i=p->last;i>=post;i--)
p->data[i+1]= p->data[i];
//2.将数据插入顺序表
p->data[post] = data;
//3.最后一个有效元素下标++
p->last++;
return 0;
}
//3.遍历顺序表sequence 顺序 list 表
void ShowSeqlist(seqlist_t *p)
{
for(int i = 0;i<=p->last;i++)
printf("%d ",p->data[i]);
printf("\n");
}
//5.判断顺序表是否为空
int IsEpSeqlist(seqlist_t *p)
{
return p->last == -1;
}
//6.删除顺序表中指定位置的数据post删除位置
int DeletePostSeqlist(seqlist_t *p, int post)
{
//0.容错判断
if(post < 0 || post >= p->last+1 || IsEpSeqlist(p))
{
perror("DeletePostSeqlist err");
return -1;
}
//1.将post+1 --- last位置所有数据整体向前移动一个位置
for(int i = post+1;i<=p->last;i++)
p->data[i-1]=p->data[i];
//2.将最后一个元素下标--
p->last--;
return 0;
}
//7.清空顺序表
void ClearSeqList(seqlist_t *p)
{
p->last = -1;
}
//8.修改指定位置的数据
int ChangePostSeqList(seqlist_t *p,int post,int data)//post被修改的位置，data修改成的数据
{
//1.容错判断
if(post < 0 || post >= p->last+1 || IsEpSeqlist(p))
{
perror("ChangePostSeqList err");
return -1;
}
//2.修改指定位置数据
p->data[post] = data;
return 0;
}
//9.查找指定数据出现的位置
int SearchDataSeqList(seqlist_t *p,int data)//data代表被查找的数据
{
int i;
for(i=0;i<=p->last;i++)
if(p->data[i] == data)
return i;
return -1;//没有数据data
}
main.c
#include"seqlist.h"
int main(int argc, char const *argv[])
{
seqlist_t *p = CreateEpSeqlist();
InsertIntoSeqlist(p,0,1);
InsertIntoSeqlist(p,1,2);
InsertIntoSeqlist(p,2,3);
InsertIntoSeqlist(p,3,4);
InsertIntoSeqlist(p,4,5);
// InsertIntoSeqlist(p,5,6);
ShowSeqlist(p);// 1 2 3 4 5
DeletePostSeqlist(p,2);
ShowSeqlist(p);// 1 2 4 5
ChangePostSeqList(p,0,100);
ShowSeqlist(p);//100 2 4 5
printf("%d post is %d\n",100,SearchDataSeqList(p,100));
ClearSeqList(p);
if(IsEpSeqlist(p))
printf("IsEpSeqlist\n");
free(p);
p = NULL;
return 0;
}
Makefile
CC=gcc
CFLAGS=-c -g -Wall
OBJS=main.o seqlist.o
seqlist:$(OBJS)
$(CC) $^ -o $@
%.o:%.c
$(CC) $(CFLAGS) $< -o $@
.PHONY:clean
clean:
$(RM) *.o seqlist
1.4顺序表总结：
- 顺序表在内存中连续存储
- 顺序表的长度是固定的，#define N 5
- 顺序表查找数据、修改数据比较方便的，插入和删除麻烦
2.链表
特点：内存不连续，通过指针进行连接
解决: 长度固定的问题，插入删除麻烦的问题
- 逻辑结构：线性结构
- 存储结构：链式存储
- 操作：增删改查
2.1单向链表
结构体：
struct node_t
{
int data;//数据域
struct node_t * next;//指针域
}；
2.1.1分类
1）有头单向链表
存在一个头节点，数据域无效，指针域有效
遍历有头单向链表：
#include <stdio.h>
typedef struct node_t
{
int data;
struct node_t *next;
} link_node_t, *link_list_t;
// typedef struct node_t link_node_t;
// typedef struct node_t * link_list_t;
// link_list_t == struct node_t *
int main(int argc, char const *argv[])
{
// 1.定义几个节点（结构体变量）
link_node_t s;
link_node_t a = {1, NULL};
link_node_t b = {2, NULL};
link_node_t c = {3, NULL};
// 2.将节点连接到一起
s.next = &a;
a.next = &b;
b.next = &c;
// 3.定义一个头指针，指向头节点
link_list_t h = &s;
// 4.遍历有头单向链表(1)
// while (h->next != NULL)
// {
// h = h->next;
// printf("%d ", h->data);
// }
// 4.遍历有头单向链表(2)
h=h->next;
while(h!= NULL)
{
printf("%d ",h->data);
h = h->next;
}
printf("\n");
return 0;
}
2）无头单向链表
所有节点的指针域和数据域都有效
遍历无头单向链表
#include<stdio.h>
typedef struct node_t
{
int data;
struct node_t *next;
}link_node_t,*link_list_t;
// typedef struct node_t link_node_t;
// typedef struct node_t * link_list_t;
// link_list_t == struct node_t *
int main(int argc, char const *argv[])
{
//1.定义几个节点（结构体变量）
link_node_t a={1,NULL};
link_node_t b={2,NULL};
link_node_t c={3,NULL};
//2.将节点连接到一起
a.next = &b;
b.next = &c;
//3.定义一个头指针，指向第一个节点
link_list_t h = &a;
//4.遍历无头单向链表
while (h != NULL)
{
printf("%d ",h->data);
h = h->next;
}
printf("\n");
return 0;
}
2.1.2操作函数
linklist.h
#ifndef _LINKLIST_H_
#define _LINKLIST_H_
#include<stdio.h>
#include<stdlib.h>
typedef int datatype;
typedef struct node_t
{
datatype data;//数据域
struct node_t *next;//指针域,指向自身结构体的指针
}link_node_t,*link_list_t;
//1.创建一个空的单向链表(有头单向链表)
link_node_t *CreateEpLinkList();
//2.向单向链表的指定位置插入数据
//p保存链表的头指针 post 插入的位置 data插入的数据
int InsertIntoPostLinkList(link_node_t *p,int post, datatype data);
//3.遍历单向链表
void ShowLinkList(link_node_t *p);
//4.求单向链表长度的函数
int LengthLinkList(link_node_t *p);
//5.删除单向链表中指定位置的数据 post 代表的是删除的位置
int DeletePostLinkList(link_node_t *p, int post);
//6.判断单向链表是否为空 1代表空 0代表非空
int IsEpLinkList(link_node_t *p);
//7.修改指定位置的数据 post 被修改的位置 data修改成的数据
int ChangePostLinkList(link_node_t *p, int post, datatype data);
//8.查找指定数据出现的位置 data被查找的数据 //search 查找
int SearchDataLinkList(link_node_t *p, datatype data);
//9.删除单向链表中出现的指定数据,data代表将单向链表中出现的所有data数据删除
int DeleteDataLinkList(link_node_t *p, datatype data);
//10.转置链表
void ReverseLinkList(link_node_t *p);
//11.清空单向链表
void ClearLinkList(link_node_t *p);
#endif
1）创建一个空的（有头）单向链表
2）向post位置插入一个数据
- 先遍历找到要插入节点的前一个节点，假设这个节点为A；A的下一个节点为B；将C插入A与B之间；
- 先让C的指针域指向B；
- 再让A的指针域指向C；
（注意：顺序不可以调换）
3）删除指定位置的数据
1、先遍历找到要删除节点的前一个节点，假设为A；
2、找一个临时指针指向要删除的节点；
- 将A的指针域指向删除节点的下一个节点；
- 释放被删除节点
4）单向链表的转置
转置的思想：
(1) 将头节点与当前链表断开，断开前保存下头节点的下一个节点，保证后面链表能找得到，定义一个q保存头节点的下一个节点，断开后前面相当于一个空的链表，后面是一个无头的单向链表
(2) 遍历无头链表的所有节点，将每一个节点当做新节点插入空链表头节点的下一个节点(每次插入的头节点的下一个节点位置)
linklist.c
#include "linklist.h"
// 1.创建一个空的单向链表(有头单向链表)
link_node_t *CreateEpLinkList()
{
// 1.开辟一个结构体类型大小的空间
link_list_t p = (link_list_t)malloc(sizeof(link_node_t));
if (p == NULL)
{
perror("CreateEpLinkList");
return NULL;
}
// 2.初始化
p->next = NULL; // 空链表
return p;
}
// 4.求单向链表长度的函数
int LengthLinkList(link_node_t *p)
{
int len = 0;
while (p->next != NULL)
{
p = p->next;
len++;
}
return len;
}
// 2.向单向链表的指定位置插入数据
// p保存链表的头指针 post 插入的位置 data插入的数据
int InsertIntoPostLinkList(link_node_t *p, int post, datatype data)
{
// 0.容错判断
if (post < 0 || post > LengthLinkList(p))
{
perror("InsertIntoPostLinkList err");
return -1;
}
// 1.将头指针移动到被插入位置的前一个节点
for (int i = 0; i < post; i++)
p = p->next;
// 2.创建一个新节点，保存即将插入的数据
link_list_t pnew = (link_list_t)malloc(sizeof(link_node_t));
if (pnew == NULL)
{
perror("pnew malloc err");
return -1;
}
pnew->data = data; // 将新节点装上数据
pnew->next = NULL;
// 3.将新节点插入链表（先连后面，再连前面）
pnew->next = p->next;
p->next = pnew;
return 0;
}
// 6.判断单向链表是否为空 1代表空 0代表非空
int IsEpLinkList(link_node_t *p)
{
return p->next == NULL;
}
// 5.删除单向链表中指定位置的数据 post 代表的是删除的位置
int DeletePostLinkList(link_node_t *p, int post)
{
// 0.容错判断
if (post < 0 || post >= LengthLinkList(p) || IsEpLinkList(p))
{
perror("DeletePostLinkList");
return -1;
}
// 1.将头指针移动到被删除位置的前一个节点
for (int i = 0; i < post; i++)
p = p->next;
// 2.进行删除操作
// 1）定义pdel指向被删除节点
link_list_t pdel = p->next;
// 2）跨过被删除节点
p->next = pdel->next;
// 3）释放被删除节点
free(pdel);
pdel = NULL;
return 0;
}
// 3.遍历单向链表
void ShowLinkList(link_node_t *p)
{
while (p->next != NULL)
{
p = p->next;
printf("%d ", p->data);
}
printf("\n");
}
// 7.修改指定位置的数据 post 被修改的位置 data修改成的数据
int ChangePostLinkList(link_node_t *p, int post, datatype data)
{
// 1.容错判断
if (post < 0 || post >= LengthLinkList(p) || IsEpLinkList(p))
{
perror("ChangePostLinkList");
return -1;
}
// 2.将头指针移动到被修改位置
for (int i = 0; i <= post; i++)
p = p->next;
// 3.修改数据
p->data = data;
return 0;
}
// 8.查找指定数据出现的位置 data被查找的数据 //search 查找
int SearchDataLinkList(link_node_t *p, datatype data)
{
int post = 0; // 记录查找的位置
// 遍历链表，查找数据
while (p->next != NULL)
{
p = p->next;
if (p->data == data)
return post;
post++;
}
return -1; // 数据不存在
}
// 9.删除单向链表中出现的指定数据,data代表将单向链表中出现的所有data数据删除
int DeleteDataLinkList(link_node_t *p, datatype data)
{
// 1.定义一个指针q指向头节点的下一个节点，此时可以看作q指向一个无头单向链表
link_list_t q = p->next;
// 2.用q遍历无头单向链表，将每一个节点的数据域与data做比较，如果相同就删除
while (q != NULL)
{
if (q->data == data) // 如果相等，说明需要删除q指向的节点
{
// 跨过被删除节点
p->next = q->next;
// 释放被删除节点
free(q);
// 将q指向链表删除节点的下一个节点
q = p->next;
}
else // 不相等，指针向后移动
{
p = p->next;
q = p->next;
}
}
return 0;
}
//11.清空单向链表
void ClearLinkList(link_node_t *p)
{
// link_list_t pdel = NULL;
while (!IsEpLinkList(p))
{
DeletePostLinkList(p,0);
// pdel = p->next;
// p->next = pdel->next;
// free(pdel);
// pdel=NULL;
}
}
//10.转置链表
void ReverseLinkList(link_node_t *p)
{
link_list_t temp = NULL;//临时保存q下一个节点的地址
//断开前，保存头节点的下一个节点的地址
link_list_t q = p->next;//指向头节点的下一个节点（相当于无头单向链表的头指针）
//1.断头，断开链表
p->next = NULL;
//2.遍历无头单向链表
while (q != NULL)
{
//暂时存放q的下一个节点，防止链表丢失
temp = q->next;
//头插到有头单向链表头节点的后面
q->next = p->next;
p->next = q;
//将q重新指向之前的无头单向链表，指向此时的第一个节点
q=temp;
}
}
main.c
#include "linklist.h"
int main(int argc, char const *argv[])
{
link_list_t p = CreateEpLinkList();
InsertIntoPostLinkList(p,0,1);
InsertIntoPostLinkList(p,1,2);
InsertIntoPostLinkList(p,2,3);
ShowLinkList(p);// 1 2 3
ReverseLinkList(p);
ShowLinkList(p);//3 2 1
DeletePostLinkList(p,1);
ShowLinkList(p);// 3 1
ChangePostLinkList(p,0,100);
ShowLinkList(p);// 100 1
printf("%d post is %d\n",100,SearchDataLinkList(p,100));//0
ClearLinkList(p);
if(IsEpLinkList(p))
printf("IsEpLinkList\n");
free(p);
p =NULL;
return 0;
}
2.2单向循环链表
解决约瑟夫问题
约瑟夫问题为：设编号为1，2，……n得n个人围坐一圈，约定编号为k（k大于等于1并且小于等于n）的人从1开始报数，数到m的那个人出列。它的下一位继续从1开始报数，数到m的人出列，依次类推，最后剩下一个为猴王。
直接上图展示，初始化状态： 假设n=6，总共有6个人，k=1,从第一个人开始报数，m=5,每次数五个。
第一次报数：从一号开始，数五个数，1-2-3-4-5，数完五个数，五号被杀死，第一次报数后，剩余人数如下。
第二次报数： 从被杀死的五号的下一位开始报数，也就是六号，数五个数，6-1-2-3-4，数数完毕，四号被杀死，第二次报数后，剩余人数如下
第三次报数： 从被杀死的四号的下一位开始报数，同样是六号，数五个数，6-1-2-3-6，数数完毕，六号被杀死，第三次报数后，剩余人数如下。
第四次报数： 从被杀死的六号的下一位开始报数，也就是一号，数五个数，1-2-3-1-2，数数完毕，二号被杀死，第四次报数后，剩余人数如下。
第五次报数： 从被杀死的二号的下一位开始报数，也就是三号，数五个数，3-1-3-1-3，数数完毕，三号被杀死，只剩下一号
#include <stdio.h>
#include <stdlib.h>
typedef struct node_t
{
int data;
struct node_t *next;
}link_node_t,*link_list_t;
int main(int argc, const char *argv[])
{
int i;
link_list_t pdel = NULL;//用于指向被删除节点
link_list_t ptail = NULL;//永远指向当前链表的尾
link_list_t pnew = NULL;//永远指向新创建的节点
link_list_t h = NULL;
int all_num = 7;//猴子总数
int start_num = 2; //从几号猴子开始数
int kill_num = 3;//数到几杀死猴
// printf("请您入猴子总数 起始号码 数到几杀死:\n");
// scanf("%d%d%d",&all_num,&start_num,&kill_num);
//1.创建出一个单向循环链表
//(1)创建有all_num个节点的单向链表
h = (link_list_t)malloc(sizeof(link_node_t));
if(NULL == h)
{
perror("malloc failed");
return -1;
}
h->data = 1;
h->next = NULL;
ptail = h;//尾指针指向当前的第一个节点
for(i = 2; i <= all_num; i++)
{
//创建新的节点
pnew = (link_list_t)malloc(sizeof(link_node_t));
if(NULL == pnew)
{
perror("malloc failed");
return -1;
}
//将新节点装上数据
pnew->data = i;
pnew->next = NULL;
//将新节点链接到链表尾
ptail->next = pnew;//链接到链表的尾
ptail = pnew;//尾指针继续指向当前链表的尾
}
//(2)将头指针保存到链表的尾形成单向循环链表
ptail->next = h;//形成单向循环链表
#if 0 //用于调试程序
while(1)
{
printf("%d\n",h->data);
h = h->next;
sleep(1);
}
#endif
//2.开始杀猴子
//(1)将头指针移动到开始猴子的号码处
for(i = 0; i < start_num-1; i++)
h = h->next;
//(2)循环进行杀猴子
while(h != h->next)//条件不成的时候，就剩一个猴子,只有一个节点
{
//将头指针移动到即将删除节点的前一个节点
for(i = 0; i < kill_num-2; i++)
h = h->next;
pdel = h->next;
//跨过删除节点
h->next = pdel->next;
printf("kill is -------------%d\n",pdel->data);
free(pdel);
pdel = NULL;
//杀死猴子猴，从下一个节点开始继续开始数,将头指针移动到开始数的地方
h = h->next;
}
printf("king is=================== %d\n",h->data);
return 0;
}
总结：
顺序表和单向链表比较
(1)顺序表在内存当中连续存储的(数组)，但是链表在内存当中是不连续存储的，通过指针将数据链接在一起
(2)顺序表的长度是固定的，但是链表长度不固定
(3)顺序表查找方便，但是插入和删除麻烦，链表，插入和删除方便，查找麻烦
2.3双向链表
//双向链表的节点定义
typedef int datatype;
typedef struct node_t
{
datatype data;//数据域
struct node_t *next;//指向下一个节点的指针 next 下一个
struct node_t *prior;//指向前一个节点的指针 prior 先前的
}link_node_t,*link_list_t;
//将双向链表的头指针和尾指针封装到一个节点体里
//思想上有点像学的链式队列
typedef struct doublelinklist
{
link_list_t head; //指向双向链表的头指针
link_list_t tail; //指向双向链表的尾指针
int len; //用来保存当前双向链表的长度
}double_node_t,*double_list_t;
2.3.1操作函数
1）创建一个空的双向链表
2）双向链表中间插入
- 双向链表尾插
4）双线链表中间删除
5）双线链表删除最后一个节点
#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node_t
{
datatype data; // 数据域
struct node_t *next; // 指向下一个节点的指针 next 下一个
struct node_t *prior; // 指向前一个节点的指针 prior 前一个
} link_node_t, *link_list_t;
// 将双向链表的头指针和尾指针封装到一个结构体里
// 思想上有点像学的链式队列
typedef struct doublelinklist
{
link_list_t head; // 指向双向链表的头指针
link_list_t tail; // 指向双向链表的尾指针
int len;
} double_node_t, *double_list_t;
// 1.创建一个空的双向链表
double_list_t createEmptyDoubleLinkList()
{
// 1.开辟一个存放头尾指针结构体的空间
double_list_t p = (double_list_t)malloc(sizeof(double_node_t));
if (p == NULL)
{
perror("createEmptyDoubleLinkList");
return NULL;
}
// 2.初始化 （开辟头节点空间）
p->len = 0;
p->head = p->tail = (link_list_t)malloc(sizeof(link_node_t));
if (p->head == NULL)
{
perror("p->head malloc err");
return NULL;
}
// 3.初始化头节点
p->head->prior = NULL;
p->head->next = NULL;
return p;
}
// 2.向双向链表的指定位置插入数据 post位置， data数据
int insertIntoDoubleLinkList(double_list_t p, int post, datatype data)
{
link_list_t temp = NULL; // 用来临时保存head或tail的位置
// 1.容错判断
if (post < 0 || post > p->len)
{
printf("post err\n");
return -1;
}
// 2.开辟一个新节点空间存放数据
link_list_t pnew = (link_list_t)malloc(sizeof(link_node_t));
if (pnew == NULL)
{
perror("pnew malloc err");
return -1;
}
pnew->data = data;
pnew->next = NULL;
pnew->prior = NULL;
// 3.将节点插入链表
// 先对插入的位置进行判断,分为两种情况
if (post == p->len) // 尾插
{
p->tail->next = pnew;
pnew->prior = p->tail;
p->tail = pnew; // 移动尾指针
}
else // 中间插
{
// 1）将temp移动到被插入的位置
if (post < p->len / 2) // 前半段
{
temp = p->head; // 从前向后遍历
for (int i = 0; i <= post; i++)
temp = temp->next;
}
else // 后半段
{
temp = p->tail; // 从后向前遍历
for (int i = 0; i < p->len - 1 - post; i++)
temp = temp->prior;
}
// 2）进行插入操作（先连前面，再连后面）
temp->prior->next = pnew;
pnew->prior = temp->prior;
pnew->next = temp;
temp->prior = pnew;
}
// 链表长度+1
p->len++;
return 0;
}
// 3.遍历双向链表
void showDoubleLinkList(double_list_t p)
{
printf("正向遍历：");
link_list_t temp = p->head;
while (temp->next != NULL)
{
temp = temp->next;
printf("%d ", temp->data);
}
printf("\n*******************\n");
printf("反向遍历：");
temp = p->tail;
while (temp != p->head)
{
printf("%d ", temp->data);
temp = temp->prior;
}
printf("\n-------------------\n");
}
// 5.判断双向链表是否为空
int isEmptyDoubleLinkList(double_list_t p)
{
return p->len == 0;
}
// 4.删除双向链表指定位置的数据
int deletePostDoubleLinkList(double_list_t p, int post)
{
link_list_t temp = NULL;
// 1.容错判断
if (post < 0 || post >= p->len || isEmptyDoubleLinkList(p))
{
perror("deletePostDoubleLinkList\n");
return -1;
}
// 2.对删除位置进行判断分为两种情况
if (post == p->len - 1) // 尾删
{
// 向前移动尾指针
p->tail = p->tail->prior;
// 释放被删除节点
free(p->tail->next);
p->tail->next = NULL;
}
else // 中间删
{
// 1）将temp移动到被删除的位置
if (post < p->len / 2) // 前半段
{
temp = p->head; // 从前向后遍历
for (int i = 0; i <= post; i++)
temp = temp->next;
}
else // 后半段
{
temp = p->tail; // 从后向前遍历
for (int i = 0; i < p->len - 1 - post; i++)
temp = temp->prior;
}
// 2）进行删除操作
temp->prior->next = temp->next;
temp->next->prior = temp->prior;
free(temp);
temp = NULL;
}
// 链表长度-1
p->len--;
return 0;
}
// 6.求双向链表的长度
int lengthDoubleLinkList(double_list_t p)
{
return p->len;
}
// 7.查找指定数据出现的位置 data被查找的数据
int searchPostDoubleLinkList(double_list_t p, datatype data)
{
link_list_t h = p->head;
int post=0;
while (h->next != NULL)// 类似于遍历一个有头的单向链表
{
h=h->next;
if(h->data == data)
return post;
post++;
}
return -1;
}
// 8.修改指定位置的数据,post修改的位置 data被修改的数据
int changeDataDoubleLinkList(double_list_t p, int post, datatype data)
{
link_list_t temp = NULL;
//1.容错判断
if(post < 0 || post >= p->len)
{
perror("changeDataDoubleLinkList");
return -1;
}
//2.将temp移动到被修改的位置
if (post < p->len / 2) // 前半段
{
temp = p->head; // 从前向后遍历
for (int i = 0; i <= post; i++)
temp = temp->next;
}
else // 后半段
{
temp = p->tail; // 从后向前遍历
for (int i = 0; i < p->len - 1 - post; i++)
temp = temp->prior;
}
//3.修改数据
temp->data = data;
return 0;
}
// 9.删除双向链表中的指定数据 data代表删除所有出现的data数据
int deleteDataDoubleLinkList(double_list_t p, datatype data)
{
link_list_t h = p->head->next;
link_list_t pdel =NULL;
while (h != NULL)
{
if(h->data == data)//删除
{
if(h == p->tail)//尾删
{
p->tail = p->tail->prior;
free(p->tail->next);
p->tail->next = NULL;
h=NULL;
}
else//中间删
{
h->prior->next = h->next;
h->next->prior = h->prior;
pdel=h;
h=h->next;
free(pdel);
pdel = NULL;
}
p->len--;//长度-1
}
else//不相等
h=h->next;
}
return 0;
}
int main(int argc, char const *argv[])
{
double_list_t p = createEmptyDoubleLinkList();
for (int i = 1; i <= 5; i++)
insertIntoDoubleLinkList(p, i - 1, i);
showDoubleLinkList(p);
printf("len is %d\n",lengthDoubleLinkList(p));
changeDataDoubleLinkList(p,1,200);
printf("%d post is %d\n",200,searchPostDoubleLinkList(p,200));
deleteDataDoubleLinkList(p,5);
showDoubleLinkList(p);
while (!isEmptyDoubleLinkList(p))
deletePostDoubleLinkList(p, 0);
if (isEmptyDoubleLinkList(p))
printf("isEmptyDoubleLinkList\n");
free(p->head);
p->head = NULL;
p->tail = NULL;
free(p);
p = NULL;
return 0;
}
2.4双向循环链表
#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node_t
{
datatype data;
struct node_t * prior;
struct node_t * next;
}link_node_t,*link_list_t;
typedef struct doublelinklist
{
link_list_t head;
link_list_t tail;
}double_node_t,*double_list_t;
int main(int argc, const char *argv[])
{
int i;
int all_num = 8;//猴子总数
int start_num = 3;//从3号猴子开始数
int kill_num = 3;//数到几杀死猴子
link_list_t h = NULL;
link_list_t pdel = NULL;//用来指向被杀死猴子的节点
printf("请您输入猴子的总数，开始号码，出局号码:\n");
scanf("%d%d%d",&all_num,&start_num,&kill_num);
//1.创建一个双向的循环链表
double_list_t p = (double_list_t)malloc(sizeof(double_node_t));//申请头指针和尾指针
if(NULL == p)
{
perror("malloc failed");
return -1;
}
p->head = p->tail = (link_list_t)malloc(sizeof(link_node_t));
if(NULL == p->tail)
{
perror("p->tail malloc failed");
return -1;
}
p->head->data = 1;
p->head->prior = NULL;
p->head->next = NULL;
//将创建n个新的节点，链接到链表的尾
for(i = 2; i <= all_num; i++)
{
link_list_t pnew = (link_list_t)malloc(sizeof(link_node_t));
if(NULL == pnew)
{
perror("pnew malloc failed");
return -1;
}
pnew->data = i;
pnew->prior = NULL;
pnew->next = NULL;
//(1)将新的节点链接到链表的尾
p->tail->next = pnew;
pnew->prior = p->tail;
//(2)尾指针向后移动，指向当前链表的尾
p->tail = pnew;
}
//(3)形成双向循环链表
p->tail->next = p->head;
p->head->prior = p->tail;
//调试程序
#if 0
while(1)
{
printf("%d\n",p->head->data);
p->head = p->head->next;
sleep(1);
}
#endif
//2.循环进行杀死猴子
h = p->head;
//(1)先将h移动到start_num处，也就是开始数数的猴子号码处
for(i = 0; i < start_num-1; i++)
h = h->next;
while(h->next != h)//当h->next == h 就剩一个节点了，循环结束
{
//(2)将h移动到即将杀死猴子号码的位置
for(i = 0; i < kill_num-1; i++)
h = h->next;
//(3)进行杀死猴子，经过上面的循环后，此时的h指向即将杀死的猴子
h->prior->next = h->next;
h->next->prior = h->prior;
pdel = h;//pdel指向被杀死猴子的位置
printf("kill is -------%d\n",pdel->data);
h = h->next;//需要移动，从杀死猴子后的下一个位置开始数
free(pdel);
}
printf("猴王是%d\n",h->data);
return 0;
}
3.栈
1.什么是栈?
只能在一端进行插入和删除操作的线性表（又称为堆栈），进行插入和删除操作的一端称为栈顶，另一端称为栈底
2. 栈特点：
先进后出 FILO first in last out LIFO
杯子：往杯子里放大饼，先放进去的大饼，最后一个拿出来
3.1顺序栈
1）逻辑结构：线性结构
2）存储结构：顺序存储
3）操作：入栈、出栈
typedef struct seqstack
{
int *data;
int maxlen;
int top;
}seqstack_t;
1）创建一个空的栈
2）入栈
判满
移动栈针
将数据入栈
3）出栈
判空
移动栈针
将数据出栈
seqstack.c
#include <stdio.h>
#include <stdlib.h>
typedef struct seqstack
{
int *data; // 指向栈的存储位置
int maxlen; // 保存栈的最大长度
int top; // 称为栈针，用的时候，心里面可以将按照顺序表里的last来使用
// top 始终代表当前栈内最后一个有效元素的下标
} seqstack_t;
// 1.创建一个空的栈
seqstack_t *CreateEpSeqStack(int len) // len代表的是创建栈的时候的最大长度
{
// 1.开辟一个结构体类型大小的空间
seqstack_t *p = (seqstack_t *)malloc(sizeof(seqstack_t));
if (p == NULL)
{
perror("CreateEpSeqStack err");
return NULL;
}
// 2.初始化
p->maxlen = len; // 保存栈的最大长度
p->top = -1; // 栈为空暂时将最后一个下标赋值为-1 类似与创建空的顺序表中的last
p->data = (int *)malloc(sizeof(int) * len);
if (p->data == NULL)
{
perror("p->data malloc err");
free(p);
p = NULL;
return NULL;
}
return p;
}
// 2.判断是否为满,满返回1 未满返回0
int IsFullSeqStack(seqstack_t *p)
{
return p->top + 1 == p->maxlen;
}
// 3.入栈
int PushStack(seqstack_t *p, int data) // data代表入栈的数据
{
// 1.容错判断（判满）
if (IsFullSeqStack(p))
{
perror("IsFullSeqStack");
return -1;
}
// 2.移动栈针
p->top++;
// 3.入栈
p->data[p->top] = data;
return 0;
}
// 4.判断栈是否为空
int IsEpSeqStack(seqstack_t *p)
{
return p->top == -1;
}
// 5.出栈
int PopSeqStack(seqstack_t *p)
{
// 1.判空
if (IsEpSeqStack(p))
{
perror("IsEpSeqStack");
return -1;
}
// 2.移动栈针
p->top--;
// 3.出栈数据
return p->data[p->top + 1];
}
// 6. 清空栈
void ClearSeqStack(seqstack_t *p)
{
p->top = -1;
}
// 7. 获取栈顶数据(注意不是出栈操作，如果出栈，相当于删除了栈顶数据，只是将栈顶的数据获取到，不需要移动栈针)
int GetTopSeqStack(seqstack_t *p)
{
while (!IsEpSeqStack(p))
return p->data[p->top];
return -1;
}
// 8. 求栈的长度
int LengthSeqStack(seqstack_t *p)
{
return p->top + 1;
}
int main(int argc, char const *argv[])
{
seqstack_t *p = CreateEpSeqStack(5);
for (int i = 1; i <= 6; i++)
PushStack(p, i);
int top = GetTopSeqStack(p);
printf("top value = %d\n",top);
printf("len is %d\n", LengthSeqStack(p));
while (!IsEpSeqStack(p))
{
printf("%d ", PopSeqStack(p));
}
printf("\n");
printf("len is %d\n", LengthSeqStack(p));
free(p->data);
p->data = NULL;
free(p);
p = NULL;
return 0;
}
3.2链式栈
1）逻辑结构：线性结构
2）存储结构：链式存储
3）操作：入栈、出栈
linkstack.c
#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct linkstack
{
datatype data; // 数据域
struct linkstack *next; // 指针域
} linkstack_t;
// 1.创建一个空的栈
void CreateEpLinkStack(linkstack_t **ptop)
{
*ptop = NULL; // 主函数中top = NULL;
}
// 2.入栈 data是入栈的数据
// 参数上之所以采用二级指针，因为我们要随着入栈添加新的节点作为头，top需要永远指向当前链表的头，
// 那么修改main函数中的top，我们采用地址传递
int PushLinkStack(linkstack_t **ptop, datatype data)
{
// 1.创建一个新节点，并初始化
linkstack_t *pnew = (linkstack_t *)malloc(sizeof(linkstack_t));
if (pnew == NULL)
{
perror("PushLinkStack err");
return -1;
}
pnew->data = data;
pnew->next = NULL;
// 2.将新节点头插到无头单向链表中
pnew->next = *ptop;
// 3.移动栈针，栈针top永远只向无头单向链表的第一个节点
*ptop = pnew;
return 0;
}
// 3.判断栈是否为空
int IsEpLinkStack(linkstack_t *top)
{
return top == NULL;
}
// 4.出栈
datatype PopLinkStack(linkstack_t **ptop)
{
// 1.容错判断
if (IsEpLinkStack(*ptop))
{
perror("IsEpLinkStack");
return -1;
}
// 2.定义pdel指向被删除节点
linkstack_t *pdel = *ptop;
// 3.定义一个变量temp保存出栈数据
datatype temp = pdel->data;
// 4.移动栈针(跨过被删除节点)
*ptop = (*ptop)->next;
// 5.释放被删除节点
free(pdel);
pdel = NULL;
return temp;
}
// 5.清空栈
void ClearLinkStack(linkstack_t **ptop) // 用二级指针，是因为清空后需要将main函数中的top变为NULL
{
while (!IsEpLinkStack(*ptop))
PopLinkStack(ptop);
}
// 6.求栈的长度
int LengthLinkStack(linkstack_t *top) // 用一级指针，是因为我只是求长度，不需要修改main函数中top指针的指向
{
int len = 0;
// top相当于无头单向链表的头指针，求长度，遍历无头单向链表
while (top != NULL)
{
len++;
top = top->next;
}
return len;
}
// 7.获取栈顶数据,不是出栈,不需要移动main函数中的top，所以用一级指针
datatype GetTopLinkStack(linkstack_t *top)
{
if (!IsEpLinkStack(top))
return top->data;
return -1;
}
int main(int argc, char const *argv[])
{
linkstack_t *top; //
CreateEpLinkStack(&top);
for (int i = 1; i <= 5; i++)
PushLinkStack(&top, i);
printf("top value is %d\n", GetTopLinkStack(top));
printf("len is %d\n", LengthLinkStack(top));
while (!IsEpLinkStack(top))
{
printf("%d ", PopLinkStack(&top));
}
printf("\n");
return 0;
}
总结：
顺序栈和链式栈的区别是什么？
(1)存储结构不同，顺序栈相当于数组，连续的，链式栈 链表非连续的
(2)顺序栈的长度受限制，而链栈不会
- 顺序表和链表的相同点和不同点有哪些？
相同点： 都是线性表 逻辑结构：线性结构 一对一
不同点：
(1)顺序表存储结构是顺序存储，内存当中存储不连续的链表是链式存储，通过指针将节点联系到一起，内存上存储不连续
(2)顺序表(数组)长度固定，链表不固定
(3)顺序表查找方便，但是插入和删除麻烦，链表插入和删除方便，但是查找麻烦
2.线性表的特征是什么？
线性表： 顺序表 链表 栈(顺序栈和链式栈) 队列(顺序队列也叫循环队列和链式队列)
线性表的特征：一对一，每个节点最多有一个前驱和一个后继（首尾节点除外）
4.队列
1 什么是队列？
只允许在两端进行插入和删除操作的线性表，在队尾插入，在队头删除 插入的一端，被称为"队尾"，删除的一端被称为"队头"
在队列操作过程中，为了提高效率，以调整指针代替队列元素的移动，并将数组作为循环队列的操作空间。
2 队列的特点
先进先出 FIFO first in first out
后进后出 LILO last
4.1循环队列（顺序队列）
1）逻辑结构：线性结构
2）存储结构：顺序存储
3）操作：增删改查
#define N 5
typedef int datatype;
typedef struct
{
datatype data[N];
int rear; //后面，队尾
int front; //前面，对头
}sequeue_t；//sequence 顺序 queue队列
1）创建一个空的队列
2)入列
3）求长度
sequeue.c
#include <stdio.h>
#include <stdlib.h>
#define N 5
typedef int datatype;
typedef struct
{
datatype data[N]; // 循环队列的数组
int rear; // 存数据端 rear 后面
int front; // 取数据端 front 前面
} sequeue_t;
// 1.创建一个空的队列
sequeue_t *CreateEmptySequeue()
{
// 1.开辟一个结构体大小的空间
sequeue_t *p = (sequeue_t *)malloc(sizeof(sequeue_t));
if (p == NULL)
{
perror("CreateEmptySequeue err");
return NULL;
}
// 2.初始化
p->rear = p->front = 0; // 数组下标
return p;
}
// 3.判断队列是否为满
int IsFullSequeue(sequeue_t *p)
{
// 思想上，舍去数组上的一个存储位置,用于判断队列是否为满
// 判断rear的下一个位置是否等于front
return (p->rear + 1) % N == p->front;
}
// 2.入列 data代表入列的数据
int InSequeue(sequeue_t *p, datatype data)
{
// 1.判满
if (IsFullSequeue(p))
{
printf("IsFullSequeue\n");
return -1;
}
// 2.将数据入列
p->data[p->rear] = data;
// 3.移动队尾
p->rear = (p->rear + 1) % N;
return 0;
}
// 4.判断队列是否为空
int IsEmptySequeue(sequeue_t *p)
{
return p->rear == p->front;
}
// 5.出列
datatype OutSequeue(sequeue_t *p)
{
// 1.判空
if (IsEmptySequeue(p))
{
printf("IsEmptySequeue\n");
return -1;
}
// 2.出列
// 1）取出数据
datatype temp = p->data[p->front];
// 2）移动队头
p->front = (p->front + 1) % N;
return temp;
}
// 6.求队列的长度
int LengthSequeue(sequeue_t *p)
{
// 方法1：
// if(p->rear >= p->front)
// return p->rear-p->front;
// else
// return p->rear-p->front + N;
// 方法2：
return (p->rear - p->front + N) % N;
}
// 7.清空队列函数
void ClearSequeue(sequeue_t *p)
{
p->front = p->rear;
}
int main(int argc, char const *argv[])
{
int i = 1;
sequeue_t *p = CreateEmptySequeue();
for (i; i < 5; i++)
InSequeue(p, i);
printf("len is %d\n", LengthSequeue(p)); // 4
printf("rear is %d front is %d\n", p->rear, p->front); // 4,0
OutSequeue(p); // rear = 4,front = 1
OutSequeue(p); // rear = 4,front = 2
InSequeue(p, 100); // rear = 0,front = 2
printf("rear is %d front is %d\n", p->rear, p->front); // 0,2
printf("len is %d\n", LengthSequeue(p)); // 3
while (!IsEmptySequeue(p))
{
printf("%d ", OutSequeue(p));
}
printf("\n");
free(p);
p = NULL;
return 0;
}
4.2链式队列
1）逻辑结构：线性结构
2）存储结构: 链式存储
typedef int datatype;
typedef struct node
{
datatype data;//数据域
struct node *next;//指针域
}linkqueue_node_t,*linkqueue_list_t;
typedef struct//将队列头指针和尾指针封装到一个结构体里
{
linkqueue_list_t front;//相当于队列的头指针
linkqueue_list_t rear;//相当于队列的尾指针
//有了链表的头指针和尾指针，那么我们就可以操作这个链表
}linkqueue_t;
(1)创建一个空的队列
(2)入列
(3)出列
linkqueue.c
#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node
{
datatype data; // 数据域
struct node *next; // 指针域
} linkqueue_node_t, *linkqueue_list_t;
// linkqueue_list_t p === linkqueue_node_t *
typedef struct // 将队列头指针和尾指针封装到一个结构体里
{
linkqueue_list_t front; // 相当于队列的头指针
linkqueue_list_t rear; // 相当于队列的尾指针
// 有了链表的头指针和尾指针，那么我们就可以操作这个链表
} linkqueue_t;
// 1.创建一个空的队列
linkqueue_t *CreateEmptyLinkQueue()
{
// 1.创建存放头尾指针的空间
linkqueue_t *p = (linkqueue_t *)malloc(sizeof(linkqueue_t));
if (p == NULL)
{
perror("CreateEmptyLinkQueue err");
return NULL;
}
// 2.初始化：头尾指针都指向头节点
p->front = p->rear = (linkqueue_list_t)malloc(sizeof(linkqueue_node_t));
if (p->front == NULL)
{
perror("p->front malloc err");
return NULL;
}
p->front->next = NULL; // 空：头节点指针域为NULL
return p;
}
// 2.入列 data代表入列的数据
int InLinkQueue(linkqueue_t *p, datatype data)
{
// 1.开辟一个节点，存数据
linkqueue_list_t pnew = (linkqueue_list_t)malloc(sizeof(linkqueue_node_t));
if (pnew == NULL)
{
perror("pnew malloc err");
return -1;
}
pnew->data = data;
pnew->next = NULL;
// 2.将节点入队
p->rear->next = pnew; // 新节点链接到链表的尾
// 3.移动尾指针
p->rear = pnew; // rear移动，始终指向当前链表的尾巴
return 0;
}
// 4.判断队列是否为空
int IsEmptyLinkQueue(linkqueue_t *p)
{
return p->rear == p->front;
}
// 3.出列
datatype OutLinkQueue(linkqueue_t *p)
{
// 1.判空
if (IsEmptyLinkQueue(p))
{
printf("IsEmptyLinkQueue\n");
return -1;
}
// 2.出列数据
// 1）定义pdel指向头节点
linkqueue_list_t pdel = p->front;
// 2）移动头指针
p->front = p->front->next;
// 3）释放头节点
free(pdel);
pdel = NULL;
// 4）出队数据
return p->front->data;
}
// 5.求队列长度的函数
int LengthLinkQueue(linkqueue_t *p)
{
int len = 0;
linkqueue_list_t h = p->front; // 将链表的头指针保存的地址给h,
// 如果直接用front，求长度之后会找不到链表的头，
// 用h的移动代替front的移动
while (h->next != NULL) // 求长度，相当于遍历有头的单向链表
{
len++;
h = h->next;
}
return len;
}
// 6.清空队列
void ClearLinkQueue(linkqueue_t *p)
{
while (!IsEmptyLinkQueue(p))
OutLinkQueue(p);
}
int main(int argc, char const *argv[])
{
linkqueue_t *p = CreateEmptyLinkQueue();
for (int i = 1; i <= 5; i++)
InLinkQueue(p, i);
printf("len is %d\n", LengthLinkQueue(p));
while (!IsEmptyLinkQueue(p))
printf("%d ", OutLinkQueue(p));
printf("\n");
free(p->front);
p->front = p->rear = NULL;
free(p);
p = NULL;
return 0;
}