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

不带头结点的单链表

程序员文章站 2024-03-21 13:23:04
...

#include<cstdio>
#include<cstdbool>
#include<cstdlib>
#define OK 1
#define ERROR 0

typedef char Elemtype;
typedef struct Node {
	Elemtype data;
	struct Node *next;
}Node, *LinkList;

//初始化
void InitList(LinkList *L)
{

}

//头插法
void CreateFromHead(LinkList *L)
{
	Node *s;
	printf("Creating List From Head:\n");
	char ch = getchar();
	bool isEmpty = true;
	while (ch != '$') {
		s = (Node*)malloc(sizeof(Node));
		s->data = ch;
		s->next = *L;
		*L = s;
		if (isEmpty) {
			(*L)->next = NULL;
			isEmpty = false;
		}
		ch = getchar();
	}
}

//尾插法
void CreateFromTail(LinkList *L)
{
	Node *s, *rear= NULL;
	printf("Creating List From Tail:\n");
	char ch = getchar();
	while (ch != '$')
	{
		s = (Node*)malloc(sizeof(Node));
		s->data = ch;
		if (*L == NULL) {
			*L = s;
			rear = s;
		}
		else {
			rear->next = s;
			rear = s;
		}
		ch = getchar();
	}
	rear->next = NULL;
}

//遍历链表元素然后输出
void Display(LinkList L) {
	Node *p = L;
	printf("The link list is:\n");
	while (p) {
		printf("%c", p->data);
		p = p->next;
	}
	printf("\n");
}

//获取表长
int GetListLength(LinkList L)
{
	int count = 0;
	Node *p = L;
	while (p) {
		count++;
		p = p->next;
	}
	return count;
}


//插入元素
int InsertList(LinkList *L, int i, Elemtype e)
{
	Node *pre = *L, *s;
	if (i <= 0) return ERROR;
	int count = 0;
	if (i == 1) {
		s = (Node*)malloc(sizeof(Node));
		s->data = e;
		s->next = *L;
		*L = s;
		return OK;
	}
	while (pre) {
		count++;
		if (count < i - 1)
			pre = pre->next;
		else
			break;
	}
	if (pre == NULL) {
		printf("插入的位置不合理");
		exit(1);
	}
	s = (Node*)malloc(sizeof(Node));
	s->data = e;
	s->next = pre->next;
	pre->next = s;
	return OK;
}

// 删除元素
int DelList(LinkList *L, int i, Elemtype *e)
{
	if (*L == NULL) {
		printf("空表无法删除");
		exit(1);
	}
	if (i <= 0) return ERROR;
	if (i == 1) {
		Node *temp = *L;
		*e = (*L)->data;//别忘了带回返回值
		*L = (*L)->next;
		free(temp);
		return OK;
	}
	Node *pre = *L;
	int count = 0;
	while (pre->next) {
		count++;
		if (count < i - 1)
			pre = pre->next;
		else
			break;
	}
	if (pre->next == NULL) {
		printf("插入的位置不合理");
		exit(1);
	}
	Node *r = pre->next;
	*e = r->data;
	pre->next = r->next;
	free(r);
	return OK;
}

//合并两个非递减链表至一个大的非递减列表,不借助新的辅助空间
LinkList MergeLinkList(LinkList La, LinkList Lb)
{
	LinkList Lc = NULL;
	Node *pa = La, *pb = Lb, *pc=Lc;
	while (pa && pb) {
		if (pa->data <= pb->data) {
			if (pc == NULL) {
				Lc = pa;
				pc = pa;
			}
			else {
				pc->next = pa;
				pc = pa;
			}
			pa = pa->next;
		}
		else {
			if (pc == NULL) {
				Lc = pb;
				pc = pb;
			}
			else {
				pc->next = pb;
				pc = pb;
			}
			pb = pb->next;
		}
	}
	if (pa)
		pc->next = pa;
	if(pb)
		pc->next = pb;
	return Lc;
}

//合并两个非递减链表至一个大的非递增列表,不借助新的辅助空间
LinkList MergeLinkList2(LinkList La, LinkList Lb)
{
	LinkList Lc=NULL;
	Node *pa = La, *pb = Lb, *temp;
	while (pa && pb) {
		if (pa->data <= pb->data) {
			temp = pa->next;
			if (Lc == NULL) {
				Lc = pa;
				pa->next = NULL;
			}
			else {
				pa->next = Lc;
				Lc = pa;
			}
			pa = temp;
		}
		else {
			temp = pb->next;
			if (Lc == NULL) {
				Lc = pb;
				pb->next = NULL;
			}
			else {
				pb->next = Lc;
				Lc = pb;
			}
			pb = temp;
		}
	}
	while (pa) {
		temp = pa->next;
		pa->next = Lc;
		Lc = pa;
		pa = temp;
	}
	while (pb) {
		temp = pb->next;
		pb->next = Lc;
		Lc = pb;
		pb = temp;
	}
	return Lc;
}

//编写递归算法,删除不带头结点的单链表L中所有值为x的结点
void DelXInList(LinkList *L, Elemtype x, Node **firstPre)
{
	if (*L == NULL) return;
	Node *temp;
	if ((*L)->data == x) {
		if (*firstPre != NULL) {
			temp = *L;//一定要在下一步之前去保存*L的值,因为下一步的(*firstPre)->next其实就是L,所以如果free(*L), 释放了错误的结点空间
			(*firstPre)->next = (*L)->next;
			free(temp);
			*L = (*firstPre)->next;
		}
		else {
			temp = (*L)->next;
			free(*L);
			*L = temp;
		}
		DelXInList(L, x, firstPre);
	}
	else {
		*firstPre = *L;
		 DelXInList(&((*L)->next), x, firstPre);
	}
}

LinkList modifiedHead = NULL;
//编写递归算法,删除不带头结点的单链表L中所有值为x的结点
void DelXInList2(LinkList L, Elemtype x, Node **firstPre)
{

	if (L != NULL) {
		Node *temp;
		if (L->data == x) {
			if (*firstPre != NULL) {
				(*firstPre)->next = L->next;
				free(L);
				L = (*firstPre)->next;
			}
			else {
				temp = L->next;
				free(L);
				L = temp;
				modifiedHead = L;
			}
			DelXInList2(L, x, firstPre);
		}
		else {
			*firstPre = L;
			DelXInList2(L->next, x, firstPre);
		}
	}

}


int main()
{
	LinkList la=NULL, lb=NULL;
	CreateFromHead(&la);// fed$
	getchar();
	CreateFromTail(&lb);//abc$
	Display(la);
	Display(lb);
	//LinkList lc = MergeLinkList(la,lb);
	//Display(lc); 
	LinkList ld = MergeLinkList2(la, lb);
	Display(ld);
	InsertList(&ld, 0, 'H');
	InsertList(&ld, 1, 'H');
	Display(ld);
	InsertList(&ld, 8, '0' );
	Display(ld);
	char ch;
	DelList(&ld, 1, &ch);
	Display(ld);
	printf("The deleted is %c",ch );
//注:两个合并操作不能同时进行,不然就会干扰,因为这里的合并都利用了原有的空间,所以链表结构发生了变化



//用于验证函数删除所有值为X的结点
	LinkList le = NULL;
	CreateFromTail(&le); //  edbbcamtccbciok$
	Node *firstPre = NULL;
	Display(le);
	DelXInList(&le, 'c', &firstPre);
	Display(le);


	firstPre = NULL;
	DelXInList2(le, 'b', &firstPre);
	if(modifiedHead)
		le = modifiedHead;
	Display(le);
	return 0;
}