# （含有头结点以及尾结点）单链表各类功能的实现

void InitList(List *list); //初始化单链表
bool push_back(List *list,ElemType x); //尾插法
void show_seqlist(List *list); //显示链表内容
bool push_front(List *list,ElemType x);//头插法
bool pop_back(List *list); //尾删法
bool pop_front(List *list); //头删法
Node *find(List *list,ElemType x); //查找函数，找到返回指向该元素的指针
bool modify(List *list,ElemType x); //修改某1元素的值
void delete_val(List *list,ElemType x);//按值删除
void clear(List *list); //清空链表
void destroy(List *list); //烧毁链表
int length(List *list); //求链表长度
void resver(List *list); //逆至链表
void prio(List *list,ElemType x); //求某个值的先驱
void next(List *list,ElemType x); //求某个值的后继

List.h:

#ifndef __LIST_H__
#define __LIST_H__

#include<assert.h>
#include<iostream>
using namespace std;
typedef int ElemType;

typedef struct Node
{
ElemType data;
struct Node *next;
}Node;

typedef struct List
{
Node *first;
Node *last;
int size;
}List;

void InitList(List *list); //初始化单链表
bool push_back(List *list,ElemType x); //尾插法
void show_seqlist(List *list); //显示链表内容
bool push_front(List *list,ElemType x);//头插法
bool pop_back(List *list); //尾删法
bool pop_front(List *list); //头删法
Node *find(List *list,ElemType x); //查找函数，找到返回指向该元素的指针
bool modify(List *list,ElemType x); //修改某1元素的值
void delete_val(List *list,ElemType x);//按值删除
void clear(List *list); //清空链表
void destroy(List *list); //烧毁链表
int length(List *list); //求链表长度
void resver(List *list); //逆至链表
void prio(List *list,ElemType x); //求某个值的先驱
void next(List *list,ElemType x); //求某个值的后继
#endif

List.cpp:

#include"List.h"
//初始化单链表
void InitList(List *list)
{
Node *s = (Node *)malloc(sizeof(Node));
assert(s != NULL);
s->next = NULL;
list->first = list->last = s;
list->size = 0;
}
//尾插法：开辟并初始化—>>连接—->>指针后移
bool push_back(List *list,ElemType x)
{
Node *s = (Node *)malloc(sizeof(Node));//开辟1个结点
if(s == NULL)
{
return false;
}
s->next = NULL;//对节点的初始化
s->data = x;

list->last->next = s;//连接
list->last = s; //后移（尾指针后移）
list->size++;
return true;
}
//打印链表的内容
void show_seqlist(List *list)
{
Node *p = list->first->next;
while(p != NULL)
{
cout<<p->data<<"—>";
p = p->next;
}
cout<<"NULL"<<endl;
}
//头插法：开辟并初始化—>>连接—->>指针后移 ！！注意特殊情况！！
bool push_front(List *list,ElemType x)
{
Node *s = (Node *)malloc(sizeof(Node));
if(s == NULL)
{
return false;
}
s->data = x;
s->next = list->first->next;
list->first->next = s;
//注意：如果是第1个结点，则尾指针需要改变指向即指向第1个结点
//（不再指向头）如果不是第1个结点，尾指针指向无需改变
if(list->size == 0)
{
list->last = s;
}
list->size++;
return true;
}
//尾删法：找到最后1个节点的先驱（指向赋空）—->尾指针指向它—>size – 1
bool pop_back(List *list)
{
if(list->size == 0)
{
cout<<"链表已空"<<endl;
return false;
}
Node *pre = list->first;
while(pre->next != list->last)//找到要删除节点（最后1个结点）的先驱
{
pre = pre->next;
}
pre->next = NULL;//由于该先驱要作为尾结点，所以其指针域得赋空
free(list->last);//释放要删除的结点
list->last = pre;//尾指针指向改变

/* pre->next = NULL;
list->last = pre;

free(pre);
pre = NULL;
// free(list->last);*/

list->size–;
return true;
}
//free(p)作用是：释放p所指向的空间，而非释放指针p！！！！！
//动态开辟的空间才需要手工释放，其他的空间系统自动回收

//头删法：释放第1个节点->size⑴(如果只有1个节点，释放它以后尾指针得指向头结点)，其他情况尾指针不变
bool pop_front(List *list)
{
if(list->size == 0)
{
cout<<"链表已空"<<endl;
return false;
}
Node *p = list->first->next;//p指向要释放的第1个节点
list->first->next = p->next;//头指针指向下1个节点
free(p); //释放第1个节点
if(list->size == 1)
{
list->last = list->first;//如果只有1个节点，释放它以后尾指针得指向头结点)，其他情况尾指针不变
}
list->size–;
return true;
}
//查找函数

/*Node *find(List *list,ElemType x)
{
Node *p = list->first->next;//p指向第1个节点
while(p != NULL)
{
if(x == p->data)
return p;
else
p = p->next;
}
return NULL;
}*/
Node *find(List *list,ElemType x)
{
Node *p = list->first->next;//p指向第1个节点
while(p!=NULL && p->data!= x)
{
p = p->next;
}
return p;//while循环退出条件：没找到则–>p=NULL,找到p为指向所寻觅节点的指针
}
//修改函数
bool modify(List *list,ElemType x)
{
ElemType item;
Node *p = find(list,x);
if(p != NULL)
{
cin>>item;
p->data = item;
cout<<"it is modified"<<endl;
return true;
}
else
cout<<"it's not exist!"<<endl;
}
//按值删除结点
void delete_val(List *list,ElemType x)
{
Node *p = find(list,x); //找到要删除的结点
if(p != NULL)
{
if(p == list->first->next)//如果是第1个结点（头删法）
{
pop_front(list);
}
else if(p == list->last) //如果是最后1个结点（尾删法）
{
pop_back(list);
}
else //既不是第1个结点，也不是最后1个节点
{
p->data = p->next->data;//将要删除的结点的data赋值为下1个节点的data
p->next = p->next->next;//连接
free(p->next); //将要删除的结点的下1个结点释放
}
/*else //既不是第1个结点，也不是最后1个节点
{
Node *pre = list->first;
while(pre->next != p)//找到要删除节点的先驱
{
pre = pre->next;
}
pre->next = p->next;//连接
free(p); //释放要删除的结点
}*/
list->size–;
cout<<"it is deleted!"<<endl;
}
else
{
cout<<"it is not exist!"<<endl;
}

}
//清空单链表
/*void clear(List *list,ElemType x)
{
for(int i=0;i<list->size;++i)
{
pop_back(list);//或pop_front(list)
}
}*/
void clear(List *list)
{
Node *p = list->first->next;//p指向第1个节点
while(p != NULL)
{
list->first->next = p->next;//分离出第1个结点
free(p);//将第1个节点释放
p = list->first->next;//又指向第1个节点(连续删除第1个结点)
}
list->last = list->first; //尾指针和头指针都指向头结点
list->size = 0;
}
//烧毁链表
void destroy(List *list)
{
clear(list);//清空链表
free(list->first);//头结点释放
list->first = list->last = NULL;//头（尾）指针赋空，避免成为野指针
}
//求链表长度
int length(List *list)
{
return list->size;
}
//链表逆至
/*改变指针的指向*/
void resver(List *list)
{
Node *pre = list->first->next;//pre指向第1个节点
Node *p = pre->next; // p指向第2个结点
pre->next = NULL; //逆序以后第1个节点成为最后1个节点，所以next=NULL
while(p != NULL)
{
Node *pre1 = pre;//将当前的指向保存下来
Node *p1 = p;

pre = p; //为下1次（第n⑴次）交换做准备（必须在指向改变以后进行！！！！！）
p = p->next;

p1->next = pre1;//交换当前两个(第n次)后1个指向前1个
}
list->first->next = pre; //退出循环，p=NULL,pre指向原来的最后1个结点（逆序后成为第1个）

}
/*交换值*/
/*void resver(List *list)
{
Node *left = list->first->next;
Node *right = list->last;
Node *p = list->first;
while(left != right)
{
left->data = left->data + right->data;//对称的两个数交换
right->data = left->data – right->data;
left->data = left->data – right->data;

while(p->next != right)//找到倒数第2个结点
{
p = p->next;
}

right = p;//为下1次交换做准备
left = left->next;
}
}*/
//求某个值的先驱
void prio(List *list,ElemType x)
{
Node *p = find(list,x);
if(p == NULL)
{
cout<<"it is not exist!
"<<endl;
}
if(p == list->first->next)
{
cout<<"it does not have next"<<endl;
}
else
{
Node *pre = list->first;
while(pre->next != p)
{
pre = pre->next;
}
cout<<"it's prio is found"<<endl;
cout<<"it is"<<pre->data<<endl;;
}
}
//求某个值的后继
void next(List *list,ElemType x)
{
Node *p = find(list,x);
if(p == NULL)
{
cout<<"it is not exist!
"<<endl;
}
if(p == list->last)
{
cout<<"it does not have next"<<endl;
}
else
{
cout<<"it's next is found"<<endl;
cout<<"it is"<<p->next->data<<endl;
}
}

main.cpp:

#include"List.h"
void main()
{
List mylist;
InitList(&mylist);

int select = 1;
ElemType item;
Node *p = NULL;

while(select)
{
cout<<"**********************************"<<endl;
cout<<"* [1] push_back [2] push_front *"<<endl;
cout<<"* [3] show_seqlist[0] quit_system*"<<endl;
cout<<"* [4] pop_back [5] pop_front *"<<endl;
cout<<"* [6] find *"<<endl;
cout<<"* [7] modify [8] clear *"<<endl;
cout<<"* [9] destroy [10]delete_val *"<<endl;
cout<<"* [11] resver [12]length *"<<endl;
cout<<"* [13] prio [14]next *"<<endl;
cout<<"**********************************"<<endl;
cout<<"请选择:>";
cin>>select;
switch(select)
{
case 1:
cout<<"请输入要插入的数据(⑴结束):>";
while(cin>>item,item!=⑴)
{
push_back(&mylist,item);
}
break;
case 2:
cout<<"请输入要插入的数据(⑴结束):>";
while(cin>>item,item!=⑴)
{
push_front(&mylist,item);
}
break;
case 3:
show_seqlist(&mylist);
break;
case 4:
pop_back(&mylist);
break;
case 5:
pop_front(&mylist);
break;
case 6:
cout<<"输入你要查找的值：";
cin>>item;
p =find(&mylist,item);
if(p != NULL)
cout<<"it is found!"<<endl;
else
cout<<"it is not exit!"<<endl;
break;
case 7:
cout<<"请输入要修改的值：";
cin>>item;
modify(&mylist,item);
break;
case 8:
clear(&mylist);
break;
case 9:
destroy(&mylist);
break;
case 10:
cout<<"请输入要删除的值：";
cin>>item;
delete_val(&mylist,item);
break;
case 11:
resver(&mylist);
break;
case 12:
{
int n = length(&mylist);
cout<<"the length of the list is:"<<n<<endl;
}
break;
case 13:
cout<<"输入你要查找先驱的值：";
cin>>item;
prio(&mylist,item);
break;
case 14:
cout<<"输入你要查找后继的值：";
cin>>item;
next(&mylist,item);
break;
default:
break;
}
}
destroy(&mylist);//函数调用完以后，自动烧毁链表
}

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，请使用WINRAR解压,如遇到无法解压的请联系管理员！