单链表的实现
单链表基本概念单链表的实现基本结构初始化操作添加元素插入元素删除元素查找元素
完整测试用例
单链表基本概念
单链表是一种单向的线性表,不需要连续的存储空间.插入删除操作不需要移动元素,只需要改变指针.但是访问元素不是随机的,必须从表头开始依次向后搜索.访问时间和访问位置有关.
单链表的实现
基本结构
typedef struct SeqList{
ElemType data;
struct SeqList *next;
int Length;
//Length表是表内元素个数
};
初始化操作
//初始化链表
SeqList* intList(){
SeqList *T;
T = (SeqList*)malloc(sizeof(SeqList)); //*分配内存* //
//设置头指针
T->data =0;
T->Length = 0;
T->next = NULL;
return T;
}
指针变量的好处是可以直接修改内容的值,避免生成多个表的副本.相比我上一篇相比不在需要返回新的线性表,节约了内存消耗.具体可以参见我上一篇动态分配内存顺序表来体会其中区别.
添加元素
//在表尾添加元素e
void listAdd(SeqList *T,ElemType e){
SeqList *p = intList();
T->Length++; //创建内容为e的节点
p->data = e;
SeqList *a = T; //局部指针防止T改变，也可给T加上控制标识实现
//移动到表尾添加e
while(a->next){
a = a->next;
}
a->next = p;
}
插入元素
//插入元素e
void listInsert(SeqList *T,int i,ElemType e){
SeqList *p = intList();
p->data = e; //创建e节点
SeqList *a = T;
int j;
if(i>T->Length){
//在表尾后方插入
while(T->Length<i){
listAdd(T,0);
}
listAdd(T,e);
}else{
//在表位插入
if(i==T->Length){
listAdd(T,e);
}else{
//在表中插入
if(i>0){
for(j=0;j<i;j++){
a =a->next;
}
p->next = a->next;
a->next = p;
T->Length++;
}else{
printf("参数非法\n");
}
}
}
}
删除元素
//删除位置i的元素
void listDelete (SeqList *T,int i){
int j;
SeqList *a = T;
if(i<1 || i>T->Length){
printf("参数非法\n");
}else{
for(j=1;j<i;j++){
a = a->next;
}
a->next = a->next->next;
}
}
//判断是否为空
bool empty (SeqList *T){
if(T->Length == 0){
return true;
}else{
return false;
}
}
查找元素
//找到元素e的位置
int findElem(SeqList *T,ElemType e){
int i = 1;
SeqList *a = T->next;
while(a){
if(a->data != e){
a = a->next;
i++;
}else{
return i;
}
}
return -1; //e不在表中时返回-1
}
完整测试用例
/*此程序用以链式线性表，主函数已作出测试。
若使用可将整数类型替换为指针来建立广义表。
作者：姚帅 未经允许不得转载*/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h> //载入分配空间的头文件
typedef int ElemType;
typedef struct SeqList{
ElemType data;
struct SeqList *next;
int Length;
//Length表是表内元素个数
};
SeqList* intList(); //初始化链表，带头指针头指针data域为0
void listAdd(SeqList *T,ElemType e); //表尾添加一个元素e
void printall(SeqList *T); //输出表中所有元素
int getlength(SeqList* T); //获得表长度
ElemType getElem(SeqList *T,int i); //获得表的第i个元素
int findElem(SeqList *T,ElemType e); //找到元素e所在的位置
void listInsert(SeqList *T,int i,ElemType e); //在i位置后面插入元素e
void listDelete (SeqList *T,int i); //删除表中第i个元素
bool empty (SeqList *T); //检查表是否为空
void destroyList (SeqList *T); //销毁表
int main(){
SeqList *T =intList();
listAdd(T,10);
listAdd(T,11);
listAdd(T,12);
printf("测试用例为三个元素：");
printall(T);
listInsert(T,5,15);
printf("插入元素到第五个位置后：");
printall(T);
printf("删除第3个元素:");
listDelete(T,3);
printall(T);
printf("检查链表是否为空:%s\n",empty(T)==false?"FALSE":"TRUE");
printf("找到元素11的位置:%d\n",findElem(T,11));
printf("找到表中第5个元素:%d\n",getElem(T,5));
destroyList(T);
getchar();
}
//初始化链表
SeqList* intList(){
SeqList *T;
T = (SeqList*)malloc(sizeof(SeqList)); //*分配内存* //
//设置头指针
T->data =0;
T->Length = 0;
T->next = NULL;
return T;
}
//在表尾添加元素e
void listAdd(SeqList *T,ElemType e){
SeqList *p = intList();
T->Length++; //创建内容为e的节点
p->data = e;
SeqList *a = T; //局部指针防止T改变，也可给T加上控制标识实现
//移动到表尾添加e
while(a->next){
a = a->next;
}
a->next = p;
}
//输出所有元素
void printall(SeqList *T){
SeqList *a = T->next;
while(a){
printf("%d--",a->data);
a = a->next;
}
printf("end\n");
}
//获得表长
int getlength(SeqList* T){
return T->Length;
}
//获得第i个元素
ElemType getElem(SeqList *T,int i){
int j;
SeqList *a =T;
if(i>0 && i<=T->Length){
for(j=0;j<i;j++){
a = a->next;
}
return a->data;
}else{
return -1; //输入非法时输出-1
}
}
//找到元素e的位置
int findElem(SeqList *T,ElemType e){
int i = 1;
SeqList *a = T->next;
while(a){
if(a->data != e){
a = a->next;
i++;
}else{
return i;
}
}
return -1; //e不在表中时返回-1
}
//插入元素e
void listInsert(SeqList *T,int i,ElemType e){
SeqList *p = intList();
p->data = e; //创建e节点
SeqList *a = T;
int j;
if(i>T->Length){
//在表尾后方插入
while(T->Length<i){
listAdd(T,0);
}
listAdd(T,e);
}else{
//在表位插入
if(i==T->Length){
listAdd(T,e);
}else{
//在表中插入
if(i>0){
for(j=0;j<i;j++){
a =a->next;
}
p->next = a->next;
a->next = p;
T->Length++;
}else{
printf("参数非法\n");
}
}
}
}
//删除位置i的元素
void listDelete (SeqList *T,int i){
int j;
SeqList *a = T;
if(i<1 || i>T->Length){
printf("参数非法\n");
}else{
for(j=1;j<i;j++){
a = a->next;
}
a->next = a->next->next;
}
}
//判断是否为空
bool empty (SeqList *T){
if(T->Length == 0){
return true;
}else{
return false;
}
}
//销毁链表
void destroyList (SeqList *T){
SeqList *a = T;
while(a){
T = a->next;
free(a);
a = T;
}
}
测试结果
