C语⾔-数据结构-列表⽂章⽬录
线性表
顺序表
链式表
线性表的本质
定义：
由0个或多个数据元素的集合
数据元素之间是有顺序的
数据元素的个数是有限个
数据元素的类型必须相同
专业的定义：
线性表是具有相同类型的n(n>=0)个数据元素的有限序列
(a0,a1,a2,..an)
ai是表项，n是长度
性质：
a0为线性表的第⼀个元素，只有⼀个后继
an为线性表的最后⼀个元素，只有⼀个前驱
除a0和an以外的其他元素ai，既有前驱也有后继.
线性表的操作
创建
销毁
插⼊
删除
获得表中某个位置的元素
获得线性表的长度
清空
线性表的操作对应于我们程序中的⼀组函数
List *List_Create(void);
void List_Destroy(List *list);
c语言listinsert函数void List_Clear(List *list);
int List_Insert(List *list, ListNode *node,int pos)
ListNode *List_Delete(List *list,int pos)
ListNode *List_Get(List *list,int pos)
int List_Length(List *list)
线性表的顺序存储结构
线性表的顺序存储结构是指⽤⼀段地址连续的存储单元依次存储线性表的数据元素
看成C语⾔的数组，⽤C语⾔的⼀维数组实现顺序存储结构
#define MAXSIZE 20 //线性表的最⼤容量
typedef struct _list {
char node[MAXSIE];//存储空间的起始地址是node
int length;//表⽰线性表的当前长度
}List;
获得元素的操作
char Get(List *list,int pos){
char ret =-1;
// 1. 判断list的合法性
// 2. 判断位置的合法性
if((list!=NULL)&&(0<=pos)&&(pos<list->length)) // 3. 获得元素
ret = list->node[pos];
return ret;
}
插⼊元素的操作
算法：
1.判断线性表的合法性
2.判断插⼊位置的合法性
3.把最后⼀个元素到插⼊位置的元素依次后移⼀个位置
4.将新元素插⼊
5.将长度加1
int Insert(List *list,char c,int pos){
int ret =(list!=NULL);
int i =0;
ret = ret &&(list->length <= MAXSIZE);
ret = ret &&(0<=pos);
if( ret ){
if( pos > list->length)
pos = list->length;
for(i=list->length; i>pos; i--)
list->node[i]= list->node[i-1];
list->node[i]= c;
list->length++;
}
return ret;
}
删除元素操作
算法：
1.判断线性表的合法性
2.判断删除位置的合法性
3.将元素取出
4.将删除位置之后的所有元素都向前移动⼀个位置
5.顺序表的长度-1
har Delete(List *list,int pos){
char ret =-1;
int i =0;
if((list!=NULL)&&(0<=pos)&&(pos<list->length)){
ret = list->node[pos];
for(i=pos+1; i<list->length; i++)
list->node[i-1]= list->node[i];
list->length--;
}
return ret;
}
优点：可以快速的获取表中合法位置的元素
缺点：插⼊和删除的时候需要移动⼤量的元素
链式存储结构
定义：
为了表⽰每个数据元素与其直接后继元素之间的逻辑关系，每个元素除了存储本⾝的信息外，还要保存指⽰其直接后继的信息。n个节点链接成的⼀个链式线性表的结构叫链表，当每个节点中只包含⼀个指针域时，叫单链表
基本概念:
表头节点：链表中的第⼀个节点，包含指向第⼀个数据元素的指针以及链表⾃⾝的⼀些信息
数据节点：链表中代表数据元素的节点，包含指向下⼀个数据元素的指针和数据元素的信息。
尾节点：链表中的最后⼀个数据节点，其下⼀个元素指针为空。表⽰⽆后继。
C语⾔中可以⽤结构体来定义链表中的指针域
链表中的头节点也可以⽤结构体实现
typedef struct _node{
struct _node * node;
}LinkListNode;
typedef struct _linklist {
LinkListNode header;
int length;
}LinkList;
struct Value {
LinkListNode header;
int v;
}
获取第pos个元素的操作
//让cur指向头节点，
for(i=0; i<pos; i++)
cur=cur->next;
cur->next;
//就是我们所要的节点
插⼊操作
LinkList *cur = list;
for(i=0; i<pos; i++)
cur = cur->next;
node->next = cur->next;
cur->next = node;
list->length++;
删除操作
LinkList *cur = list;
LinkList *ret =NULL;
for(i=0; i<pos; i++)
cur = cur->next;
ret = cur->next;
cur->next = ret->next;
list->length--;
双列表列表
typedef struct _node {
struct _node *pre;
struct _node *next;
int item;
}DLinkListNode;
typedef struct _linklist {
DLinkListNode header;
int length;
}DLinkList;
单向循环链表
操作就是单链表的所有操作
创建
销毁
清空
插⼊
删除
获得
游标：在循环链表中定义⼀个"当前"指针，这个指针通常称为游标，可以通过游标访问链表中的所有元素。
新增：
获得当前游标指向的数据元素
将游标重置指向链表中的第⼀个元素
将游标移动指向到链表中的下⼀个元素
直接指定删除链表中的某个元素
typedef struct _node{
struct _node *next;
int item;
}CircleListNode;
typedef struct _linklist {
CircleListNode header;
CircleListNode *slider;
int length;
}CircleList;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。