链表
链表较顺序表的优点是 插入删除操作方便,且不需要先确定空间
顺序表较链表的优点是 操作简单,对于数输入与输出方便。
这个链表刚开始我花了一个星期去测试和理解,对指针这方面有太多的疑问了
链表最重要的是头指针和输出时如何遍历整个链表
链表的每一个节点都含有一个指针域和一个数据域,而所设定的头指针最好是不要存有数值的,以便后面链表的遍历操作。
root=p;cin>>p->data;p->next=q;p=q;
即 root->p->q;
而p=q则把原来的q又变成p;p与q进行交替输入。
node *p,*q;
if(root==NULL)
{
printf("请先初始化!\n");
return ;
}
int n,i;
printf("请输入要输入的位置:\n");
cin>>n;
p=(node*)malloc(sizeof(node));
root=p; //root->p;
for(i=0;i<n;i++)
{
q=(node*)malloc(sizeof(node));
printf("请输入元素:\n");
cin>>p->data;
if(i!=n-1)
p->next=q;//root->p->q
else
{
p->next=NULL;
}
p=q; // root->p1->p2->q;
}
printf("插入完成!\n");
求链表前驱:
第i个节点的前驱先,先创建新的节点,q,p;在经过对i-1个节点进行遍历,从而得出i节点的前驱。
node *p,*q;
if(root==NULL)
{
printf("请先初始化!\n");
return ;
}
p=(node*)malloc(sizeof(node));
p=root;
int n,i;
printf("请输入要查的前驱节点!\n");
cin>>n;
for(i=0;i<n-1;i++)
{
q=p;
p=p->next;
}
printf("第%d节点的前驱是%d",n,q->data);
return ;
链表的输出就比较简单了
只要判断后一个节点的指针域指向非空就行。
node *now;
if(root==NULL)
{
printf("请先初始化!\n");
return;
}
int i=1;
now=(node*)malloc(sizeof(node));
now=root;
while(now)
{
printf("第%d个节点的值为%d\n",i++,now->data);
now=now->next;
}
if(now==NULL)
printf("链表输出完毕!\n");
return;
删除节点:
链表的删除节点其实是该节点的前驱直接指向该节点的后驱
并利用free()函数进行释放操作。
node *p,*q;
if(root==NULL)
{
printf("请先初始化!\n");
return ;
}
p=(node*)malloc(sizeof(node));
p=root;
printf("请输入要删除的节点:\n");
int i,n;
cin>>n;
for(i=0;i<n-1;i++)
{
q=p;
p=p->next;
}
q->next=p->next;
free(p);
printf("删除完成!\n");
return;
如果要插入数据,则需要要插入节点的前驱指向 插入节点,插入节点指向后驱;
i的前驱->i节点->i的后驱。
node *p,*q,*s;
if(root==NULL)
{
printf("请先初始化!\n");
return;
}
p=(node*)malloc(sizeof(node));
p=root;
int i,n;
printf("请输入要插入的节点:\n");
cin>>n;
for(i=0;i<n-1;i++)
{
q=p;
p=p->next;
}
s=(node*)malloc(sizeof(node));
q->next=s;
printf("请输入要插入的数:\n");
cin>>s->data;
s->next=p;
printf("插入完成!\n");
return ;
关键操作已经贴上代码了,下面是全部代码
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
struct node{
int data;
struct node *next;
} *list;
node head;
node *root=NULL;
void createlist()
{
root=&head;
root=(node*)malloc(sizeof(node));
root->data=0;
root->next=NULL;
printf("链表初始化完成!\n");
}
void setnode()
{
node *p,*q;
if(root==NULL)
{
printf("请先初始化!\n");
return ;
}
int n,i;
printf("请输入要输入的位置:\n");
cin>>n;
p=(node*)malloc(sizeof(node));
root=p;
for(i=0;i<n;i++)
{
q=(node*)malloc(sizeof(node));
printf("请输入元素:\n");
cin>>p->data;
if(i!=n-1)
p->next=q;
else
{
p->next=NULL;
}
p=q;
}
printf("插入完成!\n");
}
void lengthlist()
{
if(root==NULL)
{
printf("请先初始化!\n");
return ;
}
int i=0,n;
node *p;
p=(node*)malloc(sizeof(node));
p=root;
while(p)
{
i++;
p=p->next;
}
printf("该链表长度为:%d\n",i);
return;
}
void coutlist()
{
node *now;
if(root==NULL)
{
printf("请先初始化!\n");
return;
}
int i=1;
now=(node*)malloc(sizeof(node));
now=root;
while(now)
{
printf("第%d个节点的值为%d\n",i++,now->data);
now=now->next;
}
if(now==NULL)
printf("链表输出完毕!\n");
return;
}
void prelist()
{
node *p,*q;
if(root==NULL)
{
printf("请先初始化!\n");
return ;
}
p=(node*)malloc(sizeof(node));
p=root;
int n,i;
printf("请输入要查的前驱节点!\n");
cin>>n;
for(i=0;i<n-1;i++)
{
q=p;
p=p->next;
}
printf("第%d节点的前驱是%d",n,q->data);
return ;
}
void afterlist()
{
node *p,*q;
if(root==NULL)
{
printf("请先初始化!\n");
return ;
}
p=(node*)malloc(sizeof(node));
p=root;
int i,n;
printf("请输入要查询的节点:\n");
cin>>n;
for(i=0;i<n;i++)
{
p=p->next;
}
printf("第%d节点的后驱是%d\n",n,p->data);
return;
}
void deletelist()
{
node *p,*q;
if(root==NULL)
{
printf("请先初始化!\n");
return ;
}
p=(node*)malloc(sizeof(node));
p=root;
printf("请输入要删除的节点:\n");
int i,n;
cin>>n;
for(i=0;i<n-1;i++)
{
q=p;
p=p->next;
}
q->next=p->next;
free(p);
printf("删除完成!\n");
return;
}
void setlist()
{
node *p,*q,*s;
if(root==NULL)
{
printf("请先初始化!\n");
return;
}
p=(node*)malloc(sizeof(node));
p=root;
int i,n;
printf("请输入要插入的节点:\n");
cin>>n;
for(i=0;i<n-1;i++)
{
q=p;
p=p->next;
}
s=(node*)malloc(sizeof(node));
q->next=s;
printf("请输入要插入的数:\n");
cin>>s->data;
s->next=p;
printf("插入完成!\n");
return ;
}
void show()
{
printf("1...........初始化链表.........\n");
printf("2...........输入链表...........\n");
printf("3...........求链表长度.........\n");
printf("4...........输出链表...........\n");
printf("5...........求节点的前驱.......\n");
printf("6...........求节点的后驱.......\n");
printf("7...........删除指定节点.......\n");
printf("8...........插入节点...........\n");
printf("9............退出.............. \n");
return;
}
int main()
{
int n,i=1,t;
while(i){
system("cls");
show();
cin>>n;
if(n>9||n<1)
printf("请输入正确的数!\n");
switch(n)
{
case 1:
{
createlist();
break;
}
case 2:
{
setnode();
break;
}
case 3:{
lengthlist();
break;
}
case 4:{
coutlist();
break;
}
case 5:{
prelist();
break;
}
case 6:{
afterlist();
break;
}
case 7:{
deletelist();
break;
}
case 8:{
setlist();
break;
}
case 9:{
return 0;
break;
}
}
getchar(); getchar();
}
return 0;
}