线性表
线性表是最基本、最简单，也是最常用的一种数据结构。
一个线性表(linear list)是n个具有相同特性的数据元素的有限序列。
数据元素之间的关系是一对一。
线性、非线性是在逻辑层次上讨论，不考虑存储层次
顺序表
顺序存储，逻辑相邻，物理存储地址也相邻
0.数据结构声明
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
/* ElementType类型根据实际情况而定，这里假设为int */
typedef int ElementType;
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;
//顺序表结构设计
typedef struct {
ElementType *data;
int length;
}Sequencelist;
1.顺序表初始化
Status InitList(Sequencelist *list){
//为顺序表分配一个大小为MAXSIZE 的数组空间
list->data = malloc(sizeof(ElementType) * MAXSIZE);
//存储分配失败退出
if(!list->data) exit(ERROR);
//空表长度为0
list->length = 0;
return OK;
}
2.插入
Status ListInsert(Sequencelist *list,int i,ElementType e){
//i值不合法判断
if((i<1) || (i>list->length+1)) return ERROR;
//存储空间已满
if(list->length == MAXSIZE) return ERROR;
//插入数据不在表尾,则先移动出空余位置
if(i <= list->length){
for(int j = list->length-1; j>=i-1;j--){
//插入位置以及之后的位置后移动1位
list->data[j+1] = list->data[j];
}
}
//将新元素e 放入第i个位置上
list->data[i-1] = e;
//长度+1;
++list->length;
return OK;
}
3.清空
Status ClearList(Sequencelist *list)
{
list->length=0;
return OK;
}
单链表
链式存取，用一组地址任意的存储单元存放线性表中的数据元素
此处我们引入了头结点，哨兵
0.数据结构声明
结点
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
/* ElementType类型根据实际情况而定，这里假设为int */
typedef int ElementType;
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;
//单链表结构设计
typedef struct {
ElementType data;//数据
struct Node *next;//指针域
}Node;
typedef struct Node * LinkList;
1.初始化
单链表
Status InitList(LinkList *list){
//初始化哨兵，听起来高大上
*list = (LinkList)malloc(sizeof(Node));
//存储空间分配失败
if(*list == NULL) return ERROR;
//将头结点的指针域置NULL
(*list)->next = NULL;
return OK;
}
2.遍历Traverse
Status ListTraverse(LinkList list)
{
LinkList p = list->next;
while(p)
{
printf("%d\n",p->data);
p = p->next;
}
return OK;
}
3.单链表前插法
前插法
/* 随机产生n个元素值,加入单链线性表list*/
void InsertListFromHead(LinkList *list, int n){
LinkList p;
//初始化哨兵单链表
*list = (LinkList)malloc(sizeof(Node));
(*list)->next = NULL;
//循环 前插入随机数据
for(int i = 0; i < n; i++)
{
//生成新结点
p = (LinkList)malloc(sizeof(Node));
//i赋值给新结点的data
p->data = i;
//p->next = 头结点的L->next
p->next = (*list)->next;
//将结点P插入到头结点之后;
(*list)->next = p;
}
}
4.单链表后插法
后插法
/* 随机产生n个元素值,加入单链线性表list*/
void InsertListFromTail(LinkList *list, int n){
LinkList p,r;
//初始化哨兵单链表
*list = (LinkList)malloc(sizeof(Node));
//r指向尾部的结点
r = *list;
for (int i = 0; i < n; i++) {
//生成新结点
p = (Node *)malloc(sizeof(Node));
p->data = i;
//将表尾终端结点的指针指向新结点
r->next = p;
//将当前的新结点定义为表尾终端结点
r = p;
}
//将尾指针的next = null
r->next = NULL;
}
