【郝斌数据结构自学笔记】27-29_链表插入和删除算法的演示_复习

墨蓝 2022-08-10 10:54 278阅读 0赞

27\_如何学习算法自己的一些感想

28\_链表插入和删除算法的演示

\#include<stdio.h>

\#include<malloc.h>

\#include<stdlib.h>

typedefstruct Node

int data;//数据域

struct Node \* pNext;//指针域

\}NODE,\*PNODE;//NODE等价于structNode，PNODE等价于struct Node \*

//函数声明

PNODEcreate\_list(void);

voidtraverse\_list(PNODE pHead);

boolis\_empty(PNODE pHead);

intlength\_list(PNODE);

boolinsert\_list(PNODE,int,int);

booldelete\_list(PNODE,int,int\*);

voidsort\_list(PNODE);

intmain(void)

PNODE pHead=NULL;//等价于structNode \*pHead=NULL；

int val;

pHead=create\_list();//creat\_list()功能：创建一个非循环单链表,并将该链表的头节点的地址付给pHead

traverse\_list(pHead);

int len=length\_list(pHead);

printf("链表长度是%d\\n",len);

if(is\_empty(pHead))

printf("链表为空！\\n");

else

printf("链表不空！\\n");

sort\_list(pHead);

traverse\_list(pHead);

insert\_list(pHead,4,33);

traverse\_list(pHead);

if (delete\_list(pHead,4,&val))

printf("删除成功，您删除的元素是：%d\\n",val);

else

printf("删除失败！您删除的元素不存在!\\n");

traverse\_list(pHead);

return 0;

PNODEcreate\_list(void)

int len;//用来存放有效节点的个数

int i;

int val;//用来临时存放用户输入的节点的值

//分配了一个不存放有效数据的头节点

PNODEpHead=(PNODE)malloc(sizeof(NODE));

if(NULL==pHead)

printf("分配失败，程序终止！\\n");

exit(-1);

PNODE pTail=pHead;

pTail->pNext=NULL;

printf("请输入您需要生成的链表节点的个数：len=");

scanf("%d",&len);

for (i=0;i<len;i++)

printf("请输入第%d个节点的值:",i+1);

scanf("%d",&val);

PNODEpNew=(PNODE)malloc(sizeof(NODE));

if(NULL==pNew)

printf("分配失败，程序终止！\\n");

exit(-1);

pNew->data=val;//挂

pTail->pNext=pNew;

pNew->pNext=NULL;

pTail=pNew;

return pHead;

voidtraverse\_list(PNODE pHead)

PNODE p=pHead->pNext;

while(NULL!=p)

printf("%d",p->data);

p=p->pNext;//不连续，不能用p++

printf("\\n");

return;

boolis\_empty(PNODE pHead)

if(pHead->pNext==NULL)

return true;

else

return false;

intlength\_list(PNODE pHead)

PNODE p=pHead->pNext;

int len=0;

while(NULL!=p)

len++;

p=p->pNext;

return len;

voidsort\_list(PNODE pHead)

int i,j,t;

int len=length\_list(pHead);

PNODE p,q;

for(i=0,p=pHead->pNext;i<len-1;++i,p=p->pNext)

for(j=i+1,q=p->pNext;j<len;++j,q=q->pNext)

if(p->data>q->data)//类似于数组中的：a\[i\]>a\[j\]

t=p->data;//类似于数组中的： t=a\[i\];

p->data=q->data;//类似于数组中的： a\[i\]=a\[j\];

q->data=t;//类似于数组中的： a\[j\]=t;

//在pHead所指向链表的第pos个节点的前面插入一个新的节点，新节点的值是val，并且pos的值是从1开始

boolinsert\_list(PNODE pHead,int pos,int val)

int i=0;

PNODE p=pHead;

while(NULL!=p&&i<pos-1)

p=p->pNext;

\++i;

if(i>pos-1||NULL==p)

return false;

PNODE pNew=(PNODE)malloc(sizeof(NODE));

if(NULL==pNew)

printf("动态分配内存失败！\\n");

exit(-1);

pNew->data=val;

PNODE q=p->pNext;

p->pNext=pNew;

pNew->pNext=q;

return true;

booldelete\_list(PNODE pHead,int pos,int\* pVal)

int i=0;

PNODE p=pHead;

while(NULL!=p->pNext&&i<pos-1)

p=p->pNext;

\++i;

if(i>pos-1||NULL==p->pNext)

return false;

PNODE q=p->pNext;

\*pVal=q->data;

//删除p节点后面的节点

p->pNext=p->pNext->pNext;

free(q);

q=NULL;

![SouthEast][]

29\_复习

数据结构

狭义：

数据结构是专门研究数据存储的问题

数据的存储包含两方面：个体的存储+个体关系的存储

广义：

数据结构既包括数据的存储也包括数据的操作

对存储数据的操作就是算法

算法

狭义：

算法是和数据的存储方式密切相关

广义：

算法和数据的存储方式无关

这就是泛型思想

数据的存储方式有几种

线性

连续存储【数组】

优点

存取速度很快

缺点

事先需要知道数组的长度

插入删除元素很慢

空间通常有限制

需要大块连续的内存块

离散存储【链表】

优点

空间没有限制

插入删除元素很快

缺点

存取速度很慢

线性结构的应用--栈

线性结构的应用--队列

非线性

树

图

[SouthEast]: /images/20220731/c41bf00718fa4d399d5eeb17ba68897a.png

【郝斌数据结构自学笔记】27-29_链表插入和删除算法的演示_复习

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关【郝斌数据结构自学笔记】27-29_链表插入和删除算法的演示_复习

相关【郝斌数据结构自学笔记】25_判断链表是否为空和求链表长度算法的演示

相关【郝斌数据结构自学笔记】24_链表创建和链表遍历算法的演示

相关【郝斌数据结构自学笔记】16-23_链表的定义与分类_链表节点插入与删除_每一个链表节点的数据类型该如何表示的问题

相关【郝斌数据结构自学笔记】14-15_链表的重要性_typedef的用法

相关【郝斌数据结构自学笔记】12-13_连续存储数组的算法演示

相关【郝斌数据结构自学笔记】8_结构体的使用概述

相关【郝斌数据结构自学笔记】1-4_数据结构定义及特点

相关【郝斌数据结构自学笔记】5_预备知识_指针_2

相关郝斌数据结构1线性表