C语言线性表(基于链式结构)
List.h文件
/**
* C语言线性表(基于链式结构)
* 指定数据类型为整型
* 采用头结点方式
*/
#define TRUE 1
#define FALSE 0
#define OK 1
#define NO 0
typedef int Status;
typedef int ElemType;
//定义表节点的结构
typedef struct Node{
ElemType data;
struct Node* next;
}Node;
//定义表的结构
typedef struct Node* List;
/*
* 初始化线性表
*/
List InitList(int n);
/*
* 销毁线性表
*/
void DestroyList(List l);
/*
* 清空线性表
*/
void ClearList(List l);
/*
* 判断线性表是否为空
*/
Status ListEmpty(List l);
/*
* 计算线性表中元素的个数
*/
int ListLength(List l);
/*
* 获得指定位置元素
*/
Status GetElem(List l, int i, ElemType* e);
/*
* 获得指定元素位置
*/
int LocateElem(List l, ElemType e);
/*
* 获取指定元素的前一个元素
*/
Status PriorElem(List l, int i, ElemType* e);
/*
* 获取指定元素的后一个元素
*/
Status NextElem(List l, int i, ElemType* e);
/*
* 向线性表指定位置插入一个元素
*/
Status ListInsert(List l, int i, ElemType e);
/*
* 删除线性表指定位置的元素
*/
Status ListDelete(List l, int i);
/*
* 输出链表内所有元素的值
*/
void PrintList(List l);
List.c文件
#include <stdio.h>
#include <stdlib.h>
#include "List.h"
List InitList(int n)
{
//{
/*
* 以下是一种正常的初始化方法,为了进一步提高效率还有两种改进方法头插法和尾插法,
* 这两种方法可以减少循环中一次复制运算,并减少了定义临时指针
*/
List l; //定义一个节点指针,用于保存链表第一个节点的地址
l = (List)malloc(sizeof(Node)); //定义一个节点作为头节点并赋给节点指针
l->next = NULL; //初始化头结点
Node *t; //定义一个节点指针,用于保存临时地址
t = l; //将头结点的地址赋给指针
int i;
for(i=1; i<=n; i++){
//创建一个新节点并初始化
Node* p = (Node*)malloc(sizeof(Node));
p->data = i;
p->next = NULL;
t->next = p; //另上个节点的next指针指向p;
t = p; //让t保存新节点p的地址
}
return l;
//}
}
void DestroyList(List l)
{
Node* t;
while(l){
t = l;
l = l->next;
free(t);
}
l = NULL;
}
void ClearList(List l)
{
l = l->next;
while(l){
l->data = 0;
l = l->next;
}
}
Status GetElem(List l, int i, ElemType* e)
{
while(l && i){
l = l->next;
i--;
}
if(i != 0)
return NO;
*e = l->data;
return OK;
}
Status ListEmpty(List l)
{
if(l)
return FALSE;
else
return TRUE;
}
int ListLength(List l)
{
int length = 0;
while(l){
l = l->next;
length++;
}
return length;
}
int LocateElem(List l, ElemType e)
{
l = l->next;
int location = 0;
while(l){
location++;
if(l->data == e)
return location;
l = l->next;
}
return 0;
}
Status PriorElem(List l, int i, ElemType* e)
{
int j = 1;
l = l->next;
Node* tmp_node;
while(l && j<i){
tmp_node = l;
l = l->next;
j++;
}
if(j < i)
return FALSE;
else{
*e = tmp_node->data;
return TRUE;
}
}