本文主要是介绍单链表C/C++实现(数据结构严蔚敏),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
下面是项目:头文件、源文件、测试文件
1、头文件LinkList.h:
#include<iostream>
#include<malloc.h>
using namespace std;#define ok 1
#define error 0
#define flow 0typedef int Status;
typedef int ElemType;typedef struct LNode{ElemType data;struct LNode* next;}LNode;
typedef LNode* LinkList;//初始化链表
Status InitList( LinkList& L, int n);//销毁链表
Status DestroyList(LinkList& list);//打印链表
Status Print(const LinkList& L); //在第i个位置前添加数据节点
Status ListInsert( LinkList& L, int i, ElemType e) ;//删除第i个位置的节点
Status ListDelete( LinkList& L, int i, ElemType& e);//获取链表的第i个位置数据,并返回
Status Get( const LinkList& L, int i, ElemType& e);//将递增的LA和LB进行归并,重新放入LC中
Status MergeList( LinkList& La, LinkList& Lb, LinkList& Lc);
2、源文件LinkList.cpp
#include "LinkList.h"//使用头节点反序初始化链表
Status InitList( LinkList& L, int n){L = (LinkList)(malloc( n * sizeof(LNode)));if(!L) return error;L->next = NULL;cout<<"请输入"<<n<<"个数据节点的数据\n"<<endl;for(int i=0; i < n; i++){LinkList p = (LinkList)(malloc(sizeof(LNode)));cin>>p->data;p->next = L->next;L->next = p;}return ok;
}//打印链表 ,由于初始化是按照头指针进行的,所以打印出来的是倒叙链表
Status Print(const LinkList& L){LinkList p = L->next;if(!p) return error;while(p){cout<<p->data<<" ";p=p->next; }cout<<endl;return ok;
}//销毁链表
Status DestroyList( LinkList& L){}//在第i个位置前添加数据节点
Status ListInsert(LinkList& L, int i, ElemType e){LinkList p = L;int j = 0;//找到第i-1个节点的地址放入p中 while(p && j < i-1){p = p->next; j++;}//第i-1个节点不存在,无法将数据e插入到第i个位置上 ,或则输入的位置小于1。返回错误。 if(!p || j > i-1) return error;//新建一个节点 LinkList s = (LinkList)malloc((sizeof(LNode)));//新建节点的数据部分是e s->data = e;//新建节点的指针域是第i个节点的地址。而第i位置的地址存储在第i-1中的指针域 p->next中中;s->next = p->next;//将第-1的指针域修改为新建节点的地址,就是s。使得第i-1的节点指针域指向新建节点 p->next = s;return ok;}//删除第i个位置的节点
Status ListDelete( LinkList& L, int i, ElemType& e){LinkList p = L;int j = 0;//寻找第i个节点的地址,放入p的指针域p->next中,p是第i-1位置的节点 while(p->next && j < i-1){p = p->next;j++;}//如果第i位置节点不存在,就返回错误 if(!(p->next) || j < i-1) return error;//让第i-1位置的p节点的指针域p->next指向第i+1位置的节点,然后释放第i位置的空间。 LinkList q = p->next;p->next = q->next;e = q->data;free(q);
}//获取链表的第i个位置数据,并返回
Status Get(const LinkList L, int i, ElemType& e){//L为头节点的地址,L->next存储的是第一个节点的地址,L->data,不存储数据。 //获取第一个节点的地址,并将计数器设置为1 LinkList p = L->next;int j = 1;//循环遍历节点 while(p && j < i){p = p->next; j++;}//如果节点的地址为NULL,或则查看的节点数大于 计数器一开始就大于了i, 说明第i个位置的数据不存在,返回错误0 if(!p || j > i){return error;}//如果存在,就赋值给e e = p->data;return ok;
}//将递增的LA和LB进行归并,重新放入LC中
Status MergeList( LinkList& La, LinkList& Lb, LinkList& Lc){//将La和Lb的第一个数据节点的地址赋值给pa, pb LinkList pa = La->next;LinkList pb = Lb->next;Lc = (LinkList)malloc(sizeof(LNode));Lc->next = NULL; LinkList pc = NULL;int i = 1;int j = 1;//如果La第一个节点的数据大于Lb的第一个数据节点,就将Lb的数据存到Lc中 while(pa && pb){ if(pa->data <= pb->data){pc = (LinkList)malloc(sizeof(LNode)); pc->data = pa->data;pc->next = Lc->next;Lc->next = pc;pa = pa->next;}else{pc = (LinkList)malloc(sizeof(LNode)); pc->data = pa->data;pc->next = Lc->next;Lc->next = pc;pb= pb->next;} }while(pa){pc = (LinkList)malloc(sizeof(LNode));pc->next = Lc->next;Lc->next = pc;pc->data = pa->data;pa = pa->next;}while(pb){pc = (LinkList)malloc(sizeof(LNode));pc->next = Lc->next;Lc->next = pc;pc->data = pb->data;pb = pb->next;}}
3、测试文件:test.cpp
#include<iostream>
#include "LinkList.h"
using namespace std;int main(void){LinkList La, Lb, Lc;ElemType e;int i, n ; InitList(La, 4);cout<<"链表创建完毕"<<endl;InitList(Lb, 4);cout<<"链表创建完毕"<<endl;MergeList(La, Lb, Lc);Print(Lc);return 0;
}
这篇关于单链表C/C++实现(数据结构严蔚敏)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!