1、单链表的基本概念
单链表是线性表链式存储的一种形式，其中的结点一般含有两个域，一个存放数据信息的info域，另一个指向该结点的后继结点存放地址的指针next域。一个单链表必须有一个首指针指向单链表中的第一个结点。
单链表中每个操作的单独实现
--------------------定义结点 -------------------
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef struct Node
{
ElemType data; //数据域
struct Node *next; //指针域
}Node;
typedef struct Node *Linklist;
---------------------链表初始化 ----------------------
int Create(Linklist *L)
{
*L=(Linklist)malloc(sizeof(Node));
//创建了一个结点，并且用L指向了这个结点
if(!(*L))
return ERROR;
(*L)->next=NULL;
return OK;
}
--------------------求长度函数 -----------------------
int Length(Linklist L)
{
int i=0;
Linklist p;
p=L->next; //指向的第一个结点
while(p)
{
i++;
p=p->next; //指向下一个结点
}
return i;
}
---------------------取元素操作-----------------------
int Get(Linklist L,int i)//ElemType *e)
{
int j;
Linklist p;
p=L->next;
j=1;
while(p && j<i)
{
j++;
p=p->next;
}
if (!p|| j>i)
return ERROR;
//*e= p->data;
return p->data;
}
---------------------定位元素-------------------------
int Locate(Linklist L,ElemType e)
{
int i=1;
Linklist p;
p=L->next;
while(p)
{
if (p->data==e)
return i;
p=p->next;
i++;
}
return ERROR;
}
---------------------前插元素-------------------------
int Insert(Linklist *L,int i,ElemType e)
{
int j;
Linklist p,s;
p= *L;
j=1;
while(p && j<i)
{
p=p->next;
j++;
}
if(!p|| j>i)
return ERROR;
s=(Linklist)malloc(sizeof(Node));
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
---------------------删除元素-------------------------
int Delete(Linklist *L,int i)
{
int j;
Linklist p,q;
p= *L;
j=1;
while(p->next && j<i)
{
p=p->next;
j++;
}
if(!(p->next)||j>i)
return ERROR;
q=p->next;
p->next=q->next;
free(q);
return OK;
}
---------------------判空操作-------------------------
int Check(Linklist *L)
{
Linklist p;
p=*L;
if(p->next)//头指针是否为空？
printf("链表非空！\n");
return OK;
}
---------------------清空表操作-----------------------
int Clear(Linklist *L)
{
Linklist p;
p =*L;
while(p->next)
{
p=p->next;
p->data=0;//只是数据清零，并非释放内存
}
return OK;
}
执行后：
静态链表
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存储空间初始分配量 */
typedef char ElemType;
typedef struct{
ElemType data;
int cur; //游标
}Component,StaticLinkList[MAXSIZE];
//输出
int visit(ElemType c)
{
printf("%c ",c);
return OK;
}
//初始化
int InitList(StaticLinkList space)
{
int i;
for (int i = 0; i < MAXSIZE-1; ++i)
space[i].cur =i+1;
space[MAXSIZE-1].cur =0;
return OK;
}
//分配空间
int Malloc(StaticLinkList space)
{
int i = space[0].cur;
if(space[0].cur)
space[0].cur = space[i].cur;
return i;
}
//回收空间
int Free(StaticLinkList space, int k)
{
space[k].cur = space[0].cur;
/* 把第一个元素的cur值赋给要删除的分量cur */
space[0].cur = k;
/* 把要删除的分量下标赋值给第一个元素的cur */
return OK;
}
//长度函数
int Length(StaticLinkList L)
{
int j=0;
int i=L[MAXSIZE-1].cur;
while(i)
{
i=L[i].cur;
j++;
}
return j;
}
//在第i个元素前插入元素
int Insert(StaticLinkList L,int i,ElemType e)
{
int j,k,l;
k = MAXSIZE -1;
if( i<1 || i > Length(L)+1)
return ERROR;
j=Malloc(L);
if(j)
{
L[j].data =e;
for (l = 1; l < i -1; l++)
/* 找到第i个元素之前的位置 */
k=L[k].cur;
L[j].cur = L[k].cur;
/* 把第i个元素之前的cur赋值给新元素的cur */
L[k].cur = j;
/* 把新元素的下标赋值给第i个元素之前元素的ur */
return OK;
}
return ERROR;
}
//删除第i个数组元素
int Delete(StaticLinkList L, int i)
{
int j,k;
if(i<1 || i> Length(L))
return ERROR;
k = MAXSIZE-1;
for(j=1;j<=i -1;j++)
k= L[k].cur;
j=L[k].cur;
L[k].cur = L[j].cur;
Free(L,j);
return OK;
}
int Traverse(StaticLinkList L)
{
int j=1;
int i=L[MAXSIZE-1].cur;
while(i)
{
visit(L[i].data);
i=L[i].cur;
j++;
}
return j;
printf("\n");
return OK;
}
int main()
{
StaticLinkList L;
int i;
i=InitList(L);
printf("初始化L后：L.length=%d\n",Length(L));
i=Insert(L,1,'F');
i=Insert(L,1,'E');
i=Insert(L,1,'D');
i=Insert(L,1,'B');
i=Insert(L,1,'A');
printf("\n在L的表头依次插入FEDBA后：\nL.data=");
Traverse(L);
i=Insert(L,4,'C');
printf("\n在L的“B”与“D”之间插入“C”后：\nL.data=");
Traverse(L);
i=Delete(L,1);
printf("\n在L的删除“A”后：\nL.data=");
Traverse(L);
printf("\n");
return 0;
}
网友评论