单链表
现在已经进入专业课复习，王道的数据结构复习指导的第一个数据结构虽然是顺序表，但是过于简单，就不想写了。现在复习到链表，首先单链表数其他链表的基础。所以首先把单链表所有基础操作全部写一遍。包括建表，插入，删除，逆序，判断是否为空，合并等。我这里写的是带有头结点的单链表，头结点保存链表长度。
代码如下：
#include <iostream>
using namespace std;
//带头结点的单链表类，头结点存放单链表长度
class Single_List{
private:
int data;
Single_List* next;
public:
//单链表的创建函数，尾插法
Single_List* Create(int len){
Single_List* prev,*head,*tail;
head = new Single_List;
head->data = len;
head->next = NULL;
prev = head;
if(len == 0){
goto end;
}
cout<<"请输入各个结点的数值："<<endl;
while(len--){
int data;
tail = new Single_List;
cin>>data;
this->attach(prev,tail,data);
prev = tail;
}
end: return head;
}
void attach(Single_List* prev,Single_List* tail,int data){
tail->next = NULL;
tail->data = data;
prev->next = tail;
}
int getLength(Single_List* list){
return list->data;
}
//判断单链表是否为空的函数
bool Isempty(Single_List* list){
return list->data == 0;
}
//单链表的打印函数
void Print(Single_List* list){
if(list->Isempty(list)){
cout<<"单链表为空"<<endl;
return;
}
int len = list->data;
Single_List* ptrl = list->next;
for(int i = 0 ; i < len ; i++){
cout<<ptrl->data<<" ";
ptrl = ptrl->next;
}
}
//在第index个结点后面插入数值为data的结点的函数
Single_List* Insert(Single_List* list,int index ,int data){
Single_List* prev = list;
Single_List* insert;
insert = new Single_List;
int len = list->getLength(list);
//链表为空时,无论index为多少，只能插在第一个位置
if(this->Isempty(list)){
this->attach(prev,insert,data);
list->data++;
return list;
}
//如果插入的位置大于等于链表长度直接插到末尾，
index = (list->data <= index)?list->data:index;
for(int i = 0 ; i < index ; i++){
prev = prev->next;
}
insert->data = data;
insert->next = prev->next;
prev->next = insert;
list->data++;
return list;
}
//寻找第k个结点的函数,只适用链表不为空的情况
Single_List* Findkth(Single_List* list ,int k){
Single_List* prev;
prev = list;
for(int i = 0 ; i < k ; i++){
prev = prev->next;
}
return prev;
}
//寻找数值为N的结点的函数
int FindN(Single_List* list,int N){
int result = -1;
Single_List* prev;
prev = list;
int len = this->getLength(list);
for(int i = 0 ; i < len ; i++){
prev = prev->next;
if(prev->data == N){
result = i;
break;
}
}
return result;
}
//删除数值为N的结点的函数
void DeleteN(Single_List* list,int N){
int index = this->FindN(list,N);
//不存在数值为N的情况
if(index == -1){
cout<<"单链表不存在数值为"<<N<<"的结点"<<endl;
return;
}
this->Deletekth(list,index+1);
}
//删除第k个结点的函数
void Deletekth(Single_List* list,int k){
int len = list->data;
if(this->Isempty(list)){
cout<<"单链表为空无法删除"<<endl;
return;
}
Single_List* del_pre;
del_pre = this->Findkth(list,k-1);
del_pre->next = del_pre->next->next;
list->data--;
}
//逆转链表函数
Single_List* Reverse(Single_List* list){
//单链表为空时
if(this->Isempty(list)){
return list;
}
Single_List* head,*front,*rear,*tag;
head = list; //保存头结点
//front，rear用于逆转，tag用于记录未逆转的链表
front = list->next;
rear = front->next;
front->next = NULL;
while(rear){
tag = rear->next;
rear->next = front;
front = rear;
rear = tag;
}
head->next = front;
return head;
}
//对两个升序链表进行升序合并函数
Single_List* Merge(Single_List* list1,Single_List* list2){
if(list1 == NULL){
return list1;
}
if(list2 == NULL){
return list2;
}
Single_List* list; //建立合并链表的头结点，存放两个链表长度之和
list = new Single_List;
list->data = list1->data+list2->data;
list->next = NULL;
Single_List* prev1,*prev2,*tail,*head,*tag;
prev1 = list1->next; //指向list32的第一个结点（不是存放长度的头结点，即头结点之后的结点）
prev2 = list2->next;
head = new Single_List; //建立新链表的空头结点
tag = head; //保存空头结点的地址
head->next = NULL;
while(prev1 && prev2){
tail = new Single_List;
if(prev1->data <= prev2->data){
this->attach(head,tail,prev1->data);
head = tail;
prev1 = prev1->next;
}else{
this->attach(head,tail,prev2->data);
head = tail;
prev2 = prev2->next;
}
}
if(prev1){
head->next = prev1;
}
if(prev2){
head->next = prev2;
}
list->next = tag->next;
return list;
}
//链表排序，冒泡排序
Single_List* Sort(Single_List* list){
Single_List* head,*prev1,*prev2;
head = list;
prev1 = list->next;
while(prev1){
prev2 = prev1->next;
while(prev2){
if(prev1->data > prev2->data){
prev1->data += prev2->data;
prev2->data = prev1->data - prev2->data;
prev1->data -= prev2->data;
}
prev2 = prev2->next;
}
prev1 = prev1->next;
}
return head;
}
};
int main()
{
cout<<"请输入初始化单链表的长度:"<<endl;
int len;
Single_List tmp;
Single_List* list;
cin>>len;
list = tmp.Create(len);
cout<<"单链表如下："<<endl;
tmp.Print(list);
cout<<endl;
cout<<"排序后为:"<<endl;
list = tmp.Sort(list);
tmp.Print(list);
cout<<endl;
cout<<"请输入初始化单链表的长度:"<<endl;
Single_List* list1;
cin>>len;
list1 = tmp.Create(len);
cout<<"第二个单链表如下："<<endl;
tmp.Print(list1);
cout<<endl;
cout<<"排序后为:"<<endl;
list1 = tmp.Sort(list1);
tmp.Print(list1);
cout<<endl;
cout<<"合并后链表为:"<<endl;
Single_List* merge_list = tmp.Merge(list,list1);
tmp.Print(merge_list);
cout<<endl;
cout<<"请输入插入结点的位置："<<endl;
int index,data;
cin>>index;
cout<<"插入前单链表如下："<<endl;
tmp.Print(list);
cout<<endl<<"请输入插入结点的数值："<<endl;
cin>>data;
list = tmp.Insert(list,index,data);
cout<<"插入后单链表如下："<<endl;
tmp.Print(list);
cout<<endl;
cout<<"请输入删除结点的位置："<<endl;
cin>>index;
cout<<"删除前单链表如下："<<endl;
tmp.Print(list);
tmp.Deletekth(list,index);
cout<<endl<<"删除后单链表如下："<<endl;
tmp.Print(list);
cout<<endl;
cout<<"请输入删除结点的数值："<<endl;
cin>>data;
cout<<"删除前单链表如下："<<endl;
tmp.Print(list);
tmp.DeleteN(list,data);
cout<<endl<<"删除后单链表如下："<<endl;
tmp.Print(list);
cout<<endl;
cout<<"逆转单链表前,单链表如下："<<endl;
tmp.Print(list);
cout<<endl<<"逆转单链表后,单链表如下："<<endl;
list = tmp.Reverse(list);
tmp.Print(list);
return 0;
} 代码和截图有点不一样，因为功能写的太多了，每个功能截个图，但把所有功能跑一边很麻烦。所以截图是只运行了一个功能，其他给注释了，请谅解。 创建与排序功能： 链表为空时（这里不包含头结点）
链表不为空时
合并功能（这里是2个升序序列的合并）
插入功能： 链表为空时的插入：
插入到链表末尾的情况，此时链表非空：
插入到中间的情况：
按位置删除的情况：
按值删除的情况：
逆序功能：
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017-08-13，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
