定制企业网站建设哪家好,开发app需要的技术,东莞个人网站推广建设,金融品牌网站设计单链表简介
单链表结构
头指针是指向链表中第一个结点的指针
首元结点是指链表中存储第一个数据元素a1的结点
头结点是在链表的首元结点之前附设的一个结点#xff1b;数据域内只放空表标志和表长等信息 单链表存储结构定义#xff1a;
typedef struct Lnode
{ ElemTyp…单链表简介
单链表结构
头指针是指向链表中第一个结点的指针
首元结点是指链表中存储第一个数据元素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 -2typedef 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;}elsereturn 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; //头结点指针指向新的数据结点}elsereturn 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(ji)){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);elseprintf(\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);elseprintf(插入位置%d 错误!\n, i);
}//功能菜单3的操作处理实现在单链表的第i个位置删除数据e的操作
void SubMenu3(LinkList L)
{//ListDelete_Lint i;ElemType e;printf(删除位置);scanf(%d, i);if(ListDelete_L(L, i, e) OK)printf(在单链表L的第 %d 位置成功删除数据 %d .\n, i, e);elseprintf(删除位置%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);elseprintf(单链表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 -2typedef 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;elsetail-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; elsepos 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;elsereturn 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);}}}
}
