a、顺序表
b、链表
c、两种线性表的比较
a、单链表
1. 每一个节点中除了包含数据域外，还包含一个指针域，用以指向后继节点，图为带头节点的单链表，带头节点的单链表中的头指针head指向头节点，头节点的值域不包含任何信息，从头节点的后继节点开始存储信息，头指针head始终不等于NULL，head->next等于NULL的时候链表为空；不带头节点的单链表中的头指针head直接指向开始节点，当head等于NULL的时候链表为空，
b、双链表
1. 单链表只能由开始节点走到终端节点，而不能由终端节点走向开始节点，而双链表可以实现，双链表就是在单链表节点上增添了一个指针域，指向当前节点的前驱
c、循环单链表
1. 只要将单链表的最后一个指针域指向链表中的第一个节点即可，可以实现从任何一个节点出发访问链表中的任何节点。
d、循环双链表
e、静态链表
a、顺序表的结构定义
1 #define maxSize 100 2 typedef struct 3 { 4 int data[maxSize]; //存放顺序表元素的数组 5 int length; //存放顺序表的长度 6 }Sqlist; //顺序表类型的定义
b、单链表的节点定义
typedef struct LNode { int data; //data中存放节点数据域 struct LNode * next; //指向后继节点的指针 }LNode; //定义单链表节点类型
c、双链表的节点定义
typedef struct DLNode { int data； struct DLNode *prior； //前驱 struct DLNode *next; //后继 }DLNode;
例题1
已知一个顺序表L，其中的元素已经按照递增排序，设计一个算法，插入一个元素x后保持该顺序表仍然递增有序排列。
分析：1. 要找出可以让顺序表保持有序的插入位置
2.将第一步找出的位置上及其后的元素往后移动一个位置，然后将x放至腾出的位置上
3.为了方便操作，数组元素的存放从下标1开始
int LocateElem(Sqlist L, int x) //找到要插入的位置 { int i; for(i=1; i<L.length;++i) if(x<L.data[i]) { return i; } return i; }
void insert(Sqlist &L, int x) //因为L本身要发生变化，所以使用引用型
{
int p, i;
p=LocateElem(L, x);
for(i=L.length; i>=p; --i)
{
L.data[i+1] = L.data[i];
L.data[p] = x;
++(L.length);
}
}
例题2
A和B是两个单链表（带表头结点），其中元素递增有序。设计一个算法将A和B归并成一个按照元素值非递减有序的链表C，C由A，B中的节点组成
typedef struct LNode { int data; //data中存放节点数据域 struct LNode * next; //指向后继节点的指针 }LNode; //定义单链表节点类型 void merge(LNode *A, LNode *B, LNode *C) { LNode *p = A->next; //p来跟踪A的最小节点 LNode *q = B->next; //q来跟踪B的最小节点 LNode *r; //r始终指向C的终端节点 C=A; //A的头节点来做C的头节点 C->next = NULL; free(B); r=C; //r指向C，因为此时头节点也是终端节点 while(p != NULL && q != NULL) //qp都不为空，选取较小的节点插入C的尾部 { if(p->data <= q->data) { r->next = p;p = p->next; r = r->next; } else { r->next = q;q = q->next; r = r->next; } } r->next = NULL; if(p != NULL) r->next = p; if(q != NULL) r->next = q; }
例题3
假设有n个元素已经存储在数组a中，用尾插法建立链表C
void CreatelistR(LNode *&C, int a[], int n) { LNode *s, *r; //s用来指向新申请的节点，r始终指向c的终端节点 int i; C=(LNode *)malloc(size(LNode)); //申请C的头节点空间 C->next = NULL; r=C; //r指向头节点，因为此时头节点就是终端节点 for(i=1; i<=n; ++i) //循环申请n个节点来接受数组a中的元素 { s = (LNode*)malloc(sizeof(LNode)); //s指向新申请的节点 s->data = a[i]; //用新申请的节点来接收a中的一个元素 r->next = s; //用r来接纳新节点 r = r->next; //r指向终端节点，以便于接纳下一个到来的节点 } r->next = NULL; //a中所有的元素都已经装入链表中，C的终端节点的指针域置为NULL，C建立完成 }
头插法
typedef struct LNode { int data; //data中存放节点数据域 struct LNode * next; //指向后继节点的指针 }LNode; void CreatelistF(LNode *&C, int a[], int n) { LNode *s; int i; C=(LNode *)malloc(size(LNode)); //申请C的头节点空间 C->next = NULL; for(i=1; i<=n; ++i) { s = (LNode*)malloc(sizeof(LNode)); //s指向新申请的节点 s->data = a[i]; s->next = C->next; //s所指新节点的指针域next指向C的开始节点 C->next = s; //头节点的指针域next指向s节点，使得s成为了新的开始节点 } }
原文：https://www.cnblogs.com/ai-bingjie/p/13699055.html