数据结构中用C语言实现线性链表的创建，增加删除某节点等基本功能
- 提问者网友：孤山下
- 2021-04-12 04:13
- 五星知识达人网友：从此江山别
- 2021-04-12 05:23
看看这个行不，我以前编的：
#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 100
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define NULL 0
typedef struct LNode
{
int data;
struct LNode *next;
}*Link,*Position;
typedef struct
{
Link head,tail;
int len;
}LinkList;
int MakeNode(Link &p,int e)
{
//分配由p指向的值为e的结点,并返回OK; 若分配失败,则返回ERROR
if(!(p=(Link)malloc(sizeof( Link ))))return ERROR;
p->data=e;
p->next=NULL;
return OK;
}
void FreeNode(Link &p)
{
//释放p所指的结点
free(p);
p=NULL;
}
int InitList(LinkList &L)
{
//构造一个空的线性链表L
Link p;
p=(Link)malloc(sizeof(LNode));
if(!p)return(OVERFLOW);
p->next=NULL;
L.tail=L.head=p;
L.len=0;
return OK;
}
int ClearList(LinkList &L)
{
//将线性链表L重置为空表,并释放原链表的结点空间
if(!L.len)return ERROR;
Link p,q;
q=L.head->next;
p=q;
L.head->next=NULL;
while(p!=L.tail)
{
p=q->next;
FreeNode(q);
q=p;
}
//FreeNode(q);
L.tail=L.head;
L.len=0;
return OK;
}
int DestroyList(LinkList &L)
{
//销毁线性链表L,L不再存在
if(!L.len)return ERROR;
ClearList(L);
FreeNode(L.head);
return OK;
}
int InsFirst(LinkList &L,Link h,Link s)
{
// 已知h指向线性链表的头结点,将s所指结点插入在第一个结点之前
if(!s)return ERROR;
s->next=h->next;
h->next=s;
if(h==L.tail)
L.tail=s;
L.len++;
return OK;
}
int DelFirst(LinkList &L,Link h,Link &q)
{
//已知h指向线性链表的头结点,删除链表中的第一个结点并以q返回
if(!h->next)return ERROR;
q=h->next;
h->next=q->next;
q->next=NULL;
if(!h->next)
L.tail=h;
L.len--;
return OK;
}
int Append(LinkList &L,Link s)
{
//将指针s所指的一串结点链接在线性链表L的最后一个结点
if(!s)return ERROR;
L.tail->next=s;
L.len++;
while(s->next)
{
s=s->next;
L.len++;
}
L.tail=s;
return OK;
}
int Remove(LinkList &L,Link &q)
{
//删除线性链表L中的尾结点并以q返回,改变链表L的尾指针指向新的尾结点
if(!L.len) return ERROR;
Link p;
p=L.head;
while( p != L.tail)
p=p->next;
q=L.tail;
p->next=NULL;
L.tail=p;
L.len--;
return OK;
}
Position PriorPos(LinkList L, Link p)
{
//已知p指向线性链表中的一个结点，返回p所指结点的直接前驱的位置，若无前驱，则返回NULL
if(p==L.head->next)return NULL;
Link q;
q=L.head->next;
while(q->next!=p)
q=q->next;
return q;
}
int InsBefore(LinkList &L,Link &p,Link s)
{
//已知p指向线性链表L中的一个结点,将 s 所指结点插入在 p 所指的结点之前
if(!s||!p)return ERROR;
Link q;
q=PriorPos(L, p);
if(!q)
q=L.head;
q->next=s;
s->next=p;
//p=s;
L.len++;
return OK;
}
int InsAfter(LinkList &L,Link &p,Link s)
{
// 已知p指向线性链表L中的一个结点,将s所指结点插入在p所指的结点之后
if(!s||!p)return ERROR;
if(p==L.tail)
L.tail=s;
s->next=p->next;
p->next=s;
//p=s;
L.len++;
return OK;
}
int SetCurElem(Link &p,int e)
{
//已知p指向线性链表中的一个结点，用e更新p所指结点中数据元素的值
if( !p ) return ERROR;
p->data = e;
return OK;
}
int GetCurElem(Link p)
{
//已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值
return p->data;
}
int ListEmpty(LinkList L)
{
//若线性链表为空表，则返回TRUE，否则返回FALSE
if(L.len)return TRUE;
else return FALSE;
}
int ListLength(LinkList L)
{
//返回线性链表L中元素个数
return L.len;
}
Position GetHead(LinkList L)
{
//返回线性链表L中头结点的位置
return L.head;
}
Position GetLast(LinkList L)
{
//返回线性链表L中最后一个结点的位置
return L.tail;
}
Position NextPos(LinkList L, Link p)
{
//已知p指向线性链表中的一个结点，返回p所指结点的直接后继的位置，若无后继则返回NULL
return p->next;
}
int LocatePos(LinkList L,int i,Link &p)
{
//返回p指示线性链表L中第i个结点的位置并返回OK，i 值不合法时返回ERROR
int j;
if(i<0||i>L.len)return ERROR;
p=L.head;
for(j=1;j<=i;j++)
p=p->next;
return OK;
}
int compare(int a,int b)
{
//比绞两个数的大小
return a-b;
}
Position LocateElem(LinkList L,int e,int(*compare)(int,int))
{
//返回线性链表L中第1个与e满足函数compare()判定关系的元素和位置,若不存在这样的元素,则返回NULL
Link p=L.head;
do
{
p=p->next;
}while(p&&!compare(p->data,e));
return p;
}
void visit(int a)
{
printf("%d",a);
}
int ListTraverse(LinkList L,void(*visit)(int))
{
//依次对L的每个元素调用函数visit().一旦visit()失败,则打操作失败.
if(L.len==0)
printf("对不起,线性链表为空,无法输出!\n");
else
{
Link p=L.head->next;
int j;
for(j=1;j<=L.len;j++)
{
if(j!=L.len)
{
visit(p->data);
printf("->");
p=p->next;
}
else visit(p->data);
}
printf("\n");
}
return OK;
}
void Display(LinkList L) //输出链表
{
int i;
Link p=L.head->next;
for(i=1; i<=L.len;i++)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
int main()
{
int i;
Link p, q;
LinkList La;
if(!InitList(La))return(OVERFLOW); //初始化La;
for(i=7;i>=1;i=i-2) //生成链表La;
{
MakeNode(p,i);
InsFirst(La,La.head,p);
}
printf("\t线性链表综合操作\n");
printf("===========================================\n");
printf("链表L为: "); //输出链表 La;
ListTraverse(La,visit);
printf("链表L的长度为:%d\n",ListLength(La));
Remove( La, p ); //删除La中的最后一个结点
printf("删除链表L中的最后一个结点:%d\n",p->data);
printf("此时的链表L为: "); //输出链表La
ListTraverse(La,visit);
LocatePos(La,2,p);
printf("链表L中第2个结点的值为:%d\n",p->data);
q=PriorPos(La,p);
printf("链表L中第2个结点的前驱的值为:%d\n",q->data);
q=NextPos(La,p);
printf("链表L中第2个结点的后继的值为:%d\n",q->data);
MakeNode(q,2);
InsBefore(La,p,q);
MakeNode(q,4);
InsAfter(La,p,q);
printf("在第2个结点前、后分别插入值为2、4的结点:");
ListTraverse(La,visit);
ClearList(La); //清除链表La
printf("清除链表......\n");
printf("清除后再次输出......\n");
ListTraverse(La,visit);
return OK;
}
结果如图：
- 1楼网友：鱼芗
- 2021-04-12 05:55
链表的节点分为数据和指针next两部分，指针指向链表中的下一个节点
删除节点要将删除节点前一个节点的next指针指向要删除节点的下一个节点，并把要删除的节点占用的地址空间释放
插入节点要将插入位置前一个节点的next指针指向这个节点，将这个节点的next指针指向要插入节点位置的后一个节点
查找就是把目标节点依次与链表中的节点进行比较，不相等指针指向链表下一个节点