顺序表之后是链表,链表是线性表的第二种结构。

(单)链表根据《数据结构》这本书 需要会写初始化、插入、查找、删除、取长度的函数。

首先是结构体的定义:

链表的每一个节点由本身的数据、下一个节点的地址组成。

typedef的意思是取别名。把lei这个小名 给int  修改线性表数据类型的时候可以直接改动
typedef int lei; struct ss { lei data; ss *next; };
第一个是初始化函数。这里写的是有头指针的链表,所以只需要new一个头结点,让头结点的next指向NULL。
ss* chushihua() { ss*L=new ss; L->next=NULL; return L; }
第二个是取长度函数。只要让一个临时指针指向头指针,然后一直遍历下去就好了,最终返回链表的长度。
int size(ss* L) { int len=0; while(L->next !=NULL) { L=L->next; len++; }
return len; }
第三个是查找函数,根据书的要求,有两种查找函数,其一是根据编号来查找。

可以让L指针一直遍历下去,当L的下一个节点为空节点或者到达所需要的编号停止。

如果这个时候L不为空切cnt==所需要的序号,就说明该节点存在,返回即可;否则返回空指针表示不存在。
ss* find_num(ss *L,int xuhao) { int cnt=0; while(L->next!=NULL && cnt<xuhao) {
L=L->next; cnt++; } if(cnt==xuhao && L) return L; return NULL; }
其二是根据值查找,这个就比较无脑了,一直遍历下去,直到找到或者找到结尾,如果找到就会返回,没找到也会自然而然的返回空指针。
ss* find_data(ss* L,lei data) { L=L->next; while(L && L->data!=data) {
L=L->next; } return L; }
第四个是插入函数。先查找这个位置是否可以查,如果存在该位置的前一个为空的情况,就返回错误。

否则new一个新节点,新的节点的下一个指向现在n-1的节点的下一个,让现在n-1的节点指向新的节点,就这样转接完成,返回true。
bool charu(ss* L,lei data,int weizhi) { ss *a; ss *b=L; int cnt=0; while(b &&
cnt < weizhi - 1 ) { b=b->next; cnt++; } if(b==NULL||cnt!=weizhi - 1) {
cout<<"插入位置错误"<<endl; return false; } a=new ss; a->data=data; a->next=b->next;
b->next=a; return true; }
第五个是删除函数。

先找到需要删除节点的前一个位置,如果发现要删除的节点不存在,则返回false。

如果存在,让删除节点的前一个节点的next指向需要删除节点的next,然后把需要删除的节点释放掉就可以了。
bool shanchu(ss *L,int weizhi) { ss *a; ss *b=L; int cnt=0; while(b &&
cnt<weizhi-1) { b=b->next; cnt++; } if(b==NULL ||b->next == NULL|| cnt!=weizhi
- 1) { cout<<"删除错误"<<endl; return false; } a=b->next; b->next = a->next;
free(a); return true; }
接下来是全部代码:
#include<iostream> #include<algorithm> #include<cstring> using namespace std;
typedef int lei; struct ss { lei data; ss *next; }; ss* chushihua() { ss*L=new
ss; L->next=NULL; return L; } int size(ss* L) { int len=0; while(L->next
!=NULL) { L=L->next; len++; } return len; } ss* find_num(ss *L,int xuhao) { int
cnt=0; while(L->next!=NULL && cnt<xuhao) { L=L->next; cnt++; } if(cnt==xuhao &&
L) return L; return NULL; } ss* find_data(ss* L,lei data) { L=L->next; while(L
&& L->data!=data) { L=L->next; } return L; } bool charu(ss* L,lei data,int
weizhi) { ss *a; ss *b=L; int cnt=0; while(b && cnt < weizhi - 1 ) { b=b->next;
cnt++; } if(b==NULL||cnt!=weizhi - 1) { cout<<"插入位置错误"<<endl; return false; }
a=new ss; a->data=data; a->next=b->next; b->next=a; return true; } bool
shanchu(ss *L,int weizhi) { ss *a; ss *b=L; int cnt=0; while(b && cnt<weizhi-1)
{ b=b->next; cnt++; } if(b==NULL ||b->next == NULL|| cnt!=weizhi - 1) {
cout<<"删除错误"<<endl; return false; } a=b->next; b->next = a->next; free(a);
return true; } int main() { ss *L=chushihua(); cout<<"该链表的长度为:"<<size(L)<<endl;
charu(L,1,1); charu(L,3,2); charu(L,5,3); cout<<"该链表的长度为:"<<size(L)<<endl;
cout<<"编号为1的元素的地址:"<<find_num(L,1)<<endl;
cout<<"编号为2的元素的地址:"<<find_num(L,2)<<endl; cout<<"值为3的元素的地址
:"<<find_data(L,3)<<endl; cout<<"该链表的长度为:"<<size(L)<<endl; cout<<"删除最后一个元素
"<<endl; shanchu(L,3); cout<<"该链表的长度为:"<<size(L)<<endl; return 0; }
 

技术
©2019-2020 Toolsou All rights reserved,
数字滚动抽奖小程序VaR - 风险价值 - 蒙特卡罗法 - Python百度网盘偷偷更新,终于实现免费不限速了! Chrome OS,对程序员和Windows意味着什么?,互联网营销华为Mate 40 Pro+ 5G曝光:徕卡电影镜头、陶瓷机身Qt学习2——.pro文件和.h文件介绍python:将一个文件转换为二进制文件(binary)第十一届蓝桥杯C/C++ 大学 B 组大赛软件类省赛网站手机号码抓取方式蚂蚁集团香港IPO获得中国证监会批准