不带头节点的单链表

1、操作实现1.1单链表的定义1.2初始化单链表1.3得到单链表表长1.4单链表的判空操作1.5建立单链表1.5.1头插法1.5.2尾插法 1.6按值查找结点1.6.1得到一个结点1.6.2得到该结点的位置 1.7按位查找结点1.7.1得到一个结点1.7.2得到该位置结点的数据 1.8插入数据1.9删除数据1.10输出表中数据1.11清空表 2、全部代码

       相对于带头结点的单链表对每一个结点的操作比较统一，不带头结点的单链表需要对第一个结点进行特殊的对比操作。

1、操作实现

1.1单链表的定义

通过结构体定义每个结点的数据格式

typedef int ElemType;//元素的类型 typedef struct LNode { ElemType data; LNode* next; }LNode,*LinkList;

1.2初始化单链表

通过对单链表之间设置为空完成初始化

//初始化单链表 void InitList(LinkList &L) { L = NULL; }

1.3得到单链表表长

通过遍历实现获得单链表表长，如果第一个结点就为空则返回0

//得到表长 int Length(LinkList L) { int length = 0; if(L == NULL)//首先判断第一个结点是否为空 return length; else length++; while(L->next != NULL) { length++; L = L->next; } return length; }

1.4单链表的判空操作

通过判断第一个结点是否为空，判断单链表是否为空

//判断的单链表是否为空表 bool Empty(LinkList L) { if(L == NULL) return true; else return false; }

1.5建立单链表

建立单链表分头插法和尾插法两种方式

1.5.1头插法

每次插入都在表头的位置

//头插法建立单链表 LinkList List_HeadInsert(LinkList &L) { InitList(L);//初始化 LNode *s; ElemType e; printf("输入元素（输入9999为停止）"); scanf("%d",&e); if(e != 9999)//首先对第一个结点赋值 { L = (LinkList)malloc(sizeof(LNode)); L->next = NULL; L->data = e; scanf("%d",&e); while(e != 9999){ s = (LNode*)malloc(sizeof(LNode)); s->data = e; s->next = L->next; L->next = s; scanf("%d",&e); } } return L; }

1.5.2尾插法

每次插入都在表尾的位置

//尾插法建立单链表 LinkList List_TailInsert(LinkList &L) { InitList(L);//初始化 LNode *s,*r; ElemType e; printf("输入元素（输入9999为停止）"); scanf("%d",&e); if(e != 9999)//首先对第一个结点赋值 { L = (LinkList)malloc(sizeof(LNode)); L->data = e; r = L; scanf("%d",&e); while(e != 9999) { s = (LNode*)malloc(sizeof(LNode)); s->data = e; r->next = s; r = s; scanf("%d",&e); } } r->next = NULL; return L; }

1.6按值查找结点

1.6.1得到一个结点

//在表中查找第一个与查找元素相同位置的结点 LNode* LocateElem_LNode(LinkList L, ElemType e) { int j = 1; LNode* p = L; if(p->data == e)//首先查看第一个结点 return p; else p = p->next; while(p != NULL && p->data != e) { p = p->next; j++; } if(j == Length(L)) { return NULL; } return p; }

1.6.2得到该结点的位置

int LocatedElem(LinkList L, ElemType e) { int j = 1; LNode* p = L; if(p->data == e) return j; else p = p->next; while(p != NULL && p->data != e) { p = p->next; j++; } if(j == Length(L))//到最后一位依然没找到 { return 0; } return j+1; }

1.7按位查找结点

1.7.1得到一个结点

//得到表中某一位置的结点 LNode* GetElem_LNode(LinkList L, int i) { LNode *p = L; if(i < 0 || i > Length(L)) return NULL; for(int j = 1; j < i; j++) { p = p->next; } return p; }

1.7.2得到该位置结点的数据

//获得某一位置元素的值 ElemType GetElem(LinkList L, int i) { LNode *p = L; if(i < 0 || i > Length(L)) return 0; for(int j = 1; j < i; j++) { p = p->next; } return p->data; }

1.8插入数据

向表中对应位置插入数据

//向表中插入数据 bool ListInsert(LinkList &L, int i, ElemType e) { if(i < 1 || i > Length(L)+1) return false; LNode *s = (LNode*)malloc(sizeof(LNode)); s->data = e; if(i == 1) { s->next = L; L = s; return true; } LNode *p = GetElem_LNode(L,i-1); s->next = p->next; p->next = s; return true; }

1.9删除数据

删除表中某一位置的数据

//删除表中某位置的数据 bool ListDelete(LinkList &L, int i, ElemType &e) { if(i < 1 || i > Length(L))//位置不在表中则返回false return false; if(L == NULL)//表为空则返回false return false; LNode* p; LNode* q; if(i == 1)//删除第一个结点的情况 { p = L; e = p->data; q = L->next; free(p);//释放p结点 L = q; return true; } p = GetElem_LNode(L,i-1); q = p->next; e = q->data; p->next = q->next; free(q); return true; }

1.10输出表中数据

通过遍历的方式打印表中数据

//打印单链表的所有数据 void PrintList(LinkList L) { printf("表中的数据为："); if(L != NULL) { printf("%d ",L->data); while(L->next != NULL) { L = L->next; printf("%d ",L->data); } } printf("\n"); }

1.11清空表

删除表中所有数据

//清空表的数据 bool ClearList(LinkList &L) { if(L == NULL)//表空则返回false return false; LNode *p; while(L->next != NULL)//删除第一个结点之后的所有结点 { p = L->next; L->next = p->next; free(p); } L = NULL;//删除第一个结点 return true; }

2、全部代码

#include<stdio.h> #include<stdlib.h> typedef int ElemType;//元素的类型 typedef struct LNode { ElemType data; LNode* next; }LNode,*LinkList; //初始化单链表 void InitList(LinkList &L) { L = NULL; } //得到表长 int Length(LinkList L) { int length = 0; if(L == NULL)//首先判断第一个结点是否为空 return length; else length++; while(L->next != NULL) { length++; L = L->next; } return length; } //判断的单链表是否为空表 bool Empty(LinkList L) { if(L == NULL) return true; else return false; } //头插法建立单链表 LinkList List_HeadInsert(LinkList &L) { InitList(L);//初始化 LNode *s; ElemType e; printf("输入元素（输入9999为停止）"); scanf("%d",&e); if(e != 9999)//首先对第一个结点赋值 { L = (LinkList)malloc(sizeof(LNode)); L->next = NULL; L->data = e; scanf("%d",&e); while(e != 9999){ s = (LNode*)malloc(sizeof(LNode)); s->data = e; s->next = L->next; L->next = s; scanf("%d",&e); } } return L; } //尾插法建立单链表 LinkList List_TailInsert(LinkList &L) { InitList(L);//初始化 LNode *s,*r; ElemType e; printf("输入元素（输入9999为停止）"); scanf("%d",&e); if(e != 9999)//首先对第一个结点赋值 { L = (LinkList)malloc(sizeof(LNode)); L->data = e; r = L; scanf("%d",&e); while(e != 9999) { s = (LNode*)malloc(sizeof(LNode)); s->data = e; r->next = s; r = s; scanf("%d",&e); } } r->next = NULL; return L; } //在表中查找第一个与查找元素相同位置的结点 LNode* LocateElem_LNode(LinkList L, ElemType e) { int j = 1; LNode* p = L; if(p->data == e)//首先查看第一个结点 return p; else p = p->next; while(p != NULL && p->data != e) { p = p->next; j++; } if(j == Length(L)) { return NULL; } return p; } //在表中查找第一个与查找元素相同的结点的位置 int LocatedElem(LinkList L, ElemType e) { int j = 1; LNode* p = L; if(p->data == e) return j; else p = p->next; while(p != NULL && p->data != e) { p = p->next; j++; } if(j == Length(L))//到最后一位依然没找到 { return 0; } return j+1; } //得到表中某一位置的结点 LNode* GetElem_LNode(LinkList L, int i) { LNode *p = L; if(i < 0 || i > Length(L)) return NULL; for(int j = 1; j < i; j++) { p = p->next; } return p; } //获得某一位置元素的值 ElemType GetElem(LinkList L, int i) { LNode *p = L; if(i < 0 || i > Length(L)) return 0; for(int j = 1; j < i; j++) { p = p->next; } return p->data; } //向表中插入数据 bool ListInsert(LinkList &L, int i, ElemType e) { if(i < 1 || i > Length(L)+1) return false; LNode *s = (LNode*)malloc(sizeof(LNode)); s->data = e; if(i == 1) { s->next = L; L = s; return true; } LNode *p = GetElem_LNode(L,i-1); s->next = p->next; p->next = s; return true; } //删除表中某位置的数据 bool ListDelete(LinkList &L, int i, ElemType &e) { if(i < 1 || i > Length(L))//位置不在表中则返回false return false; if(L == NULL)//表为空则返回false return false; LNode* p; LNode* q; if(i == 1)//删除第一个结点的情况 { p = L; e = p->data; q = L->next; free(p);//释放p结点 L = q; return true; } p = GetElem_LNode(L,i-1); q = p->next; e = q->data; p->next = q->next; free(q); return true; } //打印单链表的所有数据 void PrintList(LinkList L) { printf("表中的数据为："); if(L != NULL) { printf("%d ",L->data); while(L->next != NULL) { L = L->next; printf("%d ",L->data); } } printf("\n"); } //清空表的数据 bool ClearList(LinkList &L) { if(L == NULL)//表空则返回false return false; LNode *p; while(L->next != NULL)//删除第一个结点之后的所有结点 { p = L->next; L->next = p->next; free(p); } L = NULL;//删除第一个结点 return true; } int main() { LinkList L; LNode* p; ElemType e; InitList(L); if(Empty(L))//判空 printf("表是空表\n"); else printf("表不是空表\n"); List_TailInsert(L);//尾插法 PrintList(L); printf("表长为%d\n",Length(L)); p = LocateElem_LNode(L,2); printf("6的位置%d\n",LocatedElem(L,6)); printf("2号位置的数据%d\n",GetElem(L,2)); ListInsert(L,2,3);//在第2号位置插入数据3 printf("插入后的数据为"); PrintList(L); ListDelete(L,1,e);//删除一号位置的数据 printf("删除的元素为%d\n",e); printf("删除后的数据为"); PrintList(L); ClearList(L);//清空表 if(Empty(L))//清空之后判空 printf("表是空表\n"); else printf("表不是空表\n"); return 0; }