单链表简介
单链表结构
头指针是指向链表中第一个结点的指针
首元结点是指链表中存储第一个数据元素a1的结点
头结点是在链表的首元结点之前附设的一个结点;数据域内只放空表标志和表长等信息
单链表存储结构定义:
typedef struct Lnode
{
ElemType data; //数据域
struct LNode *next; //指针域
}LNode,*LinkList;
// *LinkList为Lnode类型的指针
单链表基本操作
#include <stdlib.h>
#include <stdio.h>
#define OK 1
#define FALSE 0
#define ERROR -1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
typedef struct LNode //链表结点定义
{
ElemType Data; //结点的数据域
struct LNode *Next; //结点的指针域
}LNode, *LinkList;
//功能:初始化单链表,即生成只有表头的单链表,成功返回OK,否则返回ERROR
Status InitLinkList_L(LinkList &L)
{
L = (LinkList)malloc(sizeof(LNode)); //生成头结点
if(L)
{
L->Next = NULL; //头结点的next指针为空
return OK;
}
else
return ERROR;
}
//功能:向单链表中输入n个数据,成功返回OK,否则返回ERROR
Status InputData_L(LinkList &L, int n)
{
int i;
LinkList p;
printf("链表建立方法:头插法!\n");
for(i = 1; i <= n; i++)
{
printf("第 %d 个数据:", i);
p = (LinkList)malloc(sizeof(LNode)); //生成新的数据结点
if(p)
{
scanf("%d", &(p->Data));
p->Next = L->Next; //插入位置为头结点后面,因此p的指针为头结点指针
L->Next = p; //头结点指针指向新的数据结点
}
else
return ERROR;
}
return OK;
}
//功能:查询链表L的第i个位置上是否存在元素,存在返回OK,否则返回ERROR,找到的数据存放到变量e中
Status GetElem_L(LinkList L, int i, ElemType &e)
{
LinkList p;
int j;
p = L->Next;
j = 1;
while(p&&(j<i))
{
p = p->Next;
j++;
}
if(!p || j > i)
return ERROR;
e = p->Data;
return OK;
}
//功能:向链表L的第i个位置插入一个数据e,插入成功返回OK,否则返回ERROR
Status ListInsert_L(LinkList &L, int i, ElemType e)
{
LinkList p, s;
int j;
p = L;
j = 0;
while(p &&(j < i - 1))
{
p = p->Next;
j++;
}
if(!p || j > i)
return ERROR;
s = (LinkList)malloc(sizeof(LNode));
s->Data = e;
s->Next = p->Next;
p->Next = s;
return OK;
}
//功能:将链表L的第i个位置删除,删除的值保存到e,删除成功返回OK,否则返回ERROR
Status ListDelete_L(LinkList &L, int i, ElemType &e)
{
LinkList p, q;
int j;
p = L; j = 0;
while(p->Next && (j < i-1))
{
p = p->Next;
j++;
}
if(!(p->Next) || (j > i - 1))
return ERROR;
q = p->Next;
p->Next = q->Next;
e = q->Data;
free(q); //删除后,释放对应数据的空间
return OK;
}
//功能:求链表L的长度,返回链表L的长度
int ListLength_L(LinkList L)
{
int j = 0;
LinkList p = L;
while(p->Next)
{
p = p->Next;
j++;
}
return j;
}
//功能:依次输出链表L的每个数据
void OutputList_L(LinkList L)
{
LinkList p;
int j = 0; //计数器
p = L->Next;
while(p)
{
j++;
printf("第 %d 个数据为:", j);
printf("%d\n", p->Data);
p = p->Next;
}
if(j == 0)
printf("\n空链表,数据总个数为 0 .\n");
else
printf("\n链表数据总数为:%d\n", j);
}
//功能:依次清除链表L的每个数据,并释放相应的空间,清除成功,返回OK,否则ERROR
Status ClearLis_L(LinkList &L)
{
LinkList p, q;
p = L->Next;
if(!p)
{
printf("链表为空,无需清除!\n");
return OK;
}
printf("正在清除链表L中的数据,请等待...\n");
while(p) //链表非空
{
q = p; //
p = q->Next;
free(q);
}
L->Next = NULL;
printf("链表L中的数据清除完成!\n");
return OK;
}
void ShowMenu() //主菜单
{
printf("\n");
printf("\n****************单链表(头插法)数据操作****************\n\n");
printf("\t\t1 链表数据输出\n\n");
printf("\t\t2 链表数据插入\n\n");
printf("\t\t3 链表数据删除\n\n");
printf("\t\t4 链表数据查询\n\n");
printf("\t\t5 链表数据清空\n\n");
printf("\t\t0 退出系统\n\n");
printf("****************单链表(头插法)数据操作****************\n");
printf("\n");
}
//功能:菜单2的操作处理,实现:在单链表的第i个位置插入数据e的操作
void SubMenu2(LinkList &L)
{
int i;
ElemType e;
printf("插入位置:");
scanf("%d", &i);
printf("插入的数据:");
scanf("%d", &e);
if(ListInsert_L(L, i, e) == OK)
printf("在单链表L的第 %d 位置成功插入数据 %d .\n", i, e);
else
printf("插入位置:%d 错误!\n", i);
}
//功能:菜单3的操作处理,实现:在单链表的第i个位置删除数据e的操作
void SubMenu3(LinkList &L)
{
//ListDelete_L
int i;
ElemType e;
printf("删除位置:");
scanf("%d", &i);
if(ListDelete_L(L, i, e) == OK)
printf("在单链表L的第 %d 位置成功删除数据 %d .\n", i, e);
else
printf("删除位置:%d 错误!\n", i);
}
//菜单3的操作处理,实现:查询单链表的第i个位置数据的操作
void SubMenu4(LinkList L)
{
int i;
ElemType e;
printf("插入位置:");
scanf("%d", &i);
if(GetElem_L(L, i, e) == OK)
printf("单链表L的第 %d 个位置的数据:%d\n", i, e);
else
printf("单链表L的第 %d 个位置的数据不存在!\n", i);
}
void main()
{
int choice = 0; //用户功能选择
LinkList L;
InitLinkList_L(L); //初始化单链表
while(1)
{
system("CLS");
ShowMenu();
printf("Please choose(请选择): ");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
OutputList_L(L); //调用输出函数对链表的数据进行输出
fflush(stdin);
system("pause");
break;
}
case 2:
{
SubMenu2(L); //调用菜单2功能,实现数据的插入操作
fflush(stdin);
system("pause");
break;
}
case 3:
{
SubMenu3(L);
fflush(stdin);
system("pause");
break;
}
case 4:
{
SubMenu4(L);
getchar(); getchar(); system("CLS");
break;
}
case 5:
{
ClearLis_L(L);
fflush(stdin);
system("pause");
break;
}
case 0:
{
system("CLS");
printf("谢谢使用!\n");
exit(0);
}
default:
{
printf("功能选择错误,只能选择0-5!\n");
fflush(stdin);
system("pause");
}
}
}
}
单链表创建(尾插法)
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define FALSE 0
#define ERROR -1
#define OVERFLOW -2
typedef int ElemType;
//单链表结点结构定义
typedef struct LNode
{
ElemType data; //每个结点实际存放的数据—数据域
struct LNode *next; //下一个结点的地址—指针域
}LNode, *LinkList;
int CreateList(LinkList &L, int n)
{
int i;
LinkList tail, p;
L = (LinkList) malloc (sizeof (LNode));
if(!L)
return ERROR;
L->next = NULL;
tail = NULL;
for(i = 1; i <= n; i++)
{
p = (LinkList) malloc (sizeof (LNode));
if(!p)
return ERROR;
printf("\n\n第%d个数据为:", i);
scanf("%d", &p->data); // 输入元素值
p->next = NULL;
if(i == 1)
L->next = p;
else
tail->next = p;
tail = p;
}
return OK;
}
void TransverList(LinkList L)
{
LinkList p;
int j;
p = L->next; j = 0;
while(p)
{
j++;
printf("第%d个数据为:", j);
printf("%d\n\n", p->data);
p = p->next;
}
}
void main()
{
LinkList L;
int n;
printf(" *******************************************************************\n\n");
printf(" 创建链表——尾插法\n\n");
printf(" *******************************************************************\n\n");
printf("数据个数:");
scanf("%d", &n);
CreateList(L, n);
printf("\n\n链表中的数据浏览结果\n\n");
TransverList(L);
}
静态链表
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define FALSE 0
#define ERROR -1
#define OVERFLOW -2
#define MAXSIZE 10 // 静态链表的最大长
typedef int Status;
typedef int ElemType;
struct Component //静态链表的结点结构定义
{
ElemType data;
int cur; //相对地址,相对于0号位置的地址,实际上就是数组的下标
};
//功能:实现静态链表的初始化操作,初始化成功,返回OK
Status InitStaticList(Component VList[ MAXSIZE + 1])
{
int i;
VList[0].cur = -1; //置该静态链表为空链表
for(i = 1; i <= MAXSIZE; i++) //置该静态链表的每个空间都可以存放数据
VList[i].cur = 0; //每个空间的cur为0表示该空间可以存放数据,否则表示该空间已经存放数据
return OK;
}
//功能:实现静态链表数据的全部输出
void OutputStaticList( Component VList[MAXSIZE + 1])
{
int i = 0, k = 1;
if( VList[0].cur == -1)
printf("\n 静态链表为空,无数据!\n");
else
{
printf("\n静态链表中的数据为:");
i = 0;
while( VList[i].cur != -1)
{
printf("第 %d 数据为:%d\n", k, VList[VList[i].cur].data);
i = VList[i].cur; k++;
}
}
}
//功能:实现静态链表数据的插入,插入数据是在尾部插入(也可实现在第i个位置插入数据),成功返回1,否则,返回0
Status InsertStaticList(Component VList[MAXSIZE + 1], ElemType e)
{
int i = 0, pos = 0;
if(VList[0].cur == -1) //空表时,插入数据的位置为1号位置
pos = 1;
else //非空表,插入的位置不清楚,因此需检索哪个空闲,就写入到该空间
{
for(i = 1; i <= MAXSIZE; i++) //寻找第一个可插入位置
if( VList[i].cur == 0)
break;
if( i >= MAXSIZE) //空间全部全部使用,则无插入位置
return ERROR;
else
pos = i; //将插入位置赋给pos
}
if(VList[0].cur == -1) //空表时,插入数据的位置为1号位置
i = 0;
else
{
for(i = 1; i <= MAXSIZE; i++) //寻找链表的最后一个数据位置
if( VList[i].cur == -1)
break;
if( i>= MAXSIZE)
return ERROR;
}
if( pos == 0)
return 0;
else
{
VList[pos].data = e;
VList[i].cur = pos;
VList[pos].cur = -1;
return OK;
}
}
//功能:实现静态链表数据的删除,删除成功,则返回该数据在静态链表中的位置,否则返回0
int DeleteStaticList(Component VList[MAXSIZE + 1], ElemType e)
{
int i = 0, k = 1;
if(VList[i].cur == -1) //空的静态表,不能删除数据
return 0;
while(VList[VList[i].cur].data != e)
i = VList[i].cur;
if( i == -1) //没找到
return 0;
else //找到,i存储的是被删除元素的前驱
{
k = VList[i].cur;
VList[i].cur = VList[k].cur;
VList[k].cur = 0; //该位置空出,可以写入新的数据
}
return OK;
}
//功 能:实现静态链表数据的查询,成功返回该数据在链表中的位置,否则,返回0
int SearchStaticList(Component VList[MAXSIZE + 1], ElemType e)
{
int i = 0;
if(VList[0].cur = -1)
return 0;
i = 1;
while(VList[i].cur != -1) //注意:不能按数组的方式从上到下扫描,不然可能找到以前的数据。必须按链表的方式进行扫描
if(VList[i].data != e)
i = VList[i].cur;
if( i == -1) //没找到
return 0;
else
return i; //找到返回其所在的下标
}
void ShowMenu() //主菜单
{
printf("\n");
printf("\n****************静态链表基本操作****************\n\n");
printf("\t\t1 静态链表初始化\n\n");
printf("\t\t2 静态链表数据显示\n\n");
printf("\t\t3 静态链表数据插入\n\n");
printf("\t\t4 静态链表数据删除\n\n");
printf("\t\t5 静态链表数据查询\n\n");
printf("\t\t0 退 出(exit)\n\n");
printf("****************静态链表基本操作****************\n");
printf("\n");
}
void main()
{
int choice = 0; //功能选项
ElemType e;
Component VList[MAXSIZE + 1];
InitStaticList(VList); //初始化
while(1)
{
system("CLS");
ShowMenu();
printf("Please choose: ");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
printf("严重警告:重新初始化静态链表,会使原有数据丢失!\n");
if (InitStaticList(VList) == 1)
printf("\n静态链表初始化成功!\n\n");
fflush(stdin);
system("pause");
break;
}
case 2:
{
OutputStaticList(VList);
fflush(stdin);
system("pause");
break;
}
case 3:
{
printf("插入数据:");
scanf("%d", &e);
InsertStaticList(VList, e);
fflush(stdin);
system("pause");
break;
}
case 4:
{
printf("删除数据:");
scanf("%d", &e);
DeleteStaticList(VList, e);
fflush(stdin);
system("pause");
break;
}
case 5:
{
printf("查询数据:");
scanf("%d", &e);
InsertStaticList(VList, e);
fflush(stdin);
system("pause");
break;
}
case 0:
{
system("CLS");
printf("Thanks for using!\n");
exit(0);
}
default:
{
printf("功能选择错误,只能选择0-5!\n");
fflush(stdin);
system("pause");
}
}
}
}
文章评论