数据结构——不带头结点的单链表增删查改的C语言实现

1、slist.h

#ifndef _slist_h_
#define _slist_h_

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<memory.h>
#include<vld.h>  
#pragma warning(disable:4996)
#define ElemType int
typedef struct SListNode
{
	ElemType data;
	struct SListNode *next;
}SListNode;
//不带头结点的单链表
typedef SListNode* SList;

void SListInit(SList *phead);
void SListPushBack(SList *phead, ElemType x);
void SListPushFront(SList *phead, ElemType x);
void SListShow(SList *phead);
void SListPopBack(SList *phead);
void SListPopFront(SList *phead);
bool SListInsertPos(SList *phead, SListNode* pos, ElemType x);
bool SListInsertVal(SList *phead, ElemType x);
void SListErasePos(SList *phead, SListNode* pos);
void SListEraseVal(SList *phead, ElemType x);
SListNode* SListFind(SList *phead, ElemType x);
size_t SListLength(SList *phead);
void SListSort(SList *phead);
void SListReverse(SList *phead);
void SListClear(SList *phead);
ElemType SListFront(SList phead);
ElemType SListBack(SList phead);
void SListErase_all(SList *phead, ElemType x);
#endif 

（1） 单链表初始化

void SListInit(SList *phead)
{
	assert(phead != NULL);
	*phead = NULL;
}

（2）单链表尾插、头插

void SListPushBack(SList *phead, ElemType x)
{
	assert(phead != NULL);
	SListNode* s = (SListNode*)malloc(sizeof(SListNode));
	assert(s != NULL);
	s->data = x;
	s->next = NULL;
	SListNode* p = *phead;
	if (p == NULL)
		*phead = s;
	else
	{
		while (p->next != NULL)
			p = p->next;
		p->next = s;
	}
}
void SListPushFront(SList *phead, ElemType x)
{
	assert(phead != NULL);
	SListNode* s = (SListNode*)malloc(sizeof(SListNode));
	assert(s != NULL);
	s->data = x;
	s->next = *phead;
	*phead = s;
}

 （3）单链表打印

void SListShow(SList *phead)
{
	assert(phead != NULL);
	SListNode* p = *phead;
	while (p != NULL)
	{
		printf("%d->", p->data);
		p = p->next;
	}
	printf("Over!\n");
}

（4）单链表尾删、头删

void SListPopBack(SList *phead)
{
	assert(phead != NULL);
	SListNode* p = *phead;
	SListNode* prev = NULL;
	if (p != NULL)
	{
		while (p->next != NULL)
		{
			prev = p;
			p = p->next;
		}
		if (prev == NULL)
			*phead = NULL;
		else
			prev->next = NULL;
		free(p);
	}
}
void SListPopFront(SList *phead)
{
	assert(phead != NULL);
	SListNode* p = *phead;
	if (p != NULL)
	{
		*phead = p->next;
		free(p);
	}
}

 （5）按位置插入、删除

bool SListInsertPos(SList *phead, SListNode* pos, ElemType x)
{
	assert(phead != NULL);
	assert(pos);
	SListNode* next = pos->next;
	SListNode* s = (SListNode*)malloc(sizeof(SListNode));
	assert(s != NULL);
	s->data = x;
	s->next = NULL;
	pos->next = s;
	s->next = next;
}
void SListErasePos(SList *phead, SListNode* pos)
{
	assert(phead != NULL);
	assert(pos);
	SListNode* next = pos->next;
	if (next != NULL)
	{
		pos->next = next->next;
		free(next);
	}
}

（6）按值插入、删除 

bool SListInsertVal(SList *phead, ElemType x)
{
	assert(phead != NULL);
	SListNode* p = *phead;
	SListNode* prev = NULL;
	while (p != NULL && x > p->data)
	{
		prev = p;
		p = p->next;
	}
	SListNode* s = (SListNode*)malloc(sizeof(SListNode));
	assert(s != NULL);
	s->data = x;
	s->next = NULL;
	if (prev = NULL)
	{
		s->next = *phead;
		*phead = s;
	}
	else
	{
		s->next = prev->next;
		prev->next = s;
	}
}
void SListEraseVal(SList *phead, ElemType x)
{
	assert(phead != NULL);
	SListNode* p = SListFind(*phead, x);
	SListNode* prev = *phead;
	if (p == NULL)
		return;
	while (prev != NULL && prev->next != p)
		prev = prev->next;
	if (prev == p)
		*phead = p->next;
	else
		prev->next = p->next;
	free(p);
}

（7） 查找

SListNode* SListFind(SList *phead, ElemType x)
{
	assert(phead != NULL);
	SListNode* p = *phead;
	while (p != NULL && p->data != x)
		p = p->next;
	return p;
}

（8）求单链表长度

size_t SListLength(SList *phead)
{
	assert(phead != NULL);
	size_t size = 0;
	SListNode* p = *phead;
	while (p != NULL)
	{
		size++;
		p = p->next;
	}
	return size;
}

 （9）单链表排序

void SListSort(SList *phead)
{
	assert(phead != NULL);
	if (SListLength(*phead) <= 1)
	{
		return;
	}
	SListNode *p = *phead;
	SListNode *q = p->next;
	SListNode *prev = NULL;
	SListNode *tmp = *phead;
	p->next = NULL;
	while (q != NULL)
	{
		p = q;
		q = q->next;
		while (tmp != NULL && p->data > tmp->data)
		{
			prev = tmp;
			tmp = tmp->next;
		}
		if (prev == NULL)
		{
			p->next = *phead;
			*phead = p;
		}
		else
		{
			p->next = prev->next;
			prev->next = p;
		}
		tmp = *phead;
		prev = NULL;
	}
}

（10）单链表逆置

void SListReverse(SList *phead)
{
	assert(phead != NULL);
	SListNode* p = *phead;
	SListNode* q = p->next;
	p->next = NULL;
	while (q != NULL)
	{
		p = q;
		q = q->next;
		p->next = *phead;
		*phead = p;
	}
}

 （11）清空单链表

void SListClear(SList *phead)
{
	assert(phead != NULL);
	SListNode* p = NULL;
	while (*phead != NULL)
	{
		p = *phead;
		*phead = p->next;
		free(p);
	}
}

（12）取表头元素、表尾元素 

ElemType SListFront(SList phead)
{
	assert(phead != NULL);
	return phead->data;
}
ElemType SListBack(SList phead)
{
	assert(phead != NULL);
	SListNode* p = phead;
	while (p->next != NULL)
		p = p->next;
	return p->data;
}

（13）删除等于给定值的所有节点

void SListErase_all(SList *phead, ElemType x)
{
	assert(phead != NULL);
	SListNode* p = *phead;
	SListNode* q = p->next;
	while (p != NULL && p->data == x)
	{
		p = p->next;
	}
	while (p != NULL)
	{
		if (p->next != NULL&&p->next->data == x)
			p->next = p->next->next;
		else
			p = p->next;
	}
	return phead;
}

 

2、slist.c

#include"slist.h"

int main()
{
	SList list;
	SListInit(&list);
	SListNode *p = NULL;
	ElemType item;
	int pos;
	bool flag;
	int select = 1;
	while (select)
	{
		printf("***************************************\n");
		printf("* [1] push_back       [2] push_front  *\n");
		printf("* [3] show_list       [0] quit_system *\n");
		printf("* [4] pop_back        [5] pop_front   *\n");
		printf("* [6] insert_pos      [7] insert_val  *\n");
		printf("* [8] erase_pos       [9] erase_val   *\n");
		printf("* [10] find           [11] length     *\n");
		printf("* [12] sort           [13] reverse    *\n");
		printf("* [14] clear          [15] front      *\n");
		printf("* [16] back           [17] erase_all  *\n");
		printf("***************************************\n");
		printf("请选择:>");
		scanf("%d", &select);
		if (select == 0)
		{
			break;
		}
		switch (select)
		{
		case 1:
			printf("请输入要插入的数据<以-1结束>:");
			while (scanf("%d", &item), item != -1)
			{
				SListPushBack(&list, item);
			}
			printf("尾部插入数据成功！\n");
			break;
		case 2:
			printf("请输入要插入的数据<以-1结束>:");
			while (scanf("%d", &item), item != -1)
			{
				SListPushFront(&list, item);
			}
			printf("头部插入数据成功！\n");
			break;
		case 3:
			SListShow(&list);
			break;
		case 4:
			SListPopBack(&list);
			printf("尾部删除数据成功！\n");
			break;
		case 5:
			SListPopFront(&list);
			printf("头部删除数据成功！\n");
			break;
		case 6:
			printf("请输入要插入的位置:");
			scanf("%d", &pos);
			printf("请输入要插入的元素：");
			scanf("%d", &item);
			SListInsertPos(&list, pos, item);
			flag = SListInsertPos(&list, pos, item);
			if (flag)
			{
				printf("插入数据成功！\n");
			}
			else
			{
				printf("插入数据失败！\n");
			}
			break;
		case 7:
			printf("请输入要插入的元素：");
			scanf("%d", &item);
			SListSort(&list);
			SListInsertVal(&list, item);
			flag = SListInsertVal(&list, item);
			if (flag)
			{
				printf("插入数据成功！\n");
			}
			else
			{
				printf("插入数据失败！\n");
			}
			break;
		case 8:
			printf("请输入要删除的位置：");
			scanf("%d", &pos);
			SListErasePos(&list, pos);
			printf("删除元素成功！\n");
			break;
		case 9:
			printf("请输入要删除的元素：");
			scanf("%d", &item);
			SListEraseVal(&list, item);
			printf("删除元素成功！\n");
			break;
		case 10:
			printf("请输入要查找的元素：");
			scanf("%d", &item);
			SListFind(&list, item);
			break;
		case 11:
			printf("SeqList length=%d\n", SListLength(&list));
			break;
		case 12:
			SListSort(&list);
			printf("顺序表排序成功！\n");
			break;
		case 13:
			SListReverse(&list);
			printf("顺序表转置完成！\n");
			break;
		case 14:
			SListClear(&list);
			break;
		case 15:
			printf("表头元素为%d\n", SListFront(list));
			break;
		case 16:
			printf("表尾元素为%d\n", SListBack(list));
			break;
		case 17:
			printf("请输入要删除的元素：");
			scanf("%d", &item);
			SListErase_all(&list, item);
			printf("删除成功！\n");
			break;
		default:
			printf("输入错误，请重新选择.......\n");
			break;
		}
		system("pause");
		system("cls");
	}
	return 0;
}