单链表简介

单链表结构

头指针是指向链表中第一个结点的指针

首元结点是指链表中存储第一个数据元素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&&(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");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");}}}
}