线性表-2 单链表 – ShinJiのBlog

一：实现单链表各种基本运算的算法。

#include<stdio.h>
#include<malloc.h>
typedef char ElemType;
typedef struct LNode
{
	ElemType data;
	struct LNode* next;			//指向后继结点
}LinkNode;						//声明单链表结点类型
void CreateListF(LinkNode*& L, ElemType a[], int n)		//头插法
{
	LinkNode* s;
	L = (LinkNode*)malloc(sizeof(LinkNode));		//创建头结点
	L->next = NULL;
	for (int i = 0; i < n; i++)
	{
		s = (LinkNode*)malloc(sizeof(LinkNode));	//创建新结点s
		s->data = a[i];
		s->next = L->next;		//将结点s插入原结点之前，头结点之后
		L->next = s;
	}
}
void CreateListR(LinkNode*& L, ElemType a[], int n)		//尾插法
{
	LinkNode* s, * r;
	L = (LinkNode*)malloc(sizeof(LinkNode));		//创建头结点
	L->next = NULL;
	r = L;							//r始终指向尾结点，开始时指向头结点
	for (int i = 0; i < n; i++)
	{
		s = (LinkNode*)malloc(sizeof(LinkNode));	//创建新结点s
		s->data = a[i];
		r->next = s;
		r = s;
	}
	r->next = NULL;					//尾结点的next域置为NULL
}
void InitList(LinkNode*& L)			//初始化线性表
{
	L = (LinkNode*)malloc(sizeof(LinkNode));		//创建头结点
	L->next = NULL;					//将单链表置为空表
}
void DestroyList(LinkNode*& L)		//销毁线性表
{
	LinkNode* pre = L, * p = pre->next;
	while (p != NULL)
	{
		free(p);
		pre = p;					//pre,p同步后移一个结点
		p = pre->next;
	}
	free(pre);			//此时p为NULL，pre指向尾结点，释放它
}
bool ListEmpty(LinkNode* L)			//判断线性表是否为空表
{
	return(L->next == NULL);
}
int ListLength(LinkNode* L)			//求线性表长度
{
	int i = 0;
	LinkNode* p = L;		//p指向头结点，i置为0（即头结点序号为0）
	while (p->next != NULL)
	{
		i++;
		p = p->next;
	}
	return(i);
}
void DispList(LinkNode* L)			//输出线性表
{
	LinkNode* p = L->next;			//p指向首结点
	while (p != NULL)				//p不为NULL，输出p的data域
	{
		printf("%c", p->data);
		p = p->next;				//p移向下一个结点
	}
	printf("\n");
}
bool GetElem(LinkNode* L, int i, ElemType& e)	//求线性表中第i个元素值
{
	int j = 0;
	LinkNode* p = L;		//p指向头结点，j置为0（即头结点序号为0）
	if (i <= 0)
		return false;		//i错误返回false
	while (j < i && p != NULL)		//找第i个结点p
	{
		j++;
		p = p->next;
	}
	if (p == NULL)			//不存在第i个结点，返回false
		return false;
	else                    //存在第i个结点，返回true
	{
		e = p->data;
		return true;
	}
}
int LocateElem(LinkNode* L, ElemType e)		//查找第一个值域为e的元素的序号
{
	int i = 1;
	LinkNode* p = L->next;			//p指向首结点，i置为1（即首结点序号为1）
	while (p != NULL && p->data != e)
	{
		p = p->next;
		i++;
	}
	if (p == NULL)			//不存在值为e的结点，返回0
		return (0);
	else                    //存在值为e的结点，返回逻辑序号1
		return(i);
}
bool ListInsert(LinkNode*& L, int i, ElemType e)	//插入第i个元素
{
	int  j = 0;
	LinkNode* p = L, * s;			//p指向头结点，j置为0（即头结点序号为0）
	if (i <= 0)						//i错误返回false
		return false;
	while (j < i - 1 && p != NULL)	//查找第i-1个结点p
	{
		j++;
		p = p->next;
	}
	if (p == NULL)				 //未找到i-1个结点p，返回false
		return false;
	else                         //找到i-1个结点p，插入新结点并返回true
	{
		s = (LinkNode*)malloc(sizeof(LinkNode));  //创建新结点s，将其data域置为e
		s->data = e;
		s->next = p->next;            //将结点s插入结点p之后
		p->next = s;
		return true;
	}
}
bool ListDelete(LinkNode*& L, int i, ElemType& e)		//删除第i个元素
{
	int j = 0;
	LinkNode* p = L, * q;		//p指向头结点，j置为0（即头结点序号为0）
	if (i <= 0)					//i错误返回false
		return false;
	while (j < i - 1 && p != NULL)   //查找第i-1个结点
	{
		j++;
		p = p->next;
	}
	if (p == NULL)				//未找到i-1个结点，返回false
		return false;
	else                        //找到i-1个结点p
	{
		q = p->next;			//q指向第i个结点
		if (q == NULL)			//若不存在第i个结点，返回false
			return false;
		e = q->data;
		p->next = q->next;		//从单链表中删除q结点
		free(q);				//释放q结点
		return true;			//返回true表示成功删除第i个结点
	}
}
int main()
{
	LinkNode* h;
	ElemType e;
	printf("单链表的基本运算如下:\n");
	printf("  (1)初始化单链表h\n");
	InitList(h);
	printf("  (2)依次采用尾插法插入a,b,c,d,e元素\n");
	ListInsert(h, 1, 'a');
	ListInsert(h, 2, 'b');
	ListInsert(h, 3, 'c');
	ListInsert(h, 4, 'd');
	ListInsert(h, 5, 'e');
	printf("  (3)输出单链表h:");
	DispList(h);
	printf("  (4)单链表h长度:%d\n", ListLength(h));
	printf("  (5)单链表h为%s\n", (ListEmpty(h) ? "空" : "非空"));
	GetElem(h, 3, e);
	printf("  (6)单链表h的第3个元素:%c\n", e);
	printf("  (7)元素a的位置:%d\n", LocateElem(h, 'a'));
	printf("  (8)在第4个元素位置上插入f元素\n");
	ListInsert(h, 4, 'f');
	printf("  (9)输出单链表h:");
	DispList(h);
	printf("  (10)删除h的第3个元素\n");
	ListDelete(h, 3, e);
	printf("  (11)输出单链表h:");
	DispList(h);
	printf("  (12)释放单链表h\n");
	DestroyList(h);
	return 1;
}

自己跟着敲一遍确实能理解一些了。

二：将单链表按基准划分。

#include<stdio.h>
#include<string.h>
#include<malloc.h>
typedef char ElemType;
typedef struct LNode
{
	ElemType data;
	struct LNode* next;		//指向后继结点
} LinkNode;		 			//单链表结点类型
void CreateListR(LinkNode*& L, ElemType a[], int n)//尾插法建立单链表
{
	LinkNode* s, * r;
	L = (LinkNode*)malloc(sizeof(LinkNode));  	//创建头结点
	L->next = NULL;
	r = L;						//r始终指向尾结点,开始时指向头结点
	for (int i = 0; i < n; i++)
	{
		s = (LinkNode*)malloc(sizeof(LinkNode));//创建新结点s
		s->data = a[i];
		r->next = s;				//将结点s插入r结点之后
		r = s;
	}
	r->next = NULL;				//尾结点next域置为NULL
}
void DispList(LinkNode* L)	//输出线性表
{
	LinkNode* p = L->next;	//p指向首结点
	while (p != NULL)			//p不为NULL,输出p结点的data域
	{
		printf("%c ", p->data);
		p = p->next;			//p移向下一个结点
	}
	printf("\n");
}
void DestroyList(LinkNode*& L)	//销毁线性表
{
	LinkNode* pre = L, * p = pre->next;
	while (p != NULL)
	{
		free(pre);
		pre = p;					//pre、p同步后移一个结点					
		p = pre->next;
	}
	free(pre);					//此时p为NULL,pre指向尾结点,释放它
}
void Split1(LinkNode*& L)			//解法1：将L中所有结点按首结点值进行划分
{
	LinkNode* pre, * p, * q;
	if (L->next == NULL || L->next->next == NULL)
		return;						//单链表L为空或者只有一个结点时返回 
	int x = L->next->data;			//取首结点值x 
	pre = L->next;					//pre指向首结点
	p = pre->next;					//p指向pre结点的后继结点 
	while (p != NULL)
	{
		if (p->data < x)				//结点p的值小于x时 
		{
			pre->next = p->next;		//删除结点p
			p->next = L->next;		//将结点p插入到表头
			L->next = p;
			p = pre->next;			//继续遍历 
		}
		else						//结点p的值大于等于x时 
		{
			pre = p;					//pre,p同步后移 
			p = pre->next;
		}
	}
}
void Split2(LinkNode*& L)			//解法2：将L中所有结点按首结点值进行划分
{
	LinkNode* p = L->next, * r, * L1, * r1;
	if (L->next == NULL || L->next->next == NULL)
		return;						//单链表L为空或者只有一个结点时返回 
	int x = L->next->data;			//取首结点值x 
	r = L;
	L1 = (LinkNode*)malloc(sizeof(LinkNode));	//建立大于等于x的单链表L1
	r1 = L1;
	while (p != NULL)
	{
		if (p->data < x)			//若p结点值小于x
		{
			r->next = p; r = p;
			p = p->next;
		}
		else
		{
			r1->next = p; r1 = p;
			p = p->next;
		}
	}
	r1->next = NULL;
	r->next = L1->next;			//L和L1连接 
	free(L1);
}

int main()
{
	LinkNode* L;
	ElemType a[] = "daxgdchaeb";
	int n = strlen(a);
	printf("解法1\n");
	CreateListR(L, a, n);
	printf("  L: "); DispList(L);
	printf("  以首结点值进行划分\n");
	Split1(L);
	printf("  L: "); DispList(L);
	DestroyList(L);
	printf("解法2\n");
	CreateListR(L, a, n);
	printf("  L: "); DispList(L);
	printf("  以首结点值进行划分\n");
	Split2(L);
	printf("  L: "); DispList(L);
	DestroyList(L);
	return 1;
}

看不懂捏

三：将两个单链表合并为一个单链表。

//单链表运算算法
#include <stdio.h>
#include <malloc.h>
typedef char ElemType;
typedef struct LNode
{
	ElemType data;
	struct LNode* next;		//指向后继结点
} LinkNode;		 			//单链表结点类型
void CreateListR(LinkNode*& L, ElemType a[], int n)
//尾插法建立单链表
{
	LinkNode* s, * r;
	L = (LinkNode*)malloc(sizeof(LinkNode));  	//创建头结点
	L->next = NULL;
	r = L;						//r始终指向尾结点,开始时指向头结点
	for (int i = 0; i < n; i++)
	{
		s = (LinkNode*)malloc(sizeof(LinkNode));//创建新结点s
		s->data = a[i];
		r->next = s;				//将结点s插入r结点之后
		r = s;
	}
	r->next = NULL;				//尾结点next域置为NULL
}
void Merge(LinkNode* L1, LinkNode* L2, LinkNode*& L3) //L1和L2合并产生L3
{
	LinkNode* p = L1->next, * q = L2->next, * r;
	L3 = L1;
	r = L3;				//r指向新建单链表L3的尾结点
	free(L2);			//释放L2的头结点
	while (p != NULL && q != NULL)
	{
		r->next = p; r = p; p = p->next;
		r->next = q; r = q; q = q->next;
	}
	r->next = NULL;
	if (q != NULL) p = q;
	r->next = p;
}
void DispList(LinkNode* L)	//输出线性表
{
	LinkNode* p = L->next;	//p指向首结点
	while (p != NULL)			//p不为NULL,输出p结点的data域
	{
		printf("%c ", p->data);
		p = p->next;			//p移向下一个结点
	}
	printf("\n");
}
void DestroyList(LinkNode*& L)	//销毁线性表
{
	LinkNode* pre = L, * p = pre->next;
	while (p != NULL)
	{
		free(pre);
		pre = p;					//pre、p同步后移一个结点					
		p = pre->next;
	}
	free(pre);					//此时p为NULL,pre指向尾结点,释放它
}
int main()
{
	LinkNode* L1, * L2, * L3;
	ElemType a[] = "abcdefgh";
	int n = 8;
	CreateListR(L1, a, n);
	printf("L1:"); DispList(L1);

	ElemType b[] = "12345";
	n = 5;
	CreateListR(L2, b, n);
	printf("L2:"); DispList(L2);
	printf("L1和L2合并产生L3\n");
	Merge(L1, L2, L3);
	printf("L3:"); DispList(L3);
	DestroyList(L3);
	return 1;
}

四：删除单链表给定的节点运算。

有一带头结点的单链表L，假设元素类型是int，单链表表现有9个元素，分别是3，8，2，7，1，5，2，4，6.设计一个尽可能高效的算法，完成以下功能（可以参考，但不调用linklist.cpp文件）

（1）建立单链表L，在控制台显示单链表表L的所有元素

（2）查找单链表，删除结点值为2的结点，在控制台显示输出删除后的所有结点

#include <stdio.h>
#include <malloc.h>
typedef int ElemType;
typedef struct LNode
{
	ElemType data;
	struct LNode* next;		//指向后继结点
} LinkNode;		 			//单链表结点类型
void CreateListR(LinkNode*& L, ElemType a[], int n)  //尾插法建立单链表
{
	LinkNode* s, * r;
	L = (LinkNode*)malloc(sizeof(LinkNode));  	//创建头结点
	L->next = NULL;
	r = L;						//r始终指向尾结点,开始时指向头结点
	for (int i = 0; i < n; i++)
	{
		s = (LinkNode*)malloc(sizeof(LinkNode));//创建新结点s
		s->data = a[i];
		r->next = s;				//将结点s插入r结点之后
		r = s;
	}
	r->next = NULL;				//尾结点next域置为NULL
}
void InitList(LinkNode*& L)		//初始化线性表
{
	L = (LinkNode*)malloc(sizeof(LinkNode));  //创建头结点
	L->next = NULL;				//单链表置为空表
}
void DispList(LinkNode* L)	//输出线性表
{
	LinkNode* p = L->next;	//p指向首结点
	while (p != NULL)			//p不为NULL,输出p结点的data域
	{
		printf("%d ", p->data);
		p = p->next;			//p移向下一个结点
	}
	printf("\n");
}
bool ListDelete(LinkNode*& L, int i, ElemType& e)	//删除第i个元素
{
	int j = 0;
	if (i <= 0) return false;		//i错误返回假
	LinkNode* p = L, * q;			//p指向头结点,j置为0(即头结点的序号为0)
	while (j < i - 1 && p != NULL)	//查找第i-1个结点
	{
		j++;
		p = p->next;
	}
	if (p == NULL)				//未找到第i-1个结点,返回false
		return false;
	else						//找到第i-1个结点p
	{
		q = p->next;				//q指向第i个结点
		if (q == NULL)			//若不存在第i个结点,返回false
			return false;
		e = q->data;
		p->next = q->next;		//从单链表中删除q结点
		free(q);				//释放q结点
		return true;			//返回true表示成功删除第i个结点
	}
}
int main()
{
	int a[9] = { 3,8,2,7,1,5,2,4,6 };
	int x;
	LinkNode* L;
	InitList(L);
	CreateListR(L,a,9);
	printf("（1）单链表所有元素为：");
	DispList(L);
	printf("（2）删除值为2的结点后，所有元素：");
	ListDelete(L,3,x);
	ListDelete(L, 6, x);
	DispList(L);
	return 0;
}

五：LeetCode80—删除排序数组中的重复项II。

int removeDuplicates(int* nums, int numsSize) {
    if (numsSize <= 2) {
        return numsSize;
    }
    int slow = 2, fast = 2;
    while (fast < numsSize) {
        if (nums[slow - 2] != nums[fast]) {
            nums[slow] = nums[fast];
            ++slow;
        }
        ++fast;
    }
    return slow;
}

六：LeetCode24—两两交换链表中的结点。

struct ListNode* swapPairs(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode* newHead = head->next;
    head->next = swapPairs(newHead->next);
    newHead->next = head;
    return newHead;
}

代码来自力扣官方

七：删除单链表元素最大的节点运算。

有一带头结点的单链表L，假设元素类型是int，单链表表现有10个元素，分别是31，46，82，17，61，35，22，14，46，25.设计一个尽可能高效的算法，先建立该单链表，在控制台输出显示结点排列。然后删除该单链表中最大的元素结点，并在控制台输出显示删除后的结点排列（可以参考，但不调用linklist.cpp文件）

#include <stdio.h>
#include <malloc.h>
typedef int ElemType;
typedef struct LNode
{
	ElemType data;
	struct LNode* next;		//指向后继结点
} LinkNode;		 			//单链表结点类型
void CreateListR(LinkNode*& L, ElemType a[], int n)  //尾插法建立单链表
{
	LinkNode* s, * r;
	L = (LinkNode*)malloc(sizeof(LinkNode));  	//创建头结点
	L->next = NULL;
	r = L;						//r始终指向尾结点,开始时指向头结点
	for (int i = 0; i < n; i++)
	{
		s = (LinkNode*)malloc(sizeof(LinkNode));//创建新结点s
		s->data = a[i];
		r->next = s;				//将结点s插入r结点之后
		r = s;
	}
	r->next = NULL;				//尾结点next域置为NULL
}
void InitList(LinkNode*& L)		//初始化线性表
{
	L = (LinkNode*)malloc(sizeof(LinkNode));  //创建头结点
	L->next = NULL;				//单链表置为空表
}
void DispList(LinkNode* L)	//输出线性表
{
	LinkNode* p = L->next;	//p指向首结点
	while (p != NULL)			//p不为NULL,输出p结点的data域
	{
		printf("%d ", p->data);
		p = p->next;			//p移向下一个结点
	}
	printf("\n");
}
bool ListDelete(LinkNode*& L, int i, ElemType& e)	//删除第i个元素
{
	int j = 0;
	if (i <= 0) return false;		//i错误返回假
	LinkNode* p = L, * q;			//p指向头结点,j置为0(即头结点的序号为0)
	while (j < i - 1 && p != NULL)	//查找第i-1个结点
	{
		j++;
		p = p->next;
	}
	if (p == NULL)				//未找到第i-1个结点,返回false
		return false;
	else						//找到第i-1个结点p
	{
		q = p->next;				//q指向第i个结点
		if (q == NULL)			//若不存在第i个结点,返回false
			return false;
		e = q->data;
		p->next = q->next;		//从单链表中删除q结点
		free(q);				//释放q结点
		return true;			//返回true表示成功删除第i个结点
	}
}
void delmaxnode(LinkNode*& L)
{
	LinkNode* p = L->next, * pre = L, * maxp = p, * maxpre = pre;
	while (p != NULL)
	{
		if (maxp->data < p->data)
		{
			maxp = p;
			maxpre = pre;
		}
		pre = p;
		p = p->next;
	}
	maxpre->next = maxp->next;
	free(maxp);
}
int main()
{
	int a[10] = {31,46,82,17,61,35,22,14,46,25};

	int x;
	LinkNode* L;
	InitList(L);
	CreateListR(L,a,9);
	printf("（1）单链表所有元素为：");
	DispList(L);
	printf("（2）删除值最大的元素结点后的所有元素：");
	delmaxnode(L);
	DispList(L);
	return 0;
}

发送评论 编辑评论

发送评论编辑评论