前言：
这次介绍基本数据结构的线性表和链表，并用C语言进行编写；建议最开始学数据结构时，用C语言；像栈和队列都可以用这两种数据结构来实现。
一、线性表基本介绍
1 概念：
线性表也就是关系户中最简单的一种关系，一对一。
如：学生学号的集合就是一个线性表。
2 特征：
① 有且只有一个“首元素“。
② 有且只有一个“末元素”。
③ 除“末元素”外，其余元素均有唯一的后继元素。
④ 除“首元素”外，其余元素均有唯一的前驱元素。
3 存储划分：
① 如果把线性表用“顺序存储”，那么就是“顺序表”。
② 如果把线性表用“链式存储”，那么就是“链表”。
4 常用操作：
添加，删除，插入，查找，遍历，统计。
二、线性表实现
主要实现线性表的创建、销毁和插入等操作，将接口封装在.h文件中，如下：
#ifndef __MY_SEQLIST_H__
#define __MY_SEQLIST_H__ typedef void SeqList;
typedef void SeqListNode; SeqList* SeqList_Create(int capacity); //创建线性表 void SeqList_Destroy(SeqList* list); //销毁 void SeqList_Clear(SeqList* list); //清空 int SeqList_Length(SeqList* list); //求线性表的长度 int SeqList_Capacity(SeqList* list); //求线性表的容量 int SeqList_Insert(SeqList* list, SeqListNode* node, int pos); //向线性表中插入元素 SeqListNode* SeqList_Get(SeqList* list, int pos); //获取指定位置元素 SeqListNode* SeqList_Delete(SeqList* list, int pos); //删除指定位置元素 #endif //__MY_SEQLIST_H__
注意：定义头文件时，要包含“#ifndef”，防止头文件重复包含！
1、线性表创建
主要就是对节点分配内存，代码如下：
//在结构体中套1级指针
//
typedef struct _tag_SeqList
{
int length;
int capacity;
unsigned int *node; //int* node[]
}TSeqList; SeqList* SeqList_Create(int capacity)
{
int ret = ;
TSeqList *tmp = NULL; tmp = (TSeqList *)malloc(sizeof(TSeqList));
if (tmp == NULL)
{
ret = -;
printf("func SeqList_Create() err:%d \n", ret);
return NULL;
}
memset(tmp, , sizeof(TSeqList)); //根据capacity 的大小分配节点的空间
tmp->node = (unsigned int *)malloc(sizeof(unsigned int *) * capacity);
if (tmp->node == NULL)
{
ret = -;
printf("func SeqList_Create() err: malloc err %d \n", ret);
return NULL;
}
tmp->capacity = capacity;
tmp->length = ;
return tmp;
} void SeqList_Destroy(SeqList* list)
{
TSeqList *tlist = NULL;
if (list == NULL)
{
return ;
}
tlist = (TSeqList *)list;
if (tlist->node != NULL)
{
free(tlist->node);
} free(tlist); return ;
}
2、线性表插入
插入在业界有默认的规则吧，下面将要讲到的链表也是用这个规则。用图来讲解一下吧，如下：
讲解：例如，已经有线性表34、33、32、31，在1位置想插入35，想把从1开始的先后移，再插入，插入后的线性表如右图所示。
线性表插入代码如下：
int SeqList_Insert(SeqList* list, SeqListNode* node, int pos)
{
int i =, ret = ;
TSeqList *tlist = NULL; if (list == NULL || node==NULL || pos<)
{
ret = -;
printf("fun SeqList_Insert() err:%d \n", ret);
return ret;
}
tlist = (TSeqList*)list; //判断是不是满了
if (tlist->length >= tlist->capacity)
{
ret = -;
printf("fun SeqList_Insert() (tlist->length >= tlist->capacity) err:%d \n", ret);
return ret;
} //容错修正 6个长度 容量20;用户pos10位置插入..
if (pos>=tlist->length)
{
pos = tlist->length; //
} //1 元素后移
for(i=tlist->length; i>pos; i--)
{
tlist->node[i] = tlist->node[i-];
//a[7] = a[6]
}
// i = 3
// 2插入元素
tlist->node[i] = (unsigned int )node;
tlist->length ++;
return ;
}
3、获取指定位置元素
根据pos位置获取元素，代码如下：
SeqListNode* SeqList_Get(SeqList* list, int pos)
{
int i =;
SeqListNode *ret = ;
TSeqList *tlist = NULL; if (list == NULL || pos<)
{
printf("fun SeqList_Get() err:%d \n", ret);
return NULL;
}
tlist = (TSeqList*)list; ret = (void *)tlist->node[pos];
return ret;
}
4、删除指定位置元素
将指定位置的元素进行删除，代码如下：
SeqListNode* SeqList_Delete(SeqList* list, int pos)
{
int i = ;
SeqListNode *ret = ;
TSeqList *tlist = NULL; if (list == NULL || pos<) //检查
{
printf("fun SeqList_Delete() err:%d \n", ret);
return NULL;
}
tlist = (TSeqList*)list; ret = (SeqListNode *)tlist->node[pos]; //缓存pos的位置 for (i=pos+; i<tlist->length; i++) //pos位置后面的元素前移
{
tlist->node[i-] = tlist->node[i];
}
tlist->length --;
return ret;
}
5、总体代码
整个seqlist.c代码如下，方便使用与调试：
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "seqlist.h" //在结构体中套1级指针
//
typedef struct _tag_SeqList
{
int length;
int capacity;
unsigned int *node; //int* node[]
}TSeqList; SeqList* SeqList_Create(int capacity)
{
int ret = ;
TSeqList *tmp = NULL; tmp = (TSeqList *)malloc(sizeof(TSeqList));
if (tmp == NULL)
{
ret = -;
printf("func SeqList_Create() err:%d \n", ret);
return NULL;
}
memset(tmp, , sizeof(TSeqList)); //根据capacity 的大小分配节点的空间
tmp->node = (unsigned int *)malloc(sizeof(unsigned int *) * capacity);
if (tmp->node == NULL)
{
ret = -;
printf("func SeqList_Create() err: malloc err %d \n", ret);
return NULL;
}
tmp->capacity = capacity;
tmp->length = ;
return tmp;
} void SeqList_Destroy(SeqList* list)
{
TSeqList *tlist = NULL;
if (list == NULL)
{
return ;
}
tlist = (TSeqList *)list;
if (tlist->node != NULL)
{
free(tlist->node);
} free(tlist); return ;
} //清空链表 //回到初始化状态
void SeqList_Clear(SeqList* list)
{
TSeqList *tlist = NULL;
if (list == NULL)
{
return ;
}
tlist = (TSeqList *)list;
tlist->length = ;
return ;
} int SeqList_Length(SeqList* list)
{
TSeqList *tlist = NULL;
if (list == NULL)
{
return -;
}
tlist = (TSeqList *)list;
return tlist->length;
} int SeqList_Capacity(SeqList* list)
{ TSeqList *tlist = NULL;
if (list == NULL)
{
return -;
}
tlist = (TSeqList *)list;
return tlist->capacity;
} int SeqList_Insert(SeqList* list, SeqListNode* node, int pos)
{
int i =, ret = ;
TSeqList *tlist = NULL; if (list == NULL || node==NULL || pos<)
{
ret = -;
printf("fun SeqList_Insert() err:%d \n", ret);
return ret;
}
tlist = (TSeqList*)list; //判断是不是满了
if (tlist->length >= tlist->capacity)
{
ret = -;
printf("fun SeqList_Insert() (tlist->length >= tlist->capacity) err:%d \n", ret);
return ret;
} //容错修正 6个长度 容量20;用户pos10位置插入..
if (pos>=tlist->length)
{
pos = tlist->length; //
} //1 元素后移
for(i=tlist->length; i>pos; i--)
{
tlist->node[i] = tlist->node[i-];
//a[7] = a[6]
}
// i = 3
// 2插入元素
tlist->node[i] = (unsigned int )node;
tlist->length ++;
return ;
} SeqListNode* SeqList_Get(SeqList* list, int pos)
{
int i =;
SeqListNode *ret = ;
TSeqList *tlist = NULL; if (list == NULL || pos<)
{
printf("fun SeqList_Get() err:%d \n", ret);
return NULL;
}
tlist = (TSeqList*)list; ret = (void *)tlist->node[pos];
return ret;
} SeqListNode* SeqList_Delete(SeqList* list, int pos)
{
int i = ;
SeqListNode *ret = ;
TSeqList *tlist = NULL; if (list == NULL || pos<) //检查
{
printf("fun SeqList_Delete() err:%d \n", ret);
return NULL;
}
tlist = (TSeqList*)list; ret = (SeqListNode *)tlist->node[pos]; //缓存pos的位置 for (i=pos+; i<tlist->length; i++) //pos位置后面的元素前移
{
tlist->node[i-] = tlist->node[i];
}
tlist->length --;
return ret;
}
6、调试
写一个main函数，进行上面的接口调用与调试，代码如下：
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "seqlist.h"
typedef struct _Teacher
{
int age;
char name[];
}Teacher; void main()
{
int ret = , i = ;
SeqList* list = NULL; Teacher t1, t2, t3, t4,t5;
t1.age = ;
t2.age = ;
t3.age = ;
t4.age = ;
t5.age = ; list = SeqList_Create();
if (list == NULL)
{
printf("func SeqList_Create() ret :%d \n", ret);
return ;
} ret = SeqList_Insert(list, (SeqListNode*) &t1, ); //头插法
ret = SeqList_Insert(list, (SeqListNode*) &t2, ); //头插法
ret = SeqList_Insert(list, (SeqListNode*) &t3, ); //头插法
ret = SeqList_Insert(list, (SeqListNode*) &t4, ); //头插法
ret = SeqList_Insert(list, (SeqListNode*) &t5, ); //头插法 //遍历
for (i=; i<SeqList_Length(list); i++)
{
Teacher* tmp = (Teacher *) SeqList_Get(list, i);
if (tmp == NULL)
{
return ;
}
printf("tmp->age:%d ", tmp->age);
} //删除链表中的节点
while( SeqList_Length(list) > )
{
SeqList_Delete(list, );
} system("pause"); return ;
}
三、链表
1、介绍
链表的大体有三种实现方式，用图进行讲解吧，如下图：
说明：最上面就是最传统链表，每个节点存一个next指针，保存下一个节点的地址
中间是linux内核实现的链表，一般是双向链表，有一个缺点要记录偏移量
最后是改进之后的链表，不需要记录偏移量，这是前人的智慧，我将采用最后一种进行实现。
2、定义头文件
头文件主要包含结构体定义，和接口声明，主要实现链表初始化、插入、遍历等操作，头文件如下：
#ifndef LINKLIST_H
#define LINKLIST_H #include<stdlib.h>
#include<stdio.h> //链表结点
typedef struct LINKNODE{
void* data; //指向任何类型的数据
struct LINKNODE* next;
}LinkNode; //链表结构体
typedef struct LINKLIST{
LinkNode* head;
int size;
}LinkList; //定义函数指针
typedef void(*PRINTLINKNODE)(void*); //初始化链表
LinkList* Init_LinkList();
//指定位置插入
void Insert_LinkList(LinkList* list,int pos,void* data);
//删除指定位置的值
void RemoveByPos_LinkList(LinkList* list, int pos);
//获得链表的长度
int Size_LinkList(LinkList* list);
//查找
int Find_LinkList(LinkList* list,void* data);
//返回第一个结点
void* Front_LinkList(LinkList* list);
//打印链表结点
void Print_LinkList(LinkList* list, PRINTLINKNODE print);
//释放链表内存
void FreeSpace_LinkList(LinkList* list); #endif
3、插入节点
初始化链表跟线性表类似，就不在过多说明了，主要讲解插入和删除节点，对插入节点进行讲解，如下图：
说明：需要两个指针current、node，假如在3号位置进行插入，要先处理node->next，node指向3号位置，就把3号位置指针付给它，node->next=current->next;
2号位置指向node，把node指针赋值给它，current->next=node;
注意：图片左下角的红字，是理解链表插入、删除等的关键！
代码如下：
//指定位置插入
void Insert_LinkList(LinkList* list, int pos, void* data){ if (list == NULL){
return;
}
if (data == NULL){
return;
} //友好的处理，pos越界
if (pos < || pos > list->size) {
pos = list->size;
} //创建新的结点
LinkNode* newnode = (LinkNode*)malloc(sizeof(LinkNode));
newnode->data = data;
newnode->next = NULL; //找结点
//辅助指针变量
LinkNode* pCurrent = list->head;
for (int i = ; i < pos;i++){
pCurrent = pCurrent->next;
} //新结点入链表
newnode->next = pCurrent->next;
pCurrent->next = newnode; list->size++;
}
4、删除节点
说明：
删除3号位置，先保存被删除节点的位置，再将2直接指向4；
5、整体代码
整个的代码，方便大家使用和调试，代码如下：
#include"LinkList.h" //初始化链表
LinkList* Init_LinkList(){ LinkList* list = (LinkList*)malloc(sizeof(LinkList));
list->size = ; //头结点 是不保存数据信息
list->head = (LinkNode*)malloc(sizeof(LinkNode));
list->head->data = NULL;
list->head->next = NULL; return list;
}
//指定位置插入
void Insert_LinkList(LinkList* list, int pos, void* data){ if (list == NULL){
return;
}
if (data == NULL){
return;
} //友好的处理，pos越界
if (pos < || pos > list->size) {
pos = list->size;
} //创建新的结点
LinkNode* newnode = (LinkNode*)malloc(sizeof(LinkNode));
newnode->data = data;
newnode->next = NULL; //找结点
//辅助指针变量
LinkNode* pCurrent = list->head;
for (int i = ; i < pos;i++){
pCurrent = pCurrent->next;
} //新结点入链表
newnode->next = pCurrent->next;
pCurrent->next = newnode; list->size++; }
//删除指定位置的值
void RemoveByPos_LinkList(LinkList* list, int pos){
if (list == NULL){
return;
} if (pos < || pos >= list->size){
return;
} //查找删除结点的前一个结点
LinkNode* pCurrent = list->head;
for (int i = ; i < pos;i ++){
pCurrent = pCurrent->next;
} //缓存删除的结点
LinkNode* pDel = pCurrent->next;
pCurrent->next = pDel->next;
//释放删除结点的内存
free(pDel); list->size--;
}
//获得链表的长度
int Size_LinkList(LinkList* list){
return list->size;
}
//查找
int Find_LinkList(LinkList* list, void* data){
if (list == NULL){
return -;
} if (data == NULL){
return -;
} //遍历查找
LinkNode* pCurrent = list->head->next;
int i = ;
while (pCurrent != NULL){
if (pCurrent->data == data){
break;
}
i++;
pCurrent = pCurrent->next;
} return i;
}
//返回第一个结点
void* Front_LinkList(LinkList* list){
return list->head->next->data;
}
//打印链表结点
void Print_LinkList(LinkList* list, PRINTLINKNODE print){
if (list == NULL){
return;
}
//辅助指针变量
LinkNode* pCurrent = list->head->next;
while (pCurrent != NULL){
print(pCurrent->data);
pCurrent = pCurrent->next;
} }
//释放链表内存
void FreeSpace_LinkList(LinkList* list){ if (list == NULL){
return;
} //辅助指针变量
LinkNode* pCurrent = list->head;
while (pCurrent != NULL){
//缓存下一个结点
LinkNode* pNext = pCurrent->next;
free(pCurrent);
pCurrent = pNext;
} //释放链表内存
list->size = ;
free(list); }
6、调试代码
写一个main函数进行调试，如下：
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "LinkList.h" //自定义数据类型
typedef struct PERSON{
char name[];
int age;
int score;
}Person; //打印函数
void MyPrint(void* data){
Person* p = (Person*)data;
printf("Name:%s Age:%d Score:%d\n",p->name,p->age,p->score);
} int main(void){ //创建链表
LinkList* list = Init_LinkList(); //创建数据
Person p1 = { "aaa", , };
Person p2 = { "bbb", , };
Person p3 = { "ccc", , };
Person p4 = { "ddd", , };
Person p5 = { "eee", , }; //数据插入链表
Insert_LinkList(list, , &p1);
Insert_LinkList(list, , &p2);
Insert_LinkList(list, , &p3);
Insert_LinkList(list, , &p4);
Insert_LinkList(list, , &p5); //打印
Print_LinkList(list, MyPrint); //删除3
RemoveByPos_LinkList(list, ); //打印
printf("---------------\n");
Print_LinkList(list, MyPrint); //返回第一个结点
printf("-----查找结果------------\n");
Person* ret = (Person*)Front_LinkList(list);
printf("Name:%s Age:%d Score:%d\n", ret->name, ret->age, ret->score); //销毁链表
FreeSpace_LinkList(list); system("pause");
return ;
}
运行结果如下，供参考：
四、补充C++实现链表
1、头文件
头文件LinkedList.h,代码如下：
#include <iostream> template<class T>
class Node { //节点类
public:
T e; //数据域
Node *next; //指针域 Node(T e, Node *next) : e(e), next(next) { //构造函数的列表初始化
} Node(T e) : e(e), next(nullptr) {
} Node() : next(nullptr) { //无参构造函数
}
}; template<class T>
class LinkedList {
private:
Node<T> *head; //头结点
int size;
public:
class Range {
}; class Empty {
}; LinkedList() { //构造函数
head = new Node<T>();
size = ;
} int getSize() { //获取大小
return size;
} bool isEmpty() { //判断是否为空
return size == ;
} void add(int index, T e) { //指定位置插入元素
if (index < || index > size) {
throw Range();
}
Node<T> *prev = head;
for (int i = ; i < index; ++i) {
prev = prev->next;
}
prev->next = new Node<T>(e, prev->next);
size++;
} void addFirst(T e) { //插入元素 头插法
add(, e);
} void addLast(T e) { //插入元素 尾插法
add(size, e);
} T get(int index) { //获取元素
if (size == ) {
throw Empty();
}
if (index < || index >= size) {
throw Range();
}
Node<T> *cur = head->next;
for (int i = ; i < index; ++i) {
cur = cur->next;
}
return cur->e;
} T getFirst() {
return get();
} T getLast() {
return get(size - );
} void set(int index, T e) {
if (size == ) {
throw Empty();
}
if (index < || index >= size) {
throw Range();
}
Node<T> *cur = head->next;
for (int i = ; i < index; ++i) {
cur = cur->next;
}
cur->e = e;
} void setFirst(T e) {
set(, e);
} void setLast(T e) {
set(size - , e);
} T remove(int index) { //删除指定位置元素
if (index < || index >= size) {
throw Range();
}
if (size == ) {
throw Empty();
}
Node<T> *prev = head;
for (int i = ; i < index; ++i) {
prev = prev->next;
}
Node<T> *retNode = prev->next;
prev->next = retNode->next;
retNode->next = nullptr;
size--;
return retNode->e;
} T removeFirst() {
return remove();
} T removeLast() {
return remove(size - );
} void removeElement(T e) {
Node<T> *prev = head;
while (prev->next != nullptr) {
if (prev->next->e == e) {
break;
}
prev = prev->next;
} if (prev->next != nullptr) {
Node<T> *delNode = prev->next;
prev->next = delNode->next;
delNode->next = nullptr;
size--;
}
} bool contains(T e) { //是否包含
Node<T> *cur = head;
for (int i = ; i < size; ++i) {
cur = cur->next;
if (cur->e == e) {
return true;
}
}
return false;
} void print() { //打印输出
Node<T> *prev = head;
std::cout << "LinkedList: size = " << size << std::endl;
std::cout << "[";
for (int i = ; i < size; ++i) {
prev = prev->next;
std::cout << prev->e;
if (i < size - ) {
std::cout << ", ";
}
}
std::cout << "]" << std::endl;
}
};
2、main函数
main.cpp如下：
#include <iostream>
#include "LinkedList.h" int main() {
LinkedList<int> *linkedList = new LinkedList<int>();
for (int i = ; i < ; ++i) {
linkedList->addFirst(i); //头插法
}
linkedList->add(, ); //指定位置插入元素
linkedList->print(); //打印输出
linkedList->remove(); //删除指定位置元素
linkedList->print();
linkedList->removeFirst();
linkedList->print();
linkedList->removeLast();
linkedList->print();
return ;
}
3、测试
运行结果如下：
总结
虽然线性表和单向链表是数据结构的基础，但完全掌握之后，再学习栈、队列等数据结构将会得心应手；
喜欢的希望帮忙点赞，不懂的欢迎随时留言！
