欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构带头节点单链表与不带头节点单链表的基本操作

程序员文章站 2022-03-15 18:14:44
...

带头节点单链表与不带头节点单链表的基本操作

定义单链表

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode, *LinkList;

带头节点单链表基本操作

头插法建立单链表

LinkList List_HeadInsert(LinkList &L){
	LNode *s;
	int x;
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;
	scanf("%d", &x);
	while (x != 0000){
		s = (LNode *)malloc(sizeof(LNode));
		s->data = x;
		s->next = L->next;
		L->next = s;
		scanf("%d", &x);
	}
	return L;
}

尾插法建立单链表

LinkList List_TailInsert(LinkList &L){
	int x;
	L = (LinkList)malloc(sizeof(LNode));
	LNode *s, *r = L;
	scanf("%d", &x);
	while (x != 0000){
		s = (LinkList)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;
		scanf("%d", &x);
	}
	r->next = NULL;
	return L;
}

按序号查找节点

LNode *GetElem(LinkList L, int i){
	int j = 1;
	LNode *p = L->next;
	if (i == 0)
		return L;
	if (i < 1)
		return NULL;
	while (p&&j < i){
		p = p->next;
		j++;
	}
	return p;
}

插入节点

bool ListInsert(LinkList &L, int i, int e){
	LinkList p, s;
	p = GetElem(L, i-1);
	if (!p || i < 1)
		return false;
	s = (LinkList)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

删除节点

bool ListDelete(LinkList &L, int i, int &e){
	if (i < 1)
		return false;
	LNode *p;
	int j = 0;
	p = L;
	while (p != NULL&&j < i - 1){
		p = p->next;
		j++;
	}
	if (p == NULL)
		return false;
	LNode *q = p->next;
	e = q->data;
	p->next = q->next;
	free(q);
	return true;
}

计算表长

int Length(LinkList L){
	int len = 0;
	LNode *p = L;
	while (p->next != NULL){
		p = p->next;
		len++;
	}
	return len;
}

整数元素链表的逆置

LinkList Revers(LinkList L){
	LNode *p,*s;
	p = (LinkList)malloc(sizeof(LNode));
	p->next = NULL;
	L = L->next;
	while (L!= NULL){
		s = (LinkList)malloc(sizeof(LNode));
		s->data = L->data;
		s->next = p->next;
		p->next = s;
		L = L->next;
	}
	return p;
}

链表的输出

while (L->next != NULL){
	L = L->next;
	printf("%d ", L->data);
}

主函数的测试

int main()
{
	LinkList L,M,N,P;
	List_HeadInsert(L);
	int a, b, c, d, e, f;
	LNode *a1,*b1,*m;
	int len=0;
	M = L;
	N = L;
	P = L;
	len = Length(L);
	while (M->next != NULL){
		M = M->next;
		printf("%d ", M->data);
	}
	printf("\n");
	printf("转置的结果为:");
	m = Revers(L);
	while (m->next != NULL){
		m = m->next;
		printf("%d ", m->data);
	}
	printf("\n");

	printf("输入要查找的节点序号");
	scanf("%d", &a);
	a1 = GetElem(L, a);
	if (a1)
		printf("查找的节点值为:%d\n", a1->data);
	else
		printf("没有找到改节点\n");
	printf("输入要查找的值");
	scanf("%d", &b);
	b1 = LocateElem(L, b);
	if (b1)
		printf("查找的节点值为:%d\n", b1->data);
	else
		printf("没有找到改节点\n");
	printf("输入要插入的位置和值");
	scanf("%d%d", &c,&d);
	if (ListInsert(L, c, d))
		printf("插入成功\n");
	else
		printf("插入失败\n");

	while (N->next != NULL){
		N = N->next;
		printf("%d ", N->data);
	}
	printf("\n");
	printf("输入要删除的位置");
	scanf("%d", &e);
	if (ListDelete(L, e, f))
		printf("删除成功,删除的值为%d\n",f);
	else
		printf("删除失败\n");
	printf("表长为:%d",len);
	return 0;
}

不带头节点单链表基本操作

头插法建立单链表

LinkList List_HeadInsert(LinkList &L){
	int x;
	LNode *p;
	L = (LinkList)malloc(sizeof(LNode));
	scanf("%d", &x);
	L->next = NULL;
	L->data = x;
	scanf("%d", &x);
	while (x != 0000){
		p = (LinkList)malloc(sizeof(LNode));
		p->data = x;
		p->next = L;
		L = p;
		scanf("%d", &x);
	}
	return L;
}

尾插法建立单链表

LinkList List_TailInsert(LinkList &L){
	int x;
	L = (LinkList)malloc(sizeof(LNode));
	scanf("%d", &x);
	LNode *s, *r = L;
	r->data = x;
	scanf("%d", &x);
	while (x != 0000){
		s = (LinkList)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;
		scanf("%d", &x);
	}
	r->next = NULL;
	return L;
}

插入节点

bool ListInsert(LinkList &L, int i, int e){
	if (i < 1)
		return false;
	if (i == 1){
		LNode *s = (LNode *)malloc(sizeof(LNode));
		s->data = e;
		s->next = L;
		L = s;
		return true;
	}
	LNode *p;
	int j = 1;
	p = L;
	while (p != NULL&&j < i - 1){
		p = p->next;
		j++;
	}
	if (p == NULL)
		return false;
	LNode *s = (LinkList)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

删除节点

bool ListDelete(LinkList &L, int i, int &e){
	if (i < 1)
		return false;
	LNode *p;
	p = L;
	if (i == 1){
		e = p->data;
		L = p->next;
		free(p);
		return true;
	}
	int j = 1;
	while (p != NULL&&j < i - 1){
		p = p->next;
		j++;
	}
	if (!p)
		return false;
	if (!p->next)
		return false;
	LNode *q = p->next;
	e = q->data;
	p->next = q->next;
	free(q);
	return true;
}

计算表长

int Length(LinkList L){
	int len = 0;
	LNode *p = L;
	while (p != NULL){
		p = p->next;
		len++;
	}
	return len;
}

主函数的测试

int main(){
	int i,a,e,b;
	LinkList L;
	InitList(L);
	List_TailInsert(L);
	printf("表长为%d\n", Length(L));
	printf("输入要插入的位置和值:\n");
	scanf("%d%d", &i, &a);
	ListInsert(L, i, a);
	printf("输入要删除的位置:\n");
	scanf("%d", &b);
	ListDelete(L, b, e);
	printf("删除的值为:%d\n", e);
	while (L!=NULL){
		printf("%d ", L->data);
		L = L->next;
	}
	printf("\n");
	return 0;
}

以上内容均根据王道数据结构考研复习指导学习所得