赞
踩
多清澈这天空 晴雨相拥 同心逐梦!
坚守我信心 一路出众!!
首先,按照惯例,欢迎大家边听歌边观看本博客
▶ 紫荆花盛开 (163.com)(建议复制链接,浏览器打开,csdn打开太慢了)
2022香港回归祖国25周年主题歌曲,好听!!!
首先 大家肯定知道链表的表达方式,如下
- typedef struct LNode
- {
- ElemType data;
- struct LNode *next;
-
- }LinkNode;
定义一个LNode,node节点,结点,L是link,表示链接,所以叫做LNode链接结点构成链表
第一个存放元素的信息,链表的特点就是多存了一个节点(指针域)指向后继节点。
1.一个正常的结构体代码编写
- struct
- {
- int num;
- char name[20];
- char sex;
- float score;
- }boy1,boy2;
-
你可以直接在boy2后面打个{ }初始化,在使用boy的时候我们可以具体到一个成员如boy1.num 即为boy1结构体的num成员
然后接下来其实更加常见的定义是这样子的
- struct stu
- {
- int num;
- char name[20];
- char sex;
- float score;
- }*boy1,boy2; //boy1是结构体指针,boy2是结构体
这时候我们对指向结构体的指针标表示的成员方式有所不同,可表示为(*boy1).num或者boy1->num(熟悉吧,这里算是补充一下知识点)都可以。一般配合malloc(与free)或者c++中的new(delete)函数使用,主要是结构体指针自创立开始指向的空间就不存在,所以我们得开辟一个空间给他们.
本来吧,其实我真想按课本讲一遍,但是感觉有点浪费时间,而且课本那些加深不了我的理解,所以干脆我就直接把我的理解说了,如果有错,希望各位大佬指正!
温馨提示:接下来的话可能有点绕口令!!
第一:节(结)点
我们知道一个节点包括了他的数据域和他的指针域
数据域存放他的data,指针域存放下一个节点的地址,其中在第一个的叫做头结点,头结点链接的第一个节点叫做首节点,最后一个节点叫做尾结点。经常会出现R指针,我管他叫标记指针,用于记住我们要操作的节点的下一个地址,免得链表丢失,至少现在我知道的就是这点,其中^表示NULL。
ok,接下来,来解决几个知识,保证我们看得到接下来的代码,懂了应该就会写了吧
1.1:比如Lode *r=L;让r指向头结点L。
1.2:pre=p;(pre和p都是指针),让pre指向p(指向的地址)
1.3:p=p->next p指向下一位(详细一点:p->next在等号后面表示解引用,指的是p指向的结构体的指针域的地址(表示这个结构体的下一个地址))
1.4:r->next=p 这个指的是让r对应的结构体指向p(而非指针r指向p,此时的r相当于标记指针)
1.5:s->next=p->next;p->next=s;像这种我们就推荐画图理解
1.6:p=L->next->next表示p指向L的下下指针域而L->next->next=NULL则指的是L的下一个节点的指针域为空,如下图所示
相信大家已经对链表有了初步的了解,现在我们来一个一个实现他们
- typedef char ch
- typedef struct LNode
- {
- ch data;
- struct LNode* next;
- }Linknode;
- 初始化
- void InitLnode(LinkNode *&L){
- L=new LinkNode;
- L->next=NULL;
- }
这里就不得不讲讲插入的两种方法
思路示意图如下:
- LinkList Headinster(LinkList &L,int n){
- LNode *s;
- int x=1;
- L= (LinkList)malloc(sizeof(LNode));
- L->data=x++;
- L->next=NULL;
- while(x!=n){
- s=(LNode*) malloc(sizeof(LNode));
- s->data=x;
- s->next=L;
- L=s;
- x++;
- }
- return L;
- }
核心代码
- s->next=L->next; ①
- L->next=s; ②
作用效果就是从头结点和首节点插入新的元素,从而导致先插进来的反而在后面
这里借用一下大佬的动图(侵权删)
顾名思义就是从尾部开始插入由于新的节点插入后成为新的尾部,所以我们需要用一个指针R去更新尾部节点(始终指向尾部)
大概像这样子
- LinkList TailInster(LinkList &L,int n){
- int x=1;
- L= (LinkList)malloc(sizeof(LNode));
- LNode *s,*r=L;
- while(x!=n){
- s=(LNode*) malloc(sizeof(LNode));
- s->data=x;
- r->next=s;
- r=s;
- x++;
- }
- r->next=NULL;
- return L;
- }
核心代码
- r->next=s; //①r的指针域指向S(让新结点插入到链表)
- r=s; //②r指针指向s(保持r指针一直在链表尾端,方便插入新的结点)
那么 现在我们继续写这个尾插法
- //插入(使用尾插法)
- void InsertLnode(LinkNode *&L,ch a[],int n)
- {
- LinkNode *s,*r;
- r=L;
- for(int i=0;i<n;i++)
- {
- s=new LinkNode;
- s->next=a[i];
- r->next=s;
- r=s;
- }
- r->next=NULL;
- }
- void DisplayLinkNode(LinkNode *L)
- {
- LinkNode *p=L->next;
- while(p!=NULL)
- {
- cout<<p->data<<" ";
- p=p->next;
- }
- cout<<endl<<endl;
- }
2.4链表的长度
- int LinkNodeLength(LinkNode *L)
- {
- LinkNode *p=L;
- int n=0;
- while(p->next!=NULL)//注意头结点不算我们的链表长度
- {
- n++;
- p=p->next;
- }
- return n;
- }
2.5链表中取值
- bool Getlink(LinkNode *L,int n,ch &e)
- {
- if(n<=0)
- return false;
- LinkNode *p=L;
- int j=0;
- while(j<n&&p!=NULL)
- {
- j++;
- p=p->next;
- }
- if(p==NULL)
- return false;
- else
- {
- e=p->data;
- return true;
- }
- }

记忆方法:创建指针,遍历一下,判断是否为空,否则为可取之值
2.6链表中删除
- bool DeleteNode(LinkNode *&L,int n,ch &e)
- {
- if(n<=0)
- return false;
- LinkNode *p=L,q;
- int j=0;
- while(j<n-1&&p!=NULL)//注意删除代码停在删除元素的前面
- {
- j++;
- p=p->next;
- }
- if(p==NULL)
- return false;
- q=p->next;
- if(q==NULL)
- return false
- e=q->data;
- p->next=q->next;
- delete q;
- return true;
-
- }

记忆方法 建立两个指针,遍历到删除元素的前一个,用p指向删除元素,然后进行交换
2.7新的插入
- bool insertnode(LinkNode *&L,int i,ch e)
- {
- if(i<=0)
- return false;
- LinkNode *p=L,*s;
- int j=0;
- while(j<n&&p!=NULL)
- {
- j++;
- p=p->next;
- }
- if(p==NULL||p->next==NULL)
- return false;
- s=new LinkNode;
- s->data=e;
- s->next=p->next;
- p->next=s;
- return true;
- }

记忆方法:创建一个新节点,类似头插法的方式插进去
- #include <iostream>
- using namespace std;
- typedef char ch;
- typedef struct LNode {
- ch data;
- struct LNode*next;//指针域:存放下一个节点的地址
- } LinkNode;
- //初始化
- void InitList(LinkNode *&L) {
- L = new LinkNode;
- L->next = NULL;
- }
- //插入(尾插法)
- void Insertlist(LinkNode *&L, ch a[], int n) { //传入想插入的数组(1,2,3,4),则此法插完后亦是(1,2,3,4)
- LinkNode *s, *r; //创建两个指针
- r = L; //r指向首节点L
- for (int i = 0; i < n; i++) {
- s = new LinkNode; //创建空间
- s->data = a[i]; //数据存储(值得注意的是s是指针)
- r->next = s; //r->next表示L的next指针域,其实就是赋值,将s的地址(s本身就是地址)赋给L的next域,相当于是L--s
- r = s; //然后将r指向s
- }
- r->next = NULL; //最后r指向末节,指针域为NULL
- }
- //输出
- void Displaylist(LinkNode *L) {
- LinkNode *p = L->next; //这里注意一下,其实首节点是没有数据的,直接指向下一个节点打印
- while (p != NULL) {
- cout << p->data << " ";
- p = p->next;
- }
- cout << endl << endl;
- }
- //输出长度
- int Listlength(LinkNode *L) {
- int n = 0;
- LinkNode *p = L;
- while (p->next != NULL) {
- n++;
- p = p->next;
- }
- return n;
- }
- //判断是否为空
- bool emptyelem(LinkNode *L) {
- if (L->next == NULL)
- return false;
- else
- return true;
- }
- //取值
- bool Getelem(LinkNode *L, int n, ch &e) {
- if (n <= 0)
- return false;
- LinkNode *p = L;
- int j = 0;
- while (j < n && p != NULL) {
- j++;
- p = p->next;
- }
- if (p == NULL)
- return false;
- e = p->data;
- return true;
- }
- //输出位置
- int Locelem(LinkNode *L, ch e) {
- LinkNode *p = L->next;
- int j = 1;
- while (p != NULL && p->data != e) {
- p = p->next;
- j++;
- }
- if (p == NULL) {
- return 0;
- }
-
- return j;
- }
- //指定位置插入元素
- bool insertlist(LinkNode *&L, int n, ch q) {
- if (n <= 0)
- return false;
- int j = 0;
- LinkNode *p = L, *s;
- while (j < n - 1 && p != NULL) {
- j++;
- p = p->next;
- }
- if (p==NULL||p->next == NULL)
- return false;
- else {
- s = new LinkNode;
- s->data = q;
- s->next = p->next;
- p->next = s;
- return true;
- }
- }
- //删除指定元素
- bool Delem(LinkNode *&L, int n, ch &e) {
- if (n <= 0)
- return false;
- int j = 0;
- LinkNode *p = L, *q;
- while (j < n - 1 && p != NULL) {
- j++;
- p = p->next;
- }
- if (p == NULL)
- return false;
- q = p->next;
- if (q == NULL)
- return false;
- e = q->data;
- p->next = q->next;
- delete q;
- return true;
- }
- //释放
- void Destroylist(LinkNode *&L) {
- delete L;
- }
-
- int main() {
- LinkNode *L1;
- InitList(L1);
- cout << "1.初始化单链表成功!!!" << endl << endl;
- //插入
- ch a[10] = {'a', 'b', 'c', 'd', 'e'};
- cout << "2.依次插入abcde." << "尾插法" << " ";
- Insertlist(L1, a, 5);
- cout << "插入成功!!!" << endl << endl;
- //打印
- cout << "3.当前的单链表为: ";
- Displaylist(L1);
- //输出长度
- int n = Listlength(L1);
- cout << "4.当前单链表的长度为:" << n << endl << endl;
- //判断链表是否为空
- cout << "5.当前链表";
- if (emptyelem(L1))
- cout << "不为空表" << endl << endl;
- else
- cout << "为空表" << endl << endl;
- //取值(输出元素)
- cout << "6.取值操作:"; int l;ch e;
- cout << "请输入您要取哪个位置的值:";cin >> l;
- if (Getelem(L1, l, e))
- cout << "取值成功! " << "单链表第" << l << "位的元素是:" << e << endl << endl;
- else
- cout << "取值失败,您输入的位置" << l << "越界!!!" << endl << endl;
- //查找
- cout << "7.查找操作:";ch find;
- cout << "请输入您要查找的元素: ";
- cin >> find;
- if (Locelem(L1, find) == 0)
- cout << "对不起,当前单链表中没有您查找的元素!!" ;
- else
- cout << "查找成功,您所查找的元素" << find << "在当前单链表的第" << Locelem(L1, find) << "位" ;
- cout<<endl<<endl;
- cout << "8.插入操作:";int k;ch q;
- cout << "请您输入一个数字和一个字符,代表在第几位插入一个字符:";cin >> k;cin >> q;
- if (!insertlist(L1, k, q))
- cout << "Warning:输入序号越界,插入失败!!!" << endl;
- else
- cout << "插入成功!!!" << endl << endl;
- cout << "9.当前单链表的元素有:";
- Displaylist(L1);
- cout << "10.删除操作:";int y;ch o;
- cout << "请您输入要删除的元素的序号:";cin >> y;
- if (!Delem(L1, y, o))
- cout << "对不起,您的输入的序号有误(越界),删除失败!" << endl << endl;
- else
- cout << "删除成功!成功删除第" << y << "个元素" << o << endl << endl;
- cout << "11.当前单链表的元素有:";Displaylist(L1);
- //释放
- cout << "12.销毁单链表:";Destroylist(L1);
- cout << "销毁成功!!!";
- return 0;
- }

全部失败的样例:9,p,8p,7
全部成功的样例:4,c,2p,6
所以建议大家自己打吧,看完上面的写这个代码就很轻松
感谢您今天的捧场,敬请期待下次演出。 See you next illusion.
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。