数据随机分布在内存中的各个位置，这种存储结构称为线性表的链式存储。
由于分散存储，为了能够体现出数据元素之间的逻辑关系，每个数据元素在存储的同时，要配备一个指针，用于指向它的直接后继元素，即每一个数据元素都指向下一个数据元素（最后一个指向NULL(空)）。
链表中数据元素的构成
每个元素本身由两部分组成：
1).本身的信息，称为“数据域”；
2).指向直接后继的指针，称为“指针域”。
两部分信息组成数据元素的存储结构，称之为“结点”。n个结点通过指针域相互链接，组成一个链表。
1.结构体定义
typedef struct Link{
char elem;//代表数据域
struct Link * next;//代表指针域，指向直接后继元素
}link;
2.链表创建及赋值
link * initLink(int arr[]){
link * p=(link*)malloc(sizeof(link));//创建一个头结点
link * temp=p;//声明一个指针指向头结点，用于遍历链表
//生成链表
for (int i=1; i<arr.length; i++)
{
link *a=(link*)malloc(sizeof(link));
a->elem=arr[i];
a->next=NULL;
temp->next=a;
temp=temp->next;
}
return p;
}
2.链表中查找某结点
int selectElem(link * p,int elem){
link * t=p;
int i=1;
while (t->next) {
t=t->next;
if (t->elem==elem) {
return i;
}
i++;
}
return -1;
}
3.更改链表中某结点的数据
//更新函数，add 表示更改结点在链表中的位置，newElem 为新的数据域的值
link *amendElem(link * p,int add,int newElem){
link * temp=p;
temp=temp->next;//在遍历之前，temp指向首元结点
//遍历到被删除结点
for (int i=1; i<add; i++) {
temp=temp->next;
}
temp->elem=newElem;
return p;
}
4.向链表中插入结点
插入种类：
链表中插入头结点，根据插入位置的不同，分为3种：
1).插入到链表的首部，也就是头结点和首元结点中间；
2).插入到链表中间的某个位置；
3).插入到链表最末端；
插入方法：
虽然插入位置有区别，都使用相同的插入手法。分为两步：
1）.将新结点的next指针指向插入位置后的结点；
2）.将插入位置前的结点的next指针指向插入结点；
link * insertElem(link * p,int elem,int add){
link * temp=p;//创建临时结点temp
//首先找到要插入位置的上一个结点
for (int i=1; i<add; i++) {
if (temp==NULL) {
printf("插入位置无效\n");
return p;
}
temp=temp->next;
}
//创建插入结点c
link * c=(link*)malloc(sizeof(link));
c->elem=elem;
//向链表中插入结点
c->next=temp->next;
temp->next=c;
return p;
}
5.从链表中删除节点
删除方法：
当需要从链表中删除某个结点时，需要进行两步操作：
1).将结点从链表中摘下来;
2).手动释放掉结点，回收被结点占用的内存空间;
使用malloc函数申请的空间，一定要注意手动free掉。否则在程序运行的整个过程中，申请的内存空间不会自己释放（只有当整个程序运行完了以后，这块内存才会被回收），造成内存泄漏.
link * delElem(link * p,int add){
link * temp=p;
//temp指向被删除结点的上一个结点
for (int i=1; i<add; i++) {
temp=temp->next;
}
link * del=temp->next;//单独设置一个指针指向被删除结点，以防丢失
temp->next=temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域
free(del);//手动释放该结点，防止内存泄漏
return p;
}
完整代码
#include<stdio.h>
#include<stdlib.h>
#define linksize 6
typedef struct Link{
int elem;
struct Link *next;
}link;
link *initLink();
//生成链表
link *insertElem(link *p,int elem,int add);
//链表插入函数：p为链表，elem为插入元素，add为插入位置
link *delElem(link *p,int add);
//链表删除函数：p为链表，add为删除位置
int selectElem(link *p,int elem);
//链表元素查找函数：p为链表，elem为将要查的元素，函数返回值为该元素所在位置
link *amendElem(link * p,int add,int newElem);
//更新结点的函数，newElem为新的数据域的值
void dispLink(link *p);
//输出链表所有元素
link *initLink()
{
link *p=(link*)malloc(sizeof(link));//创建一个头节点
link *temp=p;//声明一个指针指向头结点，用于遍历链表
//生成链表
int i;
for(i=0;i<linksize;i++)
{
link *a=(link*)malloc(sizeof(link));
a->elem=i+1;//元素赋值
a->next=NULL;//可选
temp->next=a;//与前一个节点链接
temp=temp->next;//temp节点后移，为增加下个节点做准备
}
return p;
}
link *insertElem(link *p,int elem,int add)
{
link *temp=p;//创建临时节点
int i;
//找到插入位置的前一个节点
for(i=1;i<add;i++)
{
if(temp==NULL)
{
printf("插入位置无效.\n");
return p;
}
temp=temp->next;
}
//创建插入节点
link *c=(link*)malloc(sizeof(link));
c->elem=elem;
//向链表插入节点
c->next=temp->next;
temp->next=c;
return p;
}
link *delElem(link *p,int add)
{
link *temp=p;
//找到删除位置的前一个节点
int i;
for(i=1;i<add;i++)
{
temp=temp->next;
}
link *del=temp->next;//存放删除节点的数据
temp->next=temp->next->next;//删除节点
free(del);
return p;
}
int selectElem(link *p,int elem)
{
link *k=p;
int i=0;
while(k->next)
{
k=k->next;
if(k->elem==elem)
{
return i;
}
i++;
}
return -1;
}
link *amendElem(link *p,int add,int newElem)
{
link *temp=p;
temp=temp->next;//temp指向首节点
//temp指向删除节点
int i;
for(i=0;i<add;i++)
{
temp=temp->next;
}
temp->elem=newElem;
return p;
}
void dispLink(link *p)
{
link *temp=p;
while(temp->next)
{
//注意头节点哦
temp=temp->next;
printf("%d",temp->elem);
}
}
void main()
{
//初始化链表
printf("初始化链表为：");
link *p=initLink();
dispLink(p);
printf("\n在第4位置插入元素6:");
p=insertElem(p,6,4);
dispLink(p);
printf("\n删除元素3：");
p=delElem(p,3);
dispLink(p);
printf("\n查找元素值为2的位置:");
int address=selectElem(p,2);
if(address==-1)
printf("\n无此元素。");
else
printf("目标元素位置：%d",address);
printf("\n更改第3位元素为7：");
p=amendElem(p,3,7);
dispLink(p);
}
网友评论