c语言建立线性表(顺序储存,链式储存,循环,双向)全

2021年9月2日 7点热度 0条评论 来源: 落春只在无意间

c语言建立线性表

顺序储存

储存结构

采用的是用内存动态分配方式定义线性表的顺序储存结构

#define LIST_MAX_SIZE 100 //线性表的最大长度
#define LISTINCREMENT 10 //线性表一次增加的量

typedef struct { 
	int* elem; //指向存放线性表数据元素的基地址
	int length; //线性表当前长度(当前存储的元素个数)
	int listsize; // 当前分配的存储容量
}SQList;

初始化(建立)顺序表

操作步骤:

  1. 申请一片连续的空间,并将其地址空间赋给elem指针变量。
  2. 开始是length 值为0.
  3. 对listsize 赋初值,其值是申请空间的最大容量。
//创建一个线性表 
//注意点是:如果无法分配空间,打印提示,并直接返回
void CreateList(SQList &L)
{ 
	L.elem = (int *)malloc(LIST_MAX_SIZE * sizeof(int));
	if (!L.elem) { 
		printf("分配地址出错\n");
		return;
	}
	L.length = 0;
	L.listsize = LIST_MAX_SIZE;
}

//求线性表中的元素个数
int ListLength(SQList L) { 
	return L.length;
}

查找操作

一、按值查找,找到返回对应的下标

一、按值查找,找到返回对应的下标,没有则返回-1。如果有多个返回第一个的位置
条件:1、线性表存在;2、线性表中有元素

算法:在条件满足的情况下,遍历一遍,如果下标在i~length之间就返回下标

int ListLocate(SQList L, int e) { 
	if (!L.elem ) { 
		printf("线性表没有初始化\n");
		return -1;
	}
	if (L.length == 0) { 
		printf("线性表中没有元素\n");
		return -1;
	}
	int i = 1;
	//下标是从1开始存储元素的
	while (i <= L.length && e != L.elem[i])
		i++;
	if (i <= L.length) { 
		printf("元素已经找到\n");
		return i;
	}
	else { 
		printf("线性表中没有该元素\n");
		return -1;
	}
}

二、按照下标返回元素

条件:1、线性表存在;2、下表没有越界

int GetList(SQList L,int i) { 
	if (!L.elem) { 
		printf("线性表没有初始化\n");
		return -1;
	}
	if (i<1 || i>L.length) { 
		printf("数组下标越界\n");
		return -1;
	}
	return L.elem[i];
}

插入操作

插入步骤,在后边一定要将 length 加1

一、在线性表尾部添加元素

条件:线性表存在

在条件满足情况下:L.elem[++L.length] = val; 表示在尾部添加元素

void ListPush(SQList& L,int val) { 
	if (!L.elem) { 
		printf("线性表没有初始化\n");
		return ;
	}
	if (L.length == L.listsize)//当前存储空间已经满了,增加分量
	{ 
		//在原来基础上扩大
		int* newbase = (int*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(int));
		if (!newbase) { 
			printf("分配空间错误\n");
			return;
		}
		L.elem = newbase; //获得新基址
		L.listsize += LISTINCREMENT;//更新容量
	}
	//在尾部插入
	L.elem[++L.length] = val;
}

二、在位置i处插入元素

步骤:

  1. 将位置i以后的元素后移一个位置。
  2. 在i处插入值
void ListInsert(SQList& L, int i, int val) { 
	if (!L.elem) { 
		printf("线性表没有初始化\n");
		return;
	}
	if (L.length == L.listsize)//当前存储空间已经满了,增加分量
	{ 
		//在原来基础上扩大
		int* newbase = (int*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(int));
		if (!newbase) { 
			printf("分配空间错误\n");
			return;
		}
		L.elem = newbase; //获得新基址
		L.listsize += LISTINCREMENT;//更新容量
	}
	for (int j = L.length; j >= i; --j) { 
		L.elem[j + 1] = L.elem[j]; //i后面的元素后移
	}
	//插入元素
	L.elem[i] = val;
	L.length++;
}

三、顺序表(有序)插入,(如都是由小到大)

基本思路是:

  1. 先找到值val插入的位置。

int pos = L.length;
	while (pos > 0 && val < L.elem[pos])
		pos--;
	//这个循坏结束后,POS对应位置元素是小于等于val的,所以可以将val插到其后边
for (int i = L.length; i >= pos+1; i--)
		L.elem[i + 1] = L.elem[i];
	//在pos后边插入
	L.elem[pos + 1] = val; 
  1. 然后将该位置以后到结尾的元素依次向后移到一位,然后在空出的位置插入val

void ListInsertorder(SQList& L, int val) { 
	if (!L.elem) { 
		printf("线性表没有初始化\n");
		return;
	}
	if (L.length == L.listsize)//当前存储空间已经满了,增加分量
	{ 
		//在原来基础上扩大
		int* newbase = (int*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(int));
		if (!newbase) { 
			printf("分配空间错误\n");
			return;
		}
		L.elem = newbase; //获得新基址
		L.listsize += LISTINCREMENT;//更新容量
	}
	//找到要插入的位置
	int pos = L.length;
	while (pos > 0 && val < L.elem[pos])
		pos--;
	//这个循坏结束后,POS对应位置元素是小于等于val的,所以可以将val插到其后边
	for (int i = L.length; i >= pos+1; i--)
		L.elem[i + 1] = L.elem[i];
	//插入
	L.elem[pos + 1] = val;
	L.length++;
}

删除操作

插入步骤,在后边一定要将 length 减1

一、删除位置i的元素,删除成功后,返回删除的值

两种情况一个是在尾部,另一个是其余位置。 如果是在结尾只要length减一就可以了。
条件:添加 i不能越界

基本步骤:

  1. 判断位置i是否合理
  2. 将位置i处的值取出
  3. 将位置i+1到结尾的元素向前移动一位
  4. length –
int ListDelete(SQList& L, int i) { 
	if (!L.elem) { 
		printf("线性表没有初始化\n");
		return -1;
	}
	if (i<1 || i>L.length) { 
		printf("数组越界\n");
		return -1;
	}
	int val = L.elem[i];
	if (i == L.length)
		L.length--;
	else
	{ 
		//元素往前移
		for (; i < L.length; i++)
			L.elem[i] = L.elem[i + 1];
		L.length--;
	}
	return val;
}

二、删除值为val的第一个元素,没有返回-1

int ListDelete_Sq(SQList& L, int val) { 
	//找到元素在的位置
	int i = 1;
	while (i <= L.length && val != L.elem[i])
		i++;
	//分情况删除
	if (i == L.length)
		L.length--;
	else if (i < L.length) { 
		//元素前移
		for (; i < L.length; ++i)
			L.elem[i] = L.elem[i + 1];
		L.length--;
	}
	else
	{ 
		printf("要删除的数据元素不存在\n");
		return -1;
	}
}

三、在非递减有序的有序表中删除多余的相同元素

基本思路是:

因为是有序的所有相同元素一定是相邻的,所有只要依次比较相邻的元素,删去相同的。

void Listdelete_Sq(SQList& L) { 
	int i = 1;
	while (i < L.length) { 
		if (L.elem[i] != L.elem[i + 1])i++;
		else {  //删除 第i+1个元素
			if (i == L.length - 1)
				L.length--;
			else { 
				for (int j = i + 1; j < L.length; j++)
					L.elem[j] = L.elem[j + 1];//删除第i个元素
				L.length--;//长度减一
			}
		}
	}
}

其余操作

一、将线性表中的所有元素转置

void reverse_Sq(SQList& L) { 
	int i = 1, j = L.length;
	while (i < j)
	{ 
		int temp = L.elem[i];
		L.elem[i] = L.elem[j];
		L.elem[j] = temp;
		i++, j--;
	}
}

二、两个有序的顺序表合并后任然有序

思路是:

取出第一个边和第二个表中最小的数据,两者比较,将最小的插入到第三个表中,重复上述步骤。直到有一个表为空。然后继续将不为空的表中的元素依次插入到第三个表中。

SQList MergeList_Sq(SQList La, SQList Lb) { 
	SQList Lc;
	Lc.listsize = Lc.length = La.length + Lb.length;
	Lc.elem = (int*)malloc(Lc.listsize * sizeof(int));
	int i, j, k;
	i = j = k = 1;
	while (i <= La.length && j <= Lb.length) { 
		if (La.elem[i] <= Lb.elem[j])Lc.elem[k++] = La.elem[i++];
		else
			Lc.elem[k++] = Lb.elem[j++];
	}
	while(i<=La.length)
		Lc.elem[k++] = La.elem[i++];
	while(j<=Lb.length)
		Lc.elem[k++] = Lb.elem[j++];
	return Lc;
}

完整代码

#include<stdio.h>
#include<malloc.h>

#define LIST_MAX_SIZE 100 //线性表的最大长度
#define LISTINCREMENT 10 //线性表一次增加的量

typedef struct { 
	int* elem; //指向存放线性表数据元素的基地址
	int length; //线性表当前长度(当前存储的元素个数)
	int listsize; // 当前分配的存储容量
}SQList;

//创建一个线性表 
//注意点是:如果无法分配空间,打印提示,并直接返回
void CreateList(SQList &L)
{ 
	L.elem = (int *)malloc(LIST_MAX_SIZE * sizeof(int));
	if (!L.elem) { 
		printf("分配地址出错\n");
		return;
	}
	L.length = 0;
	L.listsize = LIST_MAX_SIZE;
}

//求线性表中的元素个数
int ListLength(SQList L) { 
	return L.length;
}

//增加容量 
void increte_List(SQList& L) { 
	//在原来基础上扩大
	int* newbase = (int*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(int));
	if (!newbase) { 
		printf("分配空间错误\n");
		return;
	}
	L.elem = newbase; //获得新基址
	L.listsize += LISTINCREMENT;//更新容量
}

/* 查找操作*/
//一、按值查找,找到返回对应的下标,没有则返回-1。如果有多个返回第一个的位置
//条件:1、线性表存在;2、线性表中有元素

int ListLocate(SQList L, int e) { 
	if (!L.elem ) { 
		printf("线性表没有初始化\n");
		return -1;
	}
	if (L.length == 0) { 
		printf("线性表中没有元素\n");
		return -1;
	}
	int i = 1;
	//下标是从1开始存储元素的
	while (i <= L.length && e != L.elem[i])
		i++;
	if (i <= L.length) { 
		printf("元素已经找到\n");
		return i;
	}
	else { 
		printf("线性表中没有该元素\n");
		return -1;
	}
}

//二、按照下标返回元素
//条件:1、线性表存在;2、下表没有越界

int GetList(SQList L,int i) { 
	if (!L.elem) { 
		printf("线性表没有初始化\n");
		return -1;
	}
	if (i<1 || i>L.length) { 
		printf("数组下标越界\n");
		return -1;
	}
	return L.elem[i];
}

/* 插入元素*/
//一、在线性表尾部添加元素
//条件:线性表存在
void ListPush(SQList& L,int val) { 
	if (!L.elem) { 
		printf("线性表没有初始化\n");
		return ;
	}
	if (L.length == L.listsize)//当前存储空间已经满了,增加分量
		increte_List(L);
	//在尾部插入
	L.elem[++L.length] = val;
}

//二、在位置i处插入元素
void ListInsert(SQList& L, int i, int val) { 
	if (!L.elem) { 
		printf("线性表没有初始化\n");
		return;
	}
	if (L.length == L.listsize)//当前存储空间已经满了,增加分量
		increte_List(L);
	for (int j = L.length; j >= i; --j) { 
		L.elem[j + 1] = L.elem[j]; //i后面的元素后移
	}
	//插入元素
	L.elem[i] = val;
	L.length++;
}

//三、顺序表(有序)插入,(如都是由小到大)
void ListInsertorder(SQList& L, int val) { 
	if (!L.elem) { 
		printf("线性表没有初始化\n");
		return;
	}
	if (L.length == L.listsize)//当前存储空间已经满了,增加分量
		increte_List(L);
	//找到要插入的位置
	int pos = L.length;
	while (pos > 0 && val < L.elem[pos])
		pos--;
	//这个循坏结束后,POS对应位置元素是小于等于val的,所以可以将val插到其后边
	for (int i = L.length; i >= pos+1; i--)
		L.elem[i + 1] = L.elem[i];
	//插入
	L.elem[pos + 1] = val;
	L.length++;
}

/* 删除操作*/
// 一、删除位置i的元素,删除成功后,返回删除的值
// 两种情况一个是在尾部,另一个是其余位置
//添加 i不能越界
int ListDelete(SQList& L, int i) { 
	if (!L.elem) { 
		printf("线性表没有初始化\n");
		return -1;
	}
	if (i<1 || i>L.length) { 
		printf("数组越界\n");
		return -1;
	}
	int val = L.elem[i];
	if (i == L.length)
		L.length--;
	else
	{ 
		//元素往前移
		for (; i < L.length; i++)
			L.elem[i] = L.elem[i + 1];
		L.length--;
	}
	return val;
}

//二、删除值为val的第一个元素,没有返回-1

int ListDelete_Sq(SQList& L, int val) { 
	//找到元素在的位置
	int i = 1;
	while (i <= L.length && val != L.elem[i])
		i++;
	//分情况删除
	if (i == L.length)
		L.length--;
	else if (i < L.length) { 
		//元素前移
		for (; i < L.length; ++i)
			L.elem[i] = L.elem[i + 1];
		L.length--;
	}
	else
	{ 
		printf("要删除的数据元素不存在\n");
		return -1;
	}
}

//三、在非递减有序的有序表中删除多余的相同元素
void Listdelete_Sq(SQList& L) { 
	int i = 1;
	while (i < L.length) { 
		if (L.elem[i] != L.elem[i + 1])i++;
		else {  //删除 第i+1个元素
			if (i == L.length - 1)
				L.length--;
			else { 
				for (int j = i + 1; j < L.length; j++)
					L.elem[j] = L.elem[j + 1];//删除第i个元素
				L.length--;//长度减一
			}
		}
	}
}

/*其余操作*/
//一、将线性表中的所有元素转置

void reverse_Sq(SQList& L) { 
	int i = 1, j = L.length;
	while (i < j)
	{ 
		int temp = L.elem[i];
		L.elem[i] = L.elem[j];
		L.elem[j] = temp;
		i++, j--;
	}
}

//二、两个有序的顺序表合并后任然有序
SQList MergeList_Sq(SQList La, SQList Lb) { 
	SQList Lc;
	Lc.listsize = Lc.length = La.length + Lb.length;
	Lc.elem = (int*)malloc(Lc.listsize * sizeof(int));
	int i, j, k;
	i = j = k = 1;
	while (i <= La.length && j <= Lb.length) { 
		if (La.elem[i] <= Lb.elem[j])Lc.elem[k++] = La.elem[i++];
		else
			Lc.elem[k++] = Lb.elem[j++];
	}
	while(i<=La.length)
		Lc.elem[k++] = La.elem[i++];
	while(j<=Lb.length)
		Lc.elem[k++] = Lb.elem[j++];
	return Lc;
}

void show(SQList L)
{ 
	for (int i = 1; i <= L.length; ++i)
		printf("%d ", L.elem[i]);
	printf("\n");
}

int main()
{ 
	SQList La, Lb,Lc;
	CreateList(La);
	CreateList(Lb);
	for (int i = 1; i <= 5; ++i)
	{ 
		int x;
		scanf_s("%d", &x);
		ListPush(La, x);
	}
	for (int i = 1; i <= 5; ++i)
	{ 
		int x;
		scanf_s("%d", &x);
		ListPush(Lb, x);
	}
	show(La), show(Lb);
	reverse_Sq(Lb);
	show(Lb);
	Lc = MergeList_Sq(La, Lb);
	show(Lc);
	return 0;
}




链式储存

存储结构

typedef struct LNode { 
	int date;
	LNode* next;
}LNode;

建立链表

一、尾插法建立

,需要建立三个指针,一个指向头指针,一个始终指向尾部,一个指向新建立的

基本思路是:

为头节点申请空间后,让s也指向头结点。然后为p申请空间并赋值,将s的下一个指针指向p,然后指针s后移。(即将p赋给s),重复这个步骤

LNode* create_E(int n) { 
	LNode* head, * s,*p;
	head = (LNode *)malloc(sizeof(LNode));
	head->next = NULL;
	s = head;
	while (n--) { 
		p = (LNode*)malloc(sizeof(LNode));
		scanf_s("%d", &p->date);
		s->next = p; //把新节点插入链表的结尾
		s = p; //指针s后移
	}
	s->next = NULL;
	return head;
}

二、头插法建立

核心思路:

在头结点后插入新节点。理解好这句。
我们要在头结点后边插入新节点,要什么做呢?首先是将原本头结点的next放到新建立的节点的next把,然后再讲头结点的next指向p。

//只需要两个指针
LNode* create_H(int n) {   //得到的链表与输入的值相反
	LNode* head, * p;
	head = (LNode*)malloc(sizeof(LNode));
	head->next = NULL;
	while (n--) { 
		p = (LNode*)malloc(sizeof(LNode));
		scanf_s("%d", &p->date);
		p->next = head->next; //在头结点后插入新节点
		head->next = p;
	}
	return head;
}

查找位置i的两种方法

1、在i满足1<=i<=length 的情况下一直往后移动i次就可以了。

LNode* p = head->next;
	int len = GetLength(head);
	if (i > len||i<1) { 
		printf("i值不合理\n");
		return -1;
	}
	while (--i) { 
		p = p->next;
	}

因为在这里 p初值是 head->next 所以只要移动i-1次就到位置i了,所以是while(–i),如果是p初值是 head,则是 i–

2、

LNode* p, * s;
	p = head; //赋值是头结点,不是next
	int j = 0;
	while (p && j < i ) {  //找第i个位置
		p = p->next;
		j++;
	}
	if (!p || j > i) //对应的情况是i超过长度,与i小于0
	{ 
		printf("i不合理\n");
		return;
	}

链表的查找操作

一、在链表中查找第i的节点

//需要检测 i的值是否合理

int GetElem(LNode* head,int i) { 
	LNode* p = head->next;
	int len = GetLength(head);
	if (i > len||i<1) { 
		printf("i值不合理\n");
		return -1;
	}
	while (--i) { 
		p = p->next;
	}
	return p->date;
}

二、在单链表中按值查找第一个与val相等的节点

int LocateElem(LNode* head,int val) { 
	int i = 1;
	LNode* p = head->next;
	if (!p)
	{ 
		printf("当前链表为空\n");
		return -1;
	}
	while (p && p->date != val) { 
		p = p->next;
		i++;
	}
	//printf("位置i为:%d", i);
	if (i > GetLength(head))
	{ 
		printf("当前链表中没有该值\n");
		return -1;
	}
	else
		return i;

}

三、查找与val值相等的节点个数

int findnum(LNode* head,int val) { 
	LNode* p = head->next;
	int num = 0;
	while (p) { 
		if (p->date == val)
			num++;
		p = p->next;
	}
	return num;
}

四、找链表中的最大值与最小值


void find_max_min(LNode* head) { 
	LNode* p = head->next;
	int Max = p->date, Min = p->date;
	while (p) { 
		if (p->date > Max)
			Max = p->date;
		else
			Min = p->date;
		p = p->next;
	}
	printf("最大值是:%d 最小值是:%d\n", Max, Min);
}

插入操作

一、在位置i前插入数据val

void ListInsert_P(LNode* head, int i, int val) { 
	LNode* p, * s;
	p = head; //赋值是头结点,不是next
	int j = 0;
	while (p && j < i - 1) {  //找第i-1个位置
		p = p->next;
		j++;
	}
	if (!p || j > i - 1) //对应的情况是i超过长度,与i小于1
		return;
	else
	{ 
		s = (LNode*)malloc(sizeof(LNode));
		s->date = val;
		s->next = p->next;
		p->next = s;
	}
}

二、在位置i后插入数据val

//第0个就是在头结点后边
void ListInsert_N(LNode* head, int i, int val) { 
	LNode* p, * s;
	p = head; //赋值是头结点,不是next
	int j = 0;
	while (p && j < i ) {  //找第i个位置
		p = p->next;
		j++;
	}
	//printf("j: %d\n", j);
	if (!p || j > i) //对应的情况是i超过长度,与i小于0
	{ 
		printf("i不合理\n");
		return;
	}
	else
	{ 
		s = (LNode*)malloc(sizeof(LNode));
		s->date = val;
		s->next = p->next;
		p->next = s;
	}
}

三、在第一个值为val的后边添加值val1

void ListInsert_V(LNode* head, int val, int val1) { 
	int i = LocateElem(head, val);//找到值val对应的位置
	//printf("位置i为:%d", i);
	ListInsert_N(head, i, val1);
}

删除操作

int ListDelete(LNode* head, int i) { 
	LNode* p, * q;
	int val;
	p = head;
	int j = 0;
	while (p->next && j > i - 1) { 
		p = p->next;
		j++;
	}
	if (!p->next || j > i - 1)
		return -1;
	else
	{ 
		q = p->next;
		p->next = q->next;
		val = q->date;
		free(q);//释放删除的节点
	}
	return val;
}

链表逆置

void List_reverse(LNode* head) { 
	LNode* p, * pre,*temp;
	pre = NULL;
	p = head->next;
	while (p) { 
		temp = p->next;
		p->next = pre;
		pre = p;
		p = temp;
	}
	head->next = pre; //pre指向的是原来链表的终点
}

合并两个有序表

LNode* MargeList(LNode* head1, LNode* head2) { 
	LNode* Lc,*La,*Lb,*head;
	head = (LNode*)malloc(sizeof(LNode));
	head->next = NULL;
	Lc = head;
	La = head1->next;
	Lb = head2->next;
	while (La && Lb) { 
		if (La->date <= Lb->date)
		{ 
			Lc->next = La;
			Lc = La;  //记得后移
			La = La->next;

		}
		else
		{ 
			Lc->next = Lb;
			Lc = Lb;
			Lb = Lb->next;
		}
	}
	Lc->next = La ? La : Lb;
	return head;
}

完整代码

#include<stdio.h>
#include<malloc.h>


typedef struct LNode { 
	int date;
	LNode* next;
}LNode;

/* 建立链表*/
//一、尾插法建立,需要建立三个指针
//一个指向头指针,一个始终指向尾部,一个指向新建立的
LNode* create_E(int n) { 
	LNode* head, * s,*p;
	head = (LNode *)malloc(sizeof(LNode));
	head->next = NULL;
	s = head;
	while (n--) { 
		p = (LNode*)malloc(sizeof(LNode));
		scanf_s("%d", &p->date);
		s->next = p; //把新节点插入链表的结尾
		s = p; //指针s后移
	}
	s->next = NULL;
	return head;
}

//二、头插法建立 
//只需要两个指针
LNode* create_H(int n) {   //得到的链表与输入的值相反
	LNode* head, * p;
	head = (LNode*)malloc(sizeof(LNode));
	head->next = NULL;
	while (n--) { 
		p = (LNode*)malloc(sizeof(LNode));
		scanf_s("%d", &p->date);
		p->next = head->next; //在头结点后插入新节点
		head->next = p;
	}
	return head;
}

/*求链表的长度*/
int GetLength(LNode* head) { 
	LNode* p = head->next;
	int len = 0;
	while (p) { 
		p = p->next;
		len++;
	}
	return len;
}


/*链表的查找*/
//一、在链表中查找第i的节点
//需要检测 i的值是否合理

int GetElem(LNode* head,int i) { 
	LNode* p = head->next;
	int len = GetLength(head);
	if (i > len||i<1) { 
		printf("i值不合理\n");
		return -1;
	}
	while (--i) { 
		p = p->next;
	}
	return p->date;
}

//二、在单链表中按值查找第一个与val相等的节点
int LocateElem(LNode* head,int val) { 
	int i = 1;
	LNode* p = head->next;
	if (!p)
	{ 
		printf("当前链表为空\n");
		return -1;
	}
	while (p && p->date != val) { 
		p = p->next;
		i++;
	}
	//printf("位置i为:%d", i);
	if (i > GetLength(head))
	{ 
		printf("当前链表中没有该值\n");
		return -1;
	}
	else
		return i;

}
// 三、查找与val值相等的节点个数
int findnum(LNode* head,int val) { 
	LNode* p = head->next;
	int num = 0;
	while (p) { 
		if (p->date == val)
			num++;
		p = p->next;
	}
	return num;
}

//四、找链表中的最大值与最小值
void find_max_min(LNode* head) { 
	LNode* p = head->next;
	int Max = p->date, Min = p->date;
	while (p) { 
		if (p->date > Max)
			Max = p->date;
		else
			Min = p->date;
		p = p->next;
	}
	printf("最大值是:%d 最小值是:%d\n", Max, Min);
}

/*插入操作*/
//一、在位置i前插入数据val

void ListInsert_P(LNode* head, int i, int val) { 
	LNode* p, * s;
	p = head; //赋值是头结点,不是next
	int j = 0;
	while (p && j < i - 1) {  //找第i-1个位置
		p = p->next;
		j++;
	}
	if (!p || j > i - 1) //对应的情况是i超过长度,与i小于1
		return;
	else
	{ 
		s = (LNode*)malloc(sizeof(LNode));
		s->date = val;
		s->next = p->next;
		p->next = s;
	}
}

//二、在位置i后插入数据val
//第0个就是在头结点后边
void ListInsert_N(LNode* head, int i, int val) { 
	LNode* p, * s;
	p = head; //赋值是头结点,不是next
	int j = 0;
	while (p && j < i ) {  //找第i个位置
		p = p->next;
		j++;
	}
	//printf("j: %d\n", j);
	if (!p || j > i) //对应的情况是i超过长度,与i小于0
	{ 
		printf("i不合理\n");
		return;
	}
	else
	{ 
		s = (LNode*)malloc(sizeof(LNode));
		s->date = val;
		s->next = p->next;
		p->next = s;
	}
}

//三、在第一个值为val的后边添加值val1
void ListInsert_V(LNode* head, int val, int val1) { 
	int i = LocateElem(head, val);//找到值val对应的位置
	//printf("位置i为:%d", i);
	ListInsert_N(head, i, val1);
}

/*删除操作*/
//一、删除位置i的节点,并返回删除节点的值

int ListDelete(LNode* head, int i) { 
	LNode* p, * q;
	int val;
	p = head;
	int j = 0;
	while (p->next && j > i - 1) { 
		p = p->next;
		j++;
	}
	if (!p->next || j > i - 1)
		return -1;
	else
	{ 
		q = p->next;
		p->next = q->next;
		val = q->date;
		free(q);//释放删除的节点
	}
	return val;
}

/*链表逆置*/
void List_reverse(LNode* head) { 
	LNode* p, * pre,*temp;
	pre = NULL;
	p = head->next;
	while (p) { 
		temp = p->next;
		p->next = pre;
		pre = p;
		p = temp;
	}
	head->next = pre; //pre指向的是原来链表的终点
}

/*合并两个有序表*/
LNode* MargeList(LNode* head1, LNode* head2) { 
	LNode* Lc,*La,*Lb,*head;
	head = (LNode*)malloc(sizeof(LNode));
	head->next = NULL;
	Lc = head;
	La = head1->next;
	Lb = head2->next;
	while (La && Lb) { 
		if (La->date <= Lb->date)
		{ 
			Lc->next = La;
			Lc = La;  //记得后移
			La = La->next;

		}
		else
		{ 
			Lc->next = Lb;
			Lc = Lb;
			Lb = Lb->next;
		}
	}
	Lc->next = La ? La : Lb;
	return head;
}

void show(LNode* head) { 
	LNode* p = head->next;
	while (p) { 
		printf("%d ", p->date);
		p = p->next;
	}
	printf("\n");
}

int main() { 
	LNode* head1,*head2,*head;
	head1 = create_E(5);
	show(head1);
	/*head2 = create_H(5); show(head2); List_reverse(head2); show(head2); head = MargeList(head1, head2); show(head);*/
	ListInsert_V(head1, 3, 8);
	show(head1);
	ListInsert_P(head1, 3, 47);
	show(head1);
	return 0;
}

循环链表

  • 简单来说就是将原本最后一个结点的指针域由空指针指向头结点。
  • 最后一个结点的语句是:p->next == head
/* 创建循环链表(返回尾指针)*/

LNode* circular(int n) { 
	LNode* head, * s, * p,*tail;
	head = (LNode*)malloc(sizeof(LNode));//为头结点申请空间
	head->next = NULL;
	s = head;
	while (n--) { 
		p = (LNode*)malloc(sizeof(LNode));
		scanf_s("%d", &p->date);
		s->next = p; //把新节点插入链表的结尾
		s = p; //指针s后移
	}
	s->next = head;//建立循环
	tail = s;
	return tail;
}

/*打印循环链表*/
void show_cir(LNode* tail) { 
	LNode* head = tail->next;
	LNode* p = tail->next->next;
	while (p != head) { 
		printf("%d ", p->date);
		p = p->next;
	}
	printf("\n");
}

双向链表

储存结构

/*双向链表*/
typedef struct Node { 
	int date;
	Node* prior;
	Node* next;
}DuLinkList;

建立双向链表

/*建立双向链表*/
DuLinkList* create_DuL(int n) { 
	DuLinkList* head, * p, * s;
	head = (DuLinkList*)malloc(sizeof(DuLinkList));
	head->next = NULL;
	head->prior = NULL;
	s = head;
	while (n--) { 
		p = (DuLinkList*)malloc(sizeof(DuLinkList));
		scanf_s("%d", &p->date);
		s->next = p;
		p->prior = s;
		s = p;
	}
	s->next = NULL;
	return head;
}

插入操作

/*双向链表的插入操作*/
void ListInsert_DuL(DuLinkList* head, int i, int val) { 
	int len = Get_num(head);
	if (i<1 || i>len)
	{ 
		printf("i不合法\n");
		return;
	}
	DuLinkList* p ,*s;
	s = (DuLinkList*)malloc(sizeof(DuLinkList));
	s->date = val;
	p = head;
	while (--i)//i-- 得到的是位置i的结点,
		p = p->next;
	//printf("p = %d\n", p->date);
	//循环结束后p指向的是i的前一个结点
	s->next = p->next;
	p->next->prior = s;
	p->next = s;
	s->prior = p;
}

删除操作


/*双向链表的删除操作*/
int ListDelete_DuL(DuLinkList* head, int i) { 
	int len = Get_num(head);
	if (i<1 || i>len)
	{ 
		printf("i不合法\n");
		return -1;
	}
	DuLinkList* p;
	p = head;
	while (--i)
		p = p->next;
	//printf("p = %d\n", p->date);
	//循环结束后p指向的是i的前一个结点
	p = p->next; //为了简便指向位置i的结点
	int val = p->date;
	p->prior->next = p->next;
	p->next->prior = p->prior;
	free(p);
	return val;
}

其余操作

/*双向链表中结点个数(存有数据的)*/
int Get_num(DuLinkList* head) { 
	DuLinkList* p = head->next;
	int num = 0;
	while (p != NULL) { 
		p = p->next;
		num++;
	}
	//printf("num = %d\n", num);
	return num;
}

void show_DuL(DuLinkList* head) { 
	DuLinkList* p = head->next;
	while (p) { 
		printf("%d ", p->date);
		p = p->next;
	}
	printf("\n");
}

    原文作者:落春只在无意间
    原文地址: https://blog.csdn.net/qq_39838607/article/details/120047147
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。