c语言链表的尾指针,C语言单链表实现方法详解

太过爱你忘了你带给我的痛 2022-10-14 05:52 177阅读 0赞

本文实例讲述了C语言单链表实现方法。分享给大家供大家参考，具体如下：

slist.h

\#ifndef \_\_SLIST\_H\_\_

\#define \_\_SLIST\_H\_\_

\#include

typedef int ElemType;

typedef struct Node \{ //定义单链表中的结点信息

ElemType data; //结点的数据域

struct Node \*next; //结点的指针域

\}Node,\*PNode;

typedef struct List \{ //定义单链表的链表信息

PNode first; //first指向单链表中的第一个结点

PNode last; //last指向单链表中的最后一个结点

size\_t size; //记录单链表中的结点个数

\}List;

void InitList(List \*list);//初始化单链表

void push\_back(List \*list, ElemType x);//在单链表的末尾插入元素

void push\_front(List \*list, ElemType x);//在单链表的头部插入元素

void show\_list(List \*list);//打印单链表

void pop\_back(List \*list);//删除单链表的最后一个元素

void pop\_front(List \*list);//删除单链表的第一个元素

void insert\_val(List \*list, ElemType val);//将数据元素插入到单链表中(要求此时单链表中的数据元素顺序排列)

Node\* find(List \*list, ElemType x);//查找单链表中数据值为x的结点

int length(List \*list);//求单链表的长度

void delete\_val(List \*list, ElemType x);//按值删除单链表中的某个数据元素

void sort(List \*list);//对单链表进行排序

void reverse(List \*list);//逆置单链表

void clear(List \*list);//清除单链表

void destroy(List \*list);//摧毁单链表

\#endif //\_\_SLIST\_H\_\_

slist.cpp

\#include"slist.h"

void InitList(List \*list) \{

list->first = list->last = (Node\*)malloc(sizeof(Node)); //头结点

assert(list->first != NULL);

list->first->next = NULL;

list->size = 0;

void push\_back(List \*list, ElemType x) \{

//step 1：创建一个新的结点

Node \*s = (Node\*)malloc(sizeof(Node));

assert(s != NULL);

s->data = x;

s->next = NULL;

//step 2：将新结点插入单链表的表尾

list->last->next = s;

list->last = s;

//step 3：更新单链表的长度

list->size++;

void push\_front(List \*list, ElemType x) \{

//step 1：创建一个新的结点

Node \*s = (Node\*)malloc(sizeof(Node));

assert(s != NULL);

s->data = x;

s->next = NULL;

//step 2：将新结点插入单链表的表头

s->next = list->first->next;

list->first->next = s;

//step 3：判断插入的结点是否是单链表的第一个结点，若是更新链表的尾指针

if (list->size == 0)

list->last = s;

//step 4：更新单链表的长度

list->size++;

void show\_list(List \*list) \{

//step 1：指针p指向单链表的第一个结点

Node \*p = list->first->next;

//step 2：循环打印结点的信息

while (p != NULL) \{

printf("%d->", p->data);

p = p->next;

printf("Nul.\\n");

void pop\_back(List \*list) \{

//step 1：判断单链表是否为空

if (list->size == 0) return;

//step 2：定义指针p使其指向目标结点的前一个结点

Node \*p = list->first;//从头结点开始

while (p->next != list->last)

p = p->next;

//step 3：删除目标结点

free(list->last);

list->last = p;

list->last->next = NULL;

//step 4：更新单链表的长度

list->size--;

void pop\_front(List \*list) \{

//step 1：判断单链表是否为空

if (list->size == 0) return;

//step 2：定义指针p使其指向目标结点的前一个结点

Node \*p = list->first->next;

//step 3：删除目标结点

list->first->next = p->next;

free(p);

//step 4：判断删除的结点是否是单链表的最后一个结点，若是则更新单链表的尾指针

if (list->size == 1)

list->last = list->first;

//step 4：更新单链表的长度

list->size--;

void insert\_val(List \*list, ElemType x) \{

//step 1：创建一个新的结点

Node \*s = (Node\*)malloc(sizeof(Node));

assert(s != NULL);

s->data = x;

s->next = NULL;

//step 2：定义指针p使其指向待插入位置的前一个结点

Node \*p = list->first;//从头结点开始

while (p->next != NULL && p->next->data < s->data)

p = p->next;

//step 3：判断结点的待插入位置是否是表尾，若是则更新单链表的尾指针

if (p->next == NULL)

list->last = s;

//step 4：插入结点

s->next = p->next;

p->next = s;

//step 5：更新单链表长度

list->size++;

Node\* find(List \*list, ElemType x) \{

//step 1：指针p指向单链表的第一个结点

Node \*p = list->first->next;

//step 2：按照循环顺序查找链表结点

while (p != NULL && p->data != x)

p = p->next;

return p;

int length(List \*list) \{

return list->size;

void delete\_val(List \*list, ElemType x) \{

//step 1：判断单链表是否为空

if (list->size == 0) return;

//step 2：确定结点在单链表中的位置，并判断其是否存在于单链表中

Node \*p = find(list, x);

if (p == NULL) \{

printf("要删除的数据不存在！\\n");

return;

//step 3：判断结点位置是否是表尾

if (p == list->last)//是表尾

pop\_back(list);

else \{//不是表尾

Node \*q = p->next;

p->data = q->data;

p->next = q->next;

free(q);

list->size--;

void sort(List \*list) \{

//step 1：判断单链表中的结点数是否为0或1

if (list->size == 0 || list->size == 1) return;

//step 2：将单链表中第一个结点之后的链表部分截出，方便重新按顺序插入链表之中

Node \*s = list->first->next; // 指针s指向单链表的第一个节点

Node \*p = s->next;//q指向s后面的结点

list->last = s;//单链表的尾指针指向单链表的第一个结点

list->last->next = NULL;//截断链表

//step 3：将截出的链表中的结点根据其数据域大小重新插入到原来链表中

while (p != NULL) \{

s = p;

p = p->next;

Node \*q = list->first;

while (q->next != NULL && q->next->data < s->data)

q = q->next;

if (q->next == NULL)//判断q此时指向的是否是单链表的最后一个结点，若是则更新链表的尾指针

list->last = s;

//将结点重新插入链表

s->next = q->next;

q->next = s;

void reverse(List \*list) \{

//step 1：判断单链表中的结点数是否为0或1

if (list->size == 0 || list->size == 1) return;

//step 2：将单链表中第一个结点之后的链表部分截出，然后将截出的链表中的结点按头插法重新插入到原链表中

Node \*p = list->first->next;

Node \*q = p->next;

list->last = p;

list->last->next = NULL;

while (q != NULL) \{

p = q;

q = q->next;

p->next = list->first->next;

list->first->next = p;

void clear(List \*list) \{

//step 1：判断单链表是否为空

if (list->size == 0) return;

//step 2：释放单链表中的每一个结点

Node \*p = list->first->next;

while (p != NULL) \{

list->first->next = p->next;

free(p);

p = list->first->next;

//step 3：头指针和尾指针重新都指向头结点

list->last = list->first;

//step 4：更新链表长度

list->size = 0;

void destroy(List \*list) \{

//step 1：清空单链表

clear(list);

//step 2：释放头结点

free(list->first);

//step 3：头指针和尾指针都赋值为空

list->first = list->last = NULL;

main.cpp

\#include"slist.h"

void main() \{

List mylist;

InitList(&mylist);

ElemType item;

Node \*p = NULL;

int select = 1;

while (select) \{

printf("\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n");

printf("\*\[1\] push\_back \[2\] push\_front \*\\n");

printf("\*\[3\] show\_list \[4\] pop\_back \*\\n");

printf("\*\[5\] pop\_front \[6\] insert\_val \*\\n");

printf("\*\[7\] find \[8\] length \*\\n");

printf("\*\[9\] delete\_val \[10\] sort \*\\n");

printf("\*\[11\] reverse \[12\] clear \*\\n");

printf("\*\[13\*\] destroy \[0\] quit\_system \*\\n");

printf("\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n");

printf("请选择：>>");

scanf("%d", &select);

if (select == 0) break;

switch (select) \{

case 1:

printf("请输入要插入的数据(-1结束):>");

while (scanf("%d", &item), item != -1) \{

push\_back(&mylist, item);

break;

case 2:

printf("请输入要插入的数据(-1结束):>");

while (scanf("%d", &item), item != -1) \{

push\_front(&mylist, item);

break;

case 3:

show\_list(&mylist);

break;

case 4:

pop\_back(&mylist);

break;

case 5:

pop\_front(&mylist);

break;

case 6:

printf("请输入要插入的数据:>");

scanf("%d", &item);

insert\_val(&mylist, item);

break;

case 7:

printf("请输入要查找的数据:>");

scanf("%d", &item);

p = find(&mylist, item);

if (p == NULL)

printf("要查找的数据在单链表中不存在！\\n");

break;

case 8:

printf("单链表的长度为%d\\n", length(&mylist));

break;

case 9:

printf("请输入要删除的值:>");

scanf("%d", &item);

delete\_val(&mylist, item);

break;

case 10:

sort(&mylist);

break;

case 11:

reverse(&mylist);

break;

case 12:

clear(&mylist);

break;

//case 13:

//destroy(&mylist);

//break;

default:

printf("选择错误,请重新选择！\\n");

break;

destroy(&mylist); //程序结束，摧毁链表

附：单链表优化版本

slist.h

\#ifndef \_\_SLIST\_H\_\_

\#define \_\_SLIST\_H\_\_

\#include

typedef int ElemType;

typedef struct Node \{ //定义单链表中的结点信息

ElemType data; //结点的数据域

struct Node \*next; //结点的指针域

\}Node,\*PNode;

typedef struct List \{ //定义单链表的链表信息

PNode first; //first指向单链表中的第一个结点

PNode last; //last指向单链表中的最后一个结点

size\_t size; //记录单链表中的结点个数

\}List;

void InitList(List \*list);//初始化单链表

void push\_back(List \*list, ElemType x);//在单链表的末尾插入元素

void push\_front(List \*list, ElemType x);//在单链表的头部插入元素

void show\_list(List \*list);//打印单链表

void pop\_back(List \*list);//删除单链表的最后一个元素

void pop\_front(List \*list);//删除单链表的第一个元素

void insert\_val(List \*list, ElemType val);//将数据元素插入到单链表中(要求此时单链表中的数据元素顺序排列)

Node\* find(List \*list, ElemType x);//查找单链表中数据值为x的结点

int length(List \*list);//求单链表的长度

void delete\_val(List \*list, ElemType x);//按值删除单链表中的某个数据元素

void sort(List \*list);//对单链表进行排序

void reverse(List \*list);//逆置单链表

void clear(List \*list);//清除单链表

void destroy(List \*list);//摧毁单链表

//代码优化

Node\* CreateNode(ElemType x); //创建一个单链表结点

Node\* begin(List \*list); //返回单链表的第一个结点

Node\* end(List \*list); //返回单链表中最后一个结点的下一个结点

void insert(List \*list, Node \*pos, ElemType x); //在单链表的特定位置(pos)插入新的结点

\#endif //\_\_SLIST\_H\_\_

slist.cpp

\#include"slist.h"

void InitList(List \*list) \{

list->first = list->last = (Node\*)malloc(sizeof(Node)); //头结点

assert(list->first != NULL);

list->first->next = NULL;

list->size = 0;

//push\_back的优化

void push\_back(List \*list, ElemType x) \{

insert(list, end(list), x);

//push\_front的优化

void push\_front(List \*list, ElemType x) \{

insert(list, begin(list), x);

void show\_list(List \*list) \{

//step 1：指针p指向单链表的第一个结点

Node \*p = list->first->next;

//step 2：循环打印结点的信息

while (p != NULL) \{

printf("%d->", p->data);

p = p->next;

printf("Nul.\\n");

void pop\_back(List \*list) \{

//step 1：判断单链表是否为空

if (list->size == 0) return;

//step 2：定义指针p使其指向目标结点的前一个结点

Node \*p = list->first;//从头结点开始

while (p->next != list->last)

p = p->next;

//step 3：删除目标结点

free(list->last);

list->last = p;

list->last->next = NULL;

//step 4：更新单链表的长度

list->size--;

void pop\_front(List \*list) \{

//step 1：判断单链表是否为空

if (list->size == 0) return;

//step 2：定义指针p使其指向目标结点的前一个结点

Node \*p = list->first->next;

//step 3：删除目标结点

list->first->next = p->next;

free(p);

//step 4：判断删除的结点是否是单链表的最后一个结点，若是则更新单链表的尾指针

if (list->size == 1)

list->last = list->first;

//step 4：更新单链表的长度

list->size--;

//insert\_val的优化

void insert\_val(List \*list, ElemType x) \{

//step 1：创建一个新的结点

Node \*s = CreateNode(x);

//step 2：定义指针p使其指向待插入位置的前一个结点

Node \*p = list->first;//从头结点开始

while (p->next != NULL && p->next->data < s->data)

p = p->next;

//step 3：判断结点的待插入位置是否是表尾，若是则更新单链表的尾指针

if (p->next == NULL)

list->last = s;

//step 4：插入结点

s->next = p->next;

p->next = s;

//step 5：更新单链表长度

list->size++;

Node\* find(List \*list, ElemType x) \{

//step 1：指针p指向单链表的第一个结点

Node \*p = list->first->next;

//step 2：按照循环顺序查找链表结点

while (p != NULL && p->data != x)

p = p->next;

return p;

int length(List \*list) \{

return list->size;

void delete\_val(List \*list, ElemType x) \{

//step 1：判断单链表是否为空

if (list->size == 0) return;

//step 2：确定结点在单链表中的位置，并判断其是否存在于单链表中

Node \*p = find(list, x);

if (p == NULL) \{

printf("要删除的数据不存在！\\n");

return;

//step 3：判断结点位置是否是表尾

if (p == list->last)//是表尾

pop\_back(list);

else \{//不是表尾

Node \*q = p->next;

p->data = q->data;

p->next = q->next;

free(q);

list->size--;

void sort(List \*list) \{

//step 1：判断单链表中的结点数是否为0或1

if (list->size == 0 || list->size == 1) return;

//step 2：将单链表中第一个结点之后的链表部分截出，方便重新按顺序插入链表之中

Node \*s = list->first->next; // 指针s指向单链表的第一个节点

Node \*p = s->next;//q指向s后面的结点

list->last = s;//单链表的尾指针指向单链表的第一个结点

list->last->next = NULL;//截断链表

//step 3：将截出的链表中的结点根据其数据域大小重新插入到原来链表中

while (p != NULL) \{

s = p;

p = p->next;

Node \*q = list->first;

while (q->next != NULL && q->next->data < s->data)

q = q->next;

if (q->next == NULL)//判断q此时指向的是否是单链表的最后一个结点，若是则更新链表的尾指针

list->last = s;

//将结点重新插入链表

s->next = q->next;

q->next = s;

void reverse(List \*list) \{

//step 1：判断单链表中的结点数是否为0或1

if (list->size == 0 || list->size == 1) return;

//step 2：将单链表中第一个结点之后的链表部分截出，然后将截出的链表中的结点按头插法重新插入到原链表中

Node \*p = list->first->next;

Node \*q = p->next;

list->last = p;

list->last->next = NULL;

while (q != NULL) \{

p = q;

q = q->next;

p->next = list->first->next;

list->first->next = p;

void clear(List \*list) \{

//step 1：判断单链表是否为空

if (list->size == 0) return;

//step 2：释放单链表中的每一个结点

Node \*p = list->first->next;

while (p != NULL) \{

list->first->next = p->next;

free(p);

p = list->first->next;

//step 3：头指针和尾指针重新都指向头结点

list->last = list->first;

//step 4：更新链表长度

list->size = 0;

void destroy(List \*list) \{

//step 1：清空单链表

clear(list);

//step 2：释放头结点

free(list->first);

//step 3：头指针和尾指针都赋值为空

list->first = list->last = NULL;

//优化

Node\* CreateNode(ElemType x) \{

Node \*s = (Node\*)malloc(sizeof(Node));

assert(s != NULL);

s->data = x;

s->next = NULL;

return s;

Node\* begin(List \*list) \{

return list->first->next;

Node\* end(List \*list) \{

return list->last->next;

void insert(List \*list, Node \*pos, ElemType x) \{

//step 1：创建一个新的结点

Node \*s = CreateNode(x);

//step 2：确定带插入位置

Node \*p = list->first;

while (p->next != pos)

p = p->next;

//step 3：插入结点

s->next = p->next;

p->next = s;

//step 4：判断结点是否插入到链表的表尾，若是则更新单链表的表尾指针

if (pos == NULL)

list->last = s;

//step 5：更新单链表长度

list->size++;

main.cpp

\#include"slist.h"

void main() \{

List mylist;

InitList(&mylist);

ElemType item;

Node \*p = NULL;

int select = 1;

while (select) \{

printf("\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n");

printf("\*\[1\] push\_back \[2\] push\_front \*\\n");

printf("\*\[3\] show\_list \[4\] pop\_back \*\\n");

printf("\*\[5\] pop\_front \[6\] insert\_val \*\\n");

printf("\*\[7\] find \[8\] length \*\\n");

printf("\*\[9\] delete\_val \[10\] sort \*\\n");

printf("\*\[11\] reverse \[12\] clear \*\\n");

printf("\*\[13\*\] destroy \[0\] quit\_system \*\\n");

printf("\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n");

printf("请选择：>>");

scanf("%d", &select);

if (select == 0) break;

switch (select) \{

case 1:

printf("请输入要插入的数据(-1结束):>");

while (scanf("%d", &item), item != -1) \{

push\_back(&mylist, item);

break;

case 2:

printf("请输入要插入的数据(-1结束):>");

while (scanf("%d", &item), item != -1) \{

push\_front(&mylist, item);

break;

case 3:

show\_list(&mylist);

break;

case 4:

pop\_back(&mylist);

break;

case 5:

pop\_front(&mylist);

break;

case 6:

printf("请输入要插入的数据:>");

scanf("%d", &item);

insert\_val(&mylist, item);

break;

case 7:

printf("请输入要查找的数据:>");

scanf("%d", &item);

p = find(&mylist, item);

if (p == NULL)

printf("要查找的数据在单链表中不存在！\\n");

break;

case 8:

printf("单链表的长度为%d\\n", length(&mylist));

break;

case 9:

printf("请输入要删除的值:>");

scanf("%d", &item);

delete\_val(&mylist, item);

break;

case 10:

sort(&mylist);

break;

case 11:

reverse(&mylist);

break;

case 12:

clear(&mylist);

break;

//case 13:

//destroy(&mylist);

//break;

default:

printf("选择错误,请重新选择！\\n");

break;

destroy(&mylist); //程序结束，摧毁链表

希望本文所述对大家C语言程序设计有所帮助。

c语言链表的尾指针,C语言单链表实现方法详解

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 C语言实现链表尾插法

相关 c语言单链表怎样实现,C语言单链表的实现

相关 c语言链表的尾指针,C语言单链表实现方法详解

相关 C语言单链表

相关 C语言实现单链表

相关 C语言单链表

相关 C语言单链表

相关 [c语言]单链表的实现

相关链表的C语言实现之单链表的实现

相关顺序表单链表C语言实现