关键词：
★线性表是一个序列（线性结构），具有一定的顺序
★如果有多个元素，第一个元素没有前驱，最后一个元素没有后继
★线性表强调是有限的
一．线性表基本存储结构
㈠.顺序表
——把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里，用这种方法存储的线性表简称顺序表
——在顺序表中，线性表的逻辑顺序与物理顺序一致
——在顺序表中，数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现
㈡.单链表
——把线性表的元素任意存放在存储单元结点中，节点之间按照逻辑顺序通过一个个指针依次链接起来，用这种方式存储的线性表简称单链表
——在单链表中，存储单元结点可以是连续的，也可以是不连续的，甚至是零散分布在内存中任意位置上的
——在单链表中，线性表的逻辑顺序与物理顺序不一定相同
——在单链表中，数据元素之间的关系是通过节点间的指针来实现的
1）不带头结点的单链表
2）带头结点的单链表
二.抽象数据类型定义
struct list; //定义结构体作为存储的一级结构
list_init(); //初始化线性表，创建存储空间并返回指向该空间的指针
free(struct list list); //释放内存
clear(struct list list); //清空已定义的存储结构中的元素
isempty(struct list list); //判断存储结构中是否存储有数据元素
count(struct list list); //查看存储结构中存储有多少个数据元素
add(struct list list,int index,int e); //将数据元素存储入已定义的存储结构的指定位置
remove(struct list list,int index); //将线性表指定位置的元素移除
get(struct list list,int index); //将线性表指定位置的元素取出
set(struct list list,int index,int e); //修改线性表指定位置的元素值
lookup(struct list *list,int e); //查看数据e是否存在该线性表中
三.代码实现
list.h
#ifndef __LIST_H__
#define __LIST_H__
struct list;
struct list *list_init();
void list_free(struct list *list);
void list_clear（struct list *list）;
int list_isempty(struct list *list);
int list_count(struct list *list);
void list_add(struct list *list,int index,int e);
int list_remove(struct list *list,int index);
int list_get(struct list *list,int index);
void list_set(struct list *list,int index,int e);
int list_lookup(struct list *list,int e);
#endifmain.c
#include <stdlib.h>
#include <stdlib.h>
include <list.h>
//定义两个线性表，比较两个线性表中的元素，去除两个表中重复的元素
int main()
//定义指向list结构体的结构体指针变量lista/listb
struct list *lista=NULL;
struct list *listb=NULL;
//初始化lista，创建线性表并把首地址赋值给lista
lista=list_init();
//将0存储到lista指向的线性表存储结构的0号位置处
list_add(lista,0,0);
//将2存储到lista指向的线性表存储结构的0号位置处，之前定义在0号位置处的数据元素0会按照.c文件中实现的算法自动移动到0号位置后面作为1号位置的元素
list_add(lista,0,2);
list_add(lista,0,5);
listb=list_init();
list_add(listb,0,2);
list_add(list,0,1314);
list_add(listb,0,5)；
int i,j,flag;
//遍历listb指向的线性表存储结构
for(i=0;i<list_count(listb);j++)
falg=1;
for(j=0;i<list_count(lista);j++)//遍历lista指向的线性表存储结构
if(list_get(listb,i)==list_get(lista,j)) //两个线性表元素对比，相同的去除
flag=0;
break;
if(flag==1)//两表不同的元素存储(添加）到lista指向存储结构已有元素的后面
list_add(lista,list_count(lista),list_get(listb,i));
//将lista指向的存储结构的数据元素循环打印
for(i=0;i<list_count(lista);i++)
printf(“%d
”,list_get(lista,i));
list_free(lista);
list_free(listb);
return 0;
list.c
顺序表
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "list.h"
//定义数组初始长度为1，每次添加的长度为1
#define LIST_INIT_SIZE 1
#define LIST_INCR_SIZE 1
//定义结构体list作为一级结构，指针变量bottom指向数组，count变量计算线性表中已有元素的个数，size变量计算定义的结构中数组的定义的长度
struct list
int *bottom;
int count;
int size;
;
struct list *list_init()
struct list *list=NULL;
list=(struct list *)malloc(sizeof(struct list));
if(list==NULL) return NULL;
assert(list!=NULL);
list->bottom=NULL;
list->count=0;
list->size=0;
list->bottom=(int *)malloc(sizeof(int)*LIST_INIT_SIZE);
if(list->bottom==NULL)
free(list);
return NULL;
assert(list->bottom!=NULL);
//将定义的存储结构中的数组空间清零
memset(list->bottom,0,sizeof(int)*LIST_INIT_SIZE);
list->size=LIST_INIT_SIZE;
return list;
void list_free(struct list *list)
assert(list->bottom!=NULL);
assert(list!=NULL);
free(list->bottom);
free(list);
void list_clear(struct list *list)
assert(list->bottom!=NULL);
assert(list!=NULL);
list->count=0;
int list_isempty(struct list *list)
assert(list->bottom!=NULL);
assert(list!=NULL);
return (list->count==0);
int list_count(struct list *list)
assert(list->bottom!=NULL);
assert(list!=NULL);
return list->count;
void list_add(struct list *list,int index,int e)
assert(list->bottom!=NULL);
assert(list!=NULL);
//为了防止定义数组长度不够，使用realloc动态增加数组长度
if(list->count==list->size)
list->bottom=(int *)realloc(list->bottom,sizeof(int)*(list->size+LIST_INCR_SIZE));
list->size+=LIST_INCR_SIZE;
int i;
//将数据元素e添加到数组指定位置index，先将index后面的数据元素都后移一位
for(i=list->count-1;i>index-1;i--)
list->bottom[i+1]=list->bottom[i];
//将数据元素e添加到线性表存储结构index位置处
list->bottom[index]=e;
//记录线性表存储结构元素+1
list->count++;
return;
int list_remove(struct list *list,int index)
assert(list->bottom!=NULL);
assert(list!=NULL);
assert(index>=0&&index<list->count);
int i;
int result=-1;
//将线性表存储结构中数组index位置处数据元素取出
result=list->bottom[index];
//将index位置后面的元素均往前一位，覆盖掉数组index位置处的值
for(i=index;i<list->count-1;i++)
list->bottom[i]=list->bottom[i+1];
//记录线性表存储结构的数组元素减少一位
list->count--;
return result;
int list_get(struct list *list,int index)
assert(list->bottom!=NULL);
assert(list!=NULL);
assert(index>=0&&index<list->count);
int result=-1;
result=list->bottom[index];
return result;
void list_set(struct list *list,int index,int e)
assert(list->bottom!=NULL);
assert(list!=NULL);
assert(index>=0&&index<list->count);
list->bottom[index]=e;
return;
int list_lookup(struct list *list,int e)
int i;
//循环遍历数组元素并与数据元素e做比较
for(i=0;i<list->count;i++)
if(list->bottom[i]==e)
return 1;
return 0;
单链表（不带头结点）
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include "list.h"
//定义结构体作为单链表的数据节点，节点中data变量用来存储数据元素，next结构体指针变量用来存储list_node结构体变量的首地址
struct list_node
int data;
struct list_node *next;
;
//定义结构体作为一级结构，一级结构中head用来引用结构体list_node类型的数据节点，count用来记录单链表存储结构中一共使用的数据节点的数量
struct list
struct list_node *head;
int count;
;
struct list *list_init()
struct list *list=NULL;
list=(struct list *)malloc(sizeof(struct list));
if(list==NULL) return NULL;
assert(list!=NULL);
list->count=0;
list->head=NULL;
return list;
//逐级释放内存空间
void list_free(struct list *list)
assert(list!=NULL);
//定义指向list_node结构体类型的指针变量p
struct list_node *p=NULL;
//如果list引用的head变量中存储有list_node结构体类型的地址（list->head后面有数据节点），执行"断链"操作——用p指向list->head指向的元素，list->head指向该数据节点后面的节点（如果还有的话）
while(list->head!=NULL)
p=list->head;
list->head=p->next;
free(p);
assert(list->head==NULL);
free(list);
void list_clear(struct list *list)
assert(list!=NULL);
struct list_node *p=NULL;
//和list_free中的操作同理
while(list&&list->head!=NULL)
p=list->head;
list->head=p->next;
free(p);
assert(list->head==NULL);
list->count=0;
int list_isempty(struct list *list)
assert(list!=NULL);
return (list->count==0);
int list_count(struct list *list)
assert(list!=NULL);
return list->count;
void list_add(struct list *list,int index,int e)
assert(list!=NULL);
assert(index>=0&&index<=list->count);
int i;
struct list_node *p=NULL;
//定义指向list_node结构体类型的变量p和node
struct list_node *node=NULL;
node=(struct list_node *)malloc(sizeof(struct list_node));
if(node==NULL)
perror("malloc node struct error!");
exit(0);
//将数据元素e存储到已定义的结构体中，构成数据一个数据节点
node->data=e;
node->next=NULL;
//如果是添加第一个数据节点，让list->head代替node指向该数据节点（将该数据节点链接到定义的单链表存储结构中）
if(index==0)
node->next=list->head;
list->head=node;
list->count++;
return;
//如果并不是添加到第一个位置，将指针变量p移动，指向index位置前面的数据节点
p=list->head;
for(i=0;i<index-1;i++)
p=p->next;
//用p->next代替node,将数据节点链接到已定义单链表存储结构上
node->next=p->next;
p->next=node;
list->count++;
return;
int list_remove(struct list *list,int index)
assert(list!=NULL);
assert(index>=0&&index<list->count);
int i;
int result=-1;
struct list_node *p=NULL;
struct list_node *node=NULL;
//移除单链表上第一个数据元素，用node代替list->node，将数据节点取出。list->node指向该节点后一个元素
if(index==0)
node=list->head;
list->head=node->next;
result=node->data;
list->count--;
return result;
p=list->head;
for(i=0;i<index-1;i++)
p=p->next;
node=p->next;
p->next=node->next;
result=node->data;
list->count--;
return result;
void list_set(struct list *list,int index,int e)
assert(list!=NULL);
assert(index>=0&&index<list->count);
int i;
struct list_node *p=NULL;
p=list->head;
for(i=0;i<index;i++)
p=p->next;
p->data=e;
return;
int list_get(struct list *list,int index)
assert(list!=NULL);
assert(index>=0&&index<list->count);
struct list_node *p=NULL;
p=list->head;
int i,result=-1;
for(i=0;i<index;i++)
p=p->next;
result=p->data;
return result;
int list_lookup(struct list *list,int e)
assert(list!=NULL);
int i;
struct list_node *p=NULL;
p=list->head;
for(i=0;i<list->count;i++)
if(p->data==e)
return 1;
break;
p=p->next;
return 0;
单链表（带头结点）
//基本原理参考不带头结点的单链表
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include "list.h"
struct list_node
int data;
struct list_node *next;
;
struct list
struct list_node *head;
int count;
;
struct list *list_init()
struct list *list=NULL;
list=(struct list *)malloc(sizeof(struct list));
if(list==NULL) return NULL;
assert(list!=NULL);
list->head=NULL;
list->count=0;
list->head=(struct list_node *)malloc(sizeof(struct list_node));
if(list->head==NULL)
free(list);
return NULL;
assert(list->head!=NULL);
//定义头结点
list->head->data=-1;
list->head->next=NULL;
return list;
void list_free(struct list *list)
assert(list->head!=NULL);
assert(list!=NULL);
struct list_node *p=NULL;
while(list&&list->head!=NULL)
p=list->head;
list->head=p->next;
free(p);
assert(list->head==NULL);
free(list);
return;
void list_clear(struct list *list)
assert(list->head!=NULL);
assert(list!=NULL);
struct list_node *p=NULL;
while(list->head->next!=NULL)
p=list->head->next;
list->head->next=p->next;
free(p);
assert(list->head->next==NULL);
list->count=0;
int list_isempty(struct list *list)
assert(list->head!=NULL);
assert(list!=NULL);
return (list->count==0);
int list_count(struct list *list)
assert(list->head!=NULL);
assert(list!=NULL);
return list->count;
void list_add(struct list *list,int index,int e)
assert(list->head!=NULL);
assert(list!=NULL);
assert(index>=0&&index<=list->count);
int i;
struct list_node *p=NULL;
struct list_node *node=NULL;
node=(struct list_node *)malloc(sizeof(struct list_node));
if(node==NULL)
perror("malloc node struct error!
");
exit(1);
node->data=e;
node->next=NULL;
p=list->head;
for(i=-1;i<index-1;i++)
p=p->next;
node->next=p->next;
p->next=node;
list->count++;
return;
int list_remove(struct list *list,int index)
assert(list->head!=NULL);
assert(list!=NULL);
assert(index>=0&&index<list->count);
int i;
int result=-1;
struct list_node *p=NULL;
struct list_node *node=NULL;
p=list->head;
for(i=-1;i<index-1;i++)
p=p->next;
node=p->next;
p->next=node->next;
list->count--;
result=node->data;
return result;
void list_set(struct list *list,int index,int e)
assert(list->head!=NULL);
assert(list!=NULL);
struct list_node *p=NULL;
int i;
p=list->head;
for(i=-1;i<index;i++)
p=p->next;
p->data=e;
return;
int list_get(struct list *list,int index)
assert(list->head!=NULL);
assert(list!=NULL);
struct list_node *p=NULL;
int result=-1;
int i;
p=list->head;
for(i=-1;i<index;i++)
p=p->next;
result=p->data;
return result;
int list_lookup(struct list *list,int e)
assert(list->head!=NULL);
assert(list!=NULL);
struct list_node *p=NULL;
int i;
p=list->head;
for(i=-1;i<list->count-1;i++)
p=p->next;
if(list->head->data==e)
return 1;
break;
return 0;
四． 编译结果
408数据结构与算法—线性表的定义和分析(代码片段)
【408数据结构与算法】—线性表的定义和分析（二）一、🎆线性表的定义线性表的定义:线性表示具有相同数据类型的n（n>=0）个数据元素的有限序列，其中n为表长，当n=0时，线性表是一个... 查看详情
考研数据结构与算法线性表(代码片段)
文章目录一、线性表定义二、线性表基本操作三、线性表的顺序表示3.1顺序表特点3.2操作实现3.2.1插入操作3.2.2删除操作3.2.3查找操作3.3顺序表合并四、线性表的链式表示4.1链式表特点4.2操作实现4.2.1下标找值4.2.2按值查找4.2.3头部... 查看详情
数据结构与算法学习笔记线性表ⅱ(代码片段)
数据结构与算法学习笔记(4)线性表Ⅱ文章目录数据结构与算法学习笔记(4)线性表Ⅱ一.线性表的链式表示和实现1.链式存储结构情境引入2.链式存储相关术语结点链表单链表、双链表、循环链表头指针、头结点和首元结点单链表的... 查看详情
数据结构与算法之线性表(超详细顺序表链表)(代码片段)
前言通过前面数据结构与算法基础知识我么知道了数据结构的一些概念和重要性，那么我们今天总结下线性表相关的内容。当然，我用自己的理解解分享给大家。其实说实话，可能很多人依然分不清线性表，顺序表，和链表之间... 查看详情
数据结构与算法查找(search)详解(代码片段)
文章目录查找查找概论一、查找的基本概念顺序表查找一、定义二、算法有序表查找一、折半查找二、插值查找三、斐波那契查找线性索引查找一、稠密索引二、分块索引三、倒排索引二叉树排序与平衡二叉树一、二叉排序树1... 查看详情
数据结构与算法-线性表之双向链表(代码片段)
参考博客：http://www.cnblogs.com/skywang12345/p/3561803.htmlhttps://blog.csdn.net/howlaa/article/details/385132351、概述线性表是一种线性结构，由数组、单项链表和双向链表组成，这里讲讨论双向链表的理论知识和实现代码。双向链表和单项链表类... 查看详情
数据结构与算法-线性表之静态链表(代码片段)
...针，那么在没有引用或指针的语言中，该怎么实现这个的数据结构呢？一、简介 定义：用数组代替指针或引用来描述单链表，即用数组描述的链表叫做静态链表，这种描述方法叫做游标实现法； 上面的静态链表图有两个... 查看详情
数据结构——线性表(代码片段)
目录线性表什么是线性表？线性表抽象数据结构复杂的操作由基本操作组合实现线性表的顺序存储结构顺序表代码描述顺序表元素地址的确定顺序表基本操作初始化顺序表建立顺序表销毁顺序表按照元素查找插入数据删除数据顺... 查看详情
数据结构与算法线性表的链式表示和实现，超详细c语言版(代码片段)
目录链式存储结构与链式存储有关的术语头指针、头结点和首元结点讨论1.如何表示空表？2.在链表中设置头结点有什么好处？3.头结点的数据域内装的是什么？链表（链式存储结构）的特点链表的优缺点优点... 查看详情
《图解数据结构与算法》（java代码实现注释解析算法分析）(代码片段)
文章目录第1章数据结构与算法基础概述1.1数据结构和算法的重要性1.2数据结构概述逻辑结构存储结构1.3算法概述如何理解“大O记法”时间复杂度空间复杂度第2章数组2.1数组概念2.2无序数组2.3有序数组第三章栈3.1栈概念3.2栈的操... 查看详情
数据结构和算法分析之线性表(代码片段)
1.结构目录如图:自定义数组越界异常：/***@ClassName:OutOfBoundaryException*@Description:TODO自定义的数组越界的异常*@author萨摩耶*@date2018年4月29日下午3:37:11**/@SuppressWarnings("serial")publicclassOutOfBoundaryExceptionextendsException 查看详情
[nefu数据结构]阶段一复习(代码片段)
文章目录[NEFU数据结构]阶段一复习算法模块第1章绪论1.2基本概念和术语逻辑结构：存储结构：1.3抽象数据类型的表示与实现1.4算法和算法分析第2章线性表2.3~2.4线性表的顺序存储结构2.5线性表的链式表示和实现单链表循... 查看详情
数据结构与算法图(graph)详解(代码片段)
文章目录图图的基本概念一、图的定义二、图的基本概念和术语1、有向图2、无向图3、简单图4、多重图5、完全图（也称简单完全图）6、子图7、连通、连通图和连通分量8、强连通图、强连通分量9、生成树、生成森林10、... 查看详情
数据结构与算法--栈和队列(代码片段)
栈定义栈是限定仅在表尾进行插入或删除操作的线性表。因此对栈来说，表尾端有其特殊含义，称为栈顶，表头端称为栈底。不含元素的空表称为空栈。栈顶实现元素的进出，栈的修改遵循后进先出的原则。因此，栈又称为后进... 查看详情
数据结构与算法线性表(代码片段)
✍、目录总览1、线性表定义：线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为：L=(a1,a2,....,ai,ai+1,.....,an)线性... 查看详情
数据结构与算法--线性表(代码片段)
定义及特性定义是n个数据元素的有限序列，若将线性表记为((a_1,...,a_i-1,a_i,a_i+1,...,a_n))，则表中(a_i-1)领先于(a_i)，(a_i)领先于(a_i+1)，称(a_i-1)是(a_i)的直接前驱元素，(a_i+1)是(a_i)的直接后继元素。线性表元素的个数(n(n>=0))定义为... 查看详情
[算法与数据结构]谈谈线性查找法~(代码片段)
[算法与数据结构]一文详解线性查找法~📅前言一、📝算法基础知识1、什么是算法2、算法的五大特性二、📈线性查找法1、举例阐述2、实现线性查找法3、使用泛型4、升级改造5、使用自定义类6、循环不变量三、Ὄ... 查看详情
[算法与数据结构]谈谈线性查找法~(代码片段)
[算法与数据结构]一文详解线性查找法~📅前言一、📝算法基础知识1、什么是算法2、算法的五大特性二、📈线性查找法1、举例阐述2、实现线性查找法3、使用泛型4、升级改造5、使用自定义类6、循环不变量三、Ὄ... 查看详情