单链表_C语言

标签：int   void   define   author   node   结构   def   scan   efi   

/***********************************************************************************************************************
File Name : 单链表.c
Date Created : 2019-10-21
Author : 大竹竿
Description : 实现单链表各类操作
***********************************************************************************************************************/

/*带头节点的单链表 */

/*
头节点；首节点前的节点(头节点永远指向首节点，头节点不存在左指针)
头指针：指向头节点的指针
首节点：链表第一个节点
尾节点：链表最后一个节点
*/

#include
#include

#define true 1
#define false 0
#define num 5
typedef int datatype;
typedef int bool;

/* 定义节点结构体 */
typedef struct list {
datatype data; // 数据域
struct list *next; // 指针域
}List, *pList;

/* 函数声明 */
pList init(); // 初始化
void build(pList h); // 创建
int isEmpty(pList h); // 判空
int length(pList h); // 测长
void print(pList h); // 打印

/* 增 */
void head_Insert(pList h); // 头插
void tail_Insert(pList h); // 尾插
void first_head_Value_Insert(pList h); // 指定值头插(只插第一个)
void all_head_Value_Insert(pList h); // 指定值头插(所有的)
void first_tail_Value_Insert(pList h); // 指定值尾插(只插第一个)
void all_tail_Value_Insert(pList h); // 指定值尾插(所有的)
void head_Order_Insert(pList h); // 指定序号头插
void tail_Order_Insert(pList h); // 指定序号尾插

/* 删 */
void head_Delete(pList h); // 头删
void tail_Delete(pList h); // 尾删
void first_Value_Delete(pList h); // 指定值删除(只删除第一个)
void all_Value_Delete(pList h); // 指定值删除(删除所有的)
void order_Delete(pList h); // 指定序号删除

/* 改 */
void first_Value_Revise(pList h); // 指定值修改(只修改第一个)
void all_Value_Revise(pList h); // 指定值修改(修改所有的)
void order_Revise(pList h); // 指定序号修改

/* 查 */
void first_Value_Query(pList h); // 指定值查询(只查询第一个)
void all_Value_Query(pList h); // 指定值查询(查找所有的)
void order_Query(pList h); // 指定序号查询

void Destroy(pList h); // 销毁

/* 函数定义 */
/* 初始化 */
pList init()
{
pList h = (pList)malloc((sizeof(List))); // 创建头结点
h->next = NULL; // 初始化时，头结点指针域置空

return h;
}

/* 创建 */
void build(pList h)
{
pList p; // 声明一个移动指针
p = h; // 头结点h赋给p

int i, arr[num];
printf("请输入%d个数：", num);
for (i = 0; i
scanf("%d", &arr[i]);
}

for (i = 0; i
pList node = (pList)malloc(sizeof(List)); // 创建节点
node->data = arr[i]; // 节点数据域
node->next = NULL; // 节点指针域
p->next = node; // 上一个节点指向下一个节点（对于首节点而言，为头结点指向首节点）
p = p->next; // 指针后移
}

return;
}

/* 判空 */
bool isEmpty(pList h)
{
if (h->next == NULL) {
return true;
}
return false;
}

/* 测长 */
int length(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
exit(0);
}

int len = 0;
pList p = h;
while (p->next != NULL) {
len++;
p = p->next;
}
printf("当前链表长度为：%d\n", len);

return len;
}

/* 打印 */
void print(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
exit(0);
}

printf("当前链表为：");
pList p = h->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n\n");

return;
}

/* 头插 */
void head_Insert(pList h)
{
printf("请输入头插的值：");
datatype ele;
scanf("%d", &ele);

pList node = (pList)malloc(sizeof(List));
node->data = ele;
node->next = h->next;
h->next = node;

return;
}

/* 尾插 */
void tail_Insert(pList h)
{
printf("请输入尾插的值：");
datatype ele;
scanf("%d", &ele);

pList p = h; // 移动指针
while (p->next != NULL) { // 找到尾节点
p = p->next;
}

pList node = (pList)malloc(sizeof(List));
node->data = ele;
node->next = NULL;
p->next = node;

return;
}

/* 指定值头插(只插第一个) */
void first_head_Value_Insert(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
exit(0);
}

printf("请输入需要在哪个数值前插入(只插第一个)：");
datatype ele;
scanf("%d", &ele);

printf("请输入需要插入的值；");
datatype val;
scanf("%d", &val);

pList p = h; // 移动指针
while (p->next != NULL){
if (p->next->data == ele) { // 找到指定值的前驱
break;
}
p = p->next;
}

if (p->next == NULL) {
printf("输入的值%d不存在!\n", ele);
return;
}

pList node = (pList)malloc(sizeof(List));
node->data = val;
node->next = p->next;
p->next = node;

return;
}

/* 指定值头插(所有的) */
void all_head_Value_Insert(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
exit(0);
}

printf("请输入需要在哪个数值前插入(所有的)：");
datatype ele;
scanf("%d", &ele);

printf("请输入需要插入的值；");
datatype val;
scanf("%d", &val);

pList p = h;
bool flag = true;
while (p->next != NULL) { // 找到指定值的前驱
if (p->next->data == ele) {
flag = false;
pList node = (pList)malloc(sizeof(List));
node->data = val;
node->next = p->next;
p->next = node;
p = p->next->next;
continue;
}
p = p->next;
}

if (flag) {
printf("输入的值%d不存在!\n", ele);
return;
}

return;
}

/* 指定值尾插(只插第一个) */
void first_tail_Value_Insert(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
exit(0);
}

printf("请输入需要在哪个值后插入(只插第一个)：");
datatype ele;
scanf("%d", &ele);

printf("请输入需要插入的值：");
datatype val;
scanf("%d", &val);

pList p = h->next; // 移动指针
while (p != NULL) { // 找到指定值节点
if (p->data == ele) {
break;
}
p = p->next;
}

if (p == NULL) {
printf("输入的值%d不存在!\n", ele);
return;
}

pList node = (pList)malloc(sizeof(List));
node->data = val;
node->next = p->next;
p->next = node;

return;
}

/* 指定值尾插(所有的) */
void all_tail_Value_Insert(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
exit(0);
}

printf("请输入需要在哪个值后插入(所有的)：");
datatype ele;
scanf("%d", &ele);

printf("请输入需要插入的值：");
datatype val;
scanf("%d", &val);

pList p = h->next;
bool flag = true;
while (p != NULL) { // 找到指定值节点
if (p->data == ele) {
flag = false;
pList node = (pList)malloc(sizeof(List));
node->data = val;
node->next = p->next;
p->next = node;
p = p->next->next;
continue;
}
p = p->next;
}

if (flag) {
printf("输入的值%d不存在!\n", ele);
return;
}

return;
}

/* 指定序号头插 */
void head_Order_Insert(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
exit(0);
}

printf("请输入在第几个元素前插入：");
int n;
scanf("%d", &n);

if ((n length(h))) {
printf("输入的序号非法!\n");
return;
}

printf("请输入需要插入的值：");
datatype ele;
scanf("%d", &ele);

pList p = h;
int i = 1;
while (i != n) { // 找到指定序号节点的前驱
p = p->next;
i++;
}
pList node = (pList)malloc(sizeof(List));
node->data = ele;
node->next = p->next;
p->next = node;

return;
}

/* 指定序号尾插 */
void tail_Order_Insert(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
exit(0);
}

printf("请输入在第几个元素后插入：");
int n;
scanf("%d", &n);

if ((n length(h))) {
printf("输入的序号非法!\n");
return;
}

printf("请输入需要插入的值：");
datatype ele;
scanf("%d", &ele);

pList p = h;
int i = 0;
while (i != n) { // 找到指定序号节点
p = p->next;
i++;
}
pList node = (pList)malloc(sizeof(List));
node->data = ele;
node->next = p->next;
p->next = node;

return;
}

/* 头删 */
void head_Delete(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
exit(0);
}

printf("头删...\n");
pList p = h->next;
h->next = h->next->next;
free(p);

return;
}

/* 尾删 */
void tail_Delete(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
exit(0);
}

printf("尾删...\n");
pList p = h;
while (p->next->next != NULL) {
p = p->next;
}
free(p->next);
p->next = NULL;

return;
}

/* 指定值删除（删除第一个） */
void first_Value_Delete(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
exit(0);
}

printf("请输入需要删除的值(只删第一个)：");
datatype ele;
scanf("%d", &ele);

pList p = h, p1;
while (p->next != NULL) { // 找到指定值的前驱
if (p->next->data == ele) {
break;
}
p = p->next;
}

if (p->next == NULL) {
printf("输入的值%d不存在!\n", ele);
return;
}
p1 = p->next;
p->next = p->next->next;
free(p1);

return;
}

/* 指定值删除（删除所有的） */
void all_Value_Delete(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
exit(0);
}

printf("请输入需要删除的值(删除所有)：");
datatype ele;
scanf("%d", &ele);

pList p = h, p1;
bool flag = true;
while (p->next != NULL) { // 找到指定值的前驱
if (p->next->data == ele) {
flag = false;
p1 = p->next;
p->next = p->next->next;
free(p1);
continue;
}
p = p->next;
}

if (flag) {
printf("输入的值%d不存在!\n", ele);
return;
}

return;
}

/* 指定序号删除 */
void order_Delete(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
exit(0);
}

printf("请输入需要删除第几个元素：");
int n;
scanf("%d", &n);

if ((n length(h))) {
printf("输入的序号非法!\n");
return;
}

pList p = h, p1;
int i = 1;
while (i != n) { // 找到指定序号节点前驱
p = p->next;
i++;
}
p1 = p->next;
p->next = p->next->next;
free(p1);

return;
}

/* 指定值修改（只改第一个） */
void first_Value_Revise(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
exit(0);
}

printf("请输入需要修改的值(修改第一个)：");
datatype ele;
scanf("%d", &ele);

printf("请输入改为哪个值：");
datatype val;
scanf("%d", &val);

pList p = h;
while (p->next != NULL) { // 找到指定值节点的前驱
if (p->next->data == ele) {
p->next->data = val;
return;
}
p = p->next;
}

if (p->next == NULL) {
printf("输入的值%d不存在!\n", ele);
return;
}

return;
}

/* 指定值修改(修改所有) */
void all_Value_Revise(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
exit(0);
}

printf("请输入需要修改的值(修改所有的)：");
datatype ele;
scanf("%d", &ele);

printf("请输入改为哪个值：");
datatype val;
scanf("%d", &val);

pList p = h;
bool flag = true;
while (p->next != NULL) { // 找到指定值节点的前驱
if (p->next->data == ele) {
flag =false;
p->next->data = val;
}
p = p->next;
}

if (flag) {
printf("输入的值%d不存在!\n", ele);
return;
}

return;
}

/* 指定序号修改 */
void order_Revise(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
exit(0);
}

printf("请输入需要修改第几个元素：");
int n;
scanf("%d", &n);

if ((n length(h))) {
printf("输入的序号非法!\n");
return;
}

printf("请输入改为哪个值：");
datatype val;
scanf("%d", &val);

pList p = h;
int i = 0;
while (i != n) { // 找到指定序号节点
p = p->next;
i++;
}
p->data = val;

return;
}

/* 指定值查找（查找第一个） */
void first_Value_Query(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
exit(0);
}

printf("请输入需要查找的值(只查第一个)：");
datatype ele;
scanf("%d", &ele);

pList p = h;
int n = 0;
while (p->next != NULL) { // 找到指定值的前驱
n++;
if (p->next->data == ele) {
printf("元素%d在第%d号位置上!\n", ele, n);
return;
}
p = p->next;
}

if (p->next == NULL) {
printf("输入的值%d不存在!\n", ele);
return;
}

return;
}

/* 指定值查找（查找所有） */
void all_Value_Query(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
exit(0);
}

printf("请输入需要查询的值(查找所有的)：");
datatype ele;
scanf("%d", &ele);

printf("%d所处的位置分别为：", ele);
pList p = h;
int i = 0;
bool flag = true;
while (p->next != NULL) { // 找到指定值的前驱
i++;
if (p->next->data == ele) {
printf("%d ", i);
flag = false;
}
p = p->next;
}

if (flag) {
printf("输入的值%d不存在!\n", ele);
return;
}
else {
printf("\n");
}

return;
}

/* 指定序号查询 */
void order_Query(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
exit(0);
}

printf("请输入需要查询第几个位置的元素：");
int n;
scanf("%d", &n);

if ((n length(h))) {
printf("输入的序号非法!\n");
return;
}

pList p = h;
int i = 0;
while (i != n) { // 找到指定序号节点
p = p->next;
i++;
}
printf("第%d号位置的元素为：%d\n", n, p->data);

return;
}

/* 销毁 */
void Destroy(pList h)
{
if (isEmpty(h)) {
printf("链表为空!\n");
exit(0);
}

printf("销毁链表...\n");
pList p = h, p1;
while (!(isEmpty(h))) {
p1 = p->next;
p->next = p->next->next;
free(p1);
}

return;
}

int main()
{
/* 初始化 */
pList head = init(); // 创建头结点

/* 创建 */
build(head);
length(head);
print(head);

/* 头插 */
head_Insert(head);
length(head);
print(head);

/* 尾插 */
tail_Insert(head);
length(head);
print(head);

/* 指定值头插(只插第一个) */
first_head_Value_Insert(head);
length(head);
print(head);

/* 指定值头插(所有的) */
all_head_Value_Insert(head);
length(head);
print(head);

/* 指定值尾插(只插第一个) */
first_tail_Value_Insert(head);
length(head);
print(head);

/* 指定值尾插(所有的) */
all_tail_Value_Insert(head);
length(head);
print(head);

/* 指定序号头插 */
head_Order_Insert(head);
length(head);
print(head);

/* 指定序号尾插 */
tail_Order_Insert(head);
length(head);
print(head);

/* 头删 */
head_Delete(head);
length(head);
print(head);

/* 尾删 */
tail_Delete(head);
length(head);
print(head);

/* 指定值删除(删除第一个) */
first_Value_Delete(head);
length(head);
print(head);

/* 指定值删除(删除所有的) */
all_Value_Delete(head);
length(head);
print(head);

/* 指定序号删除 */
order_Delete(head);
length(head);
print(head);

/* 指定值修改(只修改第一个) */
first_Value_Revise(head);
length(head);
print(head);

/* 指定值修改(修改所有) */
all_Value_Revise(head);
length(head);
print(head);

/* 指定序号修改 */
order_Revise(head);
length(head);
print(head);

/* 指定值查询(只查第一个) */
first_Value_Query(head);
length(head);
print(head);

/* 指定值查询(查找所有的) */
all_Value_Query(head);
length(head);
print(head);

/* 指定序号查询 */
order_Query(head);
length(head);
print(head);

/* 销毁 */
Destroy(head);
length(head);
print(head);

return 0;
}

单链表_C语言

标签：int   void   define   author   node   结构   def   scan   efi   

原文地址：https://www.cnblogs.com/programmer-home/p/12928344.html