数据结构学习笔记
关于链表的程序改写（C语言----C++）
1、郝斌的C语言代码
#includestdio.h
#includemalloc.h
#includestdlib.h
typedefstructNode
{
intdata;//数据域
structNode*pNext;//指针域
}NODE,*PNODE;//NODE等价于structNode，PNODE等价于structNode*
//函数声明
PNODEcreate_list(void);
voidtraverse_list(PNODEpHead);
boolis_empty(PNODEpHead);
intlength_list(PNODE);
boolinsert_list(PNODE,int,int);
booldelete_list(PNODE,int,int*);
voidsort_list(PNODE);
intmain(void)
PNODEpHead=NULL;//等价于structNode*pHead=NULL；
intval;
pHead=create_list();//creat_list()功能：创建一个非循环单链表,并将该链表的头节点的地
址付给pHead
traverse_list(pHead);
intlen=length_list(pHead);
printf("链表长度是%d\n",len);
if(is_empty(pHead))
printf("链表为空！\n");
else
printf("链表不空！\n");
sort_list(pHead);
insert_list(pHead,4,33);
if(delete_list(pHead,4,val))
printf("删除成功，您删除的元素是：%d\n",val);
}
printf("删除失败！您删除的元素不存在!\n");
return0;
PNODEcreate_list(void)
intlen;//用来存放有效节点的个数
inti;
intval;//用来临时存放用户输入的节点的值
//分配了一个不存放有效数据的头节点
PNODEpHead=(PNODE)malloc(sizeof(NODE));
if(NULL==pHead)
printf("分配失败，程序终止！\n");
exit(-1);
PNODEpTail=pHead;//尾节点指向头节点,因为创造了0个节点,那么头节点就是尾节点
pTail-pNext=NULL;//0个节点那么没有下一个节点,则节点指针域指向NULL
printf("请输入您需要生成的链表节点的个数：len=");
scanf("%d",len);
for(i=0;ilen;i++)//for每循环一次就创造新的节点
printf("请输入第%d个节点的值:",i+1);
scanf("%d",val);
PNODEpNew=(PNODE)malloc(sizeof(NODE));//创造新的节点
if(NULL==pNew)
pNew-data=val;//挂，//新节点中数据域中的值
pTail-pNext=pNew;//尾节点的指针域保存新节点的指针(地址)
pNew-pNext=NULL;//新节点的指针域指向NULL
pTail=pNew;//新节点添加在旧链表的末尾，变成尾节点。
returnpHead;
voidtraverse_list(PNODEpHead)
PNODEp=pHead-pNext;//头节点的指针域，指向第一个节点的指针（地址）
while(NULL!=p)//最后一个节点指针域为NULL
printf("%d",p-data);//节点数据域中的数据
p=p-pNext;//下一个节点的指针域。不连续，不能用p++
printf("\n");
return;
boolis_empty(PNODEpHead)
if(pHead-pNext==NULL)//头节点指针域为NULL则链表为空
returntrue;
returnfalse;
intlength_list(PNODEpHead)//和遍历链表算法一样,只是在遍历链表时用一个变量++就行
intlen=0;
len++;//节点数自增
returnlen;//节点数
voidsort_list(PNODEpHead)//选择排序
//for(i=0;ilen-1;++i)//两两比较只需要比较len-1次
//{
//for(j=i+1;jlen;++j)//从第i+1个开始进行比较
//if(aa[j])//两数互换，大右小左，两杯水互换,引入第三个杯子temp
//temp=a;
//a=a[j];
//a[j]=temp;
//}
inti,j,t;
PNODEp,q;
for(i=0,p=pHead-pNext;ilen-1;++i,p=p-pNext)//两两比较只需要比较len-1次
for(j=i+1,q=p-pNext;jlen;++j,q=q-pNext)//从第i+1个开始进行比较
if(p-dataq-data)//类似于数组中的：aa[j]
t=p-data;//类似于数组中的：t=a;
p-data=q-data;//类似于数组中的：a=a[j];
q-data=t;//类似于数组中的：a[j]=t;
//在pHead所指向链表的第pos个节点的前面插入一个新的节点，新节点的值是val，并且
pos的值是从1开始
//看20_非循环单链表插入节点伪算法讲解部分
boolinsert_list(PNODEpHead,intpos,intval)
inti=0;
PNODEp=pHead;//指向头节点的指针(地址)
while(NULL!=pipos-1)//在遍历链表时用一个变量++然后和要插入pos位置进行比较
++i;//节点数自增
if(ipos-1
NULL==p)//插入位置大于原链表的长度或插入到NULL空链表
printf("动态分配内存失败！\n");
pNew-data=val;//节点数据域中的数据插入
//问题：已知p节点，把新节点q插入到p节点后面？两种插入算法
PNODEq=p-pNext;
p-pNext=pNew;
pNew-pNext=q;
//看21_非循环单链表删除节点伪算法的讲解部分
booldelete_list(PNODEpHead,intpos,int*pVal)
PNODEp=pHead;
while(NULL!=p-pNextipos-1)
p=p-pNext;
++i;
if(ipos-1
NULL==p-pNext)
*pVal=q-data;
//删除p节点后面的节点
p-pNext=p-pNext-pNext;
free(q);
q=NULL;
2、改写的C++代码块
#includeiostream
usingnamespacestd;
typedefclassNode
public
/p>
intdata;
Node*pNext;
}NODE,*PNODE;
//创建链表
PNODEcreate_list()
intlen; //存放有效节点个数
intval; //临时存放用户输入的节点的值
PNODEpHead=newNODE;
if(pHead==NULL)
{
cout"分配失败，程序终止！"endl;
exit(-1);
}
PNODEpTail=pHead;
pTail-pNext=NULL;
cout"请输入您要生成的链表节点的个数："endl;
cinlen;
for(inti=0;ilen;i++)
{
cout"请输入第"i+1"个节点的值："endl;
cinval;
PNODEpNew=newNODE;
if(pNew==NULL)
{
cout"分配事变，程序终止！"endl;
exit(-1);
}
//链接新节点
pTail-pNext=pNew;
pNew-data=val;
pNew-pNext=NULL;
//将新节点置为尾结点
pTail=pNew;
}
//遍历链表
//头节点的指针域，指向首节点
PNODEp=pHead-pNext;
while(p!=NULL)
{
coutp-data"";
}
coutendl;
//判断链表是否为空
boolis_Empty(PNODEpHead)
if(pHead-pNext==NULL)
//计算链表长度
intlength_list(PNODEpHead)
intlength=0;
while(p-pNext!=NULL)
{
length++;
}
returnlength;
//插入节点
inti=0;
while(p-pNext!=NULLipos-1)
{
i++;
}
if(p-pNext==NULLipos-1)
{
cout"动态分配内存失败！"endl;
}
pNew-pNext=p-pNext;
//删除节点
inti=0;
{
i++;
}
deleteq;
//冒泡排序
voidsort_list(PNODEpHead)
for(inti=0;ilen-1;i++)
{
for(intj=i+1;jlen;j++)
{
if(p-dataq-data)
{
inttemp=p-data;
p-data=q-data;
q-data=temp;
}
q=q-pNext;
}
}
intmain()
intval;
intlen=0;
PNODEpHead=NULL;
//创建链表
pHead=create_list();
//遍历链表
//判断链表是否为空
if(is_Empty(pHead))
cout"链表为空"endl;
else
cout"链表不为空"endl;
//计算链表长度
len=length_list(pHead);
cout"链表长度："lenendl;
//插入节点
if(insert_list(pHead,3,3))
{
cout"插入成功"endl;
}
else
cout"插入失败"endl;
//删除节点
if(delete_list(pHead,3,val))
{
cout"删除成功"endl;
cout"val="valendl;
}
else
cout"删除失败"endl;
//冒泡排序
system("pause");
return0;
————————————————
版权声明：本文为CSDN博主「奇幻纬度」的原创文章，遵循CC4.0BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：
