链表的实现与应用？ 链表实现c
关于数据结构中链表的实现？？？
链表是用结构体实现的（当然，用类也行）
链表打个比方，就好比寻宝，根据藏宝图找到一个地址，到那个地址后，会有另一张藏宝图，指向下一个宝藏的位置。。
链表分为单向链表和双向链表。
顾名思义，单向链表就是你只能从一个链节找到下一个链节，而不能从这个链节回到上一个链节。而双向链表正反都可以。
你知道结构体吧，里面可以认为打包一些你需要的数据。基于这个基础，你可以在里面放一个该类型的结构体的指针变量来存放下一个结构体的地址，然后再放一些你需要存的数据。这样一个一个安排好，用指针变量把他们连接起来，就组成了一个普通的单向链表。双向链表亦是如此，只不过多了一个指针记录前一个链节的地址。
每一个结构体变量叫做链节，它的下一个链节叫子节点，上一个链节叫做父节点，类比二叉树。每一个链节的内容分为两部分，指针部分和数据部分，这个不难理解。
链表由于是用指针连接起来的，所以麻烦就麻烦在这里，如果有一个小改动，比如加一个元素到某一个位置，就必须改动父节点、子节点的指针。添加节点、删除节点等操作各有不同，甚至两头的改动和中间的改动都需要分开写，这些都称作链表的维护。虽然有些复杂，但是掌握了原理之后其实非常简单。
建立链表的步骤是：
先写一个结构体类型，明确你这个链表都需要哪些东西。
比如：
struct List
{
List * p; // 指针，记录子节点的位置
int value; // 数据成员，存放数据的变量
};
然后就可以建立链表了。
List * head; // 首先申明一个头指针，记录链表的首地址，类似数组的首地址
List * temp; // 一个临时变量，之后你会知道他的作用
head = new List; // 然后就新建一个链节，用new来建立
head->p = NULL; // 把不需要的指针NULL是好习惯
head->value = 0; // 记录该节点的数据
这样就完成了一个链表的第一个链节的建立。
之后的建立完全类似：
head->p = new List; // 再新建一个节点
temp = head->p; // 让临时指针指向这个新建的节点，以后的操作就可以用temp完成了
temp->p = NULL; // 尾指针赋值为NULL
temp->value = 1; // 记录该节点的数据。
就是这样，每个节点里面都有一个指针指向下一个节点，最后一个节点的指针（尾指针）是NULL，意味着链表的结束。
链表建立之后，你就可以从首节点一个一个找，直到找到你想找的节点了。
短距离可以：
head->p->p->……->value;
很长的话就再用一个临时变量中转一下吧。
c语言程序设计——链表的应用
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#define ID struct id
struct id
{
char name[20];
int num;
int a;
int b;
int c;
double ave;
ID *next; //
};
int pc=0;
ID *creat()
{
ID *p1,*p2,*head;
int pd;
p1=p2=head=NULL;
printf("\t\t\t 开始输入记录(学号0结束)!\n");
while(1)
{
printf("请输入学生的7a686964616f31333236376635学号:\n");scanf("%d",&pd);
if(pd==0) break;
p1=(ID*)malloc(sizeof(ID));
p1->num=pd;
printf("请输入学生的姓名:\n");scanf("%s",p1->name);
printf("请输入学生的语文成绩:\n");scanf("%d",&p1->a);
printf("请输入学生的数学成绩:\n");scanf("%d",&p1->b);
printf("请输入学生的外语成绩:\n");scanf("%d",&p1->c);
p1->ave=(p1->a+p1->b+p1->c)/3.0;
if(head==NULL)
{
head=p1;
p2=p1;
}
else
{
p2->next=p1;
p2=p1;
}
pc++;
}
p2->next=NULL;
return(head);
}
ID *sort(ID *head)
{
int temp;
char str[100];
double dbl;
ID *p1,*p2;
for(p1=head;p1!=NULL;p1=p1->next)
{
for(p2=p1->next;p2!=NULL;p2=p2->next)
{
if(p1->ave<p2->ave)
{
temp=p1->num;
p1->num=p2->num;
p2->num=temp;
strcpy(str,p1->name);
strcpy(p1->name,p2->name);
strcpy(p2->name,str);
temp=p1->a;
p1->a=p2->a;
p2->a=temp;
temp=p1->b;
p1->b=p2->b;
p2->b=temp;
temp=p1->c;
p1->c=p2->c;
p2->c=temp;
dbl=p1->ave;
p1->ave=p2->ave;
p2->ave=dbl;
}
}
}
printf("排序成功!!!\n");
return (head);
}
/*输入/添加记录*/
ID *insert(ID *head)
{
ID *temp,*p1,*p2;
printf("插入操作开始!!!\n");
temp=(ID *)malloc(sizeof(ID));
printf("请输入学生的学号:\n");scanf("%d",&temp->num);
printf("请输入学生的姓名:\n");scanf("%s",temp->name);
printf("请输入学生的语文成绩:\n");scanf("%d",&temp->a);
printf("请输入学生的数学成绩:\n");scanf("%d",&temp->b);
printf("请输入学生的外语成绩:\n");scanf("%d",&temp->c);
temp->ave=(temp->a+temp->b+temp->c)/3.0;
if (head==NULL)
{
head=temp;
temp->next=NULL;
}
else
{
p1=head;
while(p1!=NULL && p1->ave > temp->ave)
{
p2=p1;
p1=p1->next;
}
p2->next=temp;
temp->next=p1;
}
printf("插入成功");
pc++;
return (head);
}
/*删除学生记录*/
ID *delet(ID *head)
{
ID *p1,*p2;
int num;
printf("请输入要删除的学生的学号:");scanf("%d",&num);
p1=head;
if (head==NULL)
{
printf("没有记录\n");
goto end;
}
while(num!=p1->num && p1!=NULL)
{
p2=p1;p1=p1->next;
}
if(num==p1->num)
{
if (p1==head)
head=p1->next;
else
p2->next=p1->next;
printf("删除成功!!!\n");
pc--;
}
end:return head;
}
/*查找学生记录*/
ID *search(ID *head)
{
ID *p1,*p2;
char str[100];
printf("请输入要查找的学生的姓名:");scanf("%s",str);
p1=head;
while(strcmp(str,p1->name) && p1!=NULL)
{
p2=p1;p1=p1->next;
}
if(strcmp(str,p1->name)==0)
{
printf("学生的学号:%d\n",p1->num);
printf("学生的姓名:%s\n",p1->name);
printf("学生的语文成绩:%d\n",p1->a);
printf("学生的数学成绩:%d\n",p1->b);
printf("学生的外语成绩:%d\n",p1->c);
printf("学生的平均成绩:%.2lf\n",p1->ave);
}
return head;
}
/*显示结果函数*/
void print(ID *head)
{
ID *p;
p=head;
printf("\t\t\t*****************\n");
printf("显示结果是:\n");
if(head!=NULL)
do
{
printf("%10d%10s%10d%10d%10d%10.2lf\n",p->num,p->name,p->a,p->b,p->c,p->ave);
p=p->next;
} while(p!=NULL);
}
void main()
{
ID *head=NULL;
int choise;
printf("\t\t\t* * * * C语言课设* * * *\n");
while(1)
{
printf("\t\t 学生信息管理系统\n");
printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
printf("\t\t 1.输入\n");
printf("\t\t 2.显示\n");
printf("\t\t 3.查找\n");
printf("\t\t 4.排序\n");
printf("\t\t 5.插入\n");
printf("\t\t 6.删除\n");
printf("\t\t 0.退出\n");
printf("\n");
printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
printf("请选择(0-6):");
scanf("%d",&choise);
switch(choise)
{
case 1: head=creat();
break;
case 2: print(head);
break;
case 3: head=search(head);
break;
case 4: head=sort(head);
break;
case 5: head=insert(head);
break;
case 6: head=delet(head);
break;
case 0:
exit(0);
break;
default :printf("输入错误,请重新输入!\n");
}
}
}
C++链表实现的方法
动态内存分配应用举例（链表）
我们知道，数组式计算机根据事先定义好的数组类型与长度自动为其分配一连续的存储单元，相同数组的位置和距离都是固定的，也就是说，任何一个数组元素的地址都可一个简单的公式计算出来，因此这种结构可以有效的对数组元素进行随机访问。但若对数组元素进行插入和删除操作，则会引起大量数据的移动，从而使简单的数据处理变得非常复杂，低效。
为了能有效地解决这些问题，一种称为“链表”的数据结构得到了广泛应用。
1． 链表概述
链表是一种动态数据结构，他的特点是用一组任意的存储单元（可以是连续的，也可以是不连续的）存放数据元素。
链表中每一个元素成为“结点”，每一个结点都是由数据域和指针域组成的，每个结点中的指针域指向下一个结点。Head是“头指针”，表示链表的开始，用来指向第一个结点，而最后一个指针的指针域为NULL(空地址)，表示链表的结束。
可以看出链表结构必须利用指针才能实现，即一个结点中必须包含一个指针变量，用来存放下一个结点的地址。
实际上，链表中的每个结点可以用若干个数据和若干个指针。结点中只有一个指针的链表称为单链表，这是最简单的链表结构。
再c++中实现一个单链表结构比较简单。例如，可定义单链表结构的最简单形式如下
struct Node
{
int Data;
Node*next;
};
这里用到了结构体类型。其中，*next是指针域，用来指向该结点的下一个结点；Data是一个整形变量，用来存放结点中的数据。当然，Data可以是任何数据类型，包括结构体类型或类类型。
在此基础上，我们在定义一个链表类list，其中包含链表结点的插入，删除，输出等功能的成员函数。
class list
{
Node*head;
public:
list(){head=NULL;}
void insertlist(int aDate,int bDate);//链表结点的插入
void Deletelist(int aDate);//链表结点的删除
void Outputlist();//链表结点的输出
Node*Gethead(){return head;}
};
2． 链表结点的访问
由于链表中的各个结点是由指针链接在一起的，其存储单元文笔是连续的，因此，对其中任意结点的地址无法向数组一样，用一个简单的公式计算出来，进行随机访问。只能从链表的头指针（即head）开始，用一个指针p先指向第一个结点，然后根据结点p找到下一个结点。以此类推，直至找到所要访问的结点或到最后一个结点（指针为空）为止。
下面我们给出上述链表的输出函数；
void list::outputlist()
{
Node*current=head;
while(current!=NULL)
{
cout<
current=current->next;
}
cout< } 3． 链表结点的插入 如果要在链表中的结点a之前插入结点b，则需要考虑下面几点情况。 （1） 插入前链表是一个空表，这时插入新结点b后。 （2） 若a是链表的第一个结点，则插入后，结点b为第一个结点。 （3） 若链表中存在a,且不是第一个结点，则首先要找出a的上一个结点a_k，然后使a_k的指针域指向b，在令b的指针域指向a，即可完成插入。 （4） 如链表中不存在a，则插在最后。先找到链表的最后一个结点a_n，然后使a_n的指针域指向结点b，而b指针的指针为空。 以下是链表类的结点插入函数，显然其也具有建立链表的功能。 void list::insertlist(int aDate,int bDate) //设aDate是结点a中的数据，bDate是结点b中的数据 { Node*p,*q,*s; //p指向结点a，q指向结点a_k，s指向结点b s=(Node*)new(Node); //动态分配一个新结点 s->Data=bDate; //设b为此结点 p=head; if(head==NULL) //若是空表，使b作为第一个结点 { head=s; s->next=NULL; } else if(p->Data==aDate) //若a是第一个结点 { s->next=p; head=s; } else { while(p->Data!=aDate&&p->next!=NULL)//查找结点a { q=p; p=p->next; } if(p->Data==aDate) ///若有结点a { q->next=s; s->next=p; } else //若没有结点a； { p->next=s; s->next=NULL; } } } 4． 链表结点的删除 如果要在链表中删除结点a并释放被删除的结点所占的存储空间，则需要考虑下列几种情况。 （1） 若要删除的结点a是第一个结点，则把head指向a的下一个结点。 （2） 若要删除的结点a存在于链表中，但不是第一个结点，则应使a得上一个结点a_k-1的指针域指向a的下一个结点a_k+1。 （3） 空表或要删除的结点a不存在，则不做任何改变。 以下是链表类的结点删除函数。 void list::deletelist(int aDate) //设aDate是要删除的结点a中的数据成员 { Node*p,*q; //p用于指向结点a,q用于指向结a的前一个结点 p=head; if(p==NULL) //若是空表 return; if(p->Data==aDate) //若a是第一个结点 { head=p->next; delete p; } else { while(p->Data!=aDate&&p->next!=NULL) //查找结点a { q=p; p=p->next; } if(p->Data==aDate) //若有结点a { q->next=p->next; delete p; } } } 例题；利用以上三个链表操作成员函数insertlist,deletelist.outputlist,可形成以下的简单链表操作程序。 #include"iostream.h" struct Node { int Data; Node*next; }; class list { Node*head; public: list(){head=NULL;} void insertlist(int aData,int bData); void deletelist(int aData); void outputlist(); Node*gethead(){return head;} }; void list::insertlist(int aData,int bData) //设aData是结点a中的数据，bData是结点b中的数据 { Node*p,*q,*s; //p指向结点a，q指向结点a_k，s指向结点b s=(Node*)new(Node); //动态分配一个新结点 s->Data=bData; //设b为此结点 p=head; if(head==NULL) //若是空表，使b作为第一个结点 { head=s; s->next=NULL; } else if(p->Data==aData) //若a是第一个结点 { s->next=p; head=s; } else { while(p->Data!=aData && p->next!=NULL)//查找结点a { q=p; p=p->next; } if(p->Data==aData) ///若有结点a { q->next=s; s->next=p; } else //若没有结点a； { p->next=s; s->next=NULL; } } } void list::deletelist(int aData) //设aData是要删除的结点a中的数据成员 { Node*p,*q; //p用于指向结点a,q用于指向结a的前一个结点 p=head; if(p==NULL) //若是空表 return; if(p->Data==aData) //若a是第一个结点 { head=p->next; delete p; } else { while(p->Data!=aData&&p->next!=NULL) //查找结点a { q=p; p=p->next; } if(p->Data==aData) //若有结点a { q->next=p->next; delete p; } } } void list::outputlist() { Node*current=head; while(current!=NULL) { cout< current=current->next; } cout< } void main() { list A,B; int Data[10]={25,41,16,98,5,67,9,55,1,121}; A.insertlist(0,Data[0]); //建立链表A首结点 for(int i=1;i<10;i++) A.insertlist(0,Data[i]); //顺序向后插入 cout<<"\n链表A:"; A.outputlist(); A.deletelist(Data[7]); cout<<"删除元素Data[7]后"; A.outputlist(); B.insertlist(0,Data[0]); //建立链表B首结点 for(i=0;i<10;i++) B.insertlist(B.gethead()->Data,Data[i]); //在首结点处顺序向后插入 cout<<"\n链表B:"; B.outputlist(); B.deletelist(67); cout<<"删除元素67后"; B.outputlist(); } 程序运行结果为 链表A；25，41，16，98，5，67，9，55，1，121 删除元素Data[7]后； 25，41，16，98，5，67，9，1，121 链表B；121，1，55，9，67，5，98，16，41，25， 删除元素67后； 121，1，55，9，5，98，16，41，25， 下面是杨辉三角的代码： #include #include using namespace std; int main() { const int n=11; int i,j,a[n][n]; for(i=1;i { a[i][i]=1; a[i][1]=1; } for(i=3;i { for(j=2;j<=i-1;j++) a[i][j]=a[i-1][j-1]+a[i-1][j]; } for(i=1;i { for(j=1;j<=i;j++) cout< } cout< return 0; } 本人愚见... 数据结构中的线性表和队列肯定会用到链表； 链表主要的作用就是能够灵活的存储数据，其实如果你不是制作什么很复杂的东西，用链表虽然会为系统节省开支，但是这点开支完全可以忽略不计的。在C语言中，如果你是初学者的话，对于链表你只需要了解它的用法就可以了，因为初学者所用到得程序一般来说简单的数组完全可以代替链表c语言中的链表实际运用