C语言线性表（基于链式结构）
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;
}
}
Status NextElem(List l, int i, ElemType* e)
{
while(l && i){
l = l->next;
i--;
}
if(i != 0)
return FALSE;
else{
if(l->next){
*e = l->next->data;
return TRUE;
}else{
return FALSE;
}
}
}
Status ListInsert(List l, int i, ElemType e)
{
l = l->next;
Node* tmp_node;
while(l && i){
tmp_node = l;
l = l->next;
i--;
}
if(i != 0)
return FALSE;
else{
Node* p = (Node*)malloc(sizeof(Node));
p->data = e;
p->next = l;
tmp_node->next = p;
return TRUE;
}
}
Status ListDelete(List l, int i)
{
Node* tmp_node;
while(l && i){
tmp_node = l;
l = l->next;
i--;
}
if(i != 0)
return TRUE;
else{
tmp_node->next = l->next;
free(l);
return TRUE;
}
}
void PrintList(List l)
{
l = l->next;
while(l){
printf("%d\n",l->data);
l = l->next;
}
}
int main()
{
List l = InitList(5);
ElemType tmp_elem = 0;
PrintList(l);
int s = GetElem(l,3,&tmp_elem);
printf("the element is %d\n", tmp_elem);
NextElem(l,3,&tmp_elem);
printf("the goal element's next element is %d\n", tmp_elem);
if(PriorElem(l,3,&tmp_elem))
printf("the goal element's prior element is %d\n", tmp_elem);
int location = LocateElem(l,4);
printf("the location id is %d\n", location);
ListInsert(l,3,8);
PrintList(l);
ListDelete(l,4);
PrintList(l);
return 0;
}
将C语言梳理一下，分布在以下10个章节中：
- Linux-C成长之路（一）：Linux下C编程概要 http://www.linuxidc.com/Linux/2014-05/101242.htm
- Linux-C成长之路（二）：基本数据类型 http://www.linuxidc.com/Linux/2014-05/101242p2.htm
- Linux-C成长之路（三）：基本IO函数操作 http://www.linuxidc.com/Linux/2014-05/101242p3.htm
- Linux-C成长之路（四）：运算符 http://www.linuxidc.com/Linux/2014-05/101242p4.htm
- Linux-C成长之路（五）：控制流 http://www.linuxidc.com/Linux/2014-05/101242p5.htm
- Linux-C成长之路（六）：函数要义 http://www.linuxidc.com/Linux/2014-05/101242p6.htm
- Linux-C成长之路（七）：数组与指针 http://www.linuxidc.com/Linux/2014-05/101242p7.htm
- Linux-C成长之路（八）：存储类，动态内存 http://www.linuxidc.com/Linux/2014-05/101242p8.htm
- Linux-C成长之路（九）：复合数据类型 http://www.linuxidc.com/Linux/2014-05/101242p9.htm
- Linux-C成长之路（十）：其他高级议题